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/

Zendy Plus

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

Zendy Tools

Zendy Open

We consider polymatrix coordination games with individual preferences whereevery player corresponds to a node in a graph who plays with each neighbor aseparate bimatrix game with non-negative symmetric payoffs. In this paper, westudy $\alpha$-approximate $k$-equilibria of these games, i.e., outcomes whereno group of at most $k$ players can deviate such that each member increases hispayoff by at least a factor $\alpha$. We prove that for $\alpha \ge 2$ thesegames have the finite coalitional improvement property (and thus$\alpha$-approximate $k$-equilibria exist), while for $\alpha < 2$ thisproperty does not hold. Further, we derive an almost tight bound of$2\alpha(n-1)/(k-1)$ on the price of anarchy, where $n$ is the number ofplayers; in particular, it scales from unbounded for pure Nash equilibria ($k =1)$ to $2\alpha$ for strong equilibria ($k = n$). We also settle the complexityof several problems related to the verification and existence of theseequilibria. Finally, we investigate natural means to reduce the inefficiency ofNash 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).

Efficient Equilibria in Polymatrix Coordination Games