We consider Social Distance Games (SDGs), that is cluster formation games in which the utility of each agent only depends on the composition of the cluster she belongs to, proportionally to her harmonic centrality, i.e., to the average inverse distance from the other agents in the cluster. Under a non-cooperative perspective, we adopt Nash stable outcomes, in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although a Nash equilibrium for a SDG can always be computed in polynomial time, we obtain a negative result concerning the game convergence and we prove that computing a Nash equilibrium that maximizes the social welfare is NP-hard by a polynomial time reduction from the NP-complete Restricted Exact Cover by 3-Sets problem. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph. Moreover, we show that there exists a class of SDGs having a lower bound on the price of stability of 56 − ε, for any ε > 0. Finally, we characterize the price of stability of SDGs for graphs with girth 4 and girth at least 5, the girth being the length of the shortest cycle in the graph.

On non-cooperativeness in social distance games

Balliu A.
;
Flammini M.
;
Olivetti D.
2019

Abstract

We consider Social Distance Games (SDGs), that is cluster formation games in which the utility of each agent only depends on the composition of the cluster she belongs to, proportionally to her harmonic centrality, i.e., to the average inverse distance from the other agents in the cluster. Under a non-cooperative perspective, we adopt Nash stable outcomes, in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although a Nash equilibrium for a SDG can always be computed in polynomial time, we obtain a negative result concerning the game convergence and we prove that computing a Nash equilibrium that maximizes the social welfare is NP-hard by a polynomial time reduction from the NP-complete Restricted Exact Cover by 3-Sets problem. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph. Moreover, we show that there exists a class of SDGs having a lower bound on the price of stability of 56 − ε, for any ε > 0. Finally, we characterize the price of stability of SDGs for graphs with girth 4 and girth at least 5, the girth being the length of the shortest cycle in the graph.
File in questo prodotto:
File Dimensione Formato  
2019_J ArtifIntellRes_66_Balliu.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Dominio pubblico
Dimensione 1.58 MB
Formato Adobe PDF
1.58 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12571/1288
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact