Synchronisation Games on Hypergraphs

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.

Dominik Wojtczak

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

Various organisations can form coalitions to make the operation more efficient 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 specific 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 beneficial 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 finite 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 Greenberg, 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 specified 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 find 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 fields 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-specific 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 define 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 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 ∈ K, we also write (xK, 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 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 ∈ {1, . . . , n}, if no coalition of at most k players can profitably deviate from s. Using this definition, 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 profitable deviation for player i from sj .

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 profile that specifies for every player i ∈ N a complete, reflexive, 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. Specifically, each player i ∈ N corresponds to a propositional variable xi and every coalition S defines 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 defined as pi(S) = ∑{(φ,v)∈Ri|νS|=φ} v.

Hypergraphs. A hypergraph is a pair H = (V,E) consisting of a finite 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 defined as R(H) = (∪f∈Ff, 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 definition 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 definition 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 , eT ) 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 define the class of games that we study in this paper. Fix a finite 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 finite 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

(G,w) and a colour assignment C, the associated strategic game G(H,M,w,C) is defined 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) = ∑e∈E:i∈e w(e, s) where

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 define W to be the value W = ∑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. ✷

Theorem 5 tells us that any method for solving general hedonic coalition nets can be applied to synchronisation games after the translation defined 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 finding 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) = ∑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 profile 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 profile switches from s to s′ . As a result φ(s′ ) - φ(s) = ∑e∈E:i∈e w(e, s′ ) - w(e, s) = pi(s′ ) - pi(s). ✷

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| · ∑e∈E |e|). This and Corollary 7 implies that simply following any strategy improvement path gives us a pseudopolynomial O(|E| · W · |V | · |M| · ∑e∈E |e|) algorithm for computing an NE.

Recall that the complexity class PLS [Johnson et al., 1988] captures the computational problem of finding 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 finding a Nash stable partition in them is PLS-hard shows PLS-hardness of finding an NE in synchronisation games. However, this encoding requires as many colours as there are number of players in the game. We 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 profitable deviation for some player in a given joint strategy profile s can be done in polynomial time. This shows that the problem of finding a local maximum of φ is in PLS. To prove PLS-hardness, we reduce from the Local Max-Cut problem [Sch¨affer and Yannakakis, 1991]. ✷

Despite this lower bound, our preliminary experimental tests showed that a simple strategy improvement path following algorithm, i.e. applying any profitable deviation in any order, performs very well in practice. E.g. it can find 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 finding 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. ✷

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 defined 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 finding 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 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 verified 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 profitably 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 satisfies 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 profitable.

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 a unique vertex and the procedure processes each edge twice, we get the running time of O(|V |). ✷

The above result can be extended to hypergraphs that have join trees with disjoint branches. For the strong equilibrium defined 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 first make use of the result from [BraultBaron, 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 define 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. ✷

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 fixed 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 profitably 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 fix 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 = ∑e∈E\E′ :v∈e w(e, (c, s-v)) and y2 v = ∑e∈E′ w(e, (cK, s-K)). If K has a profitable deviation to c from the joint strategy s, then the following holds: for all v ∈ K, pv(cK, 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. ✷

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 defined 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 specific 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 finding 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 finding 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 finding 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.