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

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

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer 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.

OriginalsprogEngelsk
TitelProceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
RedaktørerEdith Elkind
Antal sider9
ForlagInternational Joint Conferences on Artificial Intelligence
Publikationsdato2023
Sider2642-2650
ISBN (Elektronisk)9781956792034
DOI
StatusUdgivet - 2023
Begivenhed32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 - Macao, Kina
Varighed: 19. aug. 202325. aug. 2023

Konference

Konference32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
Land/OmrådeKina
ByMacao
Periode19/08/202325/08/2023
SponsorInternational Joint Conferences on Artificial Intelligence (IJCAI)
NavnIJCAI International Joint Conference on Artificial Intelligence
Vol/bind2023-August
ISSN1045-0823

Bibliografisk note

Funding Information:
Anders Yeo’s research was supported by the Danish research council for independent research under grant number DFF 7014-00037B.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Complexity of Efficient Outcomes in Binary-Action Polymatrix Games and Implications for Coordination Problems'. Sammen danner de et unikt fingeraftryk.

Citationsformater