#  Some coordination problems are harder than others

Argyrios Deligkas111Computer Science Department, Royal Holloway University of
London. Eduard Eiben222Computer Science Department, Royal Holloway University
of London. Gregory Gutin333Computer Science Department, Royal Holloway
University of London. Philip R. Neary444Economics Department, Royal Holloway
University of London. Anders Yeo555IMADA, University of Southern Denmark.
$\,{}^{,}$666Department of Mathematics, University of Johannesburg.

###### Abstract

In order to coordinate players in a game must first identify a target pattern
of behaviour. In this paper we investigate the difficulty of identifying
prominent outcomes in two kinds of binary action coordination problems in
social networks: pure coordination games and anti-coordination games. For both
environments, we determine the computational complexity of finding a strategy
profile that (i) maximises welfare, (ii) maximises welfare subject to being an
equilibrium, and (iii) maximises potential. We show that the complexity of
these objectives can vary with the type of coordination problem. Objectives
(i) and (iii) are tractable problems in pure coordination games, but for anti-
coordination games are NP-hard. Objective (ii), finding the “best” Nash
equilibrium, is NP-hard for both. Our results support the idea that
environments in which actions are strategic complements (e.g., technology
adoption) facilitate successful coordination more readily than those in which
actions are strategic substitutes (e.g., public good provision).

##### Keywords:

coordination problems; polymatrix games; potential and welfare maximisers;
complexity.

##  1 Introduction

###  1.1 Motivation

What exactly does it mean to say that a group of economic agents successfully
coordinated? Despite the frequency with which issues related to coordination
are discussed – just open any game theory journal – finding precise (i.e.,
mathematical) definitions is not so easy.

Let us spare the reader any suspense. We do not propose a formal definition of
what it means for economic agents “to coordinate” in this paper. That being
said, we contend that a key component of any such definition will be the
identification of a strategy profile (at least one) with certain properties.
While identification is not the whole story, it raises an obvious question:
given a coordination problem, is computing an outcome with certain properties
always tractable? If yes, then great. But if no, is it sensible to suppose
that economic agents, even those blessed with other-worldly levels of
rationality as is commonly presumed, can identify such an outcome in a
reasonable time frame? And if identifying a particular pattern of behaviour is
computationally challenging, ought it be viewed as a plausible prediction?

We focus on the two fundamental types of binary-action coordination problem in
social networks: pure coordination games, in which it is beneficial to act the
same as others (actions are strategic complements), and anti-coordination
games, where it pays to differentiate your behaviour from that of your
neighbours (actions are strategic substitutes). For both kinds of coordination
problem, we consider the computational complexity of identifying the following
three commonly-studied outcomes:

  1. (i)

a strategy profile that maximises welfare,

  2. (ii)

a welfare maximising Nash equilibrium, and

  3. (iii)

a strategy profile that maximises the potential (Shapley and Monderer, 1996).

The profile in (i) is that which a social planner might be expected to favour.
Unfortunately for a planner, such an outcome lacks the glue of equilibrium and
so is likely to unravel. For this reason we also consider the profile in (ii).
This describes a pattern of behaviour that a planner might view as optimal
subject to a stability requirement. The profile in (iii), when it exists,
describes the robust outcome in games of incomplete information (Ui, 2001;
Oyama and Takahashi, 2020) and that deemed the most likely long run outcome in
models of stochastic evolution (Blume, 1993; Young, 2001).777A potential
maximising outcome must be a pure strategy Nash equilibrium. It also possesses
other nice properties. For example, potential maximisers are uniquely
absorbing (Hofbauer and Sorger, 1999), select risk-dominant outcomes in games
on fixed networks (Peski, 2010) and games on random networks (Peski, 2021),
and can be useful for equilibrium refinements (Carbonell-Nicolau and McLean,
2014). Potential games appear frequently in applied work – 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)
– and the potential maximiser is often invoked as an ad hoc equilibrium
selection device.

Given two kinds of coordination problem and three strategy profiles of
interest, our goal is to classify the complexity of six different objects. The
main results, an overview of which is provided in Table 1 in Section 1.3, may
be summarised, in very broad strokes, as saying that the complexity of
identifying certain outcomes in pure coordination games is tractable whereas
for anti-coordination games it is not.

We are not the first to consider the complexity of finding outcomes in
strategic games.888A quick review of the literature is provided in Section
1.4. We focus on this issue in coordination problems for two reasons. The
first is to highlight a potential discrepancy in how difficult a game is for
players to understand as compared with how difficult it is to “solve”
conditional on understanding. That is, just because a game is uncomplicated
does not guarantee that playing it, let alone solving it, must be. While this
distinction is understood for some environments (e.g., board games), at least
in our opinion, the lines become blurred when it comes to coordination
problems. Perhaps nowhere is this more apparent than in the classic work of
Thomas Schelling (Schelling, 1960), who goes so far as to describe certain
equilibria as focal.999Not only can the set of candidate outcomes be
identified by one and all, but each individual notes that there is something
inherently salient about candidate outcome, correctly conjectures that others
have also noted this salience, correctly conjectures that others have
correctly conjectured that others have also noted this salience, and so on.
With everyone on the same page, each player then plays their part and the
focal equilibrium emerges. A discussion of which equilibrium the population is
most likely to end up at only holds water if the set of candidate outcomes is
in some sense obvious. And as we will show, this need not always be the case.
The two kinds of coordination problem that we consider in this paper (see
Definitions 3 and 4) are uncomplicated games, and yet computing certain
outcomes in a reasonable time frame is not guaranteed.101010This stands in
contrast to many existing intractability results on equilibrium computation
since often these rely on constructing games that are difficult to ascribe any
real world meaning to. One example that features prominently in this paper is
the language game of Neary (2011, 2012). This simple coordination game has
been tested experimentally (Lim and Neary, 2016) and has even been used to
introduce game theory to high school students at university open days. And
yet, despite how undemanding it is both to explain and to understand, it turns
out that identifying the welfare optimal Nash equilibrium is computationally
intractable.

The second reason for our focus on coordination problems is their importance.
Put simply, it is difficult to overstate the role that coordination problems
play in everyday life. The adoption of technological standards (Katz and
Shapiro, 1985; Farrell and Saloner, 1985; Arthur, 1989), the setting of
macroeconomic policy (Cooper and John, 1988), determining the drivers of bank
runs (Diamond and Dybvig, 1983), and the provision of public goods (Hellwig,
2003), are but a few of the many economic systems wherein coordination is key.
There are immediate benefits to one and all when the right collections of
mutually consistent actions appear, but because population behaviour is
decentralised the emergence of these “good” outcomes is far from guaranteed.
Given this, an understanding of what renders some coordination problems easier
to solve than others would be of genuine practical importance. The ability to
facilitate the emergence of a “good” outcomes could lead to a dramatic
reductions in the cost of coordination failure and in turn lead to potentially
enormous gains in welfare. Our results indicate that, at least when viewed
through an algorithmic lens, games of anti-coordination appear more difficult
to resolve than pure coordination games. Whether and how these findings carry
over to real life economic settings is a question for experimental economists,
but it is our hope that our theoretical results will prove complementary to
the large experimental literature devoted to understanding
coordination.111111While the potential discrepancy between pure coordination
games and anti-coordination games has not been considered, certain features of
coordination problems have been documented as relevant. Clearly the relative
attractiveness of the outcomes will matter. Consequently, many of the
experimental studies have considered environments that have the flavour of
Rousseau’s stag hunt wherein a tension exists between a risky equilibrium that
is optimal and another equilibrium that is suboptimal but safe. Van Huyck et
al. (1990) observe that size of population is an important factor in such
settings: a robust finding is that the smaller the group the higher average
payoffs achieved. (Crawford (1991) provides an evolutionary explanation for
these findings.) Perhaps closer in spirit to our work, Kearns et al. (2006)
and McCubbins et al. (2009) consider colouring problems, i.e., anti-
coordination games, on a variety of different network structures and conclude
that certain topologies promote successful colouring more readily than others.

The remainder of the introduction presents an example of the two kinds of
coordination problem that we consider followed by a brief overview of our
results. Section 2 formally defines the environments and the strategy profiles
of interest. Section 3 states the main results and sketches how one might, for
example, compute the potential maximiser of a pure coordination game. To our
knowledge, this is the first example where the potential maximiser is non
trivial and yet can by computed efficiently. All proofs are in the Appendix.

###  1.2 Pure coordination games and anti-coordination games

We consider binary action polymatrix games (see Definition 1 for the formal
statement), a subclass of network games first introduced in Janovskaya (1968).
Games in this class are easy to describe: a population of players live on a
graph where vertices represent players and edges represent pairwise
connections; along every edge is a binary action two-player game; every
player’s utility is the sum of payoffs earned with each neighbour where the
same action must be used with each.121212Without being specifically referred
to as such, polymatrix games appear throughout economics. For example, the
stage game of many classic models in stochastic evolutionary game theory is a
binary action polymatrix game (Kandori et al., 1993; Ellison, 1993; Morris,
2000; Peski, 2010; Kreindler and Young, 2013; Newton and Sercombe, 2020).

We will consider pure coordination polymatrix games (Definition 3), those
where every two player game is a game of pure coordination (actions are
strategic complements), and anti-coordination polymatrix games (Definition 4),
those in which every two player game is one of anti-coordination (actions are
strategic substitutes).

While this paper and its results pertain to all binary action pure/ anti-
coordination polymatrix games, let us now consider an example of each kind.
Suppose there are two societies that are identical both in their size and in
their network structure. That is, for every player in one society, there is a
“mirror image” player in the second society who has exactly the same
neighbourhood composition. The societies are differentiated only by the manner
in which neighbouring players interact. Specifically, in the first society,
each player $i$ interacts with every neighbour $j$ through $G_{ij}^{c}$ below
in Figure 1, while in the second society, player $i$ interacts with each
neighbour $j$ via $G_{ij}^{s}$ in Figure 1. We assume that
$\gamma_{i},\gamma_{j}\in[0,1]$ in both $G_{ij}^{c}$ and $G_{ij}^{s}$. (The
superscript “c” in $G_{ij}^{c}$ stands for complement while the superscript
“s” in $G_{ij}^{s}$ stands for substitute.)

22[${i}$][${j}$] & $a$ $b$
$a$ $\gamma_{i},\gamma_{j}$ $0,0$
$b$ $0,0$ 1$-\gamma_{i}$, 1$-\gamma_{j}$ 22[${i}$][${j}$] & $a$ $b$
$a$ 0,0 $\gamma_{i}$, $1-\gamma_{j}$
$b$ $1-\gamma_{i}$, $\gamma_{j}$ $0,0$

Figure 1: $G_{ij}^{c}$ and $G_{ij}^{s}$.

Games of the form $G_{ij}^{c}$ have two strict equilibria, both profiles along
the main diagonal, while those of the form $G_{ij}^{s}$ have as strict
equilibria the two profiles located on the off diagonal.131313We normalise
payoffs at all non-equilibrium outcomes to be zero. We do this for
expositional purposes only; our main results do not require it.

Observe that the two environments above are extremely close in spirit. In
each, a player’s utility depends only on her own choice of strategy and the
number of neighbours playing each strategy (but, importantly, not on the
identity of the neighbouring players playing each strategy).141414Blonski
(1999, 2000) considers anonymous games. Both environments we consider are
“locally” anonymous. Building on this, let us zoom in on two players located
at the corresponding vertex of either network and let us consider the
strategic environment faced by each. For this pair of players, optimising
behaviour is described by an almost identical threshold rule.151515The pure
coordination polymatrix game where each pairwise interaction has the structure
of $G_{ij}^{c}$ is the threshold model of Neary and Newton (2017). This
moniker was chosen as it is the polymatrix game variant of Granovetter’s
classic threshold model from sociology (Granovetter, 1978). In the pure
coordination environment, player $i$’s best response is: choose action $b$
whenever at least fraction $\gamma_{i}$ of neighbours choose action $b$, and
choose action $a$ otherwise. In the anti-coordination environment, player
$i$’s best response is: choose action $b$ whenever at least fraction
$\gamma_{i}$ of neighbours choose action $a$, and choose action $b$ otherwise.

Yet despite how similar optimal behaviour is in both environments, it turns
out that one environment is more “complex” than the other. Here is an example
of one such discrepancy: both $G_{ij}^{c}$ and $G_{ij}^{s}$ are potential
games, and when every two player game of a polymatrix game is a potential
game, then the polymatrix game is too. A well-studied object in potential
games is the potential maximising outcome. It turns out that computing the
potential maximising outcome in the pure coordination polymatrix game is a
tractable problem, whereas computing the analogous outcome in the anti-
coordination environment is not (formally, it is NP-hard).

###  1.3 Summary of main results

A classification of the tractability of each of the six objectives (three
kinds of strategy profile for each of the two kinds of coordination problem)
is given in Table 1.

Table 1: Complexity of each objective. | pure coordination | anti-coordination
---|---|---
maximising welfare | tractable |  NP-hard
Corollary 1 | Corollary 2
|  Bramoullé (2007) and Cai and Daskalakis (2011)
optimal Nash equilibrium |  NP-hard |  NP-hard
Corollary 5 |
| Cai and Daskalakis (2011)
maximising potential | tractable |  NP-hard
Corollary 3 | Corollary 4
|  Bramoullé (2007) and Cai and Daskalakis (2011)

Observe that positive results exist for both welfare maximisation and
potential maximisation in pure coordination polymatrix games. While the
complexity of computing the corresponding profiles for anti-coordination
polymatrix games have already been resolved,161616Bramoullé (2007) considers a
binary action anti-coordination polymatrix game where preferences are
homogeneous: every pairwise interaction is of the form $G_{ij}^{s}$ from
Figure 1, with $\gamma_{i}=\gamma=\frac{1}{2}$ for every player $i$. Bramoullé
shows that identifying the potential maximiser and the welfare maximiser for
this simple set up is equivalent to finding the maximum cut in a graph
(Maximum Cut is a well-known computationally hard problem). Section 4 of Cai
and Daskalakis (2011) shows that finding any Nash equilibrium (pure or mixed)
is NP-hard in the same environment explaining the result on optimal equilibria
for anti-coordination games. we will show that all four results can be
obtained by invoking a result on a novel graph-theoretic problem on oriented
graphs, hereafter orgraphs (these are directed graphs where if $ij$ is a
directed edge then $ji$ is not).

The problem, introduced in Deligkas et al. (2023), is termed Maximum Weighted
Orgraph Partition (MWOP). Informally, MWOP is described as follows (for the
formal statement see Definition 8). Begin with an orgraph and assign a
$2\times 2$ matrix to every directed edge.171717The convention we employ is
that the vertex at the tail of a directed edge references the row of the
matrix while the vertex at its head refers to the column of the matrix. Every
vertex is assigned either $a$ or $b$, and the assignment of adjacent vertices
determines the cell-entry of the matrix on the edge connecting them. The
objective of the MWOP problem is to partition the vertices into those assigned
$a$ and those assigned $b$ such that the sum of the weights on each edge is
maximised.

Deligkas et al. (2023) completely characterise when the MWOP problem is
tractable. Surprisingly, the tractability depends only on the properties of
the assigned matrices. There are three families of matrices for which the MWOP
problem is tractable. The first two cases are immediate: when the maximum
entry in every matrix is in the top left cell or in the bottom right cell,
i.e., all vertices are assigned $a$ or all are assigned $b$. The third
tractable case is when, for every $2\times 2$ matrix, the sum of the entries
along the main diagonal is no smaller than the sum of the other two terms. The
proof of this case works by constructing a new auxiliary weighted graph and
showing that the assignment that optimises the value is found by the minimum
cut in the new graph; Minimum Cut is a well-studied problem for which there
are many efficient algorithms (see, e.g., Korte and Vygen (2011)).

To see how MWOP can be used to compute welfare-optimal and potential
maximising outcomes in the coordination problems that we consider, the third
tractable case of MWOP provides the key. For any two player pure coordination
game, both the welfare matrix and the potential matrix satisfy the property
that the sum of terms along the main diagonal is at least as great as the sum
of the other two terms. For every two player anti-coordination game, the
inequality goes the other way. As an example, recall the games $G_{ij}^{c}$
and $G_{ij}^{s}$ from Figure 1 and let us consider the issue of welfare. With
$i$’s strategy choice indexing the row and $j$’s indexing the column, the
welfare matrices of both games are as given in Figure 2.

$\left[\begin{array}[]{cc}\gamma_{i}+\gamma_{j}&0\\\
0&2-\gamma_{i}-\gamma_{j}\end{array}\right]\hskip
57.81621pt\left[\begin{array}[]{cc}0&\gamma_{i}+1-\gamma_{j}\\\
1-\gamma_{i}+\gamma_{j}&0\end{array}\right]$
Figure 2: Welfare matrices for $2\times 2$ games $G_{ij}^{c}$ and $G_{ij}^{s}$
from Figure 1.

The result follows almost immediately: welfare matrices for pure coordination
polymatrix games are of the form of the left matrix in Figure 2 and so
maximising welfare is tractable.

Table 1 indicates that it is not all good news for identifying outcomes in
pure coordination polymatrix games. In particular, computing the welfare
optimal Nash equilibrium is intractable. We show this using the language game
of Neary (2011, 2012). The language game is a two-type threshold model. Each
player is a member of one of two groups, Group $A$ or Group $B$, and all
players in the same group have the same threshold, either $\gamma_{A}$ or
$\gamma_{B}$. For this simple binary action environment, we will show show
that efficient outcomes can be identified but that computing the welfare
optimal Nash equilibrium is intractable.

###  1.4 Computation of Nash Equilibria

While the theorem of Nash (1950, 1951) ensures the existence of an equilibrium
in every finite game, the proof is non-constructive and so provides no guide
on how one might find one. Chen et al. (2009) and Daskalakis et al. (2009)
showed that computing a Nash equilibrium is a problem that lies in the
complexity class PPAD. Both papers explicitly use polymatrix games in their
main constructions.181818Some classical results concerning computing
equilibria in polymatrix games existed already (Eaves, 1973; Howson Jr, 1972;
Howson Jr and Rosenthal, 1974; Miller and Zucker, 1991).

With the problem of computing of a Nash equilibrium resolved, attention has
turned to the difficulty of finding outcomes in specific classes of games (as
is our focus in this paper), to computing equilibria with certain properties
(see for example both Gilboa and Zemel (1989) and Conitzer and Sandholm
(2008)), and also to that of computing approximate equilibria. Recently,
Deligkas et al. (2022) proved a dichotomy for the complexity of finding any
approximate well-supported Nash equilibrium in binary-action polymatrix games;
in an approximate well-supported Nash equilibrium every player assigns
positive probability only on actions that approximately maximize their payoff.
Boodaghians et al. (2020) studied the smoothed complexity on coordination
polymatrix games, while Aloisio et al. (2021) studied an extension of
polymatrix games. The complexity of constrained Nash equilibria for general
polymatrix games were studied by 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 Coordination problems in networks

Section 2.1 begins with the definition of a binary action polymatrix game, and
then introduces the two kinds of coordination problem that we consider: pure
coordination polymatrix games and anti-coordination polymatrix games. In
Section 2.2 we formally define the three kinds of strategies profiles that we
are interested in.

###  2.1 Binary action polymatrix games

A polymatrix game is the simplest kind of network game: a population of
players reside on a graph where vertices represent players and edges represent
pairwise connections; along every edge is a two player game; every player’s
utility is the sum of payoffs earned with each neighbour where the same action
must be used with each (so by definition each player has the same available
strategies in all pairwise interactions in which they partake).

######  Definition 1.

A binary action polymatrix game, $\mathcal{G}$, consists of

  * •

an undirected graph $G=(V,E)$, where $V$ is a finite set
$\left\\{1,...,n\right\\}$ of players, sometimes called vertices, and a finite
set $E$ of edges, which are taken to be unordered pairs $\left\\{i,j\right\\}$
of players, $i\neq j$ (to economise on notation sometimes we will write $ij$
instead of $\left\\{i,j\right\\}$);

  * •

for each player $i\in V$, a (common) set of strategies
$S_{i}=S=\left\\{a,b\right\\}$;

  * •

for each $\left\\{i,j\right\\}\in E$, a two-player game $(u^{ij},u^{ji})$,
where the players are $i$ and $j$, the strategy set for both player $i$ and
player $j$ is $S$, and payoffs $u^{ij}:S_{i}\times S_{j}\to\mathbb{R}$ and
$u^{ji}:S_{j}\times S_{i}\to\mathbb{R}$;

  * •

for each player $i\in V$ and strategy profile
$\boldsymbol{s}=(s_{1},\dots,s_{n})\in\boldsymbol{S}=S^{n}$, the utility to
player $i$ from $\boldsymbol{s}$ is
$U_{i}(\boldsymbol{s})=\sum_{\left\\{i,j\right\\}\in E}u^{ij}(s_{i},s_{j})$.

We are interested in two kinds of binary action polymatrix games that
represent the two kinds of coordination problems. The first are pure
coordination games and the second are anti-coordination games: in the former
each player wants their neighbours to choose the same action, while in the
latter every player wants the opposite. Given that two player interactions are
the building blocks of a polymatrix game, the formal definition of each kind
of coordination problem that we employ is based on the structure of the
equilibrium set of the two player games that make up the polymatrix game.

A strategy profile $\boldsymbol{s}^{*}$ is a pure strategy Nash equilibrium if
no player can increase their utility by unilaterally changing their strategy.
Before defining this formally, note that we will occasionally write strategy
profile $\boldsymbol{s}$ as $(s_{i},\boldsymbol{s}_{-i})$ as this allows us to
describe a strategy profile “from the perspective” of player $i$.

######  Definition 2.

Strategy profile $\boldsymbol{s}^{*}$ is a pure strategy Nash equilibrium, if,
for every player $i\in V$ and every $s_{i}\in S$, it holds that
$U_{i}(s_{i}^{*},\boldsymbol{s}_{-i}^{*})\geq
U_{i}(s_{i},\boldsymbol{s}_{-i}^{*})$. A pure strategy Nash equilibrium,
$\boldsymbol{s}^{*}$, is a strict equilibrium if the inequalities are strict.

Given the above, we can now define the two kinds of coordination problem that
we consider.

######  Definition 3.

A binary-action polymatrix game is a pure coordination polymatrix game if, for
every two player game, the action profiles $(a,a)$ and $(b,b)$ are strict
equilibria.

######  Definition 4.

A binary-action polymatrix game is an anti-coordination polymatrix game if,
for every two player game, the action profiles $(a,b)$ and $(b,a)$ are strict
equilibria.

Our definition of a pure coordination game, Definition 3, is adapted from
Foster and Young (1998), where a two-person coordination game is defined as
one in which both players have $k$ strategies and there exists a enumeration
of each player’s strategy set such that it is always a strict equilibrium for
both players to play the strategy with the same index. We note that a two
player anti-coordination game is a pure coordination game according to this
definition (all one must do is swap the labelling of one of the player’s
strategy set). However, this is not the case for anti-coordination polymatrix
games in general (although it can be for specific network structures, e.g., a
bipartite graph).

###  2.2 Strategy profiles of interest

We are interested in determining the following patterns of behaviour: a
strategy profile that maximises welfare, a welfare optimal Nash equilibrium,
and a profile that maximises potential.

######  Definition 5.

Given a binary-action polymatrix game, $\mathcal{G}$, we write
$\mathcal{W}{}(\boldsymbol{s})$ for the utilitarian social welfare evaluated
at profile $\boldsymbol{s}$. That is,

$\mathcal{W}{}(\boldsymbol{s}):=\sum_{i=1}^{n}U_{i}(\boldsymbol{s}).$

The first profile that we are interested in is that which maximises social
welfare, i.e.,

$\operatorname*{argmax}_{\boldsymbol{s}\in\boldsymbol{S}}\mathcal{W}{}(\boldsymbol{s}).$
(1)

We also care about pure strategy equilibria. Let
$\boldsymbol{S}^{*}\subseteq\boldsymbol{S}$ denote the set of pure strategy
Nash equilibria. The second object of interest is a pure strategy Nash
equilibrium that maximises welfare, i.e.,

$\operatorname*{argmax}_{\boldsymbol{s}\in\boldsymbol{S}^{*}}\mathcal{W}{}(\boldsymbol{s}).$
(2)

While pure-coordination polymatrix games always possess two “trivial” pure
Nash equilibria, it is easy to come up with an example where an anti-
coordination polymatrix game does not possess a pure strategy equilibrium.
However, a well-studied class of game is potential games (Shapley and
Monderer, 1996). Potential games possess many desirable properties. One such
property is that pure strategy equilibria correspond to local optima of the
potential function so the existence of a pure strategy equilibrium is assured.

In a potential game, the incentive of each player to change their strategy can
be expressed using a single function called the potential function.

######  Definition 6.

A game is a potential game if there exists a function
$\Phi:\boldsymbol{S}\to\mathbb{R}$ such that for every player $i$, for all
$\boldsymbol{s}_{-i}$, and all pairs of actions
$s_{i}^{\prime},s_{i}^{\prime\prime}\in S_{i}$

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

When every pairwise interaction of a polymatrix game is a potential game then
the polymatrix game inherits this property, with the potential at any strategy
profile equal to the sum of the potentials along every edge. More formally, if
$\Phi^{ij}\colon S\times S\to\mathbb{R}$ denotes the pairwise-potential
function for the two-player game played between players $i$ and $j$, then the
function $\Phi\colon S^{n}\to\mathbb{R}$ is a potential function for the
polymatrix game, where

$\Phi(\boldsymbol{s}):=\sum_{\left\\{i,j\right\\}\in E}\Phi^{ij}(s_{i},s_{j})$

Whenever we consider potential maximisers, we will assume that every $2\times
2$ game in a binary action polymatrix game is a potential game, so that we
limit attention to pairwise-potential binary action polymatrix games.

The third and final pure strategy profile that we focus on is that which
maximises the potential of a pairwise-potential polymatrix game, i.e.,

$\operatorname*{argmax}_{\boldsymbol{s}\in\boldsymbol{S}}\Phi{}(\boldsymbol{s})$
(3)

where we note that since the profile that maximises the potential is
guaranteed to be a pure strategy Nash equilibrium (Shapley and Monderer, 1996)
and so optimising only over the set of pure strategies $\boldsymbol{S}$ is
without loss of generality.

To sum up, given a coordination problem, the three patterns of behaviour that
we are interested are those defined in (1), (2), and (3).

##  3 Results

In Section 3.1 we show that the problem of maximising welfare and maximising
the potential of a pure coordination polymatrix games are both tractable
problems. However, computing the two corresponding outcomes in anti-
coordination polymatrix games is intractable. While these two negative results
were known already (Bramoullé, 2007; Cai and Daskalakis, 2011), we show how
all four results can be recovered using a novel graph theoretic problem, the
Maximum Weighted Orgraph Partition (MWOP) problem, introduced in Deligkas et
al. (2023). In Section 3.2, we prove that finding the welfare optimal Nash
equilibrium in a pure coordination polymatrix game is intractable. Computing
the corresponding outcome for anti-coordination polymatrix games is known to
be intractable since Cai and Daskalakis (2011) showed that computing any pure
strategy Nash equilibrium in such games is NP-hard.

###  3.1 Maximising welfare and maximising potential

Determining when the welfare maximising outcome and the potential maximising
outcome is tractable follows by appealing to a novel graph-theoretic problem
known as the Maximum Weighted Orgraph Partition (MWOP) problem introduced in
Deligkas et al. (2023).

Throughout the paper we use standard terminology for both undirected graphs
and directed graphs, see for example the textbook of Bang-Jensen and Gutin
(2009). We define the main terms and any omitted can be found therein.

A directed graph (or just digraph) $D$ consists of a non-empty finite set
$V(D)$ of elements called vertices and a finite set $A(D)$ of ordered pairs of
distinct vertices called arcs. We call $V(D)$ the vertex set and $A(D)$ the
arc set of $D$. An oriented graph is a directed graph without $2$-cycles (that
is, if $ij\in A(D)$, then $ji\notin A(D)$).

A partition of the vertices in digraph $D$ is a mapping $P\colon
V(D)\to\left\\{a,b\right\\}$. Given a partition $P$, to keep notation simple,
we write $P=(X_{a},X_{b})$ where $X_{a}$ is the set of vertices assigned $a$
and $X_{b}$ those assigned $b$.

####  3.1.1 Maximum weighted orgraph partition

In this section we state formally the MWOP problem and we characterise the
conditions on matrices that render the problem tractable. We begin by defining
a family of matrices.

######  Definition 7.

Let ${\cal F}$ denote a family of $2\times 2$ matrices. For each matrix
$M\in{\cal F}$ let $m_{aa}$, $m_{ab}$, $m_{ba}$ and $m_{bb}$ denote the
entries of $M$, so that

$M=\left[\begin{array}[]{cc}m_{aa}&m_{ab}\\\ m_{ba}&m_{bb}\\\
\end{array}\right].$

We say that a family $\mathcal{F}$ of $2\times 2$ matrices is _closed under
multiplication by a positive scalar_ if for all $2\times 2$ matrices $M$ and
all $c\in\mathbb{R}^{+}$ it holds that $M\in\mathcal{F}$ if and only if
$c\cdot M\in\mathcal{F}$. We are now ready to define the MWOP problem.

######  Definition 8 (Maximum Weighted Orgraph Partition).

Given a family of real $2\times 2$ matrices $\mathcal{F}$ that is closed under
multiplication by a positive scalar, an _instance of MWOP[ $\mathcal{F}$]_ is
given by the pair $(D,f)$, where

  * •

$D$ is an oriented graph on $n$ vertices;

  * •

$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_{a},X_{b})$, of $V(D)$, the weight of an arc $ij\in
A(D)$, denoted $\xi^{P}(ij)$, is defined as follows, where
$M=\left[\begin{array}[]{cc}m_{aa}&m_{ab}\\\ m_{ba}&m_{bb}\\\
\end{array}\right]=f(ij)$ is the matrix assigned to the arc $ij$.

$\xi^{P}(ij)=\left\\{\begin{array}[]{rcl}m_{aa}&\mbox{if}&i,j\in X_{a}\\\
m_{bb}&\mbox{if}&i,j\in X_{b}\\\ m_{ab}&\mbox{if}&i\in X_{a}\mbox{ and }j\in
X_{b}\\\ m_{ba}&\mbox{if}&i\in X_{b}\mbox{ and }i\in X_{a}\\\
\end{array}\right.$ (4)

Given an orgraph $D$ and a partition $P$ of $V(D)$, the _weight of $D$_,
denoted by $\xi^{P}(D)$, is defined as the sum of the weights on every arc.
That is, $\xi^{P}(D)=\sum_{ij\in A(D)}\xi^{P}(ij)$. Finally, given an instance
$(D,f)$ of MWOP[$\mathcal{F}$], the _objective_ of MWOP[$\mathcal{F}$] is to
find a partition $P$ of $V(D)$ that maximizes $\xi^{P}(D)$.

Note that Deligkas et al. (2023) defined an instance of MWOP[$\mathcal{F}$] in
a way that they do not require $\mathcal{F}$ to be closed under multiplication
by a positive scalar but instead impose a scalar $c_{ij}\in\mathbb{R}^{+}$ on
a each arc $ij$. However, these two definitions are equivalent, as we can
always take a “closure” of the family by including all multiples of each
matrix in $\mathcal{F}$ and then for each arc in the digraph replaces the
constant $c_{ij}$ and matrix $M_{ij}$ by the matrix $c_{ij}\cdot M_{ij}$.

Before proceeding, let us pause and remark on the need for oriented graphs.
While polymatrix games do not specify directed connections, when assigning a
matrix to the edge connecting a pair of players, imposing an orientation on
that edge is more precise as it removes any perceived ambiguity. Without doing
so, statements about which vertex refers to the row of the matrix and which
vertex refers to the column may cause confusion.

The main result in Deligkas et al. (2023) is that the tractability of solving
MWOP[$\mathcal{F}$] depends on properties of the matrices in the family of
matrices ${\cal F}$. We now introduce three properties of matrices that will
prove useful.

  1. Property (i):

$m_{aa}=\max\\{m_{aa},m_{bb},m_{ab},m_{ba}\\}$.

  2. Property (ii):

$m_{bb}=\max\\{m_{aa},m_{bb},m_{ab},m_{ba}\\}$.

  3. Property (iii):

$m_{aa}+m_{bb}\geq m_{ab}+m_{ba}$.

The following is the main result in Deligkas et al. (2023).

######  Theorem (Deligkas et al. (2023)).

Given a family of $2\times 2$ matrices $\mathcal{F}$ that is closed under
multiplication by a positive scalar, MWOP[$\mathcal{F}$] can be solved in
polynomial time if either all matrices in ${\cal F}$ satisfy Property (i), or
all matrices in ${\cal F}$ satisfy Property (ii), or all matrices in ${\cal
F}$ satisfy Property (iii). Otherwise, MWOP[$\mathcal{F}$] is NP-hard.

The result above decomposes MWOP[$\mathcal{F}$] into four subcases. Those in
which every matrix satisfies one of the three properties and “everything
else”. We emphasise that there are many subcases covered by “everything else”.

The proof of cases covered by Property (i) and Property (ii) are almost
immediate. Clearly the optimal partition $(X_{a},X_{b})$ is either
$\big{(}V(D),\emptyset\big{)}$ or $\big{(}\emptyset,V(D)\big{)}$.

The case where every matrix satisfies Property (iii) is directly applicable to
binary action pure coordination polymatrix games since both the welfare matrix
and the potential matrix of every two-player game possess this property. We
now sketch the proof from Deligkas et al. (2023) for this case. (Given its
importance, we repeat the proof in A.1.) Let us suppose there is a vertex $i$
in $D$, with two out-neighbours that for the purpose of this explainer we
label as $j_{1}$ and $j_{2}$. The out-neighbourhood of $i$ is depicted below
in Figure 3, with the matrices on arcs $ij_{1}$ and $ij_{2}$ denoted $M_{{1}}$
and $M_{{2}}$ respectively. (Recall that the convention we employ is that the
tail vertex of any arc indexes the row of the matrix on that arc.) Both
$j_{1}$ and $j_{2}$ may have other neighbours (either in- or out-neighbours)
that are omitted from the image. This possibility is conveyed by the three
lines emitting from each. For the sake of exposition, let us suppose that the
off diagonal entries in both matrices $M_{{1}}$ and $M_{{2}}$ are zero.

$j_{1}$$j_{2}$$i$$M_{{1}}$$M_{{2}}$22[$i$][$j_{1}$] & $a$ $b$
$a$ $m^{1}_{aa}$ $0$
$b$ $0$ $m^{1}_{bb}$ 22[$i$][$j_{2}$] & $a$ $b$
$a$ $m^{2}_{aa}$ $0$
$b$ $0$ $m^{2}_{bb}$ Figure 3: The neighbourhood of vertex $i$ in $D$.

The proof proceeds by constructing a new weighted undirected graph, $H$, with
vertex set $V(H)=V(D)\cup\left\\{x,y\right\\}$ as follows. Let $G(D)$ denote
the undirected graph obtained from $D$ by ignoring orientations. Let
$E(H)=E(G(D))\cup\left\\{xi,yi\;|\;i\in V(D)\right\\}$ and initially assign
all edges zero weight.

In Figure 4 below, we display the neighbourhoods of $i$, $j_{1}$ and $j_{2}$
in $H$. We have coloured vertex $j_{1}$ in blue and $j_{2}$ in red. There is a
weight assigned to each edge that captures precisely the loss that occurs from
assigning a vertex to one of the two partitions; the exact way the weight is
computed can be found in the proof at the Appendix.

We emphasise that the weights currently assigned to some of the edges are
incomplete as we include only the weight contributed due to vertex $i$ and its
neighbours.191919The weights are also colour coded to reflect the neighbour of
$i$ that generated the weight. That is, since vertices $j_{1}$ and $j_{2}$
have more neighbours in $D$ other than $i$, there should be more weight on
some of the edges. We use the symbol $\mathcal{O}$ to connote that there are
be omitted terms; the omitted weights may differ for each edge even though we
use $\mathcal{O}$ for each.

$j_{1}$$j_{2}$$i$$x$$y$$\frac{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}m^{2}_{aa}}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}m^{2}_{bb}}}{2}$$\frac{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}m^{1}_{aa}}+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}m^{1}_{bb}}}{2}$$\frac{-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}m^{2}_{aa}}}{2}+\mathcal{O}$$\frac{-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}m^{1}_{aa}}}{2}+\mathcal{O}$$-\frac{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}m^{2}_{bb}}}{2}+\mathcal{O}$$-\frac{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}m^{1}_{bb}}}{2}+\mathcal{O}$$-\frac{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}m^{1}_{bb}}}{2}-\frac{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}m^{2}_{bb}}}{2}$$\frac{-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}m^{1}_{aa}}}{2}+\frac{-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}m^{2}_{aa}}}{2}$
Figure 4: The neighbourhood of $i$ in $H$. Symbol $\mathcal{O}$ conveys
omitted weights.

For every edge to which either $x$ is adjacent or $y$ is adjacent, the weights
may be negative. In fact, in the example of Figure 4 all are negative. Now, to
each edge adjacent to either $x$ or $y$ we add a weight of magnitude equal to
that of the largest negative weight in the graph such that the weight on every
edge becomes non-negative. It is shown in the proof that while doing this will
change the value of the solution, doing this will not alter the partition that
maximises the sum of the weights.

With non-negative weight on each edge, it is straightforward to show that the
partition that maximises the sum of the weights on every edge is equivalent to
finding a minimum $x$-$y$ cut in the graph $H$. One such cut is shown in
Figure 5 below, where $i,j_{1}\in X_{a}$ and $j_{2}\in X_{b}$. The edges
remaining after the cut are those that contribute weight and are depicted in
bold.

$j_{1}$$j_{2}$$i$$x$$y$cut Figure 5: Remaining edges after an $x$-$y$ cut in
which $i,j_{1}\in X_{a}$ and $j_{2}\in X_{b}$.

We conclude the sketch of the proof of part (iii) by noting that a minimum
$x$-$y$ cut in a graph can be performed in polynomial time (see, e.g., Korte
and Vygen (2011)).

When it comes to applying this result to polymatrix games, we will interpret
vertex $x$ as a dummy player who is forced to choose action $a$ and vertex $y$
as a dummy player who must choose action $b$. Since every player must choose
either action $a$ or action $b$, a player must be connected to either $x$ or
$y$ but not both. Hence the need for a cut.

For a proof of the hardness of every other possible case, we refer the reader
to Deligkas et al. (2023).

In the next two subsections we show how to utilise the theorem of Deligkas et
al. (2023) to derive as corollaries several results, both positive and
negative, for various classes of binary-action polymatrix games. First we
focus on maximising welfare and then on maximising potential.

####  3.1.2 Maximising social welfare via MWOP

Consider a binary action polymatrix game $\mathcal{G}$ on graph $G$ and fix an
arbitrary orientation of every edge to generate an oriented graph
$D_{G}=\big{(}V(D_{G}),A(D_{G})\big{)}$. Now suppose that for every arc $ij\in
A(D_{G})$, that $i$ is the row player and that $j$ is the column player of the
two-player game played over edge $\left\\{i,j\right\\}\in E(G)$. We define the
_welfare matrix_ on arc $ij$ as follows:
$W^{ij}:=\left[\begin{array}[]{cc}w^{ij}_{aa}&w^{ij}_{ab}\\\
w^{ij}_{ba}&w^{ij}_{bb}\\\ \end{array}\right]$, where
$w^{ij}_{s_{i},s_{j}}=u^{ij}(s_{i},s_{j})+u^{ji}(s_{j},s_{i})$ for
$s_{i},s_{j}\in\left\\{a,b\right\\}$. In words, given a strategy profile
$\boldsymbol{s}=(s_{1}\ldots,s_{n})$, the term $w^{ij}_{s_{i},s_{j}}$,
captures precisely the “contribution” of edge $\\{i,j\\}\in V(G)$ towards the
utilitarian social welfare $\mathcal{W}{}(\boldsymbol{s})$. Let $(D_{G},f)$ be
an instance of MWOP such that for all arcs $ij\in A(D_{G})$ we have
$f(ij)=W^{ij}$.

For any strategy profile $\boldsymbol{s}$, we use $P(\boldsymbol{s})$ to
denote the partition of players into those choosing action $a$ and those
choosing $b$. The next lemma follows immediately.

######  Lemma 1.

For every possible strategy profile $\boldsymbol{s}$, it holds that
$\mathcal{W}{(}\boldsymbol{s})=\xi^{P(\boldsymbol{s})}(D_{G})$.

The above lemma gives us a straightforward correspondence between maximising
the utilitarian social welfare of a polymatrix game and MWOP. In order to
provide the complexity dichotomy for the problem of computing a strategy
profile that maximises welfare, let us first formally define a parameterised
version of the problem, which restricts the set of allowed welfare matrices in
an instance of the problem. More precisely, let $\mathcal{F}$ be a family of
$2\times 2$ matrices. Then Welfare Maximisation[$\mathcal{F}$] is defined as
follows.

######  Definition 9 (Welfare Maximisation[$\mathcal{F}$]).

Given a binary action polymatrix game $\mathcal{G}$ on graph $G$ and an
orientation $D_{G}$ of $G$ such that for every arc $ij\in A(D_{G})$ the
welfare matrix $W^{ij}$ is in $\mathcal{F}$, find a strategy profile
$\boldsymbol{s}$ that maximises the utilitarian social welfare
$\mathcal{W}{(}\boldsymbol{s})$.

We highlight that the chosen orientation does not matter for the complexity of
the problem. This is if any matrix $M$ satisfies one of the Properties
(i)-(iii), then its transpose $M^{T}$ will satisfy the same property.

Taken together, Lemma 1 and the theorem of Deligkas et al. (2023) yield the
following clean complexity dichotomy for the Welfare
Maximisation[$\mathcal{F}$] problem.

######  Theorem 1.

Given a collection of $2\times 2$ matrices $\mathcal{F}$ that is closed under
multiplication by a positive scalar, Welfare Maximisation _[ $\mathcal{F}$]_
can be solved in polynomial time if either all matrices in ${\cal F}$ satisfy
Property (i), or all matrices in ${\cal F}$ satisfy Property (ii), or all
matrices in ${\cal F}$ satisfy Property (iii). Otherwise, Welfare Maximisation
_[ $\mathcal{F}$]_ is NP-hard.

It can easily be verified that the welfare-matrix $W^{ij}$ of a $2\times 2$
pure-coordination game between players $i$ and $j$ has
$w^{ij}_{aa}+w^{ij}_{bb}\geq w^{ij}_{ab}+w^{ij}_{ba}$. Similarly, for all
$2\times 2$ games of anti-coordination, such an inequality never holds. Given
this, Theorem 1 immediately yields the following two corollaries.

######  Corollary 1.

The problem of maximising social welfare in binary-action pure-coordination
polymatrix games is solvable in polynomial time.

######  Corollary 2.

The problem of maximising social welfare in binary-action anti-coordination
polymatrix games is NP-hard.

####  3.1.3 Maximising potential via MWOP

We now show how to use MWOP to maximise the potential in a binary action
polymatrix game $\mathcal{G}$ on graph $G$. We assume that every two player
game is a potential game thereby ensuring that the $\mathcal{G}$ is too. Again
fix an orientation on every edge $\left\\{i,j\right\\}\in E(G)$ with $i$
indexing the row and $j$ the column. The potential matrix on arc $ij$ is given
by $\Phi^{ij}:=\left[\begin{array}[]{cc}\phi^{ij}_{aa}&\phi^{ij}_{ab}\\\
\phi^{ij}_{ba}&\phi^{ij}_{bb}\\\ \end{array}\right]$.

Let $\Phi(\boldsymbol{s})$ be the sum of the pairwise potentials along every
arc. If we denote by $P(\boldsymbol{s})$ the partition associated with
strategy profile $\boldsymbol{s}$, we get the following lemma for potential
that parallels Lemma 1 for welfare.

######  Lemma 2.

For every strategy profile $\boldsymbol{s}$ of a binary action polymatrix
game, it holds that $\Phi(\boldsymbol{s})=\xi^{P(\boldsymbol{s})}(D)$.

Before we state the main result for maximising the potential, let us first
formally define the parameterised version of the problem depending on a family
$\mathcal{F}$ of allowed potential matrices.

######  Definition 10 (Potential Maximisation[$\mathcal{F}$]).

Given a binary action polymatrix game $\mathcal{G}$ on graph $G$ and an
orientation $D$ of $G$ such that for every arc $ij\in A(D)$, the game between
$i$ and $j$ is a potential game with its potential matrix $\Phi^{ij}$ in
$\mathcal{F}$, find a strategy $\boldsymbol{s}$ that maximises the overall
potential $\Phi(\boldsymbol{s})$ of $\mathcal{G}$.

Lemma 2 combined with the theorem of Deligkas et al. (2023) yields the
following. To the best of our knowledge, this is the first example of a
potential game where the identifying the potential maximiser is non trivial
and yet doing so is possible.

######  Theorem 2.

Given a collection of $2\times 2$ matrices $\mathcal{F}$ that is closed under
multiplication by a positive scalar, Potential Maximisation _[ $\mathcal{F}$]_
can be solved in polynomial time if either all matrices in ${\cal F}$ satisfy
Property (i), or all matrices in ${\cal F}$ satisfy Property (ii), or all
matrices in ${\cal F}$ satisfy Property (iii). Otherwise, Potential
Maximisation _[ $\mathcal{F}$]_ is NP-hard.

Consider a two player binary action pure coordination game between players,
labeled $i$ and $j$, that admits a potential, $\Phi^{ij}$. In this case it is
immediate that
$\phi^{ij}_{aa}+\phi^{ij}_{bb}\geq\phi^{ij}_{ab}+\phi^{ij}_{ba}$ (since both
profiles $(a,a)$ and $(b,b)$ are pure strategy Nash equilibria and hence are
local maximisers of the potential function $\Phi^{ij}$). For a two player game
of anti-coordination the inequality holds strictly in the other direction
since profiles $(a,b)$ and $(b,a)$ are equilibria. Given this, Theorem 2
reveals another difference between pure-coordination and anti-coordination
polymatrix games, when every two player game in each is a pairwise-potential
game. In the latter class of games it is NP-hard to maximise the potential
function (this was already shown in Bramoullé (2007) and Cai and Daskalakis
(2011)), whereas for the former class of games the problem can be solved in
polynomial time.

######  Corollary 3.

The problem of maximising the potential in binary action pure-coordination
polymatrix games is solvable in polynomial time.

######  Corollary 4.

The problem of maximising the potential in binary-action anti-coordination
polymatrix games is NP-hard.

###  3.2 Computing a welfare-optimal equilibrium

In the previous section we showed that computing certain outcomes in pure-
coordination polymatrix games is tractable but are not in anti-coordination
games. However, as we now show, when it comes to computing a “best” Nash
equilibrium, things become almost immediately intractable. We demonstrate this
using arguably simplest pure-coordination polymatrix game with heterogeneous
preferences that can played on arbitrary graphs: the language game of Neary
(2011, 2012).

To introduce the language game we first introduce a special class of binary-
action pure-coordination polymatrix games, termed threshold games (Neary and
Newton, 2017). A threshold game is a pure-coordination polymatrix game where
every player $i$ is associated with a parameter $\gamma_{i}\in[0,1]$, and with
each neighbour $j$, player $i$ plays the following game

22[${i}$][${j}$] & $a$ $b$
$a$ $\gamma_{i},\gamma_{j}$ $0,0$
$b$ $0,0$ 1$-\gamma_{i}$, 1$-\gamma_{j}$

Note that each player in the threshold model cares only about the number of
neighbours choosing each action and not the identity of those neighbours. That
is, when player $i$ chooses action $a$ (respectively $b$) she earns
$\gamma_{i}$ (respectively $1-\gamma_{i}$) from every neighbour who also
choose $a$ (respectively $b$).

The 1-type threshold model, i.e., one wherein $\gamma_{i}=\gamma$ is the same
for all players $i$, is one of the most well-studied large population models.
When, for example, $\gamma>\frac{1}{2}$, it has been shown that everyone
playing strategy $a$ is stochastically stable (Foster and Young, 1990; Young,
1993) in a host of network structures (Kandori et al., 1993; Ellison, 1993;
Peski, 2010; Kreindler and Young, 2013). In related work, Morris (2000)
considers the issue of contagion in an infinite variant of the 1-type
threshold model. Morris supposes that the current state of play has all
players choosing strategy $b$. He proposes flipping the behaviour of a finite
of subset agents from $b$ to $a$ and then “letting the system go” via best-
response dynamics. The network property of cohesiveness is key for the
superior outcome of everyone choose action $a$ to eventually “replace” the
inferior one of everyone playing $b$. Note that in all variations of the
1-type threshold model, what is viewed as the optimal outcome is not only
agreed upon by one and all but is also trivial to identify. As such, questions
of study include whether decentralised behaviour will ultimately lead there,
if so how long will it take, and so on.

The language game of Neary (2011, 2012) is a two-type threshold model. The
population is comprised of two groups, Group $A$ and Group $B$. Every player
is a member of one of two groups, and all players in the same group have the
same threshold, either $\gamma_{A}$ or $\gamma_{B}$. With two types of player,
there are three types of pairwise interaction, $A$ with $A$, $B$ with $B$, and
$A$ with $B$. These games are shown below in Figure 6.

$\hskip 43.36243pt(u^{AA},u^{AA})\hskip 180.67499pt(u^{BB},u^{BB})$

22[$A_{1}$][$A_{2}$] & $a$ $b$

$a$ $\gamma_{A}$, $\gamma_{A}$ $0,0$

$b$ $0,0$ $1-\gamma_{A}$, $1-\gamma_{A}$ 22[$B_{1}$][$B_{2}$] & $a$ $b$

$a$ $\gamma_{B}$, $\gamma_{B}$ $0,0$

$b$ $0,0$ $1-\gamma_{B}$, $1-\gamma_{B}$

$\hskip 43.36243pt(u^{AB},u^{BA})$

22[$A$][$B$] & $a$ $b$

$a$ $\gamma_{A}$, $\gamma_{B}$ $0,0$

$b$ $0,0$ $1-\gamma_{A}$, $1-\gamma_{B}$

Figure 6: Three pairwise interactions: $(u^{AA},u^{AA})$, $(u^{BB},u^{BB})$,
and $(u^{AB},u^{BA})$.

Both within group interactions are symmetric. The across group game is an
asymmetric interaction whenever $\gamma_{A}\neq\gamma_{B}$. When
$\gamma_{B}<\frac{1}{2}<\gamma_{A}$ the across group game is a battle of the
sexes and so a tension emerges: Group-$A$ players prefer the equilibrium where
everyone coordinates on action $a$ while Group-$B$ players prefer the
opposite. Even for this simple two-type threshold model, the following theorem
shows that most cases are intractable.

######  Theorem 3.

The complexity of finding a welfare-optimal Nash equilibrium in the language
game, 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 can be solved in polynomial time.

2.

If $\gamma_{B}\geq 1/2$ the problem can be solved in polynomial time.

3.

If $\gamma_{B}=0$ and $\gamma_{A}=1$ the problem can be solved in polynomial
time.

4.

In all other cases the problem is NP-hard.

The proof, that can be found in Appendix A.2, proceeds by reducing the Minimum
Transversal problem in 3-uniform hypergraphs, a problem known to be NP-hard
(Garey and Johnson, 1979), to that of computing the welfare-optimal
equilibrium in the language game. Given Theorem 3, we can conclude the
following:

######  Corollary 5.

It is NP-hard to determine the welfare optimal Nash equilibrium in binary-
action pure coordination polymatrix games.

## APPENDIX

##  Appendix A Proofs

###  A.1 Part (iii) of Theorem in Deligkas et al. (2023)

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

###### Proof.

Let $(D,f)$ be an instance of MWOP(${\mathcal{F}}$). We will construct a new
(undirected) multigraph $H$ with vertex set $V(D)\cup\\{x,y\\}$ as follows.
Let $G(D)$ denote the undirected multigraph obtained from $D$ by removing
orientations of all arcs. Initially let $E(H)=E(G(D))\cup\\{xi,yj\;|\;i\in
V(D)\\}$ and let all edges in $H$ have weight zero. Now for each arc $ij\in
A(D)$ we modify the weight function $w$ of $H$ as follows, where $M=f(uv)$ is
the matrix associated with the arc $ij$.

  * •

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

  * •

Add $\frac{-m_{22}}{2}$ to $w(xi)$.

  * •

Add $\frac{-m_{22}}{2}$ to $w(xj)$.

  * •

Add $\frac{m_{21}-m_{11}-m_{12}}{2}$ to $w(yi)$.

  * •

Add $\frac{m_{12}-m_{11}-m_{21}}{2}$ to $w(yj)$.

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^{*}(ij)=w(ij)$ if
$\\{i,j\\}\cap\\{x,y\\}=\emptyset$ and $w^{*}(ij)=w(ij)-\theta$ otherwise. Now
we note that all $w^{*}$-weights in $H$ are non-negative. We will show that
for any $(x,y)$-cut, $(X_{1},X_{2})$ in $H$ (i.e., $(X_{1},X_{2})$ partitions
$V(H)$ and $x\in X_{1}$ and $y\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\\{y\\})$ in $D$. Therefore a minimum
weight cut in $H$ maximizes $w^{P}(D)$ in $D$.

Let $(X_{1},X_{2})$ be any $(x,y)$-cut in $H$. For every $u\in V(D)$ we note
that exactly one of the edges $xi$ and $iy$ 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\\{x\\},X_{2}\setminus\\{y\\})$ of $V(D)$).

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

  * •

$i,j\in X_{1}$. In this case when we considered the arc $ij$ above (when
defining the $w$-weights) we added $\frac{m_{21}-m_{11}-m_{12}}{2}$ to $w(yi)$
and $\frac{m_{12}-m_{11}-m_{21}}{2}$ to $w(yj)$. So, we added the following
amount to the $w$-weight of the $(s,t)$-cut, $(X_{1},X_{2})$.

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

  * •

$u,v\in X_{2}$. In this case when we considered the arc $ij$ above (when
defining the $w$-weights) we added $\left(\frac{-m_{22}}{2}\right)$ to $w(xi)$
and $\left(\frac{-m_{22}}{2}\right)$ to $w(xj)$. So, we added the following
amount to the $w$-weight of the $(x,y)$-cut, $(X_{1},X_{2})$.

$\left(\frac{-m_{22}}{2}+\frac{-m_{22}}{2}\right)=-m_{22}$

  * •

$i\in X_{1}$ and $j\in X_{2}$. In this case when we considered the arc $ij$
above (when defining the $w$-weights) we let
$w(ij)=\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}$ and added
$\left(\frac{-m_{22}}{2}\right)$ to $w(xj)$ and
$\frac{m_{21}-m_{11}-m_{12}}{2}$ to $w(yi)$. So, we added the following amount
to the $w$-weight of the $(x,y)$-cut, $(X_{1},X_{2})$.

$\displaystyle\left(\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}+\frac{-m_{22}}{2}+\frac{m_{21}-m_{11}-m_{12}}{2}\right)=m_{12}$

  * •

$j\in X_{1}$ and $i\in X_{2}$. In this case when we considered the arc $ij$
above (when defining the $w$-weights) we let
$w(ij)=\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}$ and added
$\left(\frac{-m_{22}}{2}\right)$ to $w(xi)$ and
$\frac{m_{12}-m_{11}-m_{21}}{2}$ to $w(yj)$. So, we added the following amount
to the $w$-weight of the $(x,y)$-cut, $(X_{1},X_{2})$.

$\displaystyle\left(\frac{m_{11}+m_{22}-m_{12}-m_{21}}{2}+\frac{-m_{22}}{2}+\frac{m_{12}-m_{11}-m_{21}}{2}\right)=m_{21}$

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

Analogously, if we have a partition $P=(X_{1},X_{2})$ of $V(D)$, then adding
$x$ to $X_{1}$ and $y$ to $X_{2}$ we obtain a $(x,y)$-cut with $w$-weight
$-w^{P}(D)$ of $H$. As we can find a minimum $w^{*}$-weight cut in $H$ in
polynomial time202020Often the Min Cut problem is formulated for graphs rather
than multigraphs (and $H$ is a multigraph), but we can easily reduce the Min
Cut problem from multigraphs to graphs by merging all edges with the same end-
points to one edge with the same end-points and with weight equal the sum of
the weights of the merged edges. 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, MWOP($\mathcal{F}$) can be solved in
polynomial time in this case. ∎

###  A.2 Proof of Theorem 3

The proof of parts (i) and (ii) are straightforward. Both symmetric profiles
are always Nash equilibria. For part (i) all players choose $b$ is the optimal
equilibrium and for part (ii) all players choose $a$. So we begin with the
proof of part (iii).

##### Proof of part (iii):

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

Let $(X_{a},X_{b})$ be a Nash equilibrium of $G$. This implies that all
vertices in $X_{b}\cap A$ only have edges to vertices in $X_{b}$ (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_{a}$ or a subset of $X_{b}$,
since otherwise one can find an edge from a vertex in $X_{b}\cap A$ to a
vertex in $X_{a}$. Analogously, every connected component of $G[B]$ is either
a subset of $X_{a}$ or a subset of $X_{b}$. 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 $i\in C_{A}$ and a vertex $j\in
C_{B}$, then it is not possible that $C_{B}\subseteq X_{a}$ and
$C_{A}\subseteq X_{b}$.

We now construct 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)=\\{x,y\\}\cup\\{a_{1},a_{2},\ldots,a_{l}\\}\cup\\{b_{1},b_{2},\ldots,b_{m}\\}$.
For each $C_{k}^{A}$ add an arc from $x$ to $a_{k}$ of weight
$2|E(C_{k}^{A})|$ and for each $C_{k}^{B}$ add an arc from $b_{k}$ to $y$ of
weight $2|E(C_{k}^{B})|$. Now for each $k\in\\{1,2,\ldots,l\\}$ and
$\ell\in\\{1,2,\ldots,m\\}$ we add an arc from $a_{k}$ to $b_{\ell}$ of weight
$|E(C_{k}^{A},C_{\ell}^{B})|$ and if $|E(C_{k}^{A},C_{\ell}^{B})|>0$ then add
an arc from $b_{\ell}$ to $a_{k}$ of infinite weight. This completes the
construction of $D$.

Let $(X,Y)$ be a $(x,y)$-cut (i.e., $x\in X$ and $y\in Y$) in $D$ containing
no arc of infinite weight. Let the weight of $(X,Y)$ be $\xi(X,Y)$. We will
now construct a Nash equilibrium $(X_{a},X_{b})$ of $G$. For every $a_{k}\in
X$ add all vertices in $C_{k}^{A}$ to $X_{a}$ and for every $a_{k}\in Y$ add
all vertices in $C_{k}^{A}$ to $X_{b}$. Analogously, for every $b_{\ell}\in S$
add all vertices in $C_{\ell}^{B}$ to $X_{a}$ and for every $b_{\ell}\in T$
add all vertices in $C_{\ell}^{B}$ to $X_{b}$. This defines a partition
$(X_{a},X_{b})$.

As no arc of infinite weight exists in the cut, we note that that
$(X_{a},X_{b})$ is a Nash equilibrium. We will now show that the welfare of
$(X_{a},X_{b})$ is
$\mathcal{W}{}(X_{a},X_{b})=2|E(G)|-|E(A,B)|-\mathcal{W}{}(X,Y)$. If $xa_{k}$
belongs to the cut then all arcs in $C_{k}^{A}$ contribute zero to welfare and
zero to the formula for $\mathcal{W}{(}X_{a},X_{b})$. If $b_{\ell}y$ belongs
to the cut then all arcs in $C_{\ell}^{B}$ contribute zero to the welfare and
zero to the formula for $\mathcal{W}{}(X_{a},X_{b})$. If $a_{k}b_{\ell}$
belongs to the cut then all arcs in $E(C_{k}^{A},C_{\ell}^{B})$ contribute
zero to the welfare and zero to the formula for $\mathcal{W}{}(X_{a},X_{b})$.
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_{a},X_{b})$ is indeed
$\mathcal{W}{}(X_{a},X_{b})=2|E(G)|-|E(A,B)|-\mathcal{W}{}(X,Y)$.

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

Therefore, if the maximum welfare Nash equilibrium has welfare ${\rm
wel}^{opt}$ and the minimum weight $(x,y)$-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 $(x,y)$-cut in polynomial time (see, e.g., Korte and Vygen (2011)),
this gives us a polynomial time algorithm for finding a welfare optimal Nash
equilibrium when $\gamma_{A}=1$ and $\gamma_{B}=0$. So we are done.

##### Proof of part (iv):

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 4
below.

We will start with two useful lemmas.

######  Lemma 3.

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

###### Proof.

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

$\begin{array}[]{rcl}\mathcal{W}{}\big{(}V(G),\emptyset\big{)}-\mathcal{W}{}(X_{a},X_{b})&=&\binom{|X_{b}|}{2}(2\gamma_{A})+|X_{a}|\cdot|X_{b}|(2\gamma_{A})-\binom{|X_{b}|}{2}\big{(}(2(1-\gamma_{A})\big{)}\\\
&=&q(q-1)\big{(}\gamma_{A}-(1-\gamma_{A})\big{)}+2(n_{A}-q)q\gamma_{A}\\\
&=&q\left((q-1)(2\gamma_{A}-1)+2n_{A}\gamma_{A}-2q\gamma_{A}\right)\\\
&=&q\left(2q\gamma_{A}-q-2\gamma_{A}+1+2n_{A}\gamma_{A}-2q\gamma_{A}\right)\\\
&=&q\left(2\gamma_{A}(n_{A}-1)-q+1\right)\\\ \end{array}$

Consider the function $f(q)=q\left(2\gamma_{A}(n_{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 n_{A}$ the minimum value of $f(q)$ is therefore $f(1)$ or $f(n_{A})$,
which implies the following.

$\mathcal{W}{}(V(G),\emptyset)-\mathcal{W}{}(X_{a},X_{b})\geq\min\\{f(1),f(n_{A})\\}=\min\\{2\gamma_{A}(n_{A}-1),n_{A}(n_{A}-1)(2\gamma_{A}-1)\\}$

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

######  Corollary 6.

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

###### Proof.

By replacing action $b$ with $a$ 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 3,

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

######  Lemma 4.

Let $\gamma_{A}$ and $\gamma_{B}$ be reals 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_{a},X_{b})$ is a Nash equilibrium if and only if
the following holds for all $i\in V(G)$.

  * •

For every player $i\in X_{a}\cap A$ we have $N(i)\cap X_{b}=\emptyset$ or
$\frac{|N(i)\cap X_{a}|}{|N(i)\cap
X_{b}|}\geq\frac{1-\gamma_{A}}{\gamma_{A}}$.

  * •

For every player $i\in X_{b}\cap A$ we have $N(i)\cap X_{a}=\emptyset$ or
$\frac{|N(i)\cap X_{b}|}{|N(i)\cap
X_{a}|}\geq\frac{\gamma_{A}}{1-\gamma_{A}}$.

  * •

For every player $i\in X_{a}\cap B$ we have $N(i)\cap X_{b}=\emptyset$ or
$\frac{|N(i)\cap X_{a}|}{|N(i)\cap
X_{b}|}\geq\frac{1-\gamma_{B}}{\gamma_{B}}$.

  * •

For every player $i\in X_{b}\cap B$ we have $N(i)\cap X_{a}=\emptyset$ or
$\frac{|N(i)\cap X_{b}|}{|N(i)\cap
X_{a}|}\geq\frac{\gamma_{B}}{1-\gamma_{B}}$.

###### Proof.

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

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

The statements concerning players in Group $B$ follow in an identical manner.
∎

######  Theorem 4.

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 in a threshold-game with two thresholds, $\gamma_{A}$
and $\gamma_{B}$.

###### Proof.

We will show the NP-hardness result via a reduction from Minimum Transversal
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 transversal of $H$ is a set of vertices $X$
such that $X\cap e\neq\emptyset$ for every edge $e\in E(H)$. The problem
Minimum Transversal asks to find a transversal of 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.

  1. (a):

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

  2. (b):

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

  3. (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}}$

  4. (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})$.

  5. (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}}$.

  6. (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. 7.

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 vertex $u\in V(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 7: 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_{a},X_{b})$ of $V(G)$ (where all players in
$X_{a}$ choose action $a$ and all players in $X_{b}$ choose action $b$).

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

$\xi(ij)=\left\\{\begin{array}[]{rclcl}2\gamma_{A}&&\mbox{if $i,j\in X_{a}$
and $i,j\in A$}\\\ 2\gamma_{B}&&\mbox{if $i,j\in X_{a}$ and $i,j\in B$}\\\
\gamma_{A}+\gamma_{B}&&\mbox{if $i,j\in X_{a}$ and $|\\{i,j\\}\cap A|=1$}\\\
2(1-\gamma_{A})&&\mbox{if $i,j\in X_{b}$ and $i,j\in A$}\\\
2(1-\gamma_{B})&&\mbox{if $i,j\in X_{b}$ and $i,j\in B$}\\\
2-\gamma_{A}-\gamma_{B}&&\mbox{if $i,j\in X_{b}$ and $|\\{i,j\\}\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 1.

The optimal welfare of $G-E_{3}-E_{4}$ (with value $W^{*}$) is obtained for
the partition $(X_{a},X_{b})$ if, and only if, the following holds.

$V(C_{A})\cup R\subseteq X_{a}\text{ and }V(C_{B})\subseteq X_{b}$ (i)

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

###### Proof of Claim 1.

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_{a},X_{b})$
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 3 we note that if
$V(C_{A})\not\subseteq X_{a}$ 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 6 and (e) we note that if $V(C_{B})\not\subseteq
X_{b}$ 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_{a}$
or $V(C_{B})\not\subseteq X_{b}$ then the welfare of $(X_{a},X_{b})$ 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_{a}$
and $V(C_{B})\subseteq X_{b}$.

Let $r_{e}\in R$ be arbitrary and assume that $r_{e}\in X_{b}$. By moving
$r_{e}$ to $X_{a}$ 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\hfill\qed\\\ \end{array}$

######  Claim 2.

Let $(X_{a},X_{b})$ be any Nash equilibrium of $G$ that satisfies (i) in Claim
1, then (ii) below holds.

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

###### Proof of Claim 2.

Recall that by (A) in Claim A we have $V(C_{A})\cup R\subseteq X_{a}$ and
$V(C_{B})\subseteq X_{b}$. 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_{b}$. 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_{a}$ and $x_{B}+3$
neighbours in $X_{b}$. So its current welfare is $x_{A}\gamma_{B}$, but if we
move $r_{e}$ to $X_{b}$ 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. ∎

######  Claim 3.

Let $(X_{a},X_{b})$ be any partition of $V(G)$ that satisfies (i) in Claim 1,
(ii) in Claim 2, and (iii) below. Then $(X_{a},X_{b})$ is a Nash equilibrium.

$\text{For every }u\in V(H),\text{ either }\\{u^{\prime}\\}\cup Z_{u}\subseteq
X_{a}\text{ or }\\{u^{\prime}\\}\cup Z_{u}\subseteq X_{b}.$ (iii)

###### Proof of Claim 3.

As vertices in $Z$ are only adjacent to vertices in the same partite set in
$(X_{a},X_{b})$ as themselves they do satisfy the Nash equilibrium condition.
By Lemma 4 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_{a}|}{|N(v_{A})\cap
X_{b}|}\geq\frac{1-\gamma_{A}}{\gamma_{A}}$ or $N(v_{A})\cap X_{b}=\emptyset$
(as $v_{A}\in A\cap X_{a}$).

  * •

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

  * •

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

  * •

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

  * •

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

The first inquality holds as $N(v_{A})\cap X_{b}=\emptyset$. The second
inequality holds due to the following (see (e)):

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

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

$\begin{array}[]{rcl}\frac{|N(r_{e})\cap X_{a}|}{|N(r_{e})\cap
X_{b}|}&\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_{a}$ then all neighbours of $u^{\prime}$
belong to $X_{a}$, so $N(u^{\prime})\cap X_{b}=\emptyset$, which satisfies the
fourth equation. Let $u^{\prime}\in V^{\prime}\cap X_{b}$ 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 inequality now holds because of the following:

$\frac{|N(u^{\prime})\cap X_{b}|}{|N(u^{\prime})\cap
X_{a}|}\geq\frac{z-1}{|E(H)|}>\frac{\gamma_{B}}{1-\gamma_{B}}.\hfill\qed$

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

######  Claim 4.

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 4.

Let $(X_{a},X_{b})$ 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_{a},X_{b})$ is a Nash equilibrium.

By Claim A we note that $E_{1}\cup E_{2}$ contribute $W^{*}$ towards the
welfare of $(X_{a},X_{b})$. 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_{a}$ then the
edge between $u^{\prime}$ and $Z_{u}$ contribute $z(2\gamma_{B})$ to the
welfare. If $u^{\prime}\in X_{b}$ 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_{a}\cap V^{\prime}$ we therefore get the following welfare for
$(X_{a},X_{b})$.

$\displaystyle\mathcal{W}{(X_{a},X_{b})}$
$\displaystyle=W^{*}+\epsilon_{T}+(|V(H)|-|T|)\cdot
z(2(1-\gamma_{B}))+|T|\cdot 2z\gamma_{B}$
$\displaystyle=W^{*}+\epsilon_{T}+|V(H)|\cdot z(2(1-\gamma_{B}))-|T|\cdot
2z(1-2\gamma_{B})\hfill\qed$

######  Claim 5.

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 5.

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

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

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

$W(X_{a},X_{b})=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_{a}^{opt},X_{b}^{opt})\geq w(X_{a},X_{b})$.

$\displaystyle|T^{opt}|$
$\displaystyle=\frac{W^{*}+\epsilon_{T^{opt}}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{a},X_{b})}{2z(1-2\gamma_{B})}$
$\displaystyle=\left\lceil\frac{W^{*}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{a},X_{b})}{2z(1-2\gamma_{B})}\right\rceil$ (iv)
$\displaystyle\geq\left\lceil\frac{W^{*}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{a}^{opt},X_{b}^{opt})}{2z(1-2\gamma_{B})}\right\rceil$

By Claim 4, $w(X_{a}^{opt},X_{b}^{opt})\geq w(X_{a},X_{b})>W^{*}$. If
conditions (A) in Claim A is not satisfied for $(X_{a}^{opt},X_{b}^{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_{a}^{opt},X_{b}^{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_{a}^{opt},X_{b}^{opt})$. As $(X_{a}^{opt},X_{b}^{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_{a}$. By condition (B) in Claim B we note that $Y$ is a
transversal in $H$. Let $(Y_{a},Y_{b})$ be the $G$-extension of $Y$, and note
that, by Claim D, $(Y_{a},Y_{b})$ is a Nash equilibrium satisfying the
following, where $0\leq\epsilon_{Y}<2z(1-2\gamma_{B})$:

$w(X_{a}^{opt},X_{b}^{opt})\geq W(Y_{a},Y_{b})=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_{a}^{opt},X_{b}^{opt})}{2z(1-2\gamma_{B})}\\\
&=&\left\lceil\frac{W^{*}+|V(H)|\cdot
z(2-2\gamma_{B}))-w(X_{a}^{opt},X_{b}^{opt})}{2z(1-2\gamma_{B})}\right\rceil\\\
\end{array}$

By (iv) this implies 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_{a}^{opt},X_{b}^{opt})}{2z(1-2\gamma_{B})}\right\rceil.\hfill\qed$

This finishes the proof of the theorem. ∎

## References

  * Aloisio et al. (2021) Alessandro Aloisio, Michele Flammini, Bojana Kodric, and Cosimo Vinci.  Distance polymatrix coordination games.  In _IJCAI_ , pages 3–9, 2021.
  * Armstrong and Vickers (2001) Mark Armstrong and John Vickers.  Competitive price discrimination.  _The RAND Journal of Economics_ , 32(4):579–605, 2001.  ISSN 07416261.  URL http://www.jstor.org/stable/2696383.
  * Arthur (1989) W Brian Arthur.  Competing technologies, increasing returns, and lock-in by historical events.  _Economic Journal_ , 99(394):116–131, March 1989.  URL http://ideas.repec.org/a/ecj/econjl/v99y1989i394p116-31.html.
  * 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.  ISBN 978-1-84800-997-4.
  * 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.  ISSN 0899-8256.  doi: https://doi.org/10.1006/game.1998.0699.  URL https://www.sciencedirect.com/science/article/pii/S0899825698906996.
  * Blonski (2000) Matthias Blonski.  Characterization of pure strategy equilibria in finite anonymous games.  _Journal of Mathematical Economics_ , 34(2):225–233, 2000.  ISSN 0304-4068.  doi: https://doi.org/10.1016/S0304-4068(99)00008-7.  URL https://www.sciencedirect.com/science/article/pii/S0304406899000087.
  * Blume (1993) Lawrence E. Blume.  The statistical mechanics of strategic interaction.  _Games and Economic Behavior_ , 5(3):387 – 424, 1993.  ISSN 0899-8256.  doi: DOI:10.1006/game.1993.1023.  URL https://www.sciencedirect.com/science/article/pii/S0899825683710237.
  * 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.  doi: 10.4230/LIPIcs.ITCS.2020.73.  URL https://doi.org/10.4230/LIPIcs.ITCS.2020.73.
  * Bramoullé (2007) Yann Bramoullé.  Anti-coordination and social interactions.  _Games and Economic Behavior_ , 58(1):30–49, 2007.  URL http://www.sciencedirect.com/science/article/B6WFW-4J4HKBK-3/2/9a927ef100e59dd9d7e8962e1df47a06.
  * Cai and Daskalakis (2011) Yang Cai and Constantinos Daskalakis.  On minmax theorems for multiplayer games.  In _Proc. of SODA_ , pages 217–234, 2011.
  * Carbonell-Nicolau and McLean (2014) Oriol Carbonell-Nicolau and Richard P. McLean.  Refinements of nash equilibrium in potential games.  _Theoretical Economics_ , 9(3):555–582, 2014.  doi: https://doi.org/10.3982/TE1178.  URL https://onlinelibrary.wiley.com/doi/abs/10.3982/TE1178.
  * 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.
  * Conitzer and Sandholm (2008) Vincent Conitzer and Tuomas Sandholm.  New complexity results about nash equilibria.  _Games and Economic Behavior_ , 63(2):621–641, 2008.  ISSN 0899-8256.  doi: https://doi.org/10.1016/j.geb.2008.02.015.  URL https://www.sciencedirect.com/science/article/pii/S0899825608000936.  Second World Congress of the Game Theory Society.
  * 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.  ISSN 0033-5533.  doi: 10.2307/1885539.  URL https://doi.org/10.2307/1885539.
  * Crawford (1991) Vincent P. Crawford.  An “evolutionary” interpretation of van huyck, battalio, and beil’s experimental results on coordination.  _Games and Economic Behavior_ , 3(1):25–59, 1991.  URL http://www.sciencedirect.com/science/article/B6WFW-4CYGSTV-30/2/376135e70e4dc1de7b4f476f60f7a859.
  * 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.  URL http://dl.acm.org/citation.cfm?id=2936955.
  * 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.  doi: 10.1007/978-3-319-66700-3“˙8.  URL https://doi.org/10.1007/978-3-319-66700-3_8.
  * 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.  doi: 10.4230/LIPIcs.ICALP.2020.38.  URL https://doi.org/10.4230/LIPIcs.ICALP.2020.38.
  * 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.  doi: 10.1109/FOCS54457.2022.00022.  URL https://doi.org/10.1109/FOCS54457.2022.00022.
  * Deligkas et al. (2023) Argyrios Deligkas, Eduard Eiben, Gregory Z. Gutin, Philip R. Neary, and Anders Yeo.  Complexity dichotomies for the maximum weighted digraph partition problem.  _CoRR_ , abs/2307.01109, 2023.  doi: 10.48550/arXiv.2307.01109.  URL https://doi.org/10.48550/arXiv.2307.01109.
  * 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.  ISSN 00223808.  URL http://www.jstor.org/stable/1837095.
  * Eaves (1973) B Curtis Eaves.  Polymatrix games with joint constraints.  _SIAM Journal on Applied Mathematics_ , 24(3):418–423, 1973.
  * 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.  ISSN 00129682.  URL http://www.jstor.org/stable/2951493.
  * Farrell and Saloner (1985) Joseph Farrell and Garth Saloner.  Standardization, compatibility, and innovation.  _RAND Journal of Economics_ , 16(1):70–83, Spring 1985.  URL http://ideas.repec.org/a/rje/randje/v16y1985ispringp70-83.html.
  * Foster and Young (1990) D. Foster and P. Young.  Stochastic evolutionary game dynamics.  _Theoretical Population Biology_ , 38:219–232, 1990.  URL citeseer.ist.psu.edu/foster90stochastic.html.
  * Foster and Young (1998) Dean P Foster and H.Peyton Young.  On the nonconvergence of fictitious play in coordination games.  _Games and Economic Behavior_ , 25(1):79–96, 1998.  ISSN 0899-8256.  doi: https://doi.org/10.1006/game.1997.0626.  URL https://www.sciencedirect.com/science/article/pii/S0899825697906266.
  * 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.  ISBN 0-7167-1045-5.
  * Gilboa and Zemel (1989) Itzhak Gilboa and Eitan Zemel.  Nash and correlated equilibria: Some complexity considerations.  _Games and Economic Behavior_ , 1(1):80–93, 1989.  ISSN 0899-8256.  doi: https://doi.org/10.1016/0899-8256(89)90006-7.  URL https://www.sciencedirect.com/science/article/pii/0899825689900067.
  * Granovetter (1978) Mark Granovetter.  Threshold models of collective behavior.  _American Journal of Sociology_ , 83(6):1420–1443, 1978.  ISSN 00029602, 15375390.  URL http://www.jstor.org/stable/2778111.
  * Hellwig (2003) Martin F. Hellwig.  Public-Good Provision with Many Participants.  _The Review of Economic Studies_ , 70(3):589–614, 07 2003.  ISSN 0034-6527.  doi: 10.1111/1467-937X.00257.  URL https://doi.org/10.1111/1467-937X.00257.
  * 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.  ISSN 0022-0531.  doi: https://doi.org/10.1006/jeth.1998.2485.  URL https://www.sciencedirect.com/science/article/pii/S0022053198924851.
  * Howson Jr (1972) Joseph T Howson Jr.  Equilibria of polymatrix games.  _Management Science_ , 18(5-part-1):312–318, 1972.
  * 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.
  * 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.  ISSN 00129682.  URL http://www.jstor.org/stable/2951777.
  * Katz and Shapiro (1985) Michael L Katz and Carl Shapiro.  Network externalities, competition, and compatibility.  _American Economic Review_ , 75(3):424–440, June 1985.  URL http://ideas.repec.org/a/aea/aecrev/v75y1985i3p424-40.html.
  * 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.  doi: 10.1126/science.1127207.  URL http://www.sciencemag.org/cgi/content/abstract/313/5788/824.
  * Korte and Vygen (2011) Bernhard H Korte and Jens Vygen.  _Combinatorial optimization_ , volume 1.  Springer, 2011.
  * Kreindler and Young (2013) Gabriel E. Kreindler and H. Peyton Young.  Fast convergence in evolutionary equilibrium selection.  _Games and Economic Behavior_ , 80(0):39 – 67, 2013.  ISSN 0899-8256.  doi: http://dx.doi.org/10.1016/j.geb.2013.02.004.  URL http://www.sciencedirect.com/science/article/pii/S0899825613000262.
  * Lim and Neary (2016) Wooyoung Lim and Philip R. Neary.  An experimental investigation of stochastic adjustment dynamics.  _Games and Economic Behavior_ , 100:208–219, 2016.  ISSN 0899-8256.  doi: https://doi.org/10.1016/j.geb.2016.09.010.  URL https://www.sciencedirect.com/science/article/pii/S0899825616301099.
  * 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.  doi: 10.1177/1532673X09337184.  URL https://doi.org/10.1177/1532673X09337184.
  * 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.  URL http://www.jstor.org/stable/2567028.
  * 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.  ISSN 00130133, 14680297.  URL http://www.jstor.org/stable/20485295.
  * Nash (1951) John Nash.  Non-cooperative games.  _The Annals of Mathematics_ , 54(2):286–295, September 1951.  URL http://www.jstor.org/stable/1969529.
  * Nash (1950) John F. Nash.  Equilibrium points in n-person games.  _Proceedings of the National Academy of Sciences of the United States of America_ , 36(1):48–49, 1950.  ISSN 00278424.  URL http://www.jstor.org/stable/88031.
  * Neary (2012) Philip R. Neary.  Competing conventions.  _Games and Economic Behavior_ , 76(1):301 – 328, 2012.  ISSN 0899-8256.  doi: 10.1016/j.geb.2012.06.003.  URL http://www.sciencedirect.com/science/article/pii/S0899825612000875.
  * 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.  doi: 10.22574/jmid.2017.12.005.  URL https://ideas.repec.org/a/jmi/articl/jmi-v2i1a5.html.
  * Neary (2011) Philip Ruane Neary.  _Multiple-Group Games_.  PhD thesis, University of California, San Diego, 2011.
  * Newton and Sercombe (2020) Jonathan Newton and Damian Sercombe.  Agency, potential and contagion.  _Games and Economic Behavior_ , 119:79–97, 2020.  ISSN 0899-8256.  doi: https://doi.org/10.1016/j.geb.2019.10.007.  URL https://www.sciencedirect.com/science/article/pii/S0899825619301538.
  * 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.  ISSN 07416261, 17562171.  URL http://www.jstor.org/stable/4135258.
  * Oyama and Takahashi (2020) Daisuke Oyama and Satoru Takahashi.  Generalized belief operator and robustness in binary-action supermodular games.  _Econometrica_ , 88(2):693–726, 2020.  doi: https://doi.org/10.3982/ECTA17237.  URL https://onlinelibrary.wiley.com/doi/abs/10.3982/ECTA17237.
  * Peski (2010) Marcin Peski.  Generalized risk-dominance and asymmetric dynamics.  _Journal of Economic Theory_ , 145(1):216–248, January 2010.  URL http://ideas.repec.org/a/eee/jetheo/v145y2010i1p216-248.html.
  * Peski (2021) Marcin Peski.  Fuzzy conventions, 2021.  URL https://arxiv.org/abs/2108.13474.
  * Schelling (1960) Thomas C. Schelling.  _The Strategy of Conflict_.  Harvard University Press, 1960.
  * 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.  ISSN 00129682.  URL http://www.jstor.org/stable/2692226.
  * 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.  URL http://ideas.repec.org/a/aea/aecrev/v80y1990i1p234-48.html.
  * Young (1993) H. Peyton Young.  The evolution of conventions.  _Econometrica_ , 61(1):57–84, 1993.  ISSN 00129682.  URL http://www.jstor.org/stable/2951778.
  * Young (2001) H. Peyton Young.  _Individual Strategy and Social Structure: An Evolutionary Theory of Institutions_.  Princeton, NJ: Princeton University Press, January 2001.  ISBN 0691086877.  URL http://www.worldcat.org/isbn/0691086877.