arxiv: 2605.11157 · v1 · submitted 2026-05-11 · 💻 cs.GT · cs.AI· cs.LG· cs.MA· econ.TH

Recognition: 2 theorem links

· Lean Theorem

The Price of Proportional Representation in Temporal Voting

Nicholas Teh

Authors on Pith no claims yet

Pith reviewed 2026-05-13 00:45 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.LGcs.MAecon.TH

keywords temporal votingproportional representationjustified representationutilitarian welfarewelfare losscomputational complexityAPX-hardness

0 comments

The pith

Enforcing proportional representation in repeated collective decisions creates a sublinear welfare loss.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper quantifies the efficiency cost of satisfying proportionality axioms such as justified representation when voters make decisions repeatedly over a fixed horizon. It measures this cost through the worst-case ratio of maximum possible utilitarian welfare to the maximum welfare achievable while meeting the axiom. The loss grows with the number of voters or rounds but stays sublinear, and it disappears asymptotically for justified representation while remaining bounded away from zero for stronger axioms. The work also proves that finding welfare-maximizing outcomes under these axioms is computationally hard in general but admits efficient algorithms when certain structural parameters are bounded.

Core claim

The central claim is that the worst-case ratio between unconstrained utilitarian welfare and welfare under a proportionality axiom grows with the number of voters and rounds yet remains sublinear in both quantities. For justified representation the ratio tends to one as the time horizon lengthens, while for extended justified representation and other stronger axioms a constant-factor gap persists independently of horizon length.

What carries the argument

The worst-case welfare-proportionality ratio, which takes the supremum over all preference profiles of the ratio of maximum achievable welfare to the maximum welfare attainable while satisfying the given proportionality axiom.

If this is right

The welfare loss under justified representation vanishes asymptotically as the time horizon grows.
Stronger axioms such as extended justified representation maintain a persistent welfare gap even with arbitrarily many rounds.
Finding the welfare-maximizing outcome subject to any of the axioms is NP-complete and APX-hard even when preferences are static and approval degrees are bounded.
Fixed-parameter algorithms solve the welfare maximization problem efficiently under natural structural parameters such as bounded number of candidates or treewidth.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

In long-running decision systems designers might favor basic justified representation over stronger variants to keep efficiency losses small.
The sublinear growth suggests that moderate-sized instances may incur only modest practical costs despite the theoretical worst-case bound.
Similar ratio analyses could be applied to other repeated allocation problems outside formal voting, such as dynamic committee scheduling.

Load-bearing premise

The tension is captured by worst-case ratios over all possible preference profiles, and the vanishing result for justified representation assumes that near-optimal proportional outcomes exist in sufficiently long horizons.

What would settle it

A family of approval profiles where the welfare ratio under justified representation grows linearly with the number of rounds instead of sublinearly would disprove the main efficiency claim.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper quantifies the sublinear welfare cost of proportionality in temporal voting, with JR vanishing asymptotically and new complexity results.

read the letter

The punchline for this paper is that requiring proportional representation over multiple rounds of voting leads to a welfare loss that grows but stays sublinear in the number of voters or rounds, and for the standard justified representation axiom this loss actually shrinks to zero as the time horizon gets longer, unlike stronger axioms where the gap stays. They also show that finding the best welfare outcome under these constraints is computationally hard. This work stands out for being the first to quantify that efficiency cost in the temporal setting. Previous papers focused on defining and satisfying the axioms in repeated decisions, but this one measures the exact ratio of welfare with and without the proportionality requirement. The separation result is particularly clean: JR becomes asymptotically efficient while others do not. The complexity side is also well done, with proofs of NP-completeness and APX-hardness that hold even when preferences do not change across rounds and when each voter approves only a bounded number of alternatives, plus fixed-parameter tractable algorithms for natural parameters like the number of rounds or voters. There are a couple of softer points. Since everything is worst-case, the reported bounds might be pessimistic for real-world preference data. The stress-test note questions whether the vanishing welfare loss for JR survives fully adversarial preference changes every round, where new groups might keep demanding representation and force repeated low-welfare choices. The abstract indicates the hardness results apply to static preferences, which suggests the authors have a construction for the positive JR result that works in the dynamic case too, but it would be good to verify if the proof assumes some stability or handles arbitrary changes. No major contradictions or circularity in the claims. This paper is aimed at people in computational social choice who work on multi-winner or temporal voting problems. Anyone studying fairness axioms and their efficiency implications will find the quantitative results and the algorithmic contributions valuable. It shows clear thinking on the axioms and engages properly with the existing literature on representation and welfare. I would bring it to a reading group for discussion on the bounds and the dynamic aspects. It deserves serious peer review as the contributions are specific and build directly on prior work without overclaiming.

Referee Report

2 major / 2 minor

Summary. The paper studies the price of proportional representation in temporal voting, where decisions repeat over a fixed horizon T. It formalizes the welfare-proportionality tension as the worst-case ratio between unconstrained utilitarian welfare and welfare under a proportionality axiom (JR or stronger variants). Main claims are that this ratio is sublinear in n and T, that the ratio for JR vanishes asymptotically as T grows while the conflict persists for stronger axioms, that welfare maximization subject to each axiom is NP-complete and APX-hard even under static preferences and bounded-degree approvals, and that FPT algorithms exist under natural structural parameters.

Significance. If the results hold, the work provides a valuable quantification of the efficiency cost of proportionality in repeated collective decisions, with a clean axiomatic separation that distinguishes JR from stronger rules. The sublinear bound and vanishing result for JR are positive for the practical viability of proportionality, while the hardness results (even in the static case) and FPT algorithms add computational insight. The paper ships formal proofs of the bounds, separation, and complexity results.

major comments (2)

[§5] §5 (JR vanishing result): The claim that the welfare ratio for JR approaches 1 as T → ∞ requires that, for any preference profile, a JR-satisfying outcome sequence exists whose total welfare is (1-o(1)) of the unconstrained optimum. In the general temporal model with arbitrary dynamic approval changes across rounds, satisfying temporal JR (cumulative or sliding-window) can force repeated low-welfare selections to cover emerging groups, which may prevent vanishing. The hardness results are shown even for static preferences; please clarify whether the vanishing proof is restricted to static preferences or extends to the full dynamic case used in the model definition.
[§6.1] §6.1 (APX-hardness): The reduction for APX-hardness of welfare maximization under JR is given for static preferences with bounded-degree approvals. Confirm whether the same reduction (or a direct adaptation) establishes APX-hardness in the dynamic temporal setting, or if the dynamic case requires separate arguments, as this affects the scope of the computational results.

minor comments (2)

[§2] The notation for the welfare ratio (e.g., definition of the price function) could be introduced in the model section rather than deferred to the results, to improve readability.
[Table 1] Table 1 (complexity summary): The entry for FPT algorithms lists parameters but omits the exact running-time dependence; adding the explicit f(k) form would help.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. We appreciate the positive evaluation of the paper's significance and the specific suggestions for clarification on the scope of our results. We address each major comment below.

read point-by-point responses

Referee: [§5] §5 (JR vanishing result): The claim that the welfare ratio for JR approaches 1 as T → ∞ requires that, for any preference profile, a JR-satisfying outcome sequence exists whose total welfare is (1-o(1)) of the unconstrained optimum. In the general temporal model with arbitrary dynamic approval changes across rounds, satisfying temporal JR (cumulative or sliding-window) can force repeated low-welfare selections to cover emerging groups, which may prevent vanishing. The hardness results are shown even for static preferences; please clarify whether the vanishing proof is restricted to static preferences or extends to the full dynamic case used in the model definition.

Authors: We thank the referee for this insightful question. The vanishing result is established for the general temporal model, including arbitrary dynamic preference changes. The proof constructs a JR-satisfying sequence by allocating a vanishing fraction of rounds to cover newly emerging groups while prioritizing high-welfare candidates in the remaining rounds; because the number of distinct groups that can emerge is bounded by n and the horizon is T, the fraction of 'coverage' rounds is o(1) as T grows. We will add a short clarifying paragraph in §5 explicitly stating that the argument holds in the dynamic case and briefly indicating why emerging groups do not prevent the o(1) term. revision: yes
Referee: [§6.1] §6.1 (APX-hardness): The reduction for APX-hardness of welfare maximization under JR is given for static preferences with bounded-degree approvals. Confirm whether the same reduction (or a direct adaptation) establishes APX-hardness in the dynamic temporal setting, or if the dynamic case requires separate arguments, as this affects the scope of the computational results.

Authors: The APX-hardness carries over immediately to the dynamic setting. The static-preference instance is a special case of the temporal model in which approvals are identical across all rounds; therefore any hardness result for the static case directly implies hardness for the general dynamic model. We will insert one clarifying sentence in §6.1 making this reduction inheritance explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results derive from independent worst-case analysis and complexity proofs

full rationale

The paper defines the welfare-proportionality tension explicitly as the worst-case ratio of utilitarian welfare to welfare under a proportionality axiom, with all quantities (JR, stronger axioms, temporal horizons) introduced as independent primitives before any bounds or hardness results are stated. The sublinear loss bounds, asymptotic vanishing for JR, and NP/APX-hardness proofs (even for static preferences) are established via direct constructions and reductions against external benchmarks such as approval structures and preference profiles; no step reduces a claimed prediction or theorem back to a fitted parameter or self-citation by construction. Self-citations to prior temporal voting work are present but non-load-bearing, as the central separation and efficiency results rest on the paper's own formalizations and proofs rather than imported uniqueness theorems or ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, ad-hoc axioms, or invented entities; the work adapts standard multiwinner axioms (JR and variants) and utilitarian welfare to the temporal model without introducing new primitives.

pith-pipeline@v0.9.0 · 5494 in / 1217 out tokens · 55063 ms · 2026-05-13T00:45:23.465096+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

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.
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3.3 … P n,ℓ UTIL (JR) ≤ ℓ/(ℓ−n+2√n−1) … vanishes asymptotically when ℓ≫n

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

[1]

Hardness of approximating problems on cubic graphs

[Alimonti and Kann, 1997] Paola Alimonti and Viggo Kann. Hardness of approximating problems on cubic graphs. In Algorithms and Complexity, pages 288–298,

work page 1997
[2]

Better collective decisions via uncertainty reduction

[Alouf-Heffetzet al., 2022 ] Shiri Alouf-Heffetz, Laurent Bulteau, Edith Elkind, Nimrod Talmon, and Nicholas Teh. Better collective decisions via uncertainty reduction. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 24–30,

work page 2022
[3]

Justified representation in approval-based committee voting.Social Choice and Welfare, 48:461–485,

[Azizet al., 2017 ] Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. Justified representation in approval-based committee voting.Social Choice and Welfare, 48:461–485,

work page 2017
[4]

Biega, Krishna P

[Biegaet al., 2018 ] Asia J. Biega, Krishna P. Gummadi, and Gerhard Weikum. Equity of attention: Amortizing indi- vidual fairness in rankings. InProceedings of the 41st In- ternational ACM SIGIR Conference on Research & Devel- opment in Information Retrieval (SIGIR), pages 405–414,

work page 2018
[5]

Ro- bust and verifiable proportionality axioms for multiwinner voting

[Brill and Peters, 2023] Markus Brill and Jannik Peters. Ro- bust and verifiable proportionality axioms for multiwinner voting. InProceedings of the 24th ACM Conference on Economics and Computation (EC), page 301,

work page 2023
[6]

Completing priceable committees: utilitarian and repre- sentation guarantees for proportional multiwinner voting

[Brill and Peters, 2024] Markus Brill and Jannik Peters. Completing priceable committees: utilitarian and repre- sentation guarantees for proportional multiwinner voting. InProceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9528–9536,

work page 2024
[7]

Justified rep- resentation for perpetual voting.IEEE Access, 9:96598– 96612,

[Bulteauet al., 2021 ] Laurent Bulteau, Noam Hazon, Rutvik Page, Ariel Rosenfeld, and Nimrod Talmon. Justified rep- resentation for perpetual voting.IEEE Access, 9:96598– 96612,

work page 2021
[8]

Proportional aggregation of preferences for sequential decision making

[Chandaket al., 2024 ] Nikhil Chandak, Shashwat Goel, and Dominik Peters. Proportional aggregation of preferences for sequential decision making. InProceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9573–9581,

work page 2024
[9]

Proportionality for constrained pub- lic decisions.arXiv preprint arXiv:2409.02609,

[Chingomaet al., 2025 ] Julian Chingoma, Umberto Grandi, and Arianna Novaro. Proportionality for constrained pub- lic decisions.arXiv preprint arXiv:2409.02609,

work page arXiv 2025
[10]

Ap- proximate proportionality in online fair division

[Chooet al., 2026 ] Davin Choo, Winston Fu, Derek Khu, Tzeh Yuan Neoh, Tze-Yang Poon, and Nicholas Teh. Ap- proximate proportionality in online fair division. InPro- ceedings of the 43rd International Conference on Machine Learning (ICML),

work page 2026
[11]

[Elkindet al., 2022 ] Edith Elkind, Sonja Kraiczy, and Nicholas Teh

Extended version available at arXiv:2508.03253. [Elkindet al., 2022 ] Edith Elkind, Sonja Kraiczy, and Nicholas Teh. Fairness in temporal slot assignment. In Proceedings of the 15th International Symposium on Al- gorithmic Game Theory, pages 490–507,

work page arXiv 2022
[12]

Welfare vs

[Fairsteinet al., 2022 ] Roy Fairstein, Dan Vilenchik, Reshef Meir, and Kobi Gal. Welfare vs. representation in par- ticipatory budgeting. InProceedings of the 21st Interna- tional Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 409–417,

work page 2022
[13]

Proportional decisions in perpetual voting

[Lackner and Maly, 2023] Martin Lackner and Jan Maly. Proportional decisions in perpetual voting. InProceed- ings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5722–5729,

work page 2023
[14]

Utilitarian welfare and representation guaran- tees of approval-based multiwinner rules.Artificial Intel- ligence, 288:103366,

[Lackner and Skowron, 2020] Martin Lackner and Piotr Skowron. Utilitarian welfare and representation guaran- tees of approval-based multiwinner rules.Artificial Intel- ligence, 288:103366,

work page 2020
[15]

Perpetual voting: Fairness in long-term decision making

[Lackner, 2020] Martin Lackner. Perpetual voting: Fairness in long-term decision making. InProceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2103–2110,

work page 2020
[16]

Integer program- ming with a fixed number of variables.Mathematics of Operations Research, 8(4):538–548,

[Lenstra Jr, 1983] Hendrik W Lenstra Jr. Integer program- ming with a fixed number of variables.Mathematics of Operations Research, 8(4):538–548,

work page 1983
[17]

Fairness in repeated matching: A max- imin perspective

[Limet al., 2026 ] Eugene Lim, Tzeh Yuan Neoh, and Nicholas Teh. Fairness in repeated matching: A max- imin perspective. InProceedings of the 40th AAAI Con- ference on Artificial Intelligence (AAAI), pages 17111– 17119,

work page 2026
[18]

A generalised theory of proportionality in collective decision making

[Masaˇríket al., 2024 ] Tomáš Masa ˇrík, Grzegorz Pier- czy´nski, and Piotr Skowron. A generalised theory of proportionality in collective decision making. InPro- ceedings of the 25th ACM Conference on Economics and Computation (EC), pages 734–754,

work page 2024
[19]

Online fair division with additional infor- mation

[Neohet al., 2026 ] Tzeh Yuan Neoh, Jannik Peters, and Nicholas Teh. Online fair division with additional infor- mation. InProceedings of the 43rd International Confer- ence on Machine Learning (ICML),

work page 2026
[20]

[Peterset al., 2021 ] Dominik Peters, Grzegorz Pierczy ´nski, and Piotr Skowron

Extended ver- sion available at arXiv:2505.24503. [Peterset al., 2021 ] Dominik Peters, Grzegorz Pierczy ´nski, and Piotr Skowron. Proportional participatory budgeting with additive utilities. InProceedings of the 35th Interna- tional Conference on Neural Information Processing Sys- tems (NeurIPS), pages 12726–12737,

work page arXiv 2021
[21]

Strengthening propor- tionality in temporal voting

[Phillipset al., 2026 ] Bradley Phillips, Edith Elkind, Nicholas Teh, and Tomasz W ˛ as. Strengthening propor- tionality in temporal voting. InProceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS),

work page 2026
[22]

Fairness in rankings and recom- mendations: an overview.The VLDB Journal, 31:431– 458,

[Pitouraet al., 2022 ] Evaggelia Pitoura, Kostas Stefanidis, and Georgia Koutrika. Fairness in rankings and recom- mendations: an overview.The VLDB Journal, 31:431– 458,

work page 2022
[23]

Propor- tional justified representation

[Sánchez-Fernándezet al., 2017 ] Luis Sánchez-Fernández, Edith Elkind, Martin Lackner, Norberto Fernández, Jesús Fisteus, Pablo Basanta Val, and Piotr Skowron. Propor- tional justified representation. InProceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 670–676,

work page 2017
[24]

Fairness of exposure in rankings

[Singh and Joachims, 2018] Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. InProceed- ings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 2219–2228,

work page 2018
[25]

Proportional public decisions

[Skowron and Górecki, 2022] Piotr Skowron and Adrian Górecki. Proportional public decisions. InProceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 5191–5198,

work page 2022
[26]

Multiwinner temporal voting with aversion to change

[Zechet al., 2024 ] Valentin Zech, Niclas Boehmer, Edith Elkind, and Nicholas Teh. Multiwinner temporal voting with aversion to change. InProceedings of the 27th Euro- pean Conference on Artificial Intelligence (ECAI), pages 3236–3243,

work page 2024
[27]

Thus, by Definition 2.1, ifΦ∈ {JR,PJR}we obtain satGe(o)≥1, and ifΦ =EJR we obtain the existence of somei∈G e withsat i(o)≥1. IfΦ =EJR+, note thatG e is(3, ℓ)-cohesive (selectp e in allℓrounds), and for every roundrwe have T i∈Ge si,r ={p e} ̸=∅, so ap- plying Definition 2.2 implies either (i) somei∈G e has sati(o)≥ ⌊3ℓ/n⌋= 1or (ii)o r =p e; in either cas...

work page 1997
[28]

If v∈U, thenoselectsc v and the constraint is satisfied

Moreover, since onlys v,1, sv,2 approveonly cv, any suchSwith|S| ≥4must contain some voter of the forma e,4 for an edgee={v, u}incident tov. If v∈U, thenoselectsc v and the constraint is satisfied. If v /∈U, then becauseUis a vertex cover we haveu∈U, sooselectsc u; sincec u ∈A ae,4, the votera e,4 ∈S is satisfied, which meets the JR/PJR/EJR requirement (w...

work page 1983
[29]

In- deed, (9) follows by applying (7) ats=H c,j and using bc,Hc,j(x) =v πc(j)(x)under the consistent order (8)

Conversely, ifxis EJR-feasible, choose any permutationπthat orders the classes nondecreas- ingly by the realized valuesv C(x)(breaking ties arbitrarily); then(x,(v C(x))C∈C)satisfies (8) and (9), so it is feasible for the corresponding ILP and attains the same welfare. In- deed, (9) follows by applying (7) ats=H c,j and using bc,Hc,j(x) =v πc(j)(x)under t...

work page 1983
[30]

Therefore, the algorithm is FPT with respect toκ+D

κ ·2 κ) after preprocessing; including the computation of the type- pattern families and the demands(d U)U⊆T , the running time isf(κ, D)·poly(n, m, ℓ). Therefore, the algorithm is FPT with respect toκ+D. D.6 Proof of Proposition 5.6 Let the distinct profiles be indexed byj∈[q], and for eachjletL j denote the number of rounds of profilej(soPq j=1 Lj =ℓ). ...

work page 1983