Distance Polymatrix Coordination Games

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 benefits 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 scientific community obviously benefit 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 benefits, 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 profits 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 benefit 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 efficiency of the system. Our reference point for stability will be k-strong Nash equilibria, which are action profiles from which no group of up to k agents can simultaneously deviate such that all of them profit from the deviation. Such a definition also includes the standard notion of Nash equilibria for k = 1. However, we will see that only for k ≥ 2 the inefficiency 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-first-hand interactions.

1.1 RelatedWork

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 fixed 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 fixed 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 finding 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 inefficiency 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 ineffieciency 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 first upper and lower bounds on the Price of Anarchy for bounded-degree graphs, and the first 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.

2 Model and Definitions

Distance Polymatrix Coordination Games. Given an integer d ≥ 1, a d-distance polymatrix coordination game

is a tuple defined 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 finite set of strategies of player x. A strategy profile σ = (σ1, . . . , σn) is a configuration 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 profile σ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 profile σ, 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 profile σ is defined as

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 profile σ, the social welfare of σ is defined as SW(σ) = ∑x∈V ux(σ). A social optimum of game G is a strategy profile σ∗ that maximizes the social welfare. We denote by OPT(G) = SW(σ∗ ) the corresponding value.

k-strong Nash equilibrium. Given two strategy profiles σ = (σ1, . . . , σn) and σ∗ = (σ∗ 1 , . . . , σ∗n ), and a subset Z ⊆ V , let σ Z→ σ∗ be the strategy profile σ′ = (σ′1 , . . . , σ′n ) such that σ′x = σ∗x if x ∈ Z, and σ′x = σx otherwise. Given k ≥ 1, a strategy profile σ is a k-strong Nash equilibrium of G if, for any strategy profile σ∗ 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 benefit. We denote the (possibly empty) set of k-strong Nash equilibria of G by NEk(G).

k-strong Price of Anarchy (PoA) and Price of Stability (PoS). The k-strong Price of Anarchy of a game G is defined as PoAk(G) := maxσ∈NEk(G) OPT(G) SW(σ) , i.e., it is the 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 defined as PoSk(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, PoSk(G) ≤ PoAk(G), whereas both quantities are not defined 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 profile in which all players play s∗ is a k-strong Nash equilibrium for any k. The utility of player 1 for this strategy profile 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 PoA 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 PoAk(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 PoA 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 PoA 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

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 ).

Before proving the theorem, we provide a lemma that gives an upper bound on the social welfare of any strategy profile.

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

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,

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

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

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

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

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

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 · ∑e∈E (uve (σ) +uze (σ)) ≥ ∆-1 · (2 ∑h∈[d] αh · (∆- 1)h-1)-1 · SW(σ∗ ). This shows the claim, since we get PoAk(G) = SW(σ∗ ) SW(σ) ≤ 2 ∑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

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 girth 1 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 profile σ, we(σ) = 1 if both v and z play s∗ in σ, and 0 otherwise; (v) for every x ∈ V , px(σ) = ∑h∈[d] αh(∆- 1)⌊h/2⌋ if x plays s in σ, otherwise px(σ) = 0. Let σ and σ∗ be the strategy profiles in which all players play strategy s and s∗ , respectively. We present two technical lemmas, which use the above defined 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 benefit 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 fix 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 example). Finally, we show that player y does not get any benefit from the deviation, thus reaching a contradiction.

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(σ∗ ) = ∑h∈[d] αh|Eh(x)| = ∑h∈[d] αh∆(∆ - 1)h-1 .

4 k-strong PoA 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 PoAk(G) ≤ (2+α2·(n-2))·(n-1) k-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 profile.

Proof sketch. We define 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 ∑dh=2 nh(e) = ∑dh=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 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

1 the length of a shortest cycle contained in the graph

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

Lemma 6. It holds that

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

where (10), (11), (12), and (13), follow by Lemma 5, Eq. (9), Lemma 6, and Lemma 4, respectively. By exploiting (13), we get PoAk(G) ≤ (n-1 k-1)·(2+α2·(n-2)) (n-2 k-2) = (2+α2·(n-2))·(n-1) k-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 PoAk(G) ≥ (2+α2·(n-2))·(n-1) k-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 defined 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 profile σ, and we(σ) = 0 otherwise; (iv) p1(σ) = k - 1 if player 1 plays strategy s under strategy profile σ, and p1(σ) = 0 otherwise; (v) px(σ) = 0 for any strategy profile σ and x ≥ 2. Let σ and σ∗ be the strategy profiles in which all players play strategy s and s∗ , respectively. We can show that σ is a k-strong Nash equilibrium and that PoAk(G) ≥ SW(σ∗ ) SW(σ) = (2+α2·(n-2))·(n-1) k-1 .

5 The k-strong PoS of General Graphs

In this section we show that there exists a d-distance polymatrix coordination game G such that PoSk(G) is asymptotically equal to the upper bound on PoAk shown in Theorem 3, thus we completely characterize the inefficiency of d-distance polymatrix coordination games for general graphs.

The modus operandi that we use to create the lower bound for PoSk is to start from the lower bound instance on PoAk 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 influence 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.

Proof. Let G be defined as follows. The underlying graph G has n nodes and 2n - 3 edges, where

(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 profile 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 define 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) = 1k , 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.

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 profiles, e.g., the bottom layer, is 2n-3 + α2(n-2)(n-3/2) , giving the PoSk(G).

(1+α2)k

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 specifically 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 specific topologies.

Acknowledgements

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