PaperlayerView exact revision on arXiv

Source-linked AI summary

Proportional Representation in Temporal Voting with Ranked Preferences

Noam Hazon, Leora Schmerler, Nicholas Teh

arXiv:2609.30555v1cs.GTcs.AI

TL;DR

The paper asks how to guarantee proportional representation when rankings change and acceptable cutoffs may vary across voters or rounds. It defines temporal ranking-based axioms and studies their attainability and verification under different information and preference conditions, finding that cutoff flexibility limits exact guarantees while restrictions recover some.

  • Problem

    Ranked preferences do not specify which candidates each voter finds acceptable, and a suitable cutoff may vary by round or voter, complicating proportional representation over time.

    Source: §1 · p. 1

  • Method

    The paper defines temporal JR, PJR, EJR, and PSC variants for different cutoff and agreement patterns, then analyzes their guarantees under offline, semi-online, and online information.

    Source: §1 · p. 2

  • Results

    Fixed-rank-PJR is attainable offline, rank-wPJR semi-online, and weak PSC online; individual cutoffs preclude exact JR/PJR guarantees, but serial dictatorship achieves the optimal additive PJR loss.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    Preference restrictions recover exact weak all-rank proportionality or online solid-coalition guarantees, while verification tractability depends on profile structure and axiom strength.

    Source: §8 · p. 41

    The fixed-rank-PJR construction considers all voter groups and runs in O(2^n · poly(n, m, |T|)); whether a polynomial-time guarantee exists remains open.

    Source: §4.1 · p. 10

Abstract

from arXiv · show

We study proportional representation in temporal voting, where one candidate is selected in each round. While prior work has focused on approval ballots, we consider ranked preferences, which may change over time. A natural approach treats each voter's top candidates as approved, but the right cutoff may differ across voters and rounds. We therefore require proportionality to hold for every admissible choice of cutoffs, whether fixed and common, common but varying across rounds, or set individually for each voter in each round. Combining these interpretations with temporal versions of justified representation (JR), proportional JR (PJR), extended JR (EJR), and proportionality for solid coalitions (PSC) gives us a hierarchy of axioms. We ask which of these axioms can be guaranteed, and with how much knowledge of the future. Unlike with approval ballots, no version of EJR can be guaranteed, and for the other axioms, flexibility in the cutoffs comes at a price. With a fixed common cutoff, JR, PJR, and PSC can be guaranteed, but only by rules that see all preferences in advance. Once the cutoff may vary across rounds, even such rules cannot guarantee JR or PSC for groups that agree in only some rounds. For groups that agree in every round, however, knowing only the number of rounds suffices for PJR in polynomial time, and PSC needs no knowledge of the future at all. Under individual cutoffs, no version of JR or PJR can be guaranteed, yet a rule as simple as serial dictatorship achieves PJR up to an additive loss that no rule can improve on, however much it knows. Natural preference restrictions restore exact guarantees. Finally, we show that checking our axioms is often coNP-complete; but perhaps surprisingly, a stronger axiom can be easier to check.

1 Introduction

The paper adapts temporal proportional representation to changing rankings, where acceptable candidates depend on cutoffs that may be shared or vary across voters and rounds. It studies which guarantees hold under different agreement patterns, preference restrictions, and levels of advance information.

1.1 Our Results

  • The axioms distinguish cutoff flexibility, whether groups must agree in every round, and whether representation means JR, PJR, EJR, or PSC.With three candidates, fixed-rank-wEJR can be unattainable; with two candidates and complete rankings, fixed-rank-wEJR and rank-wEJR coincide with their wPJR counterparts.Source: §1.1 · p. 2
  • Fixed-rank-PJR is attainable offline, rank-wPJR semi-online, and weak PSC online, while rank-JR and rank-PSC can fail even offline.For groups agreeing in only some rounds, no semi-online rule guarantees fixed-rank-JR or fixed-rank-PSC; under individual cutoffs, serial dictatorship attains the optimal additive PJR loss.Source: §1.1 · p. 2
  • With few first choices, a polynomial-time semi-online rule achieves the smallest additive loss depending only on their number; three choices suffice for exact all-rank-PJR, but four can make it unattainable.An online rule also gives interval guarantees: zero loss with two first choices and an optimal one-round loss with three.Source: §1.1 · p. 2
  • Single-peaked and single-crossing preferences allow any number of first choices but support exact all-rank-wPJR only for groups agreeing in every round.A common single-crossing order also permits polynomial-time online rank-wPSC; online all-rank-wPJR has an optimal additive loss of logarithmic order in the number of voters.Source: §1.1 · p. 3
  • Verification is often coNP-complete, but strengthening an axiom can make checking easier.On three-candidate Euclidean profiles, weak JR and PJR verification is polynomial for fixed-rank and all-rank versions but coNP-complete for rank versions.Source: §1.1 · p. 3
  • For truncated ballots, list-length restrictions extend the polynomial-time common-order rule, while verification of weak all-rank axioms can still be coNP-complete.The paper also classifies verification by ballot lengths and omitted candidates.Source: §1.1 · p. 3

1.2 Related Work

  • The framework extends temporal approval-based proportionality to rankings and flexible cutoffs, building on prior cohesive and solid-coalition rules.It also establishes the optimal finite-horizon loss for all-rank-PJR, extending earlier serial-dictatorship results for approval ballots.Source: §1.2 · pp. 3–4

2 Preliminaries

The preliminaries model repeated elections with strict rankings, one winner per round, and groups whose representation depends on shared approvals. They define temporal JR-family requirements and distinguish rules by how much of the future they know.

2 Preliminaries

  • There are n voters, m candidates, and a finite horizon of rounds, with each voter reporting a strict ranking in every round.A candidate’s rank is its position in that voter’s ordering; rank 1 is the first choice.Source: §2 · p. 4
  • Single-peaked profiles rank candidates lower as they move away from a voter’s peak on an axis; single-crossing profiles order voters so pairwise preferences change at most once.One-dimensional Euclidean profiles rank candidates by distance and are both single-peaked and single-crossing in the corresponding orders.Source: §2 · p. 4
  • An offline rule may use the whole profile; a semi-online rule sees the current and earlier profiles plus the horizon, while an online rule does not know the horizon.Each rule outputs one candidate as winner in every round.Source: §2 · pp. 4–5

2.1 Axioms for Approval Ballots

  • For approval ballots, a group agrees in a round when its members share an approved candidate and is represented when a member approves that round’s winner.The axioms require sufficiently large groups that agree across rounds to receive representation, but differ in how it is counted.Source: §2.1 · p. 5
  • JR requires one represented round, PJR requires representation proportional to group size and agreeing rounds, and EJR requires one member to receive the group’s full entitlement.Weak versions apply these requirements only to groups that agree in every round; the non-weak versions also cover groups agreeing in some rounds.Source: §2.1 · p. 5
  • The default Hare quota gives a group an entitlement of floor(|T||S|/n) rounds, while the stronger Droop condition can give it a larger entitlement.Under Droop, the largest integer entitlement is ceil((|T| + 1)|S|/n) − 1.Source: §2.1 · p. 5

3 Proportionality Axioms and Their Relationships

The section defines temporal proportionality for ranked preferences through alternative cutoff and group-protection rules, then relates the resulting axioms and characterizes all-rank guarantees ordinally.

3 Proportionality Axioms and Their Relationships

  • Temporal proportionality for rankings adapts approval-based axioms and solid-coalition protection to repeated winner selection and preferences that may change between rounds.Proportionality is measured by the rounds in which groups agree and are represented.Source: §3 · p. 5

3.1 Approval-based Axioms

  • A single winner sequence must meet approval-based requirements for every cutoff choice: one common cutoff, a common cutoff per round, or individual voter-round cutoffs.These are the fixed-rank, rank, and all-rank interpretations, respectively.Source: §3.1 · pp. 5–6

3.2 Axioms for Solid Coalitions

  • PSC protects groups ranking a common candidate set above all others; rank-PSC counts representation across all rounds, while PSC has no all-rank version.An all-rank solid group would need to use the same cutoff.Source: §3.2 · p. 6

3.3 Relations among the Axioms

  • All-rank axioms imply rank axioms, which imply fixed-rank axioms; within approval-based families, EJR implies PJR, which implies JR, and each implies its weak version.The corresponding PJR-to-PSC implications hold for rank and fixed-rank versions.Source: §3.3 · p. 6

3.4 Extended Justified Representation

  • No version of EJR is always satisfiable on unrestricted profiles, although with at most two candidates fixed-rank and rank weak EJR coincide with weak PJR.The two-candidate equivalences hold on any fixed round interval and yield online guarantees; all-rank-wEJR can still fail with two voters and two candidates.Source: §3.4 · pp. 7–8

3.5 An Ordinal Interpretation of the All-rank Axioms

  • The minimum representation under all-round agreement equals the number of rounds with Pareto-efficient winners, yielding ordinal characterizations of weak all-rank PJR and JR.Weak all-rank JR requires a Pareto-efficient winning round for every group of size at least n/|T|; all-rank-JR fails exactly when some group has no first-choice-winning round and |S|DW(S) ≥ n. The theorem also gives the largest shortfall over rank matrices without requiring cutoff choices.Source: §3.5 · pp. 8–9

4 Existence and Computability Results

This section examines attainable guarantees and impossibilities under unrestricted rankings, as cutoff flexibility, group agreement across rounds, and the information available to rules vary. It establishes additive all-rank-PJR guarantees and exact existence conditions, and considers weak PSC guarantees and polynomial-time results under stated horizon conditions.

4.1 Groups That Agree in Some Rounds

  • Offline, fixed-rank-PJR can be satisfied simultaneously for all common cutoffs by a two-stage greedy rule that reserves and assigns rounds to groups.The rule processes cutoffs in order, then assigns reserved rounds starting with groups that agree in fewer rounds; whether a polynomial-time guarantee exists is open.Source: §4.1 · pp. 9–10
  • When cutoffs may vary across rounds, rank-JR and rank-PSC can both be unattainable, even on a static one-dimensional Euclidean profile; therefore rank-PJR can fail too.The construction uses groups that agree in at least four of five rounds but are never represented.Source: §4.1 · p. 11
  • Even with a fixed common cutoff, no semi-online rule guarantees fixed-rank-JR or fixed-rank-PSC, even on common-axis single-peaked profiles, and thus none guarantees fixed-rank-PJR.The impossibility follows because preferences in later rounds can make previously unrepresented voters form a new group.Source: §4.1 · p. 11

4.2 Groups That Agree in Every Round

  • With a known horizon, a polynomial-time semi-online rule guarantees rank-wPJR for groups agreeing in every round, using no future preferences.The Method of Equal Shares adaptation charges voters from budgets; a group’s members pay only in rounds that represent it until its entitlement is met.Source: §4.2 · pp. 12–13
  • Without knowing the horizon, no online rule guarantees even fixed-rank-wJR; consequently, none guarantees any of the approval-based axioms.The impossibility compares two horizons with identical preferences in their initial rounds but incompatible representation requirements.Source: §4.2 · p. 13
  • Online rules can guarantee fixed-rank-wPSC or rank-wPSC without a known horizon, using a Solid Coalition Refinement adaptation.For rank-wPSC, the rule considers all rank vectors for rounds so far and selects winners by refining approval sets according to claim priority.Source: §4.2 · pp. 13–14
  • When groups agree in every round, each version of Algorithm 3 satisfies its corresponding weak PSC axiom with the Droop size condition.With a known horizon, Algorithm 2 satisfies rank-wPJR—and hence rank-wPSC—in polynomial time; its fixed-rank version is polynomial-time as well.Source: §4.2 · p. 15

4.3 Optimal Additive Guarantees

  • For |T|=qn+s, serial dictatorship achieves the optimal all-rank-PJR additive loss ⌊s(n−s)/n⌋ online; no smaller loss works universally, even offline for all-rank-wPJR.Exact all-rank guarantees can fail on some profiles.Source: §4.3 · pp. 16–17, §4.2 · p. 16
  • For fixed n and horizon, universal all-rank-PJR existence holds exactly when |T| mod n is 0, 1, or n−1; all-rank-JR exists exactly when |T|=1 or |T|≥n−1.The characterizations also hold for the corresponding weak axioms, and serial dictatorship suffices in each positive case. The additive loss is independent of q but can grow linearly with n.Source: §4.3 · p. 17

5 Stronger Guarantees under Preference Restrictions

This section examines how preference restrictions shape proportionality guarantees, including exact and approximate PJR or JR outcomes under bounded first choices, single-peaked preferences, and single-crossing profiles. It also considers how guarantees depend on horizon knowledge and whether groups agree throughout the horizon.

5.1 Few First Choices

  • When at most d candidates are ranked first in each round, Algorithm 4 is a polynomial-time semi-online rule: for every group S, the winner is a first choice of some member of S in at least ⌊|S||T|/n⌋−∆d rounds, satisfying all-rank-PJR with additive loss ∆d.No smaller additive loss depending only on d suffices across all voter counts and horizons, even for an offline rule and all-rank-wPJR.Source: §5.1 · p. 18
  • For all-rank-JR, a profile sequence exists exactly when |T|(1−1/d)^|T|<1; one polynomial-time online rule achieves all positive cases without knowing d or |T|.For d≤3 the condition holds at every horizon; for d=4 it holds when |T|=1 or |T|≥7.Source: §5.1 · pp. 19–20

5.1.1 Proportionality on Every Time Interval

  • On every contiguous interval, a polynomial-time online rule guarantees all-rank-PJR with additive loss d−2, which is optimal up to Θ(d) in the worst case.For two first choices the loss is zero; for three, loss one is optimal, even against an offline rule on a static one-dimensional Euclidean profile.Source: §5.1.1 · p. 20
  • For complete profiles with at most two candidates, a polynomial-time online rule satisfies rank-wEJR and fixed-rank-wEJR on every interval; universally, these exist iff |T|=1 or m≤2, while all-rank-wEJR exists iff |T|=1 or m=1.The universal existence characterizations allow voter counts to vary; the interval rule applies to complete profiles with at most two candidates.Source: §5.1.1 · p. 21

5.2 Single-peaked and Single-crossing Profiles

  • With a known horizon, a polynomial-time semi-online rule guarantees all-rank-wPJR on single-peaked or single-crossing profiles, even when axes or voter orders vary by round.It represents each group in at least ⌈(|T| + 1)|S|/n⌉−1 rounds, under the stronger Droop size condition |S| > ℓn/(|T| + 1).Source: §5.2 · p. 22
  • A common single-crossing voter order permits rank-wPSC with the Droop size condition via a polynomial-time online rule.The rule uses intervals of the voter order and keeps the smallest common approval set for each interval in each round.Source: §5.2 · p. 22
  • No online rule always satisfies all-rank-wJR on static strict one-dimensional Euclidean profiles, even with 15 voters, 15 candidates, a common candidate axis, and a common single-crossing voter order.The impossibility arises from not knowing when decisions will end, even though preferences remain unchanged across the possible horizons.Source: §5.2 · p. 23
  • For randomized online rules, some horizon among 3, 4, and 5 has violation probability at least 1/3 for all-rank-wJR on the same profile.Using identical random choices across the three horizons, the violation probabilities sum to at least one.Source: §5.2 · p. 23
  • Θ(log n) is the optimal worst-case additive loss for online all-rank-wPJR on a common single-crossing order; the upper bound is 2⌈log2 n⌉, and no deterministic rule achieves o(log n).The lower bound holds even for static strict one-dimensional Euclidean profiles with m = n.Source: §5.2 · pp. 23–24
  • On a common single-crossing order, rank-wPSC is exact online and all-rank-wPJR is exact semi-online, but online all-rank-wPJR incurs logarithmic loss; Theorem 5.4 needs no common voter order.Theorem 5.4 applies to every time interval, with loss depending on the number of first choices rather than the number of voters.Source: §5.2 · p. 24

6 Verifying Proportionality

This section studies the verification complexity of proportionality axioms for proposed sequences on complete rankings, across cutoff models and preference restrictions. It covers cases with polynomial-time verification and coNP-completeness, as well as verification and existence testing for all-rank EJR and wEJR on complete two-candidate profiles.

6.4 Single-crossing Profiles

  • For single-crossing profiles, a common voter order across rounds makes all four all-rank JR and PJR verification problems polynomial, whereas changing orders makes them coNP-complete.The changing-order hardness holds even with three candidates and at most two distinct first choices per round.Source: §6 · p. 25, §6.4 · p. 29

6.1 Fixed Cutoffs

  • For complete rankings, fixed-rank-wPSC is polynomial for any candidate count, while fixed-rank-wJR and wPJR become coNP-complete from four and three candidates, respectively.Three-candidate fixed-rank-wPJR hardness holds even for single-crossing rounds with at most two first choices and a constant winner; the hardness extends to every larger fixed candidate count.Source: §6.1 · pp. 25–26

6.2 Common Cutoffs That Vary across Rounds

  • Rank-wJR, rank-wPJR, and rank-wPSC verification is coNP-complete with three fixed-line Euclidean candidates and a constant winner; with at most two candidates, seven listed rank and all-rank axioms are polynomial.The two-candidate tractability result covers rank-wJR, rank-wPJR, rank-wPSC, all-rank-JR, all-rank-PJR, all-rank-wJR, and all-rank-wPJR.Source: §6.2 · pp. 27–28

6.3 Individual Cutoffs on Single-peaked Profiles

  • On single-peaked profiles, all-rank-wJR and all-rank-wPJR are polynomial with arbitrarily many candidates, while fixed-rank-wJR, wPJR, and wPSC are polynomial for three candidates.For three-candidate single-peaked profiles, weak JR and PJR verification is polynomial for fixed-rank and all-rank versions but coNP-complete for rank versions.Source: §6.3 · pp. 28–29

6.4 Single-crossing Profiles

  • With one common single-crossing voter order, all-rank-JR, all-rank-PJR, all-rank-wJR, and all-rank-wPJR are polynomial-time verifiable in O(n^4 + n^2|T|m) arithmetic operations.The verification algorithm can also recover a violating group.Source: §6.4 · pp. 29–30
  • With round-specific single-crossing orders, verifying all four axioms is coNP-complete even with three candidates, at most two first choices per round, and a constant proposed winner.These profiles still permit constructing an all-rank-PJR sequence, distinguishing construction from verification.Source: §6.4 · pp. 30–31

6.5 Extended Justified Representation with Two Candidates

  • On complete two-candidate profiles, all-rank-EJR and all-rank-wEJR coincide, holding exactly when sorted first-choice win counts satisfy u(s) ≥ floor(|T|s/n) for every s, enabling polynomial verification and profile-specific existence testing.Every satisfying sequence is the first-choice sequence of some voter; existence can be tested among at most n such sequences.Source: §6.5 · p. 32
  • This profile-specific existence test is not a universal guarantee: individual-cutoff EJR axioms can still be impossible to satisfy, even with two candidates.The two-candidate result complements rather than contradicts the impossibility example.Source: §6.5 · pp. 31–32

7 Truncated Ballots

This section studies how truncated ballots affect proportionality guarantees, algorithms, and verification complexity. It also identifies ballot and profile restrictions under which verification or rank-wPSC remains tractable.

7.1 Algorithms with Truncated Ballots

  • Truncation preserves guarantees for GCR, general SCR, first-choice and ordered-budget rules; Algorithms 1 and 3 retain fixed-rank-PJR and fixed-rank-wPSC/rank-wPSC, respectively.Both SCR versions also retain the Droop guarantee; SCR claims include only voters whose lists are long enough for the relevant cutoff.Source: §7 · p. 32, §7.1 · p. 33

7 Truncated Ballots

  • Checking all-rank-wJR or all-rank-wPJR can become coNP-complete even when each ballot omits only two candidates.Truncation changes the characterization of these axioms and the complexity of verification.Source: §7 · p. 32

7.1 Algorithms with Truncated Ballots

  • With a common single-crossing voter order, a polynomial-time online rule satisfies rank-wPSC under Hare or Droop, and both quotas are polynomial-time verifiable.The rule requires the voter order and compatible single-crossing completions, but not the unreported parts of those completions or future rankings.Source: §7.1 · p. 34
  • For arbitrary nonempty truncated ballots, fixed-rank-wPSC is polynomial-time verifiable under either Hare or Droop size conditions.The verification result needs no restriction on preferences.Source: §7.1 · p. 35
  • Modified MES achieves rank-wPJR, or the Droop size condition with adjusted initial budgets, while first-choice rules retain JR and PJR but not the cited EJR conclusion.The no-affordable-candidate case selects a voter’s first choice without deductions; the EJR conclusion relying on complete two-candidate ballots is not extended.Source: §7.1 · p. 35

7.2 A Characterization for All-rank Verification

  • A group can agree in every round under some rank matrix exactly when its members have a common listed candidate in every round.Unlisted candidates are unacceptable, so truncation removes the complete-ranking option of agreeing by setting every cutoff to the full candidate count.Source: §7.2 · pp. 35–36
  • Weak-axiom violations have polynomially checkable certificates, placing all verification problems considered here in coNP.Source: §7.2 · p. 36

7.3 When Does Truncation Make Verification Hard?

  • With two candidates, all-rank-wJR takes O(n|T|), while all-rank-wPJR is polynomial with at most one length-one ballot per round but coNP-complete with two.The hardness holds even when other ballots are complete, the winner is constant, and strict Euclidean completions use fixed candidate positions.Source: §7.3 · p. 36
  • For single-peaked ballots with m ≥3, omitting at most one candidate preserves polynomial verification, whereas two omissions can make both weak-axiom checks coNP-complete.Hardness holds even with equal list lengths; for fixed ballot length, it holds when there are two more candidates than the ballot length.Source: §7.3 · pp. 37, 39
  • Length-one ballots permit polynomial verification of both weak axioms, but length at most two makes both coNP-complete, even under a common single-crossing voter order.The hardness result uses three candidates at fixed Euclidean positions and a constant proposed winner.Source: §7.3 · p. 39

7.4 Verification with Few Deeply Truncated Ballot Types

  • With θ distinct deeply truncated ballot types, single-peaked profiles admit all-rank-wJR and all-rank-wPJR verification in 2^θ poly(n,m,|T|) time using at most 2^θn minimum-cut computations.The algorithm also returns a violating group and corresponding rank matrix when the proposed sequence violates the axiom.Source: §7.4 · pp. 39–40
  • With θ deeply truncated ballot types, all-rank-wJR and all-rank-wPJR can be verified in 2^θ poly(n, m, |T|) time using minimum cuts.The construction checks at most n choices of v for each of 2^θ sets Q; each network has O(n + |T|) nodes and O(n|T|) arcs.Source: §7.4 · pp. 40–41
  • Neither all-rank-wJR nor all-rank-wPJR verification admits a 2^o(θ) poly(n, m, |T|) algorithm under ETH, even with three candidates.The lower bound follows from a reduction from Independent Set.Source: §7.4 · p. 41
  • All-rank-wJR and all-rank-wPJR verification can be coNP-complete with three candidates and Euclidean completions, for nearly complete or very short ballots.By contrast, single-peaked profiles with few deeply truncated types admit efficient verification through the minimum-cut approach.Source: §7.4 · p. 41
  • Under truncation, GCR, MES, general SCR, and the first-choice and ordered budget rules retain their respective guarantees; a common single-crossing order enables polynomial-time online rank-wPSC and verification.Source: §7.4 · p. 41

8 Discussion

The discussion organizes guarantees by cutoff, group, and information choices, then highlights how preference restrictions affect those guarantees and how verification differs from construction.

8 Discussion

  • On unrestricted rankings, fixed-rank-PJR is attainable offline, rank-wPJR semi-online, and weak PSC online; optimal additive loss describes what remains achievable for all-rank-PJR.The discussion also distinguishes fixed-rank-wEJR and rank-wEJR, which can hold on every interval with two candidates, from unattainable all-rank-wEJR under individual cutoffs.Source: §8 · p. 41
  • Few first choices protect groups that agree in only some rounds, while single-peaked and single-crossing preferences yield exact weak all-rank proportionality.A common single-crossing order permits efficient online rank-wPSC, including with truncated ballots; horizon knowledge can still be necessary on static Euclidean profiles.Source: §8 · p. 41
  • On three-candidate Euclidean profiles, weak JR and PJR verification is easy for fixed-rank and all-rank versions but hard for rank versions.A common single-crossing order makes weak and non-weak all-rank verification polynomial.Source: §8 · p. 41
  • Changing orders can make verification hard even when an exact all-rank-PJR sequence is easy to construct, and truncation can add verification difficulty without removing constructive guarantees.These contrasts show that verification complexity does not simply track the existence of a rule with guarantees.Source: §8 · p. 42
  • Open questions include polynomial-time offline fixed-rank-PJR, online rank-wPSC without a common single-crossing order, and exact all-rank-PJR under three first choices.For more than three first choices, the optimal additive loss on time intervals remains between Δd = d/e + O(1) and d − 2.Source: §8 · p. 42

A.1 Proof of Lemma 3.5

The proof establishes that Pareto-efficient winners represent an agreeing group, and constructs rankings that make representation occur exactly in those rounds.

A.1 Proof of Lemma 3.5

  • If a group agrees in round j and the selected winner is Pareto efficient for it, the group is represented in that round under every ranking matrix.Otherwise, every group member would approve a candidate they unanimously prefer to the winner, contradicting Pareto efficiency.Source: §A.1 · p. 45
  • Together, the universal implication and constructed profile establish the lemma’s exact relationship between Pareto efficiency and representation for an always-agreeing group.The construction leaves rankings outside the group arbitrary.Source: §A.1 · p. 45
  • The proof constructs a rank matrix where the group agrees in every round but is represented only when the selected winner is Pareto efficient for it.In a non-efficient round, all group members approve a candidate they prefer to the selected winner and none approves that winner.Source: §A.1 · p. 45

A.2 Proof of Theorem 3.6

The proof reduces all-rank violations to per-round choices of cutoffs, then characterizes when a group can violate PJR or JR using dominated and first-choice rounds.

A.2 Proof of Theorem 3.6

  • Independent round-by-round cutoff choices maximize the violation using Pareto-dominated rounds, first-choice-winner rounds, and otherwise zero-contribution rounds.A dominated winner can contribute |S|/n; a first-choice winner contributes |S|/n − 1, while the remaining case contributes at most zero.Source: §A.2 · p. 45
  • All-rank-PJR fails exactly when |S|DW(S) − (n − |S|)FW(S) ≥ n.Here DW(S) and FW(S) count Pareto-dominated and first-choice-winner rounds, respectively.Source: §A.2 · p. 45
  • All-rank-JR fails exactly when FW(S) = 0 and |S|DW(S) ≥ n.Zero representation is possible only if no round's winner is a member's first choice; then only dominated rounds can provide agreement without representation.Source: §A.2 · p. 45

B.1 Proof of Theorem 4.1

The proof establishes fixed-rank-PJR by reserving enough rounds for group-cutoff pairs and showing those reservations can be assigned without overlap. An invariant bounds total demand, yielding representation for every group and cutoff.

B.1 Proof of Theorem 4.1

  • Stage 1 maintains that the sum of g-values for groups within size threshold k is at most k|V′|/n for every voter subset V′.The induction separates groups disjoint from the newly selected group from intersecting groups, bounding their contributions using the prior invariant and remaining demand.Source: §B.1 · pp. 45–46
  • Every positive reservation g(S,r) can be assigned to that many distinct unassigned rounds where S agrees under A(r).The proof first shows all reserved rounds can be assigned; the invariant and demand-maximizing selection ensure enough rounds remain for each pair.Source: §B.1 · p. 46
  • For every cutoff r and group S, the algorithm represents S in at least δ(S,r) rounds, proving fixed-rank-PJR.The assigned rounds are disjoint across pairs, and each round assigned to a pair with cutoff t ≤ r represents S under A(r).Source: §B.1 · p. 47

C A Stronger Size Condition with Three First Choices

With at most three first-ranked candidates per round, Algorithm 4 yields a stronger group-size guarantee using initial voter budgets of (|T| + 1/4)/n. The extra quarter is optimal, even offline.

C A Stronger Size Condition with Three First Choices

  • A group with more than ℓn/(|T| + 1/4) members has a member’s first choice selected in at least ℓ rounds.The guarantee assumes at most three candidates are ranked first in each round and Algorithm 4 starts each voter with (|T| + 1/4)/n units.Source: C A Stronger Size Condition with Three… · p. 47
  • The proof bounds the total remaining budget and shows each group pays at least (|T| + 1/4)|S|/n − 1 across first-choice wins.Each such round contributes at most one unit toward the group's payment, yielding the stated ceiling guarantee.Source: C A Stronger Size Condition with Three… · p. 47
  • No constant greater than 1/4 can replace 1/4 uniformly over voter counts and horizons, even for offline rules and groups agreeing every round.For d = 3, |T| = 2, and n = 9, every sequence leaves a four-voter group unrepresented despite its agreement in every round under some rank matrix.Source: C A Stronger Size Condition with Three… · p. 47

Related papers

Loading 2609.30555v1…