zbMATH — the first resource for mathematics

Pairwise-interaction games. (English) Zbl 1332.68071
Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 159-170 (2011).
Summary: We study the complexity of computing Nash equilibria in games where players arranged as the vertices of a graph play a symmetric 2-player game against their neighbours. We call this a pairwise-interaction game. We analyse this game for \(n\) players with a fixed number of actions and show that (1) a mixed Nash equilibrium can be computed in constant time for any game, (2) a pure Nash equilibrium can be computed through Nash dynamics in polynomial time for games with a symmetrisable payoff matrix, (3) determining whether a pure Nash equilibrium exists for zero-sum games is NP-complete, and (4) counting pure Nash equilibria is #P-complete even for 2-strategy games. In proving (3), we define a new defective graph colouring problem called Nash colouring, which is of independent interest, and prove that its decision version is NP-complete. Finally, we show that pairwise-interaction games form a proper subclass of the usual graphical games.
For the entire collection see [Zbl 1217.68003].

68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91A10 Noncooperative games
91A43 Games involving graphs
Full Text: DOI
[1] Ackermann, H., Roglin, H., Vocking, B.: On the impact of combinatorial structure on congestion games. In: Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 613–622 (2006) · doi:10.1109/FOCS.2006.55
[2] Àlvarez, C., Gabarró, J., Serna, M.: Pure Nash equilibria in games with a large number of actions. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 95–106. Springer, Heidelberg (2005) · Zbl 1156.91308 · doi:10.1007/11549345_10
[3] Berninghaus, S.K., Haller, H.: Pairwise interaction on random graphs, Tech. Report 06–16, Sonderforschungsbereich 504, University of Mannheim (February 2007) · Zbl 1311.91056
[4] Bhalgat, A., Chakraborty, T., Khanna, S.: Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games. In: Proceedings of the 11th ACM Conference on Electronic Commerce (EC 2010), pp. 73–82 (2010) · doi:10.1145/1807342.1807353
[5] Brandt, F., Fischer, F., Holzer, M.: Equilibria of graphical games with symmetries. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 198–209. Springer, Heidelberg (2008) · Zbl 05496534 · doi:10.1007/978-3-540-92185-1_27
[6] Brandt, F., Fischer, F., Holzer, M.: Symmetries and the complexity of pure Nash equilibrium. Journal of Computer and System Sciences 75, 163–177 (2009) · Zbl 1154.91352 · doi:10.1016/j.jcss.2008.09.001
[7] Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 261–272 (2006) · doi:10.1109/FOCS.2006.69
[8] Cheng, S., Reeves, D.M., Vorobeychik, Y., Wellman, M.P.: Notes on the equilibria in symmetric games. In: Proceedings of the 6th International Workshop on Game Theoretic and Decision Theoretic Agents (GTDT 2004), pp. 71–78 (2004)
[9] Conitzer, V., Sandholm, T.: New complexity results about Nash equilibria. Games and Economic Behavior 63, 621–641 (2008) · Zbl 1142.91365 · doi:10.1016/j.geb.2008.02.015
[10] Cowen, L.J., Goddard, W., Jesurum, C.E.: Defective coloring revisited. J. Graph Theory 24, 205–219 (1995) · Zbl 0877.05019 · doi:10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T
[11] Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. Commun. ACM 52, 89–97 (2009) · Zbl 05747703 · doi:10.1145/1461928.1461951
[12] Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), pp. 604–612 (2004) · Zbl 1192.91042 · doi:10.1145/1007352.1007445
[13] Fischer, F., Holzer, M., Katzenbeisser, S.: The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria. Information Processing Letters 99, 239–245 (2006) · Zbl 1185.91027 · doi:10.1016/j.ipl.2006.03.010
[14] Gilboa, I., Zemel, E.: Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior 1, 80–93 (1989) · Zbl 0755.90093 · doi:10.1016/0899-8256(89)90006-7
[15] Halldórsson, M.M., Lau, H.C.: Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring. Journal of Graph Algorithms and Applications 1, 1–13 (1997) · Zbl 0891.05061 · doi:10.7155/jgaa.00003
[16] Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences of the United States of America 79, 2554–2558 (1982) · Zbl 1369.92007 · doi:10.1073/pnas.79.8.2554
[17] Kaplansky, I.: A contribution to von Neumann’s theory of games. The Annals of Mathematics 46, 474–479 (1945) · Zbl 0063.03139 · doi:10.2307/1969164
[18] Kearns, M.J., Littman, M.L., Singh, S.P.: Graphical models for game theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence (UAI 2001), pp. 253–260 (2001)
[19] Leven, D., Galil, Z.: NP-completeness of finding the chromatic index of regular graphs. Journal of Algorithms 4, 35–44 (1983) · Zbl 0509.68037 · doi:10.1016/0196-6774(83)90032-9
[20] Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14, 124–143 (1996) · Zbl 0862.90137 · doi:10.1006/game.1996.0044
[21] Nash, J.: Non-cooperative games. The Annals of Mathematics 54, 286–295 (1951) · Zbl 0045.08202 · doi:10.2307/1969529
[22] Nowak, M.A., May, R.M.: Evolutionary games and spatial chaos. Nature 359, 826–829 (1992) · doi:10.1038/359826a0
[23] Papadimitriou, C.H., Roughgarden, T.: Computing equilibria in multi-player games. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 82–91 (2005) · Zbl 1297.91005
[24] Santos, F.C., Rodrigues, J.F., Pacheco, J.M.: Graph topology plays a determinant role in the evolution of cooperation. Proceedings of the Royal Society B: Biological Sciences 273, 51–55 (2006) · doi:10.1098/rspb.2005.3272
[25] Schäffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20, 56–87 (1991) · Zbl 0716.68048 · doi:10.1137/0220004
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.