Introduction
Multiwinner voting rules are the backbone of representative democracy, used to select committees, parliaments, or boards. Traditionally, these rules are designed to optimize for three primary objectives: excellence (electing the most popular candidates), diversity (ensuring every voter is represented by at least one candidate they like), or proportionality (ensuring cohesive groups receive representation proportional to their size).
However, these standard objectives often ignore the social cohesion of the resulting electorate. A committee can be perfectly proportional yet deeply polarized, consisting of extreme candidates who leave the electorate divided into isolated, disconnected factions. This paper introduces a new paradigm in computational social choice: the selection of "interlacing" committees that actively favor candidates who bridge different voter groups and foster consensus.
Quantifying Connectivity: PAIRS and CONS
To evaluate how well a committee connects an electorate, the authors propose two novel quantitative metrics based on approval ballots:
PAIRS: This metric counts the number of pairs of voters who share a direct connection. A connection exists if both voters approve at least one common candidate within the elected committee.CONS(Consensus): This metric measures indirect connectivity. It counts the number of pairs of voters connected via a sequence of shared candidates (e.g., Voter A shares a candidate with Voter B, who in turn shares a different candidate with Voter C).
While PAIRS is a straightforward measure of overlap, CONS is a more robust measure of societal bridging. It effectively measures the size of connected components in the voter-candidate hypergraph, rewarding the formation of chains that link disparate parts of the political spectrum.
Computational Complexity and Structured Domains
The authors prove that maximizing either PAIRS or CONS is NP-hard in general elections, making it computationally difficult to find optimal committees as the number of voters and candidates grows. To find tractable solutions, the research focuses on the Voter-Candidate Interval (VCI) domain.
In the VCI model, voters and candidates are placed on a 1D political spectrum (such as a left-to-right axis), and voters approve all candidates within a certain distance of their own position. The authors demonstrate that in this structured 1D domain, both metrics can be maximized in polynomial time. While PAIRS can be solved using existing algorithmic frameworks, CONS requires a novel and complex 3D dynamic programming approach.
The Submodularity Divide
A critical theoretical insight of the paper is the mathematical distinction between the two metrics. PAIRS is a submodular function, meaning it exhibits diminishing returns. This property makes it mathematically "well-behaved," allowing it to be easily combined with other submodular goals—such as popularity—by simply splitting committee seats between the two objectives.
In contrast, CONS is non-submodular. Because a single moderate candidate can suddenly merge two massive, previously isolated voter clusters, the CONS score can experience a quadratic spike. This lack of submodularity makes CONS fundamentally harder to optimize and leads to more significant trade-offs when trying to satisfy other democratic criteria.
Theoretical Trade-offs
The research establishes rigorous axiomatic bounds on the trade-offs between anti-polarization metrics and traditional voting goals like Approval Voting (AV) scores, Chamberlin-Courant (CC) diversity, and Extended Justified Representation (EJR).
- Linear Trade-offs for
PAIRS: The authors prove that if a voting rule guarantees an $\alpha$-approximation ofPAIRSand a $\beta$-approximation of standard metrics, then $\alpha + \beta \le 1$. This bound is tight. - Quadratic Trade-offs for
CONS: Due to its non-submodular nature, the trade-offs forCONSare steeper. To maintain a high approximation of standard metrics, the guaranteed approximation forCONSdrops quadratically.
Despite these harsh worst-case bounds, the authors provide a positive result for structured domains: in the 1D VCI model, it is always possible to find a committee that achieves at least 25% of the optimal CONS score while simultaneously achieving 50% of the optimal scores for AV, CC, EJR, or PAIRS.
Conclusion and Future Directions
This work highlights the inherent tension between reducing polarization and maintaining traditional representation. While the theoretical trade-offs can be steep, the introduction of PAIRS and CONS provides a formal framework for designing committees that do more than just represent factions—they connect them.
Future research may involve tightening the mathematical bounds for CONS and applying these interlacing concepts to other areas of collective decision-making, such as Participatory Budgeting. Testing these metrics on real-world election data may also reveal that practical trade-offs are less severe than the theoretical worst-case scenarios suggest.
Summary updated