We consider Social Distance Games (SDGs), that is cluster formation games in which agent utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. We adopt Nash stable outcomes, that is states in which no agent can im- prove her utility by unilaterally changing her coalition, as the target solution concept. Although SDGs always admit a Nash equilibrium, we prove that it is NP-hard to find a social wel- fare maximizing one and obtain a negative result concerning the game convergence. 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 num- ber of nodes of the underlying graph, and a lower bound on the price of stability of 6/5 − ε. Finally, we characterize the price of stability of SDGs for graphs with girth 4 and girth at least 5.

Nash Stability in Social Distance Games

Balliu, Alkida;FLAMMINI, MICHELE;Olivetti, Dennis
2017

Abstract

We consider Social Distance Games (SDGs), that is cluster formation games in which agent utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. We adopt Nash stable outcomes, that is states in which no agent can im- prove her utility by unilaterally changing her coalition, as the target solution concept. Although SDGs always admit a Nash equilibrium, we prove that it is NP-hard to find a social wel- fare maximizing one and obtain a negative result concerning the game convergence. 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 num- ber of nodes of the underlying graph, and a lower bound on the price of stability of 6/5 − ε. Finally, we characterize the price of stability of SDGs for graphs with girth 4 and girth at least 5.
978-1-57735-780-3
Algorithmic Game Theory; Nash Equilibria; Coalitions; Harmonic Distance Centralities
File in questo prodotto:
File Dimensione Formato  
2017_31stAAAICon_342_Balliu.pdf

accesso aperto

Descrizione: Articolo principale
Licenza: Accesso gratuito
676.64 kB 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/3176
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 11
social impact