NP-hardness of deciding Nash equilibrium existence in single-peaked Schelling games

At least 2 years old · documented by

Let Λ∈(0,1)\Lambda\in(0,1) be a peak. A Single-Peaked Jump Schelling Game and a Single-Peaked Swap Schelling Game are instances of the respective models, and NE⁡\operatorname{NE} denotes a Nash equilibrium. Equilibrium-existence complexity conjecture. For both the Single-Peaked Jump Schelling Game and the Single-Peaked Swap Schelling Game, it is NP-hard to decide whether a given instance admits an NE⁡\operatorname{NE}. This is a main open problem for both game variants; the paper establishes hardness for finding equilibria via improving-response dynamics and notes NP-hardness of equilibrium-existence decisions when stubborn agents are allowed, but the stated result without that assumption remains open.

References

Primary source

Tobias Friedrich, Pascal Lenzner, Louise Molitor and Lars Seifert, “Single-Peaked Jump Schelling Games”, arXiv:2302.12107 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.