# The Price of Proportional Representation in Temporal Voting

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

## Key facts

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

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

- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Equity of Attention: Amortizing Individual Fairness in Rankings](https://mlsanity.com/paper/1805.01788/) (2018)
- [Fairness in Rankings and Recommendations: An Overview](https://mlsanity.com/paper/2104.05994/) (2021)
- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Proportional Participatory Budgeting with Additive Utilities](https://mlsanity.com/paper/2008.13276/) (2020)
- [Proportional Justified Representation](https://mlsanity.com/paper/1611.09928/) (2016)
- [Robust and Verifiable Proportionality Axioms for Multiwinner Voting](https://mlsanity.com/paper/2302.01989/) (2023)
- [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)
- [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)
- [Better Collective Decisions via Uncertainty Reduction](https://mlsanity.com/paper/2207.04983/) (2022)
- [Verifying Proportionality in Temporal Voting](https://mlsanity.com/paper/2502.05949/) (2025)
- [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)
- [Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting](https://mlsanity.com/paper/2312.08187/) (2023)
- [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)
- [Welfare vs. Representation in Participatory Budgeting](https://mlsanity.com/paper/2201.07546/) (2022)
- [A Generalised Theory of Proportionality in Collective Decision Making](https://mlsanity.com/paper/2307.06077/) (2023)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)
- [Proportionality for Constrained Public Decisions](https://mlsanity.com/paper/2409.02609/) (2024)

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

- [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 study proportional representation in the temporal voting model, where collective decisions are made repeatedly over time over a fixed horizon. Prior work has extensively investigated how proportional representation axioms from multiwinner voting (e.g., justified representation (JR) and its variants) can be adapted, satisfied, and verified in this setting. However, much less is understood about their interaction with social welfare. In this work, we quantify the efficiency cost of enforcing proportionality. We formalize the welfare-proportionality tension via the worst-case ratio between the maximum achievable utilitarian welfare and the maximum welfare attainable subject to a proportionality axiom. We show that imposing proportional representation in the temporal setting can incur a growing, yet sublinear, welfare loss as the number of voters or rounds increases. We further identify a clean separation among axioms: for JR, the welfare loss diminishes as the time horizon grows and vanishes asymptotically, whereas for stronger axioms this conflict persists even with many rounds. Moreover, we prove that welfare maximization under each axiom is NP-complete and APX-hard, even under static preferences and bounded-degree approvals, and provide fixed-parameter algorithms under several natural structural parameters.