# Temporal Elections: Welfare, Strategyproofness, and Proportionality

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 24 Aug 2024.

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

- [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)
- [Repeated Fair Allocation of Indivisible Items](https://mlsanity.com/paper/2304.01644/) (2023)
- [Multiwinner Temporal Voting with Aversion to Change](https://mlsanity.com/paper/2408.11017/) (2024)
- [Better Collective Decisions via Uncertainty Reduction](https://mlsanity.com/paper/2207.04983/) (2022)
- [The Price of Fairness for Indivisible Goods](https://mlsanity.com/paper/1905.04910/) (2019)
- [Approval-Based Apportionment](https://mlsanity.com/paper/1911.08365/) (2019)
- [When Votes Change and Committees Should (Not)](https://mlsanity.com/paper/2005.02300/) (2020)
- [Settling the Score: Portioning with Cardinal Preferences](https://mlsanity.com/paper/2307.15586/) (2023)
- [Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting](https://mlsanity.com/paper/2312.08187/) (2023)
- [Strategyproofness and Proportionality in Party-Approval Multiwinner Elections](https://mlsanity.com/paper/2211.13567/) (2022)
- [Line-Up Elections: Parallel Voting with Shared Candidate Pool](https://mlsanity.com/paper/2007.04960/) (2020)
- [Obvious Manipulability of Voting Rules](https://mlsanity.com/paper/2111.01983/) (2021)

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

- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Not in My Backyard! Temporal Voting Over Public Chores](https://mlsanity.com/paper/2508.08810/) (2025)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [The Price of Proportional Representation in Temporal Voting](https://mlsanity.com/paper/2605.11157/) (2026)
- [Optimal bounds for dissatisfaction in perpetual voting](https://mlsanity.com/paper/2501.01969/) (2024)
- [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)
- [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 investigate a model of sequential decision-making where a single alternative is chosen at each round. We focus on two objectives -- utilitarian welfare (Util) and egalitarian welfare (Egal) -- and consider the computational complexity of maximizing these objectives, as well as their compatibility with strategyproofness and proportionality. We observe that maximizing Util is easy, but the corresponding decision problem for Egal is NP-complete even in restricted cases. We complement this hardness result for Egal with parameterized complexity analysis and an approximation algorithm. Additionally, we show that, while a mechanism that outputs an outcome that maximizes Util is strategyproof, all deterministic mechanisms for computing outcomes that maximize Egal fail a very weak variant of strategyproofness, called non-obvious manipulability (NOM). However, we show that when agents have non-empty approval sets at each timestep, choosing an Egal-maximizing outcome while breaking ties lexicographically satisfies NOM. Regarding proportionality, we prove that a proportional (PROP) outcome can be computed efficiently, but finding an outcome that maximizes Util while guaranteeing PROP is NP-hard. We also derive upper and lower bounds on the (strong) price of proportionality with respect to Util and Egal. Some of our results extend to p-mean welfare measures other than Egal and Util.