# Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with
Implications for Coordination Problems

Argyrios Deligkas1 Eduard Eiben1 Gregory Gutin1 Philip R. Neary1 &Anders
Yeo2,3 1Royal Holloway, University of London
2University of Southern Denmark
3University of Johannesburg {argyrios.deligkas, eduard.eiben, g.gutin,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We investigate the difficulty of finding economically efficient solutions to
coordination problems on graphs. Our work focuses on two forms of coordination
problem: pure-coordination games and anti-coordination games. We consider
three objectives in the context of simple binary-action polymatrix games: (i)
maximizing welfare, (ii) maximizing potential, and (iii) finding a welfare-
maximizing Nash equilibrium. We introduce an intermediate, new graph-partition
problem, termed MaximumWeightedDigraphPartition, which is of independent
interest, and we provide a complexity dichotomy for it. This dichotomy, among
other results, provides as a corollary a dichotomy for Objective (i) for
general binary-action polymatrix games. In addition, it reveals that the
complexity of achieving these objectives varies depending on the form of the
coordination problem. Specifically, Objectives (i) and (ii) can be efficiently
solved in pure-coordination games, but are NP-hard in anti-coordination games.
Finally, we show that objective (iii) is NP-hard even for simple non-trivial
pure-coordination games.

##  1 Introduction

A coordination problem is one wherein all parties can realize mutual gains,
but only by making mutually consistent decisions. Such problems can range from
small-scale issues, such as arranging where to meet with a friend Schelling
(1978), to larger institutional-level issues, such as ensuring the efficient
functioning of organizations Young (2001).

Broadly speaking there are two kinds of coordination problems: “pure-
coordination games”, in which it is beneficial to act the same as others, and
“anti-coordination games”, where it pays to differentiate your behavior from
that of others. Examples of the former include using euros as currency because
others use euros and driving on the same side of the road as everyone else.
Examples of the latter include not supplying a public good if a neighbor is
already doing so, and choosing a product that is different from the
mainstream.

We zoom in on the payoff-structure of coordination problems and focus on the
following question.

> Are there characteristics inherent to certain coordination problems that
> render them easier to resolve?

In this paper, we adopt the most fundamental framework of multi-player
coordination, and model the two above-mentioned environments as binary-action
polymatrix games Janovskaya (1968). The expressive power of polymatrix games
has made them the “go-to” method to model problems ranging from coordination
games on graphs Apt et al. (2017, 2022); Rahn and Schäfer (2015) and
additively separable hedonic games Bogomolnaia and Jackson (2002), to
building-blocks for hardness reductions Chen et al. (2009); Daskalakis et al.
(2009); Deligkas et al. (2022); Rubinstein (2018) and applications in protein-
function prediction and semi-supervised learning Elezi et al. (2018); Vascon
et al. (2020).

Formally, a polymatrix game is represented by a graph, where every vertex
corresponds to a player, and every edge corresponds to a two-player game that
is played between the adjacent vertices. A player’s payoff is the sum of
payoffs earned from interacting with every player in their neighborhood, where
the same action must be used with each. The graph structure captures the
dependencies of the players, while the payoff structure of the two-player
games models the nature of each pairwise interaction that can, in theory, vary
arbitrarily: from settings of pure competition to those with perfectly aligned
interests. In pure-coordination polymatrix games, every two-player game has as
pure Nash equilibria the two strategy profiles where the players choose the
same action. On the other hand, in anti-coordination polymatrix games, every
two-player game has as pure Nash equilibria the two strategy profiles where
the players choose different actions. See Fig. 1 for $2\times 2$ example of
each.

22[${i}$][${j}$] & one two
one $2,1$ $0,0$
two $0,0$ $1,2$ 22[${i}$][${j}$] & one two
one $9,9$ $2,10$
two $10,2$ $0,0$

Figure 1: Examples of coordination games. Left: Pure-coordination game; Right:
anti-coordination game.

###  1.1 Our Contribution

We provide a comprehensive study for the complexity-landscape of economically-
efficient outcomes for binary-action pure-coordination and anti-coordination
polymatrix games. We focus on the computational complexity of the following
objectives for these classes of games.

Objective (i):

maximize social welfare.

Objective (ii):

maximize a potential function; when the game is pairwise-potential.

Objective (iii):

find a welfare-optimal Nash equilibrium.

We will show that Objectives (i) and (ii) are special cases of a novel graph-
partition problem, that we call MaximumWeightedDigraphPartition (MWDP for
short). This problem is of independent interest, since it includes many well-
known graph-theoretic problems like maximum and minimum cut Korte and Vygen
(2011) as special cases. Our first technical result is a complexity dichotomy
for MWDP (Theorem 2). This result yields as an immediate corollary a dichotomy
for social-welfare outcomes for general binary-action polymatrix games, a
result which, to the best of our knowledge, was not known before.

The dichotomy for MWDP reveals, again as immediate corollary, that anti-
coordination games are significantly harder than pure-coordination games. More
specifically, it shows that Objective (i) can be solved in polynomial time for
pure-coordination games, while it is NP-hard in the worst case for anti-
coordination games. Although the NP-hardness for anti-coordination games was
implied by Cai and Daskalakis Cai and Daskalakis (2011), our result provides a
more fine grained resolution for this problem, since it identifies a much
larger class of games for which the problem is intractable.

Another corollary of our dichotomy is the tractability of Objective (ii) for
pairwise-potential pure-coordination games, i.e., pure-coordination polymatrix
games where every two-player game admits a potential. This result is in stark
contrast to pairwise-potential anti-coordination games where it is known that
not only is it NP-hard to find a potential-maximizing outcome, but it is PLS-
complete, i.e., intractable, to find any local maximum of the potential
function Cai and Daskalakis (2011).

Given the positive results for Objectives (i) and (ii) for pure-coordination
games, one might wonder if Objective (iii) is tractable as well for this type
of game. Observe that for these games it is easy to find an arbitrary Nash
equilibrium: every such game possesses at least two “trivial” Nash equilibria
wherein all players choose the same action. In addition, every potential-
maximizing outcome corresponds to a Nash equilibrium too. Unfortunately, as
our second technical result shows, Objective (iii) becomes immediately
intractable for almost every potential pure-coordination game where one of the
two trivial Nash equilibria is not an obviously-optimal solution. In fact, we
provide a dichotomy for Objective (iii) for the arguably most fundamental
subclass of pure-coordination games, known as threshold games Neary and Newton
(2017).

###  1.2 Further Related Work

Our work relates to several areas of study, including the significance of
coordination problems and the role of maximizing potential in economic
contexts, and issues of computational complexity in algorithmic game theory.

#### Coordination problems in economics.

Since they were introduced in philosopher David Lewis’ study on convention and
language Lewis (1969), coordination games have been one of the modeling tool
of choice for economists, being applied to the adoption of technological
standards Katz and Shapiro (1985); Farrell and Saloner (1985); Arthur (1989),
the setting of macroeconomic policy Cooper and John (1988), the study of bank
runs Diamond and Dybvig (1983), etc.

Pure coordination polymatrix games in particular have received lots of
attention from game theorists. A vast literature considers equilibrium
selection in the case where every two-player game is a “stag-hunt” and finds
that, for almost all network structures, uniform adoption of the “safe” risk-
dominant action is the long run prediction Kandori et al. (1993); Foster and
Young (1990); Young (1993); Ellison (1993); Morris (2000); Peski (2010). The
conclusion of this literature is that even if there is a universally agreed
upon optimal equilibrium, successfully achieving that outcome is far from
assured.

In the above papers, all players are in a sense “the same”, since a common
$2\times 2$ game occurs along every edge of the graph. Pure coordination
polymatrix games with heterogeneous preferences, in particular the language
game Neary (2012) and the threshold model Neary and Newton (2017), will play
an important role in our analysis. We defer a detailed description of these
games to Section 5.

Though of similar importance, anti-coordination polymatrix games, see
Bramoullé Bramoullé (2007), have certainly received less attention. Other
network games wherein action choice is a strategic substitute include those of
public good provision Bramoullé and Kranton (2007); Galeotti et al. (2010).

Coordination problems are of such economic importance that countless
experiments have been performed to try and ascertain how people attempt to
coordinate on optimal outcomes and when they will be successful. Van Huyck et
al. Van Huyck et al. (1990) find that smaller groups successfully coordinate
far more frequently than larger groups. Kearns et al. Kearns et al. (2006) and
McCubbins et al. McCubbins et al. (2009) consider coloring problems (i.e.,
anti-coordination games) on a variety of different network structures. Both
conclude that certain network structures, in particular “small worlds”
networks, are easier for subjects to color successfully.

#### Potential-maximizing equilibria.

Potential games were first introduced by Shapley and Monderer Shapley and
Monderer (1996) and have received significant attention. Potential-maximizing
Nash equilibria are desirable since they are stochastically-stable Blume
(1993), can be uniquely absorbing Hofbauer and Sorger (1999), select risk-
dominant outcomes in games played on random networks Peski (2021), and are
robust in games with incomplete information Ui (2001). Potential games appear
frequently in applied work, for example to study the effects of price
discrimination policies in oligopolies Armstrong and Vickers (2001), the
impact of uncertainty on technology adoption Ostrovsky and Schwarz (2005), and
issues of collective action Myatt and Wallace (2009). Many of the classic
models in applied game theory are potential games including the Cournot model
and congestion games Rosenthal (1973).

#### Nash equilibria in polymatrix games.

Computational aspects of (approximate) Nash equilibria in polymatrix games
received a lot of attention over the years, starting from classical results
from fifty years ago Eaves (1973); Howson Jr (1972); Howson Jr and Rosenthal
(1974); Miller and Zucker (1991), to more recent results Chen et al. (2009);
Daskalakis et al. (2009); Rubinstein (2018), and the very recent dichotomy for
the complexity of finding any approximate well-supported Nash equilibrium in
general binary-action polymatrix games Deligkas et al. (2022). Boodaghians et
al. Boodaghians et al. (2020) studied the smoothed complexity on coordination
polymatrix games, while Aloisio et al. Aloisio et al. (2021) studied an
extension of polymatrix games. The complexity of constrained Nash equilibria
for general polymatrix games were studied in Deligkas et al. (2017), while
Barman et al. (2015); Deligkas et al. (2020); Elkind et al. (2006); Ortiz and
Irfan (2017) study games with tree-underlying structure. Finally, Deligkas et
al. (2016) provides an experimental comparison of various algorithms for
polymatrix games.

##  2 Preliminaries

Given a $2\times 2$ matrix $M$, we denote by $m_{11}$, $m_{12}$, $m_{21}$ and
$m_{22}$ the entries of $M$, such that
$M=\left[\begin{array}[]{cc}m_{11}&m_{12}\\\ m_{21}&m_{22}\\\
\end{array}\right]$. For any graph $G$, we denote $V(G)$ and $E(G)$ the sets
of vertices and edges respectively; if the graph is directed, we use $A(G)$
instead to denote the set of arcs of the graph. We assume knowledge of
standard notions of directed graphs Bang-Jensen and Gutin (2009).

An $n$-player binary-action _polymatrix game_ is defined by a graph $G$, where
each vertex represents a player. Each player $i\in V(G)$ has two actions
called one and two. For each edge $ij\in E(G)$, there is a $2\times 2$ two-
player game $(\Pi^{ij},\Pi^{ji})$, where matrix $\Pi^{ij}$ gives the payoffs
that player $i$ obtains from their interaction with player $j$, and likewise
matrix $\Pi^{ji}$ gives the payoffs player $j$ gets with the interaction with
player $i$.

A pure _strategy profile_ $\mathbf{s}=(s_{1},s_{2},\dots,s_{n})$ specifies an
action for each of the players; we will use $S$ to denote the set of all
strategy profiles. It is convenient to think of $s_{i}=(1,0)^{T}$ when player
$i$ chooses action one and $s_{i}=(0,1)^{T}$ when they choose action two. For
each strategy profile $\mathbf{s}\in S$, the payoff of player $i$ is
$p_{i}(\mathbf{s}):=s_{i}^{T}\cdot\sum_{j\;:\;ij\in E(G)}\Pi^{ij}\cdot s_{j}$.
In other words, the payoff obtained by a player is the sum of the payoffs
obtained from the interaction with every neighboring player, where the same
action must be used with each.

We are interested in computing welfare-optimal strategy profiles and in
finding pure strategy Nash equilibrium profiles (and in the combination of
both concepts).

######  Definition 1.

The social welfare of strategy profile $\mathbf{s}$ is
$\mathcal{W}{(\mathbf{s}{})}:=\sum_{i\in V}p_{i}(\mathbf{s}{})$.

We denote by $\mathbf{s}_{-i}$ the _partial strategy profile_ consisting of
the strategies of the $n-1$ players other than $i$. That is, from the
perspective of player $i$ using strategy $s_{i}$, the strategy profile
$\mathbf{s}{}$ can be viewed as $(s_{i},\mathbf{s}_{-i})$.

A strategy profile $\mathbf{s}{}^{*}$ is a pure Nash equilibrium if no player
can strictly increase their payoff by unilaterally changing their strategy
choice. Formally, $\mathbf{s}^{*}$ is a Nash equilibrium, if for every player
$i$ and every $s_{i}\neq s^{*}_{i}$ it holds that
$p_{i}(s^{*}_{i},\mathbf{s}_{-i}^{*})\geq p_{i}(s_{i},\mathbf{s}_{-i}^{*})$.

###  2.1 Classes of polymatrix games

We are focused on two classes of binary-action polymatrix games that capture
coordination problems.

#### Pure coordination games.

In a pure-coordination polymatrix game, the payoff of a player increases with
the number of neighbors who choose the same action as them. Formally, a
binary-action polymatrix game is pure-coordination if for every edge $ij\in
E(G)$ the strategy profiles $(\textsf{one},\textsf{one})$ and
$(\textsf{two},\textsf{two})$ are Nash equilibria for the two-player game
$(\Pi^{ij},\Pi^{ji})$. Observe that every game in this class possesses at
least two “trivial” Nash equilibria wherein all players choose the same
action.

#### Anti-coordination games.

In an anti-coordination polymatrix game, each player’s payoff increases with
the number of neighbors who choose a different action. Formally, a binary-
action polymatrix game is anti-coordination if for every edge $ij\in E$ the
strategy profiles $(\textsf{one},\textsf{two})$ and
$(\textsf{two},\textsf{one})$ are Nash equilibria for the two-player game
$(\Pi^{ij},\Pi^{ji})$.

#### Potential games.

A strategic game is a potential game Shapley and Monderer (1996) if the
incentive of all players to change their strategy can be expressed using a
single function called the potential function. Potential games possess many
desirable properties: pure strategy equilibria correspond to local optima of
the potential function so the existence of a pure strategy equilibrium is
assured. Formally, a game is a potential game if there exists a function
$\Phi:S\to\mathbb{R}$ such that for every player $i$, for all
$\mathbf{s}_{-i}$, and all pairs of actions
$s_{i}^{\prime},s_{i}^{\prime\prime}\in S$

$\Phi(s_{i}^{\prime},\mathbf{s}_{-i})-\Phi(s_{i}^{\prime\prime},\mathbf{s}_{-i})=p_{i}(s_{i}^{\prime},\mathbf{s}_{-i})-p_{i}(s_{i}^{\prime\prime},\mathbf{s}_{-i}).$

We emphasize that the same function $\Phi$ captures the change in payoff
associated with a deviation for every player.

#### Pairwise-potential polymatrix games.

When every pairwise interaction, i.e., two-player game, of a polymatrix game
is a potential game, then the polymatrix game inherits this property. In fact,
the potential at any strategy profile is equal to the sum of the potentials
along every edge of the graph $G$. In other words, if $\Phi^{uv}$ denotes the
pairwise-potential function for the two-player game played between $u$ and
$v$, then the function $\Phi(\mathbf{s}):=\sum_{uv}\Phi^{uv}(\mathbf{s})$ is a
potential function for the polymatrix game.

##  3 MaximumWeightedDigraphPartition

In this section we introduce the MaximumWeightedDigraphPartition problem
(MWDP), and we provide a dichotomy for its complexity. We then show how
Objectives (i) and (ii) in binary-action polymatrix games are special cases of
MWDP, and as such complexity dichotomies can be given for each of these issues
in relation to polymatrix games.

####  $\textsc{MaximumWeightedDigraphPartition}(\mathcal{F})$.

Given a family $\mathcal{F}$ of $2\times 2$ matrices, an instance of
$\textsc{MWDP}(\mathcal{F})$ is given by a tuple $(D,c,f)$, where:

  * •

$D$ is an oriented graph on $n$ vertices (that is, a directed graph without
any $2$-cycle);

  * •

$c:A(D)\rightarrow\mathbb{R}^{+}$ assigns positive weights to arcs;

  * •

$f:A(D)\rightarrow\mathcal{F}$, is an assignment of a matrix from the family
of matrices $\mathcal{F}$ to each arc in $D$.

Given a partition, $P=(X_{1},X_{2})$ of $V(D)$, the weight of an arc $uv\in
A(D)$ is defined as follows, where $M=f(uv)$ is the matrix in $\mathcal{F}$
assigned to the arc $uv$.

$w^{P}(uv)=\left\\{\begin{array}[]{rcl}c(uv)\cdot m_{11}&\mbox{if}&u,v\in
X_{1}\\\ c(uv)\cdot m_{22}&\mbox{if}&u,v\in X_{2}\\\ c(uv)\cdot
m_{12}&\mbox{if}&u\in X_{1}\mbox{ and }v\in X_{2}\\\ c(uv)\cdot
m_{21}&\mbox{if}&u\in X_{2}\mbox{ and }v\in X_{1}\\\ \end{array}\right.$

Given a partition $P$, the weight of $D$, denoted by $w^{P}(D)$, is defined as
the sum of the weights on every arc $uv$. That is, $w^{P}(D)=\sum_{a\in
A(D)}w^{P}(a)$. The goal is to find a partition $P$ that maximizes $w^{P}(D)$.

We would like to highlight that the orientation of an arc in an instance of
$\textsc{MWDP}(\mathcal{F})$ is required to determine which vertex defines the
row and which vertex defines the column of the assigned matrix.

###  3.1 A dichotomy for the complexity of $\textsc{MWDP}(\mathcal{F})$

Our main result shows that the tractability of solving
MaximumWeightedDigraphPartition depends on properties of the matrices in the
family of matrices $\mathcal{F}$. We now introduce three properties that a
matrix $M\in\mathcal{F}$ may satisfy.

  * •

Property (a): $m_{11}+m_{22}\geq m_{12}+m_{21}$.

  * •

Property (b): $m_{11}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$.

  * •

Property (c): $m_{22}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$.

Using the three properties above, we present a dichotomy for the complexity of
$\textsc{MWDP}(\mathcal{F})$ with respect to $\mathcal{F}$.

######  Theorem 2.

An instance $(D,c,f)$ of $\textsc{MWDP}(\mathcal{F})$ can be solved in
polynomial time if one of the following holds.

  1. 1.

All matrices in $\mathcal{F}$ satisfy Property (a).

  2. 2.

All matrices in $\mathcal{F}$ satisfy Property (b).

  3. 3.

All matrices in $\mathcal{F}$ satisfy Property (c).

In every other case, $\textsc{MWDP}(\mathcal{F})$ is NP-hard.

Theorem 2 decomposes the space into four cases, each of varying difficulty.
Cases 2 and 3 are immediate, since they admit trivially-optimal solutions: in
Case 2 all vertices belong to $X_{1}$ and in Case 3 all vertices belong to
$X_{2}$. On the other hand, Case 1 is far from trivial and it requires a more
sophisticated argument that creates an equivalent min-cut instance on an
undirected graph (see Lemma 3), which is known to be solvable polynomial-time
Korte and Vygen (2011). Finally, the last case deals with “every other case”
and shows that the problem becomes intractable. The proof involves a series of
intricate subcases and constructions.111Due to space constraints, the formal
proof appears in the Supplementary material, alongside other missing proofs.

######  Lemma 3.

If all matrices in $\mathcal{F}$ satisfy Property (a), then
$\textsc{MWDP}(\mathcal{F})$ can be solved in polynomial time.

###### Proof.

Let $(D,c,f)$ be an instance of $\textsc{MWDP}(\mathcal{F})$ that satisfies
the constraints above. We will construct a new edge-weighted, undirected,
graph $H$ with vertex set $V(D)\cup\\{s,t\\}$ as follows. Let $UG(D)$ denote
the undirected graph obtained from $D$ by removing orientations of all arcs.
Initially, let $E(H)=E(UG(D))\cup\\{su,tu\;|\;u\in V(D)\\}$ and let all edges
in $H$ have weight zero. For each arc $uv\in A(D)$ we modify the edge-weight
function $w$ of $H$ as follows, where $M=f(uv)$ is the matrix associated with
the arc $uv$.

  * •

Let $w(uv)=c(uv)\cdot(m_{11}+m_{22}-m_{12}-m_{21})/2$. Note $w(uv)$ is the
weight of the undirected edge $uv$ in $H$ associated with the arc $uv\in A(D)$
and that this weight is non-negative; this is guaranteed by Property (a) and
it is crucial for the correctness of the lemma.

  * •

Add $c(uv)\cdot(-m_{22})/2$ to $w(su)$.

  * •

Add $c(uv)\cdot(-m_{22})/2$ to $w(sv)$.

  * •

Add $c(uv)\cdot(m_{21}-m_{11}-m_{12})/2$ to $w(tu)$.

  * •

Add $c(uv)\cdot(m_{12}-m_{11}-m_{21})/2$ to $w(tv)$.

Let $\theta$ be the smallest possible weight of all edges in $H$ after we
completed the above process ($\theta$ may be negative). Now consider the
weight function $w^{*}$ obtained from $w$ by subtracting $\theta$ from all
edges incident with $s$ or $t$. That is, $w^{*}(uv)=w(uv)$ if
$\\{u,v\\}\cap\\{s,t\\}=\emptyset$ and $w^{*}(uv)=w(uv)-\theta$ otherwise.
Note that all $w^{*}$-weights in $H$ are non-negative. We will show that for
any $(s,t)$-cut, $(X_{1},X_{2})$ in $H$, i.e., $(X_{1},X_{2})$ partitions
$V(H)$ and $s\in X_{1}$ and $t\in X_{2}$, the $w^{*}$-weight of the cut is
equal to $-w^{P}(D)-|V(D)|\cdot\theta$, where $P$ is the partition
$(X_{1}\setminus\\{s\\},X_{2}\setminus\\{t\\})$ in $D$. Therefore, a minimum-
weight cut in $H$ maximizes $w^{P}(D)$ in $D$.

Let $(X_{1},X_{2})$ be any $(s,t)$-cut in $H$. For every $u\in V(D)$ we note
that exactly one of the edges $su$ and $ut$ will belong to the cut. Therefore,
we note that the $w^{*}$-weight of the cut is $|V(D)|\cdot\theta$ less than
the $w$-weight of the cut. It therefore suffices to show that the $w$-weight
of the cut is $-w^{P}(D)$ (where $P$ is the partition
$(X_{1}\setminus\\{s\\},X_{2}\setminus\\{t\\})$ of $V(D)$).

Let $(X_{1},X_{2})$ be some $(s,t)$-cut. There are four possibilities for any
$uv\in A(D)$, which follow from the definition of the $w$-weights.

  * •

$u,v\in X_{1}$. In this case, we have added $-c(uv)\cdot m_{11}$ to the
$w$-weight of the $(s,t)$-cut.

  * •

$u,v\in X_{2}$. In this case, we have added $-c(uv)\cdot m_{22}$ to the
$w$-weight of the $(s,t)$-cut.

  * •

$u\in X_{1}$ and $v\in X_{2}$. In this case, we have added $-c(uv)\cdot
m_{12}$ to the $w$-weight of the $(s,t)$-cut.

  * •

$v\in X_{1}$ and $u\in X_{2}$. In this case, we have added $-c(uv)\cdot
m_{21}$ to the $w$-weight of the $(s,t)$-cut.

Therefore we note that in all cases we have added $-w^{P}(uv)$ to the
$w$-weight of the $(s,t)$-cut, $(X_{1},X_{2})$. So the total $w$-weight of the
$(s,t)$-cut is $-w^{P}(D)$ as desired.

Analogously, if we have a partition $P=(X_{1},X_{2})$ of $V(D)$, then adding
$s$ to $X_{1}$ and $t$ to $X_{2}$ we obtain a $(s,t)$-cut with $w$-weight
$-w^{P}(D)$ of $H$. As we can find a minimum $w^{*}$-weight cut in $H$ in
polynomial time Korte and Vygen (2011) we can find a partition
$P=(X_{1},X_{2})$ of $V(D)$ with minimum value of $-w^{P}(D)$, which
corresponds to the maximum value of $w^{P}(D)$. Therefore,
$\textsc{MWDP}(\mathcal{F})$ can be solved in polynomial time in this case. ∎

##  4 Social Welfare and Potential Maximization

In this section we show how we can utilize Theorem 2 and derive as corollaries
several results, both positive and negative, for various classes of binary-
action polymatrix games. First, we present a simple reduction from general
binary-action polymatrix games to MWDP that is used to solve Objective (i),
i.e., maximize the social welfare.

####  Social Welfare via MWDP.

Given a polymatrix game with underlying graph $G$, we create an instance of
MWDP as follows.

  * •

$D$ has the same vertex-set as $G$. In addition, for every edge of $G$ we add
a directed edge in $D$ with arbitrary orientation. An edge from $u$ to $v$
specifies that player $u$ chooses a row and player $v$ chooses a column in the
two-player game played between the two corresponding players.

  * •

$c(uv)=1$ for every oriented edge $uv\in A(D)$.

  * •

For each two-player game $(\Pi^{uv},\Pi^{vu})$, with $uv\in E(G)$, we create
the welfare-matrix $W^{uv}:=\Pi^{uv}+\Pi^{vu}$, and we associate it with the
oriented edge between $u$ and $v$ as follows:

    * –

$f(uv)=W^{uv}$, if we have added the arc $uv$;

    * –

$f(uv)=(W^{uv})^{T}$, if we have added the arc $vu$.

The reduction above induces an immediate translation between strategy profiles
and partitions. Player $v$ chooses action one if and only if the corresponding
vertex $v$ in $D$ belongs to $X_{1}$. Conversely, player $v$ chooses action
two if and only if the corresponding vertex $v$ in $D$ belongs to $X_{2}$.

For any strategy profile $\mathbf{s}$, we use $P(\mathbf{s})$ to denote the
corresponding partition. The following lemma trivially follows from the
reduction above.

######  Lemma 4.

For every possible strategy profile $\mathbf{s}$, it holds that
$\mathcal{W}(\mathbf{s})=w^{P(\mathbf{s})}(D)$.

So, the combination of Lemma 4 and Theorem 2, yields a series of results. The
first one, is a clean complexity dichotomy for maximizing social welfare in
general binary-action polymatrix games. To the best of our knowledge, this is
the first dichotomy of this kind.

######  Theorem 5.

Consider a binary-action polymatrix game on input graph $G$. Let
$W^{uv}=\Pi^{uv}+\Pi^{vu}$ for every $uv\in E(G)$. Finding a strategy profile
that maximizes the social welfare can be solved in polynomial time if one of
the following holds.

  * •

$w^{uv}_{11}+w^{uv}_{22}\geq w^{uv}_{12}+w^{uv}_{21}$ for every $uv\in E(G)$.

  * •

$w^{uv}_{11}\geq\max\\{w^{uv}_{12},w^{uv}_{21},w^{uv}_{22}\\}$ for every
$uv\in E(G)$.

  * •

$w^{uv}_{22}\geq\max\\{w^{uv}_{11},w^{uv}_{12},w^{uv}_{21}\\}$ for every
$uv\in E(G)$.

In every other case, the problem is NP-hard.

The reduction from welfare maximization to MWDP is immediate. The reduction in
the opposite direction can be seen as follows. Consider an arc $uv$ of weight
$c$ with matrix $M$. For entry $m_{ij}$ in $M$, let $\frac{c\cdot m_{ij}}{2}$
be the payoff to each player when player $u$ chooses strategy $i$ and player
$v$ chooses $j$. Clearly the total welfare is given by $c\cdot m_{ij}$. The
proof now follows by appealing to Theorem 2.

Theorem 5 implies two immediate corollaries for coordination polymatrix games.
Firstly, for every welfare-matrix $W^{uv}$ of a pure-coordination game it
holds that $w^{uv}_{11}+w^{uv}_{22}\geq w^{uv}_{12}+w^{uv}_{21}$. Second, it
is not difficult to construct anti-coordination games where
$w^{uv}_{11}+w^{uv}_{22}<w^{uv}_{12}+w^{uv}_{21}$.222The construction of
Appendix C.2 from Cai and Daskalakis Cai and Daskalakis (2011) creates these
types of welfare matrices.

######  Corollary 6.

Maximizing social welfare in binary-action pure-coordination polymatrix games
can be done in polynomial time.

######  Corollary 7.

It is NP-hard to maximize social welfare in binary-action anti-coordination
polymatrix games.

#### Pairwise-Potential Games via MWDP.

Next we show how to reduce the problem of maximizing the potential in
pairwise-potential binary-action polymatrix games to the MWDP problem. Observe
that for this class of games, every pairwise-potential $\Phi^{uv}$ can be
written as a $2\times 2$ potential-matrix, so
$\Phi^{uv}:=\left[\begin{array}[]{cc}\phi^{uv}_{11}&\phi^{uv}_{12}\\\
\phi^{uv}_{21}&\phi^{uv}_{22}\\\ \end{array}\right]$. To create an instance of
MWDP we will follow a similar approach as before. This time though, we use
potential-matrices: $\Phi^{uv}$ will be associated with the oriented edge
between $u$ and $v$ as follows.

  * •

$f(uv)=\Phi^{uv}$, if we have added the arc $uv$;

  * •

$f(uv)=(\Phi^{uv})^{T}$, if we have added the arc $vu$.

To reduce from MWDP to potential maximization, let the matrix $M$ on arc $uv$
with weight $c$ be given by the potential matrix above. Such a matrix is the
potential of a $2\times 2$ game given by
$\left[\begin{array}[]{cc}\frac{\phi_{11}}{2},\frac{\phi_{11}}{2}&0,\phi_{12}-\frac{\phi_{11}}{2}\\\
\phi_{21}-\frac{\phi_{11}}{2},0&\phi_{22}-\phi_{21},\phi_{22}-\phi_{12}\\\
\end{array}\right]$. As before, we have reduced in both directions and so we
have a one-to-one translation between partitions and strategy profiles. So, if
we denote $P(\mathbf{s})$ the partition associated with strategy profile
$\mathbf{s}$ we get the following lemma, where $\Phi(\mathbf{s})$ is the sum
of the pairwise potentials.

######  Lemma 8.

For every possible strategy profile $\mathbf{s}$ of a pairwise-potential
polymatrix game, it holds that $\Phi(\mathbf{s})=w^{P(\mathbf{s})}(D)$.

Lemma 8 combined with Theorem 2, yield the following theorem. Again, to the
best of our knowledge, this is the first dichotomy of this kind.

######  Theorem 9.

Consider a binary-action potential polymatrix game on input graph $G$ with
pairwise-potential matrices $\Phi^{uv}$, for every $uv\in E(G)$. Finding a
strategy profile that maximizes the potential function $\Phi$ can be solved in
polynomial time if one of the following holds.

  * •

$\phi^{uv}_{11}+\phi^{uv}_{22}\geq\phi^{uv}_{12}+\phi^{uv}_{21}$ for every
$uv\in E(G)$.

  * •

$\phi^{uv}_{11}\geq\max\\{\phi^{uv}_{12},\phi^{uv}_{21},\phi^{uv}_{22}\\}$ for
every $uv\in E(G)$.

  * •

$\phi^{uv}_{22}\geq\max\\{\phi^{uv}_{11},\phi^{uv}_{12},\phi^{uv}_{21}\\}$ for
every $uv\in E(G)$.

In every other case, the problem is NP-hard.

Theorem 9 reveals another difference between pure-coordination and anti-
coordination polymatrix games, when both are pairwise-potential games. While
for the latter class of games it is NP-hard to maximize the potential function
(this was implied in Cai and Daskalakis Cai and Daskalakis (2011)), for the
former class of games the problem can be solved in polynomial time.

######  Corollary 10.

Maximizing the potential of a pairwise-potential binary-action pure-
coordination polymatrix game can be solved in polynomial time.

###### Proof.

We will show that when the game is pure-coordination, for every $uv\in E(G)$
the potential-matrix $\Phi^{uv}$ satisfies that
$\phi^{uv}_{11}+\phi^{uv}_{22}\geq\phi^{uv}_{12}+\phi^{uv}_{21}$. Recall,
since the game is pure-coordination the following hold.

  * •

Outcome $(\textsf{one},\textsf{one})$, that corresponds to $\phi^{uv}_{11}$ of
the potential-matrix, is a Nash equilibrium for the two-player game played on
$uv$. So, since this is a Nash equilibrium and the two-player game is
potential, any deviation from $(\textsf{one},\textsf{one})$ will lower the
payoffs of both players, and thus it will lower the value of the pairwise-
potential. Therefore,
$\phi^{uv}_{11}\geq\max\\{\phi^{uv}_{12},\phi^{uv}_{21}\\}$.

  * •

Outcome $(\textsf{two},\textsf{two})$, that corresponds to $\phi^{uv}_{22}$ of
the potential-matrix, is a Nash equilibrium for the two-player game played on
$uv$. Using verbatim the arguments as before, it follows that
$\phi^{uv}_{22}\geq\max\\{\phi^{uv}_{12},\phi^{uv}_{21}\\}$.

Our claim follows by combining the two bullets above. ∎

##  5 Welfare-optimal Nash equilibria

In this section we focus on the computation of welfare-optimal Nash equilibria
in binary-action polymatrix games. We focus only on pure-coordination games
since the result of Cai and Daskalakis (2011) already implies that in anti-
coordination games, welfare-optimal Nash equilibria are NP-hard to compute. On
the other hand, our results indicate that pure-coordination games are
considerably more well-behaved, since they admit polynomial-time algorithms
for welfare and potential maximization. Unfortunately, as we prove, when it
comes to computing a “best” Nash equilibrium, things become almost immediately
intractable even for the arguably simplest class of pure-coordination games,
which we term 2-type threshold-games, which is a special case of anonymous
games.

#### Anonymous pure-coordination games.

In an anonymous game Blonski (1999), the payoff of a player does not depend on
the identity of their opponents, but only from the number of players that
choose a specific action. In an anonymous polymatrix game on graph $G$ every
player $u\in V(G)$ is associated with a single payoff matrix $\Pi^{u}$ that is
used in every two-player game they participate, i.e., player $u$ participates
in the games $(\Pi^{u},\Pi^{v})$, for every $v\in E(G)$. We say that an
anonymous polymatrix game has $k$ types of players if there exists a set of
payoff matrices $\mathcal{A}$ of size $k$ and $\Pi^{u}\in\mathcal{A}$ for
every $u\in V(G)$. Finally, a pure-coordination game is $k$-type anonymous, if
it satisfies the conditions above.

Next we focus on a special class of binary-action pure-coordination anonymous
games, termed threshold games Neary and Newton (2017); their name follows from
the fact that they model game-theoretically the classic threshold model of
Granovetter Granovetter (1978), wherein it is optimal for each player to
choose each action once the fraction of their neighbors choosing that action
exceeds a specific threshold.

#### Threshold games.

A threshold-game is a binary-action anonymous pure-coordination polymatrix
game, where every player $u$ is associated with a parameter
$\gamma_{u}\in[0,1]$ and their payoff-matrix is
$\Pi^{u}:=\left[\begin{array}[]{cc}\gamma_{u}&0\\\ 0&1-\gamma_{u}\\\
\end{array}\right]$.

Clearly, finding optimal outcomes in a 1-type threshold-game (i.e., one
wherein $\gamma_{u}$ is the same for all players $u$) is trivial. However, as
we now show, the problem becomes interesting when a second type is introduced.
Specifically, we use the Language Game Neary (2012), in which the population
is partitioned into two types, $A$ and $B$, such that all players of type $A$
have threshold $\gamma_{A}$ and all players in Group $B$ have threshold
$\gamma_{B}$, with $0\leq\gamma_{B}\leq\gamma_{A}\leq 1$. When
$\gamma_{B}\leq\frac{1}{2}\leq\gamma_{A}$ a tension emerges: type-$A$ players
prefer that everyone coordinates on action one while type-$B$ players prefer
the opposite. Even for this simple two-type threshold model, the following
shows that most cases are intractable.

######  Theorem 11.

The complexity of finding a welfare-maximizing Nash equilibrium in a
threshold-game with two thresholds, $\gamma_{A},\gamma_{B}$, such that
$0\leq\gamma_{B}\leq\gamma_{A}\leq 1$, is as follows.

1.

If $\gamma_{A}\leq 1/2$ the problem is polynomial time.

2.

If $\gamma_{B}\geq 1/2$ the problem is polynomial time.

3.

If $\gamma_{B}=0$ and $\gamma_{A}=1$ the problem is polynomial time.

4.

In all other cases the problem is NP-hard.

###### Proof sketch.

Cases 1-2. If $\gamma_{A}\leq 1/2$, or $\gamma_{B}\geq 1/2$, then all players
prefer the same action and selecting that action for each player gives a
maximum-welfare Nash equilibrium.

Case 3. Now, let $\gamma_{A}=1$ and let $\gamma_{B}=0$ and $G$ be a graph and
let $(A,B)$ be a partition of $V(G)$, so that if $u\in
Y\Leftrightarrow\gamma_{u}=\gamma_{Y}$, where $Y\in\\{A,B\\}$. We want to find
a Nash equilibrium, $(X_{\textsf{one}},X_{\textsf{two}})$, of maximum welfare,
where $X_{i}$ denotes the set of players that choose action
$i\in\\{\textsf{one},\textsf{two}\\}$.

Let $(X_{\textsf{one}},X_{\textsf{two}})$ be a Nash equilibrium of $G$. This
implies that all vertices in $X_{\textsf{two}}\cap A$ only have edges to
vertices in $X_{\textsf{two}}$ (as otherwise it is not a Nash equilibrium).
Note that this means that any connected component $C$ in $G[A]$ is either
subset of $X_{\textsf{one}}$ or a subset of $X_{\textsf{two}}$, else one can
find an edge from a vertex in $X_{\textsf{two}}\cap A$ to a vertex in
$X_{\textsf{one}}$. Analogously, every connected component of $G[B]$ is either
a subset of $X_{\textsf{one}}$ or a subset of $X_{\textsf{two}}$. Finally,
given a connected component $C_{A}$ of $G[A]$ and a connected component
$C_{B}$ of $G[B]$, if there is an edge in $G$ between a vertex $u\in C_{A}$
and a vertex $v\in C_{B}$, then it is not possible that $C_{B}\subseteq
X_{\textsf{one}}$ and $C_{A}\subseteq X_{\textsf{two}}$.

We can view the value of social welfare in a Nash equilibrium in term of the
loss w.r.t. the sum of maximum achievable utility of each player which is in
this case the sum of degrees of vertices in $G$ or $2|E(G)|$. The equilibrium
that maximizes the social welfare then minimizes this loss. We now build an
auxiliary digraph $D$ whose vertices are the components of $G[A]$, the
components of $G[B]$ and two new vertices $s$ and $t$. There is an arc from
$s$ to every component in $G[A]$, an arc from every component in $G[B]$ to
$t$, and two opposite arcs between every connected component $C_{A}$ of $G[A]$
and every connected component $C_{B}$ of $G[B]$ such there is an edge in $G$
between a vertex $u\in C_{A}$ and a vertex $v\in C_{B}$. The goal is to set up
the weights of the arcs such that there is a one-to-one correspondence between
minimal $s$-$t$ cuts in $D$ and Nash equilibria in $G$ given by: (i) every
player in the “$s$ side” of the cut chooses action one and (ii) every player
in the “$t$ side” chooses action two. Moreover, the weight of the cut should
be exactly the loss w.r.t. $2|E(G)|$. It is rather straightforward to verify
that setting the weights as follows achieves this: every arc from $s$ to a
component $C_{A}$ of $G[A]$ has weight sum of degrees of vertices in $C_{A}$;
every arc from a component $C_{B}$ of $G[B]$ to $t$ has weight sum of degrees
of vertices in $C_{B}$; every arc from a component $C_{A}$ of $G[A]$ to a
component $C_{B}$ of $G[B]$ has weight two times the number of edges between
$C_{A}$ and $C_{B}$; every arc from a component $C_{B}$ of $G[B]$ to a
component $C_{A}$ of $G[A]$ has weight infinity (as players in $C_{B}$ cannot
use strategy one if players in $C_{A}$ use strategy two). To find a welfare-
maximizing Nash equilibrium, it now suffices to find a minimum weight $s$-$t$
cut in $D$ that can be done in polynomial time Korte and Vygen (2011).

Case 4. First note that if $\gamma_{B}=0$, then $1/2<\gamma_{A}<1$, and we can
exchange the role of $A$ and $B$ and that of the strategy one and strategy
two. Hence, it suffices to prove the statement for
$0<\gamma_{B}<1/2<\gamma_{A}\leq 1$.

We will show the NP-hardness result via a reduction from Minimum Traversal
problem in $3$-uniform hypergraphs333The problem is also called $3$-Hitting
Set., which is known to be NP-hard Garey and Johnson (1979). A $3$-uniform
hypergraph $H$ has a set of vertices $V(H)$ and a set of hyperedges $E(H)$,
where every hyperedge $e\in E(H)$ is a subset of vertices of size exactly $3$.
A traversal of $H$ is a set of vertices $X$ such that $X\cap e\neq\emptyset$
for every edge $e\in E(H)$. Minimum Traversal problem asks to find a traversal
of the minimum size.

Let $H$ be a $3$-uniform hypergraph. We will create a graph, $G$, and a
partition $(A,B)$ of $V(G)$ such that a solution to our problem for $G$ will
give us a minimum traversal in $H$. We also refer the reader to Figure 3 for
an illustration.

$C_{A}$$C_{B}$$r_{e_{1}}$$r_{e_{2}}$$r_{e_{3}}$$\cdots$$r_{e_{m}}$$u_{1}^{\prime}$$u_{2}^{\prime}$$u_{3}^{\prime}$$u_{4}^{\prime}$$\cdots$$u_{n}^{\prime}$$Z_{u_{1}^{\prime}}$$Z_{u_{2}^{\prime}}$$Z_{u_{3}^{\prime}}$$Z_{u_{4}^{\prime}}$$Z_{u_{n}^{\prime}}$
Figure 2: The construction of Case 4 in Theorem 11. The graph $G$ when $H$ is
a $3$-uniform hypergraph with $m$ edges, including the edges
$e_{1}=\\{u_{1},u_{2},u_{3}\\}$ and $e_{2}=\\{u_{1},u_{3},u_{4}\\}$. The
square vertices in $C_{A}$ denotes A-vertices and round vertices (everywhere
else) denote B-vertices.

For the reduction, we will need to fix some sizes that depend of $\gamma_{A}$,
$\gamma_{B}$, $|V(H)|$, and $|E(H)|$. We postpone the selection of the sizes
to the appendix, where we give exact proofs of the statements below. The graph
$G$ consists of:

  * •

Cliques $C_{A}$, $C_{B}$ that are “sufficiently large”; the sizes are selected
in a way such that in any welfare-optimal Nash equilibrium, players in $C_{A}$
choose action one and in $C_{B}$ choose action two. $A$ contains precisely the
players in $C_{A}$, all the remaining players are in $B$.

  * •

Vertex sets $R=\bigcup_{e\in E(H)}\\{r_{e}\\}$, $V^{\prime}=\bigcup_{u\in
V(H)}\\{u^{\prime}\\}$. There is an edge between $r_{e}$ and $u^{\prime}$ iff
$u\in e$. Moreover, there are $c_{A}$ edges from every $r_{e}$ to $C_{A}$ and
$c_{B}$ edges from every $r_{e}$ to $C_{B}$. $c_{A}$ and $c_{B}$ are selected
so that if every player in $C_{A}$ uses one and in $C_{B}$ two, then $r_{e}$
(recall that $r_{e}\in B$) prefers one if at least one of its exactly three
neighbors in $V^{\prime}$ chooses one.

  * •

For every $u\in V(H)$, vertex set $Z_{u}$ of size $z$ that is to be fixed.
There is an edge from every vertex $z\in Z_{u}$ to the vertex $u^{\prime}\in
V^{\prime}$. Hence, in any Nash equilibrium $z$ chooses the same strategy as
$u^{\prime}$. This also allows $u^{\prime}$ the freedom of choosing one even
though $u^{\prime}\in B$.

By a clever selection of the sizes, we can achieve that if $\mathbf{s}$ is a
welfare-maximizing Nash equilibrium that partitions players into
$(X_{\textsf{one}},X_{\textsf{two}})$ by the strategy they are using, then:

  1. 1.

$V(C_{A})\cup R\subseteq X_{\textsf{one}}$, $V(C_{B})\subseteq
X_{\textsf{two}}$. Intuitively, this is because the choice of $c_{A}$ and
$c_{B}$ guarantees that the loss of utility for the players in $C_{A}$ when a
player $r_{e}\in R$ selects two, is larger than the gain players in
$V(G)\setminus V(C_{A})$ can get from this selection.

  2. 2.

For every $e\in E(H)$, $r_{e}$ has a neighbor in $V^{\prime}\cap
X_{\textsf{one}}$;

Note that the second condition states that $V^{\prime}\cap X_{\textsf{one}}$
is a traversal of $H$. We now observe that because
$V^{\prime}\cup\bigcup_{u\in V(H)}Z_{u}\subseteq B$, there is a significant
gain in overall welfare if we decrease the number of players in $V^{\prime}$
that choose action one, as long as we preserve the above two conditions.
Therefore, a welfare-maximizing Nash equilibrium not only gives a traversal,
but a minimum traversal in $H$. ∎

##  6 Discussion

Our paper provides several novel dichotomy results for the complexity of
economically-efficient outcomes in general binary-action polymatrix games,
coordination games, potential games, and threshold games.

Our main tool for deriving the majority of these results is the dichotomy for
MWDP, a novel graph-theoretic problem, which we strongly believe will find
applications in other domains too. To this end, we have already identified
several problems arising from graph theory whose complexity can easily be
determined by our dichotomy for MWDP. Our list includes both well-known
problems ((Directed) Max Cut, (Directed) Min $(s,t)$-cut, Max Density
Subgraph) and new ones that we describe in the supplementary material.

#### Acknowledgements.

Anders Yeo’s research was supported by the Danish research council for
independent research under grant number DFF 7014-00037B.

## References

  * Aloisio et al. [2021] Alessandro Aloisio, Michele Flammini, Bojana Kodric, and Cosimo Vinci.  Distance polymatrix coordination games.  In IJCAI, pages 3–9, 2021.
  * Apt et al. [2017] Krzysztof R Apt, Bart de Keijzer, Mona Rahn, Guido Schäfer, and Sunil Simon.  Coordination games on graphs.  International Journal of Game Theory, 46(3):851–877, 2017.
  * Apt et al. [2022] Krzysztof R Apt, Sunil Simon, and Dominik Wojtczak.  Coordination games on weighted directed graphs.  Mathematics of Operations Research, 47(2):995–1025, 2022.
  * Armstrong and Vickers [2001] Mark Armstrong and John Vickers.  Competitive price discrimination.  The RAND Journal of Economics, 32(4):579–605, 2001.
  * Arthur [1989] W Brian Arthur.  Competing technologies, increasing returns, and lock-in by historical events.  Economic Journal, 99(394):116–131, March 1989.
  * Bang-Jensen and Gutin [2009] Jørgen Bang-Jensen and Gregory Z. Gutin.  Digraphs - Theory, Algorithms and Applications, Second Edition.  Springer Monographs in Mathematics. Springer, 2009.
  * Barman et al. [2015] Siddharth Barman, Katrina Ligett, and Georgios Piliouras.  Approximating nash equilibria in tree polymatrix games.  In SAGT, pages 285–296, 2015.
  * Blonski [1999] Matthias Blonski.  Anonymous games with binary actions.  Games and Economic Behavior, 28(2):171–180, 1999.
  * Blume [1993] Lawrence E. Blume.  The statistical mechanics of strategic interaction.  Games and Economic Behavior, 5(3):387 – 424, 1993.
  * Bogomolnaia and Jackson [2002] Anna Bogomolnaia and Matthew O Jackson.  The stability of hedonic coalition structures.  Games and Economic Behavior, 38(2):201–230, 2002.
  * Boodaghians et al. [2020] Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta.  Smoothed efficient algorithms and reductions for network coordination games.  In ITCS, volume 151, pages 73:1–73:15, 2020.
  * Bramoullé and Kranton [2007] Yann Bramoullé and Rachel Kranton.  Public goods in networks.  Journal of Economic Theory, 135(1):478–494, 2007.
  * Bramoullé [2007] Yann Bramoullé.  Anti-coordination and social interactions.  Games and Economic Behavior, 58(1):30–49, 2007.
  * Cai and Daskalakis [2011] Yang Cai and Constantinos Daskalakis.  On minmax theorems for multiplayer games.  In Proc. of SODA, pages 217–234, 2011.
  * Chen et al. [2009] Xi Chen, Xiaotie Deng, and Shang-Hua Teng.  Settling the complexity of computing two-player Nash equilibria.  Journal of the ACM, 56(3):14:1–14:57, 2009.
  * Cooper and John [1988] Russell Cooper and Andrew John.  Coordinating Coordination Failures in Keynesian Models*.  The Quarterly Journal of Economics, 103(3):441–463, 08 1988.
  * Daskalakis et al. [2009] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou.  The complexity of computing a Nash equilibrium.  SIAM J. Comput., 39(1):195–259, 2009.
  * Deligkas et al. [2016] Argyrios Deligkas, John Fearnley, Tobenna Peter Igwe, and Rahul Savani.  An empirical study on computing equilibria in polymatrix games.  In Proc. of AAMAS, pages 186–195, 2016.
  * Deligkas et al. [2017] Argyrios Deligkas, John Fearnley, and Rahul Savani.  Computing constrained approximate equilibria in polymatrix games.  In Proc. of SAGT, volume 10504, pages 93–105, 2017.
  * Deligkas et al. [2020] Argyrios Deligkas, John Fearnley, and Rahul Savani.  Tree polymatrix games are ppad-hard.  In Proc. of ICALP, volume 168, pages 38:1–38:14, 2020.
  * Deligkas et al. [2022] Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos.  Pure-circuit: Strong inapproximability for PPAD.  In Proc. of FOCS, pages 159–170. IEEE, 2022.
  * Diamond and Dybvig [1983] Douglas W. Diamond and Philip H. Dybvig.  Bank runs, deposit insurance, and liquidity.  Journal of Political Economy, 91(3):pp. 401–419, 1983.
  * Eaves [1973] B Curtis Eaves.  Polymatrix games with joint constraints.  SIAM Journal on Applied Mathematics, 24(3):418–423, 1973.
  * Elezi et al. [2018] Ismail Elezi, Alessandro Torcinovich, Sebastiano Vascon, and Marcello Pelillo.  Transductive label augmentation for improved deep network learning.  In Proc. of ICPR, pages 1432–1437, 2018.
  * Elkind et al. [2006] Edith Elkind, Leslie Ann Goldberg, and Paul Goldberg.  Nash equilibria in graphical games on trees revisited.  In Proc. of EC, pages 100–109, 2006.
  * Ellison [1993] Glenn Ellison.  Learning, local interaction, and coordination.  Econometrica, 61(5):1047–1071, 1993.
  * Farrell and Saloner [1985] Joseph Farrell and Garth Saloner.  Standardization, compatibility, and innovation.  RAND Journal of Economics, 16(1):70–83, Spring 1985.
  * Foster and Young [1990] D. Foster and P. Young.  Stochastic evolutionary game dynamics.  Theoretical Population Biology, 38:219–232, 1990.
  * Galeotti et al. [2010] Andrea Galeotti, Sanjeev Goyal, Matthew O. Jackson, Fernando Vega-Redondo, and Leeat Yariv.  Network games.  The Review of Economic Studies, 77(1):218–244, 2010.
  * Garey and Johnson [1979] Michael R Garey and David S Johnson.  Computers and intractability.  A Series of Books in the Mathematical Sciences. Freeman and Co, 1979.
  * Granovetter [1978] Mark Granovetter.  Threshold models of collective behavior.  American Journal of Sociology, 83(6):1420–1443, 1978.
  * Hofbauer and Sorger [1999] Josef Hofbauer and Gerhard Sorger.  Perfect foresight and equilibrium selection in symmetric potential games.  Journal of Economic Theory, 85(1):1–23, 1999.
  * Howson Jr and Rosenthal [1974] Joseph T Howson Jr and Robert W Rosenthal.  Bayesian equilibria of finite two-person games with incomplete information.  Management Science, 21(3):313–315, 1974.
  * Howson Jr [1972] Joseph T Howson Jr.  Equilibria of polymatrix games.  Management Science, 18(5-part-1):312–318, 1972.
  * Janovskaya [1968] E. B. Janovskaya.  Equilibrium points in polymatrix games.  (in Russian), Latvian Mathematical Journal, 1968.
  * Kandori et al. [1993] Michihiro Kandori, George J. Mailath, and Rafael Rob.  Learning, mutation, and long run equilibria in games.  Econometrica, 61(1):29–56, 1993.
  * Katz and Shapiro [1985] Michael L Katz and Carl Shapiro.  Network externalities, competition, and compatibility.  American Economic Review, 75(3):424–440, June 1985.
  * Kearns et al. [2006] Michael Kearns, Siddharth Suri, and Nick Montfort.  An Experimental Study of the Coloring Problem on Human Subject Networks.  Science, 313(5788):824–827, 2006.
  * Korte and Vygen [2011] Bernhard H Korte and Jens Vygen.  Combinatorial optimization, volume 1.  Springer, 2011.
  * Lewis [1969] David K. Lewis.  Convention: A Philosophical Study.  Cambridge, Mass: Harvard University Press, 1969.
  * Lovász [1973] L. Lovász.  Coverings and colorings of hypergraphs.  Proc. 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing, pages 3–12, 1973.
  * McCubbins et al. [2009] Mathew D. McCubbins, Ramamohan Paturi, and Nicholas Weller.  Connected coordination: Network structure and group coordination.  American Politics Research, 37(5):899–920, 2009.
  * Miller and Zucker [1991] Douglas A Miller and Steven W Zucker.  Copositive-plus lemke algorithm solves polymatrix games.  Operations research letters, 10(5):285–290, 1991.
  * Morris [2000] Stephen Morris.  Contagion.  Review of Economic Studies, 67(1):57–78, January 2000.
  * Myatt and Wallace [2009] David P. Myatt and Chris Wallace.  Evolution, teamwork and collective action: Production targets in the private provision of public goods.  The Economic Journal, 119(534):61–90, 2009.
  * Neary and Newton [2017] Philip R Neary and Jonathan Newton.  Heterogeneity in preferences and behavior in threshold models.  The Journal of Mechanism and Institution Design, 2(1):141–159, December 2017.
  * Neary [2012] Philip R. Neary.  Competing conventions.  Games and Economic Behavior, 76(1):301 – 328, 2012.
  * Ortiz and Irfan [2017] Luis Ortiz and Mohammad Irfan.  Tractable algorithms for approximate nash equilibria in generalized graphical games with tree structure.  In Proc. of AAAI, volume 31, 2017.
  * Ostrovsky and Schwarz [2005] Michael Ostrovsky and Michael Schwarz.  Adoption of standards under uncertainty.  The RAND Journal of Economics, 36(4):816–832, 2005.
  * Peski [2010] Marcin Peski.  Generalized risk-dominance and asymmetric dynamics.  Journal of Economic Theory, 145(1):216–248, January 2010.
  * Peski [2021] Marcin Peski.  Fuzzy conventions, 2021.
  * Rahn and Schäfer [2015] Mona Rahn and Guido Schäfer.  Efficient equilibria in polymatrix coordination games.  In Proc. of MFCS, pages 529–541. Springer, 2015.
  * Rosenthal [1973] Robert W. Rosenthal.  A class of games possessing pure-strategy nash equilibria.  International Journal of Game Theory, 2(1):65–67, 1973.
  * Rubinstein [2018] Aviad Rubinstein.  Inapproximability of Nash equilibrium.  SIAM J. Comput., 47(3):917–959, 2018.
  * Schaefer [1978] Thomas J. Schaefer.  The complexity of satisfiability problems.  In Proc. of STOC, pages 216–226. ACM, 1978.
  * Schelling [1978] Thomas C. Schelling.  Micromotives and Macrobehavior.  W. W. Norton, revised edition, September 1978.
  * Shapley and Monderer [1996] Lloyd S. Shapley and Dov Monderer.  Potential games.  Games and Economic Behavior, 14:124–143, 1996.
  * Ui [2001] Takashi Ui.  Robust equilibria of potential games.  Econometrica, 69(5):1373–1380, 2001.
  * Van Huyck et al. [1990] John B Van Huyck, Raymond C Battalio, and Richard O Beil.  Tacit coordination games, strategic uncertainty, and coordination failure.  American Economic Review, 80(1):234–48, March 1990.
  * Vascon et al. [2020] Sebastiano Vascon, Marco Frasca, Rocco Tripodi, Giorgio Valentini, and Marcello Pelillo.  Protein function prediction as a graph-transduction game.  Pattern Recognition Letters, 134:96–105, 2020.
  * Young [1993] H. Peyton Young.  The evolution of conventions.  Econometrica, 61(1):57–84, 1993.
  * Young [2001] H. Peyton Young.  Individual Strategy and Social Structure: An Evolutionary Theory of Institutions.  Princeton, NJ: Princeton University Press, January 2001.

##  Appendix A Proving Lemma 3 and Other Basic Results

Recall that we consider the following general problem called
MaximumWeightedDigraphPartition (MWDP).

MWDP (${\cal F}$):

We are given a family of $2\times 2$ matrices ${\cal F}$. For each matrix
$M\in{\cal F}$ let $m_{11}$, $m_{12}$, $m_{21}$ and $m_{22}$ denote the
entries of $M$, such that

$M=\left[\begin{array}[]{cc}m_{11}&m_{12}\\\ m_{21}&m_{22}\\\
\end{array}\right]$

An instance of MWDP (${\cal F}$) consists of an oriented graph $D$ (that is, a
directed graph without directed $2$-cycles), arc-weights
$c:A(D)\rightarrow\mathbb{R}^{+}$ and an assignment, $f:A(D)\rightarrow{\cal
F}$, of a matrix from ${\cal F}$ to each arc in $D$.

Given a partition, $P=(X_{1},X_{2})$, of $V(D)$ the weight of en arc $uv\in
E(D)$ is defined as follows, where $M=f(uv)$ is the matrix assigned to the arc
$uv$.

$w^{P}(uv)=\left\\{\begin{array}[]{rcl}c(uv)\cdot m_{11}&\mbox{if}&u,v\in
X_{1}\\\ c(uv)\cdot m_{22}&\mbox{if}&u,v\in X_{2}\\\ c(uv)\cdot
m_{12}&\mbox{if}&u\in X_{1}\mbox{ and }v\in X_{2}\\\ c(uv)\cdot
m_{21}&\mbox{if}&u\in X_{2}\mbox{ and }v\in X_{1}\\\ \end{array}\right.$

The weight of $D$, $w^{P}(D)$, is defined as the sum of all the weights of the
arcs. That is, $w^{P}(D)=\sum_{a\in A(D)}w^{P}(a)$. The aim is to find the
partition, $P$, that maximizes $w^{P}(D)$.

Lemma 3 If $m_{11}+m_{22}\geq m_{12}+m_{21}$ for all matrices $M\in{\cal F}$
then MWDP (${\cal F}$) can be solved in polynomial time.

Proof: Let $(D,c,f)$ be an instance of MWDP (${\cal F}$). We will construct a
new (undirected) graph $H$ with vertex set $V(D)\cup\\{s,t\\}$ as follows. Let
$UG(D)$ denote the undirected graph obtained from $D$ by removing orientations
of all arcs. Initially let $E(H)=E(UG(D))\cup\\{su,tu\;|\;u\in V(D)\\}$ and
let all edges in $H$ have weight zero. Now for each arc $uv\in A(D)$ we modify
the weight function $w$ of $H$ as follows, where $M=f(uv)$ is the matrix
associated with the arc $uv$.

  * •

Let $w(uv)=c(uv)\times\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}$. Note $w(uv)$ is
the weight of the undirected edge $uv$ in $H$ associated with the arc $uv$ in
$D$ and that this weight is non-negative.

  * •

Add $c(uv)\times\left(\frac{-m_{22}}{2}\right)$ to $w(su)$.

  * •

Add $c(uv)\times\left(\frac{-m_{22}}{2}\right)$ to $w(sv)$.

  * •

Add $c(uv)\times\frac{m_{21}-m_{11}-m_{12}}{2}$ to $w(tu)$.

  * •

Add $c(uv)\times\frac{m_{12}-m_{11}-m_{21}}{2}$ to $w(tv)$.

Let $\theta$ be the smallest possible weight of all edges in $H$ after we
completed the above process ($\theta$ may be negative). Now consider the
weight function $w^{*}$ obtained from $w$ by subtracting $\theta$ from all
edges incident with $s$ or $t$. That is, $w^{*}(uv)=w(uv)$ if
$\\{u,v\\}\cap\\{s,t\\}=\emptyset$ and $w^{*}(uv)=w(uv)-\theta$ otherwise. Now
we note that all $w^{*}$-weights in $H$ are non-negative. We will show that
for any $(s,t)$-cut, $(X_{1},X_{2})$ in $H$ (ie, $(X_{1},X_{2})$ partitions
$V(H)$ and $s\in X_{1}$ and $t\in X_{2}$) the $w^{*}$-weight of the cut is
equal to $-w^{P}(D)-|V(D)|\theta$, where $P$ is the partition
$(X_{1}\setminus\\{s\\},X_{2}\setminus\\{t\\})$ in $D$. Therefore a minimum
weight cut in $H$ maximizes $w^{P}(D)$ in $D$.

Let $(X_{1},X_{2})$ be any $(s,t)$-cut in $H$. For every $u\in V(D)$ we note
that exactly one of the edges $su$ and $ut$ will belong to the cut. Therefore,
we note that the $w^{*}$-weight of the cut is $|V(D)|\theta$ less than the
$w$-weight of the cut. It therefore suffices to show that the $w$-weight of
the cut is $-w^{P}(D)$ (where $P$ is the partition
$(X_{1}\setminus\\{s\\},X_{2}\setminus\\{t\\})$ of $V(D)$).

Let $uv\in A(D)$ be arbitrary and consider the following four possibilities.

  * •

$u,v\in X_{1}$. In this case when we considered the arc $uv$ above (when
defining the $w$-weights) we added $c(uv)\times\frac{m_{21}-m_{11}-m_{12}}{2}$
to $w(tu)$ and $c(uv)\times\frac{m_{12}-m_{11}-m_{21}}{2}$ to $w(tv)$. So, we
added the following amount to the $w$-weight of the $(s,t)$-cut,
$(X_{1},X_{2})$.

$c(uv)\times\left(\frac{m_{21}-m_{11}-m_{12}}{2}+\frac{m_{12}-m_{11}-m_{21}}{2}\right)=-c(uv)\cdot
m_{11}$

  * •

$u,v\in X_{2}$. In this case when we considered the arc $uv$ above (when
defining the $w$-weights) we added $c(uv)\times\left(\frac{-m_{22}}{2}\right)$
to $w(su)$ and $c(uv)\times\left(\frac{-m_{22}}{2}\right)$ to $w(sv)$. So, we
added the following amount to the $w$-weight of the $(s,t)$-cut,
$(X_{1},X_{2})$.

$c(uv)\times\left(\frac{-m_{22}}{2}+\frac{-m_{22}}{2}\right)=-c(uv)\cdot
m_{22}$

  * •

$u\in X_{1}$ and $v\in X_{2}$. In this case when we considered the arc $uv$
above (when defining the $w$-weights) we let
$w(uv)=c(uv)\times\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}$ and added
$c(uv)\times\left(\frac{-m_{22}}{2}\right)$ to $w(sv)$ and
$c(uv)\times\frac{m_{21}-m_{11}-m_{12}}{2}$ to $w(tu)$. So, we added the
following amount to the $w$-weight of the $(s,t)$-cut, $(X_{1},X_{2})$.

$c(uv)\times\left(\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}+\frac{-m_{22}}{2}+\frac{m_{21}-m_{11}-m_{12}}{2}\right)=-c(uv)\cdot
m_{12}$

  * •

$v\in X_{1}$ and $u\in X_{2}$. In this case when we considered the arc $uv$
above (when defining the $w$-weights) we let
$w(uv)=c(uv)\times\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}$ and added
$c(uv)\times\left(\frac{-m_{22}}{2}\right)$ to $w(su)$ and
$c(uv)\times\frac{m_{12}-m_{11}-m_{21}}{2}$ to $w(tv)$. So, we added the
following amount to the $w$-weight of the $(s,t)$-cut, $(X_{1},X_{2})$.

$c(uv)\times\left(\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}+\frac{-m_{22}}{2}+\frac{m_{12}-m_{11}-m_{21}}{2}\right)=-c(uv)\cdot
m_{21}$

Therefore we note that in all cases we have added $-w^{P}(uv)$ to the
$w$-weight of the $(s,t)$-cut, $(X_{1},X_{2})$. So the total $w$-weight of the
$(s,t)$-cut is $-w^{P}(D)$ as desired.

Analogously, if we have a partition $P=(X_{1},X_{2})$ of $V(D)$, then adding
$s$ to $X_{1}$ and $t$ to $X_{2}$ we obtain a $(s,t)$-cut with $w$-weight
$-w^{P}(D)$ of $H$. As we can find a minimum $w^{*}$-weight cut in $H$ in
polynomial time we can find a partition $P=(X_{1},X_{2})$ of $V(D)$ with
minimum value of $-w^{P}(D)$, which corresponds to the maximum value of
$w^{P}(G)$. Therefore, MWDP (${\cal F}$) can be solved in polynomial time in
this case. ∎

######  Proposition 12.

If $m_{11}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$ for all matrices $M\in{\cal
F}$ then MWDP (${\cal F}$) can be solved in polynomial time.

Proof: In this case the maximum is clearly obtained by the partition
$P=(X_{1},X_{2})=(V(D),\emptyset)$ as the maximum possible value of $w^{P}(a)$
for every $a\in A(D)$ is obtained when both endpoints of $a$ belong to
$X_{1}$. Therefore, the problem is polynomial time solvable. ∎

######  Proposition 13.

If $m_{22}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$ for all matrices $M\in{\cal
F}$ then MWDP (${\cal F}$) can be solved in polynomial time.

Proof: In this case the maximum is clearly obtained by the partition
$P=(X_{1},X_{2})=(\emptyset,V(D))$ as the maximum possible value of $w^{P}(a)$
for every $a\in A(D)$ is obtained when both endpoints of $a$ belong to
$X_{2}$. Therefore, the problem is polynomial time solvable. ∎

A hypergraph, $H=(V,E)$, is $3$-uniform if all edges of $H$ contain three
vertices. Two edges overlap if they have at least two vertices in common. A
hypergraph is linear if it contains no overlapping edges. A hypergraph is
2-colorable if the vertex set can be colored with two colors such that every
edge contains vertices of both colors. The following result is well-known.

######  Theorem 14.

Lovász [1973]444In fact, Lovász [1973] proves the result for 4-uniform
hypergraphs, but a simple gadget allows one to reduce it to 3-uniform
hypergraphs. Also, note that the 2-colorability of 3-uniform hypergraphs
problem is equivalent to the monotone NAE 3-SAT problem whose NP-completeness
follows from Schaefer’s dichotomy theorem Schaefer [1978], where monotonicity
means that no negations are allowed in the SAT formulas. It is NP-hard to
decide if a $3$-uniform hypergraph is 2-colorable.

We will extend the above theorem to the following theorem, where we only
consider linear hypergraphs.

######  Theorem 15.

It is NP-hard to decide if a linear $3$-uniform hypergraph is 2-colorable.

Proof: We will reduce from the problem to decide if a $3$-uniform hypergraph
is 2-colorable, which is NP-hard by Theorem 14. So let $H$ be a $3$-uniform
hypergraph. We will reduce $H$ to a linear $3$-uniform hypergraph,
$H^{\prime}$, such that $H$ is 2-colorable if and only if $H^{\prime}$ is
2-colorable. This will complete the proof.

We may assume that $H$ is not linear, as otherwise we just let $H^{\prime}=H$
and we are done. Let $e_{y}=\\{x_{1},x_{2},y\\}$ and
$e_{z}=\\{x_{1},x_{2},z\\}$ be two edges that intersect in at least two
vertices. Let $F$ be a copy of the Fano plane and let
$e=\\{f_{1},f_{2},f_{3}\\}$ be any edge in $F$. It is known that $F$ is not
2-colorable but $F-e$ is 2-colorable and any 2-coloring of $F-e$ assigns the
same color to all vertices of $e$ (as $F$ is not 2-colorable). Now add $F-e$
to $H-x_{1}$ and for every edge in $H$ that contains $x_{1}$ replace $x_{1}$
by some vertex in $\\{f_{1},f_{2},f_{3}\\}$. Furthermore do this such that
$e_{y}$ and $e_{z}$ are given different vertices in $\\{f_{1},f_{2},f_{3}\\}$.
Note that the resulting hypergraph is 2-colorable if and only if $H$ is
2-colorable. Furthermore, the number of edges that overlap has decreased. So,
we have to perform the above operation at most ${|E(H)|\choose
2}\leq|E(H)|^{2}$ times in order to get rid of all overlapping edges. So this
reduction is polynomial and results in a linear $3$-uniform hypergraph,
$H^{\prime}$, that is 2-colorable if and only if $H$ 2-colorable. ∎

######  Theorem 16.

If $m_{11}+m_{22}<m_{12}+m_{21}$ and
$\max\\{m_{11},m_{22}\\}<\max\\{m_{12},m_{21}\\}$ for some matrix $M\in{\cal
F}$ then MWDP (${\cal F}$) is NP-hard to solve.

Proof: We will reduce from the problem of determining if a linear $3$-uniform
hypergraph is bipartite, which is NP-hard by Theorem 15. Let $H=(V,E)$ be a
linear $3$-uniform hypergraph. We will now construct an instance of MWDP
(${\cal F}$), such that a solution to this instance will tell us if $H$ is
bipartite or not.

We start by letting $V(D)=V(H)$ and for each edge $e\in E(H)$ we add a
directed $3$-cycle $C_{e}=xyzx$ to $D$, where $V(e)=\\{x,y,z\\}$. Furthermore
for each arc $a$ in the directed $3$-cycle let $c(a)=1$ and $f(a)=M$ ($M$ is
defined in the statement of the theorem). As $H$ is linear we note that $D$ is
an oriented graph (i.e., it has no directed $2$-cycles or parallel arcs). We
now consider the following cases.

Case 1. $m_{11}=m_{22}$: In this case we will show that the above construction
of $(D,c,f)$ is sufficient. If $P=(X_{1},X_{2})$ is a partition on $V(H)$ (and
therefore also a partition of $V(D)$) and $e\in E(H)$ then the following
holds.

  * •

If $|V(e)\cap X_{1}|=3$ then the arcs of $C_{e}$ contribute $3m_{11}$ to
$w^{P}(D)$.

  * •

If $|V(e)\cap X_{1}|=2$ then the arcs of $C_{e}$ contribute
$m_{11}+m_{12}+m_{21}$ to $w^{P}(D)$.

  * •

If $|V(e)\cap X_{1}|=1$ then the arcs of $C_{e}$ contribute
$m_{22}+m_{12}+m_{21}$ to $w^{P}(D)$.

  * •

If $|V(e)\cap X_{1}|=0$ then the arcs of $C_{e}$ contribute $3m_{22}$ to
$w^{P}(D)$.

So, as $m_{11}=m_{22}$, this implies the following.

  * •

If $|V(e)\cap X_{1}|\in\\{0,3\\}$ then the arcs of $C_{e}$ contribute
$3m_{11}$ to $w^{P}(D)$.

  * •

If $|V(e)\cap X_{1}|\in\\{1,2\\}$ then the arcs of $C_{e}$ contribute
$m_{11}+m_{12}+m_{21}$ to $w^{P}(D)$.

And as $m_{12}+m_{21}>m_{11}+m_{22}=2m_{11}$ we note that the maximum value of
$w^{P}(D)$ is $|V(H)|(m_{11}+m_{12}+m_{21})$ if and only if $|V(e)\cap
X_{1}|\in\\{1,2\\}$ for all $e\in E(H)$, which is equivalent to $H$ being
bipartite (as $X_{1}$ are the vertices with one color and $X_{2}$ are the
vertices with the other color). So in this case we have the desired reduction.

Case 2. $m_{11}\not=m_{22}$: Without loss of generality we may assume that
$m_{11}>m_{22}$. We now construct an instance, $(G(x,y),c,f)$, of MWDP (${\cal
F}$) such that every optimal solution $(X_{1},X_{2})$ for $G(x,y)$ has $x\in
X_{1}$ and $y\in X_{2}$.

If $m_{12}>m_{21}$ then $m_{12}$ is the unique largest value in
$\\{m_{11},m_{22},m_{12},m_{21}\\}$. Let $G(x,y)$ have vertex set $\\{x,y\\}$
and contain a single arc $xy$ with $f(xy)=M$ and $c(xy)=1$. Then $x\in X_{1}$
and $y\in X_{2}$ for all optimal solutions $(X_{1},X_{2})$ to $G(x,y)$.

If $m_{21}>m_{12}$ then $m_{21}$ is the unique largest value in
$\\{m_{11},m_{22},m_{12},m_{21}\\}$. Analogously to the above construction,
let $G(x,y)$ have vertex set $\\{x,y\\}$ and contain a single arc $yx$ with
$f(yx)=M$ and $c(xy)=1$. Then $x\in X_{1}$ and $y\in X_{2}$ for all optimal
solutions $(X_{1},X_{2})$ to $G(x,y)$.

Finally consider the case when $m_{12}=m_{21}$. Let $G(x,y)$ have vertex set
$\\{x,y,z\\}$ and contain a directed $3$-cycle $xyzx$ with
$f(xy)=f(yz)=f(zx)=M$ and $c(xy)=c(yz)=2$ and $c(zx)=1$. Then $x\in X_{1}$
(and $z\in X_{1}$) and $y\in X_{2}$ for all optimal solutions $(X_{1},X_{2})$
to $G(x,y)$ (as $m_{12}>m_{11}>m_{22}$).

Let $m^{*}=\max\\{m_{12},m_{21}\\}$ and let
$\theta=\frac{m_{11}-m_{22}}{m^{*}-m_{11}}$. Note that $\theta>0$ as
$m_{11}>m_{22}$ and $m^{*}>m_{11}$. We now add $G(x,y)$ to $D$ (defined beforw
Case 1) and add arcs between $G(x,y)$ and $D$ as follows.

  * •

If $m_{12}>m_{21}$. In this case add all possible arcs, $a$, from $x$ to
$V(D)$ and let $c(a)=0$ and $f(a)=M$ for each of these. Now for each $e\in
E(H)$ we add $\theta$ to the $c$-value of the three arcs from $x$ to
$V(C_{e})$. This completes the construction.

  * •

If $m_{12}\leq m_{21}$. In this case add all possible arcs, $a$, from $V(D)$
to $x$ and let the $c(a)=0$ and $f(a)=M$ for each of these. Now for each $e\in
E(H)$ we add $\theta$ to the $c$-value of the three arcs from $V(C_{e})$ to
$x$. This completes the construction.

Let $D^{*}$ denote the resulting digraph. Now multiply the $c$-values of all
arcs in $G(x,y)$ by a large enough constant to force $x\in X_{1}$ and $y\in
X_{2}$ for all optimal solutions $(X_{1},X_{2})$ to $D^{*}$. Let
$P=(X_{1},X_{2})$ be any partition of $V(H)$. The following now holds for each
$e\in E(H)$.

If $|V(e)\cap X_{1}|=3$:

Then the arcs of $C_{e}$ contribute $3m_{11}$ to $w^{P}(D^{*})$ and the
weights we added to the arcs between $x$ and $V(e)$ when considering $e$
contribute $3\theta m_{11}$ to $w^{P}(D^{*})$. So all-in-all $w^{P}(D^{*})$
has increased by the following amount due to $e$,

$s_{3}=3m_{11}+3\theta m_{11}$

If $|V(e)\cap X_{1}|=2$:

Then the arcs of $C_{e}$ contribute $m_{11}+m_{12}+m_{21}$ to $w^{P}(D^{*})$
and the weights we added to the arcs between $x$ and $V(e)$ when considering
$e$ contribute $2\theta m_{11}+\theta m^{*}$ to $w^{P}(D^{*})$. So all-in-all
$w^{P}(D^{*})$ has increased by the following amount due to $e$,

$s_{2}=m_{11}+m_{12}+m_{21}+\theta(2m_{11}+m^{*})$

If $|V(e)\cap X_{1}|=1$:

Then the arcs of $C_{e}$ contribute $m_{22}+m_{12}+m_{21}$ to $w^{P}(D^{*})$
and the weights we added to the arcs between $x$ and $V(e)$ when considering
$e$ contribute $\theta m_{11}+2\theta m^{*}$ to $w^{P}(D^{*})$. So all-in-all
$w^{P}(D^{*})$ has increased by the following amount due to $e$,

$s_{1}=m_{22}+m_{12}+m_{21}+\theta(m_{11}+2m^{*})$

If $|V(e)\cap X_{1}|=0$:

Then the arcs of $C_{e}$ contribute $3m_{22}$ to $w^{P}(D^{*})$ and the
weights we added to the arcs between $x$ and $V(e)$ when considering $e$
contribute $3\theta m^{*}$ to $w^{P}(D^{*})$. So all-in-all $w^{P}(D^{*})$ has
increased by the following amount due to $e$,

$s_{0}=3m_{22}+3\theta m^{*}$

We will now show that $s_{0}=s_{3}<s_{2}=s_{1}$, which implies that $H$ is
bipartite if and only if the optimal solution, $P=(X_{1},X_{2})$, for $D^{*}$
has $|V(e)\cap X_{1}|\in\\{1,2\\}$ for all $e\in E(H)$. So we have reduced the
problem of determining if a linear $3$-uniform hypergraph is 2-colorable
(which is NP-hard by Theorem 15) to MWDP (${\cal F}$) as desired. So the
following claims complete the proof.

Claim 2.A: $s_{0}=s_{3}$.

Proof of Claim 2.A: Note that the following holds as
$\theta=\frac{m_{11}-m_{22}}{m^{*}-m_{11}}$, which proves the claim.

$\begin{array}[]{rcl}s_{3}-s_{0}&=&(3m_{11}+3\theta m_{11})-(3m_{22}+3\theta
m^{*})\\\
&=&3(m_{11}-m_{22})+3\frac{m_{11}-m_{22}}{m^{*}-m_{11}}(m_{11}-m^{*})\\\
&=&0\\\ \end{array}$

Claim 2.B: $s_{2}=s_{1}$.

Proof of Claim 2.B: Note that the following holds as
$\theta=\frac{m_{11}-m_{22}}{m^{*}-m_{11}}$, which proves the claim.

$s_{2}-s_{1}=m_{11}-m_{22}+\theta(m_{11}-m^{*})=(m_{11}-m_{22})-(m_{11}-m_{22})=0$

Claim 2.C: $s_{3}<s_{2}$.

Proof of Claim 2.C: Note that the following holds as
$\theta=\frac{m_{11}-m_{22}}{m^{*}-m_{11}}$, which proves the claim.

$\begin{array}[]{rcl}s_{2}-s_{3}&=&(m_{12}+m_{21}-2m_{11})+\theta(m^{*}-m_{11})\\\
&=&(m_{12}+m_{21}-2m_{11})+(m_{11}-m_{22})\\\
&=&(m_{12}+m_{21})-(m_{11}+m_{22})\\\ &>&0\\\ \end{array}$

∎

Note that Lemma 3, Proposition 12, Proposition 13 and Theorem 16 imply a
dichotomy for MWDP (${\cal F}$) when ${\cal F}$ only contains a single matrix.
In order to obtain a complete dichotomy for all ${\cal F}$ we need the results
in the following section.

##  Appendix B Proving Theorem 2

Let $M$ be a $2\times 2$ matrix. We now define the following three properties
of $M$ which may, or may not, hold.

Property (a):

$m_{11}+m_{22}\geq m_{12}+m_{21}$.

Property (b):

$m_{11}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$.

Property (c):

$m_{22}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$.

Note that Lemma 3, Proposition 12, Proposition 13 and Theorem 16 can be
reformulates as follows.

######  Corollary 17.

MWDP (${\cal F}$) can be solved in polynomial time if all matrices in ${\cal
F}$ satisfy Property (a) or all matrices in ${\cal F}$ satisfy Property (b) or
all matrices in ${\cal F}$ satisfy Property (c). MWDP (${\cal F}$) is NP-hard
if some matrix in ${\cal F}$ does not satisfy any of the properties (a), (b)
or (c).

######  Theorem 18.

We consider MWDP (${\cal F}$), where $M$ and $R$ are distinct matrices in
${\cal F}$. If $M$ satisfies Property (b), but not Property (a) or Property
(c) and $R$ satisfy Property (c), but not Property (b) (it may, or may not,
satisfies Property (a)) then MWDP (${\cal F}$) is NP-hard to solve.

By symmetry, if $M$ satisfies Property (c), but not Property (a) or Property
(b) and $R$ satisfies Property (b), but not Property (c) (it may, or may not,
satisfy Property (a)) then the problem is also NP-hard to solve.

Proof: Let $M$ and $R$ be defined as in the statement of the theorem. That is,
the following holds.

(a):

$m_{11}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$ (as Property (b) holds for
$M$).

(b):

$m_{11}+m_{22}<m_{12}+m_{21}$ (as Property (a) does not hold for $M$)

(c):

$m_{22}<\max\\{m_{11},m_{22},m_{12},m_{21}\\}$ (as Property (c) does not hold
for $M$)

(d):

$r_{22}=\max\\{r_{11},r_{22},r_{12},r_{21}\\}$ (as Property (c) holds for
$R$).

(e):

$r_{11}<\max\\{r_{11},r_{22},r_{12},r_{21}\\}$ (as Property (b) does not hold
for $R$)

(f):

$m_{11}>m_{22}$, as by (a) and (c) we have
$m_{11}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}>m_{22}$.

(g):

$r_{22}>r_{11}$, as by (d) and (e) we have
$r_{22}=\max\\{r_{11},r_{22},r_{12},r_{21}\\}>r_{11}$.

We will first construct an instance $(D(x,x^{\prime},y,y^{\prime}),c,f)$ of
MWDP (${\cal F}$) such that for all optimal solutions $P=(X_{1},X_{2})$ of the
instance we have $x,x^{\prime}\in X_{1}$ and $y,y^{\prime}\in X_{2}$. We
consider the following cases.

Case 1: $m_{11}=m_{12}=m_{21}$ is not true and $r_{22}=r_{12}=r_{21}$ is also
not true. In this case
$V(D(x,x^{\prime},y,y^{\prime}))=\\{x,x^{\prime},x^{\prime\prime},y,y^{\prime},y^{\prime\prime}\\}$
and
$A(D(x,x^{\prime},y,y^{\prime}))=\\{xx^{\prime},x^{\prime}x^{\prime\prime},x^{\prime\prime}x,yy^{\prime},y^{\prime}y^{\prime\prime},y^{\prime\prime}y\\}$.
Furthermore $c(a)=1$ for all arcs $a\in A(D(x,x^{\prime},y,y^{\prime}))$ and
$f(xx^{\prime})=f(x^{\prime}x^{\prime\prime})=f(x^{\prime\prime}x)=M$ and
$f(yy^{\prime})=f(y^{\prime}y^{\prime\prime})=f(y^{\prime\prime}y)=R$. The
only optimal solution $P=(X_{1},X_{2})$ is now
$X_{1}=\\{x,x^{\prime},x^{\prime\prime}\\}$ and
$X_{2}=\\{y,y^{\prime},y^{\prime\prime}\\}$ with value
$w^{P}(D(x,x^{\prime},y,y^{\prime}))=3m_{11}+3r_{22}$.

Case 2: $m_{11}=m_{12}=m_{21}$ and $r_{22}=r_{12}=r_{21}$. In this case
$V(D(x,x^{\prime},y,y^{\prime}))=\\{x,x^{\prime},x_{2},x_{3},y,y^{\prime},y_{2},y_{3}\\}$
and
$A(D(x,x^{\prime},y,y^{\prime}))=\\{xx_{2},xx_{3},x^{\prime}x_{2},x^{\prime}x_{3},x_{2}x_{3},yy_{2},yy_{3},y^{\prime}y_{2},y^{\prime}y_{3},y_{2}y_{3}\\}$.
Furthermore $c(a)=1$ for all arcs $a\in A(D(x,x^{\prime},y,y^{\prime}))$ and
$f(xx_{2})=f(xx_{3})=f(x^{\prime}x_{2})=f(x^{\prime}x_{3})=f(y_{2}y_{3})=M$
and
$f(yy_{2})=f(yy_{3})=f(y^{\prime}y_{2})=f(y^{\prime}y_{3})=f(x_{2}x_{3})=R$.
We note that $X_{1}=\\{x,x^{\prime},y_{2},y_{3}\\}$ and
$X_{2}=\\{y,y^{\prime},x_{2},x_{3}\\}$ is an optimal solution with value
$w^{P}(D(x,x^{\prime},y,y^{\prime}))=m_{11}+4m_{12}+r_{22}+4r_{21}=5m_{11}+5r_{22}$.

For the sake of contradiction assume that some other optimal solution
$P=(X_{1},X_{2})$ has $x\in X_{2}$. If both $x_{2}$ and $x_{3}$ are in $X_{1}$
then $w^{P}(x_{2}x_{3})=r_{11}<r_{22}$, contradicting the fact that $P$ was
optimal. So either $x_{2}\in X_{2}$ or $x_{3}\in X_{2}$. but in either case we
have an arc $a\in\\{xx_{2},xx_{3}\\}$ with $w^{P}(a)=m_{22}<m_{11}$,
contradicting the fact that $P$ was optimal. So we must have $x\in X_{1}$ for
all optimal solutions $P=(X_{1},X_{2})$. Analogously we can show that we also
must have $x^{\prime}\in X_{1}$, $y\in X_{2}$ and $y^{\prime}\in X_{2}$, which
completes the proof of Case 2.

Case 3: $m_{11}=m_{12}=m_{21}$ is not true but $r_{22}=r_{12}=r_{21}$ is true.
In this case
$V(D(x,x^{\prime},y,y^{\prime}))=\\{x,x^{\prime},y,y^{\prime},z\\}$ and
$A(D(x,x^{\prime},y,y^{\prime}))=\\{xx^{\prime},x^{\prime}z,zx,yy^{\prime},y^{\prime}z,zy\\}$.
Furthermore $c(a)=1$ for all arcs $a\in A(D(x,x^{\prime},y,y^{\prime}))$ and
$f(xx^{\prime})=f(x^{\prime}z)=f(zx)=M$ and
$f(yy^{\prime})=f(y^{\prime}z)=f(zy)=R$. We note that
$X_{1}=\\{x,x^{\prime},z\\}$ and $X_{2}=\\{y,y^{\prime}\\}$ is an optimal
solution with value
$w^{P}(D(x,x^{\prime},y,y^{\prime}))=3m_{11}+r_{22}+r_{12}+r_{21}=3m_{11}+3r_{22}$.
It is furthermore not difficult to check that this is the only optimal
solution.

Case 4: $m_{11}=m_{12}=m_{21}$ but $r_{22}=r_{12}=r_{21}$ is not true. This
can be proved analogously to Case 3.

Now that we have constructed $D(x,x^{\prime},y,y^{\prime})$ we can give the
NP-hardness proof. We will reduce from the (unweighted) MaxCut problem. Let
$G$ be any graph where we wish to find a cut with the maximum number of edges.
We initially let $V(D^{*})=V(G)$. Let
$\epsilon=\frac{m_{11}-m_{22}}{r_{22}-r_{11}}$ and note that $\epsilon>0$ by
properties (f) and (g). For each edge $e\in E(G)$, we now perform the
following modifications to $D^{*}$.

1.

If $e=uv$ in $G$ then add the arc $uv$ to $D^{*}$ (any orientation of $e$ can
be added to $D^{*}$) and let $c(uv)=1$ and $f(uv)=M$.

2.

Add a copy, $D_{e}(x_{e},x_{e}^{\prime},y_{e},y_{e}^{\prime})$, of
$D(x,x^{\prime},y,y^{\prime})$ to $D^{*}$ and add the following arcs.

2a.

Add the directed $4$-cycle $C_{e}=ux_{e}vy_{e}u$ to $D^{*}$ and let
$c(a)=\epsilon$ and $f(a)=R$ for all $a\in A(C_{e})$.

2b.

Add the arcs
$A_{e}=\\{vx^{\prime}_{e},x^{\prime}_{e}u,vy^{\prime}_{e},y^{\prime}_{e}u\\}$
to $D^{*}$ and let $c(a)=1/2$ and $f(a)=M$ for all $a\in A(A_{e})$.

3.

Multiply $c(a)$ by a large constant, $K$, for all arcs $a$ which are part of a
gadget $D_{e}(x_{e},x_{e}^{\prime},y_{e},y_{e}^{\prime})$ such that
$x_{e},x_{e}^{\prime}\in X_{1}$ and $y_{e},y_{e}^{\prime}\in X_{2}$ for all
optimal solutions $P=(X_{1},X_{2})$.

Let $P=(X_{1},X_{2})$ be an optimal solution for the instance $(D^{*},c,f)$.
Let $e=uv\in E(G)$ be arbitrary, such that $uv$ was added to $D^{*}$ in Step 1
above. Now consider the following four cases.

Case A: $u,v\in X_{1}$. The arcs added to $D^{*}$ in Step 1 and Steps 2a and
2b above contribute the following to $w^{P}(D^{*})$.

$s_{A}=m_{11}+\frac{2m_{11}+m_{12}+m_{21}}{2}+\epsilon(2r_{11}+r_{12}+r_{21})$

Case B: $u,v\in X_{2}$. The arcs added to $D^{*}$ in Step 1 and Steps 2a and
2b above contribute the following to $w^{P}(D^{*})$.

$s_{B}=m_{22}+\frac{2m_{22}+m_{12}+m_{21}}{2}+\epsilon(2r_{22}+r_{12}+r_{21})$

Case C: $u\in X_{1}$ and $v\in X_{2}$. The arcs added to $D^{*}$ in Step 1 and
Steps 2a and 2b above contribute the following to $w^{P}(D^{*})$.

$s_{C}=m_{12}+\frac{2m_{21}+m_{11}+m_{22}}{2}+\epsilon(r_{11}+r_{22}+r_{12}+r_{21})$

Case D: $u\in X_{1}$ and $v\in X_{2}$. The arcs added to $D^{*}$ in Step 1 and
Steps 2a and 2b above contribute the following to $w^{P}(D^{*})$.

$s_{D}=m_{21}+\frac{2m_{12}+m_{11}+m_{22}}{2}+\epsilon(r_{11}+r_{22}+r_{12}+r_{21})$

We immediately see that $s_{C}=s_{D}$ as they are both equal to
$m_{21}+m_{12}+(m_{11}+m_{22})/2+\epsilon(r_{11}+r_{22}+r_{12}+r_{21})$. We
will now show that $s_{A}=s_{B}$, which follows from the following, as
$\epsilon=\frac{m_{11}-m_{22}}{r_{22}-r_{11}}$.

$\begin{array}[]{crcl}&m_{11}-m_{22}&=&\epsilon(r_{22}-r_{11})\\\
\Updownarrow&&&\\\ &2m_{11}+2\epsilon r_{11}&=&2m_{22}+2\epsilon r_{22}\\\
\Updownarrow&&&\\\
&m_{11}+\frac{2m_{11}+m_{12}+m_{21}}{2}+\epsilon(2r_{11}+r_{12}+r_{21})&=&m_{22}+\frac{2m_{22}+m_{12}+m_{21}}{2}+\epsilon(2r_{22}+r_{12}+r_{21})\\\
\Updownarrow&&&\\\ &s_{A}&=&s_{B}\\\ \end{array}$

This implies that $s_{A}=s_{B}$. We also note that the following holds.

$\begin{array}[]{rclcl}(s_{C}+s_{D})-(s_{A}+s_{B})&=&(m_{12}+m_{21})-(m_{11}+m_{22})&>&0\\\
\end{array}$

So for every edge $e\in E(G)$ belonging to the cut $(X_{1},X_{2})$ we add
$s_{C}$ ($=s_{D}$) to the value $w^{P}(D^{*})$ and for every edge $e\in E(G)$
not belonging to the cut $(X_{1},X_{2})$ we add $s_{A}$
($=s_{B}<s_{C}=s_{D}$). So an optimal solution to max-cut for $G$ is
equivalent to an optimal solution $(X_{1},X_{2})$ of $(D^{*},c,f)$. This
completes the proof of the first part of the theorem.

The second part follows immediately by symmetry. ∎

######  Theorem 19.

We consider $\textsc{MWDP}({\mathcal{F}}$), where $M$ and $R$ are distinct
matrices in ${\cal F}$. If $M$ satisfies Property (b), but not Property (a) or
Property (c) and $R$ satisfies Property (a), but not Property (b) or Property
(c) then $\textsc{MWDP}({\cal F}$) is NP-hard to solve.

By symmetry, if $M$ satisfies Property (c), but not Property (a) or Property
(b) and $R$ satisfies Property (a), but not Property (b) or Property (c) then
the problem is also NP-hard to solve.

Proof: Let $M$ and $R$ be defined as in the statement of the theorem. That is,
the following holds.

(a):

$m_{11}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$ (as Property (b) holds for
$M$).

(b):

$m_{11}+m_{22}<m_{12}+m_{21}$ (as Property (a) does not hold for $M$)

(c):

$m_{22}<\max\\{m_{11},m_{22},m_{12},m_{21}\\}$ (as Property (c) does not hold
for $M$)

(d):

$r_{11}+r_{22}\geq r_{12}+r_{21}$ (as Property (a) holds for $R$).

(e):

$r_{22}<\max\\{r_{11},r_{22},r_{12},r_{21}\\}$ (as Property (c) does not hold
for $R$).

(f):

$r_{11}<\max\\{r_{11},r_{22},r_{12},r_{21}\\}$ (as Property (b) does not hold
for $R$)

(g):

$m_{11}>m_{22}$, as by (a) and (c) we have
$m_{11}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}>m_{22}$.

(h):

$r_{12}\not=r_{21}$, as if $r_{12}=r_{21}$, then
$r_{12}=r_{21}=\max\\{r_{11},r_{22},r_{12},r_{21}\\}$, by (e) and (f), which
is impossible by (d) (and (e) and (f)).

We will first construct an instance $(D(x,x^{\prime},y,y^{\prime}),c,f)$ of
MWDP (${\cal F}$) such that for all optimal solutions $P=(X_{1},X_{2})$ of the
instance we have $x,x^{\prime}\in X_{1}$ and $y,y^{\prime}\in X_{2}$. We
consider the following cases, which exhaust all possiblities by statement (h)
above.

Case 1: $r_{12}>r_{21}$. By (e) and (f) we note that $r_{12}$ is the unique
largest value in $\\{r_{11},r_{22},r_{12},r_{21}\\}$. Let
$V(D(x,x^{\prime},y,y^{\prime}))=\\{x,x^{\prime},y,y^{\prime}\\}$ and
$A(D(x,x^{\prime},y,y^{\prime}))=\\{xy,x^{\prime}y^{\prime}\\}$. Furthermore
$c(xy)=c(x^{\prime}y^{\prime})=1$ and $f(xy)=f(x^{\prime}y^{\prime})=R$. The
only optimal solution $P=(X_{1},X_{2})$ is now $X_{1}=\\{x,x^{\prime}\\}$ and
$X_{2}=\\{y,y^{\prime}\\}$ with value
$w^{P}(D(x,x^{\prime},y,y^{\prime}))=2r_{12}$.

Case 2: $r_{21}>r_{12}$. By (e) and (f) we note that $r_{21}$ is the unique
largest value in $\\{r_{11},r_{22},r_{12},r_{21}\\}$. Let
$V(D(x,x^{\prime},y,y^{\prime}))=\\{x,x^{\prime},y,y^{\prime}\\}$ and
$A(D(x,x^{\prime},y,y^{\prime}))=\\{yx,y^{\prime}x^{\prime}\\}$. Furthermore
$c(yx)=c(y^{\prime}x^{\prime})=1$ and $f(yx)=f(y^{\prime}x^{\prime})=R$. The
only optimal solution $P=(X_{1},X_{2})$ is now $X_{1}=\\{x,x^{\prime}\\}$ and
$X_{2}=\\{y,y^{\prime}\\}$ with value
$w^{P}(D(x,x^{\prime},y,y^{\prime}))=2r_{21}$.

Now that we have constructed $D(x,x^{\prime},y,y^{\prime})$ we can give the
NP-hardness proof. We will reduce from the (unweighted) MaxCut problem. So let
$G$ be any graph where we are interested in finding a cut with the maximum
number of edges. We initially let $V(D^{*})=V(G)$. Let
$r^{*}=\max\\{r_{12},r_{21}\\}$ and let
$\epsilon=\frac{m_{11}-m_{22}}{r^{*}-r_{11}}$ and note that $\epsilon>0$ by
properties (g), (e) and (f). For each edge $e\in E(G)$ we now perform the
following modifications to $D^{*}$.

1.

If $e=uv$ in $G$ then add the arc $uv$ to $D^{*}$ (any orientation of $e$ can
be added to $D^{*}$) and let $c(uv)=1$ and $f(uv)=M$.

2.

Add a copy, $D_{e}(x_{e},x_{e}^{\prime},y_{e},y_{e}^{\prime})$, of
$D(x,x^{\prime},y,y^{\prime})$ to $D^{*}$ and add the following arcs.

2a.

If $r_{12}>r_{21}$ then add the arcs $A_{e}^{\prime}=\\{x_{e}u,x_{e}v\\}$ to
$D^{*}$ and let $c(x_{e}u)=c(x_{e}v)=\epsilon$ and $f(x_{e}u)=f(x_{e}v)=R$.

And if $r_{12}<r_{21}$ then add the arcs $A_{e}^{\prime}=\\{ux_{e},vx_{e}\\}$
to $D^{*}$ and let $c(u_{e}x)=c(vx_{e})=\epsilon$ and $f(ux_{e})=f(vx_{e})=R$.

2b.

Add the arcs
$A_{e}=\\{vx^{\prime}_{e},x^{\prime}_{e}u,vy^{\prime}_{e},y^{\prime}_{e}u\\}$
to $D^{*}$ and let $c(a)=1/2$ and $f(a)=M$ for all $a\in A(A_{e})$.

3.

Multiply $c(a)$ by a large constant, $K$, for all arcs $a$ which are part of a
gadget $D_{e}(x_{e},x_{e}^{\prime},y_{e},y_{e}^{\prime})$ such that
$x_{e},x_{e}^{\prime}\in X_{1}$ and $y_{e},y_{e}^{\prime}\in X_{2}$ for all
optimal solutions $P=(X_{1},X_{2})$.

Let $P=(X_{1},X_{2})$ be an optimal solution for the instance $(D^{*},c,f)$.
Let $e=uv\in E(G)$ be arbitrary, such that $uv$ was added to $D^{*}$ in Step 1
above. Now consider the following four cases.

Case A: $u,v\in X_{1}$. The arcs added to $D^{*}$ in Step 1 and Steps 2a and
2b above contribute the following to $w^{P}(D^{*})$.

$s_{A}=m_{11}+\frac{2m_{11}+m_{12}+m_{21}}{2}+\epsilon(2r_{11})$

Case B: $u,v\in X_{2}$. The arcs added to $D^{*}$ in Step 1 and Steps 2a and
2b above contribute the following to $w^{P}(D^{*})$.

$s_{B}=m_{22}+\frac{2m_{22}+m_{12}+m_{21}}{2}+\epsilon(2r^{*})$

Case C: $u\in X_{1}$ and $v\in X_{2}$. The arcs added to $D^{*}$ in Step 1 and
Steps 2a and 2b above contribute the following to $w^{P}(D^{*})$.

$s_{C}=m_{12}+\frac{2m_{21}+m_{11}+m_{22}}{2}+\epsilon(r^{*}+r_{11})$

Case D: $u\in X_{2}$ and $v\in X_{1}$. The arcs added to $D^{*}$ in Step 1 and
Steps 2a and 2b above contribute the following to $w^{P}(D^{*})$.

$s_{D}=m_{21}+\frac{2m_{12}+m_{11}+m_{22}}{2}+\epsilon(r^{*}+r_{11})$

We immediately see that $s_{C}=s_{D}$ as they are both equal to
$m_{21}+m_{12}+(m_{11}+m_{22})/2+\epsilon(r^{*}+r_{11})$. We will now show
that $s_{A}=s_{B}$, which follows from the following, as
$\epsilon=\frac{m_{11}-m_{22}}{r^{*}-r_{11}}$.

$\begin{array}[]{crcl}&m_{11}-m_{22}&=&\epsilon(r^{*}-r_{11})\\\
\Updownarrow&&&\\\ &2m_{11}+2\epsilon r_{11}&=&2m_{22}+2\epsilon r^{*}\\\
\Updownarrow&&&\\\ &m_{11}+\frac{2m_{11}+m_{12}+m_{21}}{2}+2\epsilon
r_{11}&=&m_{22}+\frac{2m_{22}+m_{12}+m_{21}}{2}+2\epsilon r^{*}\\\
\Updownarrow&&&\\\ &s_{A}&=&s_{B}\\\ \end{array}$

This implies that $s_{A}=s_{B}$. We also note that the following holds.

$\begin{array}[]{rclcl}(s_{C}+s_{D})-(s_{A}+s_{B})&=&(m_{12}+m_{21})-(m_{11}+m_{22})&>&0\\\
\end{array}$

So for every edge $e\in E(G)$ belonging to the cut $(X_{1},X_{2})$ we add
$s_{C}$ ($=s_{D}$) to the value $w^{P}(D^{*})$ and for every edge $e\in E(G)$
not belonging to the cut $(X_{1},X_{2})$ we add $s_{A}$
($=s_{B}<s_{C}=s_{D}$). So an optimal solution to max-cut for $G$ is
equivalent to an optimal solution $(X_{1},X_{2})$ of $(D^{*},c,f)$. This
completes the proof of the first part of the theorem.

The second part follows immediately by symmetry. ∎

Now we are ready to prove our dichotomy.

Theorem 2 MWDP (${\cal F}$) can be solved in polynomial time if all matrices
in ${\cal F}$ satisfy Property (a) or all matrices in ${\cal F}$ satisfy
Property (b) or all matrices in ${\cal F}$ satisfy Property (c). Otherwise,
MWDP (${\cal F}$) is NP-hard.

Proof: Parts (1), (2) and (3) follow from Corollary 17 (and also from Lemma 3,
Proposition 12 and Proposition 13). So now assume that some matrix in ${\cal
F}$ does not satisfy Property (a), some matrix (possibly the same) does not
satisfy Property (b) and some matrix (possibly the same) does not satisfy
Property (c). Let $M$ be a matrix in ${\cal F}$ that does not satisfy Property
(a). If $M$ does not satisfy Property (b) and does not satisfy Property (c)
then we are done by Theorem 16, so, without loss of generality, we may assume
that $M$ satisfies Property (b). If $M$ satisfies Property (c), then
$m_{11}=m_{22}=\max\\{m_{11},m_{22},m_{12},m_{21}\\}$, which implies that
Property (a) holds, a contradiction. So assume that $M$ satisfies Property
(b), but not Property (a) or Property (c).

Let $R$ be a matrix in ${\cal F}$ that does not satisfy Property (b). If $R$
satisfies Property (c), then we are done by Theorem 18, so we may assume that
this is not the case. If $R$ satisfies Property (a), then we are done by
Theorem 19, so we may assume that this is not the case. But now $R$ does not
satisfy Property (a), Property (b) or Property (c) and we are done by Theorem
16. ∎

##  Appendix C Proving Case 3 of Theorem 11

Let $\gamma_{A}=1$ and let $\gamma_{B}=0$ and $G$ be a graph and let $(A,B)$
be a partition of $V(G)$, so that if $u\in
Y\Leftrightarrow\gamma_{u}=\gamma_{Y}$, where $Y\in\\{A,B\\}$. We want to find
a Nash equilibrium, $(X_{\textsf{one}},X_{\textsf{two}})$, of maximum welfare,
where $X_{i}$ denotes the set of players that choose action
$i\in\\{\textsf{one},\textsf{two}\\}$.

Let $(X_{\textsf{one}},X_{\textsf{two}})$ be a Nash equilibrium of $G$. This
implies that all vertices in $X_{\textsf{two}}\cap A$ only have edges to
vertices in $X_{\textsf{two}}$ (as otherwise it is not a Nash equilibrium).
Note that this means that any connected component $C$ in $G[A]$ is either
subset of $X_{\textsf{one}}$ or a subset of $X_{\textsf{two}}$, else one can
find an edge from a vertex in $X_{\textsf{two}}\cap A$ to a vertex in
$X_{\textsf{one}}$. Analogously, every connected component of $G[B]$ is either
a subset of $X_{\textsf{one}}$ or a subset of $X_{\textsf{two}}$. Finally,
given a connected component $C_{A}$ of $G[A]$ and a connected component
$C_{B}$ of $G[B]$, if there is an edge in $G$ between a vertex $u\in C_{A}$
and a vertex $v\in C_{B}$, then it is not possible that $C_{B}\subseteq
X_{\textsf{one}}$ and $C_{A}\subseteq X_{\textsf{two}}$.

We now build a digraph $D$ as follows. Let
$C_{1}^{A},C_{2}^{A},\ldots,C_{l}^{A}$ be the components of $G[A]$ and
$C_{1}^{B},C_{2}^{B},\ldots,C_{m}^{B}$ the components of $G[B]$. Let
$V(D)=\\{s,t\\}\cup\\{a_{1},a_{2},\ldots,a_{l}\\}\cup\\{b_{1},b_{2},\ldots,b_{m}\\}$.
For each $C_{i}^{A}$ add an arc from $s$ to $a_{i}$ of weight
$2|E(C_{i}^{A})|$ and for each $C_{i}^{B}$ add an arc from $b_{i}$ to $t$ of
weight $2|E(C_{i}^{B})|$. Now for each $i\in\\{1,2,\ldots,l\\}$ and
$j\in\\{1,2,\ldots,m\\}$ we add an arc from $a_{i}$ to $b_{j}$ of weight
$|E(C_{i}^{A},C_{j}^{B})|$ and if $|E(C_{i}^{A},C_{j}^{B})|>0$ then add an arc
from $b_{j}$ to $a_{i}$ of infinite weight. This completes the construction of
$D$.

Let $(S,T)$ be a $(s,t)$-cut (i.e., $s\in S$ and $t\in T$) in $D$ containing
no arc of infinite weight. Let the weight of $(S,T)$ be $w(S,T)$. We will now
construct a Nash equilibrium $(X_{\textsf{one}},X_{\textsf{two}})$ of $G$. For
every $a_{i}\in S$ add all vertices in $C_{i}^{A}$ to $X_{\textsf{one}}$ and
for every $a_{i}\in T$ add all vertices in $C_{i}^{A}$ to $X_{\textsf{two}}$.
Analogously, for every $b_{j}\in S$ add all vertices in $C_{j}^{B}$ to
$X_{\textsf{one}}$ and for every $b_{j}\in T$ add all vertices in $C_{j}^{B}$
to $X_{\textsf{two}}$. This defines a partition
$(X_{\textsf{one}},X_{\textsf{two}})$.

As no arc of infinite weight exists in the cut, we note that that
$(X_{\textsf{one}},X_{\textsf{two}})$ is a Nash equilibrium. We will now show
that the welfare of $(X_{\textsf{one}},X_{\textsf{two}})$ is
$w(X_{\textsf{one}},X_{\textsf{two}})=2|E(G)|-|E(A,B)|-w(S,T)$. If $sa_{i}$
belongs to the cut then all arcs in $C_{i}^{A}$ contribute zero to the welfare
and zero to the formula for $w(X_{\textsf{one}},X_{\textsf{two}})$. If
$b_{j}t$ belongs to the cut then all arcs in $C_{j}^{B}$ contribute zero to
the welfare and zero to the formula for
$w(X_{\textsf{one}},X_{\textsf{two}})$. If $a_{i}b_{j}$ belongs to the cut
then all arcs in $E(C_{i}^{A},C_{j}^{B})$ contribute zero to the welfare and
zero to the formula for $w(X_{\textsf{one}},X_{\textsf{two}})$. All other arcs
contribute two to the welfare if both end-points lie in $A$ or both end-points
lie in $B$ and if exactly one end-point lies in $A$ and the other in $B$ then
the edge contributes one to the welfare. So the welfare of
$(X_{\textsf{one}},X_{\textsf{two}})$ is indeed
$w(X_{\textsf{one}},X_{\textsf{two}})=2|E(G)|-|E(A,B)|-w(S,T)$.

Conversely let $(Y_{\textsf{one}},Y_{\textsf{two}})$ be a Nash equilibrium of
maximum weight. We saw above that all vertices in $C_{i}^{A}$ belong to
$Y_{\textsf{one}}$ or to $Y_{\textsf{two}}$. If they belong to
$Y_{\textsf{one}}$, then let $a_{i}$ belong to $S$ and otherwise let $a_{i}$
belong to $T$. Analogously if all vertices of $C_{j}^{B}$ belong to
$Y_{\textsf{one}}$ then let $b_{j}$ belong to $S$ and otherwise let $b_{j}$
belong to $T$. Furthermore let $s$ belong to $S$ and $t$ belong to $T$, which
gives us a $(s,t)$-cut $(S,T)$. We will show that the weight of the cut,
$w(S,T)$, satisfies
$w(Y_{\textsf{one}},Y_{\textsf{two}})=2|E(G)|-|E(A,B)|-w(S,T)$, where
$w(Y_{\textsf{one}},Y_{\textsf{two}})$ is the welfare of
$(Y_{\textsf{one}},Y_{\textsf{two}})$. As
$(Y_{\textsf{one}},Y_{\textsf{two}})$ is exactly the Nash equilibrium we
obtained above if we had started with $(S,T)$, we note that
$w(Y_{\textsf{one}},Y_{\textsf{two}})=2|E(G)|-|E(A,B)|-w(S,T)$ indeed holds.

Therefore, if the maximum welfare Nash equilibrium has welfare ${\rm
wel}^{opt}$ and the minimum weight $(s,t)$-cut has weight ${\rm cut}^{opt}$
then ${\rm wel}^{opt}=2|E(G)|-|E(A,B)|-{\rm cut}^{opt}$. As we can find a
minimum $(s,t)$-cut in polynomial time Korte and Vygen [2011], this gives us a
polynomial time algorithm for finding a maximum welfare Nash equilibrium when
$\gamma_{A}=1$ and $\gamma_{B}=0$. So we are done.

##  Appendix D Proving Case 4 of Theorem 11

Recall that it suffices to prove the theorem for
$0<\gamma_{B}<1/2<\gamma_{A}\leq 1$. Thus it is enough to prove Theorem 23
below.

We will start with two useful lemmas.

######  Lemma 20.

Let $\gamma_{A}$ be any real such that $1/2<\gamma_{A}\leq 1$. Let $G$ be the
complete graph with $a\geq 2$ vertices of type A (and no vertices of type B).
The maximum welfare is obtained when all players choose action one.
Furthermore, if $(X_{\textsf{one}},X_{\textsf{two}})\not=(V(G),\emptyset)$
then the welfare is at least
$\min\\{2\gamma_{A}(a-1),a(a-1)(2\gamma_{A}-1)\\}$ less than the optimum.

Proof: Define $G$ as in the statement. Assume that
$(X_{\textsf{one}},X_{\textsf{two}})$ is a partition of $V(G)$. The welfare of
this partition is denoted by $w(X_{\textsf{one}},X_{\textsf{two}})$. First
assume that $(X_{\textsf{one}},X_{\textsf{two}})\not=(V(G),\emptyset)$. Then
the following holds, where $q=|X_{\textsf{two}}|$,

$\begin{array}[]{rcl}w(V(G),\emptyset)-w(X_{\textsf{one}},X_{\textsf{two}})&=&{|X_{\textsf{two}}|\choose
2}(2\gamma_{A})+|X_{\textsf{one}}|\cdot|X_{\textsf{two}}|(2\gamma_{A})-{|X_{\textsf{two}}|\choose
2}(2(1-\gamma_{A}))\\\
&=&q(q-1)(\gamma_{A}-(1-\gamma_{A}))+2(a-q)q\gamma_{A}\\\
&=&q\left((q-1)(2\gamma_{A}-1)+2a\gamma_{A}-2q\gamma_{A}\right)\\\
&=&q\left(2q\gamma_{A}-q-2\gamma_{A}+1+2a\gamma_{A}-2q\gamma_{A}\right)\\\
&=&q\left(2\gamma_{A}(a-1)-q+1\right)\\\ \end{array}$

Consider the function $f(q)=q\left(2\gamma_{A}(a-1)-q+1\right)$ and note that
$f^{\prime}(q)=-2q+2\gamma_{A}(a-1)+1$, which implies that the minimum value
of $f(q)$ in any interval is found in one of its endpoints. As $1\leq q\leq a$
the minimum value of $f(q)$ is therefore $f(1)$ or $f(a)$, which implies the
following.

$w(V(G),\emptyset)-w(X_{\textsf{one}},X_{\textsf{two}})\geq\min\\{f(1),f(a)\\}=\min\\{2\gamma_{A}(a-1),a(a-1)(2\gamma_{A}-1)\\}$

As the above minimum is positive, we note that if
$(X_{\textsf{one}},X_{\textsf{two}})\not=(V(G),\emptyset)$ then
$(X_{\textsf{one}},X_{\textsf{two}})$ does not obtain the maximum welfare, so
the maximum welfare is obtained when all players choose action one.
Furthermore, if $(X_{\textsf{one}},X_{\textsf{two}})\not=(V(G),\emptyset)$
then the welfare is at least
$\min\\{2\gamma_{A}(a-1),a(a-1)(2\gamma_{A}-1)\\}$ less than the optimum as
seen above. ∎

######  Corollary 21.

Let $\gamma_{B}$ be any real such that $0\leq\gamma_{B}<1/2$. Let $G$ be the
complete graph with $b\geq 2$ vertices of type B (and no vertices of type A).
The maximum welfare is obtained when all players choose action two and if
$(X_{\textsf{one}},X_{\textsf{two}})\not=(\emptyset,V(G))$ then the welfare is
at least $\min\\{2(1-\gamma_{B})(b-1),b(b-1)(1-2\gamma_{B})\\}$ less than the
optimum.

Proof: By replacing action two with one and vice versa and letting
$\gamma_{B}^{new}=1-\gamma_{B}$ then we obtain an equivalent problem. The
following now completes the proof, by Lemma 20,

$\min\\{2\gamma_{B}^{new}(b-1),b(b-1)(2\gamma_{B}^{new}-1)\\}=\min\\{2(1-\gamma_{B})(b-1),b(b-1)(1-2\gamma_{B})\\}$

∎

######  Lemma 22.

Let $\gamma_{A}$ and $\gamma_{B}$ be given rationals, such that
$0<\gamma_{B}\leq 1/2\leq\gamma_{A}\leq 1$. Let $G$ be any graph and let
$(A,B)$ be a partition of $V(G)$. The partition
$(X_{\textsf{one}},X_{\textsf{two}})$ is a Nash equilibrium if and only if the
following holds for all $u\in V(G)$.

  * •

For every vertex $u\in X_{\textsf{one}}\cap A$ we have $N(u)\cap
X_{\textsf{two}}=\emptyset$ or $\frac{|N(u)\cap X_{\textsf{one}}|}{|N(u)\cap
X_{\textsf{two}}|}\geq\frac{1-\gamma_{A}}{\gamma_{A}}$.

  * •

For every vertex $u\in X_{\textsf{two}}\cap A$ we have $N(u)\cap
X_{\textsf{one}}=\emptyset$ or $\frac{|N(u)\cap X_{\textsf{two}}|}{|N(u)\cap
X_{\textsf{one}}|}\geq\frac{\gamma_{A}}{1-\gamma_{A}}$.

  * •

For every vertex $u\in X_{\textsf{one}}\cap B$ we have $N(u)\cap
X_{\textsf{two}}=\emptyset$ or $\frac{|N(u)\cap X_{\textsf{one}}|}{|N(u)\cap
X_{\textsf{two}}|}\geq\frac{1-\gamma_{B}}{\gamma_{B}}$.

  * •

For every vertex $u\in X_{\textsf{two}}\cap B$ we have $N(u)\cap
X_{\textsf{one}}=\emptyset$ or $\frac{|N(u)\cap X_{\textsf{two}}|}{|N(u)\cap
X_{\textsf{one}}|}\geq\frac{\gamma_{B}}{1-\gamma_{B}}$.

Proof: Let $(X_{\textsf{one}},X_{\textsf{two}})$ be a partition of $V(G)$. Let
$u\in X_{\textsf{one}}\cap A$ be arbitrary. If we move $u$ from
$X_{\textsf{one}}$ to $X_{\textsf{two}}$ then $u$’s gain is $|N(u)\cap
X_{\textsf{two}}|(1-\gamma_{A})-|N(u)\cap X_{\textsf{one}}|\gamma_{A}$. This
gain is greater than zero if $\frac{|N(u)\cap X_{\textsf{one}}|}{|N(u)\cap
X_{\textsf{two}}|}<\frac{1-\gamma_{A}}{\gamma_{A}}$, so $u$ satisfies the Nash
equilibrium property if and only if $N(u)\cap X_{\textsf{two}}=\emptyset$ or
$\frac{|N(u)\cap X_{\textsf{one}}|}{|N(u)\cap
X_{\textsf{two}}|}\geq\frac{1-\gamma_{A}}{\gamma_{A}}$.

Now let $u\in X_{\textsf{two}}\cap A$ be arbitrary. If we move $u$ from
$X_{\textsf{two}}$ to $X_{\textsf{one}}$ then $u$’s gain is $|N(u)\cap
X_{\textsf{one}}|\gamma_{A}-|N(u)\cap X_{\textsf{two}}|(1-\gamma_{A})$. This
gain is greater than zero if $\frac{|N(u)\cap X_{\textsf{two}}|}{|N(u)\cap
X_{\textsf{one}}|}<\frac{\gamma_{A}}{1-\gamma_{A}}$, so $u$ satisfies the Nash
equilibrium property if and only if $N(u)\cap X_{\textsf{one}}=\emptyset$ or
$\frac{|N(u)\cap X_{\textsf{two}}|}{|N(u)\cap
X_{\textsf{one}}|}\geq\frac{\gamma_{A}}{1-\gamma_{A}}$.

Now let $u\in X_{\textsf{one}}\cap B$ be arbitrary. If we move $u$ from
$X_{\textsf{one}}$ to $X_{\textsf{two}}$ then $u$’s gain is $|N(u)\cap
X_{\textsf{two}}|(1-\gamma_{B})-|N(u)\cap X_{\textsf{one}}|\gamma_{B}$. This
gain is greater than zero if $\frac{|N(u)\cap X_{\textsf{one}}|}{|N(u)\cap
X_{\textsf{two}}|}<\frac{1-\gamma_{B}}{\gamma_{B}}$, so $u$ satisfies the Nash
equilibrium property if and only if $N(u)\cap X_{\textsf{two}}=\emptyset$ or
$\frac{|N(u)\cap X_{\textsf{one}}|}{|N(u)\cap
X_{\textsf{two}}|}\geq\frac{1-\gamma_{B}}{\gamma_{B}}$.

Now let $u\in X_{\textsf{two}}\cap B$ be arbitrary. If we move $u$ from
$X_{\textsf{two}}$ to $X_{\textsf{one}}$ then $u$’s gain is $|N(u)\cap
X_{\textsf{one}}|\gamma_{B}-|N(u)\cap X_{\textsf{two}}|(1-\gamma_{B})$. This
gain is greater than zero if $\frac{|N(u)\cap X_{\textsf{two}}|}{|N(u)\cap
X_{\textsf{one}}|}<\frac{\gamma_{B}}{1-\gamma_{B}}$, so $u$ satisfies the Nash
equilibrium property if and only if $N(u)\cap X_{\textsf{one}}=\emptyset$ or
$\frac{|N(u)\cap X_{\textsf{two}}|}{|N(u)\cap
X_{\textsf{one}}|}\geq\frac{\gamma_{B}}{1-\gamma_{B}}$. ∎

######  Theorem 23.

Let $\gamma_{A}$ and $\gamma_{B}$ be reals such that
$0<\gamma_{B}<1/2<\gamma_{A}\leq 1$. Then it is NP-hard to find a maximum
welfare Nash equilibrium.

Proof: We will show the NP-hardness result via a reduction from Minimum
Traversal problem in $3$-uniform hypergraphs, which is known to be NP-hard
Garey and Johnson [1979]. A $3$-uniform hypergraph $H$ has a set of vertices
$V(H)$ and a set of hyperedges $E(H)$, where every edge $e\in E(H)$ is a
subset of vertices of size exactly $3$. A traversal of $H$ is a set of
vertices $X$ such that $X\cap e\neq\emptyset$ for every edge $e\in E(H)$.
Minimum Traversal problem asks to find a traversal of the minimum size.

Let $H$ be a $3$-uniform hypergraph where we want to find a minimum
transversal. Let $\gamma_{A}$ and $\gamma_{B}$ be given reals, such that
$0<\gamma_{B}<1/2<\gamma_{A}\leq 1$. We first define the following constants.

(a):

Let $\theta=6|E(H)|+2|V(H)|\lceil
3|E(H)|\frac{1-\gamma_{B}}{\gamma_{B}(1-2\gamma_{B})}\rceil$.

(b):

Let $x_{B}$ be the smallest possible positive integer such that
$x_{B}(1-\gamma_{B})(\gamma_{A}-\gamma_{B})/\gamma_{B}>\theta$.

(c):

Let $x_{A}$ be any integer such that the following holds (which is possible as
$1/\gamma_{B}>1$ (in fact, $1/\gamma_{B}>2$).

$(x_{B}+3)\frac{1-\gamma_{B}}{\gamma_{B}}-\frac{1}{\gamma_{B}}<x_{A}<(x_{B}+3)\frac{1-\gamma_{B}}{\gamma_{B}}$

(d):

Let $c_{A}$ be the smallest possible integer such that $c_{A}\geq x_{A}$ and
$(c_{A}-1)(2\gamma_{A}-1)>\theta+2|E(H)|\cdot(x_{A}+x_{B})$.

(e):

Let $c_{B}$ be the smallest possible integer such that $c_{B}\geq x_{B}$ and
$(c_{B}-1)(1-2\gamma_{B})>\theta+2|E(H)|\cdot(x_{A}+x_{B})$ and
$\frac{c_{B}-1}{|E(H)|}\geq\frac{\gamma_{B}}{1-\gamma_{B}}$.

(f):

Let $z=\lceil 3|E(H)|\frac{1-\gamma_{B}}{\gamma_{B}(1-2\gamma_{B})}\rceil$.
Note that $\theta=6|E(H)|+2z|V(H)|$.

We will now construct a graph $G$ and a partition $(A,B)$ of $V(G)$ such that
a solution to our problem for $G$ will give us a minimum transversal in $H$.
For an illustration, see Fig. 3.

Let $C_{A}$ and $C_{B}$ be cliques, such that $|C_{A}|=c_{a}$ and
$|C_{B}|=c_{b}$ (see (d) and (e)). For each edge $e\in E(H)$, let $r_{e}$ be a
vertex and let $R=\cup_{e\in E(H)}\\{r_{e}\\}$. For each edge $u\in E(H)$, let
$u^{\prime}$ be a vertex and let $V^{\prime}=\cup_{u\in
V(H)}\\{u^{\prime}\\}$. Furthermore let $Z_{u}$ denote a set of $z$ vertices
and let $Z=\cup_{u\in V(H)}Z_{u}$. We will now let $V(G)=V(C_{A})\cup
V(C_{B})\cup R\cup V^{\prime}\cup Z$.

Let $E_{1}$ denote the edges in $C_{A}\cup C_{B}$. For every vertex $r_{e}\in
R$ add $x_{A}$ edges to $C_{A}$ and add $x_{B}$ vertices to $C_{B}$. Let
$E_{2}$ denote these edges. For every $e\in E(H)$ add an edge from $r_{e}$ to
$u^{\prime}$ if and only if $u\in V(e)$ in $H$. Let $E_{3}$ denote these
edges. For every $u\in V(H)$ add all edges between $u^{\prime}$ and $Z_{u}$ to
$G$. Let $E_{4}$ denote these edges. Note that $|E_{4}|=|V(H)|\cdot
z=|V(H)|\lceil 3|E(H)|\frac{1-\gamma_{B}}{\gamma_{B}(1-2\gamma_{B})}\rceil$
(by (f)). This completes the description of $G$ and note that $E(G)=E_{1}\cup
E_{2}\cup E_{3}\cup E_{4}$.

Note that by (a)-(f) above all values of $\theta$, $x_{B}$, $x_{A}$, $c_{A}$,
$c_{B}$ and $z$ are polynomial in $|V(H)|+|E(H)|$ (as $\gamma_{A}$ and
$\gamma_{B}$ are considered constant). Therefore, $|V(G)|$ is also a
polynomial in $|V(H)|+|E(H)|$. Let all vertices in $C_{A}$ belong to $A$ and
all other vertices belong to $B$. That is $B=V(C_{B})\cup R\cup V^{\prime}\cup
Z$. This completes the definition of the partition $(A,B)$ of $V(G)$.

$C_{A}$$C_{B}$$r_{e_{1}}$$r_{e_{2}}$$r_{e_{3}}$$\cdots$$r_{e_{m}}$$u_{1}^{\prime}$$u_{2}^{\prime}$$u_{3}^{\prime}$$u_{4}^{\prime}$$\cdots$$u_{n}^{\prime}$$Z_{u_{1}^{\prime}}$$Z_{u_{2}^{\prime}}$$Z_{u_{3}^{\prime}}$$Z_{u_{4}^{\prime}}$$Z_{u_{n}^{\prime}}$
Figure 3: The graph $G$ when $H$ is a $3$-uniform hypergraph with $m$ edges,
including the edges $e_{1}=\\{u_{1},u_{2},u_{3}\\}$ and
$e_{2}=\\{u_{1},u_{3},u_{4}\\}$. The square vertices in $C_{A}$ denotes
A-vertices and round vertices (everywhere else) denote B-vertices.
Furthermore, the thick edges between $u_{i}$ and $Z_{u_{i}}$ denotes that all
edges are present.

We will show that a welfare optimizing Nash equilibrium for $G$ gives us a
minimum transversal for $H$, thereby proving the desired NP-hardness result.
Assume we have a partition $(X_{\textsf{one}},X_{\textsf{two}})$ of $V(G)$
(where all players in $X_{\textsf{one}}$ choose action one and all players in
$X_{\textsf{two}}$ choose action two).

For every edge $uv\in G$ let the weight $w(uv)$ of $uv$ be the increase in
welfare achieved because of that edge. That is, the following holds.

$w(uv)=\left\\{\begin{array}[]{rclcl}2\gamma_{A}&&\mbox{if $u,v\in
X_{\textsf{one}}$ and $u,v\in A$}\\\ 2\gamma_{B}&&\mbox{if $u,v\in
X_{\textsf{one}}$ and $u,v\in B$}\\\ \gamma_{A}+\gamma_{B}&&\mbox{if $u,v\in
X_{\textsf{one}}$ and $|\\{u,v\\}\cap A|=1$}\\\ 2(1-\gamma_{A})&&\mbox{if
$u,v\in X_{\textsf{two}}$ and $u,v\in A$}\\\ 2(1-\gamma_{B})&&\mbox{if $u,v\in
X_{\textsf{two}}$ and $u,v\in B$}\\\ 2-\gamma_{A}-\gamma_{B}&&\mbox{if $u,v\in
X_{\textsf{two}}$ and $|\\{u,v\\}\cap A|=1$}\\\ 0&&otherwise\\\
\end{array}\right.$

Define $W^{*}$ be the the value of the optimal welfare of $G-E_{3}-E_{4}$. We
will now prove the following claims.

Claim A: The optimal welfare of $G-E_{3}-E_{4}$ (with value $W^{*}$) is
obtained for the partition $(X_{\textsf{one}},X_{\textsf{two}})$ if, and only
if, the following holds.

(A)

$V(C_{A})\cup R\subseteq X_{\textsf{one}}$ and $V(C_{B})\subseteq
X_{\textsf{two}}$.

Furthermore any partition that does not satisfy (A) above will have welfare at
most $W^{*}-\theta$ (see (a)).

Proof of Claim A: Let $C^{+}$ be the component of $G-E_{3}-E_{4}$ containing
the vertices $V(C_{A})\cup V(C_{B})\cup R$. Let $W^{+}$ be the value of the
welfare for $C^{+}$ for the partition $(V(C_{A})\cup R,V(C_{B}))$ and let
$(X_{\textsf{one}},X_{\textsf{two}})$ be any partition $G-E_{3}-E_{4}$. Let
$W_{A}^{+}$ be the optimal welfare for $C_{A}$ and let $W_{B}^{+}$ be the
optimal welfare for $C_{B}$.

Note that
$\min\\{2\gamma_{A}(c_{A}-1),c_{A}(c_{A}-1)(2\gamma_{A}-1)\\}\geq(c_{A}-1)(2\gamma_{A}-1)$
as $2\gamma_{A}>1\geq 2\gamma_{A}-1$. By Lemma 20 we note that if
$V(C_{A})\not\subseteq X_{\textsf{one}}$ then the welfare of $C_{A}$ is at
most the following (by (d)):

$\begin{array}[]{rcl}W_{A}^{+}-\min\\{2\gamma_{A}(c_{A}-1),c_{A}(c_{A}-1)(2\gamma_{A}-1)\\}&\leq&W_{A}^{+}-(c_{A}-1)(2\gamma_{A}-1)\\\
&<&W_{A}^{+}-(\theta+2|E(H)|\cdot(x_{A}+x_{B}))\\\ \end{array}$

Analogously, by Corollary 21 and (e) we note that if $V(C_{B})\not\subseteq
X_{\textsf{two}}$ then the welfare of $C_{B}$ is at most the following:

$\begin{array}[]{rcl}W_{B}^{+}-\min\\{2(1-\gamma_{B})(c_{B}-1),c_{B}(c_{B}-1)(1-2\gamma_{B})\\}&\leq&W_{B}^{+}-(c_{B}-1)(1-2\gamma_{B})\\\
&<&W_{B}^{+}-(\theta+2|E(H)|\cdot(x_{A}+x_{B}))\\\ \end{array}$

As the maximum welfare we can obtain from the edges in $E_{2}$ is not more
than $2|E(H)|\cdot(x_{A}+x_{B})$ we note that if $V(C_{A})\not\subseteq
X_{\textsf{one}}$ or $V(C_{B})\not\subseteq X_{\textsf{two}}$ then the welfare
of $(X_{\textsf{one}},X_{\textsf{two}})$ is at least $\theta$ less than
$W_{A}^{+}+W_{B}^{+}$ and therefore also at least $\theta$ less than $W^{*}$.
So we may assume that $V(C_{A})\subseteq X_{\textsf{one}}$ and
$V(C_{B})\subseteq X_{\textsf{two}}$.

Let $r_{e}\in R$ be arbitrary and assume that $r_{e}\in X_{\textsf{two}}$. By
moving $r_{e}$ to $X_{\textsf{one}}$ we would increase the welfare of
$G-E_{3}-E_{4}$ by $x_{A}(\gamma_{A}+\gamma_{B})-x_{B}(2(1-\gamma_{B}))$. By
(c) we note that
$(x_{B}+3)\frac{1-\gamma_{B}}{\gamma_{B}}-\frac{1}{\gamma_{B}}<x_{A}$, which
implies the following (by (b)):

$\begin{array}[]{rcl}x_{A}(\gamma_{A}+\gamma_{B})-x_{B}(2(1-\gamma_{B}))&\geq&\left((x_{B}+3)\frac{1-\gamma_{B}}{\gamma_{B}}-\frac{1}{\gamma_{B}}\right)(\gamma_{A}+\gamma_{B})-2x_{B}(1-\gamma_{B}))\\\
&=&x_{B}\left(\frac{1-\gamma_{B}}{\gamma_{B}}(\gamma_{A}+\gamma_{B})-2(1-\gamma_{B}))\right)+\left(3\frac{1-\gamma_{B}}{\gamma_{B}}-\frac{1}{\gamma_{B}}\right)(\gamma_{A}+\gamma_{B})\\\
&=&x_{B}(1-\gamma_{B})\left(\frac{\gamma_{A}+\gamma_{B}}{\gamma_{B}}-2\right)+\left(\frac{2-3\gamma_{B}}{\gamma_{B}}\right)(\gamma_{A}+\gamma_{B})\\\
&\geq&x_{B}(1-\gamma_{B})\left(\frac{\gamma_{A}-\gamma_{B}}{\gamma_{B}}\right)\\\
&>&\theta\\\ \end{array}$

This completes the proof of Claim A.

Claim B: Let $(X_{\textsf{one}},X_{\textsf{two}})$ be any Nash equilibrium of
$G$ that satisfies condition (A) in Claim A, then condition (B) below holds.

(B)

For every $e\in E(H)$ the vertex $r_{e}$ has a neighbour in $V^{\prime}\cap
X_{\textsf{one}}$.

Proof of Claim B: Recall that by (A) in Claim A we have $V(C_{A})\cup
R\subseteq X_{\textsf{one}}$ and $V(C_{B})\subseteq X_{\textsf{two}}$. For the
sake of contradiction assume that there exists a $r_{e}\in R$ such that all
three neighbours of $r_{e}$ in $V^{\prime}$ belong to $X_{\textsf{two}}$. We
will now show that $r_{e}$ does not satisfy the Nash equilibrium property.

The vertex $r_{e}$ currently has $x_{A}$ neighbours in $X_{\textsf{one}}$ and
$x_{B}+3$ neighbours in $X_{\textsf{two}}$. So its current welfare is
$x_{A}\gamma_{B}$, but if we move $r_{e}$ to $X_{\textsf{two}}$ then its
welfare will become $(x_{B}+3)(1-\gamma_{B})$. By (c), the following holds.

$(x_{B}+3)(1-\gamma_{B})-x_{A}\gamma_{B}>(x_{B}+3)(1-\gamma_{B})-\left((x_{B}+3)\frac{1-\gamma_{B}}{\gamma_{B}}\right)\gamma_{B}=0$

So, $r_{e}$ does not satisfy the Nash equilibrium property, a contradiction.
This completes the proof of Claim B.

Claim C: Let $(X_{\textsf{one}},X_{\textsf{two}})$ be any partition of $V(G)$
that satisfies condition (A) in Claim A, condition (B) in Claim B and
condition (C) below. Then $(X_{\textsf{one}},X_{\textsf{two}})$ is a Nash
equilibrium.

(C)

For every $u\in V(H)$, either $\\{u^{\prime}\\}\cup Z_{u}\subseteq
X_{\textsf{one}}$ or $\\{u^{\prime}\\}\cup Z_{u}\subseteq X_{\textsf{two}}$.

Proof of Claim C: As vertices in $Z$ are only adjacent to vertices in the same
partite set in $(X_{\textsf{one}},X_{\textsf{two}})$ as themselves they do
satisfy the Nash equilibrium condition. By Lemma 22 we therefore need to show
that the following holds for all $v_{A}\in V(C_{A})$ and all $v_{B}\in
V(C_{B})$ and all $r_{e}\in R$ and all $u^{\prime}\in V^{\prime}$ and all
$z\in Z$.

  * •

$\frac{|N(v_{A})\cap X_{\textsf{one}}|}{|N(v_{A})\cap
X_{\textsf{two}}|}\geq\frac{1-\gamma_{A}}{\gamma_{A}}$ or $N(v_{A})\cap
X_{\textsf{two}}=\emptyset$ (as $v_{A}\in A\cap X_{\textsf{one}}$).

  * •

$\frac{|N(v_{B})\cap X_{\textsf{two}}|}{|N(v_{B})\cap
X_{\textsf{one}}|}\geq\frac{\gamma_{B}}{1-\gamma_{B}}$ or $N(v_{B})\cap
X_{\textsf{one}}=\emptyset$ (as $v_{B}\in B\cap X_{\textsf{two}}$).

  * •

$\frac{|N(r_{e})\cap X_{\textsf{one}}|}{|N(r_{e})\cap
X_{\textsf{two}}|}\geq\frac{1-\gamma_{B}}{\gamma_{B}}$ or $N(r_{e})\cap
X_{\textsf{two}}=\emptyset$ (as $r_{e}\in B\cap X_{\textsf{one}}$).

  * •

If $u^{\prime}\in X_{\textsf{one}}$, then $\frac{|N(u^{\prime})\cap
X_{\textsf{one}}|}{|N(u^{\prime})\cap
X_{\textsf{two}}|}\geq\frac{1-\gamma_{B}}{\gamma_{B}}$ or $N(u^{\prime})\cap
X_{\textsf{two}}=\emptyset$ (as $u^{\prime}\in B\cap X_{\textsf{one}}$).

  * •

If $u^{\prime}\in X_{\textsf{two}}$, then $\frac{|N(u^{\prime})\cap
X_{\textsf{two}}|}{|N(u^{\prime})\cap
X_{\textsf{one}}|}\geq\frac{\gamma_{B}}{1-\gamma_{B}}$ or $N(u^{\prime})\cap
X_{\textsf{one}}=\emptyset$ (as $u^{\prime}\in B\cap X_{\textsf{two}}$).

The first equation holds as $N(v_{A})\cap X_{\textsf{two}}=\emptyset$. The
second equation holds, due to the following (see (e)):

$\frac{|N(v_{B})\cap X_{\textsf{two}}|}{|N(v_{B})\cap
X_{\textsf{one}}|}\geq\frac{|V(C_{B})|-1}{|E(H)|}\geq\frac{\gamma_{B}}{1-\gamma_{B}}$

The third equation holds because of the following (see (c)):

$\begin{array}[]{rcl}\frac{|N(r_{e})\cap X_{\textsf{one}}|}{|N(r_{e})\cap
X_{\textsf{two}}|}&\geq&\frac{x_{A}+1}{x_{B}+2}\\\
&>&\frac{(x_{B}+3)\frac{1-\gamma_{B}}{\gamma_{B}}-\frac{1}{\gamma_{B}}+1}{x_{B}+2}\\\
&=&\frac{(x_{B}+3)(1-\gamma_{B})-1+\gamma_{B}}{\gamma_{B}(x_{B}+2)}\\\
&=&\frac{1-\gamma_{B}}{\gamma_{B}}\\\ \end{array}$

If $u^{\prime}\in V^{\prime}\cap X_{\textsf{one}}$ then all neighbours of
$u^{\prime}$ belong to $X_{\textsf{one}}$, so $N(u^{\prime})\cap
X_{\textsf{two}}=\emptyset$, which satisfies the fourth equation. Let
$u^{\prime}\in V^{\prime}\cap X_{\textsf{two}}$ be arbitrary. By (f) we note
that the following holds (as $\gamma_{B}<1/2$).

$z=\lceil
3|E(H)|\frac{1-\gamma_{B}}{\gamma_{B}(1-2\gamma_{B})}\rceil>|E(H)|\frac{\gamma_{B}}{1-\gamma_{B}}+1$

The fifth equation now holds because of the following:

$\frac{|N(u^{\prime})\cap X_{\textsf{two}}|}{|N(u^{\prime})\cap
X_{\textsf{one}}|}\geq\frac{z-1}{|E(H)|}>\frac{\gamma_{B}}{1-\gamma_{B}}$

This completes the proof of Claim C.

Let $T$ be any transversal of $H$. Define a partition
$(X_{\textsf{one}},X_{\textsf{two}})$ of $V(G)$ as follows. For every $u\in T$
let $V(Z_{u})\cup\\{u^{\prime}\\}$ belong to $X_{\textsf{one}}$ and for every
$u\in V(H)\setminus T$ let $V(Z_{u})\cup\\{u^{\prime}\\}$ belong to
$X_{\textsf{two}}$. Then add $V(C_{A})\cup R$ to $X_{\textsf{one}}$ and add
$V(C_{B})$ to $X_{\textsf{two}}$. We call this the $G$-extension of $T$.

Claim D: The $G$-extension of $T$ is a Nash equilibrium with the following
welfare, where $\epsilon_{T}$ is some value satisfying
$0\leq\epsilon_{T}<2z(1-2\gamma_{B})$.

$W^{*}+\epsilon_{T}+|V(H)|\cdot z(2(1-\gamma_{B}))-|T|\cdot 2z(1-2\gamma_{B})$

Proof of Claim D: Let $(X_{\textsf{one}},X_{\textsf{two}})$ be the
$G$-extension of a transversal $T$ in $H$. As conditions (A), (B) and (C) are
all satisfied in Claims A, B and C, respectively we note that by Claim C
$(X_{\textsf{one}},X_{\textsf{two}})$ is a Nash equilibrium.

By Claim A we note that $E_{1}\cup E_{2}$ contribute $W^{*}$ towards the
welfare of $(X_{\textsf{one}},X_{\textsf{two}})$. Let $\epsilon_{T}$ be the
welfare that the edges $E_{3}$ contribute and note that $0\leq\epsilon_{T}\leq
2|E_{3}|=6|E(H)|$. By (f), $z=\lceil
3|E(H)|\frac{1-\gamma_{B}}{\gamma_{B}(1-2\gamma_{B})}\rceil>\frac{3|E(H)|}{1-2\gamma_{B}}$,
which implies that $0\leq\epsilon_{T}\leq 6|E(H)|<2z(1-2\gamma_{B})$.

We will now compute the contribution to the welfare from the edges in $E_{4}$.
Let $u^{\prime}\in V^{\prime}$ be arbitrary. If $u^{\prime}\in
X_{\textsf{one}}$ then the edge between $u^{\prime}$ and $Z_{u}$ contribute
$z(2\gamma_{B})$ to the welfare. If $u^{\prime}\in X_{\textsf{two}}$ then the
edge between $u^{\prime}$ and $Z_{u}$ contribute $z(2(1-\gamma_{B}))$ to the
welfare. As there are $|T|$ vertices in $X_{\textsf{one}}\cap V^{\prime}$ we
therefore get the following welfare of $(X_{\textsf{one}},X_{\textsf{two}})$.

$W^{*}+\epsilon_{T}+(|V(H)|-|T|)\cdot z(2(1-\gamma_{B}))+|T|\cdot
2z\gamma_{B}=W^{*}+\epsilon_{T}+|V(H)|\cdot z(2(1-\gamma_{B}))-|T|\cdot
2z(1-2\gamma_{B})$

This completes the proof of Claim D.

Claim E: If we can find the welfare optimum Nash equilibrium of $G$ then we
can find the minimum transversal in $H$. This implies that finding the welfare
optimum Nash equilibrium for $\gamma_{A}$ and $\gamma_{B}$ is NP-hard.

Proof of Claim E: Assume that
$(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})$ is a welfare optimal Nash
equilibrium of $G$ and let $w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})$
be the welfare of $(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})$. Let
$T^{opt}$ be a minimum transversal of $H$. We will show that the following
holds, which completes the proof of Claim E.

$|T^{opt}|=\left\lceil\frac{W^{*}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})}{2z(1-2\gamma_{B})}\right\rceil$

Let $(X_{\textsf{one}},X_{\textsf{two}})$ be the $G$-extension of $T^{opt}$,
and note that, by Claim D, $(X_{\textsf{one}},X_{\textsf{two}})$ is a Nash
equilibrium satisfying the following, where
$0\leq\epsilon_{T^{opt}}<2z(1-2\gamma_{B})$.

$W(X_{\textsf{one}},X_{\textsf{two}})=W^{*}+\epsilon_{T^{opt}}+|V(H)|\cdot
z(2-2\gamma_{B}))-|T^{opt}|\cdot 2z(1-2\gamma_{B})$

This implies the following as $\epsilon_{T^{opt}}<2z(1-2\gamma_{B})$ and
$w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})\geq
w(X_{\textsf{one}},X_{\textsf{two}})$.

$\begin{array}[]{rcl}\vspace{0.2cm}|T^{opt}|&=&\frac{W^{*}+\epsilon_{T^{opt}}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{\textsf{one}},X_{\textsf{two}})}{2z(1-2\gamma_{B})}\\\
\vspace{0.2cm}\hfil&=&\left\lceil\frac{W^{*}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{\textsf{one}},X_{\textsf{two}})}{2z(1-2\gamma_{B})}\right\rceil\hskip
71.13188pt(*)\\\ &\geq&\left\lceil\frac{W^{*}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})}{2z(1-2\gamma_{B})}\right\rceil\\\
\end{array}$

By Claim D $w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})\geq
w(X_{\textsf{one}},X_{\textsf{two}})>W^{*}$. If conditions (A) in Claim A is
not satisfied for $(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})$ then by
Claim A the welfare of the edges $E_{1}\cup E_{2}$ is at most $W^{*}-\theta$.
This implies the following (by (f)).

$\begin{array}[]{rcl}w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})&\leq&W^{*}-\theta+2(|E_{3}|+|E_{4}|)\\\
&=&W^{*}-(6|E(H)|+2z|V(H)|)+2(3|E(H)|+z\cdot|V(H)|)\\\ &=&W^{*}\\\
\end{array}$

This contradiction implies that condition (A) in Claim A must be satisfied for
$(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})$. As
$(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})$ is a Nash equilibrium, Claim
B implies that condition (B) in Claim B holds.

Let $Y$ contain all vertices $u\in V(H)$ that satisfy $u^{\prime}\in
V^{\prime}\cap X_{\textsf{one}}$. By condition (B) in Claim B we note that $Y$
is a transversal in $H$. Let $(Y_{\textsf{one}},Y_{\textsf{two}})$ be the
$G$-extension of $Y$, and note that, by Claim D,
$(Y_{\textsf{one}},Y_{\textsf{two}})$ is a Nash equilibrium satisfying the
following, where $0\leq\epsilon_{Y}<2z(1-2\gamma_{B})$:

$w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})\geq
W(Y_{\textsf{one}},Y_{\textsf{two}})=W^{*}+\epsilon_{Y}+|V(H)|\cdot
z(2-2\gamma_{B}))-|Y|\cdot 2z(1-2\gamma_{B})$

This implies the following (as $\epsilon_{Y}<2z(1-2\gamma_{B})$),

$\begin{array}[]{rcl}\vspace{0.2cm}|T^{opt}|\;\leq\;|Y|&=&\frac{W^{*}+\epsilon_{Y}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})}{2z(1-2\gamma_{B})}\\\
&=&\left\lceil\frac{W^{*}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})}{2z(1-2\gamma_{B})}\right\rceil\\\
\end{array}$

By $(*)$ this implies that the following holds, which completes the proof of
Claim E and this theorem.

$|T^{opt}|=\left\lceil\frac{W^{*}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{\textsf{one}}^{opt},X_{\textsf{two}}^{opt})}{2z(1-2\gamma_{B})}\right\rceil$

∎

##  Appendix E Applications of MWDP in Graph Theory and Related Areas

Weighted Partition:

Given a digraph, $D$, find a partition $(X_{1},X_{2})$ of $V(D)$ such that the
following is maximized where $A(X,Y)$ denotes the set of arcs with tail in $X$
and head in $Y$ (where $a,b,c,d$ are given constants).

$a\cdot|A(X_{1},X_{1})|+b\cdot|A(X_{1},X_{2})|+c\cdot|A(X_{2},X_{1})|+d\cdot|A(X_{2},X_{2})|$

Equivalence to MWDP: Let $M={\small\left[\begin{array}[]{cc}a&b\\\ c&d\\\
\end{array}\right]}$ for every arc. This equivalence goes both ways so we have
a dichotomy for this problem.

Max Cut:

Given a graph, $G$, find a spanning bipartite subgraph of $G$ with the maximum
number of edges.

Equivalence to MWDP: Let $M={\small\left[\begin{array}[]{cc}0&1\\\ 1&0\\\
\end{array}\right]}$ for any orientation of each edge. This equivalence goes
both ways so our dichotomy for this problem implies this problem is NP-hard.

Directed Max Cut:

Given a digraph, $D$, find a partition $(X_{1},X_{2})$ of $V(D)$ with the
maximum number of arcs from $X_{1}$ to $X_{2}$.

Equivalence to MWDP: Let $M={\small\left[\begin{array}[]{cc}0&1\\\ 0&0\\\
\end{array}\right]}$ for every arc. This equivalence goes both ways so our
dichotomy for this problem implies this problem is NP-hard.

Closeness to Eulerian:

Given a digraph, $D$, find a partition $(X_{1},X_{2})$ of $V(D)$ where the
difference between the number of arcs from $X_{1}$ to $X_{2}$ and the number
of arcs from $X_{2}$ to $X_{1}$ is maximized. Note that this value is zero for
Eulerian digraphs.

This value can also be shown to be equal to the minimum number of paths that
need to be added to $D$ in order to make it Eulerian (so is the number of
paths the Chiness Postman Problem Algorithm adds).

Equivalence to MWDP: Let $M={\small\left[\begin{array}[]{cc}0&1\\\ -1&0\\\
\end{array}\right]}$ for every arc or if we do not allow negative values we
can add 1 to all values and get
$M^{\prime}={\small\left[\begin{array}[]{cc}1&2\\\ 0&1\\\
\end{array}\right]}$. This equvalence goes both ways so our dichotomy for this
problem implies this problem is polynomial.

Directed Min $(s,t)$-cut:

Given a digraph, $D$, with $s,t\in V(D)$, find a $(s,t)$-partition
$(X_{1},X_{2})$ (i.e., $s\in X_{1}$ and $t\in X_{2}$) with the fewest number
of arcs from $X_{1}$ to $X_{2}$.

This is equivalent to finding the largest number of arc-disjoint paths from
$s$ to $t$ (by Menger’s Theorem).

Equivalence to MWDP: Let $M={\small\left[\begin{array}[]{cc}1&0\\\ 1&1\\\
\end{array}\right]}$ and $S={\small\left[\begin{array}[]{cc}|E(G)|&0\\\ 0&0\\\
\end{array}\right]}$ and $T={\small\left[\begin{array}[]{cc}0&0\\\ 0&|E(G)|\\\
\end{array}\right]}$. All arcs of $D$ get associated with matrix $M$. We then
add a new vertex $s^{\prime}$ and the arc $s^{\prime}s$ which we associate
with matrix $S$. We also add a new vertex $t^{\prime}$ and the arc
$tt^{\prime}$ which we associate with matrix $T$. Now the maximum value we can
obtain is $3|A(D)|$ minus the size of a minimum $(s,t)$-cut. So by our
dichotomy result this is polynomial.

Min $(s,t)$-cut:

Given a graph, $G$, with $s,t\in V(G)$, find a $(s,t)$-partition
$(X_{1},X_{2})$ (ie $s\in X_{1}$ and $t\in X_{2}$) with the fewest number of
edges between $X_{1}$ and $X_{2}$.

This is equvalent to finding the fewest number of edge-disjoint paths between
$s$ and $t$ (by Menger’s Theorem).

Equivalence to MWDP: This follows from the directed min $(s,t)$-cut problem
(by replacing each edge by a directed $2$-cycle). But it can also be shown to
be polynomial directly using our dichotomy result by letting
$M={\small\left[\begin{array}[]{cc}1&0\\\ 0&1\\\ \end{array}\right]}$ and
$S={\small\left[\begin{array}[]{cc}|E(G)|&0\\\ 0&0\\\ \end{array}\right]}$ and
$T={\small\left[\begin{array}[]{cc}0&0\\\ 0&|E(G)|\\\ \end{array}\right]}$.

$2$-color-partition:

Given a $2$-edge-colored graph, $G$, find a partition $(X_{1},X_{2})$ which
maximizes the sum of the number of edges in $X_{1}$ of color one and the
number of edges in $X_{2}$ of color two.

Equivalence to MWDP: Let $M_{1}={\small\left[\begin{array}[]{cc}1&0\\\ 0&0\\\
\end{array}\right]}$ and let $M_{2}={\small\left[\begin{array}[]{cc}0&0\\\
0&1\\\ \end{array}\right]}$. By associating $M_{1}$ to any orientation of each
edge of color one and associating $M_{2}$ to any orientation of each edge of
color two we note that our dichotomy implies that this problem is polynomial.

Max Average Degree:

Given a graph, $G$, and an integer $k$, find a vertex set $X\subseteq V(G)$
such that the induced subgraph $G[X]$ has average degree strictly greater than
$k$.

Equivalence to MWDP: Let $M_{1}={\small\left[\begin{array}[]{cc}k&0\\\ 0&0\\\
\end{array}\right]}$ and let $M_{2}={\small\left[\begin{array}[]{cc}0&0\\\
0&2\\\ \end{array}\right]}$.

We will now create a digraph $D$ as follows. Initially let $D$ be any
orientation of $G$. Then, for each vertex $u\in V(G)$ add a new vertex,
$v_{u}$, and the arc $uv_{u}$ to $D$. This defines $D$. Note that
$|V(D)|=2|V(G)|$.

Associate $M_{1}$ to the arc $uv_{u}$ for all $u\in V(G)$. Associate $M_{2}$
to all other arcs of $D$.

Assume that $(X_{1},X_{2})$ is an arbitrary solution for $D$. We may assume
that $u$ and $v_{u}$ belong to the same set in $(X_{1},X_{2})$. Let
$W=V(G)\cap X_{2}$. Let $e(W,W)$ denote the number of edges in $G[W]$. Then
the welfare of $(X_{1},X_{2})$ is the following.

$w(X_{1},X_{2})=k|V(G)|-k|W|+2e(W,W)$

So $w(X_{1},X_{2})>k|V(G)|$ if and only if $2e(W,W)>k|W|$, which is equivalent
to $k<\frac{2e(W,W)}{|W|}$. As $2e(W,W)/|W|=(\sum_{u\in W}d_{G[W]}(u))/|W|$ we
note that the average degree in $G[W]$ is greater than $k$ if and only if
$w(X_{1},X_{2})>k|V(G)|$.

So, by our dichotomy, the Max average degree problem is polynomial.

Max Density:

Given a graph, $G$, find a vertex set $X\subseteq V(G)$ such that the number
of edges divided by the number of vertices in the induced subgraph $G[X]$ is
maximum possible.

Equivalence to MWDP: This is polynomial by the above result on the Max average
degree problem as $e(X,X)/|X|$ is maximum if and only if $2e(X,X)/|X|$ is
maximum.

$2$-color-difference:

We are given a edge-weighted $2$-edge-colored graph, $G$, where $w_{i}(X)$
denotes the weight of all edges in a vertex set $X$ of color $i$. Find a set
$X\subseteq V(G)$, which maximizes $w_{2}(X)-w_{1}(X)$.

Equivalence to MWDP: Let $M_{1}={\small\left[\begin{array}[]{cc}1&0\\\ 0&0\\\
\end{array}\right]}$ and let $M_{2}={\small\left[\begin{array}[]{cc}-1&0\\\
0&0\\\ \end{array}\right]}$.

Note that if we do not want negative weights in $M_{2}$ we can add 1 to all
entries without changing the problem (the value of the result just increases
by 1 for every arc associated with $M_{2}$).

Given a digraph $D$ where every arc, $uv$, is associated with a cost $c_{uv}$
and a matrix $M_{uv}\in\\{M_{1},M_{2}\\}$ we can reduce to an instance, $G$,
of $2$-color-difference as follows. Costs in $D$ become weights in $G$.

Let $G$ be the underlying graph of $D$ and for every arc $uv\in A(D)$ we color
$uv$ with color 2 in $G$ if $M_{uv}=M_{1}$ and we color $uv$ with color 1,
otherwise. Let $(X_{1},X_{2})$ be a solution for $D$. Then the weight of
$(X_{1},X_{2})$ in $D$ is the sum of all the costs of arcs in $X_{1}$
associated with $M_{1}$ minus the sum of the costs of arcs in $X_{1}$
associated with $M_{2}$. However this is exactly $w_{2}(X_{1})-w_{1}(X_{1})$
in $G$. Thus, an optimal solution for the 2-color-difference problem
corresponds to an optimal solution for MWDP($M_{1}$,$M_{2}$). Therefore, as
our reduction is polynomial, our dichotomy result shows that the 2-color-
difference problem is NP-hard.