Phragmén's Voting Methods and Justified Representation

Markus Brill, Rupert Freeman, Svante Janson, Martin LacknerAAAI 2017 · DOI

Abstract

This paper re-evaluates the load-balancing voting methods proposed by Lars Edvard Phragmén in the late 19th century within the context of modern computational social choice. We demonstrate that the "sequential Phragmén" rule is a polynomial-time algorithm that satisfies Proportional Justified Representation (PJR), addressing a significant gap in multi-winner election theory. While optimization-based variants like max-Phragmén and var-Phragmén offer strong fairness properties such as Perfect Representation, they are computationally intractable. Our analysis highlights seq-Phragmén as a practical and fair alternative for large-scale committee elections.

Introduction

In multi-winner "committee" elections, voters use approval ballots to select a fixed-size set of candidates. A central challenge is ensuring proportional representation: cohesive groups of voters should receive a number of seats proportional to their size. Modern social choice theory defines several fairness axioms, including Justified Representation (JR), Proportional Justified Representation (PJR), and Extended Justified Representation (EJR).

While Proportional Approval Voting (PAV) satisfies the strongest of these, it is NP-hard to compute, making it impractical for large-scale applications. This paper investigates Phragmén’s methods as computationally efficient alternatives that maintain high fairness standards, specifically focusing on the gap between computational efficiency and axiomatic fairness.

Methodology: The Load-Balancing Metaphor

Phragmén’s methods treat election results as a load-balancing problem. Each elected candidate represents one unit of "load," which must be distributed among the voters who approved them. This "cost" reduces the voters' remaining capacity to influence subsequent seat selections.

Visualization of the sequential load-balancing process in Phragmén's voting methods.

The authors analyze three primary variants:

  • max-Phragmén: An optimization approach that selects a committee to minimize the maximum load any single voter carries.
  • var-Phragmén: An optimization approach that minimizes the variance of voter loads (the sum of squared loads).
  • seq-Phragmén: A greedy, sequential approach. In each round, it adds the candidate that results in the smallest possible new maximum load, assuming the load of the new candidate is shared equally among its supporters to equalize their total loads.

Key Results

The study reveals that seq-Phragmén is a breakthrough rule. It is the first discovered rule that is both computationally efficient—calculable in polynomial time $O(k^3 mn \log^2 n)$—and satisfies the PJR property. In contrast, optimization variants like max-Phragmén and var-Phragmén are NP-complete to compute.

Furthermore, the paper introduces the concept of Perfect Representation (PR), where every voter carries an identical load. While max-Phragmén and var-Phragmén satisfy PR, the widely used PAV rule does not. Interestingly, var-Phragmén fails PJR despite its optimization focus, highlighting that variance minimization does not always align with proportional fairness.

Conclusion

Phragmén’s sequential method offers a robust solution for large-scale multi-winner elections where computational efficiency and PJR are required. While the "gold standard" of Extended Justified Representation (EJR) remains elusive for polynomial-time rules, seq-Phragmén significantly narrows the gap between theoretical fairness and practical implementation. Future research should investigate whether any efficient rule can satisfy EJR and how these methods perform under empirical preference distributions rather than worst-case theoretical scenarios.

Summary updated

BibTeX
@inproceedings{brill2017phragmen,
  author = {Markus Brill and Rupert Freeman and Svante Janson and Martin Lackner},
  title = {{Phragmén's Voting Methods and Justified Representation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10598},
}
Figure