PaperlayerView exact revision on arXiv

Source-linked AI summary

Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees

Georgios Papasotiropoulos

arXiv:2609.35331v1cs.GTcs.AI

TL;DR

RevSeqPAV’s fairness and optimization guarantees are less understood than those of its forward counterpart, despite the rule’s history and practical use. The paper analyzes both dimensions, finding severe unrestricted worst cases alongside meaningful guarantees in restricted settings.

  • Problem

    RevSeqPAV’s proportional representation and ability to approximate the maximum PAV score are less understood than SeqPAV’s, despite its historical prominence and practical use.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes RevSeqPAV’s proportionality guarantees and its approximation of the maximum PAV score, considering both unrestricted elections and restricted regimes.

    Source: §1.1 · p. 2

  • Results

    In unrestricted instances, RevSeqPAV can have proportionality degree zero and no positive constant PAV-score approximation, while it satisfies EJR for r ≤ 2 and provides stronger guarantees in restricted regimes.

    Source: §5 · p. 9

  • Takeaways & Limitations

    RevSeqPAV’s guarantees depend on the setting: it has worst-case shortcomings, but offers fairness and optimization guarantees when few candidates are deleted or ballots are bounded.

    Source: §5 · p. 9

    The EJR guarantee for at most two deletions is tight and cannot be extended to larger numbers of deletions.

    Source: §3 · p. 4

Abstract

from arXiv · show

We study the Reverse Sequential Proportional Approval Voting Rule (RevSeqPAV) in approval-based committee elections. Despite its historical prominence and practical use, its properties and guarantees are much less understood than those of Sequential PAV. We analyze it along two dimensions: proportional representation (measured by Extended Justified Representation, its approximations, and proportionality degree) and approximation of the maximum PAV score of instances. We first establish strong negative results for general, unrestricted election instances and then identify settings in which the rule provides meaningful fairness and optimization guarantees.

1 Introduction

RevSeqPAV is a historically established elimination-based alternative to Sequential PAV, but its fairness and optimization guarantees have received less study despite practical use. This section sets out the paper’s worst-case findings and the restricted settings in which the rule offers guarantees.

1 Introduction

  • The harmonic PAV objective supports proportional representation, but its optimization is NP-hard; RevSeqPAV remains much less studied than SeqPAV despite Thiele’s preference for elimination.RevSeqPAV is used by LiquidFeedback as “Harmonic Weighting,” and a stronger proportionality claim made to justify its use was later disproved.Source: §1 · pp. 1–2

1.1 Contributions

  • RevSeqPAV has proportionality degree zero at every ℓ, with some ℓ-cohesive group receiving no approved winner; its proportional-rankings measure also has worst-case guarantee zero.The result resolves an open question about the rule’s proportionality degree.Source: §1.1 · p. 2
  • RevSeqPAV satisfies EJR when r = m − k ≤ 2, but for every r ≥ 3 there is an instance where it violates EJR.The authors frame the positive result as identifying a class of elections where RevSeqPAV always satisfies EJR; SeqPAV may fail even JR for r = 1 or 2.Source: §1.1 · p. 2
  • RevSeqPAV always satisfies (1/r)-EJR, and sufficiently large groups with common preferences receive the representation level prescribed by the axiom.This approximation guarantee applies even where full EJR fails.Source: §1.1 · p. 2
  • Without restrictions, RevSeqPAV can return a committee whose PAV score is an arbitrarily small fraction of the optimum.This answers negatively whether the rule has an approximation factor comparable to SeqPAV’s.Source: §1.1 · p. 2
  • For fixed r, the PAV-score approximation bound converges to 1 as k grows; if every voter approves at most b candidates, the bound is 1/b and tight.The first regime concerns committees that are a large fraction of the candidates.Source: §1.1 · p. 2

2 Preliminaries

The preliminaries define the election and PAV objective, then specify RevSeqPAV’s deletion rule and the fairness and approximation measures used to analyze it.

2 Preliminaries

  • An election consists of voters, candidates, approval ballots, and a desired committee size k; r = m − k counts the candidates that must be deleted, and b is the largest ballot size.A feasible committee contains exactly k candidates.Source: §2 · p. 3
  • PAV scores a candidate set by summing voters’ harmonic scores based on how many approved candidates they receive; PAV selects a feasible committee maximizing that score.The maximum feasible PAV score is denoted OPT_k.Source: §2 · p. 3
  • RevSeqPAV repeatedly deletes the candidate with the smallest immediate marginal PAV loss, where an approving voter with t approved candidates remaining contributes 1/t to that candidate’s loss.The process starts with all candidates and stops when k remain.Source: §2 · p. 3
  • EJR requires each ℓ-cohesive group to contain a voter with at least ℓ approved winners; JR is its ℓ = 1 case, and α-EJR relaxes the satisfaction threshold.The group must be sufficiently large and share at least ℓ commonly approved candidates.Source: §2 · p. 3
  • Proportionality degree measures guaranteed average satisfaction for ℓ-cohesive groups, while a PAV approximation factor compares a rule’s score with OPT_k.The approximation guarantee requires PAV(R(E)) ≥ α OPT_k for every election.Source: §2 · p. 3

3 Proportionality Guarantees of RevSeqPAV

RevSeqPAV satisfies EJR when at most two candidates are deleted, but for every r ≥ 3 some election makes it violate EJR. The section also establishes a (1/r)-EJR guarantee and zero worst-case proportionality degree and ranking proportionality quality.

EJR guarantees

  • EJR is guaranteed when r ≤ 2, but for every r ≥ 3 some election violates it.In the counterexample, alternatives that initially make a commonly approved candidate seem dispensable are themselves deleted, leaving the cohesive group underrepresented.Source: §3 · pp. 4–5

Approximate EJR

  • RevSeqPAV satisfies (1/r)-EJR, and a further threshold result guarantees EJR to sufficiently high-demand cohesive groups even when EJR fails overall.The threshold condition is stated in terms of the group's cohesion level.Source: §3 · p. 6

Proportionality degree

  • For every integer ℓ ≥ 1, RevSeqPAV's proportionality degree is exactly 0.The proof constructs an ℓ-cohesive group whose members receive no approved winner.Source: §3 · p. 6

Ranking proportionality

  • The worst-case proportionality quality of rankings produced by RevSeqPAV is 0.The top-k prefix of its ranking is the committee returned for size k, and the construction yields a group with positive justifiable demand but zero average satisfaction in that prefix.Source: §3 · pp. 6–7

4 Approximation Guarantees of RevSeqPAV

RevSeqPAV has no positive worst-case approximation ratio for PAV score, but earns guarantees when few candidates are deleted or voter ballots are bounded in size. The few-deletions bound approaches optimality as the committee size grows for fixed deletions.

  • 0 is RevSeqPAV’s worst-case approximation ratio for PAV score, even when the committee size is fixed at k = 1.An instance deletes a PAV-optimal candidate first, and the resulting ratio tends to zero.Source: §4 · p. 7
  • PAV(W) ≥ k/(m−1) OPTk when RevSeqPAV returns committee W, a bound that approaches 1 for fixed deletions as k grows.The proof starts from the first deletion, which maximizes PAV score among sets of size m−1, then bounds each later deletion’s loss by a 1/s fraction of the current score.Source: §4 · pp. 7–8
  • When every voter approves at most b candidates, RevSeqPAV guarantees PAV(W) ≥ 1/b OPTk.The bound applies independently of the number of candidates deleted.Source: §4 · p. 8
  • For every b ≥ 2 and ε > 0, an election exists with PAV(W) < (1/b + ε) OPT1, making the bounded-ballot guarantee tight.The construction causes the rule to delete the optimal singleton candidate first; as the construction parameter grows, the score ratio approaches 1/b.Source: §4 · p. 9

5 Conclusions

RevSeqPAV performs poorly on unrestricted adversarial instances, but has stronger guarantees in restricted settings. The paper also identifies open questions about proportionality under bounded ballot size, other positive-proportionality domains, agreement with SeqPAV, and empirical comparisons.

  • In the worst case, RevSeqPAV may fail EJR, have proportionality degree 0, and provide no positive constant approximation of optimal PAV score.Source: §5 · p. 9
  • For r ≤ 2, RevSeqPAV satisfies EJR; it also provides (1/r)-EJR and EJR-level representation to sufficiently large cohesive groups.Source: §5 · p. 9
  • RevSeqPAV approximates optimal PAV score by k/(m−1) when k is close to m, or by 1/b when each voter approves at most b candidates; the latter bound is tight.Source: §5 · p. 9
  • Whether bounded ballot size improves proportionality, which restrictions yield positive proportionality degree, when SeqPAV and RevSeqPAV coincide or are optimal, and how they compare empirically remain open questions.Source: §5 · p. 9
Loading 2609.35331v1…