Thesis defense of Veerle Timmermans, February 1, 2019


On Friday, February 1, 2019, Veerle Timmermans will defend her PhD thesis “Uniqueness and Computation of Equilibria in Resource Allocation Games”. This thesis has been supervised by prof.dr. T. Harks (Augsburg University) and prof.dr.ir C.P.M. van Hoesel. The ceremony will take place at Minderbroedersberg 4-6 at Maastricht University at 10:00 hrs.

Abstract

Game theory is the study of conflict and cooperation between rational decision makers, or players, within a competitive environment. It offers a framework in which the strategic interaction between players can be modeled, which is used to understand the behavior of these players in practice. A strategic game always consists out of three elements: a collection of players, a collection of available strategies for each player, and a utility function for each player. The utility function for a player assigns, depending on all the chosen strategies, a utility value to that specific player. A resource allocation game is a special type of game, where players compete over a finite set of sparse resources. In this thesis we discuss two types of resource allocation games: atomic splittable congestion games and multimarket oligopolies.

One of the most important tools that game theorists have at their disposal is the Nash equilibrium: a set of strategies that players act out, with the property that no player benefits from an unilateral deviation. Intuitively, this means that if a player is told the strategies of all her opponents, she would still choose to retain her original strategy. Hence, as a player it is in your best interest to choose your strategy according to a Nash equilibrium. After all, if all other players do the same, and choose their strategy according to the same Nash equilibrium, this is the strategy that maximizes your utility.

For both atomic splittable congestion games and multimarket oligopolies it is known that Nash equilibria always exist. In this thesis we focus on two questions in particular: when does a game has a unique, pure Nash equilibrium? And can we compute this Nash equilibrium efficiently?