We investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. Pareto optimal solutions have been already consid- ered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable un- der the deviation of the grand coalition, as they do not per- mit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximiz- ing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ,√n}-approximating one can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combina- tions: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges.

On Pareto Optimality in Social Distance Games

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

Abstract

We investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. Pareto optimal solutions have been already consid- ered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable un- der the deviation of the grand coalition, as they do not per- mit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximiz- ing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ,√n}-approximating one can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combina- tions: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges.
978-1-57735-780-3
File in questo prodotto:
File Dimensione Formato  
2017_31stAAAICon_349_Balliu.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Accesso gratuito
Dimensione 688.45 kB
Formato Adobe PDF
688.45 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/3337
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 12
social impact