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

Argyrios Deligkas, Eduard Eiben, Gregory Gutin +2

We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordinati…