Individual Rationality in Topological Distance Games Is Surprisingly Hard
Authors: Argyrios Deligkas, Eduard Eiben, Dušan Knop, Šimon Schierreich
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of finding individually rational outcomes; this notion is widely assumed to be the very minimal stability requirement and requires that the utility of every agent in a solution is nonnegative. We perform a comprehensive study of the problem s complexity, and we prove that even in very basic cases, deciding whether an individually rational solution exists is intractable. and We perform a comprehensive and in-depth study of the complexity of individual rationality (IR) in topological distance games with the aim of identifying the precise cut-off between tractable and intractable classes of instances. |
| Researcher Affiliation | Collaboration | Argyrios Deligkas1 , Eduard Eiben1 , Duˇsan Knop2 and ˇSimon Schierreich2 1Royal Holloway, University of London 2Czech Technical University in Prague {argyrios.deligkas,eduard.eiben}@rhul.ac.uk, {dusan.knop,schiesim}@fit.cvut.cz |
| Pseudocode | Yes | Theorem 6. There is an algorithm for the IR-TOPOLOGICAL DISTANCE GAME problem running in |V (G)|O(|N|) time. Proof. The algorithm is a simple brute-force. We exhaustively try all assignments of vertices of the topology to agents. Then, in polynomial time, we verify whether the checked possibility assigns to each agent a different vertex and whether the assignment is individually rational. If this is the case, we return yes as the result. Otherwise, if no possibility leads to an individually rational assignment, we return no. |
| Open Source Code | No | Due to space constraints, some details are omitted and are available in the full version of the paper [Deligkas et al., 2024b]. No other mentions of code availability. |
| Open Datasets | No | The paper presents theoretical results on computational complexity and does not involve the use of datasets for training, validation, or testing. |
| Dataset Splits | No | The paper presents theoretical results on computational complexity and does not involve the use of datasets for training, validation, or testing, thus no split information is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity; it does not describe any experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or versions required for experiments. |
| Experiment Setup | No | The paper is theoretical, presenting computational complexity results rather than experimental setups or hyperparameters. |