We propose a new class of generalized distance polymatrix games, which extends distance polymatrix coordination games by allowing each subgame to be played by more than two agents. These games can be efe ctively modeled using hypergraphs, where each hyperedge represents a subgame played by its agents. Similar to distance polymatrix coordination games, the overall utility of a player depends on the payofs of subgames involving players within a certain distance from . As in the original model, these payofs are discounted proportionally by factors that depend on the distance of the corresponding hyperedges. After formalizing and motivating our model, we investigate the existence of exact and approximate strong equilibria. We also examine the degradation of social welfare using the standard measures of the Price of Anarchy and the Price of Stability, both for general and bounded-degree hypergraphs.
Polymatrix games [
In this paper, we present and study a new, more general model called generalized distance
polymatrix games, where each local game can involve more than two players, and the utility of
an agent can depend on games at a distance bounded by . In this new model, the interaction
graph is represented as an undirected hypergraph, with each hyperedge corresponding to a
game played by the players it includes. Following the idea proposed in [
Our model is related to polymatrix coordination games [
Given two integers ≥ 1 and ≥ 1, let [] = {1, . . . , } and define the falling factorial as () := · ( − 1) · . . . · ( − + 1). A weighted hypergraph is a triple ℋ = (, , ) consisting of a finite set = [] of nodes, a collection ⊆ 2 of hyperedges, and a weight : → R associating a real value () with each hyperedge ∈ . For simplicity, when referring to weighted hypergraphs, we omit the term “weighted”. The arity of a hyperedge is its size ||. An -hypergraph is a hypergraph such that the arity of each hyperedge is at most , where 2 ≤ ≤ . A complete -hypergraph is a hypergraph (, , ) such that := { ⊆ : | | ≤ }. A uniform -hypergraph is a hypergraph such that the arity of each hyperedge is . An undirected graph is a uniform 2-hypergraph. A hypergraph is said to be ∆ -regular if each of its nodes is contained in exactly ∆ hyperedges. It is said to be linear if any two of its hyperedges share at most one node. A hypergraph is called a hypertree if it admits a host graph such that is a tree. Given two distinct nodes and in a hypergraph ℋ, a − simple path of length in ℋ is a sequence of distinct hyperedges (1, . . . , ) of ℋ, such that ∈ 1, ∈ , ∩ +1 ̸= ∅, for every ∈ [ − 1], and ∩ = ∅ whenever > + 1. The distance from to , (, ), is the length of the shortest − simple path in ℋ. A cycle in a hypergraph ℋ is defined as a simple path (1, . . . , ), but the further condition 1 ∩ ̸= ∅ must hold. This definition of cycle is originally due to Berge, and it can be also stated as an alternating sequence of 1, 1, 2, . . . , , of distinct vertices and distinct hyperedges so that each contains both and +1. The girth of a hypergraph is the length of the shortest cycle it contains.
Generalized Distance Polymatrix Games. A generalized distance polymatrix game (or GDPG) = (ℋ, (Σ )∈ , ()∈ , ()∈ , ( ℎ)ℎ∈[]), is a game based on an -hypergraph ℋ, and defined as follows: Agents: The set of agents is = [], i.e., each node corresponds to an agent. We reasonably assume that ≥ ≥ 2.
Strategy profile or outcome: For any ∈ , Σ is a finite set of strategies of player . A strategy profile or outcome = ( 1, . . . , ) is a configuration in which each player ∈ plays strategy ∈ Σ .
Weight function: For any hyperedge ∈ , let : × ∈Σ → R≥ 0 be the weight function that assigns, to each subset of strategies played respectively by every ∈ , a weight ( ) ≥ 0. In what follows, for the sake of brevity, given any strategy profile , we will often denote ( ) simply as ( ).
Preference function: For any ∈ , let : Σ → R≥ 0 be the player-preference function that assigns, to each strategy played by player , a non-negative real value ( ), called player-preference. In what follows, for the sake of brevity, given any strategy profile , we will often denote ( ) simply as ( ).
Distance-factors sequence: 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.
Utility function: For any ℎ ∈ [], let ℎ() be the set of hyperedges such that the minimum distance between and one of the players ∈ is exactly ℎ − 1. Then, for any ∈ , the utility function : × ∈ Σ → R of player , for any strategy profile is defined as ( ) := ( ) + ∑︀ℎ∈[] ℎ ∑︀∈ℎ() ( ).
The social welfare SW( ) of a strategy profile is defined as the sum of all the agents’ utilities in , i.e., SW( ) := ∑︀∈ ( ). A social optimum of game is a strategy profile * that maximizes the social welfare. We denote by OPT() = SW( * ) the corresponding value. -approximate -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 -approximate -strong Nash equilibrium (or (, )-equilibrium) of if, for any strategy profile * and any ⊆ such that || ≤ , there exists ∈ such that ( ) ≥ ( → * ). We say that a player -improves from a deviation → * if ( ) < ( ′). Informally, is a (, )-equilibrium if, for any coalition of at most players deviating, there exists at least one player in the coalition that does not -improve her utility by deviating. We denote the (possibly empty) set of (, )-equilibria of by NE (). Clearly, if = 1, NE () contains all the -strong equilibria, and when = 1 and = 1, it contains the classic Nash equilibria.
NE () = ∅. (, )-Price of Anarchy (PoA) and (, )-Price of Stability (PoS). The (, )-Price of Anarchy of a game is defined as PoA () := max ∈NE () OSPWT(()) , i.e., it is the worstcase ratio between the optimal social welfare and the social welfare of a (, )-equilibrium. OPT() , i.e., it The (, )-Price of Stability of game is defined as PoS () := min ∈NE () SW( ) is the best-case ratio between the optimal social welfare and the social welfare of a (, )Nash equilibrium. Clearly, PoS () ≤ PoA (), whereas both quantities are not defined if
First, we analyze the existence of -approximate -strong equilibria and investigate the degradation of social welfare when a deviation from the current strategy profile can involve up to agents. Consequently, we compute tight bounds on the resulting Price of Anarchy and Stability.
Since (, )-equilibria may not exist since they cannot always exist even in polymatrix
coordination games [
We say that a game has a finite (, )-improvement property (or (, )-FIP for short) if every sequence of (, )-improving deviations is finite. In such a case, we necessarily have that any (, )-FIP ends in a (, )-equilibrium, which implies the latter’s existence, too.
For a given hyperedge and a subset ⊆ , let ℎ () := |{ ∈ : ∈ ℎ()}|, i.e., ℎ () is the number of players ∈ that are at distance ℎ − 1 from .
Theorem 1. Let be a GDPG. Then: i) has the (, 1)-FIP for every ≥ 1; ii) has the (, )-FIP for every ≥ max⊆ :{max∈{∑︀ℎ∈[] ℎℎ ()}} and for every .
||=
The value ∑︀ℎ∈[] ℎℎ () strictly depends on and ℎ (). When = 1, we have ∑︀ℎ∈[] ℎℎ () = 1 () ≤ | | for every ∈ and ⊆ , so we can assume ≥ . When the hypergraph of a game is a hyperlist, we have ∑︀ℎ∈[] ℎℎ () ≤ 2 ∑︀ℎ∈[] ℎ, for every ∈ , and ⊆ . When the hypergraph of a game is a hypertree of maximum degree ∆ , we have ∑︀ℎ∈[] ℎℎ () ≤ ∑︀ℎ∈[] ℎℎ− 1∆ ℎ− 1, for every ∈ , and ⊆ .
We provide here tight upper and lower bounds for the (, )-Price of Anarchy when the hypergraph ℋ of a game is general. We also show a lower bound for the (1, )-Price of Stability asymptotically equal to the upper bound for the (1, )-Price of Anarchy. First we remark that for any integers ≥ 1, ≥ 2, < , and ≥ , there exists a simple GDPG with agents such that PoA () = ∞. Thus, we will only take into account the estimation of the (, )-PoA for ≥ ≥ 2 since it is not possible to bound the (, )-PoA for < , not even for bounded-degree graphs and not even when ∆ = 1 .
Theorem 2. For any ≥ 1, any integer ≥ and any GDPG having a distance-factors sequence ( ℎ)ℎ∈[], it holds that
PoA () ≤ ( − 1)− 1 ( + 2( − 2))
( − 1)− 1 .
Theorem 3. For every ≥ 1, every integers ≥ 2, ≥ , ≥ 1, ≥ , and every -distancefactors sequence ( ℎ)ℎ∈[], there is a GDPG with
PoA () ≥ ( − 1)− 1 ( + 2( − ))
( − 1)− 1 .
We conclude this section by providing a lower bound for PoS1(), which can be used alongside the upper bound in Theorem 2 to characterize the (1, )-Price of Stability. Theorem 4. For any ≥ 6, there exists a GDPG such that
− ( − 1)− 1 ( + 2( − ))
PoS1() ≥ − 1 ( − 1)− 1 2(1 + 2)
In this section, we analyze the (, )-Price of Anarchy for games whose hypergraphs have bounded-degree. We also say that a game is ∆ -bounded degree if the degree of every node in the underlying hypergraph is at most ∆ . Here, we will only focus on the cases where ≥ , as already observed, and ∆ ≥ 2, since the case when ∆ = 1 is encompassed by Section 3.2. Theorem 5. For every ∆ -bounded-degree GDPG , with distance-factor sequence ( ℎ)ℎ∈[], and for every ≥ , it holds that
PoA () ≤ · ∑︁ ℎ · ∆ · (∆ − 1)ℎ− 1ℎ− 1
ℎ∈[]
Theorem 6. For every ≥ 1, any integers ≥ , ∆ ≥ 3, ≥ 1, and any distance-factors sequence ( ℎ)ℎ∈[], there exists a ∆ -bounded-degree GDPG such that .
PoA () ≥ · ∑︀ℎ∈[] ℎ∆(∆
− 1)ℎ− 1ℎ− 1 1 + ∑︀ℎ−=11 ℎ+1(2(∆ − 1)⌊(ℎ+1)/2⌋( − 1)⌊(ℎ+1)/2⌋− 1 + 2(∆ − 1)⌊ℎ/2⌋− 1( − 1)⌊ℎ/2⌋) Remark 1. Please note that, if all the distance-factors are not lower than a constant > 0, from Theorem 6 we can conclude that the (, )-price of anarchy of ∆ -bounded-degree GDPG, as a function of , can grow as Ω( (∆ − 1)/2( − 1)/2).
This study leaves some open problems, such as (i) closing the gap between the upper and the lower bound on the Price of Anarchy for bounded-degree hypergraphs; (ii) extending the results on the Price of Stability to values of greater than one; and (iii) computing a lower bound on the Price of Stability for bounded-degree hypergraphs.
We acknowledge: the project ‘Soluzioni innovative per il problema della copertura nelle multiinterfacce e relative varianti’, UNINT, the PNRR MIUR project FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI; the PNRR MIUR project VITALITY (ECS00000041), Spoke 2 ASTRA - Advanced Space Technologies and Research Alliance; the PNRR MIUR project HaMMon - Hazard Mapping and vulnerability Monitoring, Innovation Grant; the PNRR MIUR project SERICS - Security and Rights in Cyber Space (PE00000014), Spoke 2 - Misinformation and Fakes; the Italian MIUR PRIN 2017 project ALGADIMAR - Algorithms, Games, and Digital Markets (2017R9FHSR_002); GNCS-INdAM. in Additive Separable Generalized Group Activity Selection Problems, in: Proc. 28th Intl.
Joint Conf. Artif. Intell. (IJCAI), 2019, pp. 102–108. [14] I. Ashlagi, P. Krysta, M. Tennenholtz, Social Context Games, in: Proc. 4th Intl. Workshop
Internet & Network Economics (WINE), 2008, pp. 675–683. [15] V. Bilò, A. Celi, M. Flammini, V. Gallotti, Social context congestion games, Theoret.
Comput. Sci. 514 (2013) 21–35. [16] 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. [17] 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. [18] 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. [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.