Efficient equilibria in polymatrix coordination games

DOI10.1007/978-3-662-48054-0_44MaRDI QIDQ2946422zbMATH OpenOpenAlexFDO

Authors Mona Rahn, Guido Schäfer

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.07518

Mathematics Subject Classification ID

Equilibrium refinements (91A11) Cooperative games (91A12) Games involving graphs (91A43)

Abstract: 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 $alpha$-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 $alpha$. We prove that for $alphage2$ these games have the finite coalitional improvement property (and thus $alpha$-approximate $k$-equilibria exist), while for $alpha<2$ this property does not hold. Further, we derive an almost tight bound of $2alpha(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 $2alpha$ 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).

Recommendations

• Coordination games on graphs
• Coordination games on weighted directed graphs
• Coordination games on graphs (extended abstract)
• On approximate Nash equilibria in network design
• Coordination games on directed graphs

Cites work

• Computing desirable partitions in additively separable hedonic games
• Convergence and approximation in potential games
• Coordination games on graphs (extended abstract)
• Edge Dominating Sets in Graphs
• Finding social optima in congestion games with positive externalities
• scientific article; zbMATH DE number 3139273 (Why is no real title available?)
• Improved equilibria via public service advertising
• Intrinsic robustness of the price of anarchy
• On minmax theorems for multiplayer games
• Potential games
• Strong price of anarchy, utility games and coalitional dynamics
• The curse of simultaneity
• The stability of hedonic coalition structures
• Worst-case equilibria

Cited in

(8)

• Coordination games on graphs
• Coordination games on graphs (extended abstract)
• Efficient Coordination in Weakest-Link Games
• Price of anarchy for graph coloring games with concave payoff
• Coordination games on weighted directed graphs
• The inefficiency of Nash and subgame perfect equilibria for network routing
• One-sided markets with externalities
• Topological price of anarchy bounds for clustering games on networks

This page was built for publication: Efficient equilibria in polymatrix coordination games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946422)