Bounding the Inefficiency of Compromise
Authors: Ioannis Caragiannis, Panagiotis Kanellopoulos, Alexandros A. Voudouris
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We formulate simple games that capture this behavior and quantify the inefficiency of equilibria using the well-known notion of the price of anarchy. Our results indicate that compromise comes at a cost that strongly depends on the neighborhood size.Technical contribution. We study questions related to the existence, computational complexity, and quality of equilibria in k-COF games. We show that there exist simple 1-COF games that do not admit pure Nash equilibria and, furthermore, that even in games where equilibria exist, their quality may be suboptimal, i.e., the price of stability (defined in [Anshelevich et al., 2008]) is strictly greater than 1. |
| Researcher Affiliation | Academia | Ioannis Caragiannis University of Patras caragian@ceid.upatras.gr Panagiotis Kanellopoulos CTI & University of Patras kanellop@ceid.upatras.gr Alexandros A. Voudouris University of Patras voudouris@ceid.upatras.gr |
| Pseudocode | No | The paper describes algorithms conceptually (e.g., 'standard algorithms for computing shortest or longest paths in directed acyclic graphs') but does not provide any explicitly labeled 'Pseudocode' or 'Algorithm' blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use any datasets, thus no information regarding public dataset availability is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, therefore it does not discuss training/validation/test splits. |
| Hardware Specification | No | The paper focuses on theoretical contributions and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper focuses on theoretical contributions and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training settings. |