On Pareto Optimality in Social Distance Games
Authors: Alkida Balliu, Michele Flammini, Dennis Olivetti
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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... We first show that, while computing a Pareto stable solution maximizing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ, n}-approximating one can be determined in polynomial time... We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs... |
| 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 Dennis Olivetti Gran Sasso Science Institute, Italy. dennis.olivetti@gssi.infn.it |
| Pseudocode | Yes | Stable solutions suitably approximating optimal ones can be determined according to the following algorithm: P , X = V , G(X) subgraph induced by X, i = 1; while X = do ui node of maximum degree in G(X); Nui set containing ui and its neighbors in G(X); P P {Nui}, X X \ Nui, i i + 1; G(X) subgraph induced by X; end |
| Open Source Code | No | The paper is theoretical and does not describe implementation details or mention the release of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not describe experiments or use any datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments or dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe computational experiments, therefore no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe implementation details that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setups, hyperparameters, or training configurations. |