Nash Stability in Social Distance Games
Authors: Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Alkida Balliu Gran Sasso Science Institute, Italy. alkida.balliu@gssi.infn.it Michele Flammini DISIM University of L Aquila & Gran Sasso Science Institute, Italy. michele.flammini@univaq.it Giovanna Melideo DISIM University of L Aquila, Italy. giovanna.melideo@univaq.it Dennis Olivetti Gran Sasso Science Institute, Italy. dennis.olivetti@gssi.infn.it |
| Pseudocode | No | The paper describes theoretical concepts and proofs, but does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper makes no mention of providing concrete access to source code for the methodology described. |
| Open Datasets | No | The paper focuses on theoretical analysis and proofs in game theory, not on empirical evaluations using datasets. Therefore, it does not provide concrete access information for a publicly available or open dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments or data splitting. Therefore, it does not provide specific dataset split information needed to reproduce data partitioning. |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments that would require specific hardware details. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific ancillary software details with version numbers needed to replicate an experiment. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details, such as hyperparameter values, training configurations, or system-level settings. |