Variety-Seeking Jump Games on Graphs
Authors: Lata Narayanan, Jaroslav Opatrny, Shanmukha Tummala, Alexandros A. Voudouris
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We first show that such games may have an improving response cycle, even when G is 3-regular and |V | = n+3. This means that there is an initial assignment of the agents to the nodes of the graph so that if the agents jump one by one to empty nodes of the graph, they will eventually cycle back to that initial assignment; in other words, starting from such an assignment, an equilibrium cannot be reached. In spite of this impossibility, we show that the game is potential (that is, the Nash dynamics converges to an equilibrium) under any of the following conditions: k = 2; |V | = n + 1; the graph is of degree at most 2; the graph is 3-regular and |V | = n+2. Additionally, we show that there is always an equilibrium when the graph is a tree, or a cylinder, or a torus by carefully constructing one for these cases. We next switch to analyzing the quality of equilibria under two different objectives: The social welfare (defined as the total utility of the agents) and the number of colorful edges (defined as the number of edges between agents of different types). Both objectives are different measures of diversity and have been considered before by [Li et al., 2025] for the case of swap games. We show tight bounds on the price of anarchy, which quantifies the loss in the social welfare or the number of colorful edges in the worst equilibrium. In particular, we show that the price of anarchy with respect to social welfare is Θ(n) for general games, and Θ(k) for symmetric types (that is, when all types are of the same cardinality). For colorful edges, we show that the price of anarchy is Θ(n) even for symmetric types, and Θ(δ) when the graph is δ-regular and the types are symmetric. In addition, for both objectives, we provide lower bounds on the price of stability, showing that there are instances in which the optimal assignment is not necessarily an equilibrium. |
| Researcher Affiliation | Academia | Lata Narayanan1 , Jaroslav Opatrny1 , Shanmukha Tummala1 and Alexandros A. Voudouris2 1Department of Computer Science and Software Engineering, Concordia University 2School of Computer Science and Electronic Engineering, University of Essex EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes methods and proofs in prose and mathematical notation but does not include any explicitly labeled pseudocode or algorithm blocks. Figures 1-4 are diagrams of graphs, not algorithmic procedures. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the methodology described, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper mentions data from the General Social Survey [Smith et al., 2019] in the introduction as background for diversity, but this is not a dataset used for empirical evaluation within this paper's methodology. The paper is theoretical and does not conduct experiments on datasets. |
| Dataset Splits | No | The paper describes a theoretical framework and does not involve experiments with datasets that would require training/test/validation splits. |
| Hardware Specification | No | The paper focuses on theoretical analysis of game properties and does not describe any experimental setup or hardware specifications. |
| Software Dependencies | No | The paper presents theoretical results and proofs; therefore, it does not mention any software dependencies or specific version numbers required for replication. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, hyperparameters, or training configurations. |