PaperlayerView exact revision on arXiv

Source-linked AI summary

Proportionality and the Limits of Welfarism

Dominik Peters, Piotr Skowron

arXiv:1911.11747v3cs.GTecon.TH

TL;DR

The paper asks how different voting rules realize proportional representation and where welfare-based rules reach their limits. It introduces axioms and impossibility results distinguishing welfare from voting-power proportionality, then presents the Method of Equal Shares. The method satisfies several proportionality properties in polynomial time, while PAV achieves a factor-2 core approximation under Pigou–Dalton fairness.

  • Problem

    Existing proportionality axioms did not capture the distinct forms of proportionality achieved by Phragmén’s rule and PAV, motivating an analysis of welfarism’s limits.

  • Method

    The paper proposes laminar proportionality and priceability, proves impossibility results for welfarist rules, and introduces the Method of Equal Shares.

  • Results

    The Method of Equal Shares satisfies EJR, laminar proportionality, and priceability in polynomial time, while PAV provides a factor-2 approximation to the core.

  • Takeaways & Limitations

    The results formalize a dichotomy between fair distributions of voter welfare and fair distributions of voting power.

  • Takeaways & Limitations

    Priceability does not guarantee utility levels or efficiency, and known priceable rules fail Pareto-optimality.

Abstract

from arXiv · show

We study two influential voting rules proposed in the 1890s by Phragmén and Thiele, which elect a committee or parliament of k candidates which proportionally represents the voters. Voters provide their preferences by approving an arbitrary number of candidates. Previous work has proposed proportionality axioms satisfied by Thiele's rule (now known as Proportional Approval Voting, PAV) but not by Phragmén's rule. By proposing two new proportionality axioms (laminar proportionality and priceability) satisfied by Phragmén but not Thiele, we show that the two rules achieve two distinct forms of proportional representation. Phragmén's rule ensures that all voters have a similar amount of influence on the committee, and Thiele's rule ensures a fair utility distribution. Thiele's rule is a welfarist voting rule (one that maximizes a function of voter utilities). We show that no welfarist rule can satisfy our new axioms, and we prove that no such rule can satisfy the core. Conversely, some welfarist fairness properties cannot be guaranteed by Phragmén-type rules. This formalizes the difference between the two types of proportionality. We then introduce an attractive committee rule, the Method of Equal Shares, which satisfies a property intermediate between the core and extended justified representation (EJR). It satisfies laminar proportionality, priceability, and is computable in polynomial time. We show that our new rule provides a logarithmic approximation to the core. On the other hand, PAV provides a factor-2 approximation to the core, and this factor is optimal for rules that are fair in the sense of the Pigou--Dalton principle.

1. Introduction

The paper distinguishes welfare-based proportionality, exemplified by PAV, from power-based proportionality, exemplified by Phragmén’s rule. It formalizes this distinction with new axioms, impossibility results, and the Method of Equal Shares.

  • 1. Introduction: Phragmén’s rule and PAV achieve proportionality in fundamentally different senses: fair distribution of voting power versus fair distribution of voter welfare.
  • 1. Introduction: In an illustrative profile, Phragmén’s rule gives the first three voters half the seats, while PAV selects a committee with more equal voter satisfaction.
  • 1. Introduction: Laminar proportionality and priceability are satisfied by Phragmén’s rule but not by Thiele’s rule, and no welfarist rule can satisfy either axiom.
  • 1. Introduction: No welfarist rule can satisfy the core, although the core’s existence for every profile remains open.
  • 1. Introduction: PAV gives a factor-2 approximation to the core, and no rule satisfying Pigou–Dalton fairness can guarantee a better factor.
  • 1. Introduction: The Method of Equal Shares satisfies EJR, laminar proportionality, and priceability, is computable in polynomial time, and achieves a logarithmic core approximation.

2. The Model and Definitions of Rules

The paper models approval-based committee elections and defines Phragmén’s rule, the Method of Equal Shares, PAV, and welfarist rules. These rules differ in how they allocate representation, either through voter-funded selection, continuous earning, or welfare-vector optimization.

  • Model: An election instance consists of candidates, voters, an approval profile, and a desired committee size k.
  • Proportional Approval Voting: PAV chooses a size-k committee maximizing the sum of voter satisfaction, with satisfaction determined by the number of approved committee members.
  • Phragmén’s Sequential Rule: Phragmén’s Sequential Rule continuously gives voters money and selects candidates when approving voters collectively have n/k dollars.
  • Method of Equal Shares: The Method of Equal Shares gives each voter one dollar and sequentially selects candidates whose total price n/k can be shared among approving voters.
  • Method of Equal Shares: Equal Shares resembles Phragmén’s rule, but distributes voter resources upfront rather than continuously.
  • Rule properties: Equal Shares can return fewer than k candidates, while PAV and Phragmén’s rule are evaluated with different computational properties.Equal Shares may select fewer than k candidates; Phragmén’s rule and Equal Shares are computable in polynomial time, whereas PAV is NP-hard to evaluate.
  • Welfarism: A welfarist rule selects committees by optimizing a function of voters’ welfare vectors, and PAV is one such rule.

3. Laminar Proportionality

Laminar proportionality recursively specifies acceptable committees for well-structured approval profiles. Phragmén’s rule and Equal Shares satisfy it, whereas PAV does not.

  • Definition: Laminar profiles are built recursively from unanimous instances, unanimous candidates, and disjoint sums of proportional subinstances.
  • Examples: Integral party-list instances are laminar, and laminar proportionality extends party-list proportionality beyond integral party-list profiles.
  • Definition: A laminar election instance has an approval-set system in which candidate-supporter sets are nested or disjoint.
  • Axiom: Laminar proportionality requires committees to follow the recursive structure of the profile, including unanimous candidates and proportional allocation across disjoint subinstances.
  • Results: Phragmén’s rule and the Method of Equal Shares are laminar proportional, while PAV fails laminar proportionality.
  • Welfarism: No welfarist committee rule satisfies laminar proportionality.

4. Price Systems

Priceability represents committees through equal voter budgets and candidate prices, capturing similar voter influence. It is satisfied by Phragmén’s rule and Equal Shares but does not guarantee efficiency or compatibility with welfarism.

  • Definition: A committee is priceable when equal voter budgets can fund every elected candidate at one common price while preventing affordable additional candidates.
  • Limitations: Priceability constrains voter influence but does not ensure utility guarantees or efficiency, and it is logically incomparable with laminar proportionality.
  • Properties: Priceable committees satisfy proportional justified representation for groups meeting the relevant size and approval-union quotas.
  • Properties: Priceability can be checked by linear programming, unlike proportional justified representation, whose verification is coNP-complete.
  • Results: Phragmén’s rule and Equal Shares always return priceable committees.
  • Results: On party-list profiles, a committee is priceable exactly when it is selected by D’Hondt with committee size equal to the committee’s size.
  • Welfarism: No Pareto-optimal welfarist rule always returns committees supported by price systems.The paper conjectures that Pareto-optimality may not be necessary for this incompatibility.

5. The Core

The core is an attractive stability notion, but it conflicts with egalitarian utility distribution and cannot be satisfied by welfarist rules. PAV achieves the best possible core approximation under Pigou–Dalton fairness, while Equal Shares offers weaker core approximation alongside stronger proportionality guarantees.

  • Core definition and motivation: The core requires that no voter coalition can propose a smaller proportional committee that strictly improves every member’s utility.It implies extended justified representation, but its universal existence remains open, and all known committee rules fail it.
  • Core versus egalitarian fairness: Every core outcome in the k = 12 example violates the Pigou–Dalton principle because cohesive coalitions can force higher utility than less cohesive voters.The blocking coalition {v1, v2, v3} forces candidates that leave some voters with utility 4 and others with utility 2, enabling an equalizing transfer.
  • Core versus egalitarian fairness: No rule can satisfy both the Pigou–Dalton principle and the (2 −ε)-core property for every ε > 0.This establishes an incompatibility between a minimal egalitarian condition and core stability, rather than merely showing failure for PAV.
  • Approximating the core: PAV satisfies the 2-core property, and this approximation is optimal among rules satisfying Pigou–Dalton fairness.PAV satisfies Pigou–Dalton, cannot satisfy the (2 −ε)-core, and therefore reaches the tight factor-2 boundary under that fairness requirement.
  • Approximating the core: Equal Shares provides an O(log k)-core approximation, but fails every O(log^c k)-core property for c < 1.The lower bound arises from blocking coalitions whose members receive highly unequal improvements, limiting the practical force of such deviations.
  • Constrained deviations: Equal Shares satisfies EJR and a strengthened property intermediate between the core and EJR, while also satisfying priceability.Its constrained-deviation guarantee is stronger than EJR but does not provide full core stability.
  • Welfarism and the core: No welfarist committee rule satisfies the core property.The impossibility construction uses profiles with welfare vectors that induce contradictory choices under voter permutations.

6. Conclusion

The study distinguishes welfare-based and power-based proportionality, showing that PAV and Phragmén’s rule embody these different fairness concepts. It introduces a rule combining Phragmén’s proportionality properties with EJR, while leaving several priceability and core questions open.

  • Phragmén’s proportionality properties cannot be achieved by welfarist rules, while PAV’s welfare-based fairness is incompatible with some Phragmén-style properties.
  • The paper introduces Equal Shares, which combines Phragmén’s proportionality properties with extended justified representation.
  • The paper identifies two distinct fairness dimensions: welfare distribution, represented by PAV, and voting-power distribution, represented by Phragmén’s rule and Equal Shares.
  • Known priceable rules fail Pareto-optimality, while natural welfare-maximizing approaches cannot guarantee priceability.
  • Open questions concern whether Pareto-optimal and priceable committees always exist and whether welfarist rules can approximate the core better than PAV.

A. Additional Discussion

The additional discussion clarifies the formal treatment of laminar proportionality and proves a structural property of laminar profiles. It explains why a stronger decomposition condition is not adopted.

  • The appendix explains that laminar proportionality focuses on integral profiles and records formalization choices underlying the concept.
  • A proposed stronger decomposition condition would require proportional outcomes on combined instances to be unions of outcomes from separate instances.
  • Many laminar proportional rules fail this stronger condition, motivating the weaker formalization used in the paper.
  • For a laminar profile, the voter sets approving candidates form a laminar family.
  • The proof establishes this structural property by induction over unanimous profiles, commonly approved candidates, and decompositions into disjoint laminar subprofiles.

A.1. Overlapping Parties: Comparing Equal Shares and Phragm´en’s Sequential Rule

Equal Shares and Phragmén’s Sequential Rule treat overlapping-party support differently. In the stated example, Equal Shares allocates seats according to total party support, whereas Phragmén’s rule follows exclusive supporters.

  • Equal Shares satisfies EJR and a core property subject to priceability with equal payments, while Phragmén’s rule is committee-monotonic.
  • With 50% first-party voters, 25% consensus voters, 25% second-party voters, and k = 100, Equal Shares selects 75% first-party and 25% second-party candidates.
  • In the same profile, Phragmén’s rule and PAV assign roughly two-thirds of seats to the first party and one-third to the second.
  • Phragmén’s rule and PAV effectively base party proportions on voters who approve only one party, because consensus voters are satisfied by either outcome.
  • The example can also be interpreted as laminar under voter approval sets, although this differs from laminarity defined through candidate-approval voter sets.

A.2. Proportionality with Respect to Disagreements

Equal Shares interprets proportionality through equalized monetary voting power, while PAV uses diminishing marginal representation and therefore treats overlapping support differently.

  • Equal Shares gives each voter voting power equal to the money they hold, so a group γ times larger initially has γ times more voting power.
  • Equal Shares uses shared support for committee members to determine how groups’ resources translate into representation.
  • PAV’s intuitive voting power decreases with existing representation, taking the form 1/r_i+1 for a voter with r representatives.

B. Proofs Omitted From the Main Text

The omitted proofs establish laminar proportionality for Phragmén’s rule and Equal Shares, while PAV fails it. They also prove Equal Shares’ logarithmic core approximation and exhibit limits involving priceable deviations.

  • Laminar proportionality: Phragmén’s rule and Equal Shares are laminar proportional, whereas PAV fails laminar proportionality.The Phragmén result is proved by induction; Equal Shares is also established by induction, while PAV has counterexamples.
  • Phragmén’s rule: Phragmén’s sequential rule terminates at time k/n on every laminar instance.The proof uses induction over unanimous profiles and disjoint laminar subinstances.
  • PAV counterexample: An optimal PAV committee can fail laminar proportionality, as shown by the committee {c1, c2, c3, c4} in Example 4.The example identifies this committee as one of PAV’s optimal committees but not as laminar proportional.
  • Core approximation: Equal Shares satisfies the O(log k)-core property but fails the O(log^c k)-core property for every c < 1.The upper-bound proof derives a logarithmic guarantee, while the construction establishes the lower-bound limitation.
  • Core approximation: For every c < 1, a constructed family shows Equal Shares cannot guarantee an O(log^c k)-core approximation.The construction chooses parameters with x in the order of log(k) and derives x > log^c(k).
  • Priceable deviations: Equal Shares violates the core when deviations are restricted to priceable committees.The proposition defines the restricted deviation class, and an example gives a priceable deviation that improves representation for a voter coalition.
Loading 1911.11747v3…