Game Implementation: What Are the Obstructions?
Authors: Jiehua Chen, Seyedeh Negar Layegh Khavidaki, Sebastian Vincent Haydn, Sofia Simola, Manuel Sorge
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that GAME IMPLEMENTATION is NP-hard even for two players, solving in particular a long-standing open question and suggesting more restrictions are necessary to obtain tractability results. We thus study the regime in which players have only a small constant number of strategies and obtain the following. First, this case remains NP-hard even if each player s utility depends only on three others. Second, we repair a flawed efficient algorithm for the case of both small number of strategies and small number of players. Among further results, we characterize sets of desired strategies that can be implemented at zero cost as a generalization of Nash equilibria. |
| Researcher Affiliation | Academia | TU Wien, Austria {jiehua.chen, seyedehngar.khavidaki, sofia.simola, manuel.sorge}@tuwien.ac.at, e51832021@student.tuwien.ac.at |
| Pseudocode | Yes | Algorithm 1: Minimum cost exact implementation |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | This paper is theoretical and does not involve empirical evaluation on datasets, thus no information on public dataset availability for training is provided. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical evaluation on datasets, thus no information on training/validation/test splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments requiring specific hardware, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on proofs and algorithm design, not implementation details requiring specific software versions or dependencies. |
| Experiment Setup | No | The paper is theoretical and does not report on empirical experiments, thus no experimental setup details are provided. |