Distance Preservation Games

Aziz, Haris; Chan, Hau; Lederer, Patrick; Narang, Shivika; Walsh, Toby

doi:10.24963/ijcai.2025/415

Distance Preservation Games

Haris Aziz, Hau Chan, Patrick Lederer, Shivika Narang, Toby Walsh

Download BibTeX Cite

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

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

Keywords

Game Theory and Economic Paradigms: GTEP: Computational social choice
Game Theory and Economic Paradigms: GTEP: Noncooperative games
Game Theory and Economic Paradigms: GTEP: Cooperative games

Abstract

We introduce and analyze distance preservation games (DPGs). In DPGs, agents express ideal distances to other agents and need to choose locations in the unit interval while preserving their ideal distances as closely as possible. We analyze the existence and computation of location profiles that are jump stable (i.e., no agent can benefit by moving to another location) or welfare optimal for DPGs, respectively. Specifically, we prove that there are DPGs without jump stable location profiles and identify important cases where such outcomes always exist and can be computed efficiently. Similarly, we show that finding welfare optimal location profiles is NP-complete and present approximation algorithms for finding solutions with social welfare close to optimal. Finally, we prove that DPGs have a price of anarchy of at most 2.

Haris Aziz, Hau Chan, Patrick Lederer, Shivika Narang, and Toby Walsh. 2025. Distance Preservation Games. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3735–3743. https://doi.org/10.24963/ijcai.2025/415

@inproceedings{ijcai2025p415,
  title     = {Distance Preservation Games},
  author    = {Aziz, Haris and Chan, Hau and Lederer, Patrick and Narang, Shivika and Walsh, Toby},
  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     = {3735--3743},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/415},
  url       = {https://doi.org/10.24963/ijcai.2025/415},
}

TY  - CPAPER
TI  - Distance Preservation Games
AU  - Aziz, Haris
AU  - Chan, Hau
AU  - Lederer, Patrick
AU  - Narang, Shivika
AU  - Walsh, Toby
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  - 3735
EP  - 3743
DO  - 10.24963/ijcai.2025/415
UR  - https://doi.org/10.24963/ijcai.2025/415
ER  -