On Non-Cooperativeness in Social Distance Games

Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

82 Lataukset (Pure)

Abstrakti

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 6/5 − ε, for any ε > 0. Finally, we characterize the price of stability 5 of SDGs for graphs with girth 4 and girth at least 5, the girth being the length of the shortest cycle in the graph.
AlkuperäiskieliEnglanti
Sivut625-653
JulkaisuJournal of Artificial Intelligence Research
Vuosikerta66
TilaJulkaistu - 2019
OKM-julkaisutyyppiA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Sormenjälki

Sukella tutkimusaiheisiin 'On Non-Cooperativeness in Social Distance Games'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä