On the complexity of Pareto-optimal Nash and strong equilibria. (English) Zbl 1310.91043
Kontogiannis, Spyros (ed.) et al., Algorithmic game theory. Third international symposium, SAGT 2010, Athens, Greece, October 18–20, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-16169-8/pbk). Lecture Notes in Computer Science 6386, 312-322 (2010).
Summary: We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Pareto-optimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Pareto-optimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of player-specific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Pareto-optimal Nash and strong equilibria that can be computed efficiently.
For the entire collection see [Zbl 1197.68014].
For the entire collection see [Zbl 1197.68014].
MSC:
| 91A43 | Games involving graphs |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structure on congestion games. J. ACM 55(6) (2008) · Zbl 1325.91010 · doi:10.1145/1455248.1455249 |
| [2] | Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. Games Econ. Behav. 65(2), 289–317 (2009) · Zbl 1156.91419 · doi:10.1016/j.geb.2008.03.005 |
| [3] | Aumann, R.: Acceptable points in general cooperative n-person games. In: Contributions to the Theory of Games IV. Annals of Mathematics Study, vol. 40, pp. 287–324 (1959) · Zbl 0085.13005 · doi:10.1515/9781400882168-018 |
| [4] | Blonski, M.: Anonymous games with binary actions. Games Econ. Behav. 28, 171–180 (1999) · Zbl 0937.91019 · doi:10.1006/game.1998.0699 |
| [5] | Blonski, M.: Characterization of pure strategy equilibria in finite anonymous games. J. Math. Econ. 34(2), 225–233 (2000) · Zbl 0962.91003 · doi:10.1016/S0304-4068(99)00008-7 |
| [6] | Brandt, F., Fischer, F., Holzer, M.: Symmetries and the complexity of pure Nash equilibrium. J. Comput. Syst. Sci. 75(3), 163–177 (2009) · Zbl 1154.91352 · doi:10.1016/j.jcss.2008.09.001 |
| [7] | Chien, S., Sinclair, A.: Strong and Pareto price of anarchy in congestion games. In: Proc. 36th Intl. Coll. Automata, Languages and Programming (ICALP), pp. 279–291 (2009) · Zbl 1248.91009 · doi:10.1007/978-3-642-02927-1_24 |
| [8] | Daskalakis, C., Papadimitriou, C.: Computing equilibria in anonymous games. In: Proc. 48th Symp. Foundations of Computer Science (FOCS), pp. 83–93 (2007) · doi:10.1109/FOCS.2007.24 |
| [9] | Daskalakis, C., Papadimitriou, C.: Discretized multinomial distributions and Nash equilibria in anonymous games. In: Proc. 49th Symp. Foundations of Computer Science (FOCS), pp. 25–34 (2008) · doi:10.1109/FOCS.2008.84 |
| [10] | Dunkel, J., Schulz, A.: On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. Math. Oper. Res. 33(4), 851–868 (2008) · Zbl 1231.91010 · doi:10.1287/moor.1080.0322 |
| [11] | Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure Nash equilibria. In: Proc. 36th Symp. Theory of Computing (STOC), pp. 604–612 (2004) · Zbl 1192.91042 · doi:10.1145/1007352.1007445 |
| [12] | Gottlob, G., Greco, G., Scarcello, F.: Pure Nash equilibria: Hard and easy games. J. Artif. Intell. Res. 24, 195–220 (2005) · Zbl 1134.91312 |
| [13] | Harks, T., Hoefer, M., Klimm, M., Skopalik, A.: Computing pure Nash and strong equilibria in bottleneck congestion games. In: Proc. 18th European Symposium on Algorithms, ESA (to appear 2010) · Zbl 1287.91004 · doi:10.1007/978-3-642-15781-3_3 |
| [14] | Harks, T., Klimm, M., Möhring, R.H.: Strong Nash equilibria in games with the lexicographical improvement property. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 463–470. Springer, Heidelberg (2009) · doi:10.1007/978-3-642-10841-9_43 |
| [15] | Holzman, R., Law-Yone, N.: Strong equilibrium in congestion games. Games Econ. Behav. 21(1-2), 85–101 (1997) · Zbl 0899.90169 · doi:10.1006/game.1997.0592 |
| [16] | Konishi, H., Breton, M.L., Weber, S.: Equilibria in a model with partial rivalry. J. Econ. Theory 72(1), 225–237 (1997) · Zbl 0883.90128 · doi:10.1006/jeth.1996.2203 |
| [17] | Mas-Colell, A., Whinston, M., Green, J.: Microeconomic Theory. Oxford University Press, Oxford (1995) · Zbl 1256.91002 |
| [18] | Meyers, C.: Network Flow Problems and Congestion Games: Complexity and Approximation Results. PhD thesis, MIT (June 2006) |
| [19] | Milchtaich, I.: Congestion games with player-specific payoff functions. Games Econ. Behav. 13(1), 111–124 (1996) · Zbl 0848.90131 · doi:10.1006/game.1996.0027 |
| [20] | Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. Intl. J. Game Theory 2, 65–67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559 |
| [21] | Rozenfeld, O., Tennenholtz, M.: Strong and correlated strong equilibria in monotone congestion games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 74–86. Springer, Heidelberg (2006) · doi:10.1007/11944874_8 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
