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.
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:
- 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.
- 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.
- 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