NP-hardness of deciding Nash equilibrium existence in single-peaked Schelling games
Let be a peak. A Single-Peaked Jump Schelling Game and a Single-Peaked Swap Schelling Game are instances of the respective models, and 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 . 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
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.