Proportional Representation Guarantees for Cohesive Groups

158 concepts86 papers1 proposal

Imagine you are electing a 5-member committee to represent a community of 100 voters. Suppose 51 of these voters share a preference for Candidates A, B, and C, while the remaining 49 voters prefer Candidates X, Y, and Z.

Under a standard approval voting system or a greedy utility-maximizing algorithm, Candidates A, B, and C each receive 51 votes, while X, Y, and Z receive 49. The algorithm selects the top vote-getters, filling the committee entirely with the majority's choices. Despite making up nearly half of the population, the minority group receives zero representation.

This phenomenon is known as the tyranny of the majority. It occurs because standard optimization objectives maximize aggregate satisfaction, which naturally favors the largest demographic block. To prevent this, researchers in computational social choice design selection mechanisms governed by formal proportional representation axioms. These mathematical guarantees ensure that any cohesive group of voters receives a share of influence proportional to its size.

The Baseline: Justified Representation

To protect minority groups, we must first mathematically define what a group "deserves." The foundational building block for this is the Hare quota, defined as $\frac{n}{k}$, where $n$ is the total number of voters and $k$ is the number of available seats. If a group's size meets or exceeds this threshold, they have enough collective voting power to claim at least one representative.

The simplest formal standard for this protection is Justified Representation (JR). A committee satisfies JR if any group of voters that is at least as large as the Hare quota ($\ge \frac{n}{k}$), and whose members all approve at least one common candidate, is guaranteed to have at least one member of the committee who satisfies at least one voter in that group.

While JR prevents total exclusion, it is a weak, binary condition. A group constituting 90% of the electorate could technically satisfy JR by having a single candidate represent them, leaving the remaining four seats to a 10% minority. To scale this protection proportionally, Edith Elkind et al. introduced Proportional Justified Representation (PJR) in Proportional Justified Representation.

Under PJR, if a cohesive group of voters is large enough to claim $\ell$ quotas (i.e., its size is at least $\ell \cdot \frac{n}{k}$), the committee must collectively contain at least $\ell$ distinct candidates approved by the group. This ensures that representation scales linearly with group size.

Traditional Greedy Selection (Maximizes Total Votes):
[ Majority (51%): A, B, C ]  ---> Gets 100% of Seats {A, B, C}
[ Minority (49%): X, Y, Z ]  ---> Gets 0% of Seats

Proportional Justified Representation (PJR):
[ Majority (51%) ] -----------> Gets 2 Seats {A, B}
[ Minority (49%) ] -----------> Gets 1 Seat  {X}

Finding rules that satisfy these axioms efficiently is a core algorithmic challenge. As demonstrated by Markus Brill et al. in Phragmén's Voting Methods and Justified Representation, a sequential voting method originally proposed by 19th-century mathematician Lars Edvard Phragmén satisfies PJR in polynomial time. It works by treating voting as a load-balancing problem: voters continuously accumulate "virtual credit" over time, and whenever a group has pooled enough credit to afford a candidate, that candidate is selected, and the group's credit is drawn down.

From Binary Axioms to Continuous Optimization

Classic axioms like JR and PJR operate as binary tests: a committee either satisfies the property or it fails. This pass-fail structure creates a significant limitation: it cannot distinguish between a committee that barely clears the minimum threshold and one that maximizes overall voter inclusion.

To resolve this, researchers have shifted toward quantitative metrics. As explored by Łukasz Janeczko et al. in The Complexity of Proportionality Degree in Committee Elections and Biaoshuai Tao et al. in The Degree of (Extended) Justified Representation and Its Optimization, the Proportionality Degree (PD) transforms qualitative fairness axioms into continuous optimization objectives.

Instead of checking for a binary condition, these metrics measure the exact number of voters within any cohesive group who are satisfied by the selected committee. By optimizing for the degree of representation, algorithms can actively maximize voter inclusion across diverse segments of the population rather than simply satisfying a worst-case mathematical constraint.

Making Proportionality Robust to Real-World Disagreement

A major vulnerability of classic PJR and Extended Justified Representation (EJR) is their reliance on perfectly cohesive groups—subsets of voters who approve the exact same candidates. In real-world scenarios, like-minded people rarely align perfectly. If a group of voters agrees on 95% of candidates but exhibits minor individual variations, strict mathematical protections can completely vanish.

To bridge this gap, the authors have developed more flexible frameworks. In Proportional Public Decisions, Piotr Skowron et al. proposed proportionality criteria that extend guarantees to any group of a certain size, regardless of internal preference diversity.

Similarly, Jannik Peters et al. introduced robust proportionality axioms in Robust and Verifiable Proportionality Axioms for Multiwinner Voting. Instead of defining fairness based on rigid voter blocks, their mechanism evaluates whether unselected candidates have "justified claims" to a seat based on under-represented voter segments. This shift from rigid group definitions to flexible, claim-based verification ensures that minor internal disagreements do not compromise a minority group's collective influence.

Beyond Elections: Budgeting, Ranking, and Clustering

The intuition behind justified representation is no longer confined to political committees; it is transforming resource allocation, digital platforms, and machine learning.

Participatory Budgeting

When cities allow citizens to vote on public infrastructure projects, greedy algorithms favor the absolute most popular projects, leaving minority neighborhoods empty-handed. In Proportional Participatory Budgeting with Additive Utilities, Dominik Peters et al. designed the Method of Equal Shares (MES). MES adapts multiwinner axioms to environments where projects have varying costs. It gives each voter an equal virtual budget to fund projects; any group large enough to afford a project can pool their money to secure it, ensuring that public funds are distributed proportionally across the entire population.

Content Ranking and Deliberation

In digital spaces, standard popularity-based ranking algorithms can lead to a vocal majority drowning out minority viewpoints. Daniel Halpern et al. demonstrated in Representation with Incomplete Votes that standard approval voting fails minority perspectives on digital deliberation platforms, whereas proportional selection criteria ensure diverse subgroup representation.

Taking this further, Manon Revel et al. applied JR directly to online comment sections in Representative Ranking for Deliberation in the Public Sphere, proving that enforcing representation constraints guarantees visibility for minority viewpoints with minimal cost to overall user engagement.

Data Clustering

Even in unsupervised machine learning, Leon Kellerhals et al. demonstrated that multiwinner voting axioms can be mapped to metric clustering in Proportional Fairness in Clustering: A Social Choice Perspective. By treating cluster centers as "representatives" and data points as "voters," they ensure that demographic subgroups are not unfairly distanced from all cluster centers by standard aggregate distance minimization.

Key Foundational Work

Justified Representation in Approval-Based Committee Voting (2014) — contributed 4 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_proportional_representation_gap_dffda863,
  title = {proportional representation gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proportional-representation-gap/rdr_dffda8631f14400c8a4ead3b988ffb45},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_proportional_representation_gap_dffda863_v1,
  title = {proportional representation gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proportional-representation-gap/rdr_dffda8631f14400c8a4ead3b988ffb45/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake