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

Ioannis Caragiannis Department of Computer Science, Aarhus University, Åbogade
34, 8200 Aarhus N, Denmark. Email<EMAIL_ADDRESS>Zhile
Jiang††footnotemark:

###### Abstract

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.

##  1 Introduction

Understanding the computational aspects of equilibria is a key goal of
algorithmic game theory. In this direction, we consider the fundamental class
of cut games. In a cut game, each node of an edge-weighted graph is controlled
by a distinct player. The players aim to build a cut of the graph in a non-
cooperative way. Each player has two strategies, to put the node she controls
in one of the two sides of the cut, and aims to maximize her utility, defined
as the total weight of edges in the cut that are incident to the node the
player controls. A pure Nash equilibrium (or, simply, an equilibrium) is a
state of the game in which no player has any incentive to unilaterally change
her strategy in order to improve her utility.

Cut games are potential games. The total weight of the edges in the cut is a
potential function, with the following remarkable property: for every two
states that differ in the strategy of a single player, the difference in the
value of the potential function is equal to the difference in the utility of
the deviating player. Thus, a sequence of best-response moves, consisting of
players who change their strategies and improve their utilities, is guaranteed
to lead to a state that locally maximizes the potential function and is, thus,
an equilibrium. So, finding an equilibrium is equivalent to computing a
locally-maximum cut in a graph, i.e., a cut that cannot be improved by moving
a single node from one side of the cut to the other.

Unfortunately, computing a locally-maximum cut in a graph is a PLS-hard
problem [32]. In light of this, approximate pure Nash equilibria seem to be a
reasonable compromise for cut games; in general, a $\rho$-approximate pure
Nash equilibrium is a state of a strategic game in which no player deviation
can increase her utility by a factor of more than $\rho$. Among other results,
Bhalgat et al. [7] present a polynomial-time algorithm for computing a
$3$-approximate equilibrium in cut games.

At first glance, two algorithmic ideas seem relevant for tackling the
challenge of computing approximate pure Nash equilibria. The first one is to
follow a sequence of deviations by players who improve their utility by a
factor of more than $\rho$. The existence of a potential function guarantees
that this process will eventually converge to a $\rho$-approximate
equilibrium. Unfortunately, such sequence can be exponentially long, as
Bhalgat et al. [7] have shown specifically for cut games (and for small
approximation factors). The second one is to exploit an approximation
algorithm for the problem of maximizing the potential function. For cut games,
this could involve the celebrated algorithm of Goemans and Williamson [23] for
MAX-CUT or, more generally, excellent approximations of local maxima using the
techniques of Orlin et al. [29]. Unfortunately, approximations of the
potential function and approximate equilibria are unrelated notions. So, the
algorithm in [7] exploits the structure of cut games to define restricted
subgames in which sequences of player deviations are applied separately. This
approach leads to $3$-approximate equilibria in cut games and is also
applicable to the broader class of constraint satisfaction games.

#### Our results and techniques.

In this paper, we present the first improvement to the result of Bhalgat et
al. [7], showing how to compute efficiently a $2.7371$-approximate equilibrium
in a cut game. Our result follows a general algorithmic recipe proposed by
Caragiannis et al. [11] for congestion games. Applications of this recipe to
constraint satisfaction games [10] has improved many of the approximation
bounds presented in [7] but not the one for cut games (even though it has
rediscovered a $3$-approximation). Unlike [7], the algorithms in [11, 10]
identify polynomially-long sequences of coordinated player deviations that
eventually lead to an approximate equilibrium. Our improvement is possible by
introducing a global move step in which a set of players change their
strategies simultaneously. Such a set of players is identified by solving a
semidefinite program and rounding its solution. To the best of our knowledge,
this is the first application of semidefinite programming to the computation
of approximate pure Nash equilibria. Essentially, our paper blends the two
algorithmic approaches mentioned in the previous paragraph for the first time.

The general structure of the algorithm in [10] is as follows. Players are
classified into blocks, so that players within the same block are
polynomially-related in terms of their maximum utility. Then, a set of phases
is executed. In each phase, the players in two consecutive blocks are allowed
to move. The players in the (heavy) block of higher maximum utility play
(roughly) $3$-moves, i.e., they change their strategy whenever they can
improve their utility by a factor of more than $3$. The players in the (light)
block of lower maximum utility play $(1+\varepsilon)$-moves (for some tiny
positive $\varepsilon$). At the end of the phase, the strategies of the
players in the heavy block are irrevocably decided. The crucial property of
the algorithm is that the light players of a phase are the heavy ones in the
next one. Due to the moves of the light players, the state reached at the end
of a phase has low stretch (of at most $3$) for the light players, meaning
that there is no subset of them who could simultaneously change their strategy
and improve their contribution to the potential function by a factor of more
than $3$. This guarantees that the number of $3$-moves by the heavy players in
the next phase will be polynomially-bounded and, furthermore, the effect that
these moves have to players whose strategies were irrevocably decided in
previous phases is minimal. So, all players stay close to a $3$-approximate
equilibrium at the end of the whole process.

Our algorithm follows the same general structure, even though it coordinates
more carefully the moves of the players in different blocks within a phase.
The improvement comes from a different implementation of the moves of the
light players within a phase. Here, we focus explicitly on the problem of
detecting whether there exists a set of light players who can improve their
contribution to the potential by a factor of $\rho$ by changing their
strategies simultaneously. Essentially, the algorithm of [10] solves this
problem for $\rho=3$ using local search (the analog of best-response moves by
the light players). Instead, we obtain the better approximation of $2.7371$ by
formulating this problem as a semidefinite program. Non-positive objective
values of the semidefinite program guarantee that the current cut has low
stretch for the light players. Positive objective values guarantee that by
rounding the SDP solution appropriately, we obtain a global move which
improves the potential considerably and makes progress, similar to the
progress an $(1+\varepsilon)$-move by a single light player makes in the
algorithm of [10].

Rounding the SDP solution is very challenging. The SDP objective has a mixture
of XOR-type terms, requiring that the two vectors corresponding to the
endpoints of an edge that is not in the current cut are opposite, and OR-type
terms requiring that one of the endpoints of an edge in the current cut
coincides with a special vector the SDP is using. Even though the XOR-type
terms have non-negative coefficients and standard hyperplane rounding could
yield excellent approximations for the particular terms (like in [23]), the
OR-type terms have negative coefficients, making standard hyperplane rounding
disastrous for them. So, we instead use an idea that originates from Feige and
Goemans [18], which has inspired much follow-up work on approximating MAX2-SAT
and related problems, but we consider it in an extreme that has not been
considered before. In particular, the vectors in the SDP solution are first
rotated in the $2$-dimensional plane they define with the special vector and,
then, hyperplane rounding is performed. We use the rotation function
$f(\theta)=\frac{\pi}{2}(1-\cos{\theta})$, meaning that a vector at an angle
of $\theta$ from the special vector is relocated at an angle $f(\theta)$ from
it. This gives a rather poor $1/2$-approximation to the XOR-type terms but
approximates well the OR-type constraints.

The approximation ratio we obtain is the solution of a quadratic equation; the
exact value is $\frac{1+2\sqrt{13}}{3}\approx 2.7371$. This is extremely rare
for the approximation factors obtained from SDPs in combinatorial optimization
problems. To prove the properties of rounding, we need to prove two
inequalities for triplets of $3$-dimensional vectors, which turn out to depend
on two variables only: the angles the special vector forms with the two other
vectors involved in a term of the SDP objective. As it is often the case with
the analysis of SDP-based approximation algorithms (e.g., in [26]), we have
verified one of these inequalities by extensive numerical computations. These
imply that the worst-case bound is obtained for a restriction of the
parameters to more tractable cases, for which we present a formal analysis.

#### Related work.

Even though research in algorithmic game theory gained popularity after the
seminal papers by Koutsoupias and Papadimitriou [25], Nisan and Ronan [28],
and Roughgarden and Tardos [31] (the conference versions appeared in 1999,
1999, and 2000, respectively), research in computational aspects of pure Nash
equilibria had started earlier, with the introduction of the class PLS
—standing for polynomial local search— by Johnson, Papadimitriou, and
Yannakakis [24] and subsequent (mainly negative) results on computing locally-
optimum solutions for combinatorial optimization problems. Mostly related to
the topic of the current paper is the paper by Schaeffer and Yannakakis [32].
Expressed in game-theoretic terms, they proved that computing a pure Nash
equilibrium in a cut game is a PLS-hard problem.

The connection of cut games and local search should not come as a surprise.
Cut games are potential games [27]. They admit a potential function defined
over the states of the game so that for any two states differing in the
strategy of a single player, the difference in the potential values between
the two states and the difference in the utility of the deviating player has
the same sign. The class of potential games also includes congestion games
[17, 27, 30], network design games [3], constraint satisfaction games [7, 10],
market sharing games [22], and more. Most of these games have the additional
property that the two differences mentioned above not only have the same sign
but they are actually equal. Such potential functions are usually called exact
[17]. For cut games, the total weight of edges that cross the cut is an exact
potential function.

Early attempts on computing equilibria in potential games have aimed to follow
a best-response dynamics, i.e., a sequence of player moves, in which the
utility of the deviating player increases by at least a $1+\varepsilon$
factor. This has been proved useful in a few cases —e.g., in restricted cases
of congestion games [1, 6, 14]— to compute $(1+\varepsilon)$-approximate
equilibria. Such approaches work nicely if the players are similar, in the
sense that their moves result in comparable utility increases. Simple
arguments, which relate the increase in the potential function with the
minimum increase in the utility of a deviating player can be used to bound the
running time (i.e., the length of the best-response dynamics to the
approximate equilibrium) in terms of the game size and $1/\varepsilon$.
However, players rarely have such similarities. In a cut game, we may have
players controlling nodes that have incident edges of high weight and others
which have only incident edges of negligible weight. Then, such approaches
cannot compute approximate equilibria in polynomial time, even though they can
be used to compute states of high social welfare, e.g., see [4, 5, 8, 15].

The most successful recipe for computing approximate equilibria in potential
games has been proposed by Caragiannis et al. [11]. Their approach has yielded
$2$-approximate equilibria for linear congestion games, and
$d^{\mathcal{O}(d)}$-approximate equilibria for congestion games with
polynomial latency functions of degree $d$. These results have been improved
in [19, 33]. More importantly, the recipe of [11] has been applied to other
potential games such as constraint satisfaction [10] and cost sharing games
[20], as well as to non-potential games such as weighted congestion games in
[9, 12, 21]. These last results have been possible by either approximating the
original game by a potential game in which the algorithm is applied, or by
introducing an approximate potential function to keep track of best-response
moves in the original games. In all applications of the recipe of [11], the
algorithm identifies a sequence of deviations by the players, either in the
original game or in its approximation. The current paper is the first one to
extend the recipe with global moves (of simultaneous player deviations).

Our global moves are implemented via semidefinite programming and randomized
rounding. Starting with the celebrated paper of Goemans and Williamson [23],
these tools have been proved very useful in approximating combinatorial
optimization problems such as MAX-CUT (the problem of computing a cut of
maximum total weight) and MAX-2SAT (the problem of computing a Boolean
assignment that maximizes the total weight of satisfied clauses in a formula
in conjunctive normal form), among many others. The classical semidefinite
program for MAX-CUT uses a unit vector $v_{j}$ for each graph node $j$, to
represent the side of the cut in which to node is put. The objective is just
the sum of the terms $\frac{1}{2}(1-v_{j}\cdot v_{k})$ multiplied by the
weight of edge $(j,k)$ over all edges in the input graph. Notice that the
quantity $\frac{1}{2}(1-v_{j}\cdot v_{k})$ is a XOR-type term, taking the
value $1$ if the two vectors are opposite and $0$ if the two vectors coincide
(corresponding to nodes in different sides or at the same side of the cut,
respectively). The solution of the SDP, which may inevitably consist of
vectors in many different directions, is rounded by picking a random
hyperplane crossing the vectors’ origin, and putting the nodes at the left or
the right of the cut, according to side of the hyperplane the corresponding
unit vectors are lying. In this way, Goemans and Williamson [23] improved the
trivial $1/2$-approximation for MAX-CUT to $0.8785$.

Modeling OR-type terms (like those required by MAX-2SAT) requires an extra
variable, a reference (or special) vector $\widehat{v}$. Then, using the
vector $v_{j}$ as (an approximation to) the value of a Boolean variable, the
OR-type term
$\frac{1}{4}\cdot(3+v_{j}\cdot\widehat{v}+v_{k}\cdot\widehat{v}-v_{j}\cdot
v_{k})$ takes the value $1$ if at least one of the vectors $v_{j}$ and $v_{k}$
coincide with the reference vector $\widehat{v}$. Feige and Goemans [18]
considered improved the approximation bound of [23] for MAX-2SAT by exploiting
the existence of the reference vector $\widehat{v}$ to rotate all vectors
appropriately before rounding them using a random hyperplane. Rotation
relocates each vector $v_{j}$ forming an angle $\theta$ with the reference
vector at a new position in the $2$-dimensional plane defined by $v_{j}$ and
$\widehat{v}$, at angle $f(\theta)$ from $\widehat{v}$. The rotation function
$f$ they use is a linear combination between the no-rotation function
$f(\theta)=\theta$ and the rotation function
$f(\theta)=\frac{\pi}{2}\cdot(1-\cos{\theta})$ that we also consider here. An
extensive discussion of this approach with additional details is given in
[34]. Lewin et al. [26] present the best known bound of $0.9401$ for MAX-2SAT;
in their paper, they discuss several alternatives for rounding the solution of
SDPs for MAX-2SAT. Finally, we remark that even though SDPs and rounding have
been used to handle negative coefficients successfully, e.g., in approximating
the cut-norm of a matrix [2] or in maximizing quadratic programs [13], those
formulation are very far from ours and the corresponding techniques do not
seem to be applicable in our case.

#### Roadmap.

The rest of the paper is structured as follows. We begin with preliminary
definitions and notation in Section 2. Our algorithm is presented in Section
3, which concludes with the statement of our main result (Theorem 3.1). Then,
Section 4 presents the properties of the global-moves routine of our
algorithm. We put everything together and prove Theorem 3.1 in Section 5,
while the proof of Lemma 4.2, which states the properties of randomized
rounding is deferred to Section 6. We conclude in Section 7.

##  2 Preliminaries

A cut game is defined by an edge-weighted complete $n$-node graph $G=(V,E)$.
Each edge $e$ of the graph has a non-negative weight $w_{e}$. We overload this
notation and write $w_{jk}$ to denote the weight of the edge $(j,k)$ and
$w(A)=\sum_{e\in A}{w_{e}}$ to denote the total weight of the edges in set
$A$. There are $n$ players, each corresponding to a distinct node of $G$. The
players aim to collectively but non-cooperatively build a cut of the graph,
i.e., a partition of its nodes into two sets. Player $j\in\mathcal{N}$ has two
different strategies: putting her node $i$ at the left or at the right side of
the cut. A state of the game is represented by an $n$-vector
$S=(s_{1},s_{2},...,s_{n})$, indicating that player $j$ uses strategy $s_{j}$.
Given a state $S$, we denote by $\text{CUT}(S)$ the set of edges whose
endpoints correspond to players that select different strategies in $S$. For a
subset of players $R\subseteq\mathcal{N}$, we denote by $\text{CUT}_{R}(S)$
the subset of $\text{CUT}(S)$ that consists of edges with at least one
endpoint corresponding to a player in $R$. With some abuse of notation, we
simplify $\text{CUT}_{\\{j\\}}(S)$ to $\text{CUT}_{j}(S)$. The utility of
player $j$ is the total weight of the edges incident to her node, i.e.,
$u_{j}(S)=w(\text{CUT}_{j}(S))$. We also denote by $E_{R}$ the set of edges
that are incident to at least one player in $R$ and simplify $E_{\\{j\\}}$ to
$E_{j}$. We denote by $U_{j}$ the maximum utility that player $j$ may have,
i.e., $U_{j}=w(E_{j})$.

We use a standard game-theoretic notation. Given a state
$S=(s_{1},s_{2},...,s_{n})$ and a player $j\in\mathcal{N}$, we denote by
$(S_{-j},s^{\prime}_{j})$ the state obtained by $S$ when player $j$
unilaterally changes her strategy from $s_{j}$ to its complement
$s^{\prime}_{j}$. This is an improvement move (or, simply, a move) for player
$j$ if her utility increases, i.e., if
$u_{j}(S_{-j},s^{\prime}_{j})>u_{j}(S)$. We call it a $\rho$-move when the
utility of player $j$ increases by more than a factor of $\rho>1$, i.e.,
$u_{j}(S_{-j},s^{\prime}_{j})>\rho\cdot u_{j}(S)$. A state $S$ is a pure Nash
equilibrium (or, simply, an equilibrium) if no player has a move to make.
Similarly, $S$ is a $\rho$-approximate (pure Nash) equilibrium if no player
has any $\rho$-move to make.

Given a state $S$, we denote by $\Phi(S)$ the total weight of the edges in
$\text{CUT}(S)$, i.e., $\Phi(S)=w(\text{CUT}(S))$. The function $\Phi$ is a
potential function, having the remarkable property that for every two states
$S$ and $(S_{-j},s^{\prime}_{j})$ that differ only in the strategy of player
$j$, the difference in the potential function is equal to the difference of
the utility of player $j$, i.e.,
$\Phi(S)-\Phi(S_{-j},s^{\prime}_{j})=u_{j}(S)-u_{j}(S_{-j},s^{\prime}_{j})$.

Following [10], we will often consider sequences of moves in which only
players from a certain subset $R\subseteq\mathcal{N}$ are moving. These can be
thought of as moves in a subgame defined on graph $G$ among the players in $R$
only, in which the nodes that are not controlled by players in $R$ are frozen
to a fixed placement in one of the sides of the cut. We represent states of a
subgame in the same way we do for the original game using $n$-vectors of
strategies, including both the strategies of the players in $R$ and the frozen
strategies of the players in $\mathcal{N}\setminus R$.

The next two claims follow easily by our definitions and are used repeatedly
in our proofs. Claim 2.1 shows that the subgames of a cut game are also
potential games and Claim 2.2 gives basic facts about the utility of players.

######  Claim 2.1.

Consider a cut game $\mathcal{G}$ with a set $\mathcal{N}$ of players. For
every subgame of $\mathcal{G}$ defined among a subset $R\subseteq\mathcal{N}$
of players, the function $\Phi_{R}$, defined as
$\Phi_{R}(S)=w(\text{CUT}_{R}(S))$ for each state $S$ of the subgame, is an
exact potential function.

######  Claim 2.2.

Consider a cut game $\mathcal{G}$ with a set $\mathcal{N}$ of players, and let
$j\in\mathcal{N}$ be a player and $S$ a state of $\mathcal{G}$. If player $j$
performs a $p$-move, her utility and the potential $\Phi_{R}$ for every
subgame involving her (i.e., $j\in R\subseteq\mathcal{N}$) increase by more
than $\frac{p-1}{p+1}\cdot U_{j}$. If player $j$ does not have any $p$-move to
make at state $S$, then $u_{j}(S)\geq\frac{1}{p+1}\cdot U_{j}$.

Given two states $S$ and $T$ of game $\mathcal{G}$ and a possibly empty subset
of players $R\subseteq\mathcal{N}$, we denote by $(S_{-R},T_{R})$ the state in
which each player of set $R$ uses her strategy in state $T$ and each player in
set $\mathcal{N}\setminus R$ uses her strategy in state $S$. In particular, we
denote by $(S_{-R},S^{\prime}_{R})$ the state in which each player of set $R$
uses the complement of her strategy in state $S$ and each player of set
$\mathcal{N}\setminus R$ uses her strategy in $S$. We refer to the ratio
$\frac{\Phi_{R}(S_{-R},S^{\prime}_{R})}{\Phi_{R}(S)}$ as the stretch of state
$S$ for the subgame defined by the subset of players $R\subseteq\mathcal{N}$.

##  3 The algorithm

Our algorithm (see its pseudocode as Algorithm 1) has a simple general
structure. It uses several constants: a tolerance parameter
$\varepsilon\in[0,1/4]$ and the constants $\rho=\frac{1+2\sqrt{13}}{3}\approx
2.7371$, $\sigma=\rho+\varepsilon/3$, and $\tau=\rho+2\varepsilon/3$. The
algorithm takes as input a cut game $\mathcal{G}$ with $n$ players and returns
a state $S_{\text{out}}$. As we will show, the algorithm terminates after
polynomially many steps in terms of $n$ and $1/\varepsilon$ and the state
$S_{\text{out}}$ is a $(\rho+\varepsilon)$-approximate pure Nash equilibrium,
with high probability.

Input: A cut game $\mathcal{G}$ with a set $\mathcal{N}$ of $n$ players

Output: A state $S_{\text{out}}$ of $\mathcal{G}$

1: $\Delta\leftarrow 480n/\varepsilon^{2}$;

2: Set $U_{\text{min}}\leftarrow\min_{j\in\mathcal{N}}{U_{j}}$,
$U_{\text{max}}\leftarrow\max_{j\in\mathcal{N}}{U_{j}}$, and $m\leftarrow
1+\left\lfloor\log_{\Delta}{\left(U_{\text{max}}/U_{\text{min}}\right)}\right\rfloor$
;

3: (Implicitly) partition players into block $B_{1}$, $B_{2}$, …, $B_{m}$,
such that $j\in B_{i}$ implies that
$U_{j}\in\left(U_{\text{max}}\Delta^{-i},U_{\text{max}}\Delta^{1-i}\right]$;

4: Set $S\leftarrow$ an arbitrary initial state;

5: Update $S\leftarrow\text{GLOBAL}(\mathcal{G},S,B_{1})$;

6: for phase $i\leftarrow 1$ to $m-1$ such that $B_{i}\not=\emptyset$ do

7: repeat

8: Update $(S,ch1)\leftarrow\text{LOCAL}(\mathcal{G},S,B_{i},\tau)$;

9: Update $(S,ch2)\leftarrow\text{GLOBAL}(\mathcal{G},S,B_{i+1})$;

10: until $ch1=\textbf{false}{}$ and $ch2=\textbf{false}{}$

11: end for

12: Update $S\leftarrow\text{LOCAL}(\mathcal{G},S,B_{m},\tau)$;

13: return $S_{\text{out}}\leftarrow S$;

ALGORITHM 1 The algorithm for computing approximate pure Nash equilibria in
cut games

The algorithm initializes parameter $\Delta$ to be polynomially related to $n$
and $1/\varepsilon$ (line 1). Then, in lines 2 and 3, it implicitly partitions
the players into blocks $B_{1}$, $B_{2}$, …, $B_{m}$ according to their
maximum utility. Denoting by $U_{\max}$ the maximum utility among all players,
block $B_{i}$ consists of the players with maximum utility in the interval
$(U_{\max}\Delta^{-i},U_{\max}\Delta^{1-i}]$. By the definition of $\Delta$,
the players in the same block have polynomially related maximum utilities.

The lines 4-12 are the main body of the algorithm. The algorithm utilizes two
routines, namely LOCAL() and GLOBAL(), implementing a set of local and global
moves among by players in a particular block. The computation is divided into
phases. Starting with an arbitrary initial state (in line 4), phase 0 (line 5)
executes global moves for the players in block $B_{1}$. Then, for
$i=1,...,m-1$, phase $i$ repeatedly executes local moves for the players in
block $B_{i}$ and global moves for the players in block $B_{i+1}$ until the
execution of these routines does not produces new states. Finally, the
algorithm runs phase $m$, which executes local moves for the players in block
$B_{m}$. The state produced after the execution of phase $m$ is returned as
the output state $S_{\text{out}}$.

The routine LOCAL() (see Algorithm 2) takes as input the cut game
$\mathcal{G}$, a current state $S$, a subset of players $B$, and a parameter
$p>1$; on exit, it returns an output state and a flag denoting whether the
output state is different than the input one. LOCAL() repeatedly performs
$p$-moves as long as there is a player in set $B$ that has such a $p$-move to
make.

Input: A cut game $\mathcal{G}$ with a set $\mathcal{N}$ of $n$ players, a
state $S$, a subset $B\subseteq\mathcal{N}$ of players, and a parameter $p>1$

Output: A state of $\mathcal{G}$ and a Boolean flag

1: Set $change\leftarrow\textbf{false}{}$;

2: while there is a player $j\in B$ that satisfies
$u_{j}(S_{-j},s^{\prime}_{j})>p\cdot u_{j}(S)$ do

3: Update $S\leftarrow(S_{-j},s^{\prime}_{j})$;

4: $change\leftarrow\textbf{true}{}$;

5: end while

6: return $(S,change)$;

ALGORITHM 2 The routine LOCAL()

The routine GLOBAL() is the main novelty of our algorithm compared to the
algorithm in [10]. It calls the routines SDP() and ROUND(). When executed on
input a cut game $\mathcal{G}$ with a set $\mathcal{N}$ of $n$ players, state
$S$, and the subset of players $B\subseteq\mathcal{N}$, the routine SDP()
solves the following semidefinite program:

maximize $\displaystyle Z=\frac{1}{2}\cdot\sum_{(j,k)\in
E\setminus\text{CUT}_{B}(S)}{w_{jk}\cdot(1-v_{j}\cdot v_{k})}$
$\displaystyle-\frac{1}{4}\cdot\sum_{(j,k)\in\text{CUT}_{B}(S)}{w_{jk}\cdot\left(3\sigma-1+(\sigma-1)\cdot\widehat{v}\cdot
v_{j}+(\sigma-1)\cdot\widehat{v}\cdot v_{k}-(\sigma+1)\cdot v_{j}\cdot
v_{k}\right)}$ subject to
$\displaystyle\sum_{(j,k)\in\text{CUT}_{B}(S)}{w_{jk}\cdot(3+v_{j}\cdot\widehat{v}+v_{k}\cdot\widehat{v}-v_{j}\cdot
v_{k})}\geq\min_{j\in B}{U_{j}}$
$\displaystyle\widehat{v}\cdot\widehat{v}=1,\widehat{v}\in\mathbb{R}^{n}$
$\displaystyle v_{j}\cdot v_{j}=1,v_{j}\in\mathbb{R}^{n},\forall j\in B$
$\displaystyle v_{j}=-\widehat{v},\forall j\in\mathcal{N}\setminus B$

The output of SDP() is the matrix $\mathbf{v}$ containing as columns the unit
vectors $v_{j}$ for $j\in\mathcal{N}$ and $\widehat{v}$, and the objective
value $Z$.

At a high level, the semidefinite program aims to identify a set of players
$R\subseteq B$ so that the stretch of the current state for the subgame
defined by the players in $R$ is at least $\sigma$. The special vector
$\widehat{v}$ is used as a basis for the orientation of the remaining vectors.
The vectors $v_{j}$ for $j\in\mathcal{N}\setminus B$ are set to
$-\widehat{v}$, indicating that the players in $\mathcal{N}\setminus B$ are
not considered for inclusion in the set $R$. For $j\in B$, vector $v_{j}$
indicates whether player $j$ belongs to set $R$ (when $v_{j}=\widehat{v}$) or
not (when $v_{j}=-\widehat{v}$). Of course, the vectors in a solution of the
semidefinite program can be much different than these two extreme ones. As we
will see, if the semidefinite program has non-positive objective value, no set
$R$ of players defining a subgame of high stretch at the current state exists,
and this provides a useful condition for our algorithm. Otherwise, a
subsequent appropriately performed (randomized) rounding of the SDP solution
will yield a set of simultaneous (global) moves by players that increase the
potential considerably.

This is done by the routine ROUND(), which takes as input a cut game
$\mathcal{G}$ with a set $\mathcal{N}$ of $n$ players, a state $S$, a subset
of players $B\subseteq\mathcal{N}$, and a matrix $\mathbf{v}$ having vectors
$v_{j}$ for each player $j\in B$ and the special vector $\widehat{v}$ as
columns. ROUND() performs
$\frac{23040n^{2}}{\varepsilon^{3}}\cdot\ln{\left(\frac{414720n^{4}}{\varepsilon^{4}}\right)}$
iterations. In each of them, it decides a set $R\subseteq\mathcal{N}$ of
players by rounding the set of unit vectors $\mathbf{v}$. Rounding is
performed as follows. First, for $j\in B$, each vector $v_{j}$ is rotated to
produce the unit vector $v^{\prime}_{j}$ as follows: $v^{\prime}_{j}$ is the
unit vector in $\mathbb{R}^{n}$ that lies on the plane defined by vectors
$v_{j}$ and $\widehat{v}$ and is at angle
$\frac{\pi}{2}\cdot(1-v_{j}\cdot\widehat{v})$ from vector $\widehat{v}$ and at
angle
$|\arccos{(v_{j}\cdot\widehat{v})}-\frac{\pi}{2}\cdot(1-v_{j}\cdot\widehat{v})|$
from vector $v_{j}$. Then, a random unit vector $r\in\mathbb{R}^{n}$ is
picked. For $j\in B$, player $j$ is included in set $R$ if the inner products
$v^{\prime}_{j}\cdot r$ and $\widehat{v}\cdot r$ have the same sign.
Informally, we can view vector $r$ as the unit normal vector of a random
hyperplane; then, player $j$ is included in set $R$ if the rotated vector
$v^{\prime}_{j}$ and vector $\widehat{v}$ are on the same side of the
hyperplane. ROUND() keeps the set $R$ of players in the rounding iteration
that produces the highest potential increase
$\Phi_{R}(S_{-R},S^{\prime}_{R})-\Phi_{R}(S)$ and returns state
$(S_{-R},S^{\prime}_{R})$ as output.

Now, the routine GLOBAL() (see Algorithm 3) takes as input the cut game
$\mathcal{G}$, a state $S$, and a subset of players $B$; on exit, it returns
an output state and a flag indicating whether the output state is different
than the input one. GLOBAL() repeatedly runs the routing SDP(), as long as the
objective value of the demidefinite program it solves is positive. Then, it
executes the routine ROUND() to round the solution of the semidefinite program
and decide, in this way, the set of players who will change their strategy
simultaneously. Essentially, this implements a global move. Prior to executing
SDP(), the routine LOCAL() is executed to make sure that the input state to
SDP() is an approximate equilibrium for the players in $B$.

Input: A cut game $\mathcal{G}$ with a set $\mathcal{N}$ of $n$ players, a
state $S$, and subset $B\subseteq\mathcal{N}$ of players

Output: A state of $\mathcal{G}$ and a Boolean flag

1: Set $change\leftarrow\textbf{false}{}$;

2: Update $(S,change)\leftarrow\text{LOCAL}(\mathcal{G},S,B,\tau)$

3: Set $(\mathbf{v},Z)\leftarrow\text{SDP}(\mathcal{G},S,B)$;

4: while $Z>0$ do

5: Update $S\leftarrow\text{ROUND}(\mathcal{G},S,B,\mathbf{v})$;

6: Update $change\leftarrow\textbf{true}{}$;

7: Update $S\leftarrow\text{LOCAL}(\mathcal{G},S,B,\tau)$;

8: Set $(\mathbf{v},Z)\leftarrow\text{SDP}(\mathcal{G},S,B)$;

9: end while

10: return $(S,change)$;

ALGORITHM 3 The routine GLOBAL()

This completes the detailed description of our algorithm. We will prove the
following statement.

######  Theorem 3.1.

Let $\varepsilon\in(0,1/4]$. On input a cut game $\mathcal{G}$ with $n$
players, Algorithm 1 computes a $(\rho+\varepsilon)$-approximate pure Nash
equilibrium $S_{\text{out}}$ in time $\text{poly}(n,1/\varepsilon)$ with
probability at least $1-1/n$, where $\rho=\frac{1+2\sqrt{13}}{3}\approx
2.7371$.

##  4 Properties of global moves

We devote this section to proving two important properties of routines SDP()
and ROUND(). In our analysis, we denote the upper boundary of block $B_{i}$ by
$W_{i}$ and by $W_{m+1}$ the lower boundary of block $B_{m}$, i.e.,
$W_{i}=U_{\max}\Delta^{1-i}$ for $i=1,2,...,m+1$. So, the players of block
$B_{i}$ are those with maximum utility $U_{j}\in(W_{i+1},W_{i}]$.

The next lemma guarantees that, whenever routine GLOBAL() terminates, the
state returned has stretch at most $\sigma$ for any subgame defined by subsets
of players in block $B_{i+1}$.

######  Lemma 4.1.

Consider the execution of routine $\text{SDP}()$ during phase $i\geq 0$, i.e.,
SDP() takes as input the cut game $\mathcal{G}$, the block $B_{i+1}$ as the
set of players $B$, and a state $S$ that is a $\tau$-approximate pure Nash
equilibrium for the players in $B_{i+1}$. If the objective value $Z$ of the
semidefinite program that SDP() returns is non-positive, then for every set of
players $R\subseteq B_{i+1}$, it holds that
$\sigma\cdot\Phi_{R}(S)\geq\Phi_{R}(S_{-R},S^{\prime}_{R})$.

###### Proof.

Assume otherwise and let $R$ be a non-empty subset of $B_{i+1}$ such that

$\displaystyle\sigma\cdot\Phi_{R}(S)$
$\displaystyle<\Phi_{R}(S_{-R},S^{\prime}_{R}).$ (1)

Let $\widehat{v}$ be an arbitrary unit vector and set $v_{j}=\widehat{v}$ for
$j\in R$ and $v_{j}=-\widehat{v}$ for $j\in\mathcal{N}\setminus R$. Since
$R\not=\emptyset$, there is at least one player $j^{*}\in R$ such that
$v_{j^{*}}=\widehat{v}$. Then,
$3+v_{j^{*}}\cdot\widehat{v}+v_{k}\cdot\widehat{v}-v_{j^{*}}\cdot v_{k}=4$ for
every $k\in\mathcal{N}\setminus\\{j^{*}\\}$ and

$\displaystyle\sum_{(j,k)\in\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(3+v_{j}\cdot\widehat{v}+v_{k}\cdot\widehat{v}-v_{j}\cdot
v_{k})}$ $\displaystyle\geq 4\cdot w(\text{CUT}_{j^{*}}(S))\geq
U_{j^{*}}\geq\min_{j\in B_{i+1}}{U_{j}},$

implying that $\mathbf{v}$ is a feasible solution to the semidefinite program
used in the call of $\text{SDP}(\mathcal{G},S,B_{i+1})$. The second last
inequality follows using Claim 2.2, since the $\tau$-approximate (and,
consequently, the $3$-approximate) equilibrium condition is satisfied for
player $j^{*}$.

Now, observe that edge $(j,k)$ belongs to $\text{CUT}_{R}(S)$ if it belongs to
$\text{CUT}_{B_{i+1}}(S)$ and at least one of the players $j$ and $k$ belongs
to $R$. Also, the quantity
$\frac{1}{4}\cdot(3+v_{j}\cdot\widehat{v}+v_{k}\cdot\widehat{v}-v_{j}\cdot
v_{k})$ is equal to $1$ if one of the players $j$ and $k$ belongs to $R$ and
is equal to $0$, otherwise. Thus,

$\displaystyle\Phi_{R}(S)$
$\displaystyle=\sum_{(j,k)\in\text{CUT}_{R}(S)}{w_{jk}}=\frac{1}{4}\cdot\sum_{(j,k)\in\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(3+v_{j}\cdot\widehat{v}+v_{k}\cdot\widehat{v}-v_{j}\cdot
v_{k})}.$ (2)

Furthermore, observe that edge $(j,k)$ belongs to
$\text{CUT}_{R}(S_{-R},S^{\prime}_{R})$ if it belongs to
$\text{CUT}_{B_{i+1}}(S)$ and both players $j$ and $k$ belong to $R$, or it
does not belong to $\text{CUT}_{B_{i+1}}(S)$ and exactly one of players $j$
and $k$ belongs to $R$. The quantity
$\frac{1}{4}\cdot(1+v_{j}\cdot\widehat{v}+v_{k}\cdot\widehat{v}+v_{j}\cdot
v_{k})$ is equal to $1$ if both players $j$ and $k$ belong to $R$ and is equal
to $0$, otherwise. Also, the quantity $\frac{1}{2}\cdot(1-v_{j}\cdot v_{k})$
is equal to $1$ if exactly one of the players $j$ and $k$ belongs to $R$ and
is equal to $0$, otherwise. Thus,

$\displaystyle\Phi_{R}(S_{-R},S^{\prime}_{R})$
$\displaystyle=\sum_{(j,k)\in\text{CUT}_{R}(S_{-R},S^{\prime}_{R})}{w_{jk}}$
$\displaystyle=\frac{1}{2}\cdot\sum_{(j,k)\in
E\setminus\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(1-v_{j}\cdot v_{k})}$
$\displaystyle\quad\,+\frac{1}{4}\cdot\sum_{(j,k)\in\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(1+v_{j}\cdot\widehat{v}+v_{k}\cdot\widehat{v}+v_{j}\cdot
v_{k})}.$ (3)

Using equations (2) and (3) and the definition of the semidefinite program
used in the call of $\text{SDP}(\mathcal{G},S,B_{i+1})$, our assumption (1)
yields

$\displaystyle 0$
$\displaystyle<\Phi_{R}(S_{-R},S^{\prime}_{R})-\sigma\cdot\Phi_{R}(S)$
$\displaystyle=\frac{1}{2}\cdot\sum_{(j,k)\in
E\setminus\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(1-v_{j}\cdot v_{k})}$
$\displaystyle\quad\,-\frac{1}{4}\cdot\sum_{(j,k)\in\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(3\sigma-1+(\sigma-1)\cdot
v_{j}\cdot\widehat{v}+(\sigma-1)\cdot v_{k}\cdot\widehat{v}-(\sigma+1)\cdot
v_{j}\cdot v_{k})}$ $\displaystyle=Z,$

which contradicts the condition on $Z$. The lemma follows. ∎

We now aim to prove (in Lemma 4.3 below) that, whenever the routine ROUND() is
executed on the set of vectors produced by a previous execution of routine
SDP(), the potential increases considerably. To do so, we will use an
important property of each rounding iteration, which we state in Lemma 4.2;
its proof is deferred to Section 6. We denote by $\text{XOR}(j,k)$ the event
that the random hyperplane with unit normal vector $r$ separates the rotated
vectors $v^{\prime}_{j}$ and $v^{\prime}_{k}$, i.e., the quantities
$v^{\prime}_{j}\cdot r$ and $v^{\prime}_{j}\cdot r$ have different signs.

######  Lemma 4.2.

Let $v_{j}$ and $v_{k}$ be unit vectors in $\mathbb{R}^{n}$ and let
$v^{\prime}_{j}$ and $v^{\prime}_{k}$ be the corresponding rotated vectors
with respect to another unit vector $\widehat{v}\in\mathbb{R}^{n}$. Then,

$\displaystyle\Pr[\text{XOR}(j,k)]\geq\frac{1}{4}\cdot(1-v_{j}\cdot v_{k})$
(4)

and

$\displaystyle\Pr[\text{XOR}(j,k)]\leq\frac{1}{8}\cdot(3\rho-1+(\rho-1)\cdot
v_{j}\cdot\widehat{v}+(\rho-1)\cdot v_{k}\cdot\widehat{v}-(\rho+1)\cdot
v_{j}\cdot v_{k}).$ (5)

######  Lemma 4.3.

Consider the execution of routine $\text{SDP}(\mathcal{G},S,B_{i+1})$ during
phase $i\geq 0$. If the solution $\mathbf{v}$ to the semidefinite program
computed by $\text{SDP}(\mathcal{G},S,B_{i+1})$ has objective value $Z>0$,
then, the probability that the subsequent call to
$\text{ROUND}(\mathcal{G},S,B_{i+1},v)$ fails to identify a set of players
$R\subseteq B_{i+1}$ so that
$\Phi_{R}(S_{-R},S^{\prime}_{R})-\Phi_{R}(S)\geq\frac{\varepsilon}{48}\cdot
W_{i+2}$ is at most $\frac{\varepsilon^{4}}{414720n^{4}}$.

###### Proof.

Consider the execution of routine ROUND() in phase $i$ and a rounding
iteration. Let $R\subseteq B_{i+1}$ be the set of players selected. Observe
that the increase in the potential $\Phi_{R}$ from state $S$ to state
$(S_{-R},S^{\prime}_{R})$ is equal to the total weight of the edges $(j,k)$
that do not belong to $\text{CUT}_{B_{i+1}}(S)$ and exactly one of the players
$j$ and $k$ change strategy, minus the total weight of the edges $(j,k)$ that
belong to $\text{CUT}_{B_{i+1}}(S)$ and exactly one of the players $j$ and $k$
change strategy. Using this observation and Lemma 4.2, we have

$\displaystyle\mathbb{E}[\Phi_{R}(S_{-R},S^{\prime}_{R})-\Phi_{R}(S)]$
$\displaystyle=\sum_{(j,k)\in
E\setminus\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot\Pr[\text{XOR}(j,k)]}-\sum_{(j,k)\in\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot\Pr[\text{XOR}(j,k)]}$
$\displaystyle\geq\frac{1}{4}\cdot\sum_{(j,k)\in
E\setminus\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(1-v_{j}\cdot v_{k})}$
$\displaystyle\quad\,-\frac{1}{8}\cdot\sum_{(j,k)\in\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(3\rho-1+(\rho-1)\cdot
v_{j}\cdot\widehat{v}+(\rho-1)\cdot v_{k}\cdot\widehat{v}-(\rho+1)\cdot
v_{j}\cdot v_{k})}$
$\displaystyle=\frac{Z}{2}+\frac{\sigma-\rho}{8}\cdot\sum_{(j,k)\in\text{CUT}_{B_{i+1}}(S)}{w_{jk}\cdot(3+v_{j}\cdot\widehat{v}+v_{k}\cdot\widehat{v}-v_{j}\cdot
v_{k})}$ $\displaystyle>\frac{\varepsilon}{24}\cdot W_{i+2}.$

The last inequality follows by condition $Z>0$, the constraint of the
semidefinite program and the definition of $W_{i+2}$, and the fact that
$\sigma-\rho=\varepsilon/3$.

Now, observe that the random variable $\sum_{j\in
B_{i+1}}{U_{j}}-\Phi_{R}(S_{-R},S^{\prime}_{R})+\Phi_{R}(S)$ is always non-
negative. Applying the Markov inequality on it, we get

$\displaystyle\Pr\left[\Phi_{R}(S_{-R},S^{\prime}_{R})-\Phi_{R}(S)\leq\frac{\varepsilon}{48}\cdot
W_{i+2}\right]$ $\displaystyle=\Pr\left[\sum_{j\in
B_{i+1}}{U_{j}}-\Phi_{R}(S_{-R},S^{\prime}_{R})+\Phi_{R}(S)\geq\sum_{j\in
B_{i+1}}{U_{j}}-\frac{\varepsilon}{48}\cdot W_{i+2}\right]$
$\displaystyle\leq\frac{\sum_{j\in
B_{i+1}}{U_{j}}-\mathbb{E}[\Phi_{R}(S_{-R},S^{\prime}_{R})-\Phi_{R}(S)]}{\sum_{j\in
B_{i+1}}{U_{j}}-\frac{\varepsilon}{48}\cdot W_{i+2}}$
$\displaystyle<\frac{\sum_{j\in B_{i+1}}{U_{j}}-\frac{\varepsilon}{24}\cdot
W_{i+2}}{\sum_{j\in B_{i+1}}{U_{j}}-\frac{\varepsilon}{48}\cdot W_{i+2}}\leq
1-\frac{\frac{\varepsilon}{48}\cdot W_{i+2}}{\sum_{j\in B_{i+1}}{U_{j}}}\leq
1-\frac{\varepsilon\cdot W_{i+2}}{48n\cdot
W_{i+1}}=1-\frac{\varepsilon^{3}}{23040n^{2}}.$

I.e., the probability that
$\Phi_{R}(S_{-R},S^{\prime}_{R})-\Phi_{R}(S)\leq\frac{\varepsilon}{48}\cdot
W_{i+2}$ in a rounding iteration is at most
$1-\frac{\varepsilon^{3}}{23040n^{2}}$. Thus, the probability that the
potential increase is at most $\frac{\varepsilon}{48}\cdot W_{i+2}$ after all
the
$\frac{23040n^{2}}{\varepsilon^{3}}\cdot\ln{\left(\frac{414720n^{4}}{\varepsilon^{4}}\right)}$
rounding iterations in an execution of ROUND() is at most

$\displaystyle\left(1-\frac{\varepsilon^{3}}{23040n^{2}}\right)^{\frac{23040n^{2}}{\varepsilon^{3}}\cdot\ln{\left(\frac{414720n^{4}}{\varepsilon^{4}}\right)}}\leq\frac{\varepsilon^{4}}{414720n^{4}}.$

The last inequality follows by the property $(1-1/t)^{t}\leq 1/e$. ∎

##  5 Proof of Theorem 3.1

We now show how to use the main properties of global moves from Section 4, as
well as three additional claims (Claims 5.1, 5.2, and 5.3) to prove Theorem
3.1. In our proof, we denote by $S^{i}$ the state reached at the end of phase
$i\geq 0$, i.e., $S_{\text{out}}=S^{m}$. We also denote by $R_{i}$ the set of
players that changed their strategy during phase $i$.

For every phase $i>0$, we define the following set of edges:

$\displaystyle A_{i}$
$\displaystyle=\\{(j,k)\in\text{CUT}_{R_{i}}(S^{i-1}):j,k\in R_{i}\cap
B_{i}\\}$ $\displaystyle C_{i}$
$\displaystyle=\\{(j,k)\in\text{CUT}_{R_{i}}(S^{i-1}):j,k\in R_{i}\cap
B_{i+1}\\}$ $\displaystyle D_{i}$
$\displaystyle=\\{(j,k)\in\text{CUT}_{R_{i}}(S^{i-1}):j\in R_{i}\cap
B_{i},k\in R_{i}\cap B_{i+1}\\}$ $\displaystyle F_{i}$
$\displaystyle=\\{(j,k)\not\in\text{CUT}_{R_{i}}(S^{i-1}):j\in R_{i}\cap
B_{i},k\in R_{i}\cap B_{i+1}\\}$ $\displaystyle H_{i}$
$\displaystyle=\\{(j,k)\in\text{CUT}_{R_{i}}(S^{i-1}):j\in R_{i}\cap
B_{i},k\not\in R_{i}\\}$ $\displaystyle I_{i}$
$\displaystyle=\\{(j,k)\not\in\text{CUT}_{R_{i}}(S^{i-1}):j\in R_{i}\cap
B_{i},k\not\in R_{i}\\}$ $\displaystyle J_{i}$
$\displaystyle=\\{(j,k)\in\text{CUT}_{R_{i}}(S^{i-1}):j\in R_{i}\cap
B_{i+1},k\not\in R_{i}\\}$ $\displaystyle K_{i}$
$\displaystyle=\\{(j,k)\not\in\text{CUT}_{R_{i}}(S^{i-1}):j\in R_{i}\cap
B_{i+1},k\not\in R_{i}\\}$

We will express several properties maintained by our algorithm in terms of the
weights of the above edge sets. The first one uses the definition of block
$B_{i+1}$.

######  Claim 5.1.

For every phase $i>0$, it holds
$w(C_{i})+w(D_{i})+w(F_{i})+w(J_{i})+w(K_{i})\leq n\cdot W_{i+1}$.

The next claim uses the main property guaranteed by the last call of routine
SDP() in phase $i-1$.

######  Claim 5.2.

For every phase $i>0$, it holds $-(\sigma-1)\cdot w(A_{i})-\sigma\cdot
w(D_{i})-\sigma\cdot w(H_{i})+w(F_{i})+w(I_{i})\leq 0$.

Finally, our third claim follows by the fact that the players in block
$R_{i}\cap B_{i}$ make $\tau$-moves in phase $i$.

######  Claim 5.3.

For every phase $i>0$, it holds $(\tau-1)\cdot w(A_{i})+(\tau-1)\cdot
w(D_{i})+\tau\cdot w(H_{i})-w(I_{i})+\tau\cdot w(J_{i})-\tau\cdot w(K_{i})<0$.

We are now ready to prove Theorem 3.1. We do so in Lemmas 5.4 and 5.5 below.
Assuming that all calls of routine ROUND() are successful in identifying a set
if players whose change of strategies that increase the potential
considerably, Lemma 5.4 uses Claims 5.1, 5.2, and 5.3 to show that every
players stays at a $(\rho+\varepsilon)$-equilibrium after the phase in which
its strategy is irrevocably decided.

######  Lemma 5.4.

If no call to routine ROUND() ever fails, the state $S_{\text{out}}$ is a
$(\rho+\varepsilon)$-approximate pure Nash equilibrium.

###### Proof.

Let $j$ be a player of block $B_{i}$. Notice that, if $i=m$, player $j$ has no
$\tau$-move (and, hence, no $(\rho+\varepsilon)$-move) to make after the
execution of the last phase. So, in the following, we assume that $0<i\leq
m-1$.

Let $M_{j}$ be the set of edges in $\text{CUT}_{j}(S^{i})$ whose other
endpoint corresponds to a player in blocks $B_{i+1}$, …, $B_{m-1}$. We will
first bound $w(M_{j})$. Notice that $M_{j}\subseteq\cup_{t>i}{\left(H_{t}\cup
J_{t}\right)}$. Hence,

$\displaystyle w(M_{j})$ $\displaystyle\leq\sum_{t>i}{(w(H_{t})+w(J_{t})}).$
(6)

Summing the inequalities in the statements of Claims 5.1, 5.2, and 5.3, after
multiplying the inequality in Claim 5.1 by $\tau$, we get

$\displaystyle(\tau-\sigma)\cdot w(A_{t})+\tau\cdot
w(C_{t})+(2\tau-\sigma-1)\cdot w(D_{t})+(\tau+1)\cdot w(F_{t})$
$\displaystyle+(\tau-\sigma)\cdot w(H_{t})+2\tau\cdot w(J_{t})\leq\tau\cdot
n\cdot W_{t+1}.$

Notice that the LHS is lower-bounded by
$\frac{\varepsilon}{3}\cdot(w(H_{t})+w(J_{t}))$. Thus,

$\displaystyle w(H_{t})+w(J_{t})$ $\displaystyle\leq 9n\cdot
W_{t+1}/\varepsilon.$

Now, inequality (6) yields

$\displaystyle w(M_{j})$
$\displaystyle\leq\frac{9n}{\varepsilon}\cdot\sum_{t>i}{W_{t+1}}\leq\frac{9n}{\varepsilon}\cdot
W_{i+2}\sum_{t=i+1}^{\infty}{\Delta^{i+1-t}}\leq 10n\cdot
W_{i+2}/\varepsilon.$ (7)

Now, notice that the edges in $M_{j}$ are those which can be removed from the
cut due to moves by players in phases $i+1$, …, $m$, and thus decrease the
utility of player $j$ by up to $w(M_{j})$. I.e.,

$\displaystyle u_{j}(S^{m})$ $\displaystyle\geq u_{j}(S^{i})-w(M_{j}).$ (8)

Furthermore, the edges in $M_{j}$ are those which are not included in
$\text{CUT}_{j}(S^{i}_{-j},s^{\prime}_{j})$ and thus do not contribute to the
utility player $j$ would have by changing her strategy. Moves by players in
phases $i+1$, …, $m$ may increase the utility player $j$ would have by
deviating by at most $w(M_{j})$, i.e.,

$\displaystyle u_{j}(S^{i}_{-j},s^{\prime}_{j})$ $\displaystyle\geq
u_{j}(S^{m}_{-j},s^{\prime}_{j})-w(M_{j}).$ (9)

We are ready to prove that player $j$ has no $(\rho+\varepsilon)$-move to make
after the execution of the last phase of the algorithm, using inequalities
(7), (8), and (9), and the fact that player $j$ had no $\tau$-move to make at
the end of phase $i$. We have

$\displaystyle(\rho+\varepsilon)\cdot u_{j}(S^{m})$
$\displaystyle\geq(\rho+\varepsilon)\cdot
u_{j}(S^{i})-10(\rho+\varepsilon)n\cdot W_{i+2}/\varepsilon$
$\displaystyle\geq\tau\cdot u_{j}(S^{i})-30n\cdot
W_{i+2}/\varepsilon+(\rho+\varepsilon-\tau)\cdot u_{j}(S^{i})$
$\displaystyle\geq u_{j}(S^{i}_{-j},s^{\prime}_{j})-30n\cdot
W_{i+2}/\varepsilon+\frac{\varepsilon}{3}\cdot u_{j}(S^{i})$
$\displaystyle\geq u_{j}(S^{m}_{-j},s^{\prime}_{j})-40n\cdot
W_{i+2}/\varepsilon+\frac{\varepsilon}{3}\cdot u_{j}(S^{i}).$ (10)

Now, since player $j$ has no $\tau$-move at state $S^{i}$, Claim 2.2 implies
that $u_{j}(S^{i})\geq W_{i+1}/4$ and, by the definition of the blocks,
$u_{j}(S^{i})\geq 120n\cdot W_{i+2}/\varepsilon^{2}$. Then, equation (10)
yields $(\rho+\varepsilon)\cdot u_{j}(S^{m})\geq
u_{j}(S^{m}_{-j},s^{\prime}_{j})$, as desired. ∎

Also, assuming that all calls of routine ROUND() are successful, Lemma 5.5
uses Claims 5.1, 5.2, and 5.3 to bound the total increase of the potential
$\Phi_{R_{i}}$ in phase $i$ and Claim 2.2 and Lemma 4.3 to show that this
increase happens after a small number of local and global moves.

######  Lemma 5.5.

If no call to routine ROUND() ever fails, the algorithm terminates after
performing at most $\mathcal{O}(n^{2}/\varepsilon)$ $\tau$-moves, at most
$\mathcal{O}(n^{3}/\varepsilon^{4})$ calls to routine SDP(), and at most
$\frac{414720n^{3}}{\varepsilon^{4}}$ calls to routine ROUND().

###### Proof.

We will first bound the increase in the potential $\Phi_{R_{i}}$ of phase
$i>0$, proving that

$\displaystyle\Phi_{R_{i}}(S^{i})-\Phi_{R_{i}}(S^{i-1})$ $\displaystyle\leq
18n\cdot W_{i+1}/\varepsilon.$ (11)

Observe that $\text{CUT}_{R_{i}}(S^{i-1})=A_{i}\cup C_{i}\cup D_{i}\cup
H_{i}\cup J_{i}$ and $\text{CUT}_{R_{i}}(S^{i})=A_{i}\cup C_{i}\cup D_{i}\cup
I_{i}\cup K_{i}$. Hence,
$\Phi_{R_{i}}(S^{i-1})=w(A_{i})+w(C_{i})+w(D_{i})+w(H_{i})+w(J_{i})$,
$\Phi_{R_{i}}(S^{i})=w(A_{i})+w(C_{i})+w(D_{i})+w(I_{i})+w(K_{i})$ and, thus,

$\displaystyle\Phi_{R_{i}}(S^{i})-\Phi_{R_{i}}(S^{i-1})$
$\displaystyle=-w(H_{i})+w(I_{i})-w(J_{i})+w(K_{i})$ (12)

We now multiply the inequalities in Claims 5.1, 5.2, and 5.3 by
$\frac{\sigma(\tau-1)}{\tau-\sigma}$, $\frac{\tau-1}{\tau-\sigma}$, and
$\frac{\sigma-1}{\tau-\sigma}$, respectively, and sum them up. We obtain

$\displaystyle\frac{\sigma(\tau-1)}{\tau-\sigma}\cdot
w(C_{i})+\frac{(\sigma-1)(\tau-1)}{\tau-\sigma}\cdot
w(D_{i})+\frac{(\sigma+1)(\tau-1)}{\tau-\sigma}\cdot w(F_{i})$
$\displaystyle-w(H_{i})+w(I_{i})+\frac{2\tau\sigma-\tau-\sigma}{\tau-\sigma}\cdot
w(J_{i})+w(K_{i})\leq\frac{\sigma(\tau-1)}{\tau-\sigma}\cdot n\cdot
W_{i+1}\leq 18n\cdot W_{i+1}/\varepsilon.$

The proof of inequality (11) follows by observing that all coefficients in the
RHS of this last inequality besides that of term $w(H_{i})$ are positive and
thus the RHS is lower-bounded by the LHS of (12).

By Claim 2.2, we have that a $\tau$-move increases the potential by at least
$W_{i+1}/4$. By the bound on the potential increase in the whole phase $i$
from (11), we obtain that no more than $72n/\varepsilon$ $\tau$-moves take
place in phase $i$. The bound on the total number of $\tau$-moves follows
since there are at most $n$ phases containing some player.

Similarly, by Lemma 4.3, we have that a successful call to routine
$\text{ROUND}(\mathcal{G},S,B_{i+1})$ at phase $i>0$ increases the potential
by at least $\varepsilon\cdot W_{i+2}/48$. By the bound on the potential
increase in the whole phase $i$ from (11) and the relation
$W_{i+1}/W_{i+2}=\Delta=480n/\varepsilon^{2}$, we obtain that no more than
$414720n^{2}/\varepsilon^{4}$ calls to routine
$\text{ROUND}(\mathcal{G},S,B_{i+1})$ take place in phase $i$. Again, the
bound on the total number of callls to ROUND() follows since there are at most
$n$ phases containing some player.

Regarding the number of calls to routine $\text{SDP}()$ within a phase, we
claim that this is at most the number of $\tau$-moves plus twice the number of
calls to routine $\text{ROUND}()$ plus $1$. Indeed, in each execution of the
routine $\text{GLOBAL}()$ in which $\text{ROUND}()$ is executed $t>0$ times,
there are at most $t+1\leq 2t$ executions of $\text{SDP}()$. Also, in each
execution of the routing $\text{GLOBAL}()$ in which $\text{ROUND}()$ is not
executed, the number of executions of $\text{GLOBAL}()$ (and, consequently, of
$\text{SDP}()$) is at most the number of $\tau$-moves, besides in the last
round of the phase, where we do not have any $\tau$-move but there is one
$\text{SDP}()$ call. Hence, a bound of $\mathcal{O}(n^{2}/\varepsilon^{4})$ on
the number of $\text{SDP}()$ calls in a phase follows by the bounds on the
number of $\tau$-moves and $\text{ROUND}()$ calls in a phase. The bound of
$\mathcal{O}(n^{3}/\varepsilon^{4})$ on the total number of executions of
$\text{SDP}()$ follows since there are at most $n$ phases containing some
player. ∎

To complete the proof of Theorem 3.1 after having proved Lemmas 5.4 and 5.5,
it suffices to show that the probability that a call to routine ROUND() fails
to identify a set of players whose change of strategies increase the potential
considerably is at most $1/n$. This can be done by a simple application of the
union bound: there are at most $\frac{414720n^{3}}{\varepsilon^{4}}$
executions of routine ROUND() and, by Lemma 4.3, each of them fails with
probability at most $\frac{\varepsilon^{4}}{414720n^{4}}$.

##  6 Properties of randomized rounding

In this section, we prove the two inequalities of Lemma 4.2. Let
$\theta_{j},\theta_{k}\in[0,\pi]$ be the angles vectors $v_{j}$ and $v_{k}$
form with vector $\widehat{v}$ and $\phi$ be the rotation angle vector $v_{k}$
forms with the two-dimensional plane defined by vectors $v_{j}$ and
$\widehat{v}$. Without loss of generality, we can assume that
$\theta_{j}\geq\theta_{k}$ and, furthermore, that vectors $\widehat{v}$,
$v_{j}$, and $v_{k}$ are lying in three dimensions and are defined as
$\widehat{v}=(1,0,0)$, $v_{j}=(\cos{\theta_{j}},\sin{\theta_{j}},0)$, and
$v_{k}=(\cos{\theta_{k}},\sin{\theta_{k}}\cdot\cos{\phi},\sin{\theta_{k}}\cdot\sin{\phi})$.
Denoting the rotation function by $f$ (i.e.,
$f(\theta)=\frac{\pi}{2}\cdot(1-\cos{\theta})$ for $\theta\in[0,\pi]$), we
have that the rotated vectors of $v_{j}$ and $v_{k}$ are
$v^{\prime}_{j}=(\cos{f(\theta_{j})},\sin{f(\theta_{j})},0)$ and
$v^{\prime}_{k}=(\cos{f(\theta_{k})},\sin{f(\theta_{k})}\cdot\cos{\phi},\sin{f(\theta_{k})}\cdot\sin{\phi})$,
respectively. These definitions yield

$\displaystyle v^{\prime}_{j}\cdot v^{\prime}_{k}$
$\displaystyle=\cos{f(\theta_{j})}\cdot\cos{f(\theta_{k})}+\sin{f(\theta_{j})}\cdot\sin{f(\theta_{k})}\cdot\cos{\phi}$
(13)

and

$\displaystyle v_{j}\cdot v_{k}$
$\displaystyle=\cos{\theta_{j}}\cdot\cos{\theta_{k}}+\sin{\theta_{j}}\cdot\sin{\theta_{k}}\cdot\cos{\phi}.$
(14)

The probability that a random hyperplane separates the rotated vectors
$v^{\prime}_{j}$ and $v^{\prime}_{k}$ is proportional to the angle between
them, i.e., $\Pr[\text{XOR}(j,k)]=\frac{\arccos{(v^{\prime}_{j}\cdot
v^{\prime}_{k})}}{\pi}$.

###  6.1 Proof of inequality (4) in Lemma 4.2

To prove inequality (4), it suffices to prove that

$\displaystyle\frac{\arccos{(v^{\prime}_{j}\cdot v^{\prime}_{k})}}{\pi}$
$\displaystyle\geq\frac{1-v_{j}\cdot v_{k}}{4},$

or, equivalently,

$\displaystyle v^{\prime}_{j}\cdot
v^{\prime}_{k}-\cos{\left(\frac{\pi}{4}\cdot(1-v_{j}\cdot v_{k})\right)}$
$\displaystyle\leq 0.$ (15)

By (13) and (14), and by setting
$g(x,y,\phi)=\cos{x}\cdot\cos{y}+\sin{x}\cdot\sin{y}\cdot\cos{\phi}$, the LHS
of (15) becomes

$\displaystyle
g(f(\theta_{j}),f(\theta_{k}),\phi)-\cos{\left(\frac{\pi}{4}\cdot(1-g(\theta_{j},\theta_{k},\phi))\right)}.$

Observe that $g$ is a linear function in $\cos{\phi}$, taking values in
$[-1,1]$. To see why, observe that $g(x,y,\phi)\leq g(x,y,0)=\cos{(x-y)}$ and
$g(x,y,\phi)\geq g(x,y,\pi)=\cos{(x+y)}$. Now the derivative of the LHS of
(15) with respect to $\cos{\phi}$ is

$\displaystyle\frac{\partial{g(f(\theta_{j}),f(\theta_{k}),\phi)}}{\partial{\cos{\phi}}}-\frac{\partial{g(\theta_{j},\theta_{k},\phi)}}{\partial{\cos{\phi}}}\cdot\frac{\pi}{4}\cdot\sin{\left(\frac{\pi}{4}\cdot(1-g(\theta_{j},\theta_{k},\phi))\right)},$

which is increasing in $\cos{\phi}$. To see why, observe that the derivative
of function $g(x,y,\phi)$ with respect to $\cos{\phi}$ is equal to
$\sin{x}\cdot\sin{y}$, which is non-negative when $x,y\in[0,\pi]$, and the
quantity inside the $\sin$ is decreasing in $\cos{\phi}$, taking values
between $0$ and $\pi/2$. We conclude that the LHS of (15) is convex in
$\cos{\phi}$. Thus, it is maximized when either $\cos{\phi}=1$ or
$\cos{\phi}=-1$ and it suffices to prove inequality (15) for
$\cos{\phi}\in\\{-1,1\\}$. For $\cos{\phi}=1$, we have
$g(x,y,\phi)=\cos{(x-y)}$, the LHS of (15) becomes

$\displaystyle\cos{(f(\theta_{j})-f(\theta_{k}))}-\cos{\left(\frac{\pi}{4}\cdot(1-\cos{(\theta_{j}-\theta_{k})})\right)},$

and (15) is equivalent to

$\displaystyle|f(\theta_{j})-f(\theta_{k})|-\frac{\pi}{4}\cdot(1-\cos{(\theta_{j}-\theta_{k})})$
$\displaystyle\geq 0.$ (16)

For $\cos{\phi}=-1$, we have $g(x,y,\phi)=\cos{(x+y)}$, the LHS of (15)
becomes

$\displaystyle\cos{(f(\theta_{j})+f(\theta_{k}))}-\cos{\left(\frac{\pi}{4}\cdot(1-\cos{(\theta_{j}+\theta_{k})})\right)},$

and (15) is equivalent to

$\displaystyle
f(\theta_{j})+f(\theta_{k})-\frac{\pi}{4}\cdot(1-\cos{(\theta_{j}+\theta_{k})})$
$\displaystyle\geq 0.$ (17)

We will complete the proof by showing that both (16) and (17) are true for the
particular rotation function $f(\theta)=\frac{\pi}{2}\cdot(1-\cos{(\theta)})$
we use. Without loss of generality, assume that
$0\leq\theta_{k}\leq\theta_{j}=\theta_{k}+x\leq\pi$ with
$x\in[0,\pi-\theta_{k}]$. Then, using our specific rotation function, the LHS
of inequality (16) can be written as

$\displaystyle\frac{\pi}{4}\cdot\left(2\cos{\theta_{k}}-2\cos{(\theta_{k}+x)}-1+\cos{x}\right)$
$\displaystyle=\frac{\pi}{2}\cdot\left(2\sin{\left(\theta_{k}+\frac{x}{2}\right)}\cdot\sin{\frac{x}{2}}-\sin^{2}{\frac{x}{2}}\right)$
$\displaystyle\geq\frac{\pi}{2}\cdot\sin^{2}{\frac{x}{2}}\geq 0,$

which proves inequality (16). The first inequality follows since our
assumption for $\theta_{k}$ and $x$ imply that
$\frac{x}{2}\leq\theta_{k}+\frac{x}{2}\leq\pi-\frac{x}{2}$, which yields
$\sin{\left(\theta_{k}+\frac{x}{2}\right)}\geq\sin{\frac{x}{2}}$.

The LHS of inequality (17) becomes

$\displaystyle\frac{\pi}{2}\cdot\left(2-\cos{(\theta_{k}+x)}-\cos{\theta_{k}}\right)-\frac{\pi}{4}\cdot\left(1-\cos{(2\theta_{k}+x)}\right)$
$\displaystyle=\frac{\pi}{2}\cdot\left(1-2\cos{\left(\theta_{k}+\frac{x}{2}\right)}\cdot\cos{\frac{x}{2}}+\cos^{2}{\left(\theta_{k}+\frac{x}{2}\right)}\right).$

Since $\cos{\frac{x}{2}}$ takes values in $[-1,1]$, the quantity inside this
last parenthesis is between the values
$\left(1-\cos{\left(\theta_{k}+\frac{x}{2}\right)}\right)^{2}$ and
$\left(1+\cos{\left(\theta_{k}+\frac{x}{2}\right)}\right)^{2}$, which are both
clearly non-negative. The proof of inequality (17) follows. ∎

###  6.2 Proof of inequality (5) in Lemma 4.2

To prove inequality (5), it suffices to prove that

$\displaystyle\frac{\arccos{(v^{\prime}_{j}\cdot
v^{\prime}_{k})}}{\pi}-\frac{1}{8}\cdot\left(3\rho-1+(\rho-1)\cdot
v_{j}\cdot\widehat{v}+(\rho-1)\cdot v_{k}\cdot\widehat{v}-(\rho+1)\cdot
v_{j}\cdot v_{k}\right)\leq 0.$ (18)

We have verified (18) in its general form by extensive numerical computations
using Mathematica (version 13.0) and explain how we do so later in this
section. Until then, we present a formal analysis for the simpler case where
the vectors $v_{j}$, $v_{k}$, and $\widehat{v}$ lie on the same
$2$-dimensional plane. This includes the values of parameters $\theta_{j}$,
$\theta_{k}$, and $\phi$ for which inequality (18) is tight and has allowed us
to compute the approximation factor $\rho$ explicitly, as a function of a
quadratic equation. We distinguish between two cases, depending on whether
$\phi$ is equal to $0$ or $\pi$.

#### Formal proof of inequality (18) when $\phi=0$.

In this case, equations (13) and (14) yield

$\displaystyle v^{\prime}_{j}\cdot v^{\prime}_{k}$
$\displaystyle=\cos{(f(\theta_{j})-f(\theta_{k}))}=\cos{\left(\frac{\pi}{2}\cdot(\cos{\theta_{k}}-\cos{\theta_{j}})\right)}.$

and $v_{j}\cdot v_{k}=\cos{(\theta_{j}-\theta_{k})}$, respectively, and the
LHS of (18) becomes

$\displaystyle\frac{1}{2}\cdot(\cos{\theta_{k}}-\cos{\theta_{j}})-\frac{3\rho-1}{8}-\frac{\rho-1}{8}\cdot\left(\cos{\theta_{j}}+\cos{\theta_{k}}\right)+\frac{\rho+1}{8}\cdot\cos{(\theta_{j}-\theta_{k})}$
$\displaystyle=-\frac{\rho}{2}+\sin{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\cdot\sin{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}-\frac{\rho-1}{4}\cdot\cos{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\cdot\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}$
$\displaystyle\quad\,+\frac{\rho+1}{4}\cdot\cos^{2}{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}.$
(19)

Applying the inequality $x\cdot y\leq c\cdot x^{2}+\frac{1}{4c}\cdot y^{2}$
for $c=\frac{1+\sqrt{13}}{4}$,
$x=\sin{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}$, and
$y=\sin{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}$, we obtain

$\displaystyle\sin{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\cdot\sin{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}\leq\frac{1+\sqrt{13}}{4}\cdot\sin^{2}{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}+\frac{\sqrt{13}-1}{12}\cdot\sin^{2}{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}$
$\displaystyle=\frac{1+2\sqrt{13}}{6}-\frac{1+\sqrt{13}}{4}\cdot\cos^{2}{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}-\frac{\sqrt{13}-1}{12}\cdot\cos^{2}{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}.$

Using this inequality and the fact that $\rho=\frac{1+2\sqrt{13}}{3}$, the RHS
of equation (19) is at most

$\displaystyle-\frac{\rho}{2}+\frac{1+2\sqrt{13}}{6}-\frac{\sqrt{13}-1}{12}\cdot\cos^{2}{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}-\frac{\rho-1}{4}\cdot\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}\cdot\cos{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}$
$\displaystyle-\left(\frac{1+\sqrt{13}}{4}-\frac{\rho+1}{4}\right)\cdot\cos^{2}{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}=-\frac{\sqrt{13}-1}{12}\cdot\left(\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}+\cos{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\right)^{2},$

which is clearly non-positive, completing the proof.

We remark that this last RHS expression is equal to $0$ only when
$\theta_{j}=\pi$. In this case, the RHS of (19) becomes

$\displaystyle-\frac{\rho}{2}+\cos^{2}{\left(\frac{\theta_{k}}{2}\right)}+\frac{\rho-1}{4}\cdot\sin^{2}{\left(\frac{\theta_{k}}{2}\right)}+\frac{\rho+1}{4}\cdot\sin^{2}{\left(\frac{\theta_{k}}{2}\right)}=\frac{2-\rho}{2}\cdot\left(1-\sin^{2}{\left(\frac{\theta_{k}}{2}\right)}\right),$

implying that $(\pi,\pi)$ is the only pair of values for $\theta_{j}$ and
$\theta_{k}$ for which inequality (18) is tight.

#### Formal proof of inequality (18) when $\phi=\pi$.

Then, equations (13) and (14) yield

$\displaystyle v^{\prime}_{j}\cdot v^{\prime}_{k}$
$\displaystyle=\cos{(f(\theta_{j})+f(\theta_{k}))}=\cos{\left(\pi-\frac{\pi}{2}\cdot(\cos{\theta_{j}}+\cos{\theta_{k}})\right)}.$

and $v_{j}\cdot v_{k}=\cos{(\theta_{j}+\theta_{k})}$, respectively. Notice
that

$\displaystyle\frac{\arccos{(v^{\prime}_{j}\cdot v^{\prime}_{k})}}{\pi}$
$\displaystyle=1-\frac{1}{2}\cdot|\cos{\theta_{j}}+\cos{\theta_{k}}|.$

So, we distinguish between two subcases, depending on whether
$\cos{\theta_{j}}+\cos{\theta_{k}}$ is positive or not (and, consequently, on
whether $\theta_{j}+\theta_{k}$ is lower than $\pi$ or not).

If $\cos{\theta_{j}}+\cos{\theta_{k}}>0$ (and $\theta_{j}+\theta_{k}<\pi$),
then $\frac{\arccos{(v^{\prime}_{j}\cdot
v^{\prime}_{k})}}{\pi}=1-\frac{1}{2}\cdot(\cos{\theta_{j}}+\cos{\theta_{k}})$
and the LHS of inequality (18) becomes

$\displaystyle\frac{9-3\rho}{8}-\frac{\rho+3}{8}\cdot(\cos{\theta_{j}}+\cos{\theta_{k}})+\frac{\rho+1}{8}\cdot\cos{(\theta_{j}+\theta_{k})}$
$\displaystyle=\frac{2-\rho}{2}-\frac{\rho+3}{4}\cdot\cos{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\cdot\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}+\frac{\rho+1}{4}\cos^{2}{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}$
$\displaystyle\leq\frac{2-\rho}{2}-\frac{1}{2}\cdot\cos^{2}{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}<0.$

The first inequality follows since
$\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}>0$ and $\theta_{k}\geq 0$
which implies
$\cos{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\geq\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}$.

Otherwise, if $\cos{\theta_{j}}+\cos{\theta_{k}}\leq 0$ (and
$\theta_{j}+\theta_{k}\geq\pi$), then $\frac{\arccos{(v^{\prime}_{j}\cdot
v^{\prime}_{k})}}{\pi}=1+\frac{1}{2}\cdot(\cos{\theta_{j}}+\cos{\theta_{k}})$
and the LHS of inequality (18) becomes

$\displaystyle\frac{9-3\rho}{8}+\frac{5-\rho}{8}\cdot(\cos{\theta_{j}}+\cos{\theta_{k}})+\frac{\rho+1}{8}\cdot\cos{(\theta_{j}+\theta_{k})}$
$\displaystyle=\frac{2-\rho}{2}+\frac{5-\rho}{4}\cdot\cos{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\cdot\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}+\frac{\rho+1}{4}\cos^{2}{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}$
$\displaystyle\leq\frac{2-\rho}{2}+\frac{\rho-2}{2}\cdot\cos^{2}{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}\leq
0.$

The first inequality follows since
$\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}\leq 0$ and
$\cos{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\geq-\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}$.
To see why this last inequality is true, observe that the assumption
$\theta_{j}\in[0,\pi]$ implies that
$\frac{\theta_{j}-\theta_{k}}{2}\leq\pi-\frac{\theta_{j}+\theta_{k}}{2}$ and,
hence,
$\cos{\left(\frac{\theta_{j}-\theta_{k}}{2}\right)}\geq\cos{\left(\pi-\frac{\theta_{j}+\theta_{k}}{2}\right)}=-\cos{\left(\frac{\theta_{j}+\theta_{k}}{2}\right)}$.

Notice that, again, the last inequality is tight only for the pair of values
$(\pi,\pi)$ for $\theta_{j}$ and $\theta_{k}$.

#### Verifying inequality (18) numerically.

We now consider the general case. Define the function

$\displaystyle\lambda(x,y,z)$
$\displaystyle=\frac{\arccos{\left(\cos{f(x)}\cdot\cos{f(y)}+z\cdot\sin{f(x)}\cdot\sin{f(y)}\right)}}{\pi}-\frac{3\rho-1}{8}-\frac{\rho-1}{8}\cdot\cos{x}$
$\displaystyle\quad-\frac{\rho-1}{8}\cdot\cos{y}+\frac{\rho+1}{8}\cdot\cos{x}\cdot\cos{y}+\frac{\rho+1}{8}\cdot
z\cdot\sin{x}\cdot\sin{y},$

for $x\in[0,\pi]$, $y\in[0,\pi]$, and $z\in[L,H]$ with
$L=\frac{-\cos{f(x)}\cos{f(y)}-1}{\sin{f(x)}\sin{f(y)}}$ and
$H=\frac{-\cos{f(x)}\cos{f(y)}+1}{\sin{f(x)}\sin{f(y)}}$. Notice that $[-1,1]$
is a subinterval of $[L,H]$. Now, observe that
$\lambda(\theta_{j},\theta_{k},\cos{\phi})$ is identical to the LHS of
inequality (18), after substituting $v^{\prime}_{j}\cdot v^{\prime}_{k}$ and
$v_{j}\cdot v_{k}$ using (13) and (14), respectively. The derivative of
$\lambda(x,y,z)$ with respect to $z$ is

$\displaystyle\frac{\partial{\lambda(x,y,z)}}{\partial{z}}$
$\displaystyle=-\frac{\sin{f(x)}\cdot\sin{f(y})}{\pi\cdot\sqrt{1-\left(\cos{f(x)}\cdot\cos{f(y)}+z\cdot\sin{f(x)}\cdot\sin{f(y)}\right)^{2}}}+\frac{\rho+1}{8}\cdot\sin{x}\cdot\sin{y},$

and has two roots:

$\displaystyle z_{1}(x,y)$
$\displaystyle=-\frac{\cos{f(x)}\cos{f(y)}}{\sin{f(x)}\sin{f(y)}}-\frac{1}{\sin{f(x)}\cdot\sin{f(y)}}\cdot\sqrt{1-\left(\frac{8\sin{f(x)}\sin{f(y)}}{\pi(\rho+1)\cdot\sin{x}\sin{y}}\right)^{2}}$

and

$\displaystyle z_{2}(x,y)$
$\displaystyle=-\frac{\cos{f(x)}\cos{f(y)}}{\sin{f(x)}\sin{f(y)}}+\frac{1}{\sin{f(x)}\cdot\sin{f(y)}}\cdot\sqrt{1-\left(\frac{8\sin{f(x)}\sin{f(y)}}{\pi(\rho+1)\cdot\sin{x}\sin{y}}\right)^{2}}.$

By inspecting the derivative, we can see that the function $\lambda(x,y,z)$ is
decreasing as $z$ takes values in $[L,z_{1}(x,y)]$, has a local minimum at
$z_{1}(x,y)$, increases as $z$ takes values in $[z_{1}(x,y),z_{2}(x,y)]$, has
a local maximum at $z_{2}(x,y)$, and decreases in $[z_{2}(x,y),H]$. To prove
inequality (18), it suffices to show that

$\displaystyle\max_{\theta_{j},\theta_{k},\phi\in[0,\pi]}{\lambda(\theta_{j},\theta_{k},\cos{\phi}})\leq
0.$ (20)

Given the formal bounds on $\lambda(\theta_{j},\theta_{k},1)$ and
$\lambda(\theta_{j},\theta_{k},-1)$ in our analysis above, we complete the
proof of (20) by showing through extensive numerical computations using
Mathematica that the quantity

$\displaystyle\max_{\begin{subarray}{c}\theta_{j},\theta_{k}\in[0,\pi]:\\\
z_{2}(\theta_{j},\theta_{k})\in[-1,1]\end{subarray}}{\lambda(\theta_{j},\theta_{k},z_{2}(\theta_{j},\theta_{k}))}$
(21)

is upper-bounded by $0$. The contour plot at the left of Figure 1 shows the
values of the quantity
$\max_{\phi\in[0,\pi]}{\lambda(\theta_{j},\theta_{k},\cos{\phi})}$ for all
pairs $(\theta_{j},\theta_{k})\in[0,\pi]^{2}$. The values in the area defined
by the dashed curves are those computed using (21); the remaining values are
the maximum between $\lambda(\theta_{j},\theta_{k},1)$ and
$\lambda(\theta_{j},\theta_{k},-1)$. In this way, we verify that (20) is true
with the inequality being strict everywhere besides the single point
$(\pi,\pi)$. Recall that the formal analysis above has verified that the pair
$(\pi,\pi)$ is the only point at which inequality (18) is tight when vectors
$v_{j}$, $v_{k}$, and $\widehat{v}$ lie on the same $2$-dimensional plane. The
plot at the right of Figure 1 depicts the value of
$\lambda(\theta_{j},\theta_{k},z_{2}(\theta_{j},\theta_{k}))$ for
$\theta_{j}=\theta_{k}=\theta$ being very close to $\pi$.

Figure 1: Numerical evaluation of the quantity
$\max_{\phi\in[0,\pi]}{\lambda(\theta_{j},\theta_{k},\cos{\phi}})$ for all
pairs $(\theta_{j},\theta_{k})\in[0,\pi]^{2}$ (left) and pairs
$(\theta_{j},\theta_{k})$ with $\theta_{j}=\theta_{k}=\theta\in[0,\pi]$
(right).

##  7 Extensions and open problems

We have shown how to compute $2.7371$-approximate pure Nash equilibria in cut
games in polynomial time, providing the first improvement to the
$3$-approximation bound of Bhalgat et al. [7]. With a few minor modifications,
our algorithm works for party affiliation games as well. These are
generalizations of cut games, in which an edge can be either enemy or friend,
giving utility to the players controlling its endpoints when they lie on
different sides or the same side of the cut, respectively.

As future work, it would be interesting to explore whether other rotation
functions, possibly combined with more sophisticated rounding techniques (like
those discussed in [26]), can give further improved results. How close to
almost exact equilibria can we go? Even though we have make progress on this
question here, the gap is still large. Exploring the inapproximability of
equilibria for cut games (possibly, by strengthening the PLS-hardness results
for local MAX-CUT in bounded-degree graphs; see, e.g., [16]) is another
problem that deserves investigation.

## References

  * [1] Heiner Ackermann, Heiko Röglin, and Berthold Vöcking.  On the impact of combinatorial structure on congestion games.  Journal of the ACM, 55(6):25:1–25:22, 2008.
  * [2] Noga Alon and Assaf Naor.  Approximating the cut-norm via Grothendieck’s inequality.  SIAM Journal on Computing, 35(4):787–803, 2006.
  * [3] Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden.  The price of stability for network design with fair cost allocation.  SIAM Journal on Computing, 38(4):1602–1623, 2008.
  * [4] Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab S. Mirrokni, and Alexander Skopalik.  Fast convergence to nearly optimal solutions in potential games.  In Proceedings 9th ACM Conference on Electronic Commerce (EC), pages 264–273, 2008.
  * [5] Maria-Florina Balcan, Avrim Blum, and Yishay Mansour.  Improved equilibria via public service advertising.  In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 728–737, 2009.
  * [6] Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna.  Nash dynamics in congestion games with similar resources.  In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE), pages 362–373, 2009.
  * [7] Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna.  Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games.  In Proceedings of the 11th ACM Conference on Electronic Commerce (EC), pages 73–82, 2010.
  * [8] Vittorio Bilò and Mauro Paladini.  On the performance of mildly greedy players in cut games.  Journal of Combinatorial Optimization, 32(4):1036–1051, 2016.
  * [9] Ioannis Caragiannis and Angelo Fanelli.  On approximate pure Nash equilibria in weighted congestion games with polynomial latencies.  Journal of Computer and System Sciences, 117:40–48, 2021.
  * [10] Ioannis Caragiannis, Angelo Fanelli, and Nick Gravin.  Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games.  Algorithmica, 77(4):1143–1158, 2017.
  * [11] Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik.  Efficient computation of approximate pure Nash equilibria in congestion games.  In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 532–541, 2011.
  * [12] Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik.  Approximate pure Nash equilibria in weighted congestion games: Existence, efficient computation, and structure.  ACM Transactions on Economics and Computation, 3(1):2:1–2:32, 2015.
  * [13] Moses Charikar and Anthony Wirth.  Maximizing quadratic programs: Extending Grothendieck’s inequality.  In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), pages 54–60, 2004.
  * [14] Steve Chien and Alistair Sinclair.  Convergence to approximate Nash equilibria in congestion games.  Games and Econonic Behavior, 71(2):315–327, 2011.
  * [15] George Christodoulou, Vahab S. Mirrokni, and Anastasios Sidiropoulos.  Convergence and approximation in potential games.  Theoretical Computer Science, 438:13–27, 2012.
  * [16] Robert Elsässer and Tobias Tscheuschner.  Settling the complexity of local max-cut (almost) completely.  In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), Part I, pages 171–182, 2011.
  * [17] Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar.  The complexity of pure Nash equilibria.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 604–612, 2004.
  * [18] Uriel Feige and Michel X. Goemans.  Aproximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT.  In Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems (ISTCS), pages 182–189, 1995.
  * [19] Matthias Feldotto, Martin Gairing, and Alexander Skopalik.  Bounding the potential function in congestion games and approximate pure Nash equilibria.  In Proceedings of the 10th International Conference on Web and Internet Economics (WINE), pages 30–43, 2014.
  * [20] Martin Gairing, Kostas Kollias, and Grammateia Kotsialou.  Existence and efficiency of equilibria for cost-sharing in generalized weighted congestion games.  ACM Transactions on Economics and Computation, 8(2):11:1–11:28, 2020.
  * [21] Yiannis Giannakopoulos, Georgy Noarov, and Andreas S. Schulz.  Computing approximate equilibria in weighted congestion games via best-responses.  Mathematics of Operations Research, 47(1):643–664, 2022.
  * [22] Michel X. Goemans, Li (Erran) Li, Vahab S. Mirrokni, and Marina Thottan.  Market sharing games applied to content distribution in ad hoc networks.  IEEE Journal on Selected Areas in Communications, 24(5):1020–1033, 2006.
  * [23] Michel X. Goemans and David P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  Journal of the ACM, 42(6):1115–1145, 1995.
  * [24] David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis.  How easy is local search?  Journal of Computer and System Sciences, 37(1):79–100, 1988.
  * [25] Elias Koutsoupias and Christos H. Papadimitriou.  Worst-case equilibria.  Computer Science Review, 3(2):65–69, 2009.
  * [26] Michael Lewin, Dror Livnat, and Uri Zwick.  Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems.  In Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 67–82, 2002.
  * [27] Dov Monderer and Lloyd S. Shapley.  Potential games.  Games and Economic Behavior, 14(1):124–143, 1996.
  * [28] Noam Nisan and Amir Ronen.  Algorithmic mechanism design.  Games and Economic Behavior, 35(1-2):166–196, 2001.
  * [29] James B. Orlin, Abraham P. Punnen, and Andreas S. Schulz.  Approximate local search in combinatorial optimization.  SIAM Journal on Computing, 33(5):1201–1214, 2004.
  * [30] Robert W. Rosenthal.  A class of games possessing pure-strategy Nash equilibria.  International Journal of Game Theory, 2:65–67, 1973.
  * [31] Tim Roughgarden and Éva Tardos.  How bad is selfish routing?  Journal of the ACM, 49(2):236–259, 2002.
  * [32] Alejandro A. Schäffer and Mihalis Yannakakis.  Simple local search problems that are hard to solve.  SIAM Journal on Computing, 20(1):56–87, 1991.
  * [33] Vipin Ravindran Vijayalakshmi and Alexander Skopalik.  Improving approximate pure Nash equilibria in congestion games.  In Proceedings of the 16th International Conference on Web and Internet Economics (WINE), pages 280–294, 2020.
  * [34] Uri Zwick.  Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans.  Manuscript, available at: http://www.cs.tau.ac.il/~zwick/online-papers.html, 2000.

##  Appendix A Omitted proofs

#### Proof of Claim 2.1.

Consider a subgame of $\mathcal{G}$ defined by a subset
$R\subseteq\mathcal{N}$ of players and let $S$ and $(S_{-j},s^{\prime}_{j})$
be two states of the subgame differing in the strategies of player $j\in R$.
By definition, we have

$\displaystyle\Phi_{R}(S)-\Phi_{R}(S_{-j},s^{\prime}_{j})$
$\displaystyle=w(\text{CUT}_{R}(S))-w(\text{CUT}_{R}(S_{-j},s^{\prime}_{j}))$
$\displaystyle=w(\text{CUT}_{j}(S))-w(\text{CUT}_{j}(S_{-j},s^{\prime}_{j}))=u_{j}(S)-u_{j}(S_{-j},s^{\prime}_{j}),$

as desired. ∎

#### Proof of Claim 2.2.

Assume that player $j$ performs a $p$-move, reaching the state
$(S_{-j},s^{\prime}_{j})$ from $S$, after changing her strategy from $s_{j}$
to $s^{\prime}_{j}$. Then, the increase in player $j$’s utility during the
$p$-move is

$\displaystyle u_{j}(S_{-j},s^{\prime}_{j})-u_{j}(S)$
$\displaystyle>(p-1)\cdot u_{j}(S)=\frac{p-1}{2}\cdot
u_{j}(S)+\frac{p-1}{2}\cdot(U_{j}-u_{j}(S_{-j},s^{\prime}_{j}))$
$\displaystyle=\frac{p-1}{2}\cdot
U_{j}-\frac{p-1}{2}\cdot(u_{j}(S_{-j},s^{\prime}_{j})-u_{j}(S)),$

i.e., $u_{j}(S_{-j},s^{\prime}_{j})-u_{j}(S)\geq\frac{p-1}{p+1}\cdot U_{j}$.
Since, by Claim 2.1, $\Phi_{R}$ is an exact potential for any subset of
players $R$ that contains player $j$, we have that
$\Phi_{R}(S_{-j},s^{\prime}_{j})-\Phi_{R}(S)\geq\frac{p-1}{p+1}\cdot U_{j}$ as
well.

Now assume that player $j$ has no $p$-move to make at state $S$. We have

$\displaystyle U_{j}$
$\displaystyle=u_{j}(S)+u_{j}(S_{-j},s^{\prime}_{j})\leq(p+1)\cdot u_{j}(S).$

The claim follows. ∎

#### Proof of Claim 5.1.

Indeed, observe that the edges in sets $C_{i}$, $D_{i}$, $F_{i}$, $J_{i}$, and
$K_{i}$ have at least one of their endpoint corresponding to a player in block
$B_{i+1}$. The inequality follows since the total weight in edges incident to
(the at most $n$) nodes corresponding to players in block $B_{i+1}$ is at most
$W_{i+1}$. ∎

#### Proof of Claim 5.2.

By the definition of routine GLOBAL(), in the last execution of routine SDP()
in phase $i-1$, the objective value of the semidefinite program returned is
non-positive. Then, by applying Lemma 4.1 for the set of players $R_{i}\cap
B_{i}$, we get

$\displaystyle\Phi_{R_{i}\cap B_{i}}(S^{i-1}_{-R_{i}\cap
B_{i}},S^{i}_{R_{i}\cap B_{i}})$ $\displaystyle\leq\sigma\cdot\Phi_{R_{i}\cap
B_{i}}(S^{i-1}).$ (22)

By the definition of the edge sets, notice that $\text{CUT}_{R_{i}\cap
B_{i}}(S^{i-1})=A_{i}\cup D_{i}\cup H_{i}$ and, hence,

$\displaystyle\Phi_{R_{i}\cap B_{i}}(S^{i-1})$
$\displaystyle=w(A_{i})+w(D_{i})+w(H_{i}).$ (23)

Furthermore, $\text{CUT}_{R_{i}\cap B_{i}}(S^{i-1}_{-R_{i}\cap
B_{i}},S^{i}_{R_{i}\cap B_{i}})=A_{i}\cup F_{i}\cup I_{i}$ and, hence,

$\displaystyle\Phi_{R_{i}\cap B_{i}}(S^{i-1}_{-R_{i}\cap
B_{i}},S^{i}_{R_{i}\cap B_{i}})$ $\displaystyle=w(A_{i})+w(F_{i})+w(I_{i}).$
(24)

The claim follows after using equations (23) and (24) to substitute the
potential values in (22), and rearranging. ∎

#### Proof of Claim 5.3.

Consider player $j\in R_{i}\cap B_{i}$ and let $L_{j}$ be the set of edges
incident to node $j$ that belong to the cut after the last $\tau$-move of
player $j$ in phase $i$. The increase in the utility of player $j$ after this
$\tau$-move is higher than $(1-1/\tau)\cdot w(L_{j})$. Now, since
$\Phi_{R_{i}}$ is an exact potential (by Claim 2.1), the increase of the
potential value due to the last $\tau$-move of player $j$ is equal to the
increase of her utility. Thus, the total increase of the potential between
states $S^{i-1}$ and $S^{i}$ is higher than the total utility increase in the
last $\tau$-moves of the players in $R_{i}\cap B_{i}$, i.e.,

$\displaystyle\Phi_{R_{i}}(S^{i})-\Phi_{R_{i}}(S^{i-1})$
$\displaystyle>\sum_{j\in R_{i}\cap B_{i}}{(1-1/\tau)\cdot
w(L_{j})}\geq(1-1/\tau)\cdot w\left(\cup_{j\in R_{i}\cap
B_{i}}{L_{j}}\right).$ (25)

Now, notice that $\text{CUT}_{R_{i}}(S^{i})=A_{i}\cup C_{i}\cup D_{i}\cup
I_{i}\cup K_{i}$, $\text{CUT}_{R_{i}}(S^{i-1})=A_{i}\cup C_{i}\cup D_{i}\cup
H_{i}\cup J_{i}$, and $\cup_{j\in R_{i}\cap
B_{i}}{L_{j}}\supseteq\text{CUT}_{R_{i}\cap B_{i}}(S^{i})=A_{i}\cup D_{i}\cup
I_{i}$. Hence,

$\displaystyle\Phi_{R_{i}}(S^{i})$
$\displaystyle=w(A_{i})+w(C_{i})+w(D_{i})+w(I_{i})+w(K_{i}),$ (26)
$\displaystyle\Phi_{R_{i}}(S^{i-1})$
$\displaystyle=w(A_{i})+w(C_{i})+w(D_{i})+w(H_{i})+w(J_{i}),$ (27)

and

$\displaystyle w\left(\cup_{j\in R_{i}\cap B_{i}}{L_{j}}\right)$
$\displaystyle\geq w(A_{i})+w(D_{i})+w(I_{i}).$ (28)

Using equations (26), (27), and (28) to substitute the potential values and
$w\left(\cup_{j\in R_{i}\cap B_{i}}{L_{j}}\right)$ in (25), we get

$\displaystyle w(I_{i})+w(K_{i})-w(H_{i})-w(J_{i})$
$\displaystyle>(1-1/\tau)\cdot(w(A_{i})+w(D_{i})+w(I_{i})).$

The claim follows by multiplying both sides of this last inequality by $\tau$
and rearranging. ∎