# distance_polymatrix_coordination_games__92840851.pdf

Distance Polymatrix Coordination Games

Alessandro Aloisio1,2 , Michele Flammini1 , Bojana Kodric1 and Cosimo Vinci1

1Gran Sasso Science Institute, L Aquila, Italy 2University of L Aquila, Italy {alessandro.aloisio, michele.ﬂammini, bojana.kodric, cosimo.vinci}@gssi.it

In polymatrix coordination games, each player x is a node of a graph and must select an action in her strategy set. Nodes are playing separate bimatrix games with their neighbors in the graph. Namely, the utility of x is given by the preference she has for her action plus, for each neighbor y, a payoff which strictly depends on the mutual actions played by x and y. We propose the new class of distance polymatrix coordination games, properly generalizing polymatrix coordination games, in which the overall utility of player x further depends on the payoffs arising from mutual actions of players v, z that are the endpoints of edges at any distance h < d from x, for a ﬁxed threshold value d n. In particular, the overall utility of player x is the sum of all the above payoffs, where each payoff is proportionally discounted by a factor depending on the distance h of the corresponding edge. Under the above framework, which is a natural generalization that is well-suited for capturing positive community interactions, we study the social inefﬁciency of equilibria resorting to standard measures of Price of Anarchy and Price of Stability. Namely, we provide suitable upper and lower bounds for the aforementioned quantities, both for boundeddegree and general graphs.

1 Introduction Polymatrix games [Yanovskaya, 1968] are a well-known universal framework for modeling multi-agent games, which takes into account only pairwise interactions and thus allows a succinct representation. Despite the constraint of considering only pairwise interactions, its formulation is general enough to capture a number of settings, both of theoretical and practical interest. In polymatrix games each player plays a separate bimatrix game with every other player. In the restricted version named polymatrix coordination games [Rahn and Sch afer, 2015], an outcome of a bimatrix game gives the same payoff w{x,y}(σx, σy) to the two players x and y involved in it. Moreover, every player gets also an additional payoff px(σx) that only depends on the strategy she chooses.

In this paper, we generalize polymatrix coordination games, by allowing players to receive further payoff from the interactions they are not personally involved in. The idea here is that each player beneﬁts not only from good relations with her immediate neighbors, but also from the positive environment stemming from good relations between her immediate neighbors and their respective immediate neighbors. A further generalization of this thought brings us to a model in which the utility is computed as the sum of the payoffs from the whole connected component of the interaction graph, up to a certain maximal distance d, where d is a parameter of the model. Furthermore, it seems reasonable to discount the amount of payoff received from nonneighboring edges by a factor between zero and one, and to make such factors decrease with the distance of the corresponding edge/interaction. In other words, an agent x gets also the payoff αh+1 w{v,z}(σv, σz) for every edge {v, z} at distance h < d from x, where αh+1 is the relative discount factor. We call the arising model, that generalizes polymatrix coordination games, distance polymatrix coordination games. Distance polymatrix coordination games are able to capture many types of interactions in the real world. In fact, several kinds of positive community effects easily fall within their scope. For instance, members of a scientiﬁc community obviously beneﬁt from successful collaborations with their colleagues (while at the same time having personal preferences of what they would like to work on). However, any individual also beneﬁts, albeit to a smaller degree, when his close colleagues have successful collaborations that he is not personally a part of. This is quite obvious when thinking about the student advisor relationship, but also noticeable for researchers working at the same university or institution. A further example comes from politics, where a person who belongs to a party proﬁts not only from her direct contacts, but also from the contacts of her contacts, etc. At the same time, it is also common that the beneﬁt obtained by relations at second or higher distance level generate less payoff, which is taken into account by our discount factors. In the setting described above, we will be focusing on the efﬁciency of the system. Our reference point for stability will be k-strong Nash equilibria, which are action proﬁles from which no group of up to k agents can simultaneously deviate such that all of them proﬁt from the deviation. Such a deﬁni-

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

tion also includes the standard notion of Nash equilibria for k = 1. However, we will see that only for k 2 the inefﬁciency can be suitably bounded. This fact is not a real drawback, as some degree of communication between the agents is to be expected in real-world scenarios, and especially in the ones modeled by means of these games, which assume a positive coordination effect among close agents. Our analysis provides bounds which depend on k and on the discounting factors for the part of the utility of the agents coming from non-ﬁrst-hand interactions.

1.1 Related Work Polymatrix games were introduced several decades ago [Yanovskaya, 1968] and have been thoroughly studied since, both in some classical works [Howson, 1972; Eaves, 1973; Howson and Rosenthal, 1974; Miller and Zucker, 1991] and also more recently with a special focus on equilibria [Rahn and Sch afer, 2015; Cai et al., 2016; Deligkas et al., 2017; Deligkas et al., 2020]. Polymatrix coordination games [Rahn and Sch afer, 2015], in which the bimatrix games have symmetrical payoffs and players have individual preferences, are the basis of our model. Indeed, they are encompassed by our model by setting d = 1. Polymatrix coordination games are in turn an extension of a previously introduced model that did not include individual preferences [Cai and Daskalakis, 2011]. Our model is also related to the so-called social context games [Ashlagi et al., 2008], where the players utilities are computed from the payoffs based on the underlying neighborhood graph and an aggregation function. We consider more than just the neighborhood of an agent, and we account the player s preference only for her own utility. Related to our work are also (symmetric) additively separable hedonic games [Dr eze and Greenberg, 1980] and hypergraph hedonic games [Aloisio et al., 2020], where the players are embedded in a weighted graph and the utility is computed as the sum of the edges or hyperedges towards members of the same coalition. The difference from our model, however, is that in hedonic games in general every coalition is a feasible choice for every player, there are no individual preferences, and the weights in each bimatrix are all equal to either 0 or to a ﬁxed value w. Another model related to our work is the group activity selection problem [Darmann et al., 2012; Darmann and Lang, 2017; Bil o et al., 2019], standing between polymatrix coordination games and hedonic games. Also here, in each bimatrix all the weights are either 0 or a ﬁxed value w, but there are also individual preferences that depend on the chosen activity. A generalization of polymatrix coordination games to hypergraphs is called synchronization games [Simon and Wojtczak, 2017], for which the existence and computability of pure and strong Nash equilibria have been studied, without investigating the degradation of social welfare. Some negative results for our problem can be inherited from additively separable hedonic games. For instance, computing a Nash stable outcome is PLS-complete [Gairing and Savani, 2010], while computing an optimal outcome and determining the existence of a core stable, strict core stable, Nash stable, or individually stable outcome are all NP-hard

problems [Aziz et al., 2011]. It has also been proven that ﬁnding a pure Nash equilibrium in a polymatrix coordination game is PLS-complete [Cai and Daskalakis, 2011]. The idea of obtaining utility from non-neighboring players has been explored recently for a variant of hedonic games, called distance hedonic games, that are not additively separable, since the coalition size also plays a role in determining the payoffs [Flammini et al., 2020]. They generalize fractional hedonic games [Aziz et al., 2019; Elkind et al., 2020; Monaco et al., 2020; Carosi et al., 2019; Bil o et al., 2018] similarly as our model does with polymatrix games.

1.2 Our Contribution We study the inefﬁciency of k-stable Nash equilibria of ddistance polymatrix coordination games and provide suitable bounds on both the Price of Anarchy and the Price of Stability. To the best of our knowledge, there are no previous results of this kind in the literature that would apply to our model. In Section 3, we give upper and lower bounds for bounded-degree graphs, with the gap being reasonably small, and in Section 4, a tight bound on the Price of Anarchy for general graphs. Finally, in Section 5, we show that in general graphs the Price of Stability is asymptotically equal to the Price of Anarchy, meaning that the inefﬁeciency of k-strong equilibria is fully characterized. The related proof technique is in our opinion of independent interest and a valuable contribution in itself, as it provides a general approach that can potentially be used in other contexts. We remark that our results apply also to the subclass of the classical polymatrix coordination games, for which in turn we get the ﬁrst upper and lower bounds on the Price of Anarchy for bounded-degree graphs, and the ﬁrst asymptotically tight lower bound on the Price of Stability for general graphs. Our results are summarized in Table 1. Due to space constraints, some of the proofs are only sketched, while all the details are deferred to the full version.

bounded-degree general

h [d] αh ( 1)h 1 P

h [d] αh( 1) h/2

2 P h [d] αh ( 1)h 1

(2+α2 (n 2)) (n 1)

2n 3 + α2(n 2)(n 3/2)

Table 1: Summary of our results, where UB and LB stands for upper and lower bound, respectively. Furthermore, denotes the maximal vertex degree in the bounded-degree case and αh, h [d], is the discounting factor for edges at distance h 1. The arrows denote that a result follows from an adjacent result in the table.

2 Model and Deﬁnitions Distance Polymatrix Coordination Games. Given an integer d 1, a d-distance polymatrix coordination game

G = (G, (Σx)x V , (we)e E, (px)x V , (αh)h [d])

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

is a tuple deﬁned as follows:

G = (V, E) is an undirected graph, where V is the set of players and E the set of edges between players.

For any x V , Σx is a ﬁnite set of strategies of player x. A strategy proﬁle σ = (σ1, . . . , σn) is a conﬁguration in which each player x V plays strategy σx Σx.

For any edge {v, z} E, let w{v,z} : Σv Σz R 0 be the weight function that assigns, to each pair of strategies σv, σz played respectively by v and z, a weight w{v,z}(σv, σz) 0.

For any x V , let px : Σx R 0 be the playerpreference function that assigns, to each strategy proﬁle σx played by player x, a non-negative real value px(σx), called player-preference.

Let (αh)h [d] be the distance-factors sequence of the game, that is a non-negative sequence of real parameters, called distance-factors, such that 1 = α1 α2 . . . αd 0.

In what follows, for the sake of brevity, given any strategy proﬁle σ, we will often denote w{v,z}(σv, σz) and px(σx) simply as w{v,z}(σ) and px(σ), respectively. For any h [d], let Eh(x) be the set of edges {v, z} such that the minimum distance between x and one of the players v and z is exactly h 1. Then, for any x V , the utility function ux : x V Σx R of player x, for any strategy proﬁle σ is deﬁned as

ux(σ) := px(σ) + X

e Eh(x) we(σ).

Remark 1. We observe that, if d = 1, we obtain the classical polymatrix coordination games, where the overall utility of player x only depends on payoffs we(σ) for e for which x is an endpoint. Instead, if d > 1, the overall utility of player x further depends on the discounted payoffs αh+1 w{v,z}(σ) arising by mutual actions of players v, z that are the endpoints of edges at any distance h < d from x.

Given a strategy proﬁle σ, the social welfare of σ is deﬁned as SW(σ) = P x V ux(σ). A social optimum of game G is a strategy proﬁle σ that maximizes the social welfare. We denote by OPT(G) = SW(σ ) the corresponding value.

k-strong Nash equilibrium. Given two strategy proﬁles σ = (σ1, . . . , σn) and σ = (σ 1, . . . , σ n), and a subset Z V , let σ Z σ be the strategy proﬁle σ = (σ 1, . . . , σ n) such that σ x = σ x if x Z, and σ x = σx otherwise. Given k 1, a strategy proﬁle σ is a k-strong Nash equilibrium of G if, for any strategy proﬁle σ and any Z V such that |Z| k, there exists x Z such that ux(σ) ux(σ Z σ ). Informally, σ is a k-strong Nash equilibrium if, for any coalition of at most k players deviating, there exists at least one player in the coalition that has no beneﬁt. We denote the (possibly empty) set of k-strong Nash equilibria of G by NEk(G).

k-strong Price of Anarchy (Po A) and Price of Stability (Po S). The k-strong Price of Anarchy of a game G is deﬁned as Po Ak(G) := maxσ NEk(G) OPT(G)

SW(σ) , i.e., it is the

Figure 1: The underlying graph of the d-distance polymatrix coordination game from Example 1 for n = 8, where the weight function has already been evaluated. In particular, the nodes playing strategy s are depicted as squares, and the ones playing s as hexagons.

worst-case ratio between the optimal social welfare and the social welfare of a k-strong Nash equilibrium. The k-strong Price of Stability of game G is deﬁned as Po Sk(G) := minσ NEk(G) OPT(G)

SW(σ) , i.e., it is the best-case ratio between the optimal social welfare and the social welfare of a k-strong Nash equilibrium. Clearly, Po Sk(G) Po Ak(G), whereas both quantities are not deﬁned if NEk(G) = . Example 1. Consider a d-distance polymatrix coordination game with n = 8 players whose underlying graph is a star (shown in Figure 1 for n = 8). Let Σx = {s, s } for every x [n], w{x,y}(σ) = 1 iff σx = σy = s and 0 otherwise. Furthermore, let p1(σ) = 1 iff σ1 = s and 0 otherwise, while all other player-preference functions are constant and equal to zero. Then, the strategy proﬁle in which all players play s is a k-strong Nash equilibrium for any k. The utility of player 1 for this strategy proﬁle is n 1, while for all other players it is 1 for d = 1 and 1 + (n 2)α2 for d 2.

3 k-strong Po A of Bounded-Degree Graphs In this section we compute upper and lower bounds on the k-strong Price of Anarchy of bounded-degree graphs. More formally, a game G is -bounded-degree if the degree of each node/player x V in graph G is at most . Remark 2. For k = 1, d 1, and = 1, there exists a simple -bounded-degree d-distance polymatrix coordination game G such that Po Ak(G) = [Rahn and Sch afer, 2015]. For sake of completeness, we present this example in the full version. Thus, as it is not possible to bound the kstrong Po A for k = 1, not even for bounded-degree graphs and not even when = 1, in the rest of the paper we will only focus on the estimation of the k-strong Po A for k 2. Furthermore, if = 1, w.l.o.g. we can assume that the graph consists of 2 agents and an edge between them. This special case is encompassed by Section 4, so here we will assume that 2. Theorem 1. For any integer k 2 and any -boundeddegree d-distance polymatrix coordination game G having a distance-factors sequence (αh)h [d], it holds that

Po Ak(G) 2 X

h [d] αh ( 1)h 1. (1)

Remark 3. From Eq. (1), notice that the k-strong price of anarchy of -bounded-degree d-distance polymatrix coordination games, as a function of d, grows at most as O(( 1)d).

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Before proving the theorem, we provide a lemma that gives an upper bound on the social welfare of any strategy proﬁle. Lemma 1. For any strategy proﬁle σ, it holds that SW(σ) P x V px(σ) + 2 P h [d] αh ( 1)h 1 P e E we(σ).

Proof. For any e E and h [d], let nh(e) := |{x V : e Eh(x)}|, i.e., nh(e) denotes how many players x V have distance equal to h 1 from e. We can see that X

e Eh(i) we(σ) = X

e E nh(e) we(σ). (2)

Furthermore, the number of players having distance h 1 to an edge e = {v, z} is at most equal to the number of simple paths starting from either v or z and having length h 1. This number is upper bounded by 2 ( 1)h 1. Therefore,

nh(e) 2 ( 1)h 1. (3)

By using (2) and (3), we get

x V px(σ) + X

e Eh(x) we(σ)

x V px(σ) + X

e E nh(e) we(σ)

x V px(σ) + X

h [d] αh nh(e) we(σ)

x V px(σ) + X

h [d] αh 2 ( 1)h 1we(σ)

x V px(σ) + 2 X

h [d] αh ( 1)h 1 X

thus showing the claim.

Proof of Theorem 1. Fix k 2. Let σ and σ be a worstcase k-strong Nash equilibrium and a social optimum of G, respectively. As k 2, σ is in particular also a 2-strong Nash equilibrium. Thus, for any edge e E, we know that there exists a player ve e, such that

uve(σ) uve(σ e σ ) pve(σ ) + we(σ ). (4)

For any e E, let ze denote the player in e \ {ve}. As σ is also a 1-strong Nash equilibrium, we have that

uze(σ) uze(σ {ze} σ ) pze(σ ). (5)

By using (4) and (5), we get X

e E (uve(σ) + uze(σ))

e E (pve(σ ) + pze(σ ) + we(σ ))

e E we(σ ) + X

h [d] αh ( 1)h 1

where (6) comes from Lemma 1. Furthermore, we get X

e E (uve(σ) + uze(σ)) X

x V ux(σ) = SW(σ), (7)

since, in the left-hand part of (7), the utility of each player is counted at most times. By putting together (6) and (7), we get SW(σ) 1 P e E (uve(σ) + uze(σ))

1 2 P h [d] αh ( 1)h 1 1 SW(σ ). This shows

the claim, since we get Po Ak(G) = SW(σ )

SW(σ) 2 P h [d] αh ( 1)h 1.

In the following theorem we provide a lower bound on the k-strong Price of Anarchy, relying on a nice construction from graph theory.

Theorem 2. For any k 2, 2, d 1, and any distancefactors sequence (αh)h [d], there exists a -bounded-degree d-distance polymatrix coordination game G such that

P h [d] αh ( 1)h 1 P h [d] αh( 1) h/2 . (8)

Remark 4. Notice that, if all the distance-factors are not lower than a constant c > 0, from Eq. (8) we can conclude that the k-strong price of anarchy of -bounded-degree ddistance polymatrix coordination games, as a function of d, can grow as Ω(( 1)d/2) (the formal proof of this remark is deferred to the full version).

Proof of Theorem 2. Fix k 2, 2, d 1, and a distance-factors sequence (αh)h [d]. By [Sachs, 1963], there exists an undirected graph G = (V, E) such that G is - regular (i.e., every node in V has degree ), and the girth1 of G is at least max{2d + 1, k + 1}. Let G be a -boundeddegree d-distance polymatrix coordination game such that: (i) G is its underlying graph; (ii) (αh)h [d] is its distancefactors sequence; (iii) each player x has two strategies, s and s ; (iv) for every edge e = {v, z} E and strategy proﬁle σ, we(σ) = 1 if both v and z play s in σ, and 0 otherwise; (v) for every x V , px(σ) = P h [d] αh( 1) h/2 if x plays s in σ, otherwise px(σ) = 0. Let σ and σ be the strategy proﬁles in which all players play strategy s and s , respectively. We present two technical lemmas, which use the above deﬁned properties of graph G.

Lemma 2. σ is a k-strong Nash equilibrium.

Proof sketch. We prove the claim by assuming that σ is not a k-strong Nash equilibrium, i.e., there exists a coalition Z with |Z| k such that all the players of Z get a beneﬁt when deviating simultaneously to their strategy in σ . As there exists no simple cycle with k edges in G, we have that the subgraph G induced by Z is a forest. We consider an arbitrary tree T of G and we ﬁx a root r of T. Then, we consider a player y corresponding to one of the deepest leaves of rooted tree T, and we assume w.l.o.g. that T is a complete tree of height d whose root has children and each other non-leaf node has 1 children (see Figure 2 for a clarifying

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Figure 2: The utility of a leaf node y in T, with root r, for = 4 and d = 4. Here, T denotes a perfect 3-ary tree of height 4.

example). Finally, we show that player y does not get any beneﬁt from the deviation, thus reaching a contradiction.

Lemma 3. ux(σ ) = P h [d] αh ( 1)h 1 for any x V .

Proof sketch. As graph G is -regular and the girth of G is at least 2d+1, we necessarily have that |Eh(x)| = ( 1)h 1 for every h [d]. To show the above equality, we observe that the subgraph of G made of all the edges at distance at most d 1 from x (i.e., all the edges in h [d]Eh(x)) is a perfect tree of depth d rooted in x such that each non-leaf node has degree . By using the above equality, for every x V it holds that ux(σ ) = P h [d] αh|Eh(x)| = P h [d] αh ( 1)h 1.

From Lemma 2 and 3, we get Po Ak(G)

x V ux(σ ) P

x V ux(σ) P

h [d] αh ( 1)h 1 P

h [d] αh( 1) h/2 .

4 k-strong Po A of General Graphs In this section, we provide tight bounds on the k-strong Price of Anarchy when there is no particular assumption on the underlying graph of the considered game. Such bounds depend on k, on the number of players n, and on the value α2 of the distance-factors sequence. Theorem 3. For any integer k 2 and any d-distance polymatrix coordination game G having a distance-factors sequence (αh)h [d], we have Po Ak(G) (2+α2 (n 2)) (n 1)

Before proving the theorem, we provide a lemma that, similarly to Lemma 1, gives an upper bound on the social welfare of any strategy proﬁle. Lemma 4. For any strategy proﬁle σ, it holds that SW(σ) P x V px(σ) + (2 + α2 (n 2)) P e E we(σ).

Proof sketch. We deﬁne nh(e) as in the proof of Lemma 1, and know that Eq. (2) holds. Furthermore, one can easily show that, for any e E, |n1(e)| = 2, and therefore Pd h=2 nh(e) = Pd h=1 nh(e) n1(e) n n1(e) = n 2. From here, by using Eq. (2), and the fact that α1 = 1 and α2 αh for any h [d] \ {1}, we get the claim.

Proof of Theorem 3. Fix k 2. Let σ and σ be a worstcase k-strong Nash equilibrium and a social optimum of G, respectively. As σ is a k-strong Nash equilibrium, we have that, for any Z V with |Z| = k, there exists a player

1the length of a shortest cycle contained in the graph

z1(Z) Z such that uz1(Z)(σ) uz1(Z)(σ Z σ ). Furthermore, there also exists a player z2(Z) Z(2) := Z\{z1}

such that uz2(Z)(σ) uz2(Z)(σ Z(2) σ ). If we proceed iteratively, we have that, for any i [k], there exists a player zi(Z) Z(i) := Z \ {z1(Z), . . . , zi 1(Z)} such that

uzi(Z)(σ) uzi(Z)(σ Z(i) σ ). (9)

Before continuing the proof, we present two technical lemmas below.

Lemma 5. n 1 k 1 SW(σ) = P Z V |Z|=k

P i [k] uzi(Z)(σ).

Lemma 6. It holds that X

i [k] uzx(Z)(σ Z(x) σ )

x V px(σ ) + n 2 k 2

e E we(σ ).

Proof of Theorem 3 (cont.). By putting together the auxiliary lemmas, we get n 1 k 1

i [k] uzi(Z)(σ) (10)

i [k] uzi(Z)(σ Z(i) σ ) (11)

x V px(σ ) + n 2 k 2

e E we(σ ) (12)

x V px(σ ) + X

(2 + α2 (n 2)) 1 SW(σ ), (13)

where (10), (11), (12), and (13), follow by Lemma 5, Eq. (9), Lemma 6, and Lemma 4, respectively. By exploiting (13), we

get Po Ak(G) ( n 1 k 1) (2+α2 (n 2))

( n 2 k 2) = (2+α2 (n 2)) (n 1)

thus showing the claim.

In the following theorem, we provide a tight lower bound.

Theorem 4. For any k 2, d 1, n 2, and any distancefactors sequence (αh)h [d], there is a d-distance polymatrix coordination game G with Po Ak(G) (2+α2 (n 2)) (n 1)

Proof sketch. Fix d 1, k 2, n 2, and a distance-factors sequence (αh)h [d]. Let G be the d-distance polymatrix coordination game of Example 1, having n players, (αh)h [d] as distance-factors sequence, and deﬁned as follows: (i) the underlying graph G is a star in which all the players x 2 are only connected to player 1; (ii) each player can play two strategies s, s only; (iii) we(σ) = 1 if all the players in e play strategy s under strategy proﬁle σ, and we(σ) = 0 otherwise; (iv) p1(σ) = k 1 if player 1 plays strategy s under

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

strategy proﬁle σ, and p1(σ) = 0 otherwise; (v) px(σ) = 0 for any strategy proﬁle σ and x 2. Let σ and σ be the strategy proﬁles in which all players play strategy s and s , respectively. We can show that σ is a k-strong Nash equilibrium and that Po Ak(G) SW(σ )

SW(σ) = (2+α2 (n 2)) (n 1)

5 The k-strong Po S of General Graphs

In this section we show that there exists a d-distance polymatrix coordination game G such that Po Sk(G) is asymptotically equal to the upper bound on Po Ak shown in Theorem 3, thus we completely characterize the inefﬁciency of d-distance polymatrix coordination games for general graphs. The modus operandi that we use to create the lower bound for Po Sk is to start from the lower bound instance on Po Ak provided in the proof of Theorem 4, in which the optimal outcome is a k-strong Nash equilibrium, and to suitably transform it in such a way that all the outcomes with social welfare close to the optimum, which we call set of almost optimal outcomes, cannot be stable. This is accomplished by inserting a cycle of improvement steps involving these solutions, that basically do not inﬂuence the social welfare. This technique is of independent interest, as it provides a general approach that can be potentially used in other contexts. Thus, we believe it is a valuable contribution in itself.

Theorem 5. For any n 6, there exists a d-distance polymatrix coordination game G such that Po Sk(G) = 2n 3 + α2(n 2)(n 3/2)

Proof. Let G be deﬁned as follows. The underlying graph G has n nodes and 2n 3 edges, where

E = {{1, h}, {2, ℓ} : h {2, . . . , n}, ℓ {3, . . . , n}}

(see Figure 3), and Σx = {1, 2, 3} for any x [n], i.e., each player can play the same three strategies. We call bottom layer, medium layer, and top layer the strategy proﬁle in which every player plays strategy 3, 2, and 1, respectively. We also shortly refer to strategies 3, 2, and 1 by bottom, medium, and top, respectively. We now deﬁne for each layer the player-preference and weight functions, where each entry that is not mentioned, we assume to be null. At the bottom layer p1(3) = p2(3) = (1 + α2)(1 + ϵ). At the medium layer, w{1,2}(2, 2) = w{1,h}(2, 2) = w{2,h}(2, 2) = 1+ϵ

k , where 3 h n. At the top layer p1(1) = p2(1) = 1 k, w{1,h}(1, 1) = w{2,h}(1, 1) = 1+ϵ

k , where 3 h n. Non-null edges between the layers are w{1,2}(1, 2) = 2ϵ

k , w{1,h}(1, 2) = w{1,h}(2, 1) = w{2,h}(1, 2) = w{2,h}(2, 1) = 1+ϵ

k , where 3 h n.

Figure 3: Graph G from the proof of Theorem 5 for n = 7.

player 2 top medium

top 1 k, 1 k 1+2ϵ

medium 0, 1 k 1+ϵ

Table 2: The part of the utility of player 1 and 2 coming from the player-preference and the weight w{1,2}(σ) for σ1, σ2 {1, 2}. No strategy proﬁle is stable, as always at least one player can improve her utility by deviating.

Lemma 7. The bottom layer is a k-strong equilibrium with social welfare 2(1 + α2)(1 + ϵ).

Lemma 8. All the k-strong equilibria have the same social welfare 2(1 + α2)(1 + ϵ).

Proof sketch. If there exists an equilibrium where both players 1 and 2 are at the bottom, then the social welfare is 2(1 + α2)(1 + ϵ), and we do not investigate further. If one of the players 1 and 2 is not at the bottom, then all the players will move to medium or top, starting from the ones different from 1 and 2. Finally, if both are not at the bottom, then at least one of the players 1 and 2 will always move. This is so, because each of them gets a constant utility from the remaining players, so they move just according to their bimatrix game, whose values are reported in Table 2.

The following lemma concludes the theorem.

Lemma 9. The ratio between the optimum social welfare and the social welfare given by one of the k-strong Nash stable strategy proﬁles, e.g., the bottom layer, is 2n 3 + α2(n 2)(n 3/2)

(1+α2)k , giving the Po Sk(G).

6 Conclusion In this work, we have introduced the class of d-distance polymatrix coordination games, and studied their performance (by means of the k-strong Price of Anarchy and Stability). Some open problems left by our work are that of closing the gap between the upper and lower bound on the strong Price of Anarchy for bounded-degree graphs, and providing better bounds on the strong Price of Stability speciﬁcally for the case of bounded-degree graphs. Another interesting research direction is extending the idea of obtaining utilities from non-neighboring players (as in [Flammini et al., 2020] and our work) to other graphical games [Kearns, 2007; Bil o et al., 2010], and then studying the social performance of their equilibria in general graphs or speciﬁc topologies.

Acknowledgements This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR Algorithms, Games, and Digital Markets .

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

References [Aloisio et al., 2020] Alessandro Aloisio, Michele Flammini, and Cosimo Vinci. The impact of selﬁshness in hypergraph hedonic games. In Proc. 34th Conf. Artiﬁcial Intelligence (AAAI), pages 1766 1773, 2020. [Ashlagi et al., 2008] Itai Ashlagi, Piotr Krysta, and Moshe Tennenholtz. Social context games. In Proc. 4th Intl. Workshop Internet & Network Economics (WINE), pages 675 683, 2008. [Aziz et al., 2011] Haris Aziz, Felix Brandt, and Hans Georg Seedig. Optimal partitions in additively separable hedonic games. In Proc. 22nd Intl. Joint Conf. Artif. Intell. (IJCAI), pages 43 48, 2011. [Aziz et al., 2019] Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. Fractional hedonic games. ACM Trans. Economics and Comput., 7(2):6:1 6:29, 2019. [Bil o et al., 2010] Vittorio Bil o, Angelo Fanelli, Michele Flammini, and Luca Moscardelli. When ignorance helps: Graphical multicast cost sharing games. Theoret. Comput. Sci., 411(3):660 671, 2010. [Bil o et al., 2018] Vittorio Bil o, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. Nash stable outcomes in fractional hedonic games: Existence, efﬁciency and computation. J. Artif. Intell. Res., 62:315 371, 2018. [Bil o et al., 2019] Vittorio Bil o, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. Optimality and nash stability in additive separable generalized group activity selection problems. In Proc. 28th Intl. Joint Conf. Artif. Intell. (IJCAI), pages 102 108, 2019. [Cai and Daskalakis, 2011] Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In Proc. 22nd Symp. Discr. Algorithms (SODA), pages 217 234, 2011. [Cai et al., 2016] Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos H. Papadimitriou. Zero-sum polymatrix games: A generalization of minmax. Math. Oper. Res., 41(2):648 655, 2016. [Carosi et al., 2019] Raffaello Carosi, Gianpiero Monaco, and Luca Moscardelli. Local core stability in simple symmetric fractional hedonic games. In Proc. 18th Conf. Autonomous Agents and Multi-Agent Systems (AAMAS), pages 574 582, 2019. [Darmann and Lang, 2017] Andreas Darmann and J erˆome Lang. Group activity selection problems. In Trends in computational social choice, pages 385 410. 2017. [Darmann et al., 2012] Andreas Darmann, Edith Elkind, Sascha Kurz, J erˆome Lang, Joachim Schauer, and Gerhard J. Woeginger. Group activity selection problem. In Proc. 8th Intl. Workshop Internet & Network Economics (WINE), volume 7695, pages 156 169, 2012. [Deligkas et al., 2017] Argyrios Deligkas, John Fearnley, Rahul Savani, and Paul G. Spirakis. Computing approx-

imate nash equilibria in polymatrix games. Algorithmica, 77(2):487 514, 2017. [Deligkas et al., 2020] Argyrios Deligkas, John Fearnley, and Rahul Savani. Tree polymatrix games are ppad-hard. In Proc. 47th Intl. Coll. Autom. Lang. Program. (ICALP), pages 38:1 38:14, 2020. [Dr eze and Greenberg, 1980] Jacquese H. Dr eze and Joseph Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4):987 1003, 1980. [Eaves, 1973] B. Curtis Eaves. Polymatrix games with joint constraints. SIAM Journal on Applied Mathematics, 24(3):418 423, 1973. [Elkind et al., 2020] Edith Elkind, Angelo Fanelli, and Michele Flammini. Price of Pareto Optimality in hedonic games. Artif. Intell., 288:103357, 2020. [Flammini et al., 2020] Michele Flammini, Bojana Kodric, Martin Olsen, and Giovanna Varricchio. Distance hedonic games. In Proc. 19th Conf. Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1846 1848, 2020. [Gairing and Savani, 2010] Martin Gairing and Rahul Savani. Computing stable outcomes in hedonic games. In Proc. 3rd Intl. Symp. Algorithmic Game Theory (SAGT), pages 174 185, 2010. [Howson and Rosenthal, 1974] Joseph Howson and Robert Rosenthal. Bayesian equilibria of ﬁnite two-person games with incomplete information. Management Sci., 21(3):313 315, 1974. [Howson, 1972] Joseph Howson. Equilibria of polymatrix games. Management Sci., 18(5-part-1):312 318, 1972. [Kearns, 2007] Michael Kearns. Graphical Games, page 159 180. Cambridge University Press, 2007. [Miller and Zucker, 1991] Douglas Miller and Steven Zucker. Copositive-plus Lemke algorithm solves polymatrix games. Oper. Res. Lett., 10(5):285 290, 1991. [Monaco et al., 2020] Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. Stable outcomes in modiﬁed fractional hedonic games. Auton. Agents Multi Agent Syst., 34(1):4, 2020. [Rahn and Sch afer, 2015] Mona Rahn and Guido Sch afer. Efﬁcient equilibria in polymatrix coordination games. In Proc. 40th Intl. Symp. Math. Foundations of Computer Science (MFCS), pages 529 541, 2015. [Sachs, 1963] Horst Sachs. Regular graphs with given girth and restricted circuits. Journal of the London Mathematical Society, 1(1):423 429, 1963. [Simon and Wojtczak, 2017] Sunil Simon and Dominik Wojtczak. Synchronisation games on hypergraphs. In Proc. 26th Intl. Joint Conf. Artif. Intell. (IJCAI), pages 402 408, 2017. [Yanovskaya, 1968] Elena B. Yanovskaya. Equilibrium points in polymatrix games. Lithuanian Mathematical Journal, 8(2):381 384, 1968.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)