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.
|
PDF
374kB |
| 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: | https://purl.utwente.nl/essays/76986 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page