Efficient Local Search in Coordination Games on Graphs

1 Introduction

Nash equilibrium is an important solution concept in game theory which has been widely used to reason about strategic interaction between rational agents. Although Nash's theorem guarantees existence of a mixed strategy Nash equilibrium for all finite games, pure strategy Nash equilibria need not always exist. In many scenarios of strategic interaction, apart from the question of existence of pure Nash equilibria, an important concern is whether it is possible to compute an equilibrium outcome and whether a game always converges to one. The concept of improvement paths is therefore fundamental in the study of strategic games. Improvement paths are essentially maximal paths constructed by starting at an arbitrary joint strategy and allowing players to improve their choice in a unilateral manner. At each stage, a single player who did not select a best response is allowed to update his

Dominik Wojtczak

University of Liverpool Liverpool, U.K.

choice to a better strategy. By definition, every finite improvement path terminates in a Nash equilibrium. In a seminal paper, Monderer and Shapley [1996] studied the class of games in which every improvement path is guaranteed to be finite, which was coined as the finite improvement property (FIP). They showed that games with the FIP are precisely those games to which we can associate a generalised ordinal potential function. Thus FIP not only guarantees the existence of pure Nash equilibria but also ensures that it is possible to converge to an equilibrium outcome by performing local search. This makes FIP a desirable property to have in any game. An important class of games that have the FIP is congestion games [Rosenthal, 1973]. However, the requirement that every improvement path is finite, turns out to be a rather strong condition and there are very restricted classes of games that have this property.

Young [1993] proposed weakening the finite improvement property to ensure the existence of a finite improvement path starting from any initial joint strategy. Games for which this property hold are called weakly acyclic games. Thus weakly acyclic games capture the possibility of reaching pure Nash equilibria through unilateral deviations of players irrespective of the starting state. Milchtaich [1996] showed that although congestion games with player specific payoff functions do not have the FIP, they are weakly acyclic. Weak acyclicity of a game also ensures that certain modifications of the traditional no-regret algorithm yields almost sure convergence to a pure Nash equilibrium [Marden et al., 2007].

Although finite improvement path guarantees the existence of a Nash equilibrium, it does not necessarily provide an efficient algorithm to compute an equilibrium outcome. In many situations, improvement paths could be exponentially long. In fact, Fabrikant et al. [2004] showed that computing a pure Nash equilibrium in congestion games is PLS-complete. Even for symmetric network congestion games, where it is known that a pure Nash equilibrium can be efficiently computed [Fabrikant et al., 2004], there are classes of instances where any best response improvement path is exponentially long [Ackermann et al., 2006]. Thus identifying classes of games that have finite improvement paths in which it is possible to converge to a Nash equilibrium in a polynomial number of steps is of obvious interest.

In game theory, coordination games are often used to model situations in which players attain maximum payoff when agreeing on a common strategy. In this paper, we study a simple class of coordination games in which players try to coordinate within a certain neighbourhood. The neighbourhood structure is specified by a finite 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 fixed bonus for picking that particular colour. These games constitute a natural class of strategic games, which capture the following three key characteristics. Join the crowd property: the payoff of each player weakly increases when more players choose her strategy. Asymmetric strategy sets: players may have different strategy sets. Local dependency: the payoff of each player depends only on the choices made by the players in its neighbourhood.

A similar model of coordination games on graphs was introduced in [Apt et al., 2014] where the authors considered undirected graphs. The transition from undirected to directed graphs drastically changes the status of the games. For instance, in the case of undirected graphs, coordination games have the FIP. While in the directed case, Nash equilibria may not exist. Moreover, the problem of determining the existence of Nash equilibria is NP-complete for coordination games on directed graphs [Apt et al., 2015]. However, if the underlying graph is a directed acyclic graph (DAG), a complete graph or a simple cycle, then pure Nash equilibria always exist. These proofs can easily be adapted to show that weighted DAGs and weighted simple cycles have finite improvement paths.

Related work. Although the class of potential games are well studied and has been a topic of extensive research, weakly acyclic games have received less attention. Engelberg and Schapira [2011] showed that certain Internet routing games are weakly acyclic. In a recent paper, Kawald and Lenzner [2013] show that certain classes of network creation games are weakly acyclic and moreover that a specific scheduling of players can ensure that the resulting improvement path converges to a Nash equilibrium in O(n logn) steps. Brokkelkamp and Vries [2012] improved Milchtaich's result [1996] on congestion games with player specific payoff functions by showing that a specific scheduling of players is sufficient to construct an improvement path that converges to a Nash equilibrium. Unlike in the case of exact potential games, there is no neat structural characterisation of weakly acyclic games. Attempts in this direction have been made in the past. Fabrikant et al. [2010] proved that the existence of a unique (pure) Nash equilibrium in every sub-game implies that the game is weakly acyclic. A comprehensive classification of weakly acyclic games in terms of schedulers is done in [Apt and Simon, 2012]. Finally Milchtaich [2013] showed that every finite extensive-form game of perfect information is weakly acyclic.

The model of coordination games are related to various well-studied classes of games. Coordination games on graphs are polymatrix games [Janovskaya, 1968]. In these games, the payoff for each player is the sum of the payoffs from the individual two player games he plays with every other player separately. Hoefer [2007] studied clustering games that are also polymatrix games based on undirected graphs. However, in this setup each player has the same set of strategies and it can be shown that these games have the FIP. A model that does not assume all strategies to be the same, but is still based on undirected graphs, was shown to have the FIP in [Rahn and Sch¨afer, 2015]. When the graph is undirected and complete, coordination games on graphs are special cases of the monotone increasing congestion games that were studied in [Rozenfeld and Tennenholtz, 2006].

Our contributions. In this paper, we identify some natural classes of polymatrix games based on the coordination game model, which even though do not have the FIP (cf. Example 4 in [Apt et al., 2015]), are weakly acyclic. We also show that for these games a finite improvement path of polynomial length can be constructed in a uniform manner. Thus not only do these games have pure Nash equilibria, but they can also be efficiently computed by local search.

We start by analysing coordination games on simple cycles. Even in this simple setting, improvement paths of infinite length may exist. However, we show that there always exists a finite improvement path of polynomial length. We then extend the setting of simple cycles in two directions. First we consider chains of simple cycles where we show that polynomial length improvement paths exist. We then consider simple cycles with cross-edges and show the existence of polynomial length improvement paths. We also demonstrate that these results are optimal in the sense that most natural generalisations of these structures may result in games in which a Nash equilibrium may not even exists. Most of our constructions involve a common proof technique: we identify a specific scheduling of players using which, starting at an arbitrary initial joint strategy, we can reach a joint strategy in which at most two players are not playing their best response. We argue that such a joint strategy can then be updated to converge to a Nash equilibrium. We also identify a structural condition on coalitional deviation once a Nash equilibrium is attained. This property is then used to show the existence of a finite "coalitional" improvement path which terminates in a strong equilibrium. Our results also imply an almost sure convergence, although not necessarily in a polynomial number of steps, to a Nash equilibrium when the order of deviations is random, but "fair". Fairness requires that for any deviation, there is a fixed nonzero lower bound on the probability of it taking place from any state of the game where it can be taken, which implies that the same holds for any finite sequence of deviations. A Nash equilibrium is reached almost surely with such a random order, because when starting at any state we either follow a finite improvement path to a Nash equilibrium with a nonzero chance or that path stops in another state from where we can follow another finite improvement path. As this process continues forever, almost surely one such finite improvement path will succeed.

Table 1 summarises most of our results. All the missing proofs can be found in [Simon and Wojtczak, 2016].

2 Preliminaries

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. We denote S1⇥· · ·⇥Sn by S, call each element s 2 S a joint strategy and abbreviate the sequence (sj)j6=i to s-i. We also write (si↪ s-i) instead of s. We call a strategy si of player i a best response to a joint strategy s-i if for all s0i 2 Si, pi(si↪ s-i) ≥ pi(s0i ↪ s-i).

Given two joint strategies s0 and s and a coalition K, we say that s0 is a deviation of the players in K from s if K = ¶i 2 N ♣ si 6= s0i ♦. We denote this by s K!s0 . If in addition pi(s0 ) > pi(s) holds for all i 2 K, we say that the deviation s0 from s is profitable. Further, we say that a coalition K can profitably deviate from s if there exists a profitable deviation of the players in K from s. Next, we call a joint strategy s a k-equilibrium, where k 2 ¶1↪ ▷ ▷ ▷ ↪ n♦, if no coalition of at most k players can profitably deviate from s. Using this definition, a Nash equilibrium is a 1-equilibrium and a strong equilibrium, see [Aumann, 1959], is an n-equilibrium.

A coalition is a non-empty subset K := ¶k1↪ ▷ ▷ ▷ ↪ km♦ ✓ N. Given a joint strategy s we abbreviate the sequence (sk1 ↪ ▷ ▷ ▷ ↪ skm ) of strategies to sK and Sk1 ⇥ · · · ⇥ Skm to SK. We also write (sK↪ s-K) instead of s. If there is a strategy x such that si = x for all players i 2 K, we also write (xK↪ s-K) instead of s.

A coalitional improvement path, in short a c-improvement path, is a maximal sequence ⇢ = (s1 ↪ s2 ↪ ▷ ▷ ▷ ) of joint strategies such that for every k > 1 there is a coalition K such that sk is a profitable deviation of the players in K from sk-1 . If ⇢ is finite then by last(⇢) we denote the last element of the sequence. Clearly, if a c-improvement path is finite, its last element is a strong equilibrium. We say that G is c-weakly acyclic if for every joint strategy there exists a finite c-improvement path that starts at it. Note that games that are c-weakly acyclic game have a strong equilibrium. We call a c-improvement path an improvement path if each deviating coalition consists of one player. The notion of a game being weakly acyclic [Young, 1993; Milchtaich, 1996], is then defined by referring to improvement paths instead of c-improvement paths.

3 Coordination games on directed graphs

We now define the class of games we are interested in. Fix a finite 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 2 E, a non-negative weight we. We say that a node j is a neighbour of the node i if there is an edge j ! i in G. Let Ni denote the set of all neighbours of node i in the graph G. A colour assignment is a function C : V ! 2M which assigns to each node of G a finite non-empty set of colours. We also introduce the concept of a bonus, which is a function β that to each node i and a colour c 2 M assigns a natural number β(i↪ c). Note that bonuses can be modelled by incoming edges from fixed colour source nodes, i.e. nodes with no incoming edges and only one colour available to them. When stating our results, bonuses are assumed to be not present, unless we explicitly state that they are allowed. Bonuses are extensively used in our proofs because a coordination game restricted to a given subgraph can be viewed as a coordination game with bonuses induced by the remaining nodes of the graph.

Given a weighted graph (G↪ w), a colour assignment C and a bonus function β a strategic game G(G↪ w↪ C↪ β) is defined as follows: 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) = Pj2Ni↪ si=sj wj!i + β(i↪ si).

Finally, given a directed graph G and a set of nodes K, we denote by G[K] the subgraph of G induced by K.

So each node simultaneously chooses a colour and the payoff to the node is the sum of the weights of the edges from its neighbours that chose its colour augmented by the bonus to the node from choosing the 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. Similarly if all the bonuses are 0 then we obtain a coordination game without bonuses. Likewise, to denote this game we omit the function β. In a coordination game without bonuses where the underlying graph is unweighted, each payoff function is defined by pi(s) := ♣¶j 2 Ni ♣ si = sj♦♣.

We now show a structural property of a coalition deviation from a Nash equilibrium in our coordination games. This will be used later to prove c-weak acyclicity for a class of games based on their weak acyclicity. Note that this cannot be done for all classes of graphs, because there exist a coordination game on undirected graph which is weakly acyclic, but has no strong equilibrium [Apt et al., 2014].

Lemma 2 Any profitable coalition deviation from a Nash equilibrium includes a unicoloured directed simple cycle.

4 Simple cycles

In this section we focus on the case when the game graph is a directed simple cycle. Despite the simplicity of this model the problems we consider are already nontrivial for such a basic graph structure. We first restate a result from [Apt et Example 1 ([Apt et al., 2015]) Consider the 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, 6; and 2 for the node 3. Note that the above joint strategy is not a Nash equilibrium. For example, node 1 can profitably deviate to colour a. ⇤

al., 2015] where unweighted graphs are considered. To fix the notation, let the graph be 1 ! 2 ! ▷ ▷ ▷ ! n ! 1. For i 2 ¶2↪ ▷ ▷ ▷↪ n♦, i 1 = i -1, and 1 1 = n.

Theorem 3 ([Apt et al., 2015]) Every coordination game with bonuses on an unweighted simple cycle has a cimprovement path of length O(n).

We would like to extend this result to weighted graphs with bonuses. However as the following example demonstrates, if in a simple cycle, we allow non-trivial weights on at least three edges and associate bonuses with at least three nodes then there are coordination games that need not even have a Nash equilibrium.

Example 4 Consider the simple cycle on three nodes 1, 2 and 3 in which all the edges have weight 2. Let C(1) = ¶a↪ b♦, C(2) = ¶a↪ c♦ and C(3) = ¶b↪ c♦. Let the bonus be defined as β(1↪ a) = β(2↪ c) = β(3↪ b) = 1 and equal to 0 otherwise. The structure essentially corresponds to the one shown in Figure 1. The resulting coordination game does not have a Nash equilibrium. Below we list all the 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). ⇤

We show here that this counterexample is essentially minimal, i.e. if only two nodes have bonuses or only two edges have weights then the coordination game is weakly acyclic.

Theorem 5 Every coordination game on a weighted simple cycle in which at most two nodes have bonuses has an improvement path of length O(n).

Proof sketch. Assume without loss of generality that the nodes with bonuses are 1 and k 2 N. Let s be an arbitrary joint strategy. We proceed in rounds following the cyclic order 1↪ ▷ ▷ ▷ ↪ n and let players switch to any of their best responses. Suppose the resulting joint strategy at the end of the first round, s0 , is not a Nash equilibrium. Then, it is because s01 is not a best response to s0-1 . We start the second round. Suppose player 1 updates his strategy to the colour c = s0n (the argument when c 6= s0n is very similar). We can argue that the only colour that is propagated till node k in the second round is s0n . If the best response of player k is also s0n then we reach a Nash equilibrium in at most two rounds. Otherwise, let the best response of player k be ck 2 C(k). Let t be the joint strategy after the sequence of updates by players k + 1↪ ▷ ▷ ▷ ↪ n. Suppose t is not a Nash equilibrium (note that tn = ck ) and a third round is needed. If player 1 updates his strategy to tn then the colour ck is propagated to nodes 2↪ ▷ ▷ ▷ ↪ k - 1 and a Nash equilibrium is reached. Otherwise, the best response of 1 to t-1 is some c1 2 C(1). In this case, we can argue that c1 is the only colour which is propagated in the third round, resulting in a finite improvement path. ⇤

Theorem 6 Every coordination game on a simple cycle with bonuses where at most two edges have non-trivial weights (i.e. weights greater than 1) has an improvement path of length O(n).

The above results are optimal due to Example 4. We can also show that if a game played on a simple cycle is weakly acyclic, then it is c-weakly acyclic.

Theorem 7 In a coordination game played on a weighted simple cycle with bonuses, any finite improvement path can be extended to a finite c-improvement path just by adding one profitable coalition deviation step at the end of it.

Corollary 8 Every coordination game on a weighted simple cycle in which at most two nodes have bonuses (or with bonuses but in which at most two edges have non-trivial weights) has a c-improvement path of length O(n).

5 Sequence of simple cycles

Next we look at the graph structure which consists of a chain of m ≥ 2 simple cycles. Formally, for j 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪m♦, let Cj be the cycle 1j ! 2j ▷ ▷ ▷ ! nj ! 1j . For simplicity, we assume that all the cycles have the same number of nodes. The results that we show hold for arbitrary cycles as long as each cycle has at least 3 nodes. An open chain of cycles, N is the structure in which for all j 2 ¶1↪ ▷ ▷ ▷ ↪m- 1♦ we have 1j = kj+1 for some k 2 ¶2↪ ▷ ▷ ▷ ↪ n♦. In other words, it is a chain of m cycles. First, we have the following result.

Theorem 9 Every coordination game on an unweighted open chain of cycles has an improvement path of length O(nm2 ).

We say that an open chain of cycles is weighted if at least one of the component cycle has an edge with non-trivial weights (i.e. an edge with weight at least 2).

Theorem 10 Every coordination game on a weighted open chain of cycles has an improvement path of length O(nm3 ).

Proof sketch. The idea is to view the weighted open chain of cycles as a sequence of weighted simple cycles with bonuses. The crucial observation is that at most two nodes in each cycle have bonuses. We can then apply Theorem 5 to construct a finite improvement path for each cycle and argue that these paths can be composed in a specific manner. ⇤

If we allow both weights and bonuses in the underlying graph which constitutes an open chain of cycles, then it follows from Example 4 that there are coordination games that do not have a Nash equilibrium.

Closed chain of cycles. As earlier, let Cj be the cycle 1j ! 2j ▷ ▷ ▷ ! nj ! 1j for j 2 ¶1↪ ▷ ▷ ▷ ↪m♦. Consider the structure in which for all j 2 ¶1↪ ▷ ▷ ▷ ↪m- 1♦, we have 1j = kj+1 for some k 2 ¶2↪ ▷ ▷ ▷ n♦ and 1m = k1 . In other words, instead of having a chain of simple cycles, we now have a "cycle" of simple cycles. We can argue that if these simple cycles are unweighted then the coordination game whose underlying graph is such a structure remains weakly acyclic. However, if we allow the simple cycles to have nontrivial weights then the resulting game need not have a Nash equilibrium as demonstrated in Example 12.

Theorem 11 Every coordination game on an unweighted closed chain of cycles has an improvement path of length O(nm2 ).

Example 12 Consider the coordination game with the underlying graph given in Figure 2. Here, the nodes 4, 5, and 6 have a unique strategy. From Example 4, it follows that the game does not have a Nash equilibrium. ⇤

As in the case of simple cycles, we can show that unweighted closed chains of cycles and open chains of cycles are c-weakly acyclic. This implies the existence of strong equilibria on such graph structures.

Theorem 13 Every coordination game on an unweighted closed (resp. open) chain of cycles has a c-improvement path of length O(nm3 ).

6 Simple cycles with cross-edges

In this section we consider coordination games whose underlying graph forms simple cycles along with some additional "non-cyclic" edges between nodes. We say that the graph G = (V↪ E) is a simple cycle with cross-edges if V = ¶1↪ 2↪ ▷ ▷ ▷ ↪ n♦ and the edge set E can be partitioned into two sets Ec and Ep such that Ec = ¶i ! i ⊕ 1 ♣ i 2 ¶1↪ ▷ ▷ ▷ n♦♦ and Ep = E ∩ Ec. In other words, Ec contains all the cyclic edges and Ep all the additional cross-edges in G.

The results in the previous section show that simple cycles are quite robust in maintaining weak acyclicity. Even with weighted edges and chains of simple cycles, the resulting coordination games remain weakly acyclic. In this section, we first show that if we allow arbitrary (unweighted) cross-edges, then there are games that may not have a Nash equilibrium

¶b↪ c♦

¶a↪ c♦

¶a↪ b♦

Figure 3: A partition-cycle.

(Example 14). We then identify a restricted class of cycles with cross-edges for which the game is weakly acyclic.

Example 14 Consider the graph G0 which we obtain by adding the following edges to the graph in Figure 1: 6 ! 7, 4 ! 8 and 5 ! 9. Thus G0 defines a simple cycle: 1 ! 4 ! 8 ! 2 ! 5 ! 9 ! 3 ! 6 ! 7 ! 1 along with the cross-edges represented in Figure 1 (the nodes in G0 can be easily renamed if required to form the cyclic ordering 1 ! 2 ▷ ▷ ▷ 8 ! 9). Note that in the resulting graph G0 , for any joint strategy, the payoff for node 7 is always 0 since C(7) and C(6) are disjoint. Same holds for node 8 and node 9. Also, note that 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 suffices to consider the strategies of nodes 1, 2 and 3. We can denote this by the triple (s1↪ s2↪ s3). The joint strategies are then the same as those listed in Example 4. It follows that the game does not have a Nash equilibrium. ⇤

Partition-cycle. Let G = (V↪E) be a simple cycle with cross-edges where E = Ec [ Ep. We call G a partitioncycle if (V↪ Ec) forms a simple cycle and the vertex set V can be partitioned into two sets VT and VB such that VT ↪ VB 6= ; and the following conditions are satisfied: Ep ✓ VT ⇥ VB, Ec \ (VT ⇥VT ) forms a path in (V↪ Ec) and Ec \ (VB ⇥VB) forms a path in (V↪ Ec).

Example 15 The directed graph in Figure 3 is an example of a partition-cycle. One possible partition of the vertex set would be VT = ¶1↪ 2↪ 3↪ 4↪ 5♦ and VB = ¶6↪ 7↪ 8♦. The edge set Ec consists of the edges 1 ! 2↪ 2 ! 3↪ ▷ ▷ ▷ ↪ 8 ! 1 whereas Ep = ¶1 ! 6↪ 2 ! 6↪ 3 ! 8↪ 4 ! 7♦. ⇤

We first show that every coordination game whose underlying graph is an unweighted partition cycle is weakly acyclic. For the sake of simplicity, we fix the following notation. The partition-cycle is given by G = (V↪ E) where V = ¶1↪ ▷ ▷ ▷ n♦, VT = ¶1↪ 2↪ ▷ ▷ ▷ ↪ k♦ and VB = ¶k + 1↪ k + 2↪ ▷ ▷ ▷ ↪ n♦. If Ep = ; then we get a simple cycle without cross-edges on n nodes. For i 2 VB, c 2 C(i) and a joint strategy s, let S(i↪ c↪ s) = ¶j 2 VT ♣ j ! i and sj = c♦. We also define the set MC(i↪ s) = ¶c 2 C(i) ♣ ♣S(i↪ c↪ s)♣ ≥ ♣S(i↪ c0 ↪ s)♣ for all c0 2 C(i)♦. Given a player i and a joint strategy of the other players s-i let BR(i↪ s-i) denote the set of best responses of player i to s-i.

Proof sketch. Consider an initial joint strategy s0 . We construct a finite improvement path starting in s0 as follows. We

Theorem 16 Every coordination game without bonuses on an unweighted partition-cycle has an improvement path of length O(n(n - k)).

proceed around the cycle and consider the players 1↪ 2↪ ▷ ▷ ▷ ↪ n in that order. For each player i, in turn, for the corresponding joint strategy s, if si is not a best response to s-i, we update it to a best response respecting the following property:

Let s1 be the resulting joint strategy at the end of the first round. It follows that the players 2↪ ▷ ▷ ▷ ↪ n are playing their best response in s1 . If s1 is a Nash equilibrium then the improvement path is constructed. If not then the only player who is not playing its best response is player 1. This implies that s1n 6= s0n . Let l1 be the least index in VB = ¶k+1↪ ▷ ▷ ▷ n♦ such that for all j 2 ¶l1↪ ▷ ▷ ▷ ↪ n♦, s1l1 6= s0l1 and s1l1 = s1n . Let X = ¶l1↪ l1 + 1↪ ▷ ▷ ▷ ↪ n♦. Note that X 6= ; since n 2 X. We repeatedly let players update to their best response strategies in the cyclic order in multiple rounds. We can argue that in each round ♣X♣ strictly increases. By definition, ♣X♣  ♣VB♣ and therefore the improvement path constructed in this manner eventually terminates in a Nash equilibrium. ⇤

Example 17 Consider the partition-cycle G given in Figure 3 and suppose we add weight 2 to edges 6 ! 7 and 7 ! 8. The resulting game does not have a Nash equilibrium. Note that nodes 3, 4 and 5 have a unique strategy. Also note that in any joint strategy s, the best response for players 1 and 2 is s8 (the strategy of player 8 in s). Thus we can restrict attention to joint strategies s in which s1 = s2 = s8. Let s be denoted by the triple (s6↪ s7↪ s8). Below we list all such joint strategies and underline a strategy that is not a best response: (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). ⇤

Theorem 18 Every coordination game with bonuses on an unweighted partition-cycle has an improvement path of length O(kn(n - k)).

Note that Example 17 shows that with two weighted edges between nodes in VB, it is possible to construct games which may not have a Nash equilibrium. If the weights are only present on edges between nodes in VT or on the cross-edges Ep then the resulting game remains weakly acyclic. If we allow bonuses on nodes then we can add weights to the crossedges Ep, the resulting game remains weakly acyclic. However, from Example 4 we know that if we allow both weights and bonuses, even without cross-edges, there are graphs in which the resulting game need not have a Nash equilibrium.

Given a partition cycle G = (VT [VB↪ Ec [Ep), let ET = (VT ⇥VT ) \Ec. That is, the set ET consists of all the cyclic edges between nodes in VT .

Theorem 19 Every coordination game without bonuses on a partition-cycle with weights on edges in ET [ Ep is weakly acyclic.

Theorem 20 Every coordination game with bonuses on a partition-cycle with weights on edges in Ep is weakly acyclic.

Proof sketch. Each weighted edge in Ep can be converted into a set of unweighted edges such that the resulting graph G0 is still a partition-cycle. From every finite improvement path in the coordination game whose underlying graph is G0 , we can construct a finite improvement path in G. Thus by Theorem 18, the result follows. ⇤

7 Conclusions

We presented natural classes of graphs for which coordination games have improvement or c-improvement paths of polynomial size. We also showed that for most natural extensions of these classes, the resulting coordination game may not even have a Nash equilibrium. In general, local search may not be an efficient technique to find a Nash equilibrium or a strong equilibrium in coordination games. In fact, a coordination game can have strong equilibria which cannot be reached from some of its initial joint strategies. For example, the game in Figure 4 has three trivial strong equilibria in which all players pick the same colour. However, every improvement or c-improvement path from the initial joint strategy (given by the underlined strategies) is infinite. Moreover, although the game graph is weighted, the weighted edges can be replaced by unweighted ones by adding auxiliary nodes. Therefore, the nonexistence of a finite improvement or c-improvement path in coordination games even for unweighted graphs does not imply the non-existence of Nash or strong equilibria.

In proving our results, we used various generalised potential techniques, and exploited structural properties of the classes of graphs. It would be interesting to identify a common progress measure that works for all the classes of graphs that we consider as well as for more general ones. In particular, we conjecture that coordination games on unweighted graphs with indegree at most two are c-weakly acyclic. Extensive computer simulations seem to support this conjecture. This class strictly generalises the unweighted open chains of cycles and closed chains of cycles that we showed to be c-weakly acyclic. We also leave open the existence of finite c-improvement paths in weighted open chains of cycles and partition-cycles. Although they seem likely to exist, unicoloured simple cycles introduced by coalition deviations from Nash equilibria can disappear when trying to reach a new Nash equilibrium, so a detailed analysis is required.

Acknowledgements

We are grateful to Krzysztof Apt for useful discussions. Sunil Simon was supported by the Liverpool-India fellowship provided by the University of Liverpool. Dominik Wojtczak was supported by EPSRC grant EP/M027651/1.