New paper: Some coordination problems are harder than others

[Neary, Philip]

Dear all,

I am writing to let you know of a new paper that my coauthors and I completed recently. The paper is not an evolutionary paper per se, but I hope that the main result will be of interest to the LEG community since it has an application to equilibrium selection under logit dynamics.

Consider a network game where each edge in the network represents a 2x2 potential game (importantly it need *NOT* be the same 2x2 game on every edge). It is well known that the potential maximiser of such a network game is stochastically stable under logit dynamics, but can one find the strategy profile that maximises the potential?

The paper proves a dichotomy for when computing the potential maximiser of network games of this kind is a tractable problem and when it is not. Surprisingly, at least to us, it turns out that when each 2x2 game is a coordination game of strategic complements (what we call a “pure coordination game”) the potential maximiser can be computed in polynomial time, but when each 2x2 game is a coordination game of strategic substitutes (an “anti-coordination game”) computing the potential maximiser is NP-Hard. 

Viewed in this way, it appears that there is something inherently more difficult about “solving” anti-coordination problems. That is, at least as regards this class of binary action network games, anti-coordinating is no easier than coordinating.

Any comments would be greatly appreciated.

Happy new year and all the best for 2024.

Kind regards,

Philip

This email, its contents and any attachments are intended solely for the addressee and may contain confidential information. In certain circumstances, it may also be subject to legal privilege. Any unauthorised use, disclosure, or copying is not permitted. If you have received this email in error, please notify us and immediately and permanently delete it. Any views or opinions expressed in personal emails are solely those of the author and do not necessarily represent those of Royal Holloway, University of London. It is your responsibility to ensure that this email and any attachments are virus free.