University of Twente Student Theses


The quality of equilibria in generalized market sharing games

Brethouwer, J.F. (2018) The quality of equilibria in generalized market sharing games.

[img] PDF
Abstract:We analyze the quality of several equilibria for generalized market sharing games. Generalized market sharing games model n selfish players selecting subsets of a finite set of items, where the payoff of an item is divided among all players choosing that item. Market sharing games are a special case of this, where the available subsets are restricted by budget constraints. Market sharing games were studied by Goemans, who showed that the price of anarchy is at most 2 by showing that those games are valid utility games. We show that generalized market sharing games are valid utility games as well, yet sharpen the bounds on the price of anarchy further to show that it is exactly equal to 2-1/n. We do this using a smoothness argument, allowing this price of anarchy to extend to different equilibria. These tight bounds also holds for symmetric or singleton adaptations. Furthermore we study the sequential version of the game and define a class of games called shared misery games. For this class of games we set up a framework which can be used to provide upper bounds on the sequential price of anarchy.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page