# Not in My Backyard! Temporal Voting Over Public Chores

arXiv: https://arxiv.org/abs/2508.08810 · HTML: https://mlsanity.com/paper/2508.08810/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 47 references that are in the map.
- First posted on arXiv 12 Aug 2025.

## Builds on (most cited first, 29 of 29)

- [Multi-Winner Voting with Approval Preferences](https://mlsanity.com/paper/2007.01795/) (2020)
- [Fair Allocation of Indivisible Public Goods](https://mlsanity.com/paper/1805.03164/) (2018)
- [Fair Public Decision Making](https://mlsanity.com/paper/1611.04034/) (2016)
- [Proportional Aggregation of Preferences for Sequential Decision Making](https://mlsanity.com/paper/2306.14858/) (2023)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [Repeated Fair Allocation of Indivisible Items](https://mlsanity.com/paper/2304.01644/) (2023)
- [Temporal Elections: Welfare, Strategyproofness, and Proportionality](https://mlsanity.com/paper/2408.13637/) (2024)
- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Multiwinner Temporal Voting with Aversion to Change](https://mlsanity.com/paper/2408.11017/) (2024)
- [Equitable Allocations of Indivisible Goods](https://mlsanity.com/paper/1905.10656/) (2019)
- [Better Collective Decisions via Uncertainty Reduction](https://mlsanity.com/paper/2207.04983/) (2022)
- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [The Price of Fairness for Indivisible Goods](https://mlsanity.com/paper/1905.04910/) (2019)
- [Temporal Fair Division](https://mlsanity.com/paper/2410.23416/) (2024)
- [When Votes Change and Committees Should (Not)](https://mlsanity.com/paper/2005.02300/) (2020)
- [On Maximum Weighted Nash Welfare for Binary Valuations](https://mlsanity.com/paper/2204.03803/) (2022)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions](https://mlsanity.com/paper/2202.08713/) (2022)
- [Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting](https://mlsanity.com/paper/2312.08187/) (2023)
- [Algorithms for Competitive Division of Chores](https://mlsanity.com/paper/1907.01766/) (2019)
- [The Price of Justified Representation](https://mlsanity.com/paper/2112.05994/) (2021)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [The Leximin Approach for a Sequence of Collective Decisions](https://mlsanity.com/paper/2305.18024/) (2023)
- [Fair Division of Chores with Budget Constraints](https://mlsanity.com/paper/2410.23979/) (2024)
- [Competitive division of a mixed manna](https://mlsanity.com/paper/1702.00616/) (2017)
- [On the Proximity of Markets with Integral Equilibria](https://mlsanity.com/paper/1811.08673/) (2018)
- [Free-Riding in Multi-Issue Decisions](https://mlsanity.com/paper/2310.08194/) (2023)
- [Optimal bounds for dissatisfaction in perpetual voting](https://mlsanity.com/paper/2501.01969/) (2024)

## Built on by (most cited first, 6 of 6)

- [The Price of Proportional Representation in Temporal Voting](https://mlsanity.com/paper/2605.11157/) (2026)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)
- [Strengthening Full Justified Representation: Efficient Verification and Computation](https://mlsanity.com/paper/2608.11500/) (2026)
- [AI of the People, by the People, for the People: A Social Choice Approach to Collective Control of Artificial Intelligence](https://mlsanity.com/paper/2605.16291/) (2026)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)
- [Proportional Representation in Temporal Voting with Ranked Preferences](https://mlsanity.com/paper/2609.30555/) (2026)

## Abstract (arXiv)

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.