Fair clustering

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 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 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 2304.13917 §1 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 2304.13917 §3, Example 1, Example 2.

Every result is a theorem. The paper has no experiments 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 2304.13917 prop. 1 2304.13917 §4.
• Discrete setting. Centers come from a finite candidate set; the same bound becomes 1+√2 ≈ 2.41 for the algorithm below 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 2304.13917 alg. 1 2304.13917 §5. Output satisfies PRF 2304.13917 thm. 1 and is 3-approximate PF 2304.13917 lem. 2. Running time is O(n² log n + kn²) 2304.13917 thm. 1. Card: Proportionally Representative Clustering.

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 2304.13917 thm. 2, is (1+√2)-approximate PF 2304.13917 prop. 2, and runs in O(|M| n log n + k |M| n) 2304.13917 thm. 2. Card: Proportionally Representative Clustering.

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 2304.13917 §A, Example. Use the discrete PRF from the body unless you have checked existence for your instance.

When to use which

Implementation sketch

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

# 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 2304.13917 §4 footnote 2304.13917 §7.
• Do not advance the radius after every pick. The PRF proof reasons about the state at each radius 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 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 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 2304.13917 tab. 1 2304.13917 §2.1.

Papers

• Proportionally Representative Clustering: defines PRF for centroid selection, gives SEAR for the unconstrained and discrete cases with their PF approximations, and shows the strategyproofness limits.