Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
On Non-Cooperativeness in Social Distance Games
Authors: Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti
JAIR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Alkida Balliu EMAIL Department of Computer Science, Aalto University, Finland & Gran Sasso Science Institute, Italy Michele Flammini EMAIL Gran Sasso Science Institute & DISIM University of L Aquila, Italy Giovanna Melideo EMAIL DISIM University of L Aquila, Italy Dennis Olivetti EMAIL Department of Computer Science, Aalto University, Finland & Gran Sasso Science Institute, Italy |
| Pseudocode | No | The paper describes theoretical proofs and game theory concepts. It does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code, nor does it mention any intention to release it. |
| Open Datasets | No | The paper primarily presents theoretical analysis and proofs regarding Social Distance Games and graph properties. It constructs graph instances for illustrative purposes and proofs (e.g., Figure 1, Figure 11, Figure 14, Figure 15, Figure 16) but does not refer to external or publicly available datasets. |
| Dataset Splits | No | The paper does not use or analyze any external datasets, therefore, no dataset splits are discussed. |
| Hardware Specification | No | The paper is theoretical in nature and does not describe experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and analysis, therefore, it does not describe an experimental setup or hyperparameters. |