Source-linked AI summary
Full Justified Representation in Temporal Voting: Efficient Computation and Verification
Nicholas Teh
TL;DR
Temporal FJR outcomes allow group members with partially shared preferences to be represented across rounds, but polynomial-time computation and verification for FJR remained open. The paper introduces temporal FJR+, supplies polynomial-time algorithms for it, and establishes its relationship to existing representation guarantees.
Problem
Whether temporal FJR, which permits different group members to be satisfied by different choices, could be computed and verified in polynomial time remained open.
Source: §1 · p. 2Method
The paper defines temporal FJR+ and develops a threshold-based verifier and a modified local-search PAV algorithm that penalizes minimum voter satisfaction.
Source: §1 · p. 2, §4 · p. 7, §5 · pp. 8–9Results
Temporal FJR+ is strictly stronger than FJR and EJR+ combined, matches lower quota on static party-list preferences, and has polynomial-time computation and verification.
Source: §1 · p. 2, §3.1 · p. 6, §3.2 · p. 7Takeaways & Limitations
The verifier can assess any proposed outcome regardless of how it was obtained, leaving room for other voting rules satisfying FJR+.
Source: §6 · p. 13The polynomial-time computation guarantee covers FJR+; whether the requirement in (2) can be attained in polynomial time remains open.
Source: §5.3 · pp. 12–13
Abstract
from arXiv · showhide
In temporal voting, a fixed set of voters makes a collective decision in each of several rounds, and proportionality requires that groups with shared interests be represented across these decisions. Full justified representation (FJR) is among the strongest proportionality axioms known to be satisfiable in this setting, since it allows different members of a group to be satisfied by different selected candidates. However, whether an FJR outcome can be computed in polynomial time has remained open. We resolve this question by introducing temporal FJR+, a strengthening of both FJR and extended justified representation+ (EJR+) that can be computed and verified in polynomial time. The axiom measures a group's agreement in each round by the largest number of its members who approve a common candidate, and requires some member to attain the integer part of the group's proportional share of its best attainable average satisfaction, with a shortfall of at most one unit when this share is an integer. We show that verification reduces to counting approvals among the voters below each satisfaction threshold. For computation, we observe that local search for Proportional Approval Voting (PAV) can stop at an outcome violating FJR. Somewhat counterintuitively, the remedy is to subtract a small multiple of the minimum voter satisfaction from the PAV score: every FJR+ violation then admits a single-round change whose improvement guarantees polynomial running time. We further show that temporal FJR+ is strictly stronger than FJR and EJR+ combined, and coincides with lower quota on party-list preferences. Finally, temporal FJR+ and multiwinner FJR+ are incomparable in general, but coincide when approvals are static and each candidate-round pair is treated as a separate candidate.
1 Introduction
Temporal voting asks how to represent groups across sequential decisions, including when their members agree only partially. The paper introduces temporal FJR+ and gives polynomial-time methods for computing and verifying it.
1 Introduction
- FJR allows different members of a group to be satisfied by different choices, but its temporal version had no known polynomial-time computation or verification method.Its benchmark reflects group size and opportunities for agreement across rounds, while preventing groups from reserving only their most favourable rounds.Source: §1 · p. 2
1.1 Our Contributions
- Temporal FJR+ implies both FJR and EJR+, is strictly stronger than them combined, and on static party-list preferences is equivalent to lower quota.Under lower quota, each party wins at least the integer part of its proportional share of the rounds.Source: §1 · p. 2, §1.1 · p. 2
- Verification is polynomial-time because, at each satisfaction threshold, it suffices to inspect the group of all voters below that threshold and count approvals.A failed check identifies an underrepresented group.Source: §1.1 · p. 2
- Modified local-search PAV subtracts a small multiple of minimum voter satisfaction, so every FJR+ violation admits a sufficiently large improving single-round change.Ordinary local search can stop at an outcome that violates FJR; the perturbation avoids this obstruction and ensures polynomial running time.Source: §1.1 · p. 2
- For n voters, m candidates, and ℓ rounds, verification takes O((n + ℓ)mℓ) time and computation takes O(n^2mℓ^5 log(ℓ + 1)) time.Both results allow empty approval ballots and require no divisibility assumptions.Source: §1.1 · p. 2
1.2 Related Work
- Related work includes temporal representation axioms and public-decision models; multiwinner FJR+ measures agreement differently, and its algorithms do not directly produce valid temporal outcomes.For temporal JR, PJR, and EJR, verification has been shown coNP-complete [Elkind et al., 2025c].Source: §1.2 · p. 3
2 Preliminaries
The preliminaries define temporal elections and two representation axioms. They distinguish round-by-round agreement from the group-wide satisfaction benchmark used by FJR.
2 Preliminaries
- A temporal election has a fixed electorate, approval sets that may vary by round, and an outcome selecting one candidate in each round; voter satisfaction counts approved selections.The same candidate may be selected in multiple rounds, and approval ballots may be empty.Source: §2 · p. 3
- A group’s agreement in a round is the maximum number of its members approving a common candidate, and the agreeing voters may differ across rounds.A group is (σ, τ)-cohesive when its agreement count is at least σ in at least τ rounds.Source: §2 · p. 3
- EJR+ requires a candidate approved by all members of a cohesive group in a round where such a candidate exists, when every member remains below the justified satisfaction level.This condition applies in each round meeting the stated criterion.Source: §2 · p. 4
- FJR benchmarks a group by what it can guarantee to its least-satisfied member across every subset of its proportional share of specified rounds.The group can choose candidates separately for each subset, but cannot reserve only the rounds most favourable to it; an outcome must let some group member reach the benchmark.Source: §2 · p. 4
3 Full Justified Representation +
FJR+ measures a group’s entitlement using its total best attainable satisfaction across rounds and requires representation for at least one member. It preserves FJR and EJR+ guarantees, strengthens them jointly, and matches lower quota on party-list preferences.
3 Full Justified Representation +
- FJR+ uses the group’s total attainable satisfaction across all rounds to set a proportional target for at least one member, rather than requiring simultaneous attainment across proportional-size subsets.Its round agreement count can vary by round, including changes in both the maximizing candidate and the voters approving it.Source: §3 · p. 4
- When the proportional average is not an integer, FJR+ imposes the same target as the earlier requirement; at a positive integer target β, it guarantees at least β − 1, with some cases requiring β.The difference is at most one unit and occurs only at exact equality.Source: §3 · p. 5
3.1 Relation to FJR and EJR+
- Every FJR+ outcome satisfies both FJR and EJR+, while FJR+ is strictly stronger than the two axioms combined.The two-voter, three-round example shows condition (iii) covers an equality case with differing round-agreement counts that conditions (i) and (ii) miss.Source: §3.1 · pp. 5–7
- The separating outcome in the example is Pareto efficient, so the strict separation persists even for a Pareto-efficient outcome.Preserving the fifth voter’s satisfaction requires selecting candidate c in every round, fixing the outcome.Source: §3.1 · p. 7
3.2 Party-List Preferences
- On party-list preferences, an outcome satisfies FJR+ exactly when each party wins at least the integer part of its proportional share of the rounds.The parties’ agreement counts are the same in every round.Source: §3.2 · p. 7
4 Polynomial-Time Verification
Although direct verification would inspect exponentially many groups, it suffices to check the voters below each satisfaction threshold. The resulting test is exact and runs in O((n + ℓ)mℓ) time.
4 Polynomial-Time Verification
- Any group violating FJR+ at a satisfaction level is contained in Uβ, the set of all voters below that level, which also violates it.Enlarging a group cannot decrease its round agreement counts or destroy cohesiveness; a condition (iii) violation requires Uβ = N.Source: §4 · p. 7
- O((n + ℓ)mℓ) time suffices to verify FJR+ by checking the aggregate round agreement counts of voters below each satisfaction threshold.For each threshold β, the test requires the total to be at most nβ, with equality allowed only when Uβ ≠ N and its positive round counts are not all equal.Source: §4 · p. 7
- The verifier needs only voter satisfaction and approval counts, and a failed check identifies the underrepresented group Uβ and its required level.For nβ = 4 and Uβ ≠ N, round counts (2, 2, 0, 0) violate FJR+, whereas (2, 1, 1, 0) pass.Source: §4 · p. 8
5 Polynomial-Time Computation
Modified ε-lsPAV subtracts a small multiple of minimum satisfaction from the PAV score, yielding a polynomial-time algorithm that returns an FJR+ outcome. The section proves the guarantee, bounds its running time, and distinguishes it from a stronger requirement whose polynomial-time computation remains open.
5 Polynomial-Time Computation
- Subtracting a small multiple of minimum satisfaction from the PAV score lets local search escape ties where ordinary PAV search can stop at an FJR-violating outcome.Such a tie can occur when a single-round change leaves the PAV score unchanged; accepting a change that lowers minimum satisfaction can resolve it.Source: §5 · p. 8
- Every returned outcome satisfies FJR+, with fewer than 8nℓ^4H_ℓ changes and running time O(n^2mℓ^5 log(ℓ + 1)).The guarantee holds for every initial outcome and every choice among changes exceeding the threshold.Source: §5 · p. 9
5.1 The Rule Satisfies FJR+
- Every FJR+ violation admits a single-round replacement increasing the modified score by at least 1/(4ℓ^4), so the algorithm cannot stop at a violation.At a returned outcome, every replacement improves the score by at most ε, below the violation-improvement bound.Source: §5.1 · pp. 9, 11
5.2 Running Time
- The running time is O(n^2mℓ^5 log(ℓ + 1)); with round-specific candidate sets totaling M, verification takes O((n + ℓ)M) and computation O(n^2Mℓ^4 log(ℓ + 1)).The number of changes is bounded by fewer than 8nℓ^4H_ℓ.Source: §5 · p. 9, §5.2 · p. 12
5.3 Representation at Integer Levels
- A stronger integer-level requirement is always attainable and polynomial-time verifiable, but whether it can be attained in polynomial time remains open.The algorithm’s polynomial-time guarantee covers the integer levels required by FJR and EJR+, not this stronger requirement.Source: §5.3 · pp. 12–13
6 Discussion
The discussion frames FJR+ as compatible with efficient computation and verification, while identifying faster computation and Pareto-efficient outcomes as open concerns. It also records the author’s use of GPT-6 Astra in exploring proof ideas and revising the exposition.
6 Discussion
- The polynomial bound on changes is large, and finding a Pareto-efficient FJR+ outcome in polynomial time remains open.The authors also identify as open how the initial outcome and choice among improving replacements affect changes and voter satisfaction in practice.Source: §6 · p. 13
Declaration of generative AI use
- The author used GPT-6 Astra as a research assistant for exploring proof ideas and revising the exposition, while taking responsibility for the mathematical arguments and conclusions.Source: Declaration of generative AI use · p. 13
A Harmonic Local Optima at Higher Satisfaction Levels
A family of temporal elections shows that PAV local optima can violate FJR at every positive satisfaction level. The modified score detects a single-round move even when ordinary PAV is tied.
A Harmonic Local Optima at Higher Satisfaction Levels
- For every integer k ≥ 1, an election with n = ℓ = 2k + 1 has an outcome giving every voter satisfaction k that violates FJR, although every single-round replacement leaves the PAV score unchanged.Each voter approves exactly one candidate per round.Source: A Harmonic Local Optima at Higher… · p. 16
- Selecting b in every round gives every voter satisfaction k + 1, establishing that the all-a outcome’s uniform satisfaction k falls short of the attainable group level.Source: A Harmonic Local Optima at Higher… · p. 16
- Replacing a by b in any round lowers minimum satisfaction from k to k − 1 while leaving PAV unchanged, so the modified score increases by δ.The increase exceeds ε.Source: A Harmonic Local Optima at Higher… · p. 16
B Comparison with Multiwinner Voting
Temporal FJR+ and multiwinner FJR+ both strengthen familiar representation guarantees and admit polynomial-time computation and verification. Neither implies the other in general, but they coincide under static preferences.
B Comparison with Multiwinner Voting
- Temporal and multiwinner FJR+ are incomparable in general, but coincide when preferences are static.The comparison associates each temporal election with a multiwinner election having the same approvals and voter satisfactions.Source: B Comparison with Multiwinner Voting · p. 16
B.1 The Multiwinner Axiom
This section defines multiwinner FJR+ through weighted voter and candidate assignments, and explains its relationship to FJR and EJR+.
B.1 The Multiwinner Axiom
- The definition permits nonnegative weights on voters and candidates and nonnegative amounts assigned from candidates to voters.Each below-target voter must receive β units per unit of voter weight; elected candidates additionally have a per-voter assignment bound.Source: §B.1 · p. 17
- FJR mw+ rules out weighted assignments that let below-target voters receive their target satisfaction from approved candidates within a proportionate comparison set.Voter weights represent group size, candidate weights bound assignments, and the selected committee remains an ordinary set of candidates.Source: §B.1 · p. 17
- FJR mw+ implies both FJR mw and EJR mw+.An EJR mw+ violation yields a violating assignment because unelected candidates have no upper bound x_ic ≤ z_i.Source: §B.1 · p. 17
B.2 Preserving Approvals and Satisfaction
The candidate-round construction preserves approvals and satisfaction, but its multiwinner feasible choices differ from temporal outcomes; some axiom implications nevertheless transfer.
B.2 Preserving Approvals and Satisfaction
- The construction maps each candidate-round pair to a distinct multiwinner candidate and preserves each voter’s satisfaction exactly.Repeated selections of an original candidate are represented by distinct round-specific copies.Source: §B.2 · p. 17
- Unlike a temporal outcome, a size-ℓ committee may select multiple candidate-round pairs from one round and none from another.This mismatch can prevent a temporal outcome from satisfying multiwinner FJR mw+ in the constructed election.Source: §B.2 · p. 17
- With two voters and two rounds, EJR mw+ can require both voters’ distinct approved candidates even though a temporal outcome can satisfy only one.Both voters approve different candidates in the first round, while both approval sets are empty in the second; therefore a multiwinner existence or computation result alone does not establish the temporal result.Source: §B.2 · p. 18
- If the constructed committee satisfies FJR mw, its temporal outcome satisfies temporal FJR; if it satisfies EJR mw+, the outcome satisfies temporal EJR+.Consequently, multiwinner FJR mw+ implies both temporal FJR and temporal EJR+, but its relationship with temporal FJR+ differs.Source: §B.2 · p. 18
B.3 Incomparability
The paper establishes that temporal FJR+ and multiwinner FJR+ are incomparable, including for Pareto-efficient outcomes with nonempty ballots.
B.3 Incomparability
- Temporal FJR+ and multiwinner FJR+ are incomparable, even when every voter approves exactly one candidate per round and the temporal outcome is Pareto efficient.The examples separate the axioms without empty ballots, Pareto improvements, or temporal FJR+ boundary conditions.Source: §B.3 · pp. 18, 20
- Temporal FJR+ holds for o, but voters 4 and 5 both approve unelected candidate (b, 1), have zero satisfaction, and exceed n/k = 5/3, violating EJR mw+ and thus FJR mw+.Voters 4 and 5 agree only in round one; temporal FJR+ accounts for their lack of agreement later.Source: §B.3 · pp. 18–19
- Multiwinner FJR mw+ can hold while temporal FJR+ fails: the outcome (a, c10, c11) gives every voter satisfaction one, although temporal FJR+ requires someone to reach two.The temporal requirement follows from the example’s h_r(N) total exceeding 2n, while the paper rules out a violating weighted assignment for multiwinner FJR mw+.Source: §B.3 · p. 19
- The multiwinner example’s outcome is Pareto efficient, and the weighted-group calculation rules out a multiwinner FJR mw+ violation despite the temporal shortfall.The paper contrasts temporal FJR+, which uses the electorate’s best attainable average satisfaction, with the multiwinner axiom’s weighted group and proportional comparison set.Source: §B.3 · p. 19
B.4 Static Preferences
Under static preferences, temporal FJR+ is equivalent to multiwinner FJR mw+ when each candidate-round pair is treated as a separate candidate.
B.4 Static Preferences
- For static preferences, an outcome satisfies temporal FJR+ if and only if its constructed committee satisfies FJR mw+, including when an original candidate is selected repeatedly.The equivalence uses a separate candidate for each round.Source: §B.4 · p. 20
- Static preferences make the agreement count for voters below a satisfaction level identical in every round, yielding the condition used to compare the axioms.The proof shows temporal FJR+ rules out a violating weighted assignment, and conversely a temporal violation gives an unelected copy violating EJR mw+ and therefore FJR mw+.Source: §B.4 · p. 20
- The equivalence can fail if the comparison retains the original candidate set, because multiwinner committees cannot repeat candidates while temporal outcomes can.With one voter, two rounds, and approval set {a}, committee {a, b} satisfies FJR mw+ while temporal outcome (a, b) violates temporal FJR+.Source: §B.4 · p. 20