PaperlayerView exact revision on arXiv

Source-linked AI summary

Approval-Based Apportionment: Like Portioning, Approximately like Committee Voting

Paul Gölz, Hannane Yaghoubizade

arXiv:2608.27605v1cs.GT

TL;DR

The paper asks how proportionality, priceability, and PAV-related properties relate in approval-based apportionment and how this setting connects to committee elections and portioning. It proves equivalences and implications in apportionment, constructs a lifting to portioning, and identifies approximate counterparts for several results in committee elections.

  • Problem

    The paper addresses the need to understand relationships among the many proportionality axioms and between those axioms and PAV-related properties.

  • Method

    The authors analyze approval-based apportionment, define a lifting operation to portioning, and use apportionment results to investigate approximate implications for committee elections.

  • Results

    EJR, EJR+, and FJR coincide, as do PJR, PJR+, and FPJR; Lindahl priceability is equivalent to bounded PAV improvement; and locally PAV-optimal committees are priceable.

  • Takeaways & Limitations

    Apportionment’s implication network appears closer to portioning’s than to committee elections’, while several exact apportionment implications become approximate in committee elections.

  • Takeaways & Limitations

    The paper does not study several axioms and compatibility questions, including perfect representation, laminar proportionality, committee monotonicity, and its compatibility with core stability.

Abstract

from arXiv · show

We study approval-based apportionment, a variant of committee elections in which candidates ("parties") can be selected several times. We show that the proportionality axioms EJR, EJR+, and FJR coincide, and so do PJR, PJR+, and FPJR; that Lindahl priceability, an axiom implying core stability, is equivalent to a notion of approximate optimality with respect to the proportional approval voting (PAV) score; and that locally PAV-optimal committees are priceable. Approval-based apportionment (where a candidate receives an integer number of seats) lies between committee elections (zero or one seat) and portioning (a fractional number of seats). We formally connect portioning and apportionment by giving a construction that lifts axioms from apportionment to portioning and preserves implications between them. Several of our new implications between apportionment axioms are natural from a portioning perspective, leading us to believe that apportionment sits closer to portioning than to committee elections. None of them holds in committee elections, but several extend approximately, which makes apportionment a fruitful setting for conjecturing approximate relationships in approval-based committee elections.

1 Introduction

The paper studies approval-based apportionment as a simpler model for understanding proportionality relationships, connecting it formally to portioning and testing which implications approximately extend to committee elections.

  • Motivation: The paper uses apportionment as a simpler setting where stronger theorem-proving opportunities can reveal conjectured relationships for general committee elections.Implications that fail in committee elections are then examined for approximate extensions.
  • Motivation: Approval-based apportionment allows candidates to receive multiple seats, unlike committee elections, while retaining a fixed total number of seats.It is motivated both as a model organism for committee elections and as a model for allocating legislative seats to political parties.
  • Contributions: The authors prove new implication relations among proportionality, priceability, and PAV-related properties in apportionment.These include coincidence of several proportionality axioms, an equivalence between Lindahl priceability and bounded PAV improvement, and priceability of PAV-optimal committees.
  • Connection to portioning: The paper treats portioning as the more natural second endpoint, with fractional allocations normalized to sum to 1 rather than integer allocations summing to k.A lifting construction transfers predicates from apportionment to portioning and preserves implication theorems.
  • Connection to committee elections: Several apportionment implications do not hold exactly in committee elections but extend approximately, including 2-approximate forms of FJR and FPJR.The results support using apportionment to conjecture approximate relationships in approval-based committee elections.

2 Apportionment

Approval-based apportionment allows parties to receive multiple seats, enabling several proportionality and priceability relationships that differ from committee elections. The section establishes collapses among representation axioms, an equivalence between bounded PAV improvement and Lindahl priceability, and priceability of locally PAV-optimal committees.

  • Preliminaries: Apportionment assigns k seats among parties, allowing any natural number of copies per party, unlike committee elections’ zero-or-one-seat restriction.Voter utility counts seats assigned to approved parties.
  • Proportionality axioms: FJR, EJR, and EJR+ coincide, as do FPJR, PJR, and PJR+ in apportionment.The FJR equivalence follows by averaging over a cohesive group’s approved multiset and applying EJR.
  • Connection to committee elections: Several apportionment implications fail in committee elections, but EJR+ implies 2-approximate FJR there.The paper uses apportionment results to motivate approximate relationships in the more restrictive committee-election setting.
  • PAV and priceability: Bounded PAV improvement is equivalent to Lindahl priceability in the apportionment setting.Bounded PAV improvement requires every party’s marginal PAV gain from an additional seat to be less than n/k.
  • PAV and priceability: Local PAV optimality implies priceability, making welfare optimization and priceability compatible in apportionment.The paper notes that local PAV optimality also implies Lindahl priceability through the bounded-improvement result.
  • Computational boundary: A locally PAV-optimal committee satisfies priceability, but polynomial-time computation of such a committee is not known.By contrast, local search can find a committee satisfying bounded PAV improvement in polynomial time.

3 Portioning

Approval-based portioning allocates fractional seat shares summing to one, providing a continuous counterpart to apportionment. The paper defines a limit-based lifting operation and shows that it preserves implications and connects apportionment properties to established portioning notions.

  • Portioning model: Portioning assigns each party a nonnegative fractional seat share, with all shares summing to one.Nash portioning maximizes the product of voters’ utilities.
  • Lifting construction: The lifting operation maps apportionment predicates to portioning predicates through limits of increasingly large normalized committees.A portioning satisfies lift(X) when it is the limit of committees satisfying X as committee size tends to infinity.
  • Recovered notions: The lifted framework recovers natural portioning concepts, including Lindahl equilibrium and Nash-optimal portionings as limits of PAV-optimal apportionments.This strengthens the previously known one-sided convergence result for PAV-optimal committees.
  • Preserved structure: Lifting preserves both implication results and existence results from apportionment to portioning.If X implies Y, then lift(X) implies lift(Y); if every apportionment instance has an X committee, every portioning instance has a lift(X) portioning.
  • Implication relationships: Portioning adds implications absent from apportionment, including equivalence among local PAV optimality, PAV optimality, and bounded PAV improvement analogs.The portioning implication chain also includes weak core implying decomposability, the analog of priceability.

4 Committee Elections

In committee elections, several apportionment implications fail exactly but reappear approximately. The section establishes approximate proportionality links and a bidirectional connection between bounded PAV improvement and frugal Lindahl priceability.

  • Priceability and PAV: Bounded PAV improvement prevents an outside candidate from increasing a committee’s PAV score by n/k or more.The proof constructs prices for approved alternatives outside the committee and uses a contrapositive argument for the converse direction.
  • Section perspective: The apportionment-to-committee comparison motivates testing whether exact relationships survive as approximation results.The section explicitly frames these results as transfers from the simpler apportionment setting.
  • Approximate proportionality: EJR+ implies 2-FJR, and PJR+ implies 2-FPJR in committee elections.The proof derives an EJR+ violation from a 2-FJR violation, with the PJR+ analogue established separately.
  • Priceability and PAV: α-frugal Lindahl priceability adds a third pricing condition and an approximation factor to restore a bidirectional link with bounded PAV improvement.The added condition orders prices so approved committee seats are no more expensive than equally preferred approved alternatives outside the committee.
  • Priceability and PAV: Frugal Lindahl priceability implies bounded PAV improvement, while bounded PAV improvement implies 2-frugal Lindahl priceability.Thus the two properties are related in both directions, with approximation only in the converse implication.

5 Conclusion

The conclusion summarizes new apportionment implications and the formal relationship between apportionment and portioning, while identifying open directions. It also highlights committee-election questions suggested by the apportionment results.

  • Contributions: The paper proves new axiomatic implications for approval-based apportionment and formally investigates its relationship with portioning.These are presented as the paper’s central contributions.
  • Open directions: The study leaves perfect representation, laminar proportionality, relational axioms, and axiom compatibility for future work.The authors also ask which axioms are easier to satisfy in apportionment than in general committee elections.
  • Implications for committee elections: The apportionment equivalence of EJR+ and FJR motivated asking whether EJR+ implies approximate FJR in committee elections.The conclusion also identifies frugal Lindahl priceability as a potentially useful strengthening for other work.

A Use of AI Tools

The authors used conversations with ChatGPT and Claude during initial proof development and proofreading, then reviewed, revised, and verified the arguments themselves.

  • Use of AI tools: ChatGPT and Claude assisted with initial versions of several proofs and with proofreading exposition and mathematical correctness.The listed proof topics include PAV priceability and lifts involving majoritarian portioning and Nash portioning.
  • Use of AI tools: All arguments were subsequently reviewed, revised, and verified by the authors.The authors also searched for counterexamples as part of their manual efforts.

B Apportionment

Approval-based apportionment represents committees as multisets of parties, allowing repeated selections and integer seat counts. Voter utility sums the seats assigned to approved parties, and quota uses the Hare formula.

  • Basic definitions: An apportionment instance consists of voters, parties, approval sets, and a total seat count k.A committee is a multiset W mapping parties to natural-number seat counts with total size k.
  • Basic definitions: Voter i’s utility is the sum of W(j) over parties j approved by i.This extends approval utility from selected candidates to repeated party seats.
  • Basic definitions: The Hare quota of voter group S is q(S) = floor(|S| · k/n).The quota depends on the group’s size, the total number of seats, and the number of voters.

B.1 Axiom Definitions

Apportionment axioms are defined by lifting committee-election predicates through cloning each party into k+1 candidates. This construction preserves both implication and existence results, and supplies apportionment definitions for representation, stability, priceability, and PAV criteria.

  • Predicate lifting: Each party is replaced by k+1 clones, and the apportionment committee expands each party according to its seat count.The lifted committee contains W(j) copies of party j.
  • Predicate lifting: An apportionment predicate holds exactly when its lifted committee-election predicate holds on the cloned instance.The correspondence is stated for any predicate X.
  • Implication preservation: If X implies Y for committee elections, then Xap implies Yap for apportionment; existence of X outcomes also transfers.The proof applies the cloned-instance definition in both directions.
  • Apportionment axioms: The framework defines JR, EJR/EJR+, FJR, PJR/PJR+, FPJR, core stability, priceability, Lindahl priceability, bounded PAV improvement, and PAV optimality.Local PAV optimality requires no improving one-party replacement, while PAV optimality compares every committee.
  • Priceability: Lindahl priceability and priceability in apportionment are formally shown to correspond precisely to their committee-election counterparts under lifting.The constructions aggregate or distribute clone prices while preserving the relevant conditions.

B.2 Omitted Proofs

The omitted proofs establish coincidence and non-implication results among apportionment axioms, alongside separations involving core stability, priceability, and PAV optimality.

  • Proportionality: FPJR, PJR, and PJR+ coincide in apportionment.The proof derives FPJR from PJR by averaging approvals over the multiset T.
  • Separations: EJR does not imply core stability, while PJR does not imply EJR.The separations are witnessed by methods satisfying one property but not the other.
  • Separations: Core stability does not imply Lindahl priceability.An explicit apportionment outcome is core stable but not Lindahl priceable.
  • PAV criteria: Bounded PAV improvement does not imply local PAV optimality, and local PAV optimality does not imply PAV optimality.The examples exhibit each separation through an improving replacement or a globally better committee.
  • Priceability: Lindahl priceability does not imply priceability, and priceability does not imply EJR.The first separation follows from incompatible budget bounds; the second uses seq-Phragmén as a counterexample.

C Portioning

Portioning allocates fractional seat mass across parties, normalized to total mass 1, and defines fairness, stability, welfare, and pricing concepts for these allocations.

  • Setting: A portioning instance consists of voters, parties, and approval sets, with a portioning represented by a nonnegative vector over parties.The allocated portions are fractional rather than integer seats.
  • Pricing: A Lindahl equilibrium pairs a portioning with prices whose total party revenue equals n for funded parties and whose unit-budget alternatives are not preferred.Every voter’s affordable portioning must provide utility no greater than the equilibrium outcome.
  • Fairness: Decomposability expresses a portioning as a sum of constituent allocations, while group fair share imposes a coalition-level allocation condition.The supplied definitions introduce both concepts without stating their full decompositions or share inequality.
  • Stability: Weak core excludes a coalition-funded portioning that fits its proportional budget and strictly improves every coalition member’s utility.The coalition budget is |S|/n.
  • Welfare and rules: Nash portioning maximizes the product of voters’ utilities, whereas majoritarian portioning repeatedly assigns a party mass equal to its active supporters’ fraction.The majoritarian procedure deactivates the selected party and its approving active voters each round.

C.2 Lifting Apportionment Predicates

The paper lifts apportionment predicates to portioning through large committees converging to fractional allocations. The resulting correspondences identify portioning analogs for representation, stability, pricing, PAV, and voting rules.

  • Construction: The lift uses integer committees whose normalized seat vectors converge to a portioning, with Diophantine approximation supplying suitable sequences.The construction ensures nonnegative integer counts and asymptotically vanishing coordinate error.
  • Representation: Every portioning satisfies the lifted JR property.A rounding construction gives each approved party at least one selected copy in sufficiently large committees.
  • Representation: The lifted EJR/EJR+ and FJR properties become fractional coalition guarantees based on voters’ portioning utilities.For EJR/EJR+, some coalition voter receives utility at least |S|/n; FJR compares against every affordable alternative t and utility threshold β.
  • Stability: The lifted PJR/PJR+ and FPJR properties are characterized by analogous fractional guarantees, while lifted core stability is weak core.The weak-core form requires some coalition member not to be strictly improved by any affordable portioning.
  • Pricing: The lift of priceability is decomposability, and the lift of Lindahl priceability is equivalent to Lindahl equilibrium.The pricing characterization requires party funding n·r(j) for each party receiving positive portion.
  • Voting rules: The lift of PAV is Nash portioning, while majoritarian portioning is precisely the lift of MES under a fixed tie-breaking order.The MES correspondence is established through convergence of outcomes as committee size grows.

C.3 Implication Relations

The section establishes implication and non-implication relations among apportionment axioms, including equivalences involving lifted portioning notions. It also defines the principal proportionality, priceability, stability, and PAV-based properties used in these relations.

  • Lifting to portioning: Apportionment implications lift to portioning: lifted X implies lifted Y whenever X implies Y, and existence of X committees transfers to existence of lifted X portionings.The construction uses normalized committees whose sizes tend to infinity and converge to a portioning.
  • PAV and priceability: The lifts of bounded PAV improvement, local PAV optimality, PAV optimality, and Lindahl priceability are equivalent.Lindahl equilibrium is equivalent to Nash optimality, which corresponds to lifted PAV optimality.
  • Stability and priceability: Every core-stable portioning satisfies priceability, but core stability does not imply Lindahl priceability in general.The latter separation is witnessed by a portioning that is core stable but fails the lifted bounded-PAV condition.
  • Proportionality relations: Priceability and EJR are incomparable, so PJR does not imply EJR because PJR is weaker than priceability.The examples provide one EJR portioning that is not priceable and one priceable portioning that fails EJR.

D.2 Newly Introduced Axioms

This section develops bounded PAV improvement and related priceability notions, showing how they connect to proportionality and PAV optimality while separating several implications. It also gives a polynomial procedure for finding committees satisfying bounded PAV improvement.

  • Bounded PAV improvement: Bounded PAV improvement implies EJR+ and optimal proportionality degree of ℓ−1.The condition requires every unelected candidate’s marginal PAV gain to be strictly below n/k.
  • Bounded PAV improvement: Local PAV optimality strictly implies bounded PAV improvement, with the stronger marginal-gain bound Δ+_W(c) ≤ n/(k + 1).The paper retains the weaker strict n/k threshold because it supports polynomial-time search and coincides with Lindahl priceability in apportionment.
  • Bounded PAV improvement: The strict inequality in bounded PAV improvement is necessary: replacing Δ+_W(c) < n/k by Δ+_W(c) ≤ n/k no longer guarantees EJR+.A four-voter, two-seat example violates EJR+ while meeting the weak threshold.
  • Committee-election separations: Lindahl priceability and bounded PAV improvement are incomparable in committee elections, although they coincide in apportionment.The paper gives a Lindahl-priceable committee that fails bounded PAV improvement and notes that priceability does not imply EJR+ there.
  • Algorithmic consequence: A local-search algorithm finds a committee satisfying bounded PAV improvement in O(k^2 log k) iterations.Each iteration increases PAV score by at least n/k − n/(k + 1), while the score is bounded by n·H(k).
  • Priceability variants: In apportionment, frugal Lindahl priceability is equivalent to Lindahl priceability, while frugal Lindahl priceability does not imply priceability or local PAV optimality.Stable priceability implies frugal Lindahl priceability, but the converse implications fail as stated by the propositions.

D.3 Deferred Proofs

The deferred proofs establish approximate committee-election implications and strong separation results. They also show that Pareto-optimal welfarist rules cannot guarantee even constant-factor priceability.

  • Approximate implications: In committee elections, PJR+ implies 2-FPJR.The proof uses candidate cloning and reduces a violation of 2-FPJR to a PJR+ violation.
  • Committee-election boundary: The deferred results emphasize that several apportionment implications fail exactly in committee elections, while selected relationships survive approximately.The section explicitly states that none of the remaining apportionment implications holds approximately in committee elections.
  • Priceability impossibility: No Pareto-optimal welfarist rule can always return an α-priceable committee for any constant α ≥ 1.This generalizes the impossibility of Pareto-optimal welfarist rules that always return priceable committees.
  • Cloning construction: The figure represents blocks of t identical candidates, with voters approving more than k = 57t candidates and k selected candidates colored as the committee.The construction supports the cloning-based proof of the priceability impossibility result.
  • Separation results: EJR does not imply any constant approximation of FPJR or PJR+, and consequently cannot imply any constant approximation of FJR or EJR+.The construction uses regular, irregular, and dummy candidates; its violations become arbitrarily severe as q/t grows.
Loading 2608.27605v1…