  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 research has focused on computing approximate equilibria.
We present a polynomial-time algorithm that computes $2.7371$-approximate pure
Nash equilibria in cut games. This is the first improvement to the previously
best-known bound of $3$, due to the work of Bhalgat, Chakraborty, and Khanna
from EC 2010. Our algorithm is based on a general recipe proposed by
Caragiannis, Fanelli, Gravin, and Skopalik from FOCS 2011 and applied on
several potential games since then. The first novelty of our work is the
introduction of a phase that can identify subsets of players who can
simultaneously improve their utilities considerably. This is done via
semidefinite programming and randomized rounding. In particular, a negative
objective value to the semidefinite program guarantees that no such
considerable improvement is possible for a given set of players. Otherwise,
randomized rounding of the SDP solution is used to identify a set of players
who can simultaneously improve their strategies considerably and allows the
algorithm to make progress. The way rounding is performed is another important
novelty of our work. Here, we exploit an idea that dates back to a paper by
Feige and Goemans from 1995, but we take it to an extreme that has not been
analyzed before.
