Check, Please: Verifiably Fair Clustering

Edith Elkind; Jeremy Vollen; Yu He

arxiv: 2605.12317 · v2 · pith:JYBFZ342new · submitted 2026-05-12 · 💻 cs.GT

Check, Please: Verifiably Fair Clustering

Yu He , Jeremy Vollen , Edith Elkind This is my paper

Pith reviewed 2026-05-13 03:23 UTC · model grok-4.3

classification 💻 cs.GT

keywords fair clusteringproportional representationmPJRDC-mPJR+verification algorithmSEARsocial choicecomputational complexity

0 comments

The pith

A new fairness notion for clustering can be checked efficiently while approximating full proportional representation guarantees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that verifying the standard mPJR fairness property for centroid-based clustering is computationally hard. To create a usable auditing tool, it defines DC-mPJR+ which restricts attention to coalitions of data points near unselected centers and supplies a fast verification procedure. Any clustering that satisfies a relaxed version of this restricted property also satisfies an approximate version of the original fairness condition. The SEAR clustering method always meets DC-mPJR+, giving practitioners a concrete way to test whether outputs from common algorithms such as k-means happen to be fair on particular datasets.

Core claim

We introduce Default Coalitions mPJR+ (DC-mPJR+) as a new proportionality concept that offers representation guarantees to a restricted set of coalitions around unselected centers, and as a result admits an O(mn log n + mnk) verification algorithm. DC-mPJR+ is satisfied by SEAR and any solution satisfying γ-DC-mPJR+ also satisfies (γ + 2)-mPJR+.

What carries the argument

Default Coalitions mPJR+ (DC-mPJR+), which restricts the coalitions that receive representation guarantees to those around unselected centers and thereby enables polynomial-time verification while preserving an approximation to full mPJR+.

If this is right

Verifying the original mPJR property is coNP-hard.
The stronger mPJR+ property can be defined but its direct verification requires repeated submodular minimization and is impractical at scale.
DC-mPJR+ is satisfied by the SEAR algorithm.
Any clustering meeting γ-DC-mPJR+ automatically meets (γ + 2)-mPJR+.
The O(mn log n + mnk) algorithm makes routine auditing of proportional representation feasible on moderate-sized datasets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Clustering pipelines could embed the verification routine to flag unfair outputs before deployment.
Algorithm designers might target DC-mPJR+ directly when designing new fair clustering methods.
The +2 additive gap leaves open the possibility of tighter proxies that still remain efficiently checkable.
On real data the method could be used to audit whether k-means solutions happen to deliver proportional representation without requiring changes to the underlying optimizer.

Load-bearing premise

That checking only coalitions around unselected centers still captures enough global fairness to serve as a meaningful proxy, as measured by the (γ + 2) approximation to mPJR+.

What would settle it

A concrete clustering instance and value of γ where the output satisfies γ-DC-mPJR+ yet violates (γ + 2)-mPJR+.

Figures

Figures reproduced from arXiv: 2605.12317 by Edith Elkind, Jeremy Vollen, Yu He.

**Figure 1.** Figure 1: Adapted from Example 4 of Aziz et al. [2024]: k-means/k-median may select {a0, b1, b2}, violating mPJR+ and DC-mPJR+; proportional alternatives include {a1, a2, b1} or {a1, a2, b2}. mPJR+ DC-mPJR+ Fairness notion 0.00 0.05 0.10 0.15 0.20 Satisfaction rate 10.3 13.8 16.5 15.0 10.5 14.6 18.1 16.5 bar labels: % Instance size n = 20 n = 50 n = 80 n = 100 [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗

read the original abstract

Popular centroid-based clustering methods are typically optimized for global objectives, and may fail to adequately represent large groups of datapoints. Thus, one needs proportionality notions suited for metric settings. Ideally, such notions should admit polynomial-time algorithms for (a) finding proportional outcomes, and (b) checking if a given outcome is proportional; the latter enables evaluation of traditional algorithms without proportionality guarantees (e.g., $k$-means). A promising approach imports proportionality notions from multiwinner voting with approval ballots. In particular, mPJR, the metric version of the well-known Proportional Justified Representation (PJR) axiom, satisfies (a), but whether it satisfies (b) was open. In this work, we study the computational complexity of auditing proportional representation in clustering. In the approval setting, PJR is coNP-complete to verify; however, it admits a strengthening PJR+, which satisfies (a) and (b). We show these results translate to the metric setting: mPJR is coNP-complete to verify, we define mPJR+, a metric analog of PJR+, and argue mPJR+ satisfies (a) and (b). However, auditing mPJR+ relies on repeated submodular minimization, rendering it impractical at scale, and a natural combinatorial approach is infeasible. As a partial remedy, we propose an mPJR+ verification algorithm exponential in $k$ but quasilinear in the number of datapoints. Motivated by these hardness results, we introduce DC-mPJR+: a proportionality concept offering representation guarantees to a restricted set of coalitions around unselected centers, admitting an $O(mn \log n + mnk)$ verification algorithm. DC-mPJR+ outcomes can be computed efficiently, and any $\gamma$-DC-mPJR+ solution satisfies $(\gamma + 2)$-mPJR+.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a practical auditing method for proportional fairness in clustering by defining DC-mPJR+ as a restricted, efficiently checkable proxy that still approximates the stronger mPJR notion within a factor of 2.

read the letter

The main takeaway is that verifying the full mPJR fairness notion in metric clustering is coNP-hard, but the authors introduce DC-mPJR+ over default coalitions around unselected centers, which admits an O(mn log n + mnk) verification algorithm, is satisfied by SEAR, and implies a (γ + 2)-mPJR guarantee. This is a direct and useful extension of the PJR+ idea from voting to the clustering setting. The hardness result for mPJR is standard but cleanly stated, and the move to a restricted but verifiable notion with an explicit approximation trade-off is the real contribution. They also show the verification procedure works without repeated submodular minimization, which addresses the scalability issue they flag for mPJR+ itself. The work is grounded in the metric assumption and presents the +2 gap transparently as the cost of the restriction rather than hiding it. No internal contradictions appear in the claims, and the citation pattern to prior proportionality work in social choice and clustering looks appropriate. One minor soft spot is that the default-coalition restriction could leave some fairness gaps on particular inputs even with the approximation bound, though the paper does not overclaim what it delivers. The +2 factor itself might be loose in some cases, but again this is acknowledged. This paper is for researchers in fair machine learning and computational social choice who care about making proportionality checks implementable rather than purely existential. A reader working on auditing or deploying fair clustering algorithms would find the verification routine and the SEAR example directly usable. It deserves a serious referee because the results are new, the algorithmic claims are concrete, and the theoretical relation to existing notions is spelled out without circularity or unexamined fitting.

Referee Report

0 major / 2 minor

Summary. The paper proves that verifying mPJR (Proportionally Representative Fairness) in centroid-based clustering is coNP-hard. It introduces mPJR+ as a metric analog of PJR+ but shows its verification is impractical due to repeated submodular minimization. It then defines DC-mPJR+ (Default Coalitions mPJR+), which restricts proportionality guarantees to coalitions around unselected centers and admits an O(mn log n + mnk) verification algorithm. The paper shows that the SEAR algorithm satisfies DC-mPJR+ and that any solution satisfying γ-DC-mPJR+ also satisfies (γ + 2)-mPJR+.

Significance. If the results hold, the work supplies a computationally tractable auditing tool for proportional fairness in clustering while preserving a concrete approximation guarantee to the stronger mPJR notion. This directly addresses the practical gap between theoretical fairness concepts and verifiable outputs of standard algorithms such as k-means. The explicit complexity bound and the SEAR satisfaction result are concrete strengths that could enable routine fairness checks.

minor comments (2)

The abstract states the O(mn log n + mnk) verification complexity; the main text should explicitly define the parameters m, n, and k at the first use of this bound and include a brief derivation sketch or reference to the relevant lemma.
The relationship 'any γ-DC-mPJR+ solution satisfies (γ + 2)-mPJR+' is central; ensure the proof in the relevant section is self-contained and does not rely on external results without clear citation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. We appreciate the recognition that DC-mPJR+ provides a practical, verifiable auditing tool while preserving an approximation to the stronger mPJR notion.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines new concepts (mPJR+, DC-mPJR+) from first principles as restricted variants of prior proportionality notions, then derives the verification algorithm complexity and the (γ+2) approximation bound directly from those definitions and the structure of default coalitions. No step reduces a claimed result to a fitted parameter, self-referential equation, or load-bearing self-citation; the +2 factor is explicitly derived as the cost of the restriction rather than assumed. The work is self-contained against external benchmarks with independent proofs of hardness, satisfiability by SEAR, and algorithmic runtime.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper relies on standard assumptions from computational complexity and metric spaces for clustering; it introduces new fairness definitions rather than new physical entities or fitted parameters.

axioms (1)

domain assumption Clustering occurs in a metric space where distances satisfy triangle inequality
Invoked implicitly for the definitions of mPJR and its variants in the clustering setting.

invented entities (1)

DC-mPJR+ no independent evidence
purpose: A restricted proportionality concept for efficient verification in clustering
Newly defined in the paper as coalitions around unselected centers to enable polynomial-time auditing.

pith-pipeline@v0.9.0 · 5581 in / 1385 out tokens · 95136 ms · 2026-05-13T03:23:22.878166+00:00 · methodology

Check, Please: Verifiably Fair Clustering

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)