Proportionally Representative Clustering

In plain words

You want to place k centers in a space of points, one per agent, so that the agents are fairly represented. Ordinary clustering methods such as k-means only ask how close each person is to their nearest point. That can leave a large, tight group of people with a single point while a small group gets several.

The paper asks for a fairness rule that counts groups instead. If a group is big enough to deserve some number of points, and its members sit close together, then enough points should lie near that group. The authors show that such a rule always has a solution, and they give a simple greedy procedure that finds one in polynomial time. The procedure hands out "weight" to the people and lets each one spend it on the nearest good spot, a little like a voting rule. The paper is theoretical: it proves its guarantees and does not report experiments.

TL;DR

• Defines proportionally representative fairness (PRF) for centroid selection, in an unconstrained (any location) and a discrete (finite candidate set) version §4 §5.
• SEAR (Algorithm 1 unconstrained, Algorithm 2 discrete) always outputs k centers that satisfy PRF, in polynomial time [thm. 1] [thm. 2].
• Unconstrained SEAR is a 3-approximation to Proportional Fairness (PF) in metric spaces; discrete SEAR matches the best known (1+√2) PF guarantee [Lemma 2] [Prop. 2].
• Standard k-means, k-median and k-center can violate PRF; no strategyproof algorithm satisfies PRF in the discrete case for k = 2 under the order-statistic dominance notion used §4 §6.

Problem

Centroid selection: given agents (data points) N in a metric space, candidate centers M (M = the whole space in the unconstrained case), and k, choose k centers §1. Standard objectives (k-center, k-median, k-means) are NP-hard to optimise and are not built around proportional representation §1.

Two earlier concepts are shown to be insufficient:

• Proportional Fairness (PF): a group of at least ⌈n/k⌉ agents must not all prefer an unselected center to their nearest selected one §3, Def. 1. PF is not guaranteed to exist §3, Example 2 fig. 1.
• Core fairness (LLS+21a), and the individual-fairness concept of JKL20a, do not imply unanimous proportionality (UP). UP says that a group of ℓ⌈n/k⌉ co-located agents must get ℓ centers at or nearest their location §3, Def. 2 §3, Example 1.

The paper's aim is an axiom that implies UP, is guaranteed to be satisfiable, does not need protected groups, and implies an approximate PF guarantee §1 §3.

Method

Axiom (PRF), unconstrained. An outcome X with |X| = k satisfies PRF if, for every set S of agents with |S| ≥ ℓn/k whose pairwise maximum distance is y, at least ℓ centers of X lie within distance y of some agent in S [§4, Definition]. The paper states the size threshold in terms of ℓ without saying explicitly that ℓ is an integer; the counting in the proofs treats it as one §4, Lemma 1.

Axiom (PRF), discrete. For every S with |S| ≥ ℓn/k, let ℓ′ ≤ ℓ be the number of candidates in M that lie within distance y of all agents in S, where y is the radius needed for that set. Then at least ℓ′ centers of X must lie within distance y of some agent in S §5, Definition.

Algorithm 1 (SEAR, unconstrained) alg. 1. The algorithm grows a radius over all pairwise agent distances, in increasing order. At each radius, it selects any candidate whose radius-ball carries agent weight at least n/k, then removes exactly n/k of that weight from the agents in the ball. A radius is only advanced when no candidate qualifies, so several centers can be chosen at the same radius alg. 1 §4.

# SEAR, unconstrained  [alg. 1]
# Input:  agents (points), metric d, integer k
# Output: list of k centers, drawn from the agent locations

def sear_unconstrained(agents, k):
    # Every agent starts with weight 1  [alg. 1]
    weights = {i: 1 for i in agents}
    # Candidates start as the agent locations  [alg. 1]
    candidates = set(agents)
    # Radii are the pairwise agent distances, sorted  [alg. 1]
    radii = sorted(d(i, j) for i in agents for j in agents)
    centers = []
    radius_index = 0
    while len(centers) < k:
        radius = radii[radius_index]
        # Candidates whose ball carries weight at least n/k  [alg. 1]
        supported = [
            c for c in candidates
            if weight_within(c, radius, weights) >= len(agents) / k
        ]
        if not supported:
            # Nothing qualifies: widen the radius  [alg. 1]
            radius_index += 1
            continue
        # Take the candidate with the largest supported weight  [alg. 1]
        best = max(
            supported,
            key=lambda c: weight_within(c, radius, weights),
        )
        centers.append(best)
        candidates.remove(best)
        # Remove exactly n/k of weight from agents in the ball  [alg. 1]
        # The split of that reduction across agents is not fixed  [§4]
        reduce_weight_in_ball(best, radius, weights, len(agents) / k)
    return centers

Here weight_within(c, r, w) sums the weights of agents at distance ≤ r from c. The feasibility of the reduction follows from the selection test, which checks the same ball alg. 1.

Algorithm 2 (SEAR, discrete) alg. 2. Same loop, with two differences: the radii are the agent–candidate distances, and candidates are a separate input set M, not the agent locations. The paper notes that Algorithm 1 is Algorithm 2 run with M set to the agent locations §5.

Reweighting. The paper allows any reduction that removes exactly n/k in total from the agents in the ball, for example equal reduction or reduction proportional to distance from the chosen center. Its results do not depend on which is used §4, footnote §7.

Approximation to PF. A PRF outcome in a metric space is (3+√17)/2-approximate PF [prop. 1]. Algorithm 1's output is 3-approximate PF [lem. 2]. A PRF outcome in the discrete setting is (1+√2)-approximate PF [prop. 2]. Each step uses the triangle inequality.

Strategyproofness §6. Algorithm 1 is not strategyproof even for k = 1 (it reduces to the midpoint mechanism for two agents on a line). No anonymous, PF, strategyproof algorithm exists for k = 1 in the unconstrained setting [prop. 3]. Under the order-statistic dominance notion defined in the paper, no algorithm is both PRF and order-statistic strategyproof for k = 2 in the discrete setting, when m ≥ 4 and n is even [thm. 3].

Hyperparameters

The paper has no training hyperparameters; the table lists the algorithm's inputs and constants.

Results

No experimental results. The paper's experiments section is commented out in the source §5, end. The results are theorems. All are author-reported proofs.

Setup: metric spaces; n agents, k centers. Baselines are the best previously known PF guarantees.

Table 1 also 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 the card keeps both as stated tab. 1 §2.1.

Paper vs code

No official code. A search of GitHub, the arXiv abstract page and the paper's own links found no repository owned by the authors. Hits from keyword searches were unrelated or third-party, and were not used.

Pitfalls

• Exponential definition. PRF quantifies over all subsets S of agents, and the paper says so directly §4. The algorithm avoids checking these subsets. Checking an arbitrary outcome against the definition is not addressed by the paper and should be assumed hard.
• Order of radii matters. After a center is selected, the radius index does not advance; several centers can be chosen at one radius alg. 1. The PRF proof reasons about the algorithm's state at each radius [lem. 1], so advancing the radius after every selection would be a change from the listing. The paper does not discuss that variant.
• Reduction must be exact. The weight removed per center is exactly n/k. The selection test uses the same ball, so the reduction is always feasible alg. 1. Agents' weights may reach zero.
• Tie-breaking is not specified. The algorithms say only "some candidate". The PRF proof does not depend on the choice. The approximation lower-bound example relies on a specific tie-break §4, Lemma 2. Pick a deterministic rule and document it.
• Triangle inequality. The PRF guarantee holds in general semimetric spaces §4, footnote on lem. 1. The PF approximations do not; they use the triangle inequality [lem. 2] [prop. 1] [prop. 2].
• Greedy Capture is not a substitute. Greedy Capture and ALG_g can fail to output k centers, and do not satisfy unanimous proportionality §5, Remark 1. Re-running them on the remaining centers does not in general give PRF.
• Discrete PRF-II and PRF-III can fail to exist. The paper gives an instance with n = 4, k = 2 on a line §A, Example. The discrete PRF in the body is the version guaranteed to exist.
• Not strategyproof. Algorithm 1 is manipulable even for k = 1 §6. The paper gives no strategyproof variant.
• Method of Equal Shares is not a shortcut. Turning distances into utilities (inverse distance) and running MES does not give PRF §B, Example.
• Standard centroid objectives can miss PRF. On the three-circle instance, k-means, k-median and k-center can each place two centers in the big circle and one between the small ones §4, Example and fig. 3. The paper says the big circle must be "sufficiently large"; no threshold is given.
• Experiments are absent. The experimental section is commented out in the source §5. No runtime or quality measurements exist in the paper.

Lineage

• Builds on: the Expanding Approvals Rule of Aziz and Lee (AzLe19a), which uses reweighting of voters; SEAR adds spatial information to the reweighting §1 §2.2.
• Compared against: Greedy Capture (CFLM19a discrete; MiSh20a unconstrained) tab. 1; core-fairness ALG_g (LLS+21a) §3; individual fairness (JKL20a) §2.1; and the Method of Equal Shares (PPS21a) §B.
• Follow-up: Kellerhals and Peters (KePe24b) relate PRF to approval-based PJR and analyse the approximation relations between these axioms §2.1.