IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2311.03195.html
   My bibliography  Save this paper

Some coordination problems are harder than others

Author

Listed:
  • Argyrios Deligkas
  • Eduard Eiben
  • Gregory Gutin
  • Philip R. Neary
  • Anders Yeo

Abstract

In order to coordinate players in a game must first identify a target pattern of behaviour. In this paper we investigate the difficulty of identifying prominent outcomes in two kinds of binary action coordination problems in social networks: pure coordination games and anti-coordination games. For both environments, we determine the computational complexity of finding a strategy profile that (i) maximises welfare, (ii) maximises welfare subject to being an equilibrium, and (iii) maximises potential. We show that the complexity of these objectives can vary with the type of coordination problem. Objectives (i) and (iii) are tractable problems in pure coordination games, but for anti-coordination games are NP-hard. Objective (ii), finding the best Nash equilibrium, is NP-hard for both. Our results support the idea that environments in which actions are strategic complements (e.g., technology adoption) facilitate successful coordination more readily than those in which actions are strategic substitutes (e.g., public good provision).

Suggested Citation

  • Argyrios Deligkas & Eduard Eiben & Gregory Gutin & Philip R. Neary & Anders Yeo, 2023. "Some coordination problems are harder than others," Papers 2311.03195, arXiv.org, revised Nov 2023.
    • Handle: RePEc:arx:papers:2311.03195
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2311.03195
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Van Huyck, John B & Battalio, Raymond C & Beil, Richard O, 1990. "Tacit Coordination Games, Strategic Uncertainty, and Coordination Failure," American Economic Review, American Economic Association, vol. 80(1), pages 234-248, March.
    2. , & , P., 2014. "Refinements of Nash equilibrium in potential games," Theoretical Economics, Econometric Society, vol. 9(3), September.
    3. Joseph Farrell & Garth Saloner, 1985. "Standardization, Compatibility, and Innovation," RAND Journal of Economics, The RAND Corporation, vol. 16(1), pages 70-83, Spring.
    4. Kreindler, Gabriel E. & Young, H. Peyton, 2013. "Fast convergence in evolutionary equilibrium selection," Games and Economic Behavior, Elsevier, vol. 80(C), pages 39-67.
    5. Blume Lawrence E., 1993. "The Statistical Mechanics of Strategic Interaction," Games and Economic Behavior, Elsevier, vol. 5(3), pages 387-424, July.
    6. Joseph T. Howson, Jr., 1972. "Equilibria of Polymatrix Games," Management Science, INFORMS, vol. 18(5-Part-1), pages 312-318, January.
    7. Crawford, Vincent P., 1991. "An "evolutionary" interpretation of Van Huyck, Battalio, and Beil's experimental results on coordination," Games and Economic Behavior, Elsevier, vol. 3(1), pages 25-59, February.
    8. Joseph T. Howson, Jr. & Robert W. Rosenthal, 1974. "Bayesian Equilibria of Finite Two-Person Games with Incomplete Information," Management Science, INFORMS, vol. 21(3), pages 313-315, November.
    9. Hofbauer, Josef & Sorger, Gerhard, 1999. "Perfect Foresight and Equilibrium Selection in Symmetric Potential Games," Journal of Economic Theory, Elsevier, vol. 85(1), pages 1-23, March.
    10. Foster, Dean P. & Young, H. Peyton, 1998. "On the Nonconvergence of Fictitious Play in Coordination Games," Games and Economic Behavior, Elsevier, vol. 25(1), pages 79-96, October.
    11. Blonski, Matthias, 1999. "Anonymous Games with Binary Actions," Games and Economic Behavior, Elsevier, vol. 28(2), pages 171-180, August.
    12. DavidP. Myatt & Chris Wallace, 2009. "Evolution, Teamwork and Collective Action: Production Targets in the Private Provision of Public Goods," Economic Journal, Royal Economic Society, vol. 119(534), pages 61-90, January.
    13. Peski, Marcin, 2010. "Generalized risk-dominance and asymmetric dynamics," Journal of Economic Theory, Elsevier, vol. 145(1), pages 216-248, January.
    14. Philip R Neary & Jonathan Newton, 2017. "Heterogeneity in preferences and behavior in threshold models," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 2(1), pages 141-159, December.
    15. Martin F. Hellwig, 2003. "Public-Good Provision with Many Participants," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 70(3), pages 589-614.
    16. Daisuke Oyama & Satoru Takahashi, 2020. "Generalized Belief Operator and Robustness in Binary‐Action Supermodular Games," Econometrica, Econometric Society, vol. 88(2), pages 693-726, March.
    17. Blonski, Matthias, 2000. "Characterization of pure strategy equilibria in finite anonymous games," Journal of Mathematical Economics, Elsevier, vol. 34(2), pages 225-233, October.
    18. Lim, Wooyoung & Neary, Philip R., 2016. "An experimental investigation of stochastic adjustment dynamics," Games and Economic Behavior, Elsevier, vol. 100(C), pages 208-219.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jonathan Newton, 2018. "Evolutionary Game Theory: A Renaissance," Games, MDPI, vol. 9(2), pages 1-67, May.
    2. Benndorf, Volker & Martínez-Martínez, Ismael & Normann, Hans-Theo, 2021. "Games with coupled populations: An experiment in continuous time," Journal of Economic Theory, Elsevier, vol. 195(C).
    3. Hwang, Sung-Ha & Rey-Bellet, Luc, 2021. "Positive feedback in coordination games: Stochastic evolutionary dynamics and the logit choice rule," Games and Economic Behavior, Elsevier, vol. 126(C), pages 355-373.
    4. Nax, Heinrich Harald & Newton, Jonathan, 2022. "Deep and shallow thinking in the long run," Theoretical Economics, Econometric Society, vol. 17(4), November.
    5. Lim, Wooyoung & Neary, Philip R., 2016. "An experimental investigation of stochastic adjustment dynamics," Games and Economic Behavior, Elsevier, vol. 100(C), pages 208-219.
    6. Sawa, Ryoji, 2021. "A stochastic stability analysis with observation errors in normal form games," Games and Economic Behavior, Elsevier, vol. 129(C), pages 570-589.
    7. Sawa, Ryoji & Wu, Jiabin, 2018. "Prospect dynamics and loss dominance," Games and Economic Behavior, Elsevier, vol. 112(C), pages 98-124.
    8. Sawa, Ryoji & Wu, Jiabin, 2018. "Reference-dependent preferences, super-dominance and stochastic stability," Journal of Mathematical Economics, Elsevier, vol. 78(C), pages 96-104.
    9. Mäs, Michael & Nax, Heinrich H., 2016. "A behavioral study of “noise” in coordination games," Journal of Economic Theory, Elsevier, vol. 162(C), pages 195-208.
    10. Eliaz, Kfir & Spiegler, Ran, 2015. "X-games," Games and Economic Behavior, Elsevier, vol. 89(C), pages 93-100.
    11. Ennio Bilancini & Leonardo Boncinelli, 2020. "The evolution of conventions under condition-dependent mistakes," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 69(2), pages 497-521, March.
    12. Bilancini, Ennio & Boncinelli, Leonardo & Nax, Heinrich H., 2021. "What noise matters? Experimental evidence for stochastic deviations in social norms," Journal of Behavioral and Experimental Economics (formerly The Journal of Socio-Economics), Elsevier, vol. 90(C).
    13. Sanjeev Goyal & Penélope Hernández & Guillem Martínez-Cánovas & Frédéric Moisan & Manuel Muñoz-Herrera & Angel Sánchez, 2021. "Integration and diversity," Experimental Economics, Springer;Economic Science Association, vol. 24(2), pages 387-413, June.
      • Goyal, S. & Hernández, P. & Muñnez-Cánovasz, G. & Moisan, F. & Muñoz-Herrera, M. & Sánchez, A., 2017. "Integration and Diversity," Cambridge Working Papers in Economics 1721, Faculty of Economics, University of Cambridge.
      • Sanjeev Goyal & Penélope Hernández & Guillem Martínez-Cánovas & Frederic Moisan & Manuel Muñoz-Herrera & Angel Sánchez, 2021. "Integration and Diversity," Post-Print hal-03188210, HAL.
      • Sanjeev Goyal & Penelope Hernandez & Guillem Martinez-Canovas & Frederic Moisan & Manuel Munoz-Herrera & Angel Sanchez, 2019. "Integration and Diversity," Working Papers 20190025, New York University Abu Dhabi, Department of Social Science, revised Sep 2020.
      • Sanjeev Goyal & Pénélope Hernández & Guillem Martínez-Cánovas & Frédéric Moisan & Manuel Muñoz-Herrera & Ángel Sánchez, 2021. "Integration and diversity," Post-Print halshs-03051962, HAL.
    14. John Lynham & Philip R. Neary, 2024. "Tiebout sorting in online communities," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 73(3), pages 1149-1174, October.
    15. Arenas, Alex & Diaz-Guilera, Albert & Perez, Conrad J. & Vega-Redondo, Fernando, 2002. "Self-organized criticality in evolutionary systems with local interaction," Journal of Economic Dynamics and Control, Elsevier, vol. 26(12), pages 2115-2142, October.
    16. Wallace, Chris & Young, H. Peyton, 2015. "Stochastic Evolutionary Game Dynamics," Handbook of Game Theory with Economic Applications,, Elsevier.
    17. Kevin Hasker, 2014. "The Emergent Seed: A Representation Theorem for Models of Stochastic Evolution and two formulas for Waiting Time," Levine's Working Paper Archive 786969000000000954, David K. Levine.
    18. , & , P., 2014. "Refinements of Nash equilibrium in potential games," Theoretical Economics, Econometric Society, vol. 9(3), September.
    19. Siegfried K. Berninghaus & Karl-Martin Ehrhart & Claudia Keser, 2000. "Conventions and Local Interaction Structures: Experimental Evidence," CIRANO Working Papers 2000s-36, CIRANO.
    20. Arigapudi, Srinivas, 2024. "Transitions between equilibria in Bilingual Games under Probit Choice," Journal of Mathematical Economics, Elsevier, vol. 111(C).

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2311.03195. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.