Strong price of anarchy

ABSTRACT

A strong equilibrium (Aumann 1959) is a pure Nash equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy to be the ratio of the worst case strong equilibrium to the social optimum. In contrast to the traditional price of anarchy, which quantifies the loss incurred due to both selfishness and lack of coordination, the strong price of anarchy isolates the loss originated from selfishness from that obtained due to lack of coordination. We study the strong price of anarchy in two settings, one of job scheduling and the other of network creation. In the job scheduling game we show that for unrelated machines the strong price of anarchy can be bounded as a function of the number of machines and the size of the coalition. For the network creation game we show that the strong price of anarchy is at most 2. In both cases we show that a strong equilibrium always exists, except for a well defined subset of network creation games.

REFERENCES

• 1: Susanne Albers , Stefan Eilts , Eyal Even-Dar , Yishay Mansour , Liam Roditty, On nash equilibria for a network creation game, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.89-98, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109568]
• 2: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 3: R. Aumann. Acceptable Points in General Cooperative n-Person Games. In Contributions to the Theory of Games, volume 4, 1959.
• 4: B. Awerbuch, Y. Azar, Y. Richter, and D. Tsur. Tradeoffs in Worst-Case Equilibria. In 1st International Workshop on Approximation and Online Algorithms, 2003.
• 5: D. B. Bernheim, B. Peleg, and M. D. Whinston. Coalition-proof nash equilibria: I concepts. Journal of Economic Theory, 42:1--12, 1987.
• 6: Jacomo Corbo , David Parkes, The price of selfish behavior in bilateral network formation, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073833]
• 7: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 8: E. Even-Dar, A. Kesselman, and Y. Mansour. Convergence time to nash equilibria. In ICALP, pages 502--513, 2003.