Nash Stability in Social Distance Games

Authors

  • Alkida Balliu Gran Sasso Science Institute
  • Michele Flammini University of L'Aquila and Gran Sasso Science Institute
  • Giovanna Melideo University of L'Aquila
  • Dennis Olivetti Gran Sasso Science Institute

DOI:

https://doi.org/10.1609/aaai.v31i1.10608

Keywords:

Algorithmic Game Theory, Coalition Formation, Social Distance Games, Nash Stability

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 improve 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 welfare 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 number 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.

Downloads

Published

2017-02-10

How to Cite

Balliu, A., Flammini, M., Melideo, G., & Olivetti, D. (2017). Nash Stability in Social Distance Games. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10608

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms