Efficient Local Search in Coordination Games on Graphs
Authors: Sunil Simon, Dominik Wojtczak
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study strategic games on weighted directed graphs, where the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy augmented by a fixed non-negative bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. Prior work shows that the problem of determining the existence of a pure Nash equilibrium for these games is NP-complete already for graphs with all weights equal to one and no bonuses. However, for several classes of graphs (e.g. DAGs and cliques) pure Nash equilibria or even strong equilibria always exist and can be found by simply following a particular improvement or coalition-improvement path, respectively. In this paper we identify several natural classes of graphs for which a finite improvement or coalition-improvement path of polynomial length always exists, and, as a consequence, a Nash equilibrium or strong equilibrium in them can be found in polynomial time. We also argue that these results are optimal in the sense that in natural generalisations of these classes of graphs, a pure Nash equilibrium may not even exist. |
| Researcher Affiliation | Academia | Sunil Simon IIT Kanpur Kanpur, India Dominik Wojtczak University of Liverpool Liverpool, U.K. |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. It focuses on theoretical proofs and properties of games. |
| Open Source Code | No | The paper does not provide any explicit statement or link indicating that open-source code for the described methodology is available. |
| Open Datasets | No | The paper describes theoretical work on games and graphs, not empirical experiments involving datasets or training. |
| Dataset Splits | No | The paper describes theoretical work on games and graphs, not empirical experiments involving datasets or validation splits. |
| Hardware Specification | No | The paper is theoretical and does not discuss hardware specifications for experiments. Although 'computer simulations' are mentioned for a conjecture, no hardware details are provided. |
| Software Dependencies | No | The paper describes theoretical work and does not specify software dependencies with version numbers needed to replicate any experimental results. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |