Refined Models and Coordination Mechanisms for Network Games

Most fundamental network games are nowadays well-understood from a purely analytical point of view. In particular, in the last decade the analysis of the inefficiency of equilibria (price of anarchy, price of stability and related notions) constituted one of the main research directions in algorithmic game theory. The goal of the project is to further advance our understanding of network games by (i) studying more refined models and (ii) investigating means to reduce the inefficiency.
To (i), most studies assume that the input data of a network game is given *deterministically*, where it would be more realistic to consider stochastic models. Our goal is to study risk-averse players in network games.
To (ii): For many fundamental network games it has been shown that strategic behavior has a negative impact in the sense that it leads to a large inefficiency. We aim at developing coordination mechanisms to reduce this inefficiency using more realistic models.
For both (i) and (ii), a natural pool of games which we will consider are network routing games, network cost sharing games and network formation games.
Supervisors Guido Schaefer (CWI/VUA), Lex Schrijver (CWI/UvA)
Phd student Pieter Kleer
Location Center for Mathematics and Computer Science (CWI)