TY - GEN

T1 - Efficient equilibria in polymatrix coordination games

AU - Rahn, Mona

AU - Schäfer, Guido

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=84944616263&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944616263&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48054-0_44

DO - 10.1007/978-3-662-48054-0_44

M3 - Conference contribution

AN - SCOPUS:84944616263

SN - 9783662480533

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 529

EP - 541

BT - Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Proceedings

A2 - Italiano, Giuseppe F.

A2 - Pighizzini, Giovanni

A2 - Sannella, Donald T.

PB - Springer Verlag

T2 - 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015

Y2 - 24 August 2015 through 28 August 2015

ER -