The quality of equilibria in generalized market sharing games

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.