Not in My Backyard! Temporal Voting Over Public Chores

Elkind, Edith; Neoh, Tzeh Yuan; Teh, Nicholas

doi:10.24963/ijcai.2025/424

Not in My Backyard! Temporal Voting Over Public Chores

Edith Elkind, Tzeh Yuan Neoh, Nicholas Teh

Download BibTeX Cite

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

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

Keywords

Game Theory and Economic Paradigms: GTEP: Fair division
Game Theory and Economic Paradigms: GTEP: Computational social choice

Abstract

We study a temporal voting model where voters have dynamic preferences over a set of public chores---projects that benefit society, but impose individual costs on those affected by their implementation. We investigate the computational complexity of optimizing utilitarian and egalitarian welfare. Our results show that while optimizing the former is computationally straightforward, minimizing the latter is computationally intractable, even in very restricted cases. Nevertheless, we identify several settings where this problem can be solved efficiently, either exactly or by an approximation algorithm. We also examine the effects of enforcing temporal fairness and its impact on social welfare, and analyze the competitive ratio of online algorithms. We then explore the strategic behavior of agents, providing insights into potential malfeasance in such decision-making environments. Finally, we discuss a range of fairness measures and their suitability for our setting.

Edith Elkind, Tzeh Yuan Neoh, and Nicholas Teh. 2025. Not in My Backyard! Temporal Voting Over Public Chores. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3814–3820. https://doi.org/10.24963/ijcai.2025/424

@inproceedings{ijcai2025p424,
  title     = {Not in My Backyard! Temporal Voting Over Public Chores},
  author    = {Elkind, Edith and Neoh, Tzeh Yuan and Teh, Nicholas},
  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     = {3814--3820},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/424},
  url       = {https://doi.org/10.24963/ijcai.2025/424},
}

TY  - CPAPER
TI  - Not in My Backyard! Temporal Voting Over Public Chores
AU  - Elkind, Edith
AU  - Neoh, Tzeh Yuan
AU  - Teh, Nicholas
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  - 3814
EP  - 3820
DO  - 10.24963/ijcai.2025/424
UR  - https://doi.org/10.24963/ijcai.2025/424
ER  -