English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate the difficulty of finding economically efficient solutions tocoordination problems on graphs. Our work focuses on two forms of coordinationproblem: pure-coordination games and anti-coordination games. We consider threeobjectives in the context of simple binary-action polymatrix games: (i)maximizing welfare, (ii) maximizing potential, and (iii) finding awelfare-maximizing Nash equilibrium. We introduce an intermediate, newgraph-partition problem, termed Maximum Weighted Digraph Partition, which is ofindependent interest, and we provide a complexity dichotomy for it. Thisdichotomy, among other results, provides as a corollary a dichotomy forObjective (i) for general binary-action polymatrix games. In addition, itreveals that the complexity of achieving these objectives varies depending onthe form of the coordination problem. Specifically, Objectives (i) and (ii) canbe efficiently solved in pure-coordination games, but are NP-hard inanti-coordination games. Finally, we show that objective (iii) is NP-hard evenfor simple non-trivial pure-coordination games.

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