# constrained_pure_nash_equilibria_in_polymatrix_games__9265344d.pdf

Constrained Pure Nash Equilibria in Polymatrix Games

Sunil Simon

IIT Kanpur Kanpur, India

Dominik Wojtczak

University of Liverpool Liverpool, U.K.

We study the problem of checking for the existence of constrained pure Nash equilibria in a subclass of polymatrix games deﬁned on weighted directed graphs. The payoff of a player is deﬁned as the sum of nonnegative rational weights on incoming edges from players who picked the same strategy augmented by a ﬁxed integer bonus for picking a given strategy. These games capture the idea of coordination within a local neighbourhood in the absence of globally common strategies. We study the decision problem of checking whether a given set of strategy choices for a subset of the players is consistent with some pure Nash equilibrium or, alternatively, with all pure Nash equilibria. We identify the most natural tractable cases and show NP or co NP-completness of these problems already for unweighted DAGs.

1 Introduction Identifying subclasses of games where equilibria is tractable is an important problem in algorithmic analysis of multiplayer games. Pure Nash equilibria (NEs) may not exist in games and checking whether a game has a pure NE is in general a hard problem. Even for subclasses of games in which a pure NE is guaranteed to exists (for instance, potential games) computing one remains PLS-hard (Fabrikant, Papadimitriou, and Talwar 2004). Although, Nash s theorem guarantees the existence of mixed strategy NE in all ﬁnite games, computing one is still a hard problem. Therefore, identifying restricted classes of games where equilibrium computation is tractable and also precisely identifying the borderline between tractability and hardness in such restricted classes is of obvious interest. In this paper, we study the borderline of tractability in a natural subclass of games where the utilities of players are restricted to be pairwise separable. These are called polymatrix games (Janovskaya 1968) and they form an abstract model that is useful to analyse strategic behaviour of players in games formed via pairwise interactions. In polymatrix games, the payoff for each player is the sum of the payoffs he gets from individual two

Supported by the Research-I Foundation, IIT Kanpur and the Liverpool-India fellowship, University of Liverpool. Supported by EPSRC grant EP/M027651/1. Copyright c 2017, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

player games he plays against every other player. Polymatrix games are well-studied in the literature. They include game classes with good computational properties like the two-player zero-sum games. They also have applications in areas such as artiﬁcial neural networks (Miller and Zucker 1991) and machine learning (Erdem and Pelillo 2012). In terms of tractability, the restriction to pairwise interactions does not immediately ensure the existence of efﬁcient algorithms. Computing a mixed strategy Nash equilibrium remains PPAD-complete (Cai and Daskalakis 2011) and checking for the existence of a pure NE is NP-complete in general. This motivates the need to further analyse the type of pairwise interactions that would ensure tractability. In this paper, we argue that another important factor which inﬂuences tractability is the structure of the underlying interaction graph and presence of individual preferences (that we call bonuses). The main restriction that we impose on polymatrix games is that each pairwise interaction forms a coordination game. Henceforth, we will refer to these games simply as coordination games on graphs. Coordination games are often used in game theory to model situations where players attain maximum payoff when they agree on a common strategy. The game model that we study, extends coordination games to the network setting where payoffs need not always be symmetric and players coordinate within a certain local neighbourhood. The neighbourhood structure is speciﬁed by a ﬁnite directed graph whose nodes correspond to the players. Each player chooses a colour from a set of available colours. The payoff of a player is the sum of weights on the edges from players who choose the same colour and a ﬁxed bonus for picking that particular colour. This game model is closely related to various well-studied classes of games. For instance, coordination games on graphs are graphical games (Kearns, Littman, and Singh 2001) and they are also related to hedonic games (Dreze and Greenberg 1980; Bogomolnaia and Jackson 2002). In hedonic games, the payoff of each player depends solely on the set of players that selected the same strategy. The coalition formation property inherent to coordination games on graphs make the game model relevant to cluster analysis. The problem of clustering has been studied from a game theoretic perspective for instance in (Feldman, Lewin-Eytan, and Naor 2012; Pelillo and Bul o 2014).

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

Coordination games on graphs constitute a game model which can be useful for analysing the adoption of a product or service within a network of agents interacting with each other in their local neighbourhoods. For example, consider the selection of a mobile phone operator. The interaction between users can be represented by a coordination game where the weight of the edge from i to j represents the total cost of calls from j to i. Also, the bonus function can represent individual preferences of users over the providers. Now suppose that mobile network operators allow free calls among its users. Then each mobile phone user faces a strategic choice of picking an operator that maximises his cost savings or, in the case of unweighted graphs, maximises the number of people he can call for free. If players are allowed to freely switch their operator based on their friends choices, then the stable market states correspond to pure Nash equilibria in this game. One can observe similar interactions in peer-to-peer networks, social networks and photo sharing platforms. A similar game model based on undirected graphs was introduced in (Apt et al. 2014) and further studied in (Rahn and Sch afer 2015). The transition from undirected to directed graphs drastically changes the status of the games. For instance, in the case of undirected graphs, coordination games are potential games where as in the directed case, pure NE may not even exist. Moreover, the problem of determining the existence of pure NEs is NP-complete for coordination games on directed graphs (Apt, Simon, and Wojtczak 2016). However, pure NE always exists for several natural classes of graphs (Simon and Wojtczak 2016b). However, in many practical situations, ﬁnding just one pure Nash equilibrium may not be enough. In fact, there can be exponentially many Nash equilibria, each with a different payoff to each player (see Example 2 in (Simon and Wojtczak 2016a)). Ideally, we would like to ask for the existence of a Nash equilibrium satisfying some given constraints. In this paper, we focus on checking whether a partial strategy proﬁle (i.e. strategy choices for a subset of the players) is consistent with some pure Nash equilibrium or, alternatively, with all pure Nash equilibria. We will refer to these as NE and NE decision problem, respectively. We identify the most natural tractable cases and show NP or co NP-completness of these problems already for unweighted DAGs. Related work. The complexity of checking for the existence of pure Nash equilibria in a game crucially depends on the representation of the game. Normal form representation can be exponential in the number of players whereas graphical games and polymatrix games provide a more concise representation of strategic form games. While checking for the existence of pure Nash equilibria can be solved in LOGSPACE for games in normal form, it is NP-complete for graphical games even when the payoff of each player depends only on the strategy choices of at most three other players (Gottlob, Greco, and Scarcello 2005). On the other hand, it is solvable in polynomial time for graphical games whose dependency graph has a bounded treewidth (Gottlob, Greco, and Scarcello 2005) or when each player has only two possible strategies (Thomas and van Leeuwen 2015).

For polymatrix games, checking for the existence of a pure Nash equilibrium is NP-complete even when all its individual 2-player games are win-loss ones (Apt, Simon, and Wojtczak 2016). Gilboa and Zelmel (1989) were the ﬁrst to study the computational complexity of decision problems for mixed Nash equilibria with additional constraints for two player games in normal form. For many natural constraints the corresponding decision problems were shown to be NP-hard. Further hardness results were shown in (Conitzer and Sandholm 2008) and (Bil o and Mavronicolas 2012). The existence of constrained pure NE can be solved in LOGSPACE for normal form games simply by checking every pure strategy proﬁle. For graphical games the problem is NP-hard even without any constraints, but because of the special structure of our games, this result does not directly apply to our setting. On the other hand, constrained pure NE can be found in polynomial time for graphical games played on graphs with a bounded treewidth (Greco and Scarcello 2009). We are not aware of any prior work on this problem for polymatrix games. Our paper is the ﬁrst to identify several subclasses of polymatrix games for which the existence problem of a constrainted Nash equilibrium is tractable.

2 Background

A strategic game G = (S1, . . . , Sn, p1, . . . , pn) with n > 1 players consists of a non-empty set Si of strategies and a payoff function pi : S1 Sn R, for each player i {1, 2, . . . , n}. Let S := S1 Sn and let us call each element s S a joint strategy. Given a joint strategy s, we denote by s(i) the strategy of player i in s. We abbreviate the sequence (s(j))j =i to s i and occasionally write (s(i), s i) instead of s. We call a strategy s(i) of player i a best response to a joint strategy s i of his opponents if for all x Si, pi(s(i), s i) pi(x, s i). We do not consider mixed strategies in this paper. Given two joint strategies s and s, we say that s is a deviation of the player i from s if s i = s i and s(i) = s (i). If in addition pi(s ) > pi(s), we say that the deviation s from s is proﬁtable for player i. We call a joint strategy s a (pure) Nash equilibrium if no player can proﬁtably deviate from s. For any given strategic game G, let NE(G) denote the set of all (pure) Nash equilibria in G. We now introduce the class of games we are interested in. Fix a ﬁnite set of colours M. A weighted directed graph (G, w) is a structure where G = (V, E) is a graph without self loops over the vertices V = {1, . . . , n} and w is a function that associates with each edge e E, a nonnegative rational weight we Q 0. We say that a node j is a successor of the node i, and i is a predecessor of j, if there is an edge i j in E. Let Ni denote the set of all predecessors of node i in the graph G. By a colour assignment we mean a function that assigns to each node of G a ﬁnite non-empty set of colours. A bonus is a function β that to each node i and a colour c assigns an integer β(i, c). Given a weighted graph (G, w), a colour assignment C : V 2M \ { } and a bonus function β : V M Z, a strategic game G(G, w, C, β) is deﬁned as follows:

2 {a, c} 3 {b, c}

8 {c} 9 {b}

Figure 1: Unweighted coordination game with no NE.

the players are the nodes; the set of strategies of player (node) i is the set of colours C(i); the payoff function pi(s) :=

j Ni: s(i)=s(j) wj i + β(i, s(i)). So each node simultaneously chooses a colour and its payoff is the sum of the weights of the edges from its neighbours that chose the same colour augmented by a bonus to the node from choosing this colour. We call these games coordination games on directed graphs, from now on just coordination games. When the weights of all the edges are 1, we obtain a coordination game whose underlying graph is unweighted. In this case, we simply drop the function w from the description of the game and the payoff function is deﬁned by pi(s) := |{j Ni | si = sj}| + β(i, s(i)). Similarly if all the bonuses are 0, we obtain a coordination game without bonuses. Likewise, to denote this game we omit the function β. Note that positive integer weights or bonuses can be simulated by adding unweighted edges to the graph. However, if these values are represented in binary, such an operation can increase the size of the graph exponentially.

Example 1 Consider the unweighted directed graph and the colour assignment depicted in Figure 1. Take the joint strategy s that consists of the underlined strategies. Then the payoffs are as follows: 0 for the nodes 1, 7, 8, and 9; 1 for the nodes 2, 4, 5, and 6; 2 for the node 3. Note that s is not a Nash equilibrium. For instance, node 1 can profitably deviate to colour a. In fact the coordination game associated with this graph does not have a Nash equilibrium. Note that for nodes 7, 8 and 9 the only option is to select the unique strategy in its strategy set. The best response for nodes 4, 5 and 6 is to always select the same strategy as nodes 1, 2 and 3, respectively. Therefore, to show that the game does not have a Nash equilibrium, it sufﬁces to consider the strategies of nodes 1, 2 and 3. We denote this by the triple (s1, s2, s3). Below we list all such joint strategies and we underline a strategy that is not a best response to the choice of other players: (a, a, b), (a, a, c), (a, c, b), (a, c, c), (b, a, b), (b, a, c), (b, c, b) and (b, c, c). 2

Let Q V be a nonempty subset of all the nodes of a given graph G. A query is a function q : Q M which satisﬁes the following property: for all i Q, q(i) C(i). We say that a query q is consistent with a strategy proﬁle s

Graph Class NE NE 2 colours+monochromatic query O(|G|) O(|G|) 2 colours+polychromatic query NP-comp. O(|G|) DAGs+3 colours+singleton query NP-comp. co NP-comp. simple cycles O(|G|) O(m |G|) DAGs with out-degree 1 O(|G|2.5) O(|G|2.5) colour complete graphs no bonuses O(nm m!) O(nm m!)

Table 1: Summary of the results. The last two classes are unweighted; a simple reduction from the PARTITION problem and its complement, shows NP and co NP hardness of their NE and NE problems, respectively, in the weighted case.

iff q = s|Q, i.e. q(i) = s(i) for all i Q. We call a query q : Q M monochromatic if for all i, j Q, q(i) = q(j) and otherwise we call the query polychromatic. A query q is said to be singleton if |Q| = 1. Obviously every singleton query is also a monochromatic one. In this paper, we study the following decision questions. Given a graph G = (V, E), weights w, colour assignment C, bonus function β, and query q.

NE problem: In G(G, w, C, β), is there a Nash equilibrium that is consistent with q?

NE problem: In G(G, w, C, β), is every Nash equilibrium consistent with q?

Formally, NE problem asks if there exists s NE(G) such that q = s|Q, while the NE problem asks whether for all s NE(G) it is the case that q = s|Q. Note that NE is not a complement of NE. Actually, any non-singleton NE query can be reduced to a series of singleton NE queries q|{i} for every player i Q. Note that trivially NE NP and NE co NP, because checking whether a joint strategy is a Nash equilibrium and is consistent with q can be done in polynomial time. Given a directed graph G and a set of nodes K, we denote by G[K] the subgraph of G induced by K. A (directed) graph G = (V, E) is a complete graph if for all i, j V such that i = j, we have i j E. That is from every node there is an edge to every other node. Given the set of colours M, we say that a directed graph G is colour complete (with respect to a colour assignment C) if for every colour c M each component of G[Vc] is a complete graph, where Vc = {i V | c C(i)}. In particular, every complete graph is colour complete, but not vice versa. Table 1 summarises our results in terms of the number of arithmetic operations needed. We use binary representation for all values in w and β. The size of the input game graph is |G| = O(nm + e), where n is the number of nodes in a graph, m is the number of colours and e is the number of edges. Note that the graph classes that we study can occur naturally in practice: two colours can model duopoly markets, simple cycles are used in Token ring architectures, and unweighted DAGs with out-degree 1 can model indirect elections. All details of the proofs that had to be omitted due to the page limit constraints can be found in the full version of this paper (Simon and Wojtczak 2016a).

3 Graphs with Two or Three Colours We start by studying coordination games with two colours and monochromatic queries. To ﬁx the notation, let G = (V, E) and the colour set be M = {0, 1}. Let q be a monochromatic query. Without loss of generality, we can assume q(i) = 0 for all i Q, because otherwise we can rename the colours.

Algorithm 1: Algorithm for NE for graphs with two colours and monochromatic queries.

Input: A coordination game G((V, E), w, C, β) and monochromatic query q : Q M. Output: YES if there exists a Nash equilibrium consistent with q and NO otherwise.

1 for i V do

2 if 0 C(i) then s(i) = 0 else s(i) = 1

3 stack S := {i | s(i) = 1}

4 while S = do

5 remove any element from S and assign it to i

6 for {j V i j E} do

7 if s(j) = 0 and 1 C(j) and pj((1, s j)) > pj(s) then

9 add j to S

10 if i Q s(i) = 0 return YES else return NO

Theorem 1 The NE problem for coordination games with two colours and monochromatic queries can be solved in O(|G|) time using Algorithm 1. Similarly, Algorithm 2 below solves the NE problem for monochromatic queries. Theorem 2 The NE problem for coordination games with two colours and monochromatic queries can be solved in O(|G|) time using Algorithm 2.

Algorithm 2: Algorithm for NE on graphs with two colours and monochromatic queries.

Input: A coordination game G((V, E), w, C, β) and monochromatic query q : Q M. Output: YES if all Nash equilibria are consistent with q and NO otherwise.

1 Lines 1-9 of Algorithm 1 where every 0 is replaced by 1 and every 1 by 0.

2 if i Q s(i) = 0 return YES else return NO

In fact, any polychromatic NE query can be reduced to two monochromatic ones and so we get the following. Corollary 1 The NE problem for coordination games with two colours and polychromatic queries can be solved in O(|G|) time. However, we will show that even answering singleton NE queries for unweighted DAGs is co NP-hard in the presence of three colours and no bonuses. We ﬁrst analyse the following gadget.

Figure 2: Gadget D(X1, . . . , Xk, x; Y ) where x { , }. Note that one edge has weight k 1.

X { , } Y { , }

Figure 3: Gadget used in the co NP-hardness proof of NE. Edges with weight 2 can be simulated by unweighted ones.

Proposition 1 For any Nash equilibrium s in D(X1, . . . , Xk, x; Y ) from Figure 2: (a) s(Y ) = x iff i s(Xi) = x and (b) s(Y ) = x iff i s(Xi) = x. Using this gadget we are able to show the following. Theorem 3 The NE problem for singleton queries is co NP-complete for unweighted DAGs with three colours and no bonuses. Proof. [sketch] We reduce from the tautology problem for formulae in 3-DNF form. Assume we are given a formula

φ = (a1 b1 c1) (a2 b2 c2) . . . (ak bk ck)

with k clauses and n propositional variables x1, . . . , xn, where each ai, bi, ci is a literal equal to xj or xj for some j. We will construct a coordination game Gφ of size O(n+k) such that a particular singleton NE query is true for Gφ iff φ is a tautology. First for every propositional variable xi there are four nodes Xi, Xi, Li, Li in Gφ, each with two possible colours or . We connect these four nodes using gadgets D(Xi, Xi, ; Li) and D(Xi, Xi, ; Li). This makes sure that in any Nash equilibrium, s, we have s(Li) = and s(Li) = iff Xi and Xi are assigned different colours. Next, for every clause (ai bi ci) in φ we add to the game graph Gφ node Ci. We use gadget D(ai, bi, ci, ; Ci) to connect literals with clauses, where we identify each xi with Xi and each xi with Xi. Note that Proposition 1 implies that the colour of Ci is iff all nodes ai, bi, ci are assigned . We add two nodes T and F to gather colours and from the Li and Li nodes. Also, we add an additional node Φ to gather the values of all the clauses. We connect these using gadgets D(L1, . . . , Ln, ; T), D(L1, . . . , Ln, ; F), and D(C1, . . . , Ck, ; Φ).

We need to express that for every Nash equilibrium s: s(T) = and s(F) = implies s(Φ) = . We use the gadget from Figure 3. It includes three nodes T, F, Φ that we already deﬁned in Gφ. We claim that NE query q(Z) = is true for Gφ iff Φ is a tautology. 2 On the other hand, we show that answering polychromatic NE queries is NP-hard for unweighted DAGs even with two colours and no bonuses. The construction is similar to the one in the proof of Theorem 3.

Theorem 4 The NE problem is NP-complete for unweighted DAGs with two colours and no bonuses.

Building on this we can show the following when there are three colours to choose from.

Corollary 2 The NE problem for singleton queries is NPcomplete for unweighted DAGs with three colours and no bonuses.

Note that we can also show NP/co NP-hardness for DAGs with out-degree at most two, because we can make arbitrary number of copies of any given node, e.g. to make three copies i1, i2, i3 of node i we can add nodes i , i1, i2, i3 and edges i i1, i i , i i2, i i3.

4 Simple Cycles We consider here coordination games whose underlying graph is a simple cycle. To ﬁx the notation, suppose that V = {0, 1, . . . , n 1} and the underlying graph is 0 1 n 1 0. We assume that the counting is done in cyclic order within {0, . . . , n 1} using the increment operation i 1 and the decrement operation i 1. In particular, (n 1) 1 = 0 and 0 1 = n 1. For i V , let Zi(w) = {c C(i) | β(i, c) + w β(i, c ) for all c C(i)} denote the set of colours available to player i with the bonus at most w below the maximum one available to i. For every i V , deﬁne Ai := Zi(0), i.e. all colours with the maximum bonus, Bi := Zi(wi 1 i 1), and Ci := Zi(wi 1 i). Obviously = Ai Bi Ci C(i) for every i. It is quite easy to see that in any Nash equilibrium, player i can only select a colour from Ci. Let us ﬁx a query q : Q M. In this section, without loss of generality, we assume that 0 Q.

Theorem 5 The NE problem for simple cycles can be solved in O(|G|) time.

Proof. [sketch] We argue that given a simple cycle over the nodes V = {0, . . . , n 1} and a query q : Q M, the output of Algorithm 3 is YES iff there exists a Nash equilibrium s which is consistent with q. Suppose there exists a Nash equilibrium s which is consistent with q. We can argue by induction on V that on termination of Algorithm 3, for all i V , we have s (i) Xi. Conversely, suppose the output of Algorithm 3 is YES. From the deﬁnition, this implies that for all i V , Xi = and for all j Q: q(j) Xj (in fact, Xj = {q(j)}). We deﬁne a Nash equilibrium s as follows. First, let s (0) = q(0). Next we assign values to s (i) starting at i = n 1 and going down to i = 1 as described below. If i Q then s (i) = q(i).

Algorithm 3: NE on a simple cycle

Input: A simple cycle on nodes {0, . . . , n 1}, sets Ai, Bi, Ci for i V , a query q : Q M. Output: YES if there exists a Nash equilibrium consistent with q and NO otherwise.

1 Let X0 = {q(0)}.

2 for i = 0 to n 1 do

3 if Xi Bi 1 then

4 Xi 1 = (Xi Ci 1) Ai 1

6 Xi 1 = Xi

7 if i 1 Q then

8 if q(i 1) Xi 1 then

9 return NO

11 Xi 1 = {q(i 1)}

12 return YES

Algorithm 4: NE on a simple cycle

Input: A simple cycle on nodes {0, . . . , n 1}, sets Ai, Bi, Ci for i V , a query q : Q M. Output: YES if all NEs are consistent with q and NO otherwise.

1 for c M do

2 if Algorithm 3 for q := {0 c} returns NO then

3 continue with the next c

5 Consider Xi computed by Algorithm 3 for q :

6 if exists i Q such that Xi = {q(i)} then

7 return NO

8 return YES

If i Q and Xi Bi 1 then by Algorithm 3 we have Xi = Xi 1. Let s (i) = s (i 1). Assume i Q and Xi Bi 1. If s (i 1) Xi Ci 1 set s (i) = s (i 1). Otherwise s (i 1) Ai 1 and we set s (i) to any element in Xi \ Bi 1.

Now one can show that s , as deﬁned above, is a NE. 2 Algorithm 4 reduces the NE problem to m NE queries. For for unweighted simple cycles NE can solved efﬁciently using an adaptation of Algorithm 3.

Theorem 6 The NE problem for simple cycles (unweighted simple cycles) can be solved in O(m|G|) time (respectively, O(|G|) time).

5 Colour Complete Graphs

We show that NE and NE problems can be solved in polynomial time for coordination games G((V, E), C) played on unweighted colour complete graphs with n nodes and a ﬁxed number of colours, m, and no bonuses.

Theorem 7 The NE and NE problems for unweighted colour complete graphs and no bonuses can be solved in O(nm m!) time. Proof. We claim that the set of total orders on the set of colours induces a set of joint strategies which contains the whole set NE(G). Speciﬁcally, every total order on M will be mapped to a joint strategy SP( ) as follows: assign to each player the highest colour available to him according to the total order . Formally, for all players i: SP( )(i) = max C(i). For any Nash equilibrium s let us deﬁne a relation s M M: x s y iff there exists player i such that {x, y} C(i) and s(i) = x. Lemma 1 The relation s is acyclic, i.e. for all k 2 there is no sequence of colours x1, . . . , xk such that x1 s x2 s . . . s xk s x1. Note Lemma 1 may fail when bonuses are introduced into the game. We also need the following folk result. Lemma 2 Any acyclic binary relation on a ﬁnite set can be extended to a total order. For the relation s let s be a total order from Lemma 2 such that s s. Lemma 3 For any Nash equilibrium s, SP( s) = s. From Lemma 1 and Lemma 3 we know that for every Nash equilibrium s, there exists at least one total order on M that induces it. Therefore, for NE problem ( NE problem) it sufﬁces to check for all possible total orders on M, whether the induced joint strategy SP( ), is a Nash equilibrium and if so, whether any (respectively, all) of them is consistent with q. There are m! total orders on M. Checking whether an induced strategy proﬁle is a Nash equilibrium consistent with q takes O(nm) time. This gives O(nm m!) in total. 2 Note that there are coordination games on colour complete graphs with one-to-one correspondence between the set of total orders on colours and the set of all Nash equilibria (see Example 2 in (Simon and Wojtczak 2016a)), and so with exponentially many different NEs.

6 Directed Acyclic Graphs In Section 3 we showed that the NE and NE problems are NP and co NP complete respectively even for unweighted DAGs with out-degree at most two and no bonuses. We now show that if the out-degree of each node in an unweighted DAG is at most 1 (there are no constraints on the in-degree of nodes) then these problems can be solved efﬁciently. Theorem 8 Algorithm 5 solves the NE problem for unweighted DAGs with out-degree at most one in O(|G|2.5) time. Proof. [sketch] For each node, i, we compute the set, X(i), of colours that can possibly be assigned to i in any Nash equilibrium. Such a set is trivial to compute for source nodes in G, and for the other nodes it can be computed by constructing a suitable bipartite graph based on the sets precomputed for all its neighbours and running a matching algorithm. In lines 7-10 we remove colours that are dominated by others. We need the following lemma.

Algorithm 5: Algorithm for NE on unweighted DAGs with out-degree 1.

Input: A coordination game G((V, E), C, β) and query q : Q M Output: YES if there exists a Nash equilibrium consistent with q and NO otherwise.

1 Topologically sort V into a sequence (i1, . . . , in).

2 for j := 1 . . . n do

4 Y := {X(k) | k ij E}

5 for c C(ij) do

6 S := {Z Y | c Z}; C := C \ {c}; Y := Y \ S;

7 if exists c C such that |S| + β(ij, c) β(ij, c ) < 0 then

8 continue with the next c

9 while exists c C such that |S| + β(ij, c) β(ij, c ) |Y | do

10 C := C \ {c }; Y := Y \ {Z Y | c Z}

11 Construct the following bipartite graph G := (V = (Y , {{c } {1, . . . , |S|+ β(ij, c) β(ij, c )} | c C }), E ) where Z (c , x) E iff c Z 12 if the maximum bipartite matching in G has size |Y | then

13 add c to X(ij)

14 if ij Q then

15 if q(ij) X(ij) return NO else X(ij) := {q(ij)}

16 return YES

Lemma 4 If Algorithm 5 returns YES, then for all i V , for all c X(i), there exists a Nash equilibrium s such that s i = c and for all j = i, s j X(j).

Now, if Algorithm 5 returns YES, then from the deﬁnition, for all i V , Ai = and for all j P, Aj = {q(j)}. By Lemma 4 it follows that there exists a Nash equilibrium s which is consistent with q. Conversely, suppose there exists a Nash equilibrium s which is consistent with q. Let θ = (i1, . . . , in) be the topological ordering of V chosen in line 1 of Algorithm 5. We argue that for all j {1, . . . , n}, s (ij) X(ij). The claim follows easily for i1. Consider a node im and suppose for all j < m, s (ij) X(ij). For c C, let Nim(s , c) = {ik Nim | s (ik) = c}. Since s is a Nash equilibrium, s (im) is a best response to the choices made by all nodes ik Nim. This implies that for all c = s im, |Nim(s , c)| + β(ij, c) |Nim(s , s im)| + β(ij, s im). Note that |S| |Nim(s , s im)| and so c is not discarded in line 8. Also, it guarantees the existence of a matching of size |Y | at line 12 and thus s (im) X(im). We claim that if the Hopcroft-Karp algorithm is used for each matching at line 11, then Algorithm 5 runs in

O(|G|2.5). First, for each node k, X(k) is in Y at most once and so is matched at most once for each colour. We claim that the worst case running time is for |Y | = |V |. Now, due to lines 9-10 we have |S| + β(ij, c) β(ij, c ) |Y | = O(n), so G at line 11 has O(nm) nodes and O(n nm) edges thus its matching takes O( nm n2m) time. 2 Similarly Algorithm 6 solves the NE problem.

Algorithm 6: Algorithm for NE on unweighted DAGs with out-degree 1.

Input: A coordination game G((V, E), C, β) and query q : Q M. Output: YES if all Nash equilibria are consistent with q and NO otherwise.

1 Topologically sort V into a sequence (i1, . . . , in).

2 for j := 1 . . . n do

3 X(ij) := the set of colours player ij can play in any Nash equilibrium (lines 3-13 of Algorithm 5)

4 if ij Q and X(ij) = {q(ij)} then

5 return NO

6 return YES

Theorem 9 Algorithm 6 solves the NE problem for DAGs with out-degree at most one in O(|G|2.5) time.

7 Conclusions We presented coordination games on directed graphs, a natural subclass of polymatrix games. We focused on checking whether a given partial colouring of a subset of the nodes is consistent with some pure Nash equilibrium or, alternatively, with all pure Nash equilibria. We showed these problems to be NP-complete and co NP-complete, respectively, in general. However, we also identiﬁed several natural cases when these decision problems are tractable. In the case of weighted DAGs with out-degree at most one and colour complete graphs with no bonuses a simple reduction from the PARTITION problem and its complement, shows NP and co NP-hardness of their NE and NE problems, respectively. This does not exclude the possibility that pseudo-polynomial algorithms exist for these problems. We conjecture that even for unweighted colour complete graphs these problems are NP/co NP-hard in the presence of bonuses or when the set of colours, M, is not ﬁxed. There are several ways our results can be extended further. One is to study other constraints, e.g. uniqueness of Nash equilibrium or checking maximum payoff for a given player. Another is to look at different solution concepts, e.g. strong equilibria. And yet another is to look for more classes of graphs that can be analysed in polynomial time. Given that these decision problems are already computationally hard for DAGs with three colours, the possibilities for such new classes are rather limited. Finally, we only focused on pure Nash equilibria in this paper, which may not exist for general graphs. On the other hand, mixed Nash equilibria always exist due to Nash s theorem. It would be interesting to know whether the complexity

of ﬁnding one is PPAD-complete problem just like it is for general polymatrix games (Cai and Daskalakis 2011).

References Apt, K. R.; Rahn, M.; Sch afer, G.; and Simon, S. 2014. Coordination games on graphs. In Proc. of WINE 14, volume 8877 of LNCS, 441 446. Apt, K. R.; Simon, S.; and Wojtczak, D. 2016. Coordination games on directed graphs. In Proc. of TARK 15, volume 215 of EPTCS, 67 80. Bil o, V., and Mavronicolas, M. 2012. The Complexity of Decision Problems about Nash Equilibria in Win -Lose Games. In Proc. of SAGT 12, volume 7615 of LNCS, 37 48. Bogomolnaia, A., and Jackson, M. 2002. The stability of hedonic coalition structures. Games and Economic Behavior 38(2):201 230. Cai, Y., and Daskalakis, C. 2011. On minmax theorems for multiplayer games. In Proceedings of the SODA 11, 217 234. Conitzer, V., and Sandholm, T. 2008. New complexity results about Nash equilibria. Games and Economic Behavior 63(2):621 641. Dreze, J., and Greenberg, J. 1980. Hedonic coalitions: Optimality and stability. Econometrica 48(4):987 1003. Erdem, A., and Pelillo, M. 2012. Graph transduction as a noncooperative game. Neural Computation 24(3):700 723. Fabrikant, A.; Papadimitriou, C.; and Talwar, K. 2004. The complexity of pure Nash equilibria. In Proc. of 36th STOC, 604 612. ACM. Feldman, M.; Lewin-Eytan, L.; and Naor, J. S. 2012. Hedonic clustering games. In Proc. of the ACM symposium on Parallelism in algorithms and architectures, 267 276. Gilboa, I., and Zemel, E. 1989. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior 1(1):80 93. Gottlob, G.; Greco, G.; and Scarcello, F. 2005. Pure Nash equilibria: Hard and easy games. Journal of Artiﬁcial Intelligence Research 24:357 406. Greco, G., and Scarcello, F. 2009. On the complexity of constrained Nash equilibria in graphical games. Theoretical Computer Science 410(38-40):3901 3924. Janovskaya, E. 1968. Equilibrium points in polymatrix games. Litovskii Matematicheskii Sbornik 8:381 384. Kearns, M.; Littman, M.; and Singh, S. 2001. Graphical models for game theory. In Proc. of UAI 01, 253 260. Miller, D. A., and Zucker, S. W. 1991. Copositive-plus lemke algorithm solves polymatrix games. Operations Research Letters 10(5):285 290. Pelillo, M., and Bul o, S. R. 2014. Clustering games. Studies in Computational Intelligence 532:157 186. Rahn, M., and Sch afer, G. 2015. Efﬁcient equilibria in polymatrix coordination games. In Proc. of MFCS 15, volume 9235 of LNCS, 529 541. Simon, S., and Wojtczak, D. 2016a. Constrained pure nash equilibria in polymatrix games. Co RR ar Xiv:1611.09515. Simon, S., and Wojtczak, D. 2016b. Efﬁcient local search in coordination games on graphs. In Proceeding of IJCAI 16, 482 488. AAAI Press. Thomas, A., and van Leeuwen, J. 2015. Pure Nash Equilibria in Graphical Games and Treewidth. Algorithmica 71(3):581 604.