Some coordination problems are harder than others

Argyrios Deligkas, Eduard Eiben, Gregory Gutin, Philip R. Neary and Anders Yeo

Papers from arXiv.org

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).

Date: 2023-11, Revised 2023-11
New Economics Papers: this item is included in nep-evo, nep-gth, nep-hme, nep-mic and nep-net
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2311.03195 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2311.03195

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().