University of Twente Student Theses

Login

The quality of equilibria in generalized market sharing games

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

[img]
Preview
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:http://purl.utwente.nl/essays/76986
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page