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

1 Introduction

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

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

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

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

In this paper, we adopt the most fundamental framework of multi-player coordination, and model the two above-mentioned environments as binary-action polymatrix games [Janovskaya, 1968]. The expressive power of polymatrix games has made them the "go-to" method to model problems ranging from coordination games on graphs [Apt et al., 2017; Apt et al., 2022; Rahn and Sch¨afer, 2015] and additively separable hedonic games [Bogomolnaia and Jackson, 2002], to building-blocks for hardness reductions [Chen et al., 2009; Daskalakis et al., 2009; Deligkas , 2022;

Rubinstein, 2018] and applications in protein-function prediction and semi-supervised learning [Elezi et al., 2018; Vascon et al., 2020].

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

1.1 Our Contribution

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

Objective (i): maximize social welfare.

Objective (ii): maximize a potential function; when the game is pairwise-potential.

Objective (iii): find a welfare-optimal Nash equilibrium.

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

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

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

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

1.2 Further RelatedWork

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

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

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

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

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

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

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

Nash Equilibria in Polymatrix Games. Computational aspects of (approximate) Nash equilibria in polymatrix games received a lot of attention over the years, starting from classical results from fifty years ago [Eaves, 1973; Howson Jr, 1972; Howson Jr and Rosenthal, 1974; Miller and Zucker, 1991], to more recent results [Chen et al., 2009; Daskalakis et al., 2009; Rubinstein, 2018], and the very recent dichotomy for the complexity of finding any approximate well-supported Nash equilibrium in general binaryaction polymatrix games [Deligkas et al., 2022]. 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 in [Deligkas et al., 2017], while [Barman et al., 2015; Deligkas et al., 2020; Elkind et al., 2006; Ortiz and Irfan, 2017] study games with tree-underlying structure. Finally, [Deligkas et al., 2016] provides an experimental comparison of various algorithms for polymatrix games.

The full version of the paper, containing all proofs can be found in [Deligkas et al., 2023].

2 Preliminaries

Given a 2 × 2 matrix M, we denote by m11, m12, m21 and m22 the entries of M, such that M = [ m11 m12 m21 m22 ]. For any graph G, we denote V (G) and E(G) the sets of vertices and edges respectively; if the graph is directed, we use A(G) instead to denote the set of arcs of the graph. We assume knowledge of standard notions of directed graphs [BangJensen and Gutin, 2009].

An n-player binary-action polymatrix game is defined by a graph G, where each vertex represents a player. Each player i ∈ V (G) has two actions called one and two. For each edge ij ∈ E(G), there is a 2×2 two-player game (Πij , Πji ), where matrix Πij gives the payoffs that player i obtains from their interaction with player j, and likewise matrix Πji gives the payoffs player j gets with the interaction with player i.

A pure strategy profile s = (s1, s2, . . . , sn) specifies an action for each of the players; we will use S to denote the set of all strategy profiles. It is convenient to think of si = (1, 0)T when player i chooses action one and si = (0, 1)T when they choose action two. For each strategy profile s ∈ S, the payoff of player i is pi(s) := sTi · ∑j : ij∈E(G) Πij · sj. In other words, the payoff obtained by a player is the sum of the payoffs obtained from the interaction with every neighboring player, where the same action must be used with each.

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

Definition 1. The social welfare of strategy profile s is W(s) := ∑i∈V pi(s).

We denote by s-i the partial strategy profile consisting of the strategies of the n- 1 players other than i. That is, from the perspective of player i using strategy si, the strategy profile s can be viewed as (si, s-i).

A strategy profile s∗ is a pure Nash equilibrium if no player can strictly increase their payoff by unilaterally changing their strategy choice. Formally, s∗ is a Nash equilibrium, if for every player i and every si ̸= s∗i it holds that pi(s∗i , s∗-i ) ≥ pi(si, s∗-i ).

2.1 Classes of Polymatrix Games

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

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

Anti-coordination Games. In an anti-coordination polymatrix game, each player's payoff increases with the number of neighbors who choose a different action. Formally, a binary-action polymatrix game is anti-coordination if for every edge ij ∈ E the strategy profiles (one, two) and (two, one) are Nash equilibria for the two-player game (Πij , Πji ).

Potential Games. A strategic game is a potential game [Shapley and Monderer, 1996] if the incentive of all players to change their strategy can be expressed using a single function called the potential function. Potential games possess many desirable properties: pure strategy equilibria correspond to local optima of the potential function so the existence of a pure strategy equilibrium is assured. Formally, a game is a potential game if there exists a function Φ : S → R such that for every player i, for all s-i, and all pairs of actions s′i , s′′ i ∈ S

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

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

3 The MWDP Problem

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

MWDP(F). Given a family F of 2 × 2 matrices, an instance of MWDP(F) is given by a tuple (D, c, f), where:

• D is an oriented graph on n vertices (that is, a directed graph without any 2-cycle);
• c : A(D) →R+ assigns positive weights to arcs;
• f : A(D) → F, is an assignment of a matrix from the family of matrices F to each arc in D.

Given a partition, P = (X1,X2) of V (D), the weight of an arc uv ∈ A(D) is defined as follows, where M = f(uv) is the matrix in F assigned to the arc uv.

Given a partition P, the weight of D, denoted by wP (D), is defined as the sum of the weights on every arc uv. That is, wP (D) = ∑a∈A(D) wP (a). The goal is to find a partition P that maximizes wP (D).

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

3.1 ADichotomy for the Complexity of MWDP(F )

Our main result shows that the tractability of solving MAXIMUMWEIGHTEDDIGRAPHPARTITION depends on properties of the matrices in the family of matrices F. We now introduce three properties that a matrix M ∈ F may satisfy.

• Property (a): m11 +m22 ≥ m12 +m21.
• Property (b): m11 =max{m11,m22,m12,m21}.
• Property (c): m22 =max{m11,m22,m12,m21}.

Using the three properties above, we present a dichotomy for the complexity of MWDP(F) with respect to F.

Theorem 2. An instance (D, c, f) of MWDP(F) can be solved in polynomial time if one of the following holds.

1. All matrices in F satisfy Property (a).
2. All matrices in F satisfy Property (b).
3. All matrices in F satisfy Property (c).

In every other case, MWDP(F) is NP-hard.

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

1 Due to space constraints, the formal proof appears in the Supplementary material, alongside other missing proofs.

Lemma 3. If all matrices in F satisfy Property (a), then MWDP(F) can be solved in polynomial time.

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

• Let w(uv) = c(uv) · (m11 + m22 - m12 - m21)/2. Note w(uv) is the weight of the undirected edge uv in H associated with the arc uv ∈ A(D) and that this weight is non-negative; this is guaranteed by Property (a) and it is crucial for the correctness of the lemma.
• Add c(uv) · (-m22)/2 to w(su).
• Add c(uv) · (-m22)/2 to w(sv).
• Add c(uv) · (m21 -m11 -m12)/2 to w(tu).
• Add c(uv) · (m12 -m11 -m21)/2 to w(tv).

Let θ be the smallest possible weight of all edges in H after we completed the above process (θ may be negative). Now consider the weight function w∗ obtained from w by subtracting θ from all edges incident with s or t. That is, w∗ (uv) = w(uv) if {u, v} ∩ {s, t} = ∅ and w∗ (uv) = w(uv) -θ otherwise. Note that all w∗ -weights in H are nonnegative. We will show that for any (s, t)-cut, (X1,X2) in H, i.e., (X1,X2) partitions V (H) and s ∈ X1 and t ∈ X2, the w∗ -weight of the cut is equal to -wP (D) - |V (D)| · θ, where P is the partition (X1 \{s}, X2 \{t}) in D. Therefore, a minimum-weight cut in H maximizes wP (D) in D.

Let (X1,X2) be any (s, t)-cut in H. For every u ∈ V (D) we note that exactly one of the edges su and ut will belong to the cut. Therefore, we note that the w∗ -weight of the cut is |V (D)| · θ less than the w-weight of the cut. It therefore suffices to show that the w-weight of the cut is -wP (D) (where P is the partition (X1 \ {s}, X2 \ {t}) of V (D)).

Let (X1,X2) be some (s, t)-cut. There are four possibilities for any uv ∈ A(D), which follow from the definition of the w-weights.

• u, v ∈ X1. In this case, we have added -c(uv) · m11 to the w-weight of the (s, t)-cut.
• u, v ∈ X2. In this case, we have added -c(uv) · m22 to the w-weight of the (s, t)-cut.
• u ∈ X1 and v ∈ X2. In this case, we have added -c(uv) · m12 to the w-weight of the (s, t)-cut.
• v ∈ X1 and u ∈ X2. In this case, we have added -c(uv) · m21 to the w-weight of the (s, t)-cut.

Therefore we note that in all cases we have added -wP (uv) to the w-weight of the (s, t)-cut, (X1,X2). So the total w-weight of the (s, t)-cut is -wP (D) as desired.

Analogously, if we have a partition P = (X1,X2) of V (D), then adding s to X1 and t to X2 we obtain a (s, t)-cut with w-weight -wP (D) of H. As we can find a minimum w∗ -weight cut in H in polynomial time [Korte and Vygen, 2011] we can find a partition P = (X1,X2) of V (D) with minimum value of -wP (D), which corresponds to the maximum value of wP (D). Therefore, MWDP(F) can be solved in polynomial time in this case.

4 Social Welfare and Potential Maximization

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

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

• D has the same vertex-set as G. In addition, for every edge of G we add a directed edge in D with arbitrary orientation. An edge from u to v specifies that player u chooses a row and player v chooses a column in the two-player game played between the two corresponding players.
• c(uv) = 1 for every oriented edge uv ∈ A(D).
• For each two-player game (Πuv ,Πvu ), with uv ∈ E(G), we create the welfare-matrixW uv := Πuv +Πvu , and we associate it with the oriented edge between u and v as follows:
• f(uv) =W uv , if we have added the arc uv;
• f(uv) = (W uv )T , if we have added the arc vu.

The reduction above induces an immediate translation between strategy profiles and partitions. Player v chooses action one if and only if the corresponding vertex v in D belongs to X1. Conversely, player v chooses action two if and only if the corresponding vertex v in D belongs to X2.

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

Lemma 4. For every possible strategy profile s, it holds that W(s) = wP (s) (D).

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

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

• wuv 11 +wuv 22 ≥ wuv 12 +wuv 21 for every uv ∈ E(G).
• wuv 11 ≥max{wuv 12 , wuv 21 , wuv 22 } for every uv ∈ E(G).
• wuv 22 ≥max{wuv 11 , wuv 12 , wuv 21 } for every uv ∈ E(G).

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

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

Theorem 5 implies two immediate corollaries for coordination polymatrix games. Firstly, for every welfare-matrix W uv of a pure-coordination game it holds that wuv 11 +wuv 22 ≥ wuv 12 + wuv 21 . Second, it is not difficult to construct anticoordination games where wuv 11 +wuv 22 < wuv 12 +wuv 21 . 2

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

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

Pairwise-Potential Games via MWDP. Next we show how to reduce the problem of maximizing the potential in pairwise-potential binary-action polymatrix games to the MWDP problem. Observe that for this class of games, every pairwise-potential Φuv can be written as a 2 × 2 potential-

MWDP we will follow a similar approach as before. This time though, we use potential-matrices: Φuv will be associated with the oriented edge between u and v as follows.

• f(uv) = Φuv , if we have added the arc uv;
• f(uv) = (Φuv )T , if we have added the arc vu.

To reduce from MWDP to potential maximization, let the matrix M on arc uv with weight c be given by the potential matrix above. Such a matrix is the potential of a 2 × 2

before, we have reduced in both directions and so we have a one-to-one translation between partitions and strategy profiles. So, if we denote P (s) the partition associated with strategy profile s we get the following lemma, where Φ(s) is the sum of the pairwise potentials.

Lemma 8. For every possible strategy profile s of a pairwisepotential polymatrix game, it holds that Φ(s) = wP(s) (D).

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

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

• ϕuv 11 + ϕuv 22 ≥ ϕuv 12 + ϕuv 21 for every uv ∈ E(G).
• ϕuv 11 ≥max{ϕuv 12 , ϕuv 21 , ϕuv 22 } for every uv ∈ E(G).
• ϕuv 22 ≥max{ϕuv 11 , ϕuv 12 , ϕuv 21 } for every uv ∈ E(G).

2 The construction of Appendix C.2 from Cai and Daskalakis [2011] creates these types of welfare matrices.

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

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

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

Proof. We will show that when the game is purecoordination, for every uv ∈ E(G) the potential-matrix Φuv satisfies that ϕuv 11 +ϕuv 22 ≥ ϕuv 12 +ϕuv 21 . Recall, since the game is pure-coordination the following hold.

• Outcome (one, one), that corresponds to ϕuv 11 of the potential-matrix, is a Nash equilibrium for the twoplayer game played on uv. So, since this is a Nash equilibrium and the two-player game is potential, any deviation from (one, one) will lower the payoffs of both players, and thus it will lower the value of the pairwisepotential. Therefore, ϕuv 11 ≥max{ϕuv 12 , ϕuv 21 }.
• Outcome (two, two), that corresponds to ϕuv 22 of the potential-matrix, is a Nash equilibrium for the twoplayer game played on uv. Using verbatim the arguments as before, it follows that ϕuv 22 ≥max{ϕuv 12 , ϕuv 21 }.

Our claim follows by combining the two bullets above.

5 Welfare-optimal Nash Equilibria

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

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

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

Threshold Games. A threshold-game is a binary-action anonymous pure-coordination polymatrix game, where every player u is associated with a parameter γu ∈ [0, 1] and their

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

Theorem 11. The complexity of finding a welfare-maximizing Nash equilibrium in a threshold-game with two thresholds, γA, γB, such that 0 ≤ γB ≤ γA ≤ 1, is as follows.

1. If γA ≤ 1/2 the problem is polynomial time.
2. If γB ≥ 1/2 the problem is polynomial time.
3. If γB = 0 and γA = 1 the problem is polynomial time.
4. In all other cases the problem is NP-hard.

Proof sketch. Cases 1-2. If γA ≤ 1/2, or γB ≥ 1/2, then all players prefer the same action and selecting that action for each player gives a maximum-welfare Nash equilibrium.

Case 3. Now, let γA = 1 and let γB = 0 and G be a graph and let (A,B) be a partition of V (G), so that if u ∈ Y ⇔ γu = γY , where Y ∈ {A, B}. We want to find a Nash equilibrium, (Xone,Xtwo), of maximum welfare, where Xi denotes the set of players that choose action i ∈ {one, two}.

Let (Xone, Xtwo) be a Nash equilibrium of G. This implies that all vertices in Xtwo ∩ A only have edges to vertices in Xtwo (as otherwise it is not a Nash equilibrium). Note that this means that any connected component C in G[A] is either subset of Xone or a subset of Xtwo, else one can find an edge from a vertex in Xtwo ∩ A to a vertex in Xone. Analogously, every connected component of G[B] is either a subset of Xone or a subset of Xtwo. Finally, given a connected component CA of G[A] and a connected component CB of G[B], if there is an edge in G between a vertex u ∈ CA and a vertex v ∈ CB, then it is not possible that CB ⊆ Xone and CA ⊆ Xtwo.

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

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

We will show the NP-hardness result via a reduction from MINIMUM TRAVERSAL problem in 3-uniform hypergraphs 3 , which is known to be NP-hard [Garey and Johnson, 1979]. A 3-uniform hypergraph H has a set of vertices V (H) and a set of hyperedges E(H), where every hyperedge e ∈ E(H) is a subset of vertices of size exactly 3. A traversal of H is a set of vertices X such that X ∩ e ̸= ∅ for every edge e ∈ E(H). MINIMUM TRAVERSAL problem asks to find a traversal of the minimum size.

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

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

• Cliques CA, CB that are "sufficiently large"; the sizes are selected in a way such that in any welfare-optimal Nash equilibrium, players in CA choose action one and in CB choose action two. A contains precisely the players in CA, all the remaining players are in B.
• Vertex sets R = ⋃e∈E(H) {re}, V ′ = ⋃u∈V (H) {u′ }. There is an edge between re and u′ iff u ∈ e. Moreover, there are cA edges from every re to CA and cB edges from every re to CB. cA and cB are selected so that if every player in CA uses one and in CB two, then re (recall that re ∈ B) prefers one if at least one of its

3 The problem is also called 3-HITTING SET.

exactly three neighbors in V ′ chooses one.

• For every u ∈ V (H), vertex set Zu of size z that is to be fixed. There is an edge from every vertex z ∈ Zu to the vertex u′ ∈ V ′ . Hence, in any Nash equilibrium z chooses the same strategy as u′ . This also allows u′ the freedom of choosing one even though u′ ∈ B.

By a clever selection of the sizes, we can achieve that if s is a welfare-maximizing Nash equilibrium that partitions players into (Xone, Xtwo) by the strategy they are using, then:

1. V (CA) ∪R ⊆Xone, V (CB) ⊆Xtwo. Intuitively, this is because the choice of cA and cB guarantees that the loss of utility for the players in CA when a player re ∈ R selects two, is larger than the gain players in V (G) \ V (CA) can get from this selection.
2. For every e ∈ E(H), re has a neighbor in V ′ ∩Xone;

Note that the second condition states that V ′∩Xone is a traversal of H. We now observe that because V ′ ∪ ⋃u∈V (H) Zu ⊆ B, there is a significant gain in overall welfare if we decrease the number of players in V ′ that choose action one, as long as we preserve the above two conditions. Therefore, a welfaremaximizing Nash equilibrium not only gives a traversal, but a minimum traversal in H.

6 Discussion

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

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

Acknowledgements

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