PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Proportional Committees from Violation Feedback

Frank Connor

arXiv:2608.30111v1cs.GT

TL;DR

The paper asks how to learn a proportionally representative committee without receiving the approval profile up front. It uses committee proposals and violation feedback, comparing full-witness with candidate-only information. Rejection bounds depend on k, with exact linear complexity for PJR+ and more varied bounds for EJR+.

  • Problem

    Can a learner find a proportionally representative committee from violations of its proposals rather than eliciting the full approval profile up front?

    Source: §1 · pp. 1–2

  • Method

    The learner proposes committees against a fixed hidden approval profile, and an oracle accepts or returns a violation with full-witness or candidate-only feedback.

    Source: §1 · p. 1, §2.2 · p. 4

  • Results

    PJR+ has rejection complexity k under both feedback models; EJR+ has an O(k^2 log k) full-witness deterministic upper bound and O(k^2 log k) candidate-only randomized expected bound.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The results show a hierarchy of progress: permanent retention for PJR+, observable PAV-potential progress with full EJR+ witnesses, and average potential progress with candidate-only feedback.

    Source: §6 · p. 13

    For EJR+, the bounds leave gaps, and whether the deterministic upper bounds separate by feedback model remains open.

    Source: §1.1 · p. 3, §6 · p. 13

Abstract

from arXiv · show

We study violation-feedback learning of proportionally representative approval-based committees. In each round, a learner proposes a committee of size $k$. An oracle either accepts the proposal or adversarially selects a representation violation with respect to a single fixed hidden approval profile. We compare \emph{full-witness feedback}, which reveals the violation level, an omitted candidate, and the affected voter group, with \emph{candidate-only feedback}, which reveals only that candidate. The target notions are proportional justified representation plus (PJR+) and extended justified representation plus (EJR+). In every setting we study, the number of rejected proposals can be bounded solely in terms of $k$, with no dependence on the numbers of voters and candidates. For PJR+, the optimal deterministic and randomized rejection complexities equal $k$ under both feedback models. For EJR+, the picture is more nuanced. Under full-witness feedback, we prove an $\Omega(k^{3/2})$ deterministic lower bound and give a deterministic polynomial-time algorithm using $O(k^2\log k)$ rejections. Under candidate-only feedback, randomization achieves $O(k^2\log k)$ expected rejections via uniform random deletion, while deterministic exhaustive branching gives a $2^{O(k^2(\log k)^2)}$ rejection bound. Even with full-witness feedback, randomized learners may require $k$ rejections.

1 Introduction

The paper studies whether a learner can find a proportionally representative committee from violations of proposed committees rather than receiving the approval profile up front. It establishes rejection bounds depending only on committee size k, with distinct progress mechanisms and bounds across axioms and feedback models.

1 Introduction

  • Violation-feedback learning replaces upfront approval reporting with committee proposals that reveal candidate support when a representation failure occurs.The learner receives either the violation level, omitted candidate, and witness group, or only the omitted candidate.Source: §1 · pp. 1–2
  • Across the settings studied, rejection bounds depend only on k, not on the numbers of voters or candidates.The paper presents this as surprising because larger elections contain more possible underrepresented groups and omitted candidates.Source: §1 · p. 2

1.1 Our results

  • PJR+ has rejection complexity k under both feedback models, with a matching lower bound even for randomized learners receiving full-witness feedback.The upper bound follows by retaining every candidate returned by the oracle; a packing argument limits the number returned to k.Source: §1.1 · p. 2
  • For EJR+ with full-witness feedback, a deterministic polynomial-time algorithm uses O(k^2 log k) rejections, while a lower bound is Ω(k^3/2).Full-witness responses certify PAV-improving swaps, and sufficiently strong PAV local optimality guarantees EJR+.Source: §1.1 · p. 2
  • For EJR+ with candidate-only feedback, random deletion gives O(k^2 log k) expected rejections, while deterministic exhaustive branching gives a 2^O(k^2(log k)^2) bound.The returned candidate guarantees average PAV improvement across possible deletions, but the learner does not observe the witness group needed to select a good deletion.Source: §1.1 · p. 2

1.2 Related work

  • The approach differs from work on local-improvement feedback for prescribed voting rules: here the oracle returns a group certificate and the learner seeks any committee satisfying the axiom.The paper situates the model in trial-and-error learning [Bei et al., 2013].Source: §1.2 · p. 3

2 The Violation-Feedback Model

The model treats a rejection as an oracle-provided certificate that a proposed committee violates PJR+ or EJR+. The learner repeatedly proposes size-k committees against a fixed hidden profile, while the oracle may choose an available violation adversarially.

2.1 Proportional representation

  • PJR+ violations express a collective shortfall: a sufficiently large group unanimously approves an omitted candidate but collectively approves fewer than ℓ committee members.EJR+ instead requires that every voter in the witness group individually approve fewer than ℓ members of the committee.Source: §2.1 · pp. 3–4
  • A violation is a triple (ℓ, c, S): the level ℓ, omitted candidate c, and underrepresented witness group S.The plus certificates require agreement on the single omitted candidate, not on ℓ common candidates.Source: §2.1 · p. 4

2.2 Feedback model and rejection complexity

  • Each round, the learner proposes a committee; the oracle accepts it or selects an available violation, and the learner sees either the full triple or only c.The approval profile remains fixed and hidden, and the oracle can choose adaptively among available responses.Source: §2.2 · p. 4
  • Rejection complexity counts rejected proposals before the first acceptance, with the randomized quantity taking expectation over the learner’s private randomness.The learner must succeed against every hidden profile and oracle strategy; the model imposes no computational restriction.Source: §2.2 · pp. 4–5

3 Retained-Set Progress

For PJR+, retaining every returned candidate yields a packing-based upper bound of k rejections, matching the deterministic lower bound under both feedback models. This retention rule does not extend to EJR+.

3 Retained-Set Progress

  • Retaining each returned candidate gives at most k rejections under candidate-only PJR+ feedback.Intersecting witness groups collectively approve earlier returned candidates, yielding the packing condition used to bound the number of returns.Source: §3 · pp. 5–6
  • The deterministic PJR+ rejection complexity is exactly k under both feedback models.The retention algorithm gives the upper bound, and a truthful full-witness oracle can force k rejections.Source: §3 · p. 6
  • Permanent retention fails for EJR+ because a new violation can arise after k returned candidates fill the committee.In the two-voter example, the filled committee still admits a level-2 violation returning a candidate that cannot also be retained.Source: §3 · p. 6

4 Observable Potential Progress

With full-witness feedback, the learner records revealed approvals and uses PAV-improving swaps to bound rejections; a support-size construction gives a superlinear deterministic lower bound.

4 Observable Potential Progress

  • Full-witness progress uses certified approvals in a revealed partial profile to identify PAV-improving swaps.The learner records each returned candidate as approved by the witness group and resumes local search from the same committee.Source: §4 · pp. 6–8
  • At most k^2H_k rejections suffice under full-witness feedback, and the algorithm runs in polynomial time.Each rejection forces a subsequent swap with PAV gain at least n/k^2; the score is bounded above by nH_k.Source: §4 · pp. 7–8

4.1 A Superlinear Lower Bound

  • An admissible support-size sequence of length T yields at least T deterministic rejected proposals under a truthful full-witness oracle.The construction adapts returned candidates and witness groups, then verifies all responses against one fixed approval profile.Source: §4.1 · pp. 8–9

4.1.1 An Explicit 2 3k3/2 Lower Bound

  • The explicit block construction gives a Θ(k^3/2) lower bound using q_ℓ copies of each level ℓ.The sequence is admissible, and its length lower-bounds the number of rejected proposals.Source: §4.1 · p. 8, §4.1.1 · p. 9

5 Average Potential Progress

Under candidate-only feedback, the learner has only average potential progress: random deletion gives an expected bound, while deterministic learners can branch to find an accepted proposal. The section also establishes lower bounds on what randomization and single-path updates can achieve.

5.1 Uniform Random Deletion

  • k^2H_k rejections in expectation suffice for uniform random deletion, which terminates almost surely against every fixed profile and adaptive oracle.The learner replaces the returned candidate while deleting a uniformly random committee member.Source: §5.1 · p. 10

5.2 A Randomized Lower Bound

  • Even with full-witness feedback, randomized learners can require k rejections.The lower-bound construction hides one universally approved candidate in each of k blocks.Source: §5.2 · pp. 10–11

5.3 The Single-Path Barrier

  • Bk = 3k^3/2 + O(k) rejections can be forced against every insertion–deletion learner under candidate-only feedback.The lower bound applies when the learner responds to a returned candidate by deleting one current committee member and inserting that candidate.Source: §5.3 · p. 11

5.4 Exhaustive Branching

  • 2^O(k^2(log k)^2) rejections suffice for deterministic exhaustive branching under candidate-only feedback.The learner queries all k deletion successors at each rejected proposal; the hidden PAV potential’s average increase ensures some branch reaches acceptance.Source: §5.4 · pp. 12–13

6 Discussion

The discussion organizes the results by how much progress the learner can certify, and identifies unresolved quantitative bounds, especially for candidate-only feedback.

6 Discussion

  • The results form a hierarchy: PJR+ permits permanent retention, full-witness EJR+ offers observable PAV progress, and candidate-only EJR+ offers only average progress.The paper contrasts this hierarchy with open questions about the bounds achievable in each setting.Source: §6 · p. 13
  • For full-witness deterministic EJR+ learning, the known bounds are Ω(k^3/2) and O(k^2 log k), while candidate-only feedback has the same lower bound and an exponential upper bound.Whether candidate-only deterministic EJR+ learning admits a polynomial bound remains open.Source: §6 · p. 13
  • The single-path lower bound does not cover learners that retain multiple deletion branches, and the paper conjectures randomized EJR+ learners may require more than a linear number of proposals.Source: §6 · p. 13

Disclosure of AI Use

The author reports using an LLM for editorial assistance and taking responsibility for the mathematical content and final text.

Disclosure of AI Use

  • The author used an LLM for editorial assistance and takes full responsibility for the mathematical content and final text.Source: Disclosure of AI Use · p. 13

A Optimal admissible sequences and the refined lower-bound constant

The appendix sharpens the admissible-sequence construction with a greedy recurrence and a continuum analysis yielding an explicit asymptotic lower-bound constant.

A Optimal admissible sequences and the refined lower-bound constant

A.1 The optimal greedy recurrence

The section defines a greedy recurrence over states holding the k largest preceding levels and proves that choosing the smallest admissible level yields a maximum-length admissible sequence.

A.1 The optimal greedy recurrence

  • Each state stores the k largest preceding levels, with zeros added initially, and updates by appending the smallest admissible level.The recurrence stops when no admissible level remains.Source: §A.1 · pp. 14–15
  • The recurrence produces an admissible sequence of maximum possible length.At each state, it appends the smallest admissible level and retains the k largest levels seen so far.Source: §A.1 · p. 15
  • Every admissible sequence has length at most k^2, so the recurrence terminates.A fixed level can occur at most k times, and there are k levels.Source: §A.1 · p. 15
  • Choosing the smallest admissible level preserves every continuation available after choosing any larger admissible level.Componentwise monotonicity of successor states establishes that the smaller choice permits a sequence at least as long.Source: §A.1 · p. 15

A.2 A refined asymptotic lower bound

The section develops and verifies a longer admissible-sequence construction using a scaled deficit profile, defines a convergent-series constant γ=1.1496..., and states that the lower bound also applies to QEJR+.

A.2 A refined asymptotic lower bound

  • At scaled level y, the block fraction h(y) is chosen so the normalized deficit equals y^2.The k largest preceding levels comprise complete blocks at successive deficits, followed by a partial block.Source: §A.2 · pp. 15–16
  • The scaled deficit profile uses a continuous, strictly decreasing function F and defines h by F(h(y))=y^2.For a level near the scaled value y, the construction predicts approximately kh(y) copies.Source: §A.2 · pp. 15–16
  • γ=1.1496... is defined by a convergent series whose summand is Θ(p^-3/2).The series gives the constant used in the predicted total sequence length.Source: §A.2 · p. 16
  • Theorem A.4 rigorously verifies the longer sequence motivated by the scaling calculation.The construction concatenates increasing-level blocks and establishes their admissibility.Source: §A.2 · pp. 15–17
  • The lower bound also applies to QEJR+.The full-witness bound follows from Theorem A.4, Theorem 4.6, and Proposition A.2.Source: §A.2 · p. 17
Loading 2608.30111v1…