The Maximin Support Method: An Extension of the D'Hondt Method to Approval-Based Multiwinner Elections

Luis Sánchez Fernández, Norberto Fernández García, Jesús A. Fisteus, Markus BrillAAAI 2021 · DOI

Introduction

In multiwinner elections, the objective is to select a fixed-size committee of $k$ candidates based on voter preferences. While the classic D’Hondt method (also known as the Jefferson method) is widely regarded as the gold standard for proportional representation in party-list systems, it is not directly applicable to approval-based voting. In approval voting, voters can approve multiple candidates, creating overlapping sets of support that complicate seat allocation.

The Maximin Support Method (MMS) is a novel voting rule designed to bridge this gap. It extends the logic of D’Hondt to approval-based scenarios while maintaining computational efficiency and satisfying key fairness axioms.

The D'Hondt Method as a Foundation

To understand MMS, one must first look at the D’Hondt method. In a party-list system, each voter supports exactly one party. The D’Hondt method allocates seats by iteratively dividing the total votes for each party by a series of divisors ($1, 2, 3, \dots$) and awarding seats to the highest resulting quotients.

Table 1: An example of the classic D'Hondt method calculation, where seats are allocated by dividing vote counts by successive integers.

As shown in Table 1, the method ensures that parties with higher vote counts receive a proportional share of seats. A key insight of the research is that D’Hondt can be re-characterized as a "maximin" optimizer: it is the unique method that maximizes the support value of the least-supported elected candidate in a party-list setting.

The Maximin Support Method (MMS)

The MMS extends this maximin principle to approval voting. In this context, "support" is formalized as a distribution of a voter's single vote across the candidates they approve. If a voter approves multiple elected candidates, their vote can be split among them (e.g., 0.5 to candidate A and 0.5 to candidate B).

Sequential Selection and Linear Programming

Finding a globally optimal committee that maximizes the minimum support is computationally difficult (NP-hard). To address this, MMS employs a sequential procedure:

  1. Candidate Selection: In each round, the method selects the candidate who, when added to the existing committee, maximizes the possible "maximin" support value for the updated group.
  2. Redistribution: Unlike Phragmén’s sequential rule, where a voter's "load" is fixed once assigned, MMS allows for the free redistribution of support among all currently elected candidates in every round.
  3. Efficiency: The support values for each step are calculated using Linear Programming (LP), ensuring the rule runs in polynomial time and is practical for large-scale elections.

Key Insights and Theoretical Results

The paper demonstrates that MMS provides a 2-approximation for the global maximin objective. This means the least-supported candidate in an MMS-selected committee will have at least half the support of the least-supported candidate in an optimally fair (but computationally unreachable) committee.

Axiomatic Success

MMS satisfies several critical fairness properties:

  • Committee Monotonicity: Increasing the committee size $k$ does not cause a previously elected candidate to lose their seat.
  • Proportional Justified Representation (PJR): It guarantees that cohesive groups of voters receive a fair number of representatives relative to their size.

In comparison, while Phragmén’s sequential rule is also committee-monotonic, it can perform arbitrarily poorly regarding the maximin objective. MMS maintains its 2-approximation guarantee where Phragmén fails.

Limitations and Future Directions

Despite its strengths, MMS does not satisfy Extended Justified Representation (EJR), a stronger fairness property than PJR. The challenge of finding a committee-monotonic rule that satisfies EJR remains an open problem in social choice theory. Additionally, while the 2-approximation is a significant theoretical bound, future research may investigate if tighter bounds or even better polynomial-time approximations are possible.

Summary updated

BibTeX
@inproceedings{fernandez2021maximin,
  author = {Luis Sánchez Fernández and Norberto Fernández García and Jesús A. Fisteus and Markus Brill},
  title = {{The Maximin Support Method: An Extension of the D'Hondt Method to Approval-Based Multiwinner Elections}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16714},
}
Figure