Efficient equilibria in polymatrix coordination games

Mona Rahn, Guido Schäfer*

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


We consider polymatrix coordination games with individual preferences where every player corresponds to a node in a graph who plays with each neighbor a separate bimatrix game with non-negative symmetric payoffs. In this paper, we study α-approximate k-equilibria of these games, i.e., outcomes where no group of at most k players can deviate such that each member increases his payoff by at least a factor α. We prove that for α ≥ 2 these games have the finite coalitional improvement property (and thus α-approximate k-equilibria exist), while for α < 2 this property does not hold. Further, we derive an almost tight bound of 2α(n - 1)/(k - 1) on the price of anarchy, where n is the number of players; in particular, it scales from unbounded for pure Nash equilibria (k = 1) to 2α for strong equilibria (k = n). We also settle the complexity of several problems related to the verification and existence of these equilibria. Finally, we investigate natural means to reduce the inefficiency of Nash equilibria. Most promisingly, we show that by fixing the strategies of k players the price of anarchy can be reduced to n/k (and this bound is tight).

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Proceedings
EditorsGiuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783662480533
Publication statusPublished - 1 Jan 2015
Event40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015 - Milan, Italy
Duration: 24 Aug 201528 Aug 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015


Dive into the research topics of 'Efficient equilibria in polymatrix coordination games'. Together they form a unique fingerprint.

Cite this