Complexity of Efficient Outcomes in Binary-Action Polymatrix Games and Implications for Coordination Problems

Argyrios Deligkas, Eduard Eiben, Gregory Gutin, Philip Neary, Anders Yeo

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordination games and anti-coordination games. We consider three objectives in the context of simple binary-action polymatrix games: (i) maximizing welfare, (ii) maximizing potential, and (iii) finding a welfare-maximizing Nash equilibrium. We introduce an intermediate, new graph-partition problem, termed MWDP, which is of independent interest, and we provide a complexity dichotomy for it. This dichotomy, among other results, provides as a corollary a dichotomy for Objective (i) for general binary-action polymatrix games. In addition, it reveals that the complexity of achieving these objectives varies depending on the form of the coordination problem. Specifically, Objectives (i) and (ii) can be efficiently solved in pure-coordination games, but are NP-hard in anti-coordination games. Finally, we show that objective (iii) is NP-hard even for simple non-trivial pure-coordination games.

Original languageEnglish
Title of host publicationProceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
EditorsEdith Elkind
Number of pages9
PublisherInternational Joint Conferences on Artificial Intelligence
Publication date2023
Pages2642-2650
ISBN (Electronic)9781956792034
DOIs
Publication statusPublished - 2023
Event32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 - Macao, China
Duration: 19. Aug 202325. Aug 2023

Conference

Conference32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
Country/TerritoryChina
CityMacao
Period19/08/202325/08/2023
SponsorInternational Joint Conferences on Artificial Intelligence (IJCAI)
SeriesIJCAI International Joint Conference on Artificial Intelligence
Volume2023-August
ISSN1045-0823

Fingerprint

Dive into the research topics of 'Complexity of Efficient Outcomes in Binary-Action Polymatrix Games and Implications for Coordination Problems'. Together they form a unique fingerprint.

Cite this