# synchronisation_games_on_hypergraphs__2c9b2e9c.pdf

Synchronisation Games on Hypergraphs

Sunil Simon IIT Kanpur Kanpur, India simon@cse.iitk.ac.in

Dominik Wojtczak University of Liverpool Liverpool, U.K. d.wojtczak@liv.ac.uk

We study a strategic game model on hypergraphs where players, modelled by nodes, try to coordinate or anti-coordinate their choices within certain groups of players, modelled by hyperedges. We show this model to be a strict generalisation of symmetric additively separable hedonic games to the hypergraph setting and that such games always have a pure Nash equilibrium, which can be computed in pseudo-polynomial time. Moreover, in the pure coordination setting, we show that a strong equilibrium exists and can be computed in polynomial time when the game possesses a certain acyclic structure.

1 Introduction

Coordination and anti-coordination are key concepts widely used in game theory to model situations where players are rewarded for agreeing on a common (respectively, different) action or strategy. Such strategic interaction can naturally arise in scenarios as diverse as negotiating tax treaties (coordination), product selection among a group of friends (coordination), miners drilling for resources (anti-coordination) or people trying to gain new skills to stand out from the rest in a job market (anti-coordination). In this paper, we propose a model called synchronisation games, which can be used to analyse the strategic behaviour of players whose objective is to coordinate or anti-coordinate their choice within certain groups of players. Moreover, these sets of possible choices may differ between players and a player may want to synchronise with multiple groups at the same time. For a coordinating group, a positive payoff is generated if all its members chose the same strategy. For an anti-coordinating group, a positive payoff is generated if at least one member chose a different strategy from the rest of the group. An important aspect of synchronisation games is that the utility of players depend not just on the groups that are formed by the strategic interaction, but also on the choice of action that the members of the group decide to coordinate on. This property is useful to model various natural constraints in a concise manner using this framework. As a motivating example, consider a complex task allocation problem of planning a humanitarian relief operation.

Various organisations can form coalitions to make the operation more efﬁcient and provide optimal help. In many cases, the expertise of an organisation would be higher in certain geographical domain compared to others and there might be regions and partners with whom the organisation cannot cooperate due to various technical and ideological reasons. The local interaction structure and the payoff for each organisation, therefore, depends on various parameters including expertise of the organisation, possible partners, geographical location of the task as well as the speciﬁc task that the organisation decides to execute along with its coordinating partners. Each organisation s skills can be best utilised if it coordinates with partners in the optimal geographical region, where, as a group they are able to exploit their combined expertise. A natural framework to model and analyse the behaviour of agents in such a setting would be to use hypergraphs to capture the local dependency relation. Each player corresponds to a vertex and each group to a hyperedge. Note that anticoordination within a group can be simulated using coordination by negating the original payoff and adding to the payoff of each member of the group an equal share of the original payoff. Thus coordination and anti-coordination behaviour within a group can be modelled by associating a positive and negative weight, respectively, to the corresponding hyperedges. These weights (assigned to hyperedges) provide a quantitative measure on how beneﬁcial it is for the players belonging to a particular hyperedge, to coordinate (positive weight) or anti-coordinate (negative weight). In this setting, each player picks one element from a ﬁnite set of colours that each corresponds to a project (i.e. a possible coalition). Thus, synchronisation games on hypergraphs can be used to reason about distributed coalition formation where players have preferences over members of the same coalition given by a hypergraphical social network. Coalition formation also plays a central role in game theory [Hajdukova, 2006] and it is an active area of research in multi-agent systems. In many social and economic situations, individual entities prefer to function as a group in order to achieve certain objectives. Synchronisation games are examples of non-transferable utility games. A natural assumption often made in such a setting is that a player s utility solely depends on members of the coalition that the player is part of and not on how other players are distributed among the other coalitions. Such games are often referred to as hedonic games [Dr eze and Green-

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

berg, 1980]. Despite their apparent simplicity, hedonic games have found numerous practical applications [Bogomolnaia and Jackson, 2002] (and [Aziz and Savani, 2016] for a more recent survey). Related work. Synchronisation games are related to many well-studied types of games. They strictly generalise symmetric additively separable hedonic games [Bogomolnaia and Jackson, 2002] to the hypergraphical setting. Since the payoff structure has a local dependency speciﬁed by hyperedges, they share certain features with graphical games [Kearns et al., 2001] and their generalisation action-graph games [Jiang et al., 2011]. In particular, any synchronisation game can be translated into an equivalent graphical game, but with a potential exponential blow-up in size. Synchronisation games also extend polymatrix games [Janovskaya, 1968] in the context of coordination and anti-coordination behaviour. Polymatrix games form a natural subclass of games where the utilities of players are restricted to be pairwise separable. Computational aspects of polymatrix games are well-studied [Deligkas et al., 2014] and they include game classes with good computational properties like two-player zero-sum games. Polymatrix games where the pairwise interaction is restricted to two player coordination and anti-coordination games have been studied in [Cai and Daskalakis, 2011]. Polymatrix coordination games played on an undirected and directed graph structure has been studied in [Rahn and Sch afer, 2015], [Apt et al., 2016] and [Apt et al., 2015]. Synchronisation games extend these models to hypergraphs. [Bramoull e, 2007] studies a restricted version of anti-coordination games on graphs where each player has two strategies and the strategy set for all the players is the same. The author shows how the properties of equilibria depends on the structure of the underlying graph. The coalition formation property which is inherent in our game model also makes it relevant for cluster analysis. Clustering is the problem of organising a set of objects into groups in a way as to have similar objects grouped together and dissimilar ones assigned to different groups. Hypergraph clustering is a technique that uses high-order (rather than pairwise) similarities to ﬁnd the clusters. Clustering has been studied from a game theoretic perspective [Feldman et al., 2012; Pelillo and Bul o, 2014]. In particular, [Bul o and Pelillo, 2009] showed that using such an approach outperformed the stateof-the-art techniques used for hypergraph clustering. [Hoefer, 2007] also studied clustering games that are polymatrix games based on undirected graphs. Our games are a subclass of hypergraphical games [Papadimitriou and Roughgarden, 2008] where the underlying group games are limited to coordination or anti-coordination ones only. Graphical potential games and their strong connection to Markov random ﬁelds were studied in [Babichenko and Tamuz, 2016; Ortiz, 2015]. As compared to classical centralised approaches to the team formation problem [Anagnostopoulos et al., 2010; Majumder et al., 2012] our game theoretic approach is distributed, i.e. each agent decides on its own which team to join. Analysis of coalition formation games in the presence of hard constraints on the number of coalitions that can be formed and preferences on coalitions given using a weighted undirected graph was investigated in [Sless et al., 2014]. In this

context, we extend that work in two directions. First, we introduce player-speciﬁc restrictions on the coalitions that players can join. Second, using weighted hypergraph representation for the preference relations on coalitions, allows us to represent synergies between groups of players, which is not possible with undirected graphs. Plan of the paper. We start with a background on strategic games, hedonic games, and hypergraphs in Section 2. In Section 3, we deﬁne synchronisation games on hypergraphs and a subclass of hedonic games, which generalises symmetric additively separable hedonic games to the hypergraphical setting. We then show that any synchronisation game can be associated with such a hedonic game so that their pure Nash equilibria and Nash stable partitions, respectively, coincide. In Section 4, we show that every synchronisation game has a pure Nash equilibrium (NE), which can be computed in pseudo-polynomial time. Finally, we show in Section 5 that, in the pure coordination setting, a strong equilibrium exists and can be computed in polynomial time when the game possesses a certain acyclic structure. Due to space constraints some of the proofs had to be omitted or replaced by sketches.

2 Background

Strategic games. Let N = {1, . . . , n} be the set of players. 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 S a joint strategy and abbreviate the sequence (sj)j =i to s i and j =i Sj 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 s i Si, pi(si, s i) pi(s i, s i). A game is an exact potential game if there is a function φ : S R such that s i S i, s i, s i Si, φ(s i, s i) φ(s i , s i) = pi(s i, s i) pi(s i , s i). 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 s K and Sk1 Skm to SK. We also write (s K, s K) instead of s. If there is a strategy x such that si = x for all players i K, we also write (x K, s K) instead of s. Given two joint strategies s and s and a coalition K, we say that s is a deviation of the players in K from s if K = {i N | si = s i}. We denote this by s K s . If in addition pi(s ) > pi(s) holds for all i K, we say that the deviation s from s is proﬁtable. Further, we say that a coalition K can proﬁtably deviate from s if there exists a proﬁtable deviation of the players in K from s. Next, we call a joint strategy s a k-equilibrium, where k {1, . . . , n}, if no coalition of at most k players can proﬁtably deviate from s. Using this deﬁnition, a (pure) Nash equilibrium (NE) is a 1-equilibrium and a strong equilibrium (SE), see [Aumann, 1959], is an n-equilibrium. We do not consider mixed Nash equilibria in this paper. An improvement path (of length l) is a sequence of joint strategies s1, s2, . . . , sl such that for all 1 j l 1 there is exactly one player, i, for which sj+1 is a proﬁtable deviation for player i from sj.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

Hedonic games. For i N, let Ni denote the set of all coalitions that contain i, i.e. Ni = {S N | i S}. A coalition structure is any partition, π, of N into disjoint coalitions. For a coalition structure π, we denote by πi, the unique coalition in π that player i belongs to. A hedonic game N is a pair (N, ) where N is the set of players, and = ( 1, . . . , n) is a preference proﬁle that speciﬁes for every player i N a complete, reﬂexive, and transitive preference relation i on Ni. Let π be a coalition structure. We say that π is Nash stable if no player prefers to switch to a different (possibly empty) coalition in π, i.e. for all i N we have πi i S {i}, where S π { }. Hedonic coalition nets [Elkind and Wooldridge, 2009] provide a succinct and fully expressive representation scheme for hedonic games. A hedonic coalition net N, is a pair (N, R), where N is the set of players and R = (R1, . . . , Rn). For each i N, Ri encodes player i s preference as a set of rules of the form (φ, v) where φ is a propositional logic formula, w.l.o.g. a conjunction of literals, and v is a real number. Speciﬁcally, each player i N corresponds to a propositional variable xi and every coalition S deﬁnes a valuation νS such that νS(xi) = if i S and νS(xi) = if i S. The value of coalition S Ni to player i is then deﬁned as pi(S) = P {(φ,v) Ri|νS|=φ} v.

Hypergraphs. A hypergraph is a pair H = (V, E) consisting of a ﬁnite set of vertices V and a set E of non-empty subsets of V called hyperedges. The arity of a hyperedge is its size. A hypergraph is a graph when all its edges have arity at most two. A path in H = (V, E) from vertex v to w is a sequence of hyperedges e1, . . . , ek such that v e1, w ek and ei ei+1 = for i {1, . . . , k 1}. Two vertices are connected if there is a path between these vertices. The reduction of a hypergraph H, denoted R(H) is deﬁned as R(H) = ( f F f, F) where F = {e E | there is no e E with e e }. H = (V , E ) is a subhypergraph of H = (V, E) if E E and V = e E e. Given a set of vertices X V , the hypergraph induced by X is H[X] = (V , E ) where E = {e X | e E} \ { } and V = e E e.

Acyclicity in hypergraphs. The notion of acyclicity has a natural deﬁnition in graphs and it is an important concept. However, for hypergraphs, there is no canonical definition of acyclicity. Graph acyclicity has been extended to cover hypergraphs in various ways. In increasing order of generality, these are Berge acyclicity, γ-acyclicity, βacyclicity and α-acyclicity [Fagin, 1983]. Berge acyclicity is the most restrictive notion of acyclicity in hypergraphs. A Berge cycle in a hypergraph H = (V, E) is a sequence (e1, v1, . . . , ek, vk, ek+1) with k 2 where ei-s are distinct hyperedges with ek+1 = e1, vi-s are distinct vertices satisfying the condition: vi ei ei+1. A hypergraph is Berge acyclic if it does not contain a Berge cycle. It follows from the deﬁnition of a Berge cycle that if a hypergraph H = (V, E) is Berge acyclic, then for every pair of edges e1, e2 E, |e1 e2| 1. A γ-cycle is a sequence of the form (e1, v1, . . . , ek, vk, ek+1) with k 3 where ei-s are distinct hyperedges with ek+1 = e1, vi-s are distinct vertices satisfying the following condition:

for all i {1, . . . , k 1}, vi ei ei+1 and no other ej (i.e., vi ej for all j < i and j > i + 1). vk ek e1. A hypergraph is γ-acyclic if it does not contain a γ-cycle. A β-cycle is a sequence (e1, v1, . . . , ek, vk, ek+1) with k 3, where ei-s are distinct hyperedges with ek+1 = e1, vi-s are distinct vertices satisfying the condition that for all i {1, . . . , k}, vi ei ei+1 and no other ej. A hypergraph is β-acyclic if it does not contain a β-cycle. Note that the difference between a β-cycle and a γ-cycle concerns possibly the last vertex in the cycle. Two vertices u and v are neighbours in H = (V, E) if there is some e E such that {u, v} e. A clique of a hypergraph is a subset of its vertices whose elements are pairwise neighbours. A hypergraph is conformal if every clique is included in a hyperedge. A hypergraph H has a simple cycle if there exists (v1, v2, . . . , vk) such that R(H[{vi | 1 i k}]) = {{vi, vi+1} | 1 i < n} {{vk, v1}}. A hypergraph is αacyclic if it is conformal and does not have a simple cycle. A rather strange property of α-acyclicity is that it is possible for a hypergraph to be α-acyclic while having a α-cyclic subhypergraph. The following result states that this does not occur for stronger notions of acyclicity: Berge, γ and β.

Lemma 1 [Fagin, 1983] Each subhypergraph of an acyclic hypergraph (Berge, γ and β) is acyclic.

The relationship between the various notions of acyclicity is given by the following result.

Lemma 2 [Fagin, 1983] Berge acyclicity implies γacyclicity implies β-acyclicity implies α-acyclicity. None of the reverse implications hold.

Another important notion in the context of hypergraphs is that of a join tree. A join tree for H = (V, E) (if it exists) is a rooted tree T = (VT , e T ) where the vertices VT = E and for all v V , if v e1 e2, then v is contained in all nodes of the (unique) path connecting e1 to e2 in T . A join tree T of a hypergraph H has disjoint branches if hyperedges of H belonging to different branches of T are disjoint. The following result shows that existence of a join tree with disjoint branches is a notion located between γ-acyclicity and β-acyclicity.

Lemma 3 [Duris, 2012] If a hypergraph is γ-acyclic, it has a join tree with disjoint branches. If a hypergraph has a join tree with disjoint branches, it is β-acyclic.

3 Synchronisation Games We now deﬁne the class of games that we study in this paper. Fix a ﬁnite set of colours M. A weighted hypergraph is given by the tuple (H, w) where H = (V, E) is a hypergraph over the vertices V = {1, . . . , n} where for all e E, |e| 2 and w is a function that associates with each edge e E and colour c M, an integer weight w(e, c). A colour assignment function C : V 2M assigns a ﬁnite non-empty set of colours to each vertex in H. Given an n tuple of colours s = (c1, . . . , cn) where for all i {1, . . . , n}, ci C(i), and an edge e E, we say that e is unicoloured with colour c in s if ci = c for all i e. Given a weighted hypergraph

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

(G, w) and a colour assignment C, the associated strategic game G(H, M, w, C) is deﬁned as follows: the players are the vertices V and the set of strategies of player i V is the set of colours C(i). For a joint strategy s, the payoff function pi(s) = P e E:i e w(e, s) where

w(e, s) = 0 if e is not unicoloured in s w(e, c) if e is unicoloured with c in s We call such games synchronisation games (on hypergraphs). If all weights are positive then we refer to them as coordination games (on hypergraphs). Example 4 Consider the hypergraph H = (V, E) where V = {1, 2, 3, 4, 5} and E = {e1, e2, e3, e4} with e1 = {1, 2, 3}, e2 = {2, 3, 4}, e3 = {3, 4} and e4 = {2, 5}. Let the set of colours M = {a, b, c} be commonly available to all the players. Let the weight function be as follows: w(e1, x) = 5, w(e2, x) = 2, w(e3, x) = 3 and w(e4, x) = 1 for x {a, b, c}. Consider the joint strategy s = (a, a, a, b, b) the corresponding payoff for players would be the tuple (5, 5, 5, 0, 0). For s = (a, b, b, b, a), the payoff would be (0, 2, 1, 1, 0). We now make a direct connection between synchronisation games and the following natural subclass of hedonic games. Let impartial hedonic coalition nets be hedonic coalition nets that satisfy the following two conditions: 1. All literals are positive, i.e. operator is not used. 2. Each rule of the form (φ, v) where xi occurs in φ, belongs to every Ri. Note that symmetric additively separable hedonic games [Bogomolnaia and Jackson, 2002] can be represented by impartial hedonic coalition nets where each rule has exactly two (positive) literals. At the same time, the expressiveness of impartial hedonic coalition nets is incomparable to additively separable hedonic games for which the preferences are separable but not necessarily symmetric.

Theorem 5 Any synchronisation game G(H, M, w, C) can be translated into an impartial hedonic coalition net N = (N, R), and vice versa, such that the set of Nash equilibria in G and the set of Nash stable partitions in N coincide.

Proof. It is straightforward to see that every impartial hedonic coalition net can be represented by a synchronisation game. We simply set V = N, M = N and the colour assignment C(i) = M, i.e. there is no restriction on the colours that can be picked by any of the players. At the same time for every rule (φ, r), where φ = xi1 . . . xik we add a hyperedge e = {i1, . . . , ik} to E with weight w(e, c) = r for every c M. Translating a synchronisation game into an impartial hedonic coalition net is less straightforward. We deﬁne W to be the value W = P e E maxc M |w(e, c)|, which is an upper bound on the absolute value of the payoff any player can get in G. The set of players of N will be N = V M where players in M will simulate the colours in G. For every pair of players i V and c C(i) we add the rule (xi xc, 2W +1) to N for both Ri and Rc. This ensures that player i will be in a coalition with at least one of the players c such that c C(i), because that gives him payoff of at least W +1 and otherwise

his payoff is at most W. Moreover, for every c1, c2 M such that c1 = c2 we add the rule (xc1 xc2, |V | (2W +1) 1) to N to both Rc1 and Rc2. This ensures that no two player simulating colours are in the same coalition, because otherwise the most such a player could get is 1 and he would be better off in a singleton coalition. It is straightforward to see that any Nash equilibrium in G induces a Nash stable partition in N, and vice versa. 2 Theorem 5 tells us that any method for solving general hedonic coalition nets can be applied to synchronisation games after the translation deﬁned in its proof is used. However, the problem with this translation is that it does not preserve nice properties of the underlying hypergraph, e.g. it introduces a clique of size M. As a consequence, the results for hedonic games with bounded treewidth such as [Peters, 2016] can only be applied to very restricted subclasses of synchronisation games.

4 Nash Equilibrium

In this section we study the existence and computational complexity of ﬁnding an NE in synchronisation games. We start with the following crucial fact.

Lemma 6 Every synchronisation game G(H, M, w, C) is an exact potential game.

Proof. We will show that φ(s) = P e E w(e, s) is an exact potential function. Assume that some player i switches its colour in s, which results in a strategy proﬁle s . Note that the value of w does not change for hyperedges that player i is not part of. This is because nothing changes for them when the strategy proﬁle switches from s to s . As a result φ(s ) φ(s) = P e E:i e w(e, s ) w(e, s) = pi(s ) pi(s). 2 Note that in any local maximum of the potential function φ, no player has an incentive to deviate and so it has to be a Nash equilibrium. Let W = maxe E,c C |w(e, c)|. Note that the absolute value of φ is bounded by |E| W and φ(s) is always an integer, which implies the following.

Corollary 7 Every synchronisation game has an NE and any strategy improvement path has length O(|E| W).

Checking whether any player can improve his payoff by unilateral switching of his colour can be done in O(|V | |M| P e E |e|). This and Corollary 7 implies that simply following any strategy improvement path gives us a pseudopolynomial O(|E| W |V | |M| P e E |e|) algorithm for computing an NE. Recall that the complexity class PLS [Johnson et al., 1988] captures the computational problem of ﬁnding a local maximum of a polynomially computable function with polynomially bounded neighbourhood. As PLS P would imply that NP = co-NP, it is considered unlikely that a polynomial algorithm exists for any PLS-hard problem. The fact that synchronisation games can encode symmetric additively separable hedonic games and ﬁnding a Nash stable partition in them is PLS-hard shows PLS-hardness of ﬁnding an NE in synchronisation games. However, this encoding requires as many colours as there are number of players in the game. We

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

strengthen this result by directly showing PLS-hardness already for two colours.

Theorem 8 Finding a Nash equilibrium in a synchronisation game in which there are only two colours to choose from is a PLS-complete problem.

Proof. [sketch] Checking if there is a proﬁtable deviation for some player in a given joint strategy proﬁle s can be done in polynomial time. This shows that the problem of ﬁnding a local maximum of φ is in PLS. To prove PLS-hardness, we reduce from the Local Max-Cut problem [Sch affer and Yannakakis, 1991]. 2 Despite this lower bound, our preliminary experimental tests showed that a simple strategy improvement path following algorithm, i.e. applying any proﬁtable deviation in any order, performs very well in practice. E.g. it can ﬁnd within a minute an NE in a random synchronisation game with |V | = 1000, |E| = 10000, |M| = 10, and W = 109 when run on 1.7 GHz Intel Core i5 CPU with 4 GB of RAM. We also consider now the problem of ﬁnding an NE with social welfare (the sum of all players payoffs) L, where L is an arbitrary constant, and show the following.

Theorem 9 Checking whether a synchronisation game has an NE with social welfare at least L is NP-complete.

Proof. [sketch] A straightforward reduction from the Kcolouring problem for hypergraphs. 2 Many NP-complete problems on undirected graphs can be solved in polynomial time when restricted to the class of graphs with a bounded treewidth [Robertson and Seymour, 1986]. Hypertree-width deﬁned in [Gottlob et al., 2002] is a similar measure for hypergraphs. For any given constant k checking whether a hypergraph has a hypertree-width at most k is feasible in polynomial time. The class of graphs with k-bounded hypertree-width strictly generalise the notion of hypergraphs acyclicity as the class of hypergraphs with hypertree width 1 is exactly the class of α-acyclic hypergraphs. One can show tractability of ﬁnding an NE in synchronisation games played on hypergraphs with a bounded hypertreewidth, but with the following additional restriction. We say that a synchronisation game G has the small neighborhood property if every player s payoff in G depends only on actions of O(log(|V | + |E|)/ log |M|) other players.

Theorem 10 [follows from Theorem 5.3 in [Gottlob et al., 2005]] A Nash equilibrium can be found in polynomial time for all synchronisation games that have the small neighbourhood property and are played on hypergraphs with a bounded hypertree-width.

5 Strong Equilibrium

Unlike in the case of Nash equilibria, strong equilibria may not always exist even in coordination games on graphs [Rahn and Sch afer, 2015]. The following example shows that coordination games on hypergraphs which are α-acyclic need not always have a strong equilibrium.

Example 11 Consider the hypergraph H which arises from the graph and the colour assignment depicted in Figure 1 along with the hyperedge e = {1, 2, 3, 4}. The weights on

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

Figure 1: Game with no strong equilibria

the hyperedges are depicted in Figure 1 and the weights are the same for all the colours. Let w(e, x) = 1 for all x. Due to the presence of the hyperedge e, the resulting hypergraph is α-acyclic. We now argue that the coordination game whose underlying graph is H does not have a strong equilibrium. It can be veriﬁed that there are only two (pure) Nash equilibia in this game, the joint strategies s = (a, c, c, c) and t = (b, b, c, c). In the joint strategy s, the coalition {1, 2} can proﬁtably deviate to b. While in t, the coaltion {1, 3} can profitably deviate to a. Therefore it follows that this game does not have a strong equilibrium.

We now show that strong equilibria are guaranteed to exist in coordination games when the underlying hypergraph satisﬁes certain acyclicity condition. Given a set K V , let EK = {e E | e K = }. A deviation s K s is simple if the hypergraph H[EK] is connected and all nodes in K deviate to the same colour. The following lemma says that if a joint strategy is not a strong equilibrium, then there is a simple deviation.

Lemma 12 For coordination games, if s K s is a profitable deviation for coalition K, then there exists a simple deviation which is proﬁtable.

Theorem 13 Every coordination game in which the underlying hypergraph H = (V, E) is Berge acyclic has a strong equilibrium which can be computed in O(|V |) time.

Proof. [sketch] Let H be a hypergraph that is Berge acyclic. We give a two pass algorithm that processes the nodes of the hypergraph and computes a strong equilibrium. The processing order is determined by a topological sort of the graph which we derive using the following process: Initially hypergraph H = H, i.e., (V , E ) = (V, E). Repeat until the H is reduced to one edge: Let e E be an edge which has a common vertex with one other edge. Since H is Berge acyclic, such an edge is guaranteed to exists if |E| 2. Update H to the induced subhypergraph H[E \ {e}]. By Proposition 1, H remains Berge acyclic. Let θ = e1, e2, . . . , ek be the order in which the edges are removed in the above process and ek is the last edge remaining in H . Based on this ordering, we can associate with each edge e E , a node v e which is the parent of e. We can then construct a tree T whose vertices are edges in H based on the ordering θ and argue that we can synthesise a strong equilibrium in the game by implementing a backward induction procedure on the tree T. Since the parent of each edge is

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

a unique vertex and the procedure processes each edge twice, we get the running time of O(|V |). 2 The above result can be extended to hypergraphs that have join trees with disjoint branches. For the strong equilibrium deﬁned by the procedure to be a valid joint strategy, the assumption of having disjoint branches is crucial.

Theorem 14 Every coordination game in which the underlying hypergraph H has a join tree with disjoint paths has a strong equilibrium that can be computed in time polynomial in the size of H.

Recall that the notion of a join tree with disjoint branches falls in between that of γ-acyclicity and β-acyclicity. There are β-acyclic hypergraphs which do not have a join tree with disjoint branches. The next result shows that strong equilibrium is guaranteed to exists in games whose underlying hypergraph is β-acyclic. However, the procedure given below to compute such an equilibrium does not run in polynomial time.

Theorem 15 Every coordination game in which the underlying hypergraph H = (V, E) is β-acyclic has a strong equilibrium.

Proof. [sketch] We ﬁrst make use of the result from [Brault Baron, 2014] that proves equivalence of β-acyclic graphs in terms of an elimination order of β-leaves. This elimination order, provides us with an ordering of nodes of the hypergraph H = (V, E). Let θ = v1, v2, . . . , vk be this ordering. We deﬁne an exponential sized game tree T = (VT , ET ) with vk as the root. Since H is β-acyclic, it ensures a certain restriction on the interaction of players. For instance, if there are distinct vertices v1, v2, v3 such that v1, v2 are part of a hyperedge and v2, v3 are part of a hyperedge, then the only possible interaction between v1 and v3 is through a hyperedge consisting of all three vertices. This induces an independence on the best response actions computed inductively by backward induction on the subgames of T. We can then argue that the joint strategy computed using backward induction can be translated into a strong equilibrium in H. 2 Finally, checking if a hypergraph is acyclic (Berge, γ and β) can be done in polynomial time. Given a hypergraph, it is also possible to check if it has a join tree with disjoint branches and construct such a tree (if it exists) in polynomial time [Capelli et al., 2014].

Theorem 16 Given a coordination game G(H, M, w, C) along with a joint strategy s, checking if s is a strong equilibrium is in P.

Proof. [sketch] We can argue that for a ﬁxed colour c C, it is possible to check in polynomial time the existence of a maximal coalition (in terms of set inclusion) K which can proﬁtably deviate to c. By Lemma 12, we can enumerate all the colours in M and verify if s is a strong equilibrium. Let H = (V, E) and ﬁx a coalition K of vertices that can possibly deviate to a colour c. Let E = {e E | distinct nodes u, w K with u, w e} and H = (V , E ) be the hypergraph induced by E . For v K, let y1 v = P e E\E :v e w(e, (c, s v)) and y2 v = P e E w(e, (c K, s K)). If K has a proﬁtable deviation to

c from the joint strategy s, then the following holds: for all v K, pv(c K, s K) = y1 v + y2 v > pv(s). This holds iff y2 v > pv(s) y1 v and we denote this inequality by ( ). Now starting with the set Vc = {v V | c C(v) and sv = c} we can successively eliminate nodes and converge to the maximal K for which ( ) holds. 2 Given a coordination game G(H, M, w, C), checking whether it has a strong equilibrium is NP-hard even when H is a graph [Rahn and Sch afer, 2015]. Along with Theorem 16 we get the following corollary: Corollary 17 Checking whether a given coordination game G(H, M, w, C) has a strong equilibrium is NP-complete.

6 Conclusions In this paper, we deﬁned the synchronisation game model where players try to coordinate or anti-coordinate among certain groups of players. We showed that this model corresponds to a natural subclass of hedonic games and it strictly generalises symmetric additively separable hedonic games. As a consequence, any tool that is capable of analysing hedonic games can also be used to analyse synchronisation games (after the appropriate conversion). However, since the payoffs of players in a synchronisation game depends not only on the eventual group structure that arises but also on the chosen colour, this framework can be used to model complex constraints in a more natural and concise manner. As illustrated in the paper, it is also possible to directly exploit speciﬁc structural properties to reason about synchronisation games which are lost during the translation to hedonic games. Our results can be summarised as follows. We proved that every synchronisation game has a pure NE and argued that ﬁnding one is tractable in several natural cases and, as preliminarily experimental results suggests, potentially also in practice. Moreover, we showed that strong equilibria exist in synchronisation games when played on β-acyclic hypergraphs with non-negative weights and can be found in polynomial time when the hypergraph has a join tree with disjoint paths. We believe our model is of interest because it is general enough to capture many natural strategic reasoning situations, while guaranteeing the existence of equilibria and tractability of their computation in many situations. As future work, it would be interesting to analyse the behaviour of the local search algorithm for ﬁnding an NE in synchronisation games using smoothed analysis as it was done for the the Local Max-Cut problem in [Etscheid and R oglin, 2014]. Another interesting problem is showing that ﬁnding a strong equilibrium is also tractable for β-acyclic hypergraphs.

Acknowledgements We would like to thank Alex Y. Chan for implementing the strategy improvement path following algorithm from Section 4 and performing some initial tests of its performance. We are grateful to Krzysztof Apt for useful discussions and also thank the anonymous reviewers for their valuable comments. Sunil Simon was supported in part by the Research-I Foundation, IIT Kanpur and the Liverpool-India fellowship. Dominik Wojtczak was supported in part by EPSRC grants EP/M027651/1 and EP/P020909/1.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

References [Anagnostopoulos et al., 2010] A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi. Power in unity: Forming teams in large-scale community systems. In Proceedings of the 19th International Conference on Information and Knowledge Management, pages 599 608. ACM, 2010. [Apt et al., 2015] K.R. Apt, S. Simon, and D. Wojtczak. Coordination games on directed graphs. In Proceedings of the 15th TARK, 2015. [Apt et al., 2016] K.R. Apt, B.de Keijzer, M. Rahn, G. Sch afer, and S. Simon. Coordination games on graphs. International Journal of Game Theory, 2016. [Aumann, 1959] R. J. Aumann. Acceptable points in general cooperative n-person games. In Contribution to the Theory of Games (AM-40), volume IV, pages 287 324. Princeton University Press, 1959. [Aziz and Savani, 2016] H. Aziz and R. Savani. Hedonic games, chapter 15, pages 356 376. Handbook of Computational Social Choice. Cambridge University Press, 2016. [Babichenko and Tamuz, 2016] Y. Babichenko and O. Tamuz. Graphical potential games. Journal of Economic Theory, 163:889 899, 2016. [Bogomolnaia and Jackson, 2002] A. Bogomolnaia and M. Jackson. The stability of hedonic coalition structures. Games and Economic Behavior, 38(2):201 230, 2002. [Bramoull e, 2007] Y. Bramoull e. Anti-coordination and social interactions. Games and Economic Behaviour, 58:30 49, 2007. [Brault-Baron, 2014] J. Brault-Baron. Hypergraph acyclicity revisited. Ar Xiv e-prints, 2014. [Bul o and Pelillo, 2009] S.R. Bul o and M. Pelillo. A gametheoretic approach to hypergraph clustering. In Proceedings of the 23rd NIPS, pages 1571 1579, 2009. [Cai and Daskalakis, 2011] Y. Cai and C. Daskalakis. On minmax theorems for multiplayer games. In Proceedings of the 22nd Symposium on Discrete Algorithms, pages 217 234. SIAM, 2011. [Capelli et al., 2014] F. Capelli, A. Durand, and S. Mengel. Hypergraph acyclicity and propositional model counting. In Proceedings of the 17th International Conference on Theory and Applications of Satisﬁability Testing, volume 8561 of LNCS, pages 399 414. Springer, 2014. [Deligkas et al., 2014] A. Deligkas, J. Fearnley, R. Savani, and P. Spirakis. Computing approximate Nash equilibria in polymatrix games. In Proceedings of the 10th International Conference on Web and Internet Economics, volume 8877 of LNCS, pages 58 71. Springer, 2014. [Dr eze and Greenberg, 1980] J.H. Dr eze and J. Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4):987 1003, 1980. [Duris, 2012] D. Duris. Some characterizations of γ and βacyclicity of hypergraphs. Information Processing Letters, 112(16):617 620, 2012. [Elkind and Wooldridge, 2009] E. Elkind and M. Wooldridge. Hedonic coalition nets. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, pages 417 424, 2009. [Etscheid and R oglin, 2014] M. Etscheid and H. R oglin. Smoothed analysis of local search for the maximum-cut problem. In Proceedings of the 25th Symposium on Discrete Algorithms, pages 882 889, 2014.

[Fagin, 1983] R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. Journal of ACM, 30(3):514 550, 1983. [Feldman et al., 2012] M. Feldman, L. Lewin-Eytan, and J.S. Naor. Hedonic clustering games. In Proceedings of the 24th Symposium on Parallelism in Algorithms and Architectures, pages 267 276. ACM, 2012. [Gottlob et al., 2002] G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64(3):579 627, 2002. [Gottlob et al., 2005] G. Gottlob, G. Greco, and F. Scarcello. Pure Nash equilibria: Hard and easy games. Journal of Artiﬁcial Intelligence Research, 24:357 406, 2005. [Hajdukova, 2006] J. Hajdukova. Coalition formation games: A survey. International Game Theory Review, 8(4):613 641, 2006. [Hoefer, 2007] M. Hoefer. Cost Sharing and Clustering under Distributed Competition. Ph D thesis, University of Konstanz, 2007. [Janovskaya, 1968] E.B. Janovskaya. Equilibrium points in polymatrix games. Litovskii Matematicheskii Sbornik, 8:381 384, 1968. [Jiang et al., 2011] A.X. Jiang, K. Leyton-Brown, and N.A.R. Bhat. Action-graph games. Games and Economic Behavior, 71(1):141 173, 2011. [Johnson et al., 1988] D.S. Johnson, C.H. Papadimitriou, and M. Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37(1):79 100, 1988. [Kearns et al., 2001] M. Kearns, M. Littman, and S. Singh. Graphical models for game theory. In Proceedings of the 13th Conference on Uncertainty In Artiﬁcial Intelligence, pages 253 260, 2001. [Majumder et al., 2012] A. Majumder, S. Datta, and K.V.M. Naidu. Capacitated team formation problem on social networks. In Proceedings of the 18th International Conference on Knowledge Discovery and Data Mining, pages 1005 1013. ACM, 2012. [Ortiz, 2015] L.E. Ortiz. Graphical potential games. ar Xiv preprint ar Xiv:1505.01539, 2015. [Papadimitriou and Roughgarden, 2008] C.H. Papadimitriou and T. Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM, 55(3):14:1 14:29, 2008. [Pelillo and Bul o, 2014] M. Pelillo and S.R. Bul o. Clustering games. Studies in Computational Intelligence, 532:157 186, 2014. [Peters, 2016] D. Peters. Graphical hedonic games of bounded treewidth. In Proceedings of the 30th AAAI Conference on Artiﬁcial Intelligence. AAAI Press, 2016. [Rahn and Sch afer, 2015] M. Rahn and G. Sch afer. Efﬁcient equilibria in polymatrix coordination games. In Proceedings of the 40th MFCS, pages 529 541, 2015. [Robertson and Seymour, 1986] N. Robertson and P.D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309 322, 1986. [Sch affer and Yannakakis, 1991] A.A. Sch affer and M. Yannakakis. Simple local search problems that are hard to solve. SIAM Journal on Computing, 20(1):56 87, 1991. [Sless et al., 2014] L. Sless, N. Hazon, S. Kraus, and M. Wooldridge. Forming coalitions and facilitating relationships for completing tasks in social networks. In Proceedings of the 13th AAMAS, pages 261 268, 2014.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)