Computing better approximate pure Nash equilibria in cut games via semidefinite programming

Ioannis Caragiannis, Zhile Jiang

Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so r…