Semantic Scholar Open Access 2023

Some coordination problems are harder than others

Argyrios Deligkas E. Eiben G. Gutin Philip R. Neary Anders Yeo

Abstrak

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

Topik & Kata Kunci

Economics Computer Science

Penulis (5)

Argyrios Deligkas

E. Eiben

G. Gutin

Philip R. Neary

Anders Yeo

Format Sitasi

APA MLA BibTeX

Deligkas, A., Eiben, E., Gutin, G., Neary, P.R., Yeo, A. (2023). Some coordination problems are harder than others. https://doi.org/10.48550/arXiv.2311.03195

Akses Cepat

PDF tidak tersedia langsung

Cek di sumber asli →

Lihat di Sumber doi.org/10.48550/arXiv.2311.03195

Informasi Jurnal

Tahun Terbit: 2023
Bahasa: en
Sumber Database: Semantic Scholar
DOI: 10.48550/arXiv.2311.03195
Akses: Open Access ✓