×

zbMATH — the first resource for mathematics

Strong price of anarchy. (English) Zbl 1156.91419
Summary: A strong equilibrium is a pure Nash equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy (SPoA) to be the ratio of the worst strong equilibrium to the social optimum. Differently from the Price of Anarchy (defined as the ratio of the worst Nash Equilibrium to the social optimum), it quantifies the loss incurred from the lack of a central designer in settings that allow for coordination.
We study the SPoA in two settings, namely job scheduling and network creation. In the job scheduling game we show that for unrelated machines the SPoA 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 SPoA 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.

MSC:
91B52 Special types of economic equilibria
91A12 Cooperative games
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abraham I., Dolev, D., Gonen, R., Halpern, J., 2006. Distributed computing meets game theory: Robust mechanisms for rational secret sharing and multiparty computation. In: Symposium on Principles of Distributed Computing (PODC), pp. 53-62 · Zbl 1314.68051
[2] Albers, S., Elits, S., Even-Dar, E., Mansour, Y., Roditty, L., 2006. On Nash equilibria for a network creation game. In: Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 89-98 · Zbl 1192.91036
[3] Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T., 2004. The price of stability for network design with fair cost allocation. In: Annual Symposium on Foundations of Computer Science (FOCS), pp. 295-304 · Zbl 1173.91321
[4] Aumann, R., 1959. Acceptable points in general cooperative n-person games. In: Contributions to the Theory of Games, vol. 4 · Zbl 0085.13005
[5] Awerbuch, B.; Azar, Y.; Richter, Y.; Tsur, D., Tradeoffs in worst-case equilibria, Theoret. comput. sci., 361, 2-3, 200-209, (2006), (A preliminary version in the 1st International Workshop on Approximation and Online Algorithms, 2003.) · Zbl 1097.68012
[6] Bernheim, D.B.; Peleg, B.; Whinston, M.D., Coalition-proof Nash equilibria: I. concepts, J. econ. theory, 42, 1-12, (1987) · Zbl 0619.90090
[7] Christodoulou, G., Koutsoupias, E., 2005. On the price of anarchy and stability of correlated equilibria of linear congestion games. In: Annual European Symposium on Algorithms (ESA), pp. 59-70 · Zbl 1162.91305
[8] Corbo, J., Parkes, D., 2005. The price of selfish behavior in bilateral network formation. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 99-107 · Zbl 1314.91051
[9] Czumaj, A., Vöcking, B., 2002. Tight bounds for worst-case equilibria. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 413-420 · Zbl 1092.91508
[10] Dutta, B.; Mutuswami, S., Stable networks, J. econ. theory, 76, 322-344, (1997) · Zbl 0893.90043
[11] Epstein, A., Feldman, M.., Mansour, Y., 2007, Strong equilibrium in cost sharing connection games. In: ACM Conference on Electronic Commerce (EC), pp. 84-92 · Zbl 1168.91330
[12] Even-Dar, E., Kesselman, A., Mansour, Y., 2003. Convergence time to Nash equilibria. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 502-513 · Zbl 1039.68017
[13] Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C., Shenker, S., 2003. On a network creation game. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 347-351 · Zbl 1322.91013
[14] Fiat, A., Kaplan, H., Levy, M., Olonetsky, S., 2007. Strong price of anarchy for machine load balancing. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 583-594 · Zbl 1171.68390
[15] Fotakis, D., Kontogiannis, S., Spiraklis, P., 2006. Atomic congestion games among coalitions. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 573-584 · Zbl 1223.91015
[16] Goldberg, A.V., Hartline, J., 2005. Collusion-resistant mechanisms for single-parameter agents. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 620-629 · Zbl 1297.91079
[17] Hayrapetyan, A., Tardos, E., Wexler, T., 2006. The effect of collusion in congestion games. In: 38th ACM Symposium on Theory of Computing (STOC), pp. 89-98 · Zbl 1300.91006
[18] Holzman, R.; Law-Yone, N., Strong equilibrium in congestion games, Games econ. behav., 21, 85-101, (1997) · Zbl 0899.90169
[19] Holzman, R.; Law-Yone, N., Network structure and strong equilibrium in route selection games, Math. soc. sci., 46, 193-205, (2003) · Zbl 1064.91026
[20] Jackson, M., Survey of models of network formation: stability and efficiency. chapter 1, ()
[21] Koutsoupias, E., Papadimitriou, C.H., 1999. Worst-case equilibria. In: Symposium on Theoretical Aspects of Computer Science (STACS), pp. 404-413 · Zbl 1099.91501
[22] Kranton, R.; Minehart, D., A theory of buyer-seller networks, Amer. econ. rev., 91, 485-508, (2001)
[23] Kuniavsky, S., Smorodinsky, R., 2007. Coalitional congestion games. MSc thesis. Technion, Israel · Zbl 1288.91012
[24] Milchtaich, I., Crowding games are sequentially solvable, Int. J. game theory, 27, 501-509, (1998) · Zbl 0943.91011
[25] Monderer, D.; Shapley, L.S., Potential games, Games econ. behav., 14, 124-143, (1996) · Zbl 0862.90137
[26] Montgomery, J., Social networks and labor market outcomes, Amer. econ. rev., 81, 1408-1418, (1991)
[27] Moulin, H.; Shenker, S., Strategyproof sharing of submodular costs: budget balance versus efficiency, J. econ. theory, 18, 511-533, (2001) · Zbl 1087.91509
[28] Papadimitriou, C.H., 2001. Algorithms, games, and the Internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 749-753 · Zbl 1323.68022
[29] Rosenthal, R.W., A class of games possessing pure-strategy Nash equilibria, Int. J. game theory, 2, 65-67, (1973) · Zbl 0259.90059
[30] Roughgarden, T.; Tardos, E., How bad is selfish routing?, J. ACM, 49, 2, 236-259, (2002) · Zbl 1323.90011
[31] Rozenfeld, O., Tennenholtz, M., 2006, Strong and correlated strong equilibria in monotone congestion games. Working paper. Technion, Israel
[32] Vetta, A.R., 2002, Nash equilibria in competitive societies with applications to facility location, traffic routing and auctions. In: Symposium on the Foundations of Computer Science (FOCS), pp. 416-425
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.