Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Strong Price of Anarchy, Utility Games and Coalitional Dynamics

Yoram Bachrach, Vasilis Syrgkanis, Eva Tardos, and Milan Vojnovic

Abstract

We introduce a framework for studying the effect of cooperation on the quality of outcomes in utility games. Our framework is a coalitional analog of the smoothness framework of non-cooperative games. Coalitional smoothness implies bounds on the strong price of anarchy, the loss of quality of coalitionally stable outcomes. Our coalitional smoothness framework captures existing results bounding the strong price of anarchy of network design games. Moreover, we give novel strong price of anarchy results for any monotone utility-maximization game, showing that if each player's utility is at least his marginal contribution to the welfare, then the strong price of anarchy is at most $2$. This captures a broad class of games, including games that have a price of anarchy as high as the number of players. Additionally, we show that in potential games the strong price of anarchy is close to the price of stability, the quality of the best Nash equilibrium.

We also initiate the study of the quality of coalitional out-of-equilibrium outcomes in games. To this end, we define a coalitional version of myopic best-response dynamics, and show that the bound on the strong price of anarchy implied by coalitional smoothness, also extends with small degradation to the average quality of outcomes of the given dynamic.

Details

Publication typeInproceedings
Published inSAGT 2014
URLhttp://sagt-2014.iew.technion.ac.il/
PublisherSpringer
> Publications > Strong Price of Anarchy, Utility Games and Coalitional Dynamics