PhD Defense Pieter Kleer

Pieter's promotors are Guido Schaefer and Lex Schrijver.

 

The defense will take place at 15:45 hrs in the Aula of the VU Amsterdam (De Boelelaan 1105, 1081 HV Amsterdam).

 

As from October 2019 Pieter will be joining the Max-Planck-Institut für Informatik in Saarbrucken as a postdoc.

 

Abstract

This thesis focuses on two problems at the intersection of mathematics and theoretical computer science: the computation and inefficiency of pure Nash equilibria in congestion models, as well as the uniform generation of graphs with a given degree sequence.

 

Nash equilibria are stable outcomes of a game with players who all have different (selfish) interests. An important aspect is to quantify how 'inefficient' such outcomes are, as a result of this selfish behavior (compared to a centralized outcome). This can be done using the so-called Price of Anarchy. In this thesis we provide various unifications and extensions of many works in the literature regarding the polynomial time computation of Nash equilibria, as well as bounds on this Price of Anarchy.

 

For the second problem, we make progress on the analysis of the so-called switch Markov chain for sampling graphs with a given degree sequence. This is a very simple procedure to randomize graphs while preserving the degree sequence. It starts with some graph with the given degree sequence and repeatedly chooses two edges uniformly at random that are switched, if possible. Such an operation indeed preserves the degree sequence. A major open question is to give good upper bounds on the number of switches that is needed to get close to a uniform sample from the set of all graphs with the given degree sequence. We make some progress on this problem, as well as two related Markov chains.

 

Pieter received the cum laude distinction for his thesis, you can read more about this here.

You can read the thesis here.