Variety-Seeking Jump Games on Graphs

Narayanan, Lata; Opatrny, Jaroslav; Tummala, Shanmukha; Voudouris, Alexandros A.

doi:10.24963/ijcai.2025/446

Variety-Seeking Jump Games on Graphs

Lata Narayanan, Jaroslav Opatrny, Shanmukha Tummala, Alexandros A. Voudouris

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 4005-4013.

https://doi.org/10.24963/ijcai.2025/446

Keywords

Game Theory and Economic Paradigms: GTEP: Noncooperative games

Abstract

We consider a class of jump games in which agents of different types occupy the nodes of a graph aiming to maximize the variety of types in their neighborhood. In particular, each agent derives a utility equal to the number of types different from its own in its neighborhood. We show that the jump game induced by the strategic behavior of the agents (who aim to maximize their utility) may in general have improving response cycles, but is a potential game under any of the following four conditions: there are only two types of agents; or exactly one empty node; or the graph is of degree at most 2; or the graph is 3-regular and there are two empty nodes. Additionally, we show that on trees, cylinder graphs, and tori, there is always an equilibrium. Finally, we show tight bounds on the price of anarchy with respect to two different measures of diversity: the social welfare (the total utility of the agents) and the number of colorful edges (that connect agents of different types).

Lata Narayanan, Jaroslav Opatrny, Shanmukha Tummala, and Alexandros A. Voudouris. 2025. Variety-Seeking Jump Games on Graphs. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 4005–4013. https://doi.org/10.24963/ijcai.2025/446

@inproceedings{ijcai2025p446,
  title     = {Variety-Seeking Jump Games on Graphs},
  author    = {Narayanan, Lata and Opatrny, Jaroslav and Tummala, Shanmukha and Voudouris, Alexandros A.},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {4005--4013},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/446},
  url       = {https://doi.org/10.24963/ijcai.2025/446},
}

TY  - CPAPER
TI  - Variety-Seeking Jump Games on Graphs
AU  - Narayanan, Lata
AU  - Opatrny, Jaroslav
AU  - Tummala, Shanmukha
AU  - Voudouris, Alexandros A.
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 4005
EP  - 4013
DO  - 10.24963/ijcai.2025/446
UR  - https://doi.org/10.24963/ijcai.2025/446
ER  -