More Web Proxy on the site http://driver.im/

research-article

Coordination Games on Weighted Directed Graphs

Authors:

Krzysztof R. Apt,

Sunil Simon, Dominik WojtczakAuthors Info & Claims

Mathematics of Operations Research, Volume 47, Issue 2

Pages 995 - 1025

https://doi.org/10.1287/moor.2021.1159

Published: 01 May 2022 Publication History

Abstract

We study strategic games on weighted directed graphs, where each player’s payoff is defined as the sum of the weights on the edges from players who chose the same strategy, augmented by a fixed nonnegative integer bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. We identify natural classes of graphs for which finite improvement or coalition-improvement paths of polynomial length always exist, and consequently a (pure) Nash equilibrium or a strong equilibrium can be found in polynomial time. The considered classes of graphs are typical in network topologies: simple cycles correspond to the token ring local area networks, whereas open chains of simple cycles correspond to multiple independent rings topology from the recommendation G.8032v2 on Ethernet ring protection switching. For simple cycles, these results are optimal in the sense that without the imposed conditions on the weights and bonuses, a Nash equilibrium may not even exist. Finally, we prove that determining the existence of a Nash equilibrium or of a strong equilibrium is NP-complete already for unweighted graphs, with no bonuses assumed. This implies that the same problems for polymatrix games are strongly NP-hard.

References

[1]

Ackermann H, Roglin H, Vöcking B (2008) On the impact of combinatorial structure on congestion games. J. ACM 55(6):1–22.

[2]

Apt KR, Markakis E (2011) Diffusion in social networks with competing products. Persiano G, ed. Algorithmic Game Theory. Lecture Notes in Computer Science, vol. 6982 (Springer, Berlin), 212–223.

[3]

Apt KR, Shoja E (2018) Self-stabilization through the lens of game theory. It’s All About Coordination—Essays to Celebrate the Lifelong Scientific Achievements of Farhad Arbab. Lecture Notes in Computer Science, vol. 10865 (Springer, Cham, Switzerland), 21–37.

[4]

Apt KR, Simon S (2012) A classification of weakly acyclic games. Serna M, ed. Algorithmic Game Theory. Lecture Notes in Computer Science, vol. 7615 (Springer, Berlin), 1–12.

[5]

Apt KR, Simon S (2015) A classification of weakly acyclic games. Theory Decision 4(78):501–524.

[6]

Apt KR, Simon S, Wojtczak D (2016) Coordination games on directed graphs. Proc. 15th Conf. Theoret. Aspects Rationality Knowledge. Electronic Proceedings in Theoretical Computer Science, vol. 215 (Open Publishing Association, Waterloo, Australia), 67–80.

[7]

Apt KR, Rahn M, Schäfer G, Simon S (2014) Coordination games on graphs (extended abstract). Proc. 10th Conf. Web Internet Econom. Liu TY, Qi Q, Ye Y, eds. Lecture Notes in Computer Science, vol. 8877 (Springer, Cham, Switzerland), 441–446.

[8]

Apt KR, de Keijzer B, Rahn M, Schäfer G, Simon S (2017) Coordination games on graphs. Internat. J. Game Theory. 46(3):851–877.

Digital Library

[9]

Aumann RJ (1959) Acceptable points in general cooperative n-person games. Luce RD, Tucker AW, eds. Contribution to the Theory of Games, Volume IV. Annals of Mathematical Study, vol. 40 (Princeton University Press, Princeton, NJ), 287–324.

[10]

Aziz H, Brandl F (2012) Existence of stability in hedonic coalition formation games. Conitzer, Winikoff, Padgham, van der Hoek, eds. Proc. 11th Internat. Conf. Autonomous Agents Multiagent Systems, Valencia, Spain (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 763–770.

Digital Library

[11]

Aziz H, Brandt F, Seedig HG (2010) Optimal partitions in additively separable hedonic games. Walsh T, ed. Proc. 22nd Internat. Joint Conf. Artificial Intelligence, Barcelona, Catalonia, Spain (AAAI Press), 43–48.

[12]

Aziz H, Brandt F, Seedig HG (2011) Stable partitions in additively separable hedonic games. Tumer K, Yolum P, eds. Proc. 10th Internat. Conf. Autonomous Agents Multiagent Systems, Taipei, Taiwan (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 183–190.

[13]

Banerjee S, Konishi H, Sönmez T (2001) Core in a simple coalition formation game. Soc. Choice Welfare 18:135–153.

[14]

Bogomolnaia A, Jackson MO (2002) The stability of hedonic coalition structures. Games Econom. Behav. 38(2):201–230.

[15]

Brokkelkamp KR, Vries MJ (2012) Convergence of ordered paths in generalized congestion games. Serna M, ed. Algorithmic Game Theory. Lecture Notes in Computer Science, volume 7615 (Springer, Berlin), 61–71.

[16]

Cai Y, Daskalakis C (2011) On minmax theorems for multiplayer games. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Association for Computing Machinery), 217–234.

[17]

Dijkstra EW (1974) Self-stabilizing systems in spite of distributed control. Comm. ACM 17(11):643–644.

Digital Library

[18]

Engelberg R, Schapira M (2011) Weakly-acyclic (internet) routing games. Persiano G, ed. Algorithmic Game Theory. Lecture Notes in Computer Science, vol. 6982 (Springer, Berlin), 290–301.

[19]

Engelberg R, Schapira M (2014) Weakly-acyclic (internet) routing games. Theory Comput. Systems 54(3):431–452.

Digital Library

[20]

Escoffier B, Gourvès L, Monnot J (2012) Strategic coloring of a graph. Internet Math. 8(4):424–455.

[21]

Fabrikant A, Papadimitriou C (2008) The complexity of game dynamics: BGP oscillations, sink equilibria and beyond. Shang-Hua T, ed. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms, San Francisco, California (Association for Computing Machinery, New York), 844–853.

[22]

Fabrikant A, Jaggard A, Schapira M (2013) On the structure of weakly acyclic games. Theory Comput. Systems 53:107–122.

[23]

Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure Nash equilibria. Babai L, ed. Proc. 36th ACM Sympos. Theory Comput., Chicago, IL (Association for Computing Machinery, New York), 604–612.

[24]

Gairing M, Savani R (2010) Computing stable outcomes in hedonic games. Kontogiannis S, Koutsoupias E, Spirakis PG, eds. Proc. Third Internat. Sympos. Algorithmic Game Theory, Athens, Greece (Springer, Berlin), 174–185.

Digital Library

[25]

Gourvès L, Monnot J (2009) On strong equilibria in the max cut game. Leonardi S, ed. Proc. Fifth Internat. Workshop on Internet and Network Econom., Rome, Italy. Lecture Notes in Computer Science, vol. 5929 (Springer-Verlag, Berlin), 608–615.

[26]

Gourvès L, Monnot J (2010) The max k-cut game and its strong equilibria. Kratochvíl J, Li A, Fiala J, Kolman P, eds. Theory and Applications of Models of Computation. Lecture Notes in Computer Science, vol. 6108 (Springer, Berlin), 234–246.

[27]

Granovetter M (1978) Threshold models of collective behavior. Amer. J. Sociol. 83(6):1420–1443.

[28]

Hajdukova J (2006) Coalition formation games: A survey. Internat. Game Theory Rev. 8(4):613–641.

[29]

Harks T, Klimm M, Möhring R (2013) Strong equilibria in games with the lexicographical improvement property. Internat. J. Game Theory 42(2):461–482.

Digital Library

[30]

Hoefer M (2007) Cost sharing and clustering under distributed competition. Unpublished PhD thesis, University of Konstanz, Konstanz, Germany.

[31]

Holzman R, Law-Yone N (1997) Strong equilibrium in congestion games. Games Econom. Behav. 21(1–2):85–101.

[32]

Kawald B, Lenzner P (2013) On dynamics in selfish network creation. Vöcking B, ed. Proc. 25th ACM Sympos. Parallelism Algorithms Architectures, Montréal, Québec, Canada (Association for Computing Machinery, New York), 83–92.

[33]

Konishi H, Le Breton M, Weber S (1997a) Equivalence of strong and coalition-proof Nash equilibria in games without spillovers. Econom. Theory 9(1):97–113.

[34]

Konishi H, Le Breton M, Weber S (1997b) Pure strategy Nash equilibrium in a group formation game with positive externalities. Games Econom. Behav. 21:161–182.

[35]

Levin H, Schapira M, Zohar A (2008) Interdomain routing and games. Dwork C, ed. Proc. 40th Annual ACM Sympos. Theory Comput., Victoria, British Columbia, Canada (Association for Computing Machinery, New York), 57–66.

[36]

Marden J, Arslan G, Shamma J (2007) Regret based dynamics: Convergence in weakly acyclic games. Huhns M, Shehory O, eds. Proc. Sixth Internat. Joint Conf. Autonomous Agents Multiagent Systems, Honolulu, Hawaii (Association for Computing Machinery, New York), 194–201.

[37]

Meir R, Polukarov M, Rosenschein JS, Jennings NR (2017) Iterative voting and acyclic games. Artificial Intelligence 252:100–122.

[38]

Milchtaich I (1996) Congestion games with player-specific payoff functions. Games Econom. Behav. 13:111–124.

[39]

Milchtaich I (2013) Schedulers, potentials and weak potentials in weakly acyclic games. Working Paper 2013-03, Department of Economics, Bar-Ilan University, Ramat Gan, Israel.

[40]

Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.

[41]

Panagopoulou PN, Spirakis PG (2008) A game theoretic approach for efficient graph coloring. Hong SH, Nagamochi H, Fukunaga T, eds. Algorithms and Computation. Lecture Notes in Computer Science, vol. 5369 (Springer, Berlin), 183–195.

[42]

Papadimitriou C, Roughgarden T (2008) Computing correlated equilibria in multi-player games. J. ACM 55(3):14.

Digital Library

[43]

Pelillo M, Buló SR (2014) Clustering games. Cipolla R, Battiato S, Farinella GM, eds. Registration and Recognition in Images and Videos. Studies in Computational Intelligence, vol. 532 (Springer, Berlin), 157–186.

[44]

Rahn M, Schäfer G (2015) Efficient equilibria in polymatrix coordination games. Italiano GF, Pighizzini G, Sannella D, eds. Mathematical Foundations of Computer Science, Milan, Italy. Lecture Notes in Computer Science, vol. 9235 (Springer, Berlin), 529–541.

[45]

Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1):65–67.

Digital Library

[46]

Rozenfeld O, Tennenholtz M (2006) Strong and correlated strong equilibria in monotone congestion games. Spirakis P, Mavronicolas M, Kontogiannis S, eds. Internet and Network Economics. Lecture Notes in Computer Science, vol. 4286 (Springer, Berlin), 74–86.

[47]

Rubinstein A (2018) Inapproximability of Nash equilibrium. SIAM J. Comput. 47(3):917–959.

Digital Library

[48]

Simon S, Apt KR (2015) Social network games. J. Logic Comput. 25(1):207–242.

[49]

Simon S, Wojtczak D (2016) Efficient local search in coordination games on graphs. Brewka G, ed. Proc. 25th Internat. Joint Conf. Artificial Intelligence, New York (AAAI Press, Palo Alto, CA), 482–488.

[50]

Simon S, Wojtczak D (2017a) Constrained pure Nash equilibria in polymatrix games. Singh S, Markovitch S, eds. Proc. 31st AAAI Conf. Artificial Intelligence, San Francisco (AAAI Press, Palo Alto, CA), 691–697.

[51]

Simon S, Wojtczak D (2017b) Synchronisation games on hypergraphs. Sierra C, ed. Proc. 26th Internat. Joint Conf. Artificial Intelligence, Melbourne, Australia (AAAI Press, Palo Alto, CA), 402–408.

[52]

Sless L, Hazon N, Kraus S, Wooldridge M (2014) Forming coalitions and facilitating relationships for completing tasks in social networks. Proc. 2014 Internat. Conf. Autonomous Agents Multi-agent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 261–268.

Digital Library

[53]

Wojtczak D (2018) On strong NP-completeness of rational problems. Fomin FV, Podolskii VV, eds. Proc. Internat. Comput. Sci. Sympos., Moscow, Russia (Springer, Cham, Switzerland), 308–320.

[54]

Yanovskaya E (1968) Equilibrium points in polymatrix games. Litovskii Matematicheskii Sbornik 8:381–384.

[55]

Young HP (1993) The evolution of conventions. Econometrica 61(1):57–84.

Cited By

Deligkas AEiben EGutin GNeary PYeo AElkind E(2023)Complexity of efficient outcomes in binary-action polymatrix games and implications for coordination problemsProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/294(2642-2650)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/294

Index Terms

Coordination Games on Weighted Directed Graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design

Index terms have been assigned to the content through auto-classification.

Recommendations

Loss of skills in coordination games
Abstract
This paper deals with 2-player coordination games with vanishing actions, which are repeated games where all diagonal payoffs are strictly positive and all non-diagonal payoffs are zero with the following additional property: At any stage beyond r,...
Coordination games on graphs
Abstract
We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and ...
Strong equilibrium in cost sharing connection games
EC '07: Proceedings of the 8th ACM conference on Electronic commerce

In this work we study cost sharing connection games, where each player has a source and sink he would like to connect, and the cost of the edges is either shared equally (fair connection games) or in an arbitrary way (general connection games).We study ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 47, Issue 2

May 2022

860 pages

ISSN:0364-765X

DOI:10.1287/moor.2022.47.issue-2

Issue’s Table of Contents

Copyright © 2021, INFORMS.

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 2022

Accepted: 25 February 2021

Received: 11 April 2020

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Deligkas AEiben EGutin GNeary PYeo AElkind E(2023)Complexity of efficient outcomes in binary-action polymatrix games and implications for coordination problemsProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/294(2642-2650)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/294

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents