🤖 machine learning

Proportionally Representative Clustering

This paper introduces a new fairness axiom called "proportionally representative fairness" (PRF) for centroid clustering and presents efficient polynomial-time algorithms that achieve this fairness guarantee for both unconstrained and discrete clustering settings, while also providing the first approximation algorithm for the Proportional Fairness axiom in the unconstrained case.

Original authors: Haris Aziz, Barton E. Lee, Sean Morota Chu, Jeremy Vollen

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haris Aziz, Barton E. Lee, Sean Morota Chu, Jeremy Vollen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a massive community event and need to set up k food trucks (the "centroids") to serve n hungry people (the "data points") scattered across a park (the "metric space").

The goal of traditional clustering is usually to minimize the total walking distance for everyone. It's like trying to make the average person happy. But this often leads to a problem: if 90% of the crowd is in one corner and 10% is in another, the food trucks will all cluster in the big corner, leaving the small group starving. They are "fair" in a mathematical average sense, but they ignore the small group entirely.

This paper proposes a new way to think about fairness called Proportionally Representative Fairness (PRF).

The Core Idea: "The Neighborhood Rule"

Instead of just looking at the average, PRF asks: "If a group of people is big enough to deserve a food truck, do they actually get one nearby?"

The paper introduces a specific rule:

If a group of people is large enough to "deserve" $\ell$ food trucks (based on their size relative to the total crowd), and they are all standing close together in a tight circle, then the final setup must include at least $\ell$ food trucks within that circle.
It doesn't matter if the group is defined by race, gender, or income. The group is defined purely by where they are standing and how many of them there are.

The Problem with Old Rules

The authors show that previous "fair" algorithms fail this test.

The "Greedy Capture" method: Imagine a greedy algorithm that just picks the best spot for the next truck one by one. The authors show a scenario where you have a huge crowd at one spot and a smaller crowd at another. A greedy algorithm might pick a spot that serves the small crowd well but leaves the huge crowd with too few trucks, violating the "deserving" rule.
The "Unanimous Proportionality" failure: If 10,000 people are standing at point A and 1,000 are at point B, and you need 11 trucks, a truly fair system should put 10 trucks at A and 1 at B. Old algorithms sometimes put 1 at A and 10 at B, which is mathematically "fair" in some old definitions but intuitively wrong.

The Solution: "Spatial Expanding Approval Rule" (SEAR)

The authors invented a new algorithm called SEAR (Spatial Expanding Approval Rule). Think of it like a game of "growing bubbles."

Start Small: Imagine every person has a tiny bubble around them. Everyone starts with 1 "vote."
Expand the Bubbles: Slowly, the bubbles around everyone start to grow larger at the same speed.
Find a Winner: As soon as a bubble grows big enough to overlap with a potential food truck location, and the total weight of the people inside that bubble reaches a "quota" (enough people to deserve a truck), the algorithm picks that truck.
Reset and Repeat: Once a truck is picked, the people who were "served" by that truck have their "votes" reduced (they are now satisfied). The bubbles keep growing, and the process repeats until all $k$ trucks are placed.

This method ensures that if a group is big and tight, they will "capture" a truck before the algorithm moves on to other areas.

The Results: What Did They Prove?

The paper makes three big claims about this new system:

It Always Works: Unlike some previous fairness ideas where a perfect solution might not exist, the authors prove that a PRF solution always exists and their algorithm finds it quickly (in polynomial time).
It's a Good Approximation: Even if we can't get a "perfect" fair outcome, their algorithm guarantees that the result is very close to the best possible fairness (within a factor of 3 for general spaces, and even better for specific types of spaces).
The Trade-off (The Catch): The paper also proves a hard truth: You can't have it all. If you want a system that is perfectly fair (PRF) and also strategy-proof (meaning people can't lie about where they live to get a better truck), it's mathematically impossible.
- Analogy: If you know the algorithm is trying to give you a truck, you might lie and say you live in a different spot to trick the system into placing a truck closer to you. The authors show that any system that guarantees PRF will inevitably be vulnerable to this kind of manipulation.

Summary

In short, this paper says: "Stop trying to make the average person happy. Instead, make sure that any large, tight-knit group of people gets a number of resources proportional to their size." They built a fast, reliable algorithm to do this, but warned that if people try to game the system by lying about their location, the fairness might break.

Technical Summary: Proportionally Representative Clustering

Problem Statement
The paper addresses the problem of fairness in centroid clustering, a fundamental task in unsupervised machine learning where the goal is to select a subset of $k$ centers (centroids) from a metric space to serve a set of $n$ data points (agents). While standard objectives like $k$ -means, $k$ -medians, and $k$ -center optimize for global welfare, they often fail to capture proportional representational fairness. Existing fairness concepts in clustering, such as Proportional Fairness (PF) and Core Fairness, have limitations: they may not be achievable for every instance, and they fail to satisfy a minimal intuitive requirement known as "unanimous proportionality" (where a group of agents at the same location is entitled to a number of centers proportional to their size). Furthermore, existing algorithms for fair clustering often rely on pre-specified protected attributes, whereas this work seeks fairness properties applicable to arbitrarily defined groups determined endogenously by the data distribution.

Methodology
The authors adopt an axiomatic approach, proposing a new fairness concept called Proportionally Representative Fairness (PRF). This concept is designed for both unconstrained (continuous) and discrete clustering settings.

Axiomatic Definition (PRF):
- Unconstrained Setting: An outcome $X$ satisfies PRF if, for any set of agents $S$ of size at least $\ell n/k$ with a maximum pairwise distance $y$ , there are at least $\ell$ centers in $X$ within distance $y$ of at least one agent in $S$ .
- Discrete Setting: The definition is adapted to account for the coarseness of the candidate set $M$ . If there are $\ell'$ candidates in $M$ within distance $y$ of all agents in a group $S$ (where $|S| \ge \ell n/k$ ), then at least $\ell'$ centers in the outcome must be within distance $y$ of some agent in $S$ .
Algorithm Design (SEAR):
The authors introduce SEAR (Spatial Expanding Approval Rule), a polynomial-time algorithm inspired by the Expanding Approvals Rule (EAR) from multi-winner voting but adapted for spatial data.
- Mechanism: The algorithm iteratively expands neighborhood radii based on the sorted distances between agents and candidates. Agents are assigned initial weights. When a candidate center is selected that covers a group of agents with a total weight of at least $n/k$ , that center is added to the solution, and the weights of the covered agents are reduced by $n/k$ .
- Implementation:
  - Algorithm 1 (Unconstrained): Candidates are restricted to the locations of the agents. It runs in $O(n^2 \log n + kn^2)$ .
  - Algorithm 2 (Discrete): Candidates are drawn from a finite set $M$ . It runs in $O(|M|n \log n + k|M|n)$ .

Key Contributions and Results

Existence and Properties of PRF: The paper proves that a PRF outcome is guaranteed to exist in both unconstrained and discrete settings. PRF satisfies several desirable properties: it implies unanimous proportionality, is robust to outliers, is scale-invariant, and does not require pre-specified protected groups.
Approximation of Proportional Fairness (PF):
- Unconstrained: The SEAR algorithm for the unconstrained setting provides a 3-approximation to Proportional Fairness. This is the first known polynomial-time approximation algorithm for PF in general metric spaces. The paper also establishes a tight bound of $\frac{3+\sqrt{17}}{2} \approx 3.56$ for the general existence of PRF outcomes regarding PF.
- Discrete: The SEAR algorithm for the discrete setting provides a $(1+\sqrt{2})$ -approximation to PF, matching the best known approximation factor for PF in the discrete setting while additionally satisfying the stronger PRF axiom.
Impossibility Results:
- The paper demonstrates that standard clustering algorithms ( $k$ -means, $k$ -median, $k$ -center) and previous fair clustering algorithms (like Greedy Capture) do not satisfy PRF.
- Strategyproofness: The authors prove an incompatibility between PRF and strategyproofness. Specifically, there is no algorithm that is both order-statistic strategyproof and satisfies PRF, even for $k=2$ in the discrete setting. This is shown via a reduction from approval-based committee voting, linking PRF to the Proportional Justified Representation (PJR) axiom, which is known to be incompatible with strategyproofness.

Significance
The paper claims significance in three primary areas:

Conceptual Advancement: It introduces PRF as a robust, axiomatic fairness concept that overcomes the shortcomings of existing proportional fairness definitions, particularly the failure to guarantee unanimous proportionality.
Algorithmic Breakthrough: It provides the first polynomial-time approximation algorithms for Proportional Fairness in general metric spaces (unconstrained setting) and matches the best-known bounds for the discrete setting, all while satisfying the stronger PRF axiom.
Theoretical Limits: It rigorously establishes the trade-off between fairness (specifically PRF) and incentive compatibility (strategyproofness), showing that satisfying proportional representation axioms inherently conflicts with preventing manipulation in centroid selection.

The work positions itself as a bridge between social choice theory (specifically multi-winner voting) and unsupervised machine learning, utilizing spatial information to make synchronized decisions that traditional voting rules or standard clustering objectives cannot achieve.