Check, Please: Verifiably Fair Clustering - arXiv 2605.12317 v2

Aug 22, 2026

Centroid-based clustering often optimizes global objectives and can miss the proportional representation of large, similar groups in the dataset. The work develops metric notions of proportionality for clustering, importing ideas from multiwinner voting. It studies the complexity of auditing proportional outcomes, proving that mPJR verification is coNP-complete and introducing mPJR+ and Default Coalitions mPJR+. Efficient verification algorithms are provided under restricted coalition structures.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages27

Reading Time1 h 8 min

AccessFree to download

Introduction

Proportionality in centroid-based clustering

Connection to social choice and justified representation

arXiv :2605 . 12317v2 [ cs .GT] 26 May 2026 Check, Please: Verifiably Fair Clustering Yu He, Jeremy Vollen, Edith Elkind Northwestern University [yuhe2030@u. northwestern. edu](yuhe2030@u. northwestern. edu), {vollen ,[edith. elkind](edith. elkind}@northwestern. edu)[}](edith. elkind}@northwestern. edu)[@northwestern. edu](edith. elkind}@northwestern. edu) 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 notions of proportionality that are 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 property enables us to evaluate the outputs of traditional algorithms that do not offer proportionality guarantees (such as e.g. , k-means) . A promising approach is to import proportionality notions from the setting of multiwinner voting with approval ballots. In particular, mPJR—the metric version of the well-known Proportional Justified Representation (PJR) axiom—satisfies (a), but up until now it was not known whether it satisfies (b) . In this work, we study the computational complexity of auditing proportional representation in clustering. In the approval setting, PJR is known to be coNPcomplete to verify; however, it admits a strengthening, known as PJR+, which satisfies (a) and (b) . We show that these results translate to the metric setting: we prove that mPJR is coNP-complete to verify, define a metric analog of PJR+, which we call mPJR+, and argue that mPJR+ satisfies (a) and (b) . However, the algorithm for auditing (m)PJR+ relies on repeated submodular minimization, rendering it impractical at scale, and we show that a natural combinatorial approach to verifying mPJR+ is infeasible. As a partial remedy, we propose an mPJR+ verification algorithm whose running time is exponential in the number of centers k, but quasilinear in the number of datapoints; it is practical if k is small, but does not scale well with k. Motivated by these hardness results, we introduce Default Coalitions mPJR+ (DC-mPJR+): a new proportionality concept that offers representation guarantees to a restricted set of coalitions around unselected centers, and, as a result, admitsan O (mn log n + mnk) verification algorithm. We establish that DC-mPJR+ outcomes can be computed efficiently and that DC-mPJR+ remains a meaningful proxy for global fairness: any solution satisfying γ-DC-mPJR+ also satisfies (γ + 2)-mPJR+ . 1 Introduction Clustering is one of the most fundamental tasks in computer science, with applications spanning unsupervised learning, data compression, information retrieval, image analysis, and computational biology. A particularly prominent clustering paradigm is centroid-based clustering, where one selects a set of representative centers and assigns each datapoint to a center. The quality of an outcome is typically measured by a global objective that aggregates the distances from each datapoint to its nearest cluster center using a suitable operator, such as sum (k-means), sum of squares (k-median), or max (k-center) [Jain et al. , 1999 , Xu and Wunsch, 2005 , Aggarwal and Reddy, 2014] . However, a growing body of work argues that, in many applications, centroid-based clustering should be evaluated not only by aggregate fit, but also by the way representation is distributed across different parts of the dataset. Specifically, it may be desirable to ensure that sufficiently large and similar groups of datapoints are allocated a fair share of cluster centers. This perspective connects clustering to broader questions of fairness, and in particular to notions of proportionality, which require that each group receives representation commensurate with their size. The study of proportionality is a burgeoning subarea of (computational) social choice. It dates back

FAQs

Why do centroid-based clustering methods need proportionality guarantees?

They often optimize aggregate distance objectives and may fail to represent large, similar groups fairly. Proportionality ensures each sufficiently large group receives a share of cluster centers commensurate with its size.

What is mPJR in this clustering fairness framework?

mPJR is the metric version of Proportional Justified Representation, translated from multiwinner voting to metric clustering. It is shown to be coNP-complete to verify in the auditing setting.

How does the paper address the impracticality of auditing mPJR+?

The auditing approach for (m)PJR+ depends on repeated submodular minimization, which is not scalable. The paper proposes DC-mPJR+, enabling an efficient verification algorithm and provides guarantees linking DC-mPJR+ to mPJR+.

Aug 22, 2026

Upload by Felix Montgomery