Paper deep dive
The Price of Proportional Representation in Temporal Voting
Nicholas Teh
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 7/8/2026, 1:41:42 PM
Summary
This paper investigates the trade-off between proportional representation and utilitarian social welfare in temporal voting, where collective decisions are made repeatedly over a fixed horizon. It quantifies the 'price of proportionality' for axioms including Justified Representation (JR), Proportional Justified Representation (PJR), Extended Justified Representation (EJR), and EJR+. The study demonstrates that JR's welfare loss diminishes asymptotically as the time horizon grows, while stronger axioms incur persistent sublinear losses. Additionally, it proves that welfare maximization under these axioms is NP-complete and APX-hard, but offers fixed-parameter tractable algorithms under specific structural parameters like static preferences and bounded approval degrees.
Entities (9)
Relation Signals (8)
Welfare Maximization → is → APX-hard
confidence 98% · and APX-hard, even under static preferences and bounded-degree approvals
Welfare Maximization → is → NP-complete
confidence 98% · we prove that welfare maximization under each axiom is NP-complete
Price of Proportional Representation → quantifies → welfare-proportionality tension
confidence 97% · 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.
Proportional Representation Axioms → conflictwith → Utilitarian Social Welfare
confidence 96% · imposing proportional representation in the temporal setting can incur a growing, yet sublinear, welfare loss... formalize the welfare-proportionality tension
Temporal Voting Model → studies → Justified Representation (JR)
confidence 95% · We study proportional representation in the temporal voting model... Recent work adapts classic proportionality axioms... justified representation (JR)
Justified Representation (JR) → exhibits → asymptotically vanishing welfare loss
confidence 94% · for JR, the welfare loss diminishes as the time horizon grows and vanishes asymptotically
Stronger Axioms (PJR/EJR/EJR+) → exhibit → persistent welfare loss
confidence 93% · whereas for stronger axioms this conflict persists even with many rounds.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2605.11157v1
- Canonical: https://arxiv.org/abs/2605.11157v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
142,915 characters extracted from source content.
Expand or collapse full text
The Price of Proportional Representation in Temporal Voting Nicholas Teh University of Oxford nicholas.teh@cs.ox.ac.uk 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. 1 Introduction Many collective decisions are inherently multi-stage: rather than selecting a single outcome once, an institution commits to a sequence of choices over a horizon. In modern ML-driven systems, this occurs whenever a platform allocates scarce exposure repeatedly: for instance, selecting a featured creator each day, a highlighted job posting each week, or a promoted product category each campaign cycle. A large body of work in information retrieval and recommender systems studies exactly this kind of repeated exposure allocation, where fairness is evaluated across many outputs (often called amortized or long-run fairness) and must be balanced against utility or engagement Biega et al. (2018); Singh and Joachims (2018); Pitoura et al. (2022). These settings also need not be online in the algorithmic sense: platforms commonly plan or optimize slates and exposure schedules in batch using historical logs, forecasts, or business constraints. We study such problems through the lens of the temporal voting model, a framework for long-term collective decision-making Bulteau et al. (2021); Chandak et al. (2024); Elkind et al. (2025c); Phillips et al. (2026). An instance consists of a finite horizon of ℓ rounds together with an approval profile for each round.111We study the offline planning problem: the entire ℓ -round instance (all round profiles) is given as input, and the rule outputs the full length-ℓ sequence at once. In each round the rule selects one alternative, and alternatives may be selected multiple times. This repeated nature of selection creates a fundamental tension: selecting, in each round, an alternative that has maximum support will guarantee high utilitarian welfare. However, repeatedly using such a greedy rule can systematically exclude minorities; for instance, even a sizeable segment of the population may see none of its approved alternatives selected over the entire horizon. Accordingly, the natural fairness question is whether we can achieve some kind of representation across time. The concept of proportional representation is particularly relevant here. Recent work adapts classic proportionality axioms from approval-based multiwinner voting—in particular, justified representation (JR), proportional justified representation (PJR), and extended justified representation (EJR)—to the temporal setting Bulteau et al. (2021); Chandak et al. (2024). These axioms ensure that any sufficiently large and cohesive group obtains its “fair share” of representation when representation is evaluated over the whole horizon. More recently, strengthened variants such as EJR+ were proposed to further tighten proportionality guarantees over time Phillips et al. (2026). However, while these axioms provide compelling group-representation guarantees, they may force the outcome to deviate from the welfare-maximizing optimum. Importantly, this tension arises even under static preferences and offline optimization, because proportionality imposes global, group-based constraints that couple the choices across rounds. This raises two basic questions that are central both in theory and practice: (1) How costly is enforcing proportional representation in temporal voting? (2) Can we compute a high-welfare outcome that satisfies JR/PJR/EJR/EJR+? To address the first question, we adopt the “price of fairness” perspective and study the price of proportional representation: the worst-case ratio between the maximum utilitarian welfare achievable without constraints and the maximum utilitarian welfare achievable subject to a proportionality axiom. This viewpoint provides a crisp, quantitative answer to the welfare-fairness tension: it identifies when proportionality is essentially “free” and when it provably imposes a substantial welfare penalty. To address the second question, we study the computational complexity of optimizing welfare subject to these proportionality axioms. While proportionality constraints are conceptually appealing, they implicitly encode global combinatorial structure (i.e., which cohesive groups must be represented and how their representation must be distributed over time) and it is not clear a priori whether this structure admits efficient optimization, even under restrictive preference assumptions. 1.1 Our Contributions We study four proportionality axioms JR,PJR,EJR,EJR+\JR,PJR,EJR,EJR+\ in the temporal voting setting, and analyze their compatibility with utilitarian social welfare. In Section 3, we quantify the welfare-proportionality tension via a price of proportional representation framework. We establish a general lower bound showing that enforcing any of JR/PJR/EJR/EJR+JR/PJR/EJR/EJR+ can incur a growing (yet sublinear) loss of Ω(ℓ) ( ) in the worst case, where ℓ is the number of rounds. We also prove a universal upper bound of n (the number of agents) on the price. For JR, we go further and obtain a tight, horizon-sensitive guarantee: the price decreases with ℓ and becomes asymptotically negligible when ℓ≫n n (approaching 11). In contrast, for the stronger axioms PJR/EJR/EJR+PJR/EJR/EJR+, the price can remain Ω(n) ( n) even when ℓ=Θ(n) = (n), giving us a clear separation between JR and its stronger counterparts. In Section 4, we show that maximizing utilitarian welfare subject to any of JR/PJR/EJR/EJR+JR/PJR/EJR/EJR+ is NP-complete, and that the corresponding optimization problem is APX-hard, even under static preferences and constant approval-degree bounds. This demonstrates that the computational barrier is intrinsic to the group-based proportionality constraints rather than being dependent on time-varying preferences. Finally, in Section 5, we complement the hardness results by identifying practically meaningful regimes where optimal solutions can be computed efficiently. Under static preferences, we obtain fixed-parameter tractability with respect to the number of candidates m. More generally, we develop algorithms that exploit temporal structure, including FPT results parameterized by the number of voter types (and related temporal-compression parameters), showing that repeated preference patterns across rounds enable tractable welfare maximization under temporal proportionality. Overall, our results provide the first systematic study of the efficiency cost and computational compatibility of temporal proportional representation axioms with social welfare. 1.2 Related Work We briefly survey the most relevant strands of the literature and emphasize works that are directly related to our work. Temporal voting. Proportional representation in temporal voting was first studied by Bulteau et al. Bulteau et al. (2021). They adapted two proportional representation axioms (JR and PJR) from multiwinner voting to the temporal setting (with analyses for both static and changing preferences). Chandak et al. Chandak et al. (2024) subsequently extended this analysis to the stronger EJR, and showed that EJR exists in the temporal setting. Elkind et al. Elkind et al. (2025c) built on this and study the complexity of checking whether a given outcome satisfies JR/PJR/EJR. Recently, Phillips et al. Phillips et al. (2026) examined various ways of strengthening these concepts, and showed that EJR+ and FJR (both strengthenings of EJR) are always satisfiable. We refer the reader to the survey by Elkind et al. Elkind et al. (2024c) for an overview of this area. In an adjacent line of work, Elkind et al. Elkind et al. (2024b) study temporal elections with a focus on welfare and incentive-compatibility. They investigate the computational complexity of welfare maximization and its compatibility with strategyproofness. They also adapt an individual proportionality notion (primarily studied in fair division and public decision-making), and study its compatibility and tradeoffs with utilitarian and egalitarian welfare objectives. This distinction is important for our results. The individual proportionality notion studied by Elkind et al. Elkind et al. (2024b) is vacuous in some of our hardness constructions. Subsequently, Elkind et al. Elkind et al. (2025b) consider analogous welfare optimization questions for negatively valued candidates, where proportionality notions are not well-defined. Our work differs in that we focus on group-based proportional representation axioms, which capture collective fairness guarantees that are fundamentally different from individual proportionality (where relevant, we will point out the connection and highlight the differences). Another similar (but fundamentally distinct) body of work studies the perpetual voting model Lackner (2020); Lackner and Maly (2023). This model differs from temporal voting in that decisions explicitly depend on the history of past rounds, giving it a more inherently online flavor. Other temporal voting models examine different kinds of intertemporal structure: for example, Zech et al. Zech et al. (2024) study multi-stage multiwinner elections in which each new committee should remain close to the preceding one. These works are complementary to ours: rather than controlling change between outcomes or designing an online rule, we ask how imposing group-based proportionality constraints over a fixed horizon affects utilitarian welfare and computational tractability. Proportionality in multiwinner voting. The proportionality axioms we study are inspired by the well-developed literature on proportional representation in approval-based multiwinner voting. In that setting, justified representation (JR) and extended justified representation (EJR) were introduced by Aziz et al. Aziz et al. (2017), and proportional justified representation (PJR) was later proposed as an intermediate axiom between JR and EJR by Sanchez-Fernandez et al. Sánchez-Fernández et al. (2017). Subsequently, Brill and Peters Brill and Peters (2023) introduced EJR+, a strengthening of EJR that preserves desirable practical properties such as polynomial-time verifiability and satisfaction by polynomial-time computable rules. Temporal variants of these axioms adapt the same group-protection intuition, but the introduction of rounds fundamentally changes both the structure of the constraints (e.g., how representation is required to accrue over time) and the way proportionality interacts with efficiency. Moreover, unlike in multiwinner voting, the same alternative may be selected repeatedly across rounds, which further alters the behavior of proportionality axioms and the design space of rules. Our work advances this line of research by quantifying the welfare-proportionality trade-off for temporal variants of the JR family, and by showing that the length of the time horizon affects this trade-off in qualitatively different ways depending on the strength of the axiom. Equivalently, even under static preferences, a temporal outcome is a multiset of ℓ candidate occurrences rather than a committee of ℓ distinct or interchangeable winners: multiplicities matter because selecting the same candidate repeatedly consumes rounds and repeatedly satisfies the same voters. Proportionality has also been studied in the context of public decision-making (simultaneous aggregation over multiple issues), both without constraints Skowron and Górecki (2022) and with feasibility constraints Chingoma et al. (2025) through adaptations of proportional representation axioms from multiwinner voting, as well as in even more general models of feasibility constraints Masařík et al. (2024). A related multi-issue perspective is taken by Alouf-Heffetz et al. Alouf-Heffetz et al. (2022), who study how an external intervention that reduces agents’ uncertainty can improve collective decisions under issue-by-issue majority voting. This line of work focuses on uncertainty in public decision-making, highlighting how informational and structural constraints can alter the welfare properties of collective outcomes. Welfare-proportionality tradeoffs. A complementary line of work studies proportionality constraints through a quantitative lens, often phrased as a “price of fairness” or “price of proportionality” measure. In the context of multiwinner voting, Elkind et al. Elkind et al. (2024a) initiate a systematic study of the welfare and coverage losses incurred by imposing JR and EJR constraints. Related quantitative analyses adopt approximation-style guarantees to compare voting rules against welfare- or representation-oriented benchmarks Lackner and Skowron (2020). Similar welfare–representation tradeoffs have also been examined in participatory budgeting Fairstein et al. (2022), and in designing multiwinner rules that simultaneously provide utilitarian and representation guarantees Brill and Peters (2024). Our work extends this quantitative perspective to the temporal voting setting by defining and bounding the utilitarian price of proportionality. 2 Preliminaries For every natural number k∈ℕk , we let [k]=1,2,…,k[k]=\1,2,…,k\. A temporal election is a tuple E=(P,N,ℓ,(i)i∈N)E=(P,N, ,(s_i)_i∈ N), where P is the set of m candidates, N is the set of n voters, ℓ is the number of rounds, and for each i∈Ni∈ N, i=(si,1,si,2,…,si,ℓ)s_i=(s_i,1,s_i,2,…,s_i, ), where si,r⊆Ps_i,r P is the approval set of voter i in round r, which consists of candidates that i approves in round r.222Preferences are said to be static if for every voter i∈Ni∈ N there exists a fixed approval set Ai⊆PA_i P such that si,r=Ais_i,r=A_i for every round r∈[ℓ]r∈[ ]. We denote the set of all temporal elections by ℰE and the set of temporal elections whereby in every round every voter approves at least one candidate by ℰ≥1E_≥ 1 (which we call complete elections). We say that voters from a subset S⊆NS N agree in a round r∈[ℓ]r∈[ ] if there exists a candidate that they all approve in this round, i.e., ⋂i∈Ssi,r≠∅ _i∈ Ss_i,r≠ . An outcome of a temporal election E is a sequence =(o1,o2,…,oℓ)∈Pℓo=(o_1,o_2,…,o_ )∈ P of ℓ candidates such that for every r∈[ℓ]r∈[ ], candidate or∈Po_r∈ P is chosen in round r. A candidate may be selected multiple times, i.e., it may be the case that ot=or′o_t=o_r for some r≠r′r≠ r . For a subset of rounds R⊆[ℓ]R [ ] and an outcome o, we write R=(or)r∈Ro_R=(o_r)_r∈ R to denote the suboutcome with respect to R. The satisfaction of a subset of voters S⊆NS N from a suboutcome Ro_R is satS(R)=|r∈R:or∈⋃i∈Ssi,r|sat_S(o_R)= |\r∈ R:\ o_r∈ _i∈ Ss_i,r\ |, i.e., the number of rounds in R in which the selected candidate is approved by at least one voter from S. If S=iS=\i\ for some i∈Ni∈ N, then we simply write sati(R)sat_i(o_R). 2.1 Proportional Representation Axioms We now provide the definitions of the proportionality axioms we consider, which were originally introduced in prior work on temporal voting Bulteau et al. (2021); Chandak et al. (2024); Elkind et al. (2025c). Definition 2.1 (JR/PJR/EJR). Given a temporal election E=(P,N,ℓ,(i)i∈N)E=(P,N, ,(s_i)_i∈ N) and an outcome o, if, for each t∈[ℓ]t∈[ ] and every nonempty subset of voters S⊆NS N that agrees in a size-t subset of rounds, it holds that • satS()≥min(1,⌊t⋅|S|/n⌋)sat_S(o)≥ (1, t·|S|/n ), then o provides justified representation (JR), • satS()≥⌊t⋅|S|/n⌋sat_S(o)≥ t·|S|/n , then o provides proportional justified representation (PJR), • sati()≥⌊t⋅|S|/n⌋sat_i(o)≥ t·|S|/n for some i∈Si∈ S, then o provides extended justified representation (EJR). While JR, PJR, and EJR impose proportionality guarantees based on the total number of rounds on which a group agrees, they do not ensure that such agreement translates into representation in any particular round. In particular, a group may be sufficiently large and cohesive to warrant proportional representation overall, yet still be unrepresented in a round where all its members agree. To capture this stronger notion of temporal proportionality, Phillips et al. Phillips et al. (2026) proposed extended justified representation + (EJR+),333This notion is based on the analogous strengthening of EJR in the multiwinner voting setting Brill and Peters (2023). which requires that sufficiently cohesive groups either obtain proportional satisfaction overall or receive representation in every round on which they unanimously agree. It is defined as follows. Definition 2.2 (EJR+). Given a temporal election E=(P,N,ℓ,(i)i∈N)E=(P,N, ,(s_i)_i∈ N) and σ∈[n]σ∈[n], τ∈[ℓ]τ∈[ ], we say that a nonempty subset of voters S⊆NS N is (σ,τ)(σ,τ)-cohesive if there exists a set of τ rounds R⊆[ℓ]R [ ] and a suboutcome R=(or)r∈Ro_R=(o_r)_r∈ R such that for each r∈Rr∈ R, at least σ voters in S approve oro_r. We say that an outcome o provides extended justified representation + (EJR+) if for all σ∈[n]σ∈[n], τ∈[ℓ]τ∈[ ], every (σ,τ)(σ,τ)-cohesive nonempty subset of voters S⊆NS N and every round r∈[ℓ]r∈[ ] with ⋂i∈Ssi,r≠∅ _i∈ Ss_i,r≠ , it holds that (i) sati()≥⌊τ⋅σ/n⌋sat_i(o)≥ τ·σ/n for some i∈Si∈ S, or (i) or∈⋂i∈Ssi,ro_r∈ _i∈ Ss_i,r. Phillips et al. Phillips et al. (2026) proposed two strengthenings of EJR that are always satisfiable: EJR+ and full justified representation (FJR). The latter is inspired by an analogous strengthening studied in the participatory budgeting setting—a generalization of multiwinner voting that allows items to have variable costs Peters et al. (2021). In this work, we focus on EJR+ rather than FJR, as EJR+ is better established in the multiwinner voting literature and preserves key practical properties of its multiwinner analogue—most notably polynomial-time verifiability and satisfaction by a polynomial-time computable rule. In contrast, while FJR is always satisfiable, the known constructive approach relies on a procedure whose running time is not polynomial, and Phillips et al. Phillips et al. (2026) observe that it remains open whether FJR outcomes can be computed in polynomial time. 2.2 Price of Proportional Representation In this work, we focus on utilitarian social welfare, which is the canonical efficiency benchmark in approval-based voting and is standard in quantitative welfare-proportionality tradeoff analyses Lackner and Skowron (2020); Elkind et al. (2024a, b). We view utilitarian welfare as the most informative baseline for isolating the efficiency cost of proportional representation: unlike other (e.g., egalitarian or Nash) objectives, which already encode inequality aversion, utilitarian welfare measures aggregate efficiency directly. Moreover, utilitarian welfare is additively separable across rounds, making the unconstrained optimum efficiently computable in our model and enabling transparent worst-case comparisons. Given a temporal election E=(P,N,ℓ,(i)i∈N)E=(P,N, ,(s_i)_i∈ N) and an =(o1,…,oℓ)∈Pℓo=(o_1,…,o_ )∈ P , the utilitarian welfare of o under E is the total number of approving voter-round pairs: UtilE():=∑i∈Nsati()=∑r=1ℓ|i∈N:or∈si,r|. Util_E(o):= _i∈ Nsat_i(o)= _r=1 |\i∈ N:o_r∈ s_i,r\ |. For notational simplicity, we omit the subscript E when it is obvious from context. More generally, one could consider an arbitrary welfare function WE:Pℓ→ℝ≥0W_E:P _≥ 0. Let Φ be a property of the outcome, e.g., Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\. Fix integers n,ℓ≥1n, ≥ 1, and let ℰn,ℓE^n, be the class of temporal elections with n voters and ℓ rounds; define ℰ≥1n,ℓE^n, _≥ 1 analogously for complete elections. For an election E∈ℰn,ℓE ^n, , define the unconstrained optimum by W∗(E):=max∈PℓWE()W^*(E):= _o∈ P W_E(o), and the Φ -constrained optimum by WΦ(E):=maxWE():∈Pℓ and provides ΦW (E):= \W_E(o):o∈ P and o provides \. For a fixed election E with WΦ(E)>0W (E)>0, let ρW,Φ(E):=W∗(E)WΦ(E) _W, (E):= W^*(E)W (E). For a class ⊆ℰn,ℓC ^n, , the price of Φ with respect to W over C is W(Φ;):=supE∈:WΦ(E)>0ρW,Φ(E)P_W( ;C):= _E :W (E)>0 _W, (E). In Section 3, we take =ℰ≥1n,ℓC=E^n, _≥ 1, since the price bounds there are for complete elections. To lighten notation, we let Wn,ℓ(Φ):=W(Φ;ℰ≥1n,ℓ)P_W^n, ( ):=P_W( ;E^n, _≥ 1) when the underlying class is clear. Then, we will study the following decision problem. Φ -UTIL Input: A temporal election E and an integer threshold B. Question: Does there exist an outcome ∈Pℓo∈ P such that o provides Φ and Util()≥B Util(o)≥ B? We also consider the associated optimization problem. Φ -MaxUTIL Input: A temporal election E. Task: Compute an outcome ∈Pℓo∈ P such that o provides Φ and Util() Util(o) is maximized. 3 Price of Proportional Representation We begin by quantifying the welfare cost of enforcing proportional representation in temporal elections. Here, we make two simple assumptions that are needed to ensure that the price measure is well-defined and meaningful. First, we restrict attention to complete elections E∈ℰ≥1E _≥ 1, i.e., si,r≠∅s_i,r≠ for all i∈Ni∈ N and all r∈[ℓ]r∈[ ]. Without this, the ratio can be inflated by trivial “empty approval” rounds in which no candidate is approved, and the measure would be uninformative. Second, we focus on the setting where ℓ≥n ≥ n. To see why, our proportionality axioms “assign representation” in indivisible units of rounds via terms ⌊t⋅|S|/n⌋ t·|S|/n . When ℓ<n <n, even a voter who has a nonempty approval set at every round has ⌊ℓ/n⌋=0 /n =0, and JR/PJR/EJR impose no per-voter guarantee and can be satisfied while ignoring some voters in every round. Moreover, this is unavoidable: in complete elections, one can have disjoint approvals so that each round can satisfy at most one voter, making “everyone is represented at least once” infeasible unless ℓ≥n ≥ n. This is also the minimal non-degenerate setting in which the proportionality axioms impose positive individual entitlements and have some bite; and thus, the resulting price isolates the meaningful welfare-proportionality tension. We begin with a general lower bound. Proposition 3.1. Fix any ℓ≥1 ≥ 1 and Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\. There exists a complete temporal election E∈ℰ≥1ℓ,ℓE , _≥ 1 such that ρUtil,Φ(E)≥12ℓ _ Util, (E)≥ 12 . Consequently, Utilℓ,ℓ(Φ)≥12ℓ=12nP_ Util , ( )≥ 12 = 12 n. Intuitively, the construction creates a “core” block of about ℓ voters who share a consistently popular candidate, alongside many voters whose approvals are essentially private. The welfare-maximizing outcome repeatedly satisfies the popular block, but any Φ -feasible outcome must spend many rounds on low-support candidates to ensure some baseline representation for the private voters, producing a Θ(ℓ) ( ) welfare gap. Next, we provide a universal upper bound, which serves more as a coarse sanity check showing imposing proportionality cannot blow up welfare by more than a factor n. Proposition 3.2. Fix any n,ℓ≥1n, ≥ 1, any Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\, and any complete temporal election E∈ℰ≥1n,ℓE ^n, _≥ 1 with UtilΦ(E)>0 Util (E)>0. Then ρUtil,Φ(E)≤n _ Util, (E)≤ n. Consequently, Utiln,ℓ(Φ)≤nP_ Util^n, ( )≤ n. The proof combines two simple facts: (i) welfare in any round is at most n, and Util∗(E)≤nℓ Util^*(E)≤ n ; (i) for E∈ℰ≥1E _≥ 1, any Φ -feasible outcome can be modified (without affecting feasibility) so that every round selects a candidate approved by at least one voter, guaranteeing welfare at least ℓ . For JR we can substantially strengthen Proposition 3.2; crucially, the bound improves with number of rounds. Theorem 3.3. Fix n,ℓn, with ℓ≥n ≥ n. Then, for every complete temporal election E∈ℰ≥1n,ℓE ^n, _≥ 1, ρUtil,JR(E)≤ℓ−n+2n−1 _ Util,JR(E)≤ -n+2 n-1. Consequently, Utiln,ℓ(JR)≤ℓ−n+2n−1P_ Util^n, (JR)≤ -n+2 n-1. In particular, for every fixed ε>0 >0, if ℓ=(1+ε)n =(1+ )n, then Utiln,ℓ(JR)≤1+ε+o(1)P_ Util^n, (JR)≤ 1+ +o(1), and if ℓ/n→∞ /n→∞, then Utiln,ℓ(JR)→1P_ Util^n, (JR)→ 1. At a high level, the proof is constructive: it identifies n “cheap” rounds and uses them to ensure that every voter is represented at least once, while selecting per-round welfare maximizers in the remaining rounds. An averaging argument then shows that even on the reserved n rounds, one can retain a Θ(1/n) (1/ n) fraction of the local welfare optimum. We complement Theorem 3.3 with a matching lower bound, showing tightness up to lower-order terms. Proposition 3.4. Fix n,ℓn, with ℓ≥n ≥ n. There exists a complete temporal election E∈ℰ≥1n,ℓE ^n, _≥ 1 such that ρUtil,JR(E)≥ℓ−n+2n−(1) _ Util,JR(E)≥ -n+2 n-O(1). Consequently, Utiln,ℓ(JR)≥ℓ−n+2n−(1)P_ Util^n, (JR)≥ -n+2 n-O(1). Remark 3.5. Elkind et al. Elkind et al. (2024b) study temporal elections under an individual proportionality axiom PROP, which requires each voter i to be satisfied in at least ⌊μi/n⌋ _i/n rounds, where μi _i is the number of rounds in which i approves at least one candidate (so μi=ℓ _i= on complete elections). When ⌊ℓ/n⌋=1 /n =1 (in particular, when ℓ=n =n), PROP reduces to the requirement that every voter is satisfied at least once; on complete elections, this condition coincides with JR. In this setting, Elkind et al. (Elkind et al., 2024b, Thm. 5.6) determine the worst-case utilitarian price exactly as n/(2n−1)n/(2 n-1); their lower-bound instance corresponds to the ℓ=n =n special case of Proposition 3.4. Our focus is different: we analyze group-based axioms and explicitly track how the welfare loss varies with the horizon ℓ ; Theorem 3.3 and Proposition 3.4 give a tight ℓ -sensitive bound for JR, showing that its price decreases with ℓ and tends to 11 when ℓ≫n n. Finally, we make explicit the qualitative separation suggested by Theorem 3.3: increasing the time horizon can make JR cheap, but it need not reduce the cost of stronger axioms. Theorem 3.6. Fix an integer a≥2a≥ 2 and set ℓ=an =an. Then PUtiln,an(JR)≤a−1+o(1)P^n,an_ Util(JR)≤ aa-1+o(1) as n→∞n→∞. However, for each Φ∈PJR,EJR,EJR+ ∈\PJR,EJR,EJR+\, PUtiln,an(Φ)=Ω(n)P^n,an_ Util( )= ( n). The results in this section show that enforcing proportional representation in temporal elections can incur a provable sublinear welfare loss. For JR, this loss decreases with ℓ and vanishes as ℓ becomes large relative to n (Theorem 3.3), whereas for stronger axioms (PJR/EJR/EJR+) the cost can remain Ω(n) ( n) even when ℓ is a constant-factor multiple of n (Theorem 3.6). 4 Computational Intractability Results The previous section quantified the welfare loss that can arise from enforcing proportionality in temporal elections. We now turn to the algorithmic question: given a temporal election, can we compute a high welfare outcome that satisfies a chosen proportionality axiom? Formally, we study the decision problem Φ -UTIL and its optimization variant Φ -MaxUTIL (as defined in Section 2) for Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\. Our key findings are: for each Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\, maximizing utilitarian welfare subject to Φ is NP-hard, and even APX-hard, under very strong structural restrictions. In particular, our reductions use static preferences (approval sets do not vary across rounds) and constant approval degree bounds (each candidate is approved by a constant number of voters), so that feasibility verification is straightforward; the hardness comes from the combinatorial property of simultaneously meeting many group-based representation constraints while retaining high welfare. We begin with two simple structural observations that let us treat JR/PJR/EJRJR/PJR/EJR (and, on static instances, also EJR+) in a unified way. We then prove NP-completeness of Φ -Util and strengthen this to APX-hardness for Φ -MaxUtil via a gap-preserving reduction. Our NP-hardness construction then forces every positive proportional entitlement to be exactly 11. Intuitively, whenever a cohesive group is large/frequent enough to trigger a proportionality requirement at all, it is only entitled to one unit of representation over the whole horizon. In this setting, the distinctions between JR, PJR, and EJR disappear: all three axioms reduce to the same proportionality condition. Lemma 4.1. Fix a temporal election E=(P,N,ℓ,(i)i∈N)E=(P,N, ,(s_i)_i∈ N). Assume that for every integer t>0t>0 and every nonempty voter group S⊆NS N that agrees in a size-t subset of rounds, we have ⌊t⋅|S|/n⌋≤1 t·|S|/n ≤ 1. Then for any outcome o, the following are equivalent: o satisfies JR, o satisfies PJR, and o satisfies EJR. Lemma 4.1 lets a single reduction establish hardness for all of JR/PJR/EJRJR/PJR/EJR, provided we ensure the stated condition. Our constructions achieve this in a clean, verifiable way: we enforce a constant bound k on the number of approvers per candidate, which implies that any agreeing group S must be contained in the approver set of some candidate and hence has size at most k. By choosing n sufficiently large relative to ℓ and k, we guarantee ⌊t⋅|S|/n⌋≤⌊ℓ⋅k/n⌋≤1 t·|S|/n ≤ · k/n ≤ 1 for all relevant (S,t)(S,t). Next we handle EJR+. While EJR+ is strictly stronger than EJR in general, under static preferences it collapses back to EJR: if a group ever unanimously agrees, it agrees in every round, so EJR already forces enough aggregate satisfaction to satisfy the EJR+ disjunction via (i). Lemma 4.2. For any temporal election with static preferences, an outcome satisfies EJR+ iff it satisfies EJR. Together, Lemmas 4.1 and 4.2 imply that, on the static, “low demand” instances used in our reductions, all axioms Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\ impose the same feasibility constraints (up to notational differences). We now show that Φ -UTIL is NP-complete even under very strong restrictions. The reduction is designed to isolate the algorithmic difficulty to the group-based representation constraints: preferences are static, and each candidate is approved by only constantly many voters, so the structure of potentially binding groups is simple; nevertheless, selecting a high welfare, feasible outcome encodes an NP-complete covering problem. Theorem 4.3. Fix any Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\. Then, Φ -UTIL is NP-complete, even when voters have static preferences and each candidate is approved by at most 44 voters. The above result rules out polynomial-time exact optimization unless P=NPP=NP. One might still hope for a PTAS for Φ -MaxUtil. We rule this out by proving APX-hardness under similarly strong restrictions. Theorem 4.4. Fix any Φ∈JR, PJR, EJR, EJR+ ∈\JR, PJR, EJR, EJR+\. Then Φ -MaxUTIL is APX-hard, even when voters have static preferences, each voter approves at most 33 candidates and each candidate is approved by at most 88 voters. It is worth contrasting our computational results with those of Elkind et al. Elkind et al. (2024b). They show NP-hardness of deciding whether there exists an individually proportional (PROP) outcome that also maximizes utilitarian welfare. Our focus is different: we study group-based temporal proportionality axioms JR/PJR/EJR/EJR+JR/PJR/EJR/EJR+, which impose fundamentally different constraints (and are in general incomparable with PROP). Moreover, our hardness reductions already go through under static preferences, so the intractability is not due to time-varying approvals. Finally, both reductions operate in settings where ⌊ℓ/n⌋=0 /n =0, so PROP is vacuous, yet JR/PJR/EJR/EJR+JR/PJR/EJR/EJR+ remain nontrivial due to cohesive groups—highlighting that the difficulty is inherent to group representation over time. 5 Parameterized Complexity Results The intractability results in the previous section hold even under static preferences, and rule out polynomial-time algorithms or approximation schemes in the worst case. Nevertheless, temporal elections in practice often exhibit additional structure. In such settings, worst-case hardness need not preclude efficient algorithms. Thus, we study the parameterized complexity of Φ -MaxUTIL (see Section 2). Our goal is to identify natural structural parameters under which the problem becomes tractable, and to make explicit how the algorithmic difficulty depends on these parameters. Throughout, we give exact algorithms (rather than approximation guarantees), thereby complementing the hardness results of Section 4. As a simple baseline, when the number of rounds ℓ is treated as a parameter, Φ -MaxUTIL can be solved by brute-force enumeration of outcomes: we enumerate all sequences ∈Pℓo∈ P , compute Util() Util(o), and retain the best Φ -feasible outcome. Since verifying Φ -feasibility of a given outcome o is in XP with respect to ℓ (Elkind et al., 2025c, Prop. 5.3), enumerating all mℓm outcomes gives us an XP algorithm with respect to ℓ : for some computable function f, the running time is mℓ⋅(n+m)f(ℓ)m ·(n+m)^f( ). Thus, Φ -MAXUTIL is in XP with respect to ℓ . While this approach might be impractical for large ℓ , it provides a useful reference point in settings where ℓ is constant/bounded. We then turn to more meaningful structural parameters. 5.1 Fixed m under Static Preferences Section 4 shows that even under static preferences, Φ -UTIL is NP-hard and Φ -MaxUTIL is APX-hard for all Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\; thus, tractability cannot be recovered merely by assuming static preferences. However, this structural assumption becomes algorithmically useful when combined with small parameters. In particular, if the number of candidates m is fixed, an outcome is characterized (up to permuting rounds) by its candidate multiplicities (i.e., how many times each candidate is selected). Formally, each voter i∈Ni∈ N approves a fixed set Ai⊆PA_i P in every round. Any outcome ∈Pℓo∈ P is therefore fully specified (up to permuting rounds) by its multiplicity vector ∈ℤ≥0Px _≥ 0^P with xp:=|r∈[ℓ]:or=p|and∑p∈Pxp=ℓx_p:=|\r∈[ ]:o_r=p\| _p∈ Px_p= . Under x, voter i’s satisfaction and utilitarian welfare are linear: sati()=∑p∈Aixpsat_i(x)= _p∈ A_ix_p and Util()=∑p∈Pw(p)xp Util(x)= _p∈ Pw(p)x_p, where w(p):=|i∈N:p∈Ai|.w(p):=|\i∈ N:p∈ A_i\|. To compress the instance, we group identical approval sets into approval classes :=Ai:i∈NC:=\A_i:i∈ N\, and write nC:=|i∈N:Ai=C|n_C:=|\i∈ N:A_i=C\| for each class C∈C . All voters in a class share the same satisfaction value vC():=∑p∈Cxpv_C(x):= _p∈ Cx_p. The remaining work is to encode the proportionality axiom as constraints over x (and a bounded number of auxiliary integer variables). When the number of candidates m is fixed, these ILPs have a number of integer variables bounded by a function of m only (e.g., via at most ||≤2m|C|≤ 2^m auxiliary variables), and thus are solvable in time f(m)⋅poly(n,ℓ)f(m)·poly(n, ) for ILPs in fixed dimension using the result of Lenstra Jr Lenstra Jr (1983). Although EJR implies PJR implies JR (and on static instances EJR+ is equivalent to EJR by Lemma 4.2), we state separate optimization theorems because the objective is welfare maximization under constraints: weaker axioms enlarge the feasible set, so an outcome that maximizes welfare subject to EJR may be feasible for PJR and JR but not optimal for them. Moreover, the constraint structure differs qualitatively. This contrasts with the “low demand” setting used in Section 4 (Lemma 4.1), where the three axioms coincide; here demands can exceed 11, so the distinctions matter for optimization. Theorem 5.1. Fix a temporal election E=(P,N,ℓ,(Ai)i∈N)E=(P,N, ,(A_i)_i∈ N) with static preferences, and let m=|P|m=|P|. Then JR-MAXUTIL is solvable in time f(m)⋅poly(n,m,ℓ)f(m)·poly(n,m, ) for some computable function f. In particular, it is FPT with respect to m. Theorem 5.2. Fix a temporal election with static preferences A1,…,An⊆PA_1,…,A_n P and ℓ rounds. Then PJR-MaxUTIL is solvable in time f(m)⋅poly(n,ℓ)f(m)·poly(n, ) for some computable function f. In particular, it is FPT with respect to m. Theorem 5.3. Fix a temporal election with static preferences A1,…,An⊆PA_1,…,A_n P and ℓ rounds. Then EJR-MaxUtil (and thus EJR+-MaxUtil) is solvable in time f(m)⋅poly(n,ℓ)f(m)·poly(n, ) for some computable function f. In particular, it is FPT with respect to m. 5.2 Fixed Voter Types We now move beyond static preferences while retaining a common form of structure in applications: although approvals may vary over time, the electorate often consists of a small number of behavioral types (e.g., user segments) whose members react similarly in every round. We show that this structure gives us fixed-parameter tractability for welfare maximization under temporal proportionality. Formally, let T be a set of voter types and let κ:=|T|κ:=|T|. The voters are partitioned into disjoint sets (Nθ)θ∈T(N_θ)_θ∈ T, where nθ:=|Nθ|n_θ:=|N_θ| and ∑θ∈Tnθ=n _θ∈ Tn_θ=n. For each round r∈[ℓ]r∈[ ], voters of type θ share a common approval set Aθ,r⊆PA_θ,r P; i.e., for every i∈Nθi∈ N_θ we have si,r=Aθ,rs_i,r=A_θ,r. This representation allows us to work at the type level. For an outcome =(o1,…,oℓ)o=(o_1,…,o_ ) define the (common) satisfaction of type θ by satθ():=|r∈[ℓ]:or∈Aθ,r|sat_θ(o):= |\r∈[ ]:o_r∈ A_θ,r\ |. For any voter i∈Nθi∈ N_θ, we have sati()=satθ()sat_i(o)=sat_θ(o). Moreover, utilitarian welfare can be written compactly as Util()=∑r=1ℓ∑θ∈T:or∈Aθ,rnθ Util(o)= _r=1 _θ∈ T:o_r∈ A_θ,rn_θ. It will be convenient to encode the effect of choosing a candidate in round r by the set of approving types. For each round r and candidate p∈Pp∈ P, let Xr(p):=θ∈T:p∈Aθ,r⊆TX_r(p):=\θ∈ T:p∈ A_θ,r\ T, and w(X):=∑θ∈Xnθw(X):= _θ∈ Xn_θ. Then selecting p in round r contributes w(Xr(p))w(X_r(p)) to welfare and increases satθ(⋅)sat_θ(·) by 11 exactly for θ∈Xr(p)θ∈ X_r(p). Importantly, for a fixed round r, the welfare and all proportionality-relevant effects depend only on the type pattern Xr(p)X_r(p), not on the identity of p. Thus in round r we may compress candidates into the family r:=Xr(p):p∈P⊆2TX_r:=\X_r(p):p∈ P\ 2^T, keeping one representative candidate per pattern (so |r|≤2κ|X_r|≤ 2^κ). We show that this structure leads to efficient algorithms even when preferences can vary across rounds. For JR, we obtain a dynamic program whose running time is exponential only in the number of types κ. Theorem 5.4. JR-MaxUTIL is solvable in time f(κ)⋅poly(n,m,ℓ)f(κ)·poly(n,m, ) for some computable function f. In particular, it is FPT with respect to κ. For EJR we need to account for how many times each type is satisfied, since demands scale with group size and cohesion frequency. Let γU:=|r∈[ℓ]:⋂θ∈UAθ,r≠∅| _U:= | \r∈[ ]: _θ∈ UA_θ,r≠ \ | be the number of rounds in which all types in U “agree” (i.e., have a unanimously approved candidate in that round). Then, define for each U⊆TU T the type set U induces an integer demand dU:=⌊γU⋅w(U)/n⌋d_U:= _U· w(U)/n , and D:=maxU⊆T,U≠∅dUD:= _U T,U≠ d_U. Note that D≤ℓD≤ (since dU≤γU≤ℓd_U≤ _U≤ ). Under voter types, EJR can be expressed purely at the type level: for every U with dU>0d_U>0, at least one type θ∈Uθ∈ U must achieve satisfaction at least dUd_U. Then, we get fixed-parameter tractability with respect to κ and this demand parameter D. Theorem 5.5. EJR-MaxUTIL is solvable in time f(κ,D)⋅poly(n,m,ℓ)f(κ,D)·poly(n,m, ) for some computable function f. In particular, it is FPT with respect to κ+Dκ+D. The parameter D captures the “largest proportional claim” any cohesive union of types can generate; when no type set can demand many satisfied rounds (e.g., because unanimous agreement is rare), the state space remains small. Since EJR implies PJR, the DP in Theorem 5.5 also outputs a PJR-feasible outcome. However, because PJR is strictly weaker than EJR in general, this outcome need not be welfare-optimal among all PJR-feasible outcomes. The above DPs scale linearly with ℓ . In many temporal settings, however, the approval pattern repeats: many rounds share the same “profile” across types (e.g., weekly cycles). We can exploit this further by grouping rounds into a small number of distinct profiles. Two rounds r,r′∈[ℓ]r,r ∈[ ] have the same profile if Aθ,r=Aθ,r′A_θ,r=A_θ,r for every θ∈Tθ∈ T. Then, we get the following result. Proposition 5.6. On instances with κ voter types and q round profiles, PJR-MaxUTIL is solvable in time f(κ,q)⋅poly(n,ℓ,m)f(κ,q)·poly(n, ,m) for a computable function f. In particular, it is FPT with respect to (κ,q)(κ,q). The same profile-based variable scheme can also give us ILP formulations (and hence FPT algorithms parameterized by (κ,q)(κ,q)) for JR-MaxUTIL and EJR-MaxUTIL by adapting the constraints to the corresponding feasibility conditions. Section 4 showed that static preferences alone do not restore tractability. In contrast, bounding the diversity of temporal behavior—via a small number of voter types and, optionally, a small number of round profiles—does lead to exact FPT algorithms for welfare maximization under temporal proportionality. This pinpoints temporal structure, rather than time-invariance per se, as a main driver of algorithmic tractability in temporal voting. Together, these results show that although Φ -MaxUTIL is intractable in full generality, it becomes efficiently solvable in a range of structured settings that naturally arise in temporal voting settings. This delineates a clear boundary between worst-case hardness and practically relevant tractability. 6 Conclusion In this work, we investigated proportional representation in temporal voting through a quantitative price of proportional representation framework, measuring the worst-case loss in utilitarian welfare incurred by enforcing JR/PJR/EJR/EJR+. Our bounds make the welfare-proportionality tension in this setting precise: enforcing proportionality can cause a growing, yet sublinear, welfare loss, and the magnitude of this loss depends sharply on both the axiom and the time horizon. In particular, the cost of JR vanishes on long horizons: its price approaches 11 as the number of rounds grows large relative to the number of voters. By contrast, stronger notions such as PJR/EJR/EJR+ can still incur an Ω(n) ( n) loss even when ℓ is only a constant-factor multiple of n. On the algorithmic side, we showed that maximizing utilitarian welfare subject to these proportionality constraints is NP-complete, and APX-hard, even under structural restrictions such as static preferences and bounded approval degrees. At the same time, we identified structured regimes in which optimal outcomes can be computed efficiently via fixed-parameter methods, including parameterizations by the number of candidates, the number of voter types, and the number of distinct round profiles. Our work naturally gives rise to several promising avenues for further work. One direction is to refine the quantitative bounds, particularly for stronger proportionality notions such as PJR/EJR/EJR+. Such refinements would help clarify whether the observed separations are inherent or driven by worst-case constructions. A second direction is to extend the analysis beyond utilitarian welfare. Studying the price of proportionality with respect to alternative objectives (such as egalitarian or Nash welfare) may uncover qualitatively different trade-offs and lead to new insights into how proportionality interacts with social welfare under richer normative criteria. References Alimonti and Kann [1997] Paola Alimonti and Viggo Kann. Hardness of approximating problems on cubic graphs. In Algorithms and Complexity, pages 288–298, 1997. Alouf-Heffetz et 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, 2022. Aziz et 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, 2017. Biega et al. [2018] Asia J. Biega, Krishna P. Gummadi, and Gerhard Weikum. Equity of attention: Amortizing individual fairness in rankings. In Proceedings of the 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR), pages 405–414, 2018. Brill and Peters [2023] Markus Brill and Jannik Peters. Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), page 301, 2023. Brill and Peters [2024] Markus Brill and Jannik Peters. Completing priceable committees: utilitarian and representation guarantees for proportional multiwinner voting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9528–9536, 2024. Bulteau et al. [2021] Laurent Bulteau, Noam Hazon, Rutvik Page, Ariel Rosenfeld, and Nimrod Talmon. Justified representation for perpetual voting. IEEE Access, 9:96598–96612, 2021. Chandak et al. [2024] Nikhil Chandak, Shashwat Goel, and Dominik Peters. Proportional aggregation of preferences for sequential decision making. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9573–9581, 2024. Chingoma et al. [2025] Julian Chingoma, Umberto Grandi, and Arianna Novaro. Proportionality for constrained public decisions. arXiv preprint arXiv:2409.02609, 2025. Choo et al. [2026] Davin Choo, Winston Fu, Derek Khu, Tzeh Yuan Neoh, Tze-Yang Poon, and Nicholas Teh. Approximate proportionality in online fair division. In Proceedings of the 43rd International Conference on Machine Learning (ICML), 2026. Extended version available at arXiv:2508.03253. Elkind et al. [2022] Edith Elkind, Sonja Kraiczy, and Nicholas Teh. Fairness in temporal slot assignment. In Proceedings of the 15th International Symposium on Algorithmic Game Theory, pages 490–507, 2022. Elkind et al. [2024a] Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, and Warut Suksompong. The price of justified representation. ACM Transactions on Economics and Computation, 12(3):11:1–11:27, 2024. Elkind et al. [2024b] Edith Elkind, Tzeh Yuan Neoh, and Nicholas Teh. Temporal elections: Welfare, strategyproofness, and proportionality. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), pages 3292–3299, 2024. Elkind et al. [2024c] Edith Elkind, Svetlana Obraztsova, and Nicholas Teh. Temporal fairness in multiwinner voting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 22633–22640, 2024. Elkind et al. [2025a] Edith Elkind, Alexander Lam, Mohamad Latifian, Tzeh Yuan Neoh, and Nicholas Teh. Temporal fair division of indivisible items. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 676–685, 2025. Elkind et al. [2025b] Edith Elkind, Tzeh Yuan Neoh, and Nicholas Teh. Not in my backyard! Temporal voting over public chores. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), pages 3814–3820, 2025. Elkind et al. [2025c] Edith Elkind, Svetlana Obraztsova, Jannik Peters, and Nicholas Teh. Verifying proportionality in temporal voting. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13805–13813, 2025. Fairstein et al. [2022] Roy Fairstein, Dan Vilenchik, Reshef Meir, and Kobi Gal. Welfare vs. representation in participatory budgeting. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 409–417, 2022. Lackner and Maly [2023] Martin Lackner and Jan Maly. Proportional decisions in perpetual voting. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5722–5729, 2023. Lackner and Skowron [2020] Martin Lackner and Piotr Skowron. Utilitarian welfare and representation guarantees of approval-based multiwinner rules. Artificial Intelligence, 288:103366, 2020. Lackner [2020] Martin Lackner. Perpetual voting: Fairness in long-term decision making. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2103–2110, 2020. Lenstra Jr [1983] Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538–548, 1983. Lim et al. [2026] Eugene Lim, Tzeh Yuan Neoh, and Nicholas Teh. Fairness in repeated matching: A maximin perspective. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 17111–17119, 2026. Masařík et al. [2024] Tomáš Masařík, Grzegorz Pierczyński, and Piotr Skowron. A generalised theory of proportionality in collective decision making. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), pages 734–754, 2024. Neoh et al. [2026] Tzeh Yuan Neoh, Jannik Peters, and Nicholas Teh. Online fair division with additional information. In Proceedings of the 43rd International Conference on Machine Learning (ICML), 2026. Extended version available at arXiv:2505.24503. Peters et al. [2021] Dominik Peters, Grzegorz Pierczyński, and Piotr Skowron. Proportional participatory budgeting with additive utilities. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NeurIPS), pages 12726–12737, 2021. Phillips et al. [2026] Bradley Phillips, Edith Elkind, Nicholas Teh, and Tomasz Wąs. Strengthening proportionality in temporal voting. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2026. Pitoura et al. [2022] Evaggelia Pitoura, Kostas Stefanidis, and Georgia Koutrika. Fairness in rankings and recommendations: an overview. The VLDB Journal, 31:431–458, 2022. Sánchez-Fernández et al. [2017] Luis Sánchez-Fernández, Edith Elkind, Martin Lackner, Norberto Fernández, Jesús Fisteus, Pablo Basanta Val, and Piotr Skowron. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 670–676, 2017. Singh and Joachims [2018] Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 2219–2228, 2018. Skowron and Górecki [2022] Piotr Skowron and Adrian Górecki. Proportional public decisions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 5191–5198, 2022. Zech et al. [2024] Valentin Zech, Niclas Boehmer, Edith Elkind, and Nicholas Teh. Multiwinner temporal voting with aversion to change. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), pages 3236–3243, 2024. Appendix Appendix A Further Related Work Temporal allocation and fair division. Our model is also related to temporal allocation and fair division problems, where a sequence of decisions must be evaluated not only round by round but also in terms of the cumulative guarantees it provides over time. In temporal slot assignment, Elkind et al. Elkind et al. [2022] study assignment of slots and consider proportionality-type objectives across the whole horizon; this is close in spirit to our setting, since selecting an alternative in each round can be viewed as allocating a slot. However, in our model the chosen outcome is a public decision observed by all voters, and proportionality is imposed through group-based voting axioms rather than through assignment-specific fairness criteria. A related line of work in temporal fair division studies how fairness evolves when indivisible items arrive sequentially: Elkind et al. Elkind et al. [2025a] analyze cumulative approximate envy-freeness, while Neoh et al. Neoh et al. [2026] and Choo et al. Choo et al. [2026] investigate online fair division with predictions, and approximate proportionality guarantees. These works share with ours the idea that temporal structure can make fairness and efficiency interact in nontrivial ways, but they typically concern private allocations and online arrival models. Finally, Lim et al. Lim et al. [2026] study repeated matching under a maximin objective, providing another example where repeated decisions create intertemporal fairness-efficiency tradeoffs. These papers motivate the broader temporal decision-making perspective, while our contribution is to quantify and compute the welfare cost of enforcing JR/PJR/EJR/EJR+ in the temporal voting model. Appendix B Omitted Proofs in Section 3 B.1 Proof of Proposition 3.1 Fix ℓ≥1 ≥ 1 and let n:=ℓn:= and k:=⌈ℓ⌉k:= . Partition the voters into two disjoint sets C,DC,D with |C|=k|C|=k and |D|=n−k=ℓ−k|D|=n-k= -k. Define the candidate set P:=z⊎xi,r:i∈D,r∈[ℓ]⊎yc,r:c∈C,r∈[ℓ],P:=\z\\ \ \x_i,r:i∈ D,\ r∈[ ]\\ \ \y_c,r:c∈ C,\ r∈[ ]\, where all symbols denote distinct candidates. Define the approval sets as follows for each round r∈[ℓ]r∈[ ]: • sc,r:=z,yc,rs_c,r:=\z,\,y_c,r\ for each c∈Cc∈ C, and • si,r:=xi,rs_i,r:=\x_i,r\ for each i∈Di∈ D. Note that si,r≠∅s_i,r≠ for all i∈Ni∈ N and all r∈[ℓ]r∈[ ], so E∈ℰ≥1E _≥ 1. Fix any round r∈[ℓ]r∈[ ]. Candidate z is approved by exactly the k voters in C. Every other candidate is approved by at most one voter in round r (in particular, xi,rx_i,r is approved only by voter i, yc,ry_c,r only by voter c, and candidates with mismatched indices may be approved by no one in that round). Thus, the maximum welfare contribution in round r is k, attained by selecting z. Therefore the unconstrained optimal outcome is ∗=(z,…,z)o^*=(z,…,z) and Util∗(E)=kℓ. Util^*(E)=k . Let o be any outcome that provides Φ . Note that a Φ -feasible outcome exists: select xi,rx_i,r for each i∈Di∈ D in a distinct round (thus satisfying every i∈Di∈ D once), and select z in the remaining k rounds (thus satisfying all c∈Cc∈ C many times). Since the only cohesive groups are subsets of C (and singletons in D), this outcome satisfies JR/PJR/EJR, and also EJR+. Fix a voter i∈Ni∈ N and consider the singleton group S:=iS:=\i\. Since E∈ℰ≥1E _≥ 1, S agrees in every round (since ⋂j∈Ssj,r=si,r≠∅ _j∈ Ss_j,r=s_i,r≠ for all r), and thus agrees in a size-ℓ subset of rounds. As n=ℓn= , we have ⌊ℓ⋅|S|n⌋=⌊ℓ⌋=1. ·|S|n = =1. If Φ=JR =JR, then sati()≥min1,⌊ℓ/n⌋=1sat_i(o)≥ \1, /n \=1. If Φ=PJR =PJR, then sati()≥⌊ℓ/n⌋=1sat_i(o)≥ /n =1. If Φ=EJR =EJR, then sati()≥1sat_i(o)≥ 1. Finally, suppose Φ=EJR+ =EJR+. Set σ:=1σ:=1 and τ:=ℓτ:= . For each round r∈[ℓ]r∈[ ], pick an arbitrary candidate pr∈si,rp_r∈ s_i,r (possible since si,r≠∅s_i,r≠ ), let R:=[ℓ]R:=[ ], and let o~R:=(pr)r∈R o_R:=(p_r)_r∈ R. Then S is (σ,τ)(σ,τ)-cohesive. Since ⋂j∈Ssj,r=si,r≠∅ _j∈ Ss_j,r=s_i,r≠ for all r, Definition 2.2 applied to S and any round r implies either (i) sati()≥⌊τσ/n⌋=⌊ℓ/ℓ⌋=1sat_i(o)≥ τσ/n = / =1, or (i) or∈⋂j∈Ssj,r=si,ro_r∈ _j∈ Ss_j,r=s_i,r, so voter i is satisfied in round r, and thus sati()≥1sat_i(o)≥ 1. Thus in all cases sati()≥1sat_i(o)≥ 1. Consequently, for every Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\ and every Φ -feasible outcome o, sati()≥1for all i∈N.sat_i(o)≥ 1 all i∈ N. (1) Now, let rz:=|r∈[ℓ]:or=z|r_z:= |\r∈[ ]:o_r=z\ | be the number of rounds in which z is selected. In each round with or=zo_r=z, exactly the k voters in C approve oro_r, so that round contributes k to welfare. In every other round, the selected candidate is not z and is approved by at most one voter in that round, so that round contributes at most 11. Thus, Util()≤rz⋅k+(ℓ−rz)⋅1=ℓ+rz(k−1). Util(o)≤ r_z· k+( -r_z)· 1= +r_z(k-1). Now focus on the voters in D. In round r, voter i∈Di∈ D approves exactly the candidate xi,rx_i,r. Moreover, for any fixed r the candidates xi,r:i∈D\x_i,r:i∈ D\ are distinct and each is approved by a different voter, so at most one voter in D can be satisfied in a single round. By (1), every voter in D must be satisfied at least once, so we need at least |D|=ℓ−k|D|= -k rounds in which some voter in D is satisfied. In any round where a voter in D is satisfied, we cannot have chosen z (since no voter in D approves z). Therefore, ℓ−rz≥ℓ−k⟹rz≤k. -r_z≥ -k r_z≤ k. This gives us Util()≤ℓ+k(k−1)=ℓ−k+k2. Util(o)≤ +k(k-1)= -k+k^2. Since o was an arbitrary Φ -feasible outcome, it follows that UtilΦ(E)≤ℓ−k+k2. Util (E)≤ -k+k^2. Therefore, Util∗(E)UtilΦ(E)≥kℓ−k+k2. Util^*(E) Util (E)≥ k -k+k^2. Let s:=ℓs:= , so ℓ=s2 =s^2 and k=⌈s⌉k= s . We claim that ℓ−k+k2≤2ks -k+k^2≤ 2ks. Indeed, 2ks−(ℓ−k+k2)=2ks−(s2−k+k2)=k−(s−k)2.2ks-( -k+k^2)=2ks-(s^2-k+k^2)=k-(s-k)^2. Since k=⌈s⌉k= s , we have 0≤k−s<10≤ k-s<1, thus, (s−k)2<1≤k(s-k)^2<1≤ k, so the right-hand side is nonnegative. Thus ℓ−k+k2≤2ks -k+k^2≤ 2ks, and consequently Util∗(E)UtilΦ(E)≥ks22ks=s2=12ℓ. Util^*(E) Util (E)≥ ks^22ks= s2= 12 . By definition, Util(Φ)P_ Util( ) is the supremum of Util∗(E)/UtilΦ(E) Util^*(E)/ Util (E) over elections with UtilΦ(E)>0 Util_ (E)>0, so the existence of this election implies Util(Φ)≥12ℓP_ Util( )≥ 12 . B.2 Proof of Proposition 3.2 Fix Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\ and let E=(P,N,ℓ,(si)i∈N)∈ℰ≥1E=(P,N, ,(s_i)_i∈ N) _≥ 1. Assume UtilΦ(E)>0 Util (E)>0, i.e., there exists at least one Φ -feasible outcome. For any outcome =(o1,…,oℓ)∈Pℓo=(o_1,…,o_ )∈ P , Util()=∑t=1ℓ|i∈N:ot∈si,t|≤∑t=1ℓn=nℓ, Util(o)= _t=1 |\\,i∈ N:o_t∈ s_i,t\,\ |≤ _t=1 n=n , because in each round at most n voters can approve the selected candidate. Thus, Util∗(E)≤nℓ Util^*(E)≤ n . Now, let =(o1,…,oℓ)o=(o_1,…,o_ ) be any outcome satisfying Φ (it exists by assumption). We transform o by eliminating empty rounds, i.e., rounds in which the selected candidate is approved by no voter. Formally, for each round t∈[ℓ]t∈[ ] with i∈N:ot∈si,t=∅,\i∈ N:o_t∈ s_i,t\= , pick an arbitrary voter it∈Ni_t∈ N and then pick any candidate pt∈sit,tp_t∈ s_i_t,t. Such a candidate exists because E∈ℰ≥1E _≥ 1, i.e., si,t≠∅s_i,t≠ for all i∈Ni∈ N and all t∈[ℓ]t∈[ ]. Replace oto_t by ptp_t and keep all other rounds unchanged. Let o denote the outcome obtained after performing this replacement for every empty round. By construction, for every round t∈[ℓ]t∈[ ] there exists at least one voter (namely iti_t if the round was modified, or some voter who already approved oto_t otherwise) who approves o^t o_t. Therefore each round contributes at least 11 to utilitarian welfare, and thus Util(^)≥ℓ. Util( o)≥ . It suffices to argue that a single replacement (in one empty round) cannot violate Φ ; then applying this argument sequentially gives us that o is still Φ -feasible. So fix an empty round t and let ′o be the outcome obtained from o by replacing oto_t with ptp_t. Since the round was empty, ot∉si,to_t∉ s_i,t for every voter i∈Ni∈ N. Thus, no voter loses satisfaction in round t when we replace oto_t by ptp_t, and no other round changes. Concretely, for every i∈Ni∈ N, sati(′)=sati()+[pt∈si,t]≥sati().sat_i(o )=sat_i(o)+1[p_t∈ s_i,t] _i(o). Similarly, for every voter group S⊆NS N, round t contributed 0 to satS()sat_S(o) (because oto_t was in no approval set at round t), so satS(′)=satS()+[∃i∈S:pt∈si,t]≥satS().sat_S(o )=sat_S(o)+1 [∃ i∈ S:\ p_t∈ s_i,t ] _S(o). We first prove the result for JR/PJR/EJR. All constraints in Definition 2.1 have the form satS(⋅)≥(threshold)sat_S(·)≥(threshold) (JR, PJR) or ∃i∈S∃ i∈ S with sati(⋅)≥(threshold)sat_i(·)≥(threshold) (EJR), where the thresholds depend only on the instance (and on S,tS,t), not on the outcome. Since every satSsat_S and every satisat_i weakly increases when passing from o to ′o , every JR, PJR, and EJR constraint that held for o also holds for ′o . Next, we prove the result for EJR+. Fix any σ∈[n]σ∈[n], τ∈[ℓ]τ∈[ ], any (σ,τ)(σ,τ)-cohesive nonempty S⊆NS N, and any round r∈[ℓ]r∈[ ] with ⋂i∈Ssi,r≠∅ _i∈ Ss_i,r≠ . We show the EJR+ requirement remains satisfied after the replacement. If r≠tr≠ t, then the chosen candidate in round r does not change (only round t was modified), so (i) is unchanged; and (i) can only become easier to satisfy since all satisat_i weakly increase. If r=tr=t, then the original chosen candidate oto_t was approved by no voter, and thus, ot∉⋂i∈Ssi,to_t∉ _i∈ Ss_i,t; therefore (i) was false for o at this constraint, so the constraint had to be satisfied via (i), i.e., sati()≥⌊τσ/n⌋sat_i(o)≥ τσ/n for some i∈Si∈ S. Because sati(′)≥sati()sat_i(o ) _i(o) for all i, (i) remains true for ′o as well. Thus EJR+ is preserved by the replacement. Consequently, o satisfies Φ , and therefore UtilΦ(E)≥Util(^)≥ℓ. Util (E)≥ Util( o)≥ . Combining Util∗(E)≤nℓ Util^*(E)≤ n with UtilΦ(E)≥ℓ Util (E)≥ , we get that Util∗(E)UtilΦ(E)≤nℓ=n, Util^*(E) Util (E)≤ n =n, as claimed. B.3 Proof of Theorem 3.3 Fix a complete temporal election E=(P,N,ℓ,(si)i∈N)∈ℰ≥1n,ℓE=(P,N, ,(s_i)_i∈ N) ^n, _≥ 1 with ℓ≥n ≥ n. For each round t∈[ℓ]t∈[ ], define the maximum approval count at:=maxp∈P|i∈N:p∈si,t|.a_t\;:=\; _p∈ P |\\,i∈ N:p∈ s_i,t\,\ |. Since utilitarian welfare is additive across rounds, an unconstrained utilitarian optimum can be obtained by choosing, in each round t, a candidate that attains ata_t approvals; thus Util∗(E)=∑t=1ℓat. Util^*(E)= _t=1 a_t. Let B⊆[ℓ]B [ ] be a set of n rounds minimizing ∑t∈Bat _t∈ Ba_t (equivalently, B consists of the n smallest values among att∈[ℓ]\a_t\_t∈[ ]). Write B¯:=[ℓ]∖B B:=[ ] B and define OPTB:=∑t∈Bat,OPTB¯:=∑t∈B¯at=Util∗(E)−OPTB.OPT_B:= _t∈ Ba_t,OPT_ B:= _t∈ Ba_t= Util^*(E)-OPT_B. For any set of rounds R⊆[ℓ]R [ ] and any suboutcome R=(ot)t∈Ro_R=(o_t)_t∈ R, define the welfare contributed by R as UtilR(oR):=∑t∈R|i∈N:ot∈si,t|. Util_R(o_R)\;:=\; _t∈ R |\\,i∈ N:o_t∈ s_i,t\,\ |. Claim. There exists a suboutcome Bo_B on the rounds in B such that every voter is satisfied at least once within B (i.e., sati(B)≥1sat_i(o_B)≥ 1 for all i∈Ni∈ N) and UtilB(B)≥2n−1n⋅OPTB. Util_B(o_B)≥ 2 n-1n·OPT_B. Proof of Claim. Let q:=maxt∈Batq:= _t∈ Ba_t and fix t∗∈Bt^*∈ B with at∗=qa_t^*=q. Let T⊆BT B be any set of size q (since q≤nq≤ n since at≤na_t≤ n for all rounds, so such a set exists) consisting of t∗t^* and the other q−1q-1 rounds in B with largest ata_t-values. For each t∈Tt∈ T, choose a candidate pt∈Pp_t∈ P attaining ata_t approvals in round t and set ot:=pto_t:=p_t. Let Q:=∑t∈Tat,Q:= _t∈ Ta_t, which is exactly the welfare contributed by the rounds in T. In particular, in round t∗t^* the chosen candidate is approved by q voters, so at least q voters are already satisfied after fixing the choices on T. Thus, at most n−qn-q voters remain unsatisfied. Since |B∖T|=n−q|B T|=n-q and si,t≠∅s_i,t≠ for all i,ti,t, we can choose the remaining entries oto_t for t∈B∖Tt∈ B T so that: • each previously unsatisfied voter becomes satisfied at least once within B (assign each such voter injectively to a distinct round in B∖TB T and pick a candidate she approves); and • every round in B∖TB T selects a candidate approved by at least one voter (if some rounds remain unassigned, pick any voter and a candidate she approves in that round). Thus every voter is satisfied at least once within B, and every round in B∖TB T contributes at least 11 to welfare. Therefore UtilB(B)≥Q+(n−q). Util_B(o_B)≥ Q+(n-q). If B∖T=∅B T= , then q=|B|=nq=|B|=n and the construction achieves UtilB(B)=OPTB Util_B(o_B)=OPT_B, so assume B∖T≠∅B T≠ and define r:=maxt∈B∖Tat≥ 1.r:= _t∈ B Ta_t\;≥\;1. Then OPTB=∑t∈Tat+∑t∈B∖Tat≤Q+(n−q)r.OPT_B= _t∈ Ta_t+ _t∈ B Ta_t≤ Q+(n-q)\,r. Moreover, since T contains the q rounds of B with largest ata_t-values, we have at≥ra_t≥ r for all t∈Tt∈ T, so Q≥rqQ≥ rq. Combining these bounds gives us UtilB(B)OPTB≥Q+n−qQ+(n−q)r Util_B(o_B)OPT_B≥ Q+n-qQ+(n-q)r ≥rq+n−qrq+(n−q)r ≥ rq+n-qrq+(n-q)r =rq+n−qnr, = rq+n-qnr, where the second inequality follows from the fact that r≥1r≥ 1, so the function f(Q)=Q+n−qQ+(n−q)rf(Q)= Q+n-qQ+(n-q)r is nondecreasing in Q, and Q≥rqQ≥ rq, so f(Q)≥f(rq)f(Q)≥ f(rq). Since q≥rq≥ r, we have rq+n−q=n+q(r−1)≥n+r(r−1)rq+n-q=n+q(r-1)≥ n+r(r-1), and thus UtilB(B)OPTB≥n+r(r−1)nr=r−1n+1r=(rn+1r)−1n. Util_B(o_B)OPT_B≥ n+r(r-1)nr= r-1n+ 1r= ( rn+ 1r )- 1n. By the AM-GM inequality, rn+1r≥2/n rn+ 1r≥ 2/ n, so UtilB(B)OPTB≥2n−1n=2n−1n, Util_B(o_B)OPT_B≥ 2 n- 1n= 2 n-1n, proving the claim. □ Now construct a (full time horizon) outcome o as follows: • for each t∈B¯t∈ B, choose a candidate attaining ata_t approvals in round t; • for each t∈Bt∈ B, use the choice from oBo_B. Then Util() Util(o) =OPTB¯+UtilB(B) =OPT_ B+ Util_B(o_B) ≥Util∗(E)−OPTB+2n−1n⋅OPTB ≥ Util^*(E)-OPT_B+ 2 n-1n·OPT_B =Util∗(E)−(1−2n−1n)OPTB. = Util^*(E)- (1- 2 n-1n )OPT_B. Since B consists of the n smallest values among att∈[ℓ]\a_t\_t∈[ ], its average is at most the overall average. Thus, OPTB≤nℓ∑t=1ℓat=nℓ⋅Util∗(E).OPT_B≤ n _t=1 a_t= n · Util^*(E). Indeed, sorting a1,…,aℓa_1,…,a_ in nondecreasing order, OPTBOPT_B is the sum of the first n, whose average cannot exceed the overall average. Substituting gives Util() Util(o) ≥[1−(1−2n−1n)nℓ]Util∗(E) ≥ [1- (1- 2 n-1n ) n ] Util^*(E) =ℓ−n+2n−1ℓ⋅Util∗(E). = -n+2 n-1 · Util^*(E). Finally, by construction, every voter is satisfied at least once in o (indeed, already within B), i.e., sati()≥1sat_i(o)≥ 1 for all i∈Ni∈ N. Therefore, for any nonempty voter set S⊆NS N we have satS()≥sati()≥1sat_S(o) _i(o)≥ 1 for any i∈Si∈ S. Since the right-hand side of the JR constraint is min1,⌊t|S|/n⌋∈0,1 \1, t|S|/n \∈\0,1\, this implies that all JR constraints are satisfied; thus, o provides JR. Consequently UtilJR(E)≥Util() Util_JR(E)≥ Util(o), and thus Util∗(E)UtilJR(E)≤ℓ−n+2n−1. Util^*(E) Util_JR(E)≤ -n+2 n-1. Taking the supremum over complete instances concludes the proof. B.4 Proof of Proposition 3.4 Fix n,ℓn, with ℓ≥n ≥ n, and let k:=⌈n⌉k:= n . We construct a complete temporal election E=(P,N,ℓ,(si)i∈N)E=(P,N, ,(s_i)_i∈ N) as follows. Partition the voters into two disjoint sets N=C∪˙RN=C ∪R with |C|=k|C|=k (the core voters) and |R|=n−k|R|=n-k (the private voters). Let P:=z∪pi:i∈RP:=\z\∪\p_i:i∈ R\, where all candidates are distinct. For every round t∈[ℓ]t∈[ ], define approval sets by sc,t:=zfor all c∈C, and si,t:=pifor all i∈R.s_c,t:=\z\ all c∈ C, and s_i,t:=\p_i\ all i∈ R. Then E∈ℰ≥1E _≥ 1 (every voter approves at least one candidate in every round), and preferences are static. Now, in every round t, candidate z is approved by exactly the k voters in C, while each pip_i is approved by exactly one voter. Thus, the maximum possible per-round welfare is k, attained by choosing z. Therefore the unconstrained utilitarian optimum is achieved by ∗:=(z,z,…,z)o^*:=(z,z,…,z) and Util∗(E)=kℓ. Util^*(E)=k . Let =(o1,…,oℓ)∈Pℓo=(o_1,…,o_ )∈ P be any outcome satisfying JR. We first show that every voter must be satisfied at least once. Fix any voter i∈Ni∈ N and consider the singleton group S:=iS:=\i\. Since E is complete, S agrees in every round, so it agrees in a size-ℓ subset of rounds. Applying Definition 2.1 with t=ℓt= gives the JR requirement satS()≥min1,⌊ℓ⋅|S|/n⌋=min1,⌊ℓ/n⌋=1,sat_S(o)≥ \1, ·|S|/n \= \1, /n \=1, where the last equality uses ℓ≥n ≥ n. Since S is a singleton, satS()=sati()sat_S(o)=sat_i(o), thus, sati()≥1sat_i(o)≥ 1 for every i∈Ni∈ N. In particular, every private voter i∈Ri∈ R must be satisfied in some round. But i approves only pip_i in every round, so there exists a round t(i)∈[ℓ]t(i)∈[ ] with ot(i)=pio_t(i)=p_i. If i≠ji≠ j are two private voters, then pi∩pj=∅\p_i\∩\p_j\= , so they cannot share the same witness round: t(i)≠t(j)t(i)≠ t(j). Thus o selects a private candidate in at least |R|=n−k|R|=n-k distinct rounds. Equivalently, if r:=|t∈[ℓ]:ot=z|r:= |\t∈[ ]:o_t=z\ | is the number of rounds selecting z, then ℓ−r≥n−k -r≥ n-k, i.e., r≤ℓ−n+kr≤ -n+k. A round with ot=zo_t=z contributes exactly k to welfare, while a round with ot≠zo_t≠ z contributes exactly 11. Thus, Util()=rk+(ℓ−r)⋅1 Util(o)=rk+( -r)· 1 =ℓ+r(k−1) = +r(k-1) ≤ℓ+(ℓ−n+k)(k−1) ≤ +( -n+k)(k-1) =kℓ−(k−1)(n−k). =k -(k-1)(n-k). This upper bound is achieved by selecting each private candidate pip_i once (for i∈Ri∈ R) and selecting z in all remaining ℓ−(n−k) -(n-k) rounds; this outcome satisfies every voter at least once and therefore satisfies JR. Consequently, UtilJR(E)=kℓ−(k−1)(n−k). Util_JR(E)=k -(k-1)(n-k). For this instance, Util∗(E)UtilJR(E)=kℓkℓ−(k−1)(n−k)=ℓ−n+nk+k−1. Util^*(E) Util_JR(E)= k k -(k-1)(n-k)= -n+ nk+k-1. Now set s:=ns:= n and write k=s+δk=s+δ for some δ∈[0,1)δ∈[0,1) (since k=⌈s⌉k= s ). Then nk+k−1 nk+k-1 =s2s+δ+s+δ−1 = s^2s+δ+s+δ-1 =2s−1+δ2s+δ=2n−1+δ2k≤2n−12, =2s-1+ δ^2s+δ=2 n-1+ δ^2k≤ 2 n- 12, where the last inequality uses δ2<1δ^2<1 and k≥2k≥ 2 for n≥2n≥ 2 (and the case n=1n=1 can be checked directly). Therefore Util∗(E)UtilJR(E)≥ℓ−n+2n−12=ℓ−n+2n−(1). Util^*(E) Util_JR(E)\ ≥\ -n+2 n- 12\ =\ -n+2 n-O(1). Since Util(JR)P_ Util(JR) is defined as a supremum over instances, this establishes the claimed lower bound. B.5 Proof of Theorem 3.6 Fix an integer a≥2a≥ 2. Note that Theorem 3.3 shows that for every election with n voters and ℓ≥n ≥ n rounds, Util∗(E)UtilJR(E)≤ℓ−n+2n−1. Util^*(E) Util_JR(E)≤ -n+2 n-1. Substituting ℓ=an =an gives Util(JR) _ Util(JR) ≤anan−n+2n−1 ≤ anan-n+2 n-1 =a(a−1)+2n−1n = a(a-1)+ 2 n- 1n =a−1+o(1) as n→∞. = aa-1+o(1) as n→∞. For each n, let k:=⌈n⌉k:= n and set ℓ:=an :=an. Construct a temporal election E=(P,N,ℓ,(si)i∈N)E=(P,N, ,(s_i)_i∈ N) where agents have static preferences, as follows. Partition the voters as N=C∪˙RN=C ∪R with |C|=k|C|=k (core voters) and |R|=n−k|R|=n-k (private voters). Let P:=z∪pi:i∈R,P:=\z\∪\p_i:i∈ R\, where all candidates are distinct. For every round r∈[ℓ]r∈[ ], define approval sets by sc,r:=z for all c∈C and si,r:=pi for all i∈R.s_c,r:=\z\\ for all c∈ C and s_i,r:=\p_i\\ for all i∈ R. Then, E∈ℰ≥1E _≥ 1 (every si,r≠∅s_i,r≠ ) and in every round z is approved by exactly k voters, while every pip_i is approved by exactly one voter. In each round, selecting z gives us welfare k, while selecting any pip_i gives us welfare 11. Thus, the unconstrained optimum is to pick z in every round, giving Util∗(E)=kℓ=akn. Util^*(E)=k =akn. Now fix Φ∈PJR,EJR,EJR+ ∈\PJR,EJR,EJR+\ and let =(o1,…,oℓ)o=(o_1,…,o_ ) be any Φ -feasible outcome. We first prove that every voter must be satisfied at least a times. Fix any voter i∈Ni∈ N and consider the singleton group S:=iS:=\i\. Since E∈ℰ≥1E _≥ 1, S agrees in every round, thus, in a size-ℓ subset of rounds. Moreover, ⌊ℓ/n⌋=⌊an/n⌋=a /n = an/n =a. • If Φ∈PJR,EJR ∈\PJR,EJR\, apply Definition 2.1 with t=ℓt= to obtain satS()=sati()≥⌊ℓ/n⌋=asat_S(o)=sat_i(o)≥ /n =a. • If Φ=EJR+ =EJR+, take σ:=1σ:=1 and τ:=ℓτ:= . Since si,r≠∅s_i,r≠ for all r, the singleton S is (1,ℓ)(1, )-cohesive (witnessed by choosing in each round an arbitrary candidate in si,rs_i,r). Applying Definition 2.2 to this S gives, for every round r, that either (i) sati()≥⌊τσ/n⌋=⌊ℓ/n⌋=asat_i(o)≥ τσ/n = /n =a or (i) or∈si,ro_r∈ s_i,r. Note that (i) depends only on the full outcome (not on r), so if it is false then (i) must hold for every r. If (i) holds we are done; otherwise (i) holds for all r, which implies sati()=ℓ≥asat_i(o)= ≥ a. Thus in all cases sati()≥asat_i(o)≥ a. Next, we show that at least a(n−k)a(n-k) rounds must select private candidates. Each private voter i∈Ri∈ R approves only pip_i, so sati()sat_i(o) equals the number of rounds with or=pio_r=p_i. Then, sati()≥asat_i(o)≥ a, so pip_i must be selected at least a times. Since each round can select only one candidate, the total number of rounds selecting private candidates is at least a|R|=a(n−k)a|R|=a(n-k). Let rz:=|r∈[ℓ]:or=z|r_z:= |\r∈[ ]:o_r=z\ | denote the number of rounds in which z is selected. Then rz≤ℓ−a(n−k)=an−a(n−k)=ak.r_z≤ -a(n-k)=an-a(n-k)=ak. Now, every round with or=zo_r=z contributes exactly k to welfare, while every other round contributes exactly 11. Therefore, Util()=rzk+(ℓ−rz) Util(o)=r_zk+( -r_z) =ℓ+rz(k−1) = +r_z(k-1) ≤ℓ+ak(k−1) ≤ +ak(k-1) =an+ak2−ak =an+ak^2-ak =a(n−k+k2). =a(n-k+k^2). This bound is achievable by selecting each pip_i (for i∈Ri∈ R) exactly a times and selecting z in the remaining akak rounds; this outcome satisfies sati()≥asat_i(o)≥ a for all i∈Ni∈ N, and (as noted above) the only nontrivial cohesive groups are subsets of C and singleton private voters, all of whose demands are met. More concretely, under static preferences, a voter set S agrees (i.e., has nonempty intersection) iff either S⊆CS C (intersection z\z\) or S=iS=\i\ for some i∈Ri∈ R (intersection pi\p_i\); any set containing both a core and a private voter (or two distinct private voters) has empty intersection and imposes no JR/PJR/EJR constraint. If S⊆CS C with |S|=s|S|=s, then ⌊ℓs/n⌋=⌊(an)s/n⌋=as s/n = (an)s/n =as, and since z is chosen akak times, we have satS()=ak≥assat_S(o)=ak≥ as (PJR) and each c∈Cc∈ C has satc()=ak≥assat_c(o)=ak≥ as (EJR). If S=i⊆RS=\i\ R, then sati()=asat_i(o)=a, meeting the singleton demand a. For EJR+, the only sets S that create constraints are again those with nonempty intersection (i.e., S⊆CS C or S=i⊆R)S=\i\ R); in both cases every voter in S has satisfaction at least a and in fact core voters have satisfaction akak, which is at least ⌊τσ/n⌋ τσ/n for all admissible τ≤ℓandσ≤|S|τ≤ andσ≤|S|, so (i) holds. Consequently, UtilΦ(E)=a(n−k+k2). Util (E)=a(n-k+k^2). We obtain Util∗(E)UtilΦ(E)=akna(n−k+k2)=kn−k+k2. Util^*(E) Util (E)= akna(n-k+k^2)= knn-k+k^2. With k=⌈n⌉k= n we have k≥nk≥ n and k≤n+1k≤ n+1, thus, n−k+k2≤n+k2≤n+(n+1)2=2n+2n+1≤5n-k+k^2≤ n+k^2≤ n+( n+1)^2=2n+2 n+1≤ 5n for all n≥1n≥ 1. Therefore Util∗(E)UtilΦ(E)≥n⋅n5n=15n, Util^*(E) Util (E)≥ n· n5n= 15 n, so in particular Util(Φ)=Ω(n)P_ Util( )= ( n) for each Φ∈PJR,EJR,EJR+ ∈\PJR,EJR,EJR+\ in the case where ℓ=an =an. Appendix C Omitted Proofs in Section 4 C.1 Proof of Lemma 4.1 Fix any integer t>0t>0 and any nonempty voter subset S⊆NS N that agrees in a size-t subset of rounds. Set d:=⌊t⋅|S|n⌋d:= t·|S|n . By the assumption of the lemma, d∈0,1d∈\0,1\. If d=0d=0, then JR/PJR require satS()≥0sat_S(o)≥ 0, and EJR requires ∃i∈S∃ i∈ S with sati()≥0sat_i(o)≥ 0, which holds since S≠∅S≠ . Assume d=1d=1. Then the JR and PJR requirements for (S,t)(S,t) both reduce to satS()≥1sat_S(o)≥ 1. Moreover, satS()≥1 _S(o)≥ 1 ⇔∃r∈[ℓ]∃i∈S:or∈si,r ∃ r∈[ ]\ ∃ i∈ S:\ o_r∈ s_i,r ⇔∃i∈S:sati()≥1, ∃ i∈ S:\ sat_i(o)≥ 1, so the EJR requirement for (S,t)(S,t) is equivalent to the same condition. Thus, for every such pair (S,t)(S,t), JR, PJR, and EJR impose identical constraints on o, and thus, the three axioms are equivalent. C.2 Proof of Lemma 4.2 We first show that every EJR+ outcome is EJR (this direction does not rely on static preferences). Let o satisfy EJR+ and fix any integer t>0t>0 and any nonempty voter subset S⊆NS N that agrees in a size-t subset of rounds. Let R⊆[ℓ]R [ ] with |R|=t|R|=t witness this agreement, i.e., ⋂i∈Ssi,r≠∅ _i∈ Ss_i,r≠ for all r∈Rr∈ R. For each r∈Rr∈ R choose any pr∈⋂i∈Ssi,rp_r∈ _i∈ Ss_i,r and define o~R:=(pr)r∈R o_R:=(p_r)_r∈ R. Then S is (|S|,t)(|S|,t)-cohesive. Applying EJR+ to the parameters σ:=|S|σ:=|S|, τ:=tτ:=t, the set S, and any round r∈Rr∈ R gives us either: (i) there exists i∈Si∈ S with sati()≥⌊t|S|n⌋sat_i(o)≥ t|S|n , which is exactly the EJR requirement for (S,t)(S,t); or (i) or∈⋂i∈Ssi,ro_r∈ _i∈ Ss_i,r. If (i) holds we are done. Otherwise (i) is false, so by EJR+ we must have (i) for every r∈Rr∈ R. Thus, every voter i∈Si∈ S approves the chosen candidate in each round of R, and therefore sati()≥tsat_i(o)≥ t for all i∈Si∈ S. Since |S|≤n|S|≤ n, we have that ⌊t|S|n⌋≤t t|S|n ≤ t, and the EJR requirement again holds. Thus o satisfies EJR. Now assume preferences are static and that o satisfies EJR. Let σ∈[n]σ∈[n], τ∈[ℓ]τ∈[ ], let S be any (σ,τ)(σ,τ)-cohesive subset, and let r∈[ℓ]r∈[ ] be any round with ⋂i∈Ssi,r≠∅ _i∈ Ss_i,r≠ . Under static preferences, ⋂i∈Ssi,r≠∅ _i∈ Ss_i,r≠ implies ⋂i∈Ssi,r′≠∅ _i∈ Ss_i,r ≠ for every r′∈[ℓ]r ∈[ ], so S agrees in a size-ℓ subset of rounds. Applying EJR to (S,ℓ)(S, ) gives us some i∈Si∈ S with sati()≥⌊ℓ|S|n⌋.sat_i(o)≥ |S|n . Since S is (σ,τ)(σ,τ)-cohesive we necessarily have |S|≥σ|S|≥σ, and we also have ℓ≥τ ≥τ; thus, ⌊ℓ|S|n⌋≥⌊τσn⌋. |S|n ≥ τσn . Consequently the same voter i satisfies sati()≥⌊τσn⌋sat_i(o)≥ τσn , so the EJR+ condition holds via (i). As σ,τ,S,σ,τ,S, and r were arbitrary, o satisfies EJR+. C.3 Proof of Theorem 4.3 Fix Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\. We prove NP-hardness via a reduction from Exact Cover by 3-Sets (X3C), which is known to be NP-complete. An instance of X3C consists of a universe U=1,…,uU=\1,…,u\ with u=3qu=3q and a family =S1,…,SmS=\S_1,…,S_m\ of 3-element subsets of U; it is a yes-instance if there exist q sets whose union is exactly U, and a no-instance otherwise. Without loss of generality, assume every element of U appears in at least one set (otherwise the instance is trivially a no-instance and we can map it to any fixed no-instance of Φ -UTIL). We may also assume q≥1q≥ 1; constant-size instances can be handled separately. Given (U,)(U,S), we build a temporal election E=(P,N,ℓ,(si)i∈N)E=(P,N, ,(s_i)_i∈ N) with static preferences as follows. • Voters: for every element e∈Ue∈ U, create three voters xe,ye1,ye2x_e,y_e^1,y_e^2. Additionally, create four dummy voters d1,d2,d3,d4d_1,d_2,d_3,d_4. Thus n:=3u+4=9q+4n:=3u+4=9q+4. • Rounds: set ℓ:=3q+2 :=3q+2. • Candidates: for every set Sj∈S_j , create a candidate cjc_j; for every element e∈Ue∈ U, create a candidate pep_e; and create one special candidate z. • Static preferences: for every e∈Ue∈ U, define Aye1=Aye2=peA_y_e^1=A_y_e^2=\p_e\ and Axe=pe∪cj:e∈SjA_x_e=\p_e\∪\c_j:e∈ S_j\. For each dummy voter drd_r, let Adr=zA_d_r=\z\. Set si,t=Ais_i,t=A_i for all voters i and all rounds t (hence preferences are static). By construction, each set-candidate cjc_j is approved by exactly the three voters xe:e∈Sj\x_e:e∈ S_j\, each element-candidate pep_e is approved by exactly xe,ye1,ye2\x_e,y_e^1,y_e^2\, and z is approved by exactly the four dummy voters. Thus, each candidate is approved by at most 44 voters. Finally, set the welfare threshold B:=4ℓ−q.B:=4 -q. For any outcome =(o1,…,oℓ)o=(o_1,…,o_ ), define w():=|t∈[ℓ]:ot≠z|.w(o):= |\t∈[ ]:o_t≠ z\ |. Every round with ot=zo_t=z contributes 44 to the round welfare, while every round with ot≠zo_t≠ z contributes 33. Therefore Util()=4(ℓ−w())+3w()=4ℓ−w(), Util(o)=4( -w(o))+3w(o)=4 -w(o), and thus Util()≥B⇔w()≤q. Util(o)≥ B w(o)≤ q. Let S⊆NS N be any voter subset and let t∈[ℓ]t∈[ ]. Because preferences are static, if S agrees in a size-t subset of rounds, then ⋂i∈SAi≠∅ _i∈ SA_i≠ , so S is contained in the approvers of some single candidate and hence |S|≤4|S|≤ 4. Consequently, ⌊t⋅|S|n⌋≤⌊ℓ⋅4n⌋=⌊4(3q+2)9q+4⌋= 1, t·|S|n \;≤\; · 4n \;=\; 4(3q+2)9q+4 \;=\;1, where the last equality uses q≥1q≥ 1, so 4(3q+2)<2(9q+4)4(3q+2)<2(9q+4) and 4(3q+2)≥9q+44(3q+2)≥ 9q+4. Thus, in this instance, every threshold of the form ⌊t|S|/n⌋ t|S|/n is in 0,1\0,1\. For EJR+, note that constraints are only for rounds r where ⋂i∈Ssi,r≠∅ _i∈ Ss_i,r≠ . In our instance, any such S must be contained in the approvers of a single candidate, and thus |S|≤4|S|≤ 4, giving us σ≤4σ≤ 4. Thus, we get that ⌊τ⋅σn⌋≤⌊4ℓn⌋=1. τ·σn ≤ 4 n =1. We first prove yes-instance ⟹ feasible high welfare outcome. Assume the X3C instance is a yes-instance, and fix q sets Sj1,…,SjqS_j_1,…,S_j_q whose union is exactly U. Define an outcome o by selecting cjkc_j_k in round k for k=1,…,qk=1,…,q, and selecting z in the remaining ℓ−q -q rounds. Then w()=qw(o)=q, so Util()=4ℓ−q=B Util(o)=4 -q=B. We verify that o satisfies Φ . First note that every dummy voter drd_r has satdr()≥1sat_d_r(o)≥ 1 because o selects z in ℓ−q=2q+2≥1 -q=2q+2≥ 1 rounds. Next, for each element e∈Ue∈ U, since Sj1,…,Sjq\S_j_1,…,S_j_q\ is an exact cover, there is a unique k such that e∈Sjke∈ S_j_k, and then xex_e approves cjkc_j_k; hence satxe()≥1sat_x_e(o)≥ 1 for all e∈Ue∈ U. Now consider any constraint relevant to Φ . • If Φ∈JR,PJR,EJR ∈\JR,PJR,EJR\, fix any t>0t>0 and any S⊆NS N that agrees in a size-t subset of rounds. If ⌊t⋅|S|/n⌋=0 t·|S|/n =0 the constraint is trivial. Otherwise ⌊t⋅|S|/n⌋=1 t·|S|/n =1, and since t≤ℓ=3q+2t≤ =3q+2 and n=9q+4>2ℓn=9q+4>2 , if |S|≤2|S|≤ 2, then t⋅|S|≤2ℓ<nt·|S|≤ 2 <n; thus we must have that |S|≥3|S|≥ 3. Then, (as argued above) S is a subset of the approvers of a single candidate, and thus it is contained in one of the following approver sets: d1,d2,d3,d4\d_1,d_2,d_3,d_4\, xe,ye1,ye2\x_e,y_e^1,y_e^2\ for some e, or xe1,xe2,xe3\x_e_1,x_e_2,x_e_3\ for some 3-set e1,e2,e3\e_1,e_2,e_3\. In all cases, S contains at least one voter with satisfaction at least 11 (a dummy voter, or some xex_e), so JR, PJR, and EJR are satisfied for this (S,t)(S,t). • If Φ=EJR+ =EJR+, fix any σ∈[n]σ∈[n], τ∈[ℓ]τ∈[ ], any (σ,τ)(σ,τ)-cohesive set S, and any round r with ⋂i∈Ssi,r≠∅ _i∈ Ss_i,r≠ . If ⌊τσ/n⌋=0 τσ/n =0, condition (i) holds trivially. Otherwise ⌊τσ/n⌋=1 τσ/n =1, which implies σ≥3σ≥ 3 and thus |S|≥3|S|≥ 3. The nonempty intersection implies again that S is contained in the approvers of a single candidate, so by the same case analysis as above, S contains a voter with satisfaction at least 11. Hence sati()≥⌊τσ/n⌋sat_i(o)≥ τσ/n for some i∈Si∈ S, i.e., EJR+ condition (i) holds. Therefore the constructed Φ -UTIL instance is a yes-instance. Next we prove no-instance ⟹ no feasible high welfare outcome. Assume the X3C instance is a no-instance. Suppose for contradiction that there exists an outcome o satisfying Φ with Util()≥B Util(o)≥ B. Then w()≤qw(o)≤ q. Fix any element e∈Ue∈ U and consider the element group Ge:=xe,ye1,ye2.G_e:=\x_e,y_e^1,y_e^2\. Since all three voters approve pep_e, we have ⋂i∈GeAi=pe≠∅ _i∈ G_eA_i=\p_e\≠ , so GeG_e agrees in a size-ℓ subset of rounds. Moreover, ⌊ℓ⋅|Ge|n⌋=⌊3ℓn⌋=⌊3(3q+2)9q+4⌋=⌊9q+69q+4⌋=1. ·|G_e|n = 3 n = 3(3q+2)9q+4 = 9q+69q+4 =1. Thus, by Definition 2.1, if Φ∈JR,PJR ∈\JR,PJR\ we obtain satGe()≥1sat_G_e(o)≥ 1, and if Φ=EJR =EJR we obtain the existence of some i∈Gei∈ G_e with sati()≥1sat_i(o)≥ 1. If Φ=EJR+ =EJR+, note that GeG_e is (3,ℓ)(3, )-cohesive (select pep_e in all ℓ rounds), and for every round r we have ⋂i∈Gesi,r=pe≠∅ _i∈ G_es_i,r=\p_e\≠ , so applying Definition 2.2 implies either (i) some i∈Gei∈ G_e has sati()≥⌊3ℓ/n⌋=1sat_i(o)≥ 3 /n =1 or (i) or=peo_r=p_e; in either case, at least one voter in GeG_e is satisfied in at least one round. Therefore, for every e∈Ue∈ U there exists some round t such that oto_t is approved by at least one voter in GeG_e. But the only candidates approved by any voter in GeG_e are pep_e (approved by all three) and the set-candidates cjc_j with e∈Sje∈ S_j (approved by xex_e). Hence, for each e∈Ue∈ U, the outcome must select either pep_e in some round or some cjc_j with e∈Sje∈ S_j in some round. Let wset:=|t∈[ℓ]:ot=cj for some j|w_set:= |\t∈[ ]:o_t=c_j for some j\ | and welm:=|t∈[ℓ]:ot=pe for some e|w_elm:= |\t∈[ ]:o_t=p_e for some e\ |. Then wset+welm=w()≤qw_set+w_elm=w(o)≤ q. A set-round (selecting some cjc_j) can certify the above condition for at most the three elements in SjS_j, whereas an element-round (selecting some pep_e) can certify it for exactly one element. Thus the number of distinct covered elements is at most 3wset+welm3w_set+w_elm, and therefore |U|=3q≤ 3wset+welm≤3(wset+welm)≤ 3q.|U|=3q\;≤\;3w_set+w_elm≤ 3(w_set+w_elm)\;≤\;3q. All inequalities must be tight. In particular, wset+welm=qw_set+w_elm=q and welm=0w_elm=0, so o uses exactly q set-rounds and no element-rounds. Tightness also forces these q set-rounds to cover 3q3q distinct elements, hence their underlying 3-sets are pairwise disjoint and have union U, resulting in an exact cover of size q. This contradicts that the X3C instance is a no-instance. Therefore, the constructed Φ -UTIL instance is a no-instance, and Φ -UTIL is NP-hard. Finally, we show membership in NP. Given a certificate outcome ∈Pℓo∈ P , we can compute Util() Util(o) and all sati()sat_i(o) in (nℓ)O(n ) time. To verify Φ under static preferences and the promise that each candidate has at most 44 approvers, it suffices to enumerate all voter groups S⊆NS N with ⋂i∈SAi≠∅ _i∈ SA_i≠ : for any such S pick any p∈⋂i∈SAip∈ _i∈ SA_i; then S⊆i∈N:p∈AiS \i∈ N:p∈ A_i\, so |S|≤4|S|≤ 4 and thus there are at most 242^4 such groups per candidate. For JR/PJR/EJRJR/PJR/EJR, under static preferences, any group either agrees in all rounds or in none, so it suffices to check only t=ℓt= because t↦⌊t⋅|S|/n⌋t t·|S|/n is nondecreasing and the left-hand side does not depend on t. For Φ=EJR+ =EJR+, membership in NP follows from Lemma 4.2, and we can verify EJR in polynomial time. Thus, Φ -UTIL is in NP. Therefore, Φ -UTIL is NP-complete, even when voters have static preferences and each candidate is approved by at most 44 voters. C.4 Proof of Theorem 4.4 We give a PTAS-reduction from Min-Vertex-Cover on cubic graphs, which is known to be APX-complete Alimonti and Kann [1997]. Fix Φ∈JR,PJR,EJR,EJR+ ∈\JR,PJR,EJR,EJR+\. If Φ=EJR+ =EJR+, then by Lemma 4.2, it suffices to prove the claim for EJR. Hence, throughout the proof we assume Φ∈JR,PJR,EJR ∈\JR,PJR,EJR\. Let G=(V,E)G=(V,E) be a cubic graph with |V|=m|V|=m and |E|=3m/2|E|=3m/2. We construct a temporal election EG=(P,N,ℓ,(Ai)i∈N)E_G=(P,N, ,(A_i)_i∈ N) with static preferences as follows. • Candidates. P:=z∪cv:v∈V∪pe:e∈E.P:=\z\\ ∪\ \c_v:v∈ V\\ ∪\ \p_e:e∈ E\. • Voters and approvals. Define three types of voters. – Baseline voters: voters b1,…,b8b_1,…,b_8 with Abj=zA_b_j=\z\. – Vertex supporters: for each v∈Vv∈ V, voters sv,1,sv,2s_v,1,s_v,2 with Asv,k=cvA_s_v,k=\c_v\ for k∈1,2k∈\1,2\. – Edge gadget: for each edge e=u,v∈Ee=\u,v\∈ E, voters ae,1,ae,2,ae,3,ae,4a_e,1,a_e,2,a_e,3,a_e,4 with Aae,1=Aae,2=Aae,3=peA_a_e,1=A_a_e,2=A_a_e,3=\p_e\ and Aae,4=pe,cu,cvA_a_e,4=\p_e,c_u,c_v\. Thus every voter approves at most 33 candidates. Then, the number of voters is n:=8+2|V|+4|E|=8+2m+4⋅3m2=8m+8=8(m+1).n:=8+2|V|+4|E|=8+2m+4· 3m2=8m+8=8(m+1). Set the number of rounds ℓ:=n4=2(m+1)=2m+2. := n4=2(m+1)=2m+2. For each candidate x∈Px∈ P, define its approval weight w(x):=|i∈N:x∈Ai|.w(x):= |\i∈ N:x∈ A_i\ |. By construction, w(z)=8w(z)=8, w(pe)=4w(p_e)=4 for all e∈Ee∈ E, and w(cv)=2+degG(v)=5w(c_v)=2+ _G(v)=5 for all v∈Vv∈ V, since G is cubic, where degG(⋅) _G(·) is a function that returns the degree of the vertex in G. Under static preferences, for any outcome =(o1,…,oℓ)∈Pℓo=(o_1,…,o_ )∈ P , we have Util()=∑r=1ℓw(or). Util(o)= _r=1 w(o_r). (2) Now, fix an edge e=u,v∈Ee=\u,v\∈ E and define the voter set Se:=ae,1,ae,2,ae,3,ae,4.S_e:=\a_e,1,a_e,2,a_e,3,a_e,4\. All voters in SeS_e approve pep_e, thus (under static preferences) SeS_e agrees in all ℓ rounds, and ⌊ℓ⋅|Se|n⌋=⌊(n/4)⋅4n⌋=1. ·|S_e|n = (n/4)· 4n =1. Therefore, for every Φ∈JR,PJR,EJR ∈\JR,PJR,EJR\, providing Φ (i.e., Φ -feasible) implies that SeS_e is represented at least once, i.e., ∃t∈[ℓ]such thatot∈⋃i∈SeAi=pe,cu,cv.∃\,t∈[ ]\ such that\ o_t∈ _i∈ S_eA_i=\p_e,c_u,c_v\. (3) Next, we show that we may restrict our attention to a simple class of outcomes. Claim 1. There exists an optimal Φ -feasible outcome that never selects any pep_e. Proof. Let o be any outcome that provides Φ (i.e., Φ -feasible), and suppose ot=peo_t=p_e for some e=u,ve=\u,v\. Construct ′o by replacing oto_t with cuc_u (either endpoint works). Condition (3) for edge e remains satisfied because cu∈pe,cu,cvc_u∈\p_e,c_u,c_v\. No other representation constraint can be violated by this replacement: the only voters who approve pep_e are exactly the members of SeS_e, and after the replacement the voter ae,4∈Sea_e,4∈ S_e is still satisfied in round t (since cu∈Aae,4c_u∈ A_a_e,4). Finally, by (2) the welfare strictly increases because w(cu)=5>w(pe)=4w(c_u)=5>w(p_e)=4. Moreover, any cohesive group whose common approved candidate is pep_e is contained in SeS_e; and since ℓ=n/4 =n/4, every proper subset S⊊SeS S_e has demand ⌊ℓ|S|/n⌋=⌊|S|/4⌋=0 |S|/n = |S|/4 =0, so the only potentially binding constraint involving pep_e is for SeS_e itself. Repeating this replacement exhaustively gives us an optimal Φ -feasible outcome with no pep_e. ∎ Claim 2. There exists an optimal Φ -feasible outcome in which each cvc_v appears in at most one round. Proof. Take an optimal Φ -feasible outcome with no pep_e (Claim 1). If some cvc_v appears in at least two rounds, keep one occurrence and replace each additional occurrence by z. This strictly increases welfare since w(z)=8>w(cv)=5w(z)=8>w(c_v)=5. We argue that Φ -feasibility is preserved. First, for every edge e incident to v, condition (3) only requires existence of a witnessing round, and the remaining single occurrence of cvc_v still witnesses (3) for all edges incident to v. Second, any cohesive group S with cv∈⋂i∈SAic_v∈ _i∈ SA_i must satisfy S⊆i∈N:cv∈AiS \i∈ N:c_v∈ A_i\, which has size w(cv)=5w(c_v)=5. Since ℓ=n/4 =n/4, we have ⌊ℓ⋅|S|n⌋≤⌊ℓ⋅5n⌋=⌊54⌋=1. ·|S|n ≤ · 5n = 54 =1. Thus any Φ -requirement involving such an S can be satisfied already with a single round in which some voter in S approves the chosen candidate; keeping one occurrence of cvc_v suffices, and replacing further occurrences by z cannot destroy feasibility. ∎ By Claims 1–2, there exists an optimal Φ -feasible outcome of the following canonical form: choose a set U⊆VU V, select each cvc_v for v∈Uv∈ U in exactly one round, and select z in the remaining ℓ−|U| -|U| rounds. Now, we prove that there exists a vertex cover of G if and only if there exists a feasible canonical outcome in our constructed instance. For the ‘if’ direction, let o be canonical with corresponding U⊆VU V. Since o never selects any pep_e, condition (3) implies that for each edge e=u,ve=\u,v\ at least one of cu,cvc_u,c_v is selected, i.e., at least one of u,vu,v lies in U. Thus U is a vertex cover of G. For the ‘only if’ direction, let U be a vertex cover of G, and consider the canonical outcome o that selects each cvc_v for v∈Uv∈ U exactly once and selects z in the remaining rounds. We verify that o is Φ -feasible. Consider any Φ -constraint induced by some cohesive group S and some t>0t>0 for which the demanded amount is positive. Since t≤ℓ=n/4t≤ =n/4, positivity of ⌊t⋅|S|/n⌋ t·|S|/n implies |S|≥4|S|≥ 4. Since preferences are static and S is cohesive, pick any x∈⋂i∈SAix∈ _i∈ SA_i; then S⊆i∈N:x∈AiS \i∈ N:x∈ A_i\. We distinguish cases. • If x=zx=z, then S⊆b1,…,b8S \b_1,…,b_8\, and the maximum possible demand over such groups is ⌊ℓ⋅8/n⌋=2 · 8/n =2. Note that for PJR/EJR, the maximum demand is 22 (for |S|=8|S|=8); for JR it is at most 11. Since we select z at least m+2≥2m+2≥ 2 times, all these constraints are satisfied. • If x=pex=p_e for some e=u,ve=\u,v\, then necessarily S⊆i∈N:pe∈Ai=SeS \i∈ N:p_e∈ A_i\=S_e and |S|≥4|S|≥ 4 implies S=SeS=S_e. Since U is a vertex cover, at least one endpoint (say u) lies in U, so o selects cuc_u in some round. Because cu∈Aae,4c_u∈ A_a_e,4 and ae,4∈Sea_e,4∈ S_e, this gives the required representation for SeS_e (and its demand equals 11 as computed above). • If x=cvx=c_v for some v∈Vv∈ V, then S⊆i∈N:cv∈AiS \i∈ N:c_v∈ A_i\, which has size 55; hence the demand is at most 11 as in Claim 2. Moreover, since only sv,1,sv,2s_v,1,s_v,2 approve only cvc_v, any such S with |S|≥4|S|≥ 4 must contain some voter of the form ae,4a_e,4 for an edge e=v,ue=\v,u\ incident to v. If v∈Uv∈ U, then o selects cvc_v and the constraint is satisfied. If v∉Uv∉ U, then because U is a vertex cover we have u∈Uu∈ U, so o selects cuc_u; since cu∈Aae,4c_u∈ A_a_e,4, the voter ae,4∈Sa_e,4∈ S is satisfied, which meets the JR/PJR/EJRJR/PJR/EJR requirement (with demand 11). Thus o is Φ -feasible. If |U|=k|U|=k, then by (2), a canonical outcome has welfare Util()=8(ℓ−k)+5k=8ℓ−3k. Util(o)=8( -k)+5k=8 -3k. Hence maximizing Util over Φ -feasible outcomes is equivalent to minimizing k, and WΦ(EG)=8ℓ−3⋅vc(G),W (E_G)=8 -3·vc(G), where vc(G)vc(G) is the minimum vertex cover size. Assume for contradiction that Φ-MaxUTIL -MaxUTIL admits a PTAS. Given ε∈(0,1) ∈(0,1), let δ:=ε/15δ:= /15 and run the PTAS on EGE_G to obtain a Φ -feasible outcome o with Util()≥(1−δ)⋅WΦ(EG) Util(o)≥(1-δ)· W (E_G). Canonicalize o using Claims 1–2 (this does not decrease welfare), and let k be the size of the corresponding vertex cover; let k∗:=vc(G)k^*:=vc(G). Then 8ℓ−3k≥(1−δ)(8ℓ−3k∗)⟹k≤(1−δ)k∗+8δℓ3.8 -3k\ ≥\ (1-δ)(8 -3k^*) k\ ≤\ (1-δ)k^*+ 8δ 3. In a cubic graph, each vertex covers at most 33 edges, so k∗≥|E|/3=(3m/2)/3=m/2k^*≥|E|/3=(3m/2)/3=m/2. Thus m≤2k∗m≤ 2k^*, and hence ℓ=2m+2≤4k∗+2≤6k∗, =2m+2≤ 4k^*+2≤ 6k^*, since k∗≥1k^*≥ 1 for cubic graphs. Therefore, k≤(1−δ)k∗+8δ⋅6k∗3=(1+15δ)k∗=(1+ε)k∗.k\ ≤\ (1-δ)k^*+ 8δ· 6k^*3=(1+15δ)k^*=(1+ )k^*. So the PTAS for Φ-MaxUTIL -MaxUTIL would give us a PTAS for Min-Vertex-Cover on cubic graphs, contradicting APX-completeness unless P=NPP=NP. Thus, Φ-MaxUTIL -MaxUTIL is APX-hard. Finally, note that by construction, preferences are static, each voter approves at most 33 candidates, and each candidate is approved by at most 88 voters. Appendix D Omitted Proofs from Section 5 D.1 Proof of Theorem 5.1 Fix a nonempty voter group S⊆NS N with ⋂i∈SAi≠∅ _i∈ SA_i≠ (so S agrees in every round). If ⋂i∈SAi=∅ _i∈ SA_i= , then under static preferences S never agrees in any round, hence imposes no JR constraint; thus we consider only ⋂i∈SAi≠∅ _i∈ SA_i≠ . Since the right-hand side in Definition 2.1 is nondecreasing in t and satS()sat_S(o) does not depend on t, the strongest JR requirement for such S is obtained by taking t=ℓt= , i.e., satS()≥min1,⌊ℓ⋅|S|n⌋.sat_S(o)≥ \1, ·|S|n \. Define η:=⌈nℓ⌉η:= n . Then min1,⌊ℓ⋅|S|/n⌋=1 \1, ·|S|/n \=1 if and only if ℓ⋅|S|≥n ·|S|≥ n, equivalently |S|≥η|S|≥η; otherwise the JR inequality is trivial. Moreover, under static preferences, for any outcome o with multiplicities x, we have satS()≥1⇔∃i∈S:sati()≥1,sat_S(o)≥ 1 ∃\,i∈ S:\ sat_i(x)≥ 1, because satS()sat_S(o) counts rounds r with or∈⋃i∈SAio_r∈ _i∈ SA_i, which happens in some round if and only if some voter in S approves the chosen candidate in that round. For each candidate p∈Pp∈ P let N(p):=i∈N:p∈AiN(p):=\i∈ N:p∈ A_i\ be its set of approvers. Given x, define the set of unsatisfied approvers of p by Up(x):=i∈N(p):sati(x)=0.U_p(x):=\i∈ N(p):sat_i(x)=0\. We claim that a multiplicity vector x is JR-feasible if and only if |Up(x)|≤η−1for all p∈P.|U_p(x)|≤η-1 all p∈ P. (4) Indeed, if (4) fails for some p, then Up(x)U_p(x) is cohesive (all its members approve p), has size at least η (and since |Up()|≥η=⌈n/ℓ⌉|U_p(x)|≥η= n/ , we have ℓ|Up()|≥ℓη≥n |U_p(x)|≥ η≥ n, and thus min1,⌊ℓ|Up()|/n⌋=1 \1, |U_p(x)|/n \=1), and contains no satisfied voter; equivalently satUp()()=0sat_U_p(x)(o)=0, contradicting JR. Conversely, if JR is violated, then there exists a cohesive group S with |S|≥η|S|≥η such that no voter in S is satisfied (so sati()=0sat_i(x)=0 for all i∈Si∈ S). Pick any p∈⋂i∈SAip∈ _i∈ SA_i; then S⊆Up(x)S U_p(x), so |Up()|≥|S|≥η|U_p(x)|≥|S|≥η, again contradicting (4). Let :=Ai:i∈NC:=\A_i:i∈ N\ be the set of distinct approval sets (approval classes). For each class C∈C let nC:=|i∈N:Ai=C|n_C:=|\i∈ N:A_i=C\|. All voters in class C have the same satisfaction vC(x):=∑p∈Cxpv_C(x):= _p∈ Cx_p. Introduce, for each class C∈C , a binary variable yCy_C that indicates whether the class is satisfied at least once: yC=1⟺vC(x)≥1.y_C=1\ \ v_C(x)≥ 1. This is enforced by the linear constraints ∑p∈Cxp≥yC,∑p∈Cxp≤ℓyC,yC∈0,1 for all C∈. _p∈ Cx_p≥ y_C,\ _p∈ Cx_p≤ y_C,\ y_C∈\0,1\ for all C . Then the number of unsatisfied approvers of a candidate p equals |Up(x)|=∑C∈:p∈CnC(1−yC),|U_p(x)|= _C :p∈ Cn_C(1-y_C), and the JR feasibility constraints (4) become the linear inequalities ∑C∈:p∈CnC(1−yC)≤η−1 for all p∈P. _C :p∈ Cn_C(1-y_C)≤η-1 for all p∈ P. We therefore solve the following ILP: max∑p∈Pw(p)xp _p∈ Pw(p)\,x_p subject to ∑p∈Pxp=ℓ and xp∈ℤ≥0 for all p∈P, _p∈ Px_p= and x_p _≥ 0 for all p∈ P, the class constraints defining the yCy_C above, and the JR constraints for all p∈Pp∈ P. By the discussion above, feasible solutions correspond exactly to JR-feasible multiplicity vectors, and the objective equals Util() Util(x). The ILP has m integer variables (xp)p∈P(x_p)_p∈ P and |||C| binary (hence integer) variables (yC)C∈(y_C)_C . Since ⊆2PC 2^P, we have ||≤2m|C|≤ 2^m, so the number of integer variables is bounded by a function of m only. By Lenstra’s theorem, this ILP can be solved in time f(m)⋅poly(n,ℓ)f(m)·poly(n, ) for some computable function f. From an optimal solution x, we output an outcome by selecting each candidate p in exactly xpx_p rounds (in arbitrary order), which achieves optimal utilitarian welfare among all JR-feasible outcomes. D.2 Proof of Theorem 5.2 Fix a nonempty voter group S⊆NS N and define US:=⋃i∈SAi⊆PU_S:= _i∈ SA_i P. If ⋂i∈SAi=∅ _i∈ SA_i= , then S does not agree in any round (and thus cannot agree in any nonempty subset of rounds), so Definition 2.1 imposes no PJR constraint for S. Otherwise, S agrees in every round, and since t↦⌊t⋅|S|/n⌋t t·|S|/n is nondecreasing, it suffices to enforce the strongest constraint obtained by taking t=ℓt= : satS()=|r∈[ℓ]:or∈US|=∑p∈USxp≥⌊ℓ⋅|S|n⌋.sat_S(o)= |\r∈[ ]:o_r∈ U_S\ |= _p∈ U_Sx_p\ ≥\ ·|S|n . Under static preferences, either ⋂i∈SAi=∅ _i∈ SA_i= and S agrees in no round, or ⋂i∈SAi≠∅ _i∈ SA_i≠ and S agrees in every round; hence for cohesive S it suffices to consider t=ℓt= . For every subset U⊆PU P, define g(U):=0,U=∅,maxc∈U|i∈N:c∈Ai and Ai⊆U|,U≠∅.g(U):= cases0,&U= ,\\[5.69054pt] _c∈ U\ |\i∈ N:c∈ A_i and A_i U\ |,&U≠ . cases We claim that a multiplicity vector x satisfies PJR if and only if for every U⊆PU P, ∑p∈Uxp≥⌊ℓ⋅g(U)n⌋. _p∈ Ux_p\ ≥\ · g(U)n . (5) We first prove the forward direction. Fix U⊆PU P. If g(U)=0g(U)=0, then (5) is trivial. Otherwise, pick c∈Uc∈ U attaining g(U)g(U) and let S:=i∈N:c∈Ai and Ai⊆U.S:=\i∈ N:c∈ A_i and A_i U\. Then S≠∅S≠ , and c⊆⋂i∈SAi\c\ _i∈ SA_i, so S agrees in every round. Moreover ⋃i∈SAi⊆U _i∈ SA_i U. Applying the (static) PJR inequality to S (with t=ℓt= ) gives us ∑p∈Uxp≥∑p∈∪i∈SAixp≥⌊ℓ⋅|S|n⌋=⌊ℓ⋅g(U)n⌋, _p∈ Ux_p≥ _p∈ _i∈ SA_ix_p≥ ·|S|n = · g(U)n , which is exactly (5). Next, we prove the backward direction. Let S⊆NS N be any nonempty group with ⋂i∈SAi≠∅ _i∈ SA_i≠ , and set U:=US=⋃i∈SAiU:=U_S= _i∈ SA_i. Pick any c∈⋂i∈SAic∈ _i∈ SA_i. Then c∈Uc∈ U and for every i∈Si∈ S we have c∈Aic∈ A_i and Ai⊆UA_i U, so |S|≤|i∈N:c∈Ai and Ai⊆U|≤g(U).|S|\ ≤\ |\i∈ N:c∈ A_i and A_i U\ |\ ≤\ g(U). Using (5) for this U gives satS()=∑p∈Uxp≥⌊ℓ⋅g(U)n⌋≥⌊ℓ⋅|S|n⌋,sat_S(o)= _p∈ Ux_p\ ≥\ · g(U)n \ ≥\ ·|S|n , which is exactly the strongest static PJR requirement for S (and hence implies all weaker requirements for smaller t). By the claim, PJR-feasible outcomes correspond exactly to multiplicity vectors ∈ℤ≥0Px _≥ 0^P satisfying ∑p∈Pxp=ℓ _p∈ Px_p= and (5) for all U⊆PU P. Therefore PJR-MaxUTIL reduces to the ILP max∑p∈Pw(p)xp _p∈ Pw(p)x_p subject to ∑p∈Pxp=ℓ,xp∈ℤ≥0 for all p∈P, and _p∈ Px_p= ,x_p _≥ 0 for all p∈ P, and ∑p∈Uxp≥⌊ℓ⋅g(U)n⌋ for all U⊆P. _p∈ Ux_p≥ · g(U)n for all U P. This ILP has exactly m integer variables. The number of constraints is 2m+12^m+1, and all coefficients/right-hand sides can be computed from the input in time f1(m)⋅poly(n,ℓ)f_1(m)·poly(n, ). By Lenstra’s theorem Lenstra Jr [1983], an ILP with a fixed number of integer variables can be solved in time f2(m)⋅poly(n,ℓ)f_2(m)·poly(n, ) for a computable function f2f_2 depending only on m. From an optimal solution x, we output any outcome that selects each candidate p exactly xpx_p times; under static preferences this outcome achieves welfare Util() Util(x) and satisfies PJR by construction. D.3 Proof of Theorem 5.3 Fix a nonempty voter set S⊆NS N. Under static preferences, S agrees in a round r iff ⋂i∈Ssi,r=⋂i∈SAi≠∅ _i∈ Ss_i,r= _i∈ SA_i≠ ; in that case it agrees in every round. Since t↦⌊t|S|/n⌋t t|S|/n is nondecreasing and sati()sat_i(x) is independent of t, it suffices to enforce EJR only for t=ℓt= : ∀S⊆N with ⋂i∈SAi≠∅,∃i∈S:sati(x)≥⌊ℓ⋅|S|n⌋.∀\,S N with _i∈ SA_i≠ , ∃ i∈ S:sat_i(x)≥ ·|S|n . (6) For each candidate c∈Pc∈ P, let N(c):=i∈N:c∈AiN(c):=\i∈ N:c∈ A_i\ be the set of voters approving c. For a fixed x, sort the multiset sati():i∈N(c)\sat_i(x):i∈ N(c)\ in nondecreasing order and denote the order statistics by bc,1()≤bc,2()≤⋯≤bc,|N(c)|().b_c,1(x)≤ b_c,2(x)≤·s≤ b_c,|N(c)|(x). (If N(c)=∅N(c)= , there are no constraints associated with c.) Claim 1. A multiplicity vector x satisfies EJR if and only if for every c∈Pc∈ P and every s∈[|N(c)|]s∈[|N(c)|], bc,s()≥⌊ℓsn⌋.b_c,s(x)≥ sn . (7) Proof of Claim 1. We first prove the forward direction. Assume (6) holds. Fix c∈Pc∈ P and s∈[|N(c)|]s∈[|N(c)|], and let S be the set of the s voters in N(c)N(c) with the smallest satisfaction values under x. Then S is cohesive because c∈⋂i∈SAic∈ _i∈ SA_i, so (6) implies that some i∈Si∈ S has sati()≥⌊ℓs/n⌋sat_i(x)≥ s/n . By construction, maxi∈Ssati()=bc,s() _i∈ Ssat_i(x)=b_c,s(x), hence (7) follows. Next, we prove the backward direction. Assume (7) holds for all c and s. Let S⊆NS N be any nonempty cohesive group and pick some c∈⋂i∈SAic∈ _i∈ SA_i; then S⊆N(c)S N(c). Let s:=|S|s:=|S|. Among the |N(c)||N(c)| values sati():i∈N(c)\sat_i(x):i∈ N(c)\, at most s−1s-1 are strictly smaller than bc,s()b_c,s(x). Thus, there exists i∈Si∈ S with sati()≥bc,s()≥⌊ℓs/n⌋=⌊ℓ⋅|S|/n⌋sat_i(x)≥ b_c,s(x)≥ s/n = ·|S|/n , which is exactly (6). Thus x satisfies EJR. ∎ Let :=Ai:i∈N⊆2PC:=\A_i:i∈ N\ 2^P be the set of approval classes, and for each C∈C let nC:=|i∈N:Ai=C| and vC():=∑p∈Cxp.n_C\ :=|\i∈ N:A_i=C\| and v_C(x):= _p∈ Cx_p. Thus all voters in class C have satisfaction vC(x)v_C(x). Let ρ:=|C|ρ:=|C|; since C⊆2PC 2^P, we have ρ≤2mρ≤ 2^m. Claim 1 reduces EJR to inequalities about the order statistics of satisfactions among N(c)N(c) for each c. These order statistics depend only on the relative order of the class values (vC())C∈(v_C(x))_C , which we linearize by enumerating all possible orders. Specifically, enumerate all permutations π of the ρ classes. For a fixed permutation π, introduce integer variables vCv_C (for C∈C ) and enforce: vπ(1)≤vπ(2)≤⋯≤vπ(ρ).v_π(1)\ ≤\ v_π(2)≤·s≤ v_π(ρ). (8) Ties are allowed; if multiple classes share the same satisfaction value, any order among them is consistent with the sorted multiset. For a candidate c∈Pc∈ P, let πc(1),…,πc(kc) _c(1),…, _c(k_c) be the subsequence of π consisting of exactly those classes that contain c, in the same relative order as in π. Define Hc,0:=0 and Hc,j:=∑h=1jnπc(h) for j=1,…,kc,H_c,0:=0 and H_c,j:= _h=1^jn_ _c(h) for j=1,…,k_c, so that Hc,kc=|N(c)|H_c,k_c=|N(c)|. Under (8), the sorted list of satisfactions of voters in N(c)N(c) is obtained by taking nπc(1)n_ _c(1) copies of vπc(1)v_ _c(1), then nπc(2)n_ _c(2) copies of vπc(2)v_ _c(2), and so on. Hence, for any s with Hc,j−1<s≤Hc,jH_c,j-1<s≤ H_c,j we have bc,s(x)=vπc(j)b_c,s(x)=v_ _c(j). Because s↦⌊ℓs/n⌋s s/n is nondecreasing, within each block (Hc,j−1,Hc,j](H_c,j-1,H_c,j] the strongest inequality in (7) occurs at s=Hc,js=H_c,j. Therefore, for a fixed π, the family of inequalities (7) for candidate c is equivalent to the boundary constraints vπc(j)≥⌊ℓ⋅Hc,jn⌋ for all c∈P and j∈[kc].v_ _c(j)≥ · H_c,jn for all c∈ P and j∈[k_c]. (9) Fix a permutation π. Consider the following ILP with integer variables (xp)p∈P(x_p)_p∈ P and (vC)C∈(v_C)_C : max∑p∈Pw(p)xp _p∈ Pw(p)\,x_p subject to ∑p∈Pxp=ℓ,xp∈ℤ≥0 for all p∈P, and _p∈ Px_p= ,x_p _≥ 0 for all p∈ P, and vC=∑p∈Cxp for all C∈, v_C= _p∈ Cx_p for all C , and the constraints (8) and (9). Every feasible solution defines a multiplicity vector x whose induced class satisfactions respect the order π and satisfy all inequalities (7), hence satisfy EJR by Claim 1. Conversely, if x is EJR-feasible, choose any permutation π that orders the classes nondecreasingly by the realized values vC()v_C(x) (breaking ties arbitrarily); then (,(vC())C∈)(x,(v_C(x))_C ) satisfies (8) and (9), so it is feasible for the corresponding ILP and attains the same welfare. Indeed, (9) follows by applying (7) at s=Hc,js=H_c,j and using bc,Hc,j(x)=vπc(j)(x)b_c,H_c,j(x)=v_ _c(j)(x) under the consistent order (8). Thus, the optimal EJR-feasible welfare equals the maximum ILP optimum over all permutations π. We compute this by enumerating all ρ!ρ! permutations and solving each ILP, taking the best solution. Each ILP has m+ρ≤m+2m+ρ≤ m+2^m integer variables, so by Lenstra’s theorem Lenstra Jr [1983] it can be solved in time g(m+ρ)⋅poly(n,ℓ)g(m+ρ)·poly(n, ) for some computable g. Since ρ≤2mρ≤ 2^m, the total running time is f(m)⋅poly(n,ℓ)f(m)·poly(n, ) for a computable f. Finally, from an optimal multiplicity vector x we output an outcome o∈Pℓo∈ P that selects each candidate p exactly xpx_p times; this preserves all satisfactions and Util, hence gives us an optimal solution to EJR-MaxUTIL. By Lemma 4.2, under static preferences EJR and EJR+ are equivalent, so the same algorithm also solves EJR+-MaxUTIL. D.4 Proof of Theorem 5.4 For any U⊆TU T write SU:=⋃θ∈UNθ⊆N.S_U:= _θ∈ UN_θ N. We say that a type set U⊆TU T is JR-relevant if there exists an integer t≥1t≥ 1 such that SUS_U agrees in a size-t subset of rounds and ⌊t⋅|SU|/n⌋≥1 t·|S_U|/n ≥ 1 (equivalently, t⋅|SU|≥nt·|S_U|≥ n). Let X():=θ∈T:satθ()>0X(o):=\θ∈ T:sat_θ(o)>0\ denote the set of satisfied types. Now, we claim that an outcome o satisfies JR if and only if ∀U⊆Tthat are JR-relevant,X()∩U≠∅.∀\,U T\ that are JR-relevant,X(o)∩ U≠ . (10) We first prove the forward direction. Fix a JR-relevant U and let t witness relevance. Applying JR to the voter group SUS_U with this t gives us satSU()≥min1,⌊t⋅|SU|/n⌋=1.sat_S_U(o)≥ \1, t·|S_U|/n \=1. By the definition of satSU(⋅)sat_S_U(·), this implies that some voter in SUS_U has positive satisfaction, hence some type θ∈Uθ∈ U has satθ()>0sat_θ(o)>0. Therefore X()∩U≠∅X(o)∩ U≠ . Next, we prove the backward direction. Assume (10). Let S⊆NS N and t≥1t≥ 1 be such that S agrees in a size-t subset of rounds and ⌊t⋅|S|/n⌋≥1 t·|S|/n ≥ 1. Let U:=θ∈T:S∩Nθ≠∅⊆T.U:=\θ∈ T:S∩ N_θ≠ \ T. Since adding further voters of types already present does not change any per-round intersections (all voters of a type have identical approvals in every round), SUS_U agrees in the same set of rounds as S, and thus also agrees in a size-t subset of rounds. Moreover |SU|≥|S||S_U|≥|S|, so t⋅|SU|≥nt·|S_U|≥ n. Thus, U is JR-relevant, and by (10) there exists θ∈X()∩Uθ∈ X(o)∩ U. Pick any voter i∈S∩Nθi∈ S∩ N_θ; then i has positive satisfaction, so satS()≥1sat_S(o)≥ 1. Since min1,⌊t⋅|S|/n⌋=1 \1, t·|S|/n \=1, the JR inequality for (S,t)(S,t) holds. As (S,t)(S,t) was arbitrary, o satisfies JR. Now, for each round j∈[ℓ]j∈[ ] and candidate p∈Pp∈ P define Uj(p):=θ∈T:p∈Aθ,j⊆T and wj(p):=∑θ∈Uj(p)nθ.U_j(p):=\θ∈ T:p∈ A_θ,j\ T and w_j(p):= _θ∈ U_j(p)n_θ. Then Util()=∑j=1ℓwj(oj) Util(o)= _j=1 w_j(o_j). For j∈0,1,…,ℓj∈\0,1,…, \ and X⊆TX T, let DP[j,X]DP[j,X] be the maximum welfare achievable in the first j rounds by some prefix (o1,…,oj)(o_1,…,o_j) such that the set of satisfied types after these j rounds equals X. Initialize DP[0,∅]=0DP[0, ]=0 and DP[0,X]=−∞DP[0,X]=-\,∞ for X≠∅X≠ . For each j=1,…,ℓj=1,…, and each X⊆TX T, update using DP[j,X∪Uj(p)] [j,\,X∪ U_j(p) ] =maxDP[j,X∪Uj(p)],DP[j−1,X]+wj(p) = \DP [j,\,X∪ U_j(p) ],\ DP[j-1,X]+w_j(p) \ for all p∈Pp∈ P. Correctness follows by induction on j. To obtain the claimed running time, for each round j, it suffices to consider only the distinct type-patterns j:=Uj(p):p∈P⊆2T,U_j:=\U_j(p):p∈ P\ 2^T, keeping one representative candidate per pattern (the transition and the value wj(⋅)w_j(·) depend only on the pattern). Since |j|≤2κ|U_j|≤ 2^κ and there are 2κ2^κ states X, each DP layer is updated in (2κ⋅2κ)=(4κ)O(2^κ· 2^κ)=O(4^κ) time. Then, recall that an outcome is JR-feasible if and only if its satisfied type set satisfies (10). Therefore the optimal JR welfare is equivalent to maxDP[ℓ,X]:X⊆T satisfies (10), \DP[ ,X]:\ X T satisfies eq:jr_hit_types \, and an optimal outcome can be recovered by storing standard backtracking pointers during the DP. The DP performs (ℓ⋅4κ)O( · 4^κ) transitions after the type-pattern families have been computed; including preprocessing, the running time is f(κ)⋅poly(n,m,ℓ)f(κ)·poly(n,m, ) for some computable function f. Thus, JRJR-MAXUTIL is FPT with respect to κ. D.5 Proof of Theorem 5.5 We claim that an outcome o satisfies EJR if and only if ∀U⊆T,U≠∅ with dU>0,maxθ∈Usatθ()≥dU.∀ U T,U≠ with d_U>0, _θ∈ Usat_θ(o)≥ d_U. (11) We first show the forward direction. Fix a nonempty U⊆TU T with dU>0d_U>0. For any round r∈[ℓ]r∈[ ], since all voters of a type have identical approval sets in that round, intersecting over all voters in SUS_U is the same as intersecting once per type: ⋂i∈SUsi,r=⋂θ∈UAθ,r. _i∈ S_Us_i,r\ =\ _θ∈ UA_θ,r. Hence SUS_U agrees exactly in the γU _U rounds counted by the definition of γU _U, and therefore SUS_U agrees in a size-γU _U subset of rounds, so the EJR constraint for (SU,t)(S_U,t) is strongest at t=γUt= _U because t↦⌊t|SU|/n⌋t t|S_U|/n is nondecreasing. Since EJR demands are monotone in the subset size, it suffices to apply EJR to the pair (SU,γU)(S_U, _U) to obtain some voter i∈SUi∈ S_U with sati()≥⌊γU⋅|SU|n⌋=dU.sat_i(o)≥ _U·|S_U|n =d_U. Let θ∈Uθ∈ U be the type of i. Then satθ()=sati()≥dUsat_θ(o)=sat_i(o)≥ d_U, proving (11). Next, we show the backward direction. Assume (11). Let S⊆NS N be any nonempty voter group and let t∈ℕ>0t _>0 be such that S agrees in a size-t subset of rounds. Define the set of types present in S by U:=type(i):i∈S⊆T,U:=\type(i):i∈ S\\ \ T, so that S⊆SUS S_U and S∩Nθ≠∅S∩ N_θ≠ for every θ∈Uθ∈ U. For each round r∈[ℓ]r∈[ ] we again have ⋂i∈Ssi,r=⋂θ∈UAθ,r, _i∈ Ss_i,r\ =\ _θ∈ UA_θ,r, because intersecting multiple identical sets within a type does not change the intersection. Therefore, the rounds in which S agrees are exactly the rounds counted by γU _U; in particular, t≤γUt≤ _U. Also, since S⊆SUS S_U, we have |S|≤|SU||S|≤|S_U|, and thus ⌊t⋅|S|n⌋≤⌊γU⋅|SU|n⌋=dU. t·|S|n \ ≤\ _U·|S_U|n \ =\ d_U. If dU=0d_U=0, then the EJR requirement for the pair (S,t)(S,t) is trivial. Otherwise dU>0d_U>0, and (11) gives us some θ∗∈Uθ^*∈ U with satθ∗()≥dUsat_θ^*(o)≥ d_U. Pick any voter i∗∈S∩Nθ∗i^*∈ S∩ N_θ^* (nonempty by definition of U). Then sati∗()=satθ∗()≥dU≥⌊t⋅|S|n⌋,sat_i^*(o)=sat_θ^*(o)\ ≥\ d_U\ ≥\ t·|S|n , which is exactly the EJR condition for (S,t)(S,t). As (S,t)(S,t) was arbitrary, o satisfies EJR. For any outcome o and type θ∈Tθ∈ T, define the truncated value vθ():=minD,satθ()∈0,1,…,D.v_θ(o):= \D,sat_θ(o)\\ ∈\ \0,1,…,D\. Because dU≤Dd_U≤ D for all U, condition (11) is equivalent to ∀U⊆T,U≠∅ with dU>0,maxθ∈Uvθ()≥dU.∀\,U T,U≠ with d_U>0, _θ∈ Uv_θ(o)≥ d_U. (12) Now, fix an indexing T=θ1,…,θκT=\ _1,…, _κ\, and identify a truncated satisfaction profile with a vector v=(v1,…,vκ)∈0,1,…,Dκv=(v_1,…,v_κ)∈\0,1,…,D\^κ, where vjv_j corresponds to θj _j. For each round r∈[ℓ]r∈[ ] and candidate p∈Pp∈ P, define the set of approving types Xr(p):=θ∈T:p∈Aθ,r⊆T,X_r(p):=\θ∈ T:p∈ A_θ,r\\ \ T, and for any X⊆TX T define its welfare weight w(X):=∑θ∈Xnθ.w(X):= _θ∈ Xn_θ. Thus, choosing p in round r contributes exactly w(Xr(p))w(X_r(p)) to utilitarian welfare, and increases satθ(⋅)sat_θ(·) by 11 precisely for θ∈Xr(p)θ∈ X_r(p). For each round r, let r:=Xr(p):p∈P⊆2TX_r:=\X_r(p):p∈ P\\ 2^T be the family of distinct type approval patterns achievable in that round (so |r|≤2κ|X_r|≤ 2^κ). For X⊆TX T, let Δ(X)∈0,1κ (X)∈\0,1\^κ be the indicator vector with (Δ(X))j:=[θj∈X].( (X))_j:=1[ _j∈ X]. Define DP[r,v]DP[r,v] to be the maximum utilitarian welfare achievable by an outcome on the first r rounds such that the resulting truncated satisfaction vector equals v. Initialize DP[0,(0,…,0)]=0andDP[0,v]=−∞ for all other v.DP[0,(0,…,0)]=0 [0,v]=-∞ for all other v. For each r=1,…,ℓr=1,…, , each v∈0,…,Dκv∈\0,…,D\^κ, and each X∈rX _r, define v′:=minD,v+Δ(X)(componentwise),v := \D,\,v+ (X)\ (componentwise), and update DP[r,v′]:=maxDP[r,v′],DP[r−1,v]+w(X).DP[r,v ]:= \DP[r,v ],DP[r-1,v]+w(X) \. For reconstruction, for each r and each X∈rX _r fix a representative candidate pr,X∈Pp_r,X∈ P with Xr(pr,X)=X_r(p_r,X)=X, and store standard backtracking pointers for maximizing transitions. Then, we have shown that an outcome o is EJR-feasible if and only if its truncated vector v()v(o) satisfies (12). Hence the optimal EJR welfare equals maxDP[ℓ,v]:v∈0,1,…,Dκsatisfies (12), \DP[ ,v]:v∈\0,1,…,D\^κ\ satisfies eq:ejr-truncated \, and an optimal outcome can be recovered by backtracking and outputting the stored representatives pr,Xp_r,X. There are (D+1)κ(D+1)^κ states per DP layer. In each round r we consider at most |r|≤2κ|X_r|≤ 2^κ actions, and each transition updates κ coordinates (which is polynomial in the parameter). Thus the DP core runs in time (ℓ⋅(D+1)κ⋅2κ)O( ·(D+1)^κ· 2^κ) after preprocessing; including the computation of the type-pattern families and the demands (dU)U⊆T(d_U)_U T, the running time is f(κ,D)⋅poly(n,m,ℓ)f(κ,D)·poly(n,m, ). Therefore, the algorithm is FPT with respect to κ+Dκ+D. D.6 Proof of Proposition 5.6 Let the distinct profiles be indexed by j∈[q]j∈[q], and for each j let LjL_j denote the number of rounds of profile j (so ∑j=1qLj=ℓ _j=1^qL_j= ). For U⊆TU T, let SU:=⋃θ∈UNθS_U:= _θ∈ UN_θ. For each profile j and type θ, let Aθ,j⊆PA_θ,j P for the (common) approval set of type θ in rounds of profile j. For U⊆TU T, we have γU=∑j=1qLj⋅[⋂θ∈UAθ,j≠∅] _U= _j=1^qL_j·1[ _θ∈ UA_θ,j≠ ]. For each profile j∈[q]j∈[q] and candidate p∈Pp∈ P, define the set of types approving p under profile j by Xj(p):=θ∈T:p∈Aθ,j⊆T,X_j(p)\ :=\ \θ∈ T:p∈ A_θ,j\\ \ T, and let Xj:=Xj(p):p∈P⊆ 2TX_j\ :=\ \X_j(p):p∈ P\\ \ 2^T be the family of achievable type sets in profile j. Fix a nonempty voter group S⊆NS N and let U:=type(i):i∈S⊆TU:=\type(i):i∈ S\ T be the set of types present in S. Because all voters of the same type have identical approval sets in every round, for each t∈[ℓ]t∈[ ] we have ⋃i∈Ssi,t _i∈ Ss_i,t =⋃θ∈UAθ,t=⋃i∈SUsi,t, and = _θ∈ UA_θ,t= _i∈ S_Us_i,t, and ⋂i∈Ssi,t _i∈ Ss_i,t =⋂θ∈UAθ,t=⋂i∈SUsi,t. = _θ∈ UA_θ,t= _i∈ S_Us_i,t. Hence S and SUS_U agree in exactly the same set of rounds, so the maximum agreement size for S equals γU _U. Since ⌊t|S|/n⌋ t|S|/n is nondecreasing in t, it suffices to enforce PJR only for t=γUt= _U, the maximum number of rounds in which the group can agree. Moreover, since the unions coincide in every round, satS()=satSU()sat_S(o)=sat_S_U(o) for every outcome o. Finally, |S|≤|SU||S|≤|S_U| implies ⌊γU⋅|S|n⌋≤⌊γU⋅|SU|n⌋=dU. _U·|S|n ≤ _U·|S_U|n =d_U. Therefore, if an outcome o satisfies satSU()≥dUsat_S_U(o)≥ d_U, then it satisfies the strongest PJR requirement for S, and thus satisfies all PJR constraints for S. Conversely, if o satisfies PJR, then applying PJR to the voter group SUS_U and t=γUt= _U (the number of rounds in which SUS_U agrees), we get satSU()≥⌊γU⋅|SU|/n⌋=dU.sat_S_U(o)≥ _U·|S_U|/n =d_U. Consequently, an outcome is PJR-feasible if and only if it satisfies satSU()≥dUsat_S_U(o)≥ d_U for every nonempty U⊆TU T. Fix a profile j∈[q]j∈[q] and X∈XjX∈ X_j. In a round of profile j, selecting a candidate approved by exactly the types in X contributes w(X):=∑θ∈Xnθw(X):= _θ∈ Xn_θ to utilitarian welfare. Moreover, for any U⊆TU T such a round contributes to satSU()sat_S_U(o) if and only if X∩U≠∅X∩ U≠ . Introduce an integer variable yj,X∈ℤ≥0y_j,X _≥ 0 for every profile j∈[q]j∈[q] and every X∈XjX∈ X_j, interpreted as the number of rounds of profile j in which we pick a candidate whose approving type-set is exactly X. Consider the ILP max∑j=1q∑X∈Xjw(X)yj,X _j=1^q\ _X∈ X_jw(X)\,y_j,X subject to ∑X∈Xjyj,X _X∈ X_jy_j,X =Lj for all j∈[q], =L_j for all j∈[q], ∑j=1q∑X∈XjX∩U≠∅yj,X _j=1^q\ _ subarraycX∈ X_j\\ X∩ U≠ subarrayy_j,X ≥dU for all U⊆T,U≠∅, and ≥\ d_U for all U T,U≠ , and yj,X∈ℤ≥0 y_j,X _≥ 0 for all j∈[q],∀X∈Xj. for all j∈[q],\ ∀ X∈ X_j. We now prove correctness. Given an outcome o, define yj,Xy_j,X as the number of rounds t of profile j with Xj(ot)=X_j(o_t)=X. Then the profile constraints hold by definition. For any nonempty U⊆TU T, the left-hand side of the second constraint equals the number of rounds in which the chosen candidate is approved by at least one type in U, i.e., it equals satSU()sat_S_U(o). Thus feasibility of the ILP is equivalent to satisfying satSU()≥dUsat_S_U(o)≥ d_U for all nonempty U⊆TU T, which is equivalent to PJR. Finally, the objective equals Util() Util(o) because each round counted in yj,Xy_j,X contributes exactly w(X)w(X) to welfare. Conversely, given a feasible integer solution (yj,X)(y_j,X), for each j∈[q]j∈[q] and each X∈XjX∈ X_j fix an arbitrary representative candidate pj,X∈Pp_j,X∈ P with Xj(pj,X)=X_j(p_j,X)=X (which exists by definition of XjX_j). Since candidates may be selected multiple times across rounds, we may use the same representative candidate pj,Xp_j,X in all yj,Xy_j,X rounds of profile j without violating feasibility. Assign, for each profile j, the candidates pj,XX∈Xj\p_j,X\_X∈ X_j to its LjL_j rounds so that pj,Xp_j,X is used in exactly yj,Xy_j,X rounds. The resulting outcome satisfies all constraints satSU()≥dUsat_S_U(o)≥ d_U, hence is PJR-feasible, and achieves utilitarian welfare equal to the ILP objective. For each profile j, |Xj|≤2κ|X_j|≤ 2^κ, so the number of integer variables is at most p:=∑j=1q|Xj|≤q⋅2κ.p:= _j=1^q|X_j|≤ q· 2^κ. The ILP has q profile constraints and at most 2κ−12^κ-1 nontrivial PJR constraints. All coefficients are integers of magnitude at most n or ℓ , and each dUd_U can be computed from the profile counts (Lj)j∈[q](L_j)_j∈[q] and the sets (Aθ,j)θ∈T,j∈[q](A_θ,j)_θ∈ T,\,j∈[q] in f0(κ,q)⋅poly(n,ℓ,m)f_0(κ,q)·poly(n, ,m) time by enumerating U⊆TU T and using γU=∑j=1qLj⋅[⋂θ∈UAθ,j≠∅]. _U\ =\ _j=1^qL_j·1 [ _θ∈ UA_θ,j≠ ]. By Lenstra’s result Lenstra Jr [1983], the ILP can be solved in time g(p)⋅poly(n,ℓ,m)g(p)·poly(n, ,m) for a computable function g. Since p≤q⋅2κp≤ q· 2^κ, this is of the form f(κ,q)⋅poly(n,ℓ,m)f(κ,q)·poly(n, ,m), and an optimal outcome can be reconstructed in time polynomial in the ILP size.