---
kind: concept
slug: fair-clustering
title: Fair clustering
summary: >-
  Chooses k centers so that every large enough group of agents gets nearby centers in proportion to its size. The axiom is proportionally representative fairness (PRF); SEAR always satisfies it in polynomial time, with a 3 or 1+√2 approximation to proportional fairness. Theory only: no experiments, and standard k-means-type objectives can violate PRF.
tags: [clustering, fairness, approximation-algorithms, social-choice]
papers: ["2304.13917"]
related: [k-means-clustering, algorithmic-fairness]
status: draft
updated_at: 2026-10-19
---

## Overview

The task is centroid selection. You have n agents, each a point in a metric
space, and you must place k centers. Standard objectives (k-center, k-median,
k-means) are NP-hard to optimise, and they are not built around proportional
representation [arxiv:2304.13917 §1].

The fairness axiom is proportionally representative fairness (PRF). Take any
set S of agents with at least ℓn/k members, whose largest pairwise distance is
y. Then at least ℓ centers must lie within distance y of some agent in S
[arxiv:2304.13917 §4]. A large, tight group therefore cannot be left with one
center while a small group gets several.

The paper aims for an axiom that implies unanimous proportionality (UP), is
always satisfiable, and does not need protected groups [arxiv:2304.13917 §1]
[arxiv:2304.13917 §3]. Two earlier notions miss this. Proportional fairness
(PF) is not guaranteed to exist, and core and individual-fairness notions do
not imply UP [arxiv:2304.13917 §3, Example 1, Example 2].

Every result is a theorem. The paper has no experiments [arxiv:2304.13917 §5].

### Measures of approximation

- **PF ratio.** How far a PRF outcome can be from a PF outcome, as a multiple
  of the best possible. A PRF outcome in an unconstrained metric space is
  (3+√17)/2 ≈ 3.56-approximate PF, and this bound is tight by example
  [arxiv:2304.13917 prop. 1] [arxiv:2304.13917 §4].
- **Discrete setting.** Centers come from a finite candidate set; the same
  bound becomes 1+√2 ≈ 2.41 for the algorithm below [arxiv:2304.13917 prop. 2].

## Variants

### Centers at agent locations: SEAR, Algorithm 1

The algorithm grows a radius through the sorted pairwise agent distances. At
each radius it picks a candidate whose ball holds at least n/k agent weight,
then removes n/k of weight from the agents inside that ball. Candidates start
as the agent locations. The paper notes that this is the discrete algorithm
with its candidate set equal to the agents [arxiv:2304.13917 alg. 1]
[arxiv:2304.13917 §5]. Output satisfies PRF [arxiv:2304.13917 thm. 1] and is
3-approximate PF [arxiv:2304.13917 lem. 2]. Running time is O(n² log n + kn²)
[arxiv:2304.13917 thm. 1]. Card:
[Proportionally Representative Clustering](/papers/2304.13917).

### Fixed candidate set: SEAR, Algorithm 2

Same loop, with two changes. The radii are agent–candidate distances, and the
candidates are a separate input set M. The output satisfies the discrete PRF
[arxiv:2304.13917 thm. 2], is (1+√2)-approximate PF [arxiv:2304.13917 prop. 2],
and runs in O(|M| n log n + k |M| n) [arxiv:2304.13917 thm. 2]. Card:
[Proportionally Representative Clustering](/papers/2304.13917).

### Stricter discrete variants (PRF-II, PRF-III)

The appendix defines stronger discrete versions. They can fail to exist, shown
on a line instance with n = 4 and k = 2 [arxiv:2304.13917 §A, Example]. Use the
discrete PRF from the body unless you have checked existence for your instance.

## When to use which

| Situation | Use | Why |
|---|---|---|
| Centers may be placed at agent locations | Algorithm 1 | 3-approximate PF, O(n² log n + kn²) [arxiv:2304.13917 lem. 2] [arxiv:2304.13917 thm. 1] |
| Centers must come from a fixed site list M | Algorithm 2 | Searches only M; 1+√2 PF ratio; cost grows with \|M\| [arxiv:2304.13917 prop. 2] [arxiv:2304.13917 thm. 2] |
| Distances are only a semimetric (no triangle inequality) | Either algorithm, for PRF only | PRF holds in semimetrics, but both PF ratios use the triangle inequality [arxiv:2304.13917 §4 footnote] [arxiv:2304.13917 lem. 2] [arxiv:2304.13917 prop. 2] |
| Proportional representation is the requirement | Either SEAR variant | Standard k-means, k-median and k-center can violate PRF on a three-circle instance [arxiv:2304.13917 §4 Example] [arxiv:2304.13917 fig. 3] |
| Agents may misreport locations | No variant here | Algorithm 1 is manipulable even for k = 1, and the paper gives no strategyproof variant [arxiv:2304.13917 §6] [arxiv:2304.13917 prop. 3] |
| Need measured runtime or quality | None available | The paper reports no experiments [arxiv:2304.13917 §5] |

## Implementation sketch

Language-agnostic core of the discrete algorithm. Algorithm 1 is the same
loop with M set to the agent locations.

```pseudocode
# Discrete SEAR  [arxiv:2304.13917 alg. 2]
# Input:  agents N, candidate list M, metric d, integer k
# Output: k centers drawn from M

def sear_discrete(agents, candidates, d, k):
    n = len(agents)
    # Every agent starts with weight 1  [alg. 2]
    weight = {i: 1.0 for i in agents}
    # Radii are the agent-candidate distances, sorted  [alg. 2]
    radii = sorted({d(i, c) for i in agents for c in candidates})
    centers = []
    idx = 0
    while len(centers) < k:
        r = radii[idx]
        # Unchosen candidates whose ball at r holds weight >= n/k  [alg. 2]
        ok = [c for c in candidates
              if c not in centers
              and ball_weight(c, r, weight) >= n / k]
        if not ok:
            # Nothing qualifies: widen the radius  [alg. 2]
            idx += 1
            continue
        # Any qualifying candidate; this picks the first  [§4]
        best = ok[0]
        centers.append(best)
        # Remove exactly n/k of weight from agents in the ball  [alg. 2]
        reduce_ball(best, r, weight, n / k)
        # Radius index stays put: several centers may share one radius
    return centers
```

Notes:

- The reduction is exact: n/k in total per center. How it is split across
  agents is free, for example equal shares or shares by distance [arxiv:2304.13917 §4 footnote] [arxiv:2304.13917 §7].
- Do not advance the radius after every pick. The PRF proof reasons about the
  state at each radius [arxiv:2304.13917 lem. 1], and the paper does not
  discuss the other variant.
- Tie-breaking is not stated. The sketch takes the first candidate in list
  order. The paper's approximation lower-bound example uses its own tie-break
  [arxiv:2304.13917 §4 Lemma 2]. Record the rule you use.
- Checking an arbitrary output against PRF means checking every subset S of
  agents. The paper gives no check procedure [arxiv:2304.13917 §4].

## Contradictions

None between papers. Only one card supports this page. Inside the source
paper, the table prints Greedy Capture's unconstrained PF ratio as ≈2.4, while
§2.1 cites a 2-approximation in Euclidean space. These are different settings,
and both are kept as printed [arxiv:2304.13917 tab. 1] [arxiv:2304.13917 §2.1].

## Papers

- [Proportionally Representative Clustering](/papers/2304.13917): defines PRF
  for centroid selection, gives SEAR for the unconstrained and discrete cases
  with their PF approximations, and shows the strategyproofness limits.