In polymatrix coordination games, each player 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 is given by the preference she has for her action plus, for each neighbor , a payof which strictly depends on the mutual actions played by and . We propose the new class of distance polymatrix coordination games, properly generalizing polymatrix coordination games, in which the overall utility of player further depends on the payofs arising from mutual actions of players , that are the endpoints of edges at any distance ℎ < from , for a fixed threshold value ≤ . In particular, the overall utility of player is the sum of all the above payofs, where each payof is proportionally discounted by a factor depending on the distance ℎ 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 ineficiency 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 bounded-degree and general graphs.
Polymatrix games [
In this paper, we generalize polymatrix coordination games by allowing players to receive a further payof from the interactions in which they are not personally involved. The idea here is that each player benefits not only from good relations with her immediate neighbours but also from the positive environment stemming from good relations between them and their respective immediate neighbours. A further generalization of this thought brings us to a model in which the utility is computed as the sum of the payofs from the whole connected component of the interaction graph up to a certain maximal distance , where is a parameter of the model. Furthermore, it seems reasonable to discount the payof received from nonneighbouring 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 gets also the payof ℎ+1 · {,}( , ) for every edge {, } at distance ℎ < from , where ℎ+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 efects 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 payof, which is taken into account by our discount factors.
In the setting described above, we will be focusing on the eficiency of the system. Our reference point for stability will be -strong Nash equilibria, which are action profiles from which no group of up to agents can simultaneously deviate such that all of them profit from the deviation. Our analysis provides bounds which depend on and the discounting factors for the part of the utility of the agents coming from non-first-hand interactions.
A full version of our results can be found in [
Another model related to our work is the group activity selection problem [
The idea of obtaining utility from non-neighbouring 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 payofs [ 18]. They generalize fractional hedonic games [19, 20, 21, 22, 23] similarly as our model does with polymatrix games.
Distance Polymatrix Coordination Games. Given an integer ≥ 1, a -distance polymatrix coordination game = (, (Σ )∈ , ()∈ , ()∈ , ( ℎ)ℎ∈[]) is a tuple defined as follows: • = (, ) is an undirected graph, where is the set of players and the set of edges between players. • For any ∈ , Σ is a finite set of strategies of player . A strategy profile = ( 1, . . . , ) is a configuration in which each player ∈ plays strategy ∈ Σ . • For any edge {, } ∈ , let {,} : Σ × Σ → R≥ 0 be the weight function that assigns, to each pair of strategies , played respectively by and , a weight {,}( , ) ≥ 0. • For any ∈ , let : Σ → R≥ 0 be the player-preference function that assigns, to each strategy profile played by player , a non-negative real value ( ), called player-preference. • Let ( ℎ)ℎ∈[] 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 ≥ . . . ≥ ≥ 0.
In what follows, for the sake of brevity, given any strategy profile , we will often denote {,}( , ) and ( ) simply as {,}( ) and ( ), respectively. For any ℎ ∈ [], let ℎ() be the set of edges {, } such that the minimum distance between and one of the players and is exactly ℎ − 1. Then, for any ∈ , the utility function : × ∈ Σ → R of player , for any strategy profile is defined as ( ) := ( ) + ∑︀ℎ∈[] ℎ ∑︀∈ℎ() ( ). Given a strategy profile , the social welfare of is defined as SW( ) = ∑︀∈ ( ). A social optimum of game is a strategy profile * that maximizes the social welfare. We denote by OPT() = SW( * ) the corresponding value. there exists ∈ such that ( ) ≥ ( -strong Nash equilibria of by NE(). -strong Nash equilibrium. Given two strategy profiles = ( 1, . . . , ) and * = ( 1*, . . . , *), and a subset ⊆ , let → * be the strategy profile ′ = ( 1′, . . . , ′) such that ′ = * if ∈ , and ′ = otherwise. Given ≥ 1, a strategy profile is a -strong Nash equilibrium of if, for any strategy profile * and any ⊆ such that || ≤ , → * ). We denote the (possibly empty) set of -strong Price of Anarchy (PoA) and Price of Stability (PoS). The -strong Price of AnOPT() , i.e., it is the worst-case ratio archy of a game is defined as PoA() := max ∈NE() SW( ) between the optimal social welfare and the social welfare of a -strong Nash equilibrium. The OPT() , i.e., it is the -strong Price of Stability of game is defined as PoS() := min ∈NE() SW( ) best-case ratio between the optimal social welfare and the social welfare of a -strong Nash equilibrium.
We study the ineficiency of -stable Nash equilibria of -distance 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.1, we give upper and lower bounds for bounded-degree graphs, with the gap being reasonably small, and in Section 3.2, a tight bound on the Price of Anarchy for general graphs. Finally, in Section 3.3, we show that in general graphs, the Price of Stability is asymptotically equal to the Price of Anarchy, meaning that the ineficiency of -strong equilibria is fully characterized. We remark that our results also apply 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.
In this section we compute upper and lower bounds on the -strong Price of Anarchy of bounded-degree graphs. More formally, a game is ∆ -bounded-degree if the degree of each node/player ∈ in graph is at most ∆ .
First we remark that for = 1, ≥ 1, and ∆ = 1 , there exists a simple ∆ -bounded-degree
-distance polymatrix coordination game such that PoA() = ∞ [
Theorem 1. For any integer ≥ 2 and any ∆ -bounded-degree -distance polymatrix coordination game having a distance-factors sequence ( ℎ)ℎ∈[], it holds that
PoA() ≤ 2 ∑︁ ℎ · ∆ · (∆ − 1)ℎ− 1.
ℎ∈[] Remark 1. From Eq. (1), notice that the -strong price of anarchy of ∆ -bounded-degree distance polymatrix coordination games, as a function of , grows at most as ((∆ − 1)).
In the following theorem we provide a lower bound on the -strong Price of Anarchy, relying on a nice construction from graph theory.
Theorem 2. For any ≥ 2, ∆ ≥ 2, ≥ 1, and any distance-factors sequence ( ℎ)ℎ∈[], there exists a ∆ -bounded-degree -distance polymatrix coordination game such that PoA() ≥ ∑︀ℎ∈[] ℎ · ∆ · (∆ − 1)ℎ− 1 ∑︀ℎ∈[] ℎ(∆ − 1)⌊ℎ/2⌋
(1) (2) Remark 2. Notice that, if all the distance-factors are not lower than a constant > 0, from Eq. (2) we can conclude that the -strong price of anarchy of ∆ -bounded-degree -distance polymatrix coordination games, as a function of , can grow as Ω((∆ − 1)/2).
In this section, we provide tight bounds on the -strong Price of Anarchy when there is no particular assumption on the underlying graph of the considered game. Such bounds depend on , on the number of players , and on the value 2 of the distance-factors sequence. Theorem 3. For any integer ≥ 2 and any -distance polymatrix coordination game having a distance-factors sequence ( ℎ)ℎ∈[], we have
PoA() ≤ (2 + 2 · ( − − 21)) · ( − 1) .
In the following theorem, we provide a tight lower bound.
Theorem 4. For any ≥ 2, ≥ 1, ≥ 2, and any distance-factors sequence ( ℎ)ℎ∈[], there is a -distance polymatrix coordination game with
In this section, we show that there exists a -distance polymatrix coordination game such that PoS() is asymptotically equal to the upper bound on PoA shown in Theorem 3; thus we characterise entirely the ineficiency of -distance polymatrix coordination games for general graphs. The modus operandi that we use to create the lower bound for PoS is to start from the lower bound instance on PoA provided in the proof of Theorem 4, in which the optimal outcome is a -strong Nash equilibrium, and to suitably transform it in such a way that all the outcomes with social welfare close to the optimum cannot be stable.
Theorem 5. For any ≥ 6, there exists a -distance polymatrix coordination game such that PoS() = 2 − 3 + 2( − 2)( − 3/2) (1 + 2)
In this work, we have introduced the class of -distance polymatrix coordination games and studied their performance (by means of the -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-neighbouring players (as in [18] and our work) to other graphical games [24, 25], and then studying the social performance of their equilibria in general graphs or specific topologies.
Joint Conf. Artif. Intell. (IJCAI), 2019, pp. 102–108. [18] M. Flammini, B. Kodric, M. Olsen, G. Varricchio, Distance Hedonic Games, in: Proc. 19th
Conf. Autonomous Agents and Multi-Agent Systems (AAMAS), 2020, pp. 1846–1848. [19] H. Aziz, F. Brandl, F. Brandt, P. Harrenstein, M. Olsen, D. Peters, Fractional Hedonic
Games, ACM Trans. Economics and Comput. 7 (2019) 6:1–6:29. [20] E. Elkind, A. Fanelli, M. Flammini, Price of Pareto Optimality in hedonic games, Artif.
Intell. 288 (2020) 103357. [21] G. Monaco, L. Moscardelli, Y. Velaj, Stable outcomes in modified fractional hedonic games,
Auton. Agents Multi Agent Syst. 34 (2020) 4. [22] R. Carosi, G. Monaco, L. Moscardelli, Local Core Stability in Simple Symmetric Fractional Hedonic Games, in: Proc. 18th Conf. Autonomous Agents and Multi-Agent Systems (AAMAS), 2019, pp. 574–582. [23] V. Bilò, A. Fanelli, M. Flammini, G. Monaco, L. Moscardelli, Nash Stable Outcomes in Fractional Hedonic Games: Existence, Eficiency and Computation, J. Artif. Intell. Res. 62 (2018) 315–371. [24] M. Kearns, Graphical Games, Cambridge University Press, 2007, p. 159–180. [25] V. Bilò, A. Fanelli, M. Flammini, L. Moscardelli, When ignorance helps: Graphical multicast cost sharing games, Theoret. Comput. Sci. 411 (2010) 660–671.