Unifying Proportional Fairness in Centroid and Non-Centroid Clustering
Authors: Benjamin Cookson
Nisarg Shah
Ziqi Yu
Venue: NeurIPS 2025 spotlight ()
Keywords: Proportional Fairness
Clustering
Algorithmic Fairness
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We design proportionally fair clustering methods when each agent's loss function is determined by both its distance from the other agents in its cluster and to a representative agent in its cluster.

Abstract: Proportional fairness criteria inspired by democratic ideals of proportional representation have received growing attention in the clustering literature. Prior work has investigated them in two separate paradigms. Chen et al. [ICML 2019] study _centroid clustering_, in which each data point's loss is determined by its distance to a representative point (centroid) chosen in its cluster. Caragiannis et al. [NeurIPS 2024] study _non-centroid clustering_, in which each data point's loss is determined by its maximum distance to any other data point in its cluster. 
  
We generalize both paradigms to introduce _semi-centroid clustering_, in which each data point's loss is a combination of its centroid and non-centroid losses, and study two proportional fairness criteria---the core and, its relaxation, fully justified representation (FJR). Our main result is a novel algorithm which achieves a constant approximation to the core, in polynomial time, even when the distance metrics used for centroid and non-centroid loss measurements are different. We also derive improved results for more restricted loss functions and the weaker FJR criterion, and establish lower bounds in each case.

Unifying Proportional Fairness in Centroid and Non-Centroid Clustering
Benjamin Cookson
Nisarg Shah
Department of Computer Science University of Toronto bcooksondcs. toronto..... edu
Department of Computer Science
University of Toronto
nisargoca toronto... misargaca.toronto
edu
Ziqi Yu Department of Computer Science
University of Toronto ziqiyuêcs.. toronto edu
Abstract
Proportional fairness criteria inspired by democratic ideals of proportional represen- tation have received growing attention in the clustering literature. Prior work has investigated them in two separate paradigms. Chen et al. [1] study centroid cluster- ing, in which each data point's loss is determined by its distance to representative point (centroid) chosen in its cluster. Caragiannis et al. [2] study non-centroid clustering, in which each data point's loss determined by its maximum distance to any other data point in its cluster.
We generalize both paradigms to introduce semi-centroid clustering, in which each data point's loss is a combination its centroid and non-centroid losses, and study two proportional fairness criteria-the core, and its relaxation, fully justified representation (FJR). Our main result a novel algorithm which achieves constant approximation to the core, in polynomial time, even when the distance metrics used for centroid and non-centroid loss measurements are different. We also derive improved results for more restricted loss functions and the weaker FJR criterion, and establish lower bounds each case.
Introduction
Clustering is central task in AI, in which the goal is to either partition of n data points into clusters Ci...., Ck. or return & centroids Zi...., Tkk perhaps return both the clusters and their assigned centroids. In many cases, partitioning the data points and choosing centroids are viewed as interchangeable. For example, in the traditional clustering setting, the popular k-means loss function (to be minimized) can be written in two equivalent forms:
k
min Ch
Σ IJEC
d(i,j)²
min
Σ
Σ d(i, IEC
C.
Co
This is because for a given partition (C1. Ck), the optimal choice of the centroid v, for each cluster C₁ is the average of its points (this can be generalized to non-Euclidens metrics too) and plugging in these optimal choices yields the formulation on the left.
An emerging line of research at the intersection of economics and AI focuses on applications which every data point represents agent, and studies facets such dealing with strategic manipulations
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

by selfish agents [3-7] or ensuring faimess to the agents [8-10]. Here, it not sufficient to have only a global loss function be minimized; one needs know the loss functions (i.e., preferences) the individual agents and different formulations of loss functions at the agent level, even if equivalent in the aggregate, lead different results.
Our focus is on fairness saimess--seccificllly on proportional fairess. Informally, it provides fairness guarantee to every possible group of agents-nol just just those determined by a limited set of sensitive attributes such as race and gender, or their intersections- proportionally the group size and cohesiveness of its members' preferences. Proportional faimnsss criteria have been applied to growing number of problems in AI [1, 9-13].
the strength of the guarantee scaling
For clustering, Chen al. [1] initiate the study of proportional faimess for centroid clustering. in which the loss of an agent is its distance to the centroid of its cluster. They motivate it through facility location, in which the goal is to build k facilities; each agent naturally prefers be close to its assigned facility. Caragiannis et al. [2] study proportional fairness for non-centroid clustering, in which the loss of an agent an aggregate (e.g., average or maximum) of its distances to the other agents in its cluster. Their motivation stems from clustered federated learning, in which data sources (agents) are partitioned into clusters and agents in each cluster collaboratively learn a model; each agent then wishes to be close (in terms of their data distributions) to the other agents in its cluster, so that the model they collaboratively learn is accurate for the agent personally.
But in both these applications, and in many others, may be natural for agents to care about both their distance to the centroids of their clusters and their distances the other agents in their clusters. For example, in facility location, an individual may want their assigned facility to be close to their house well other individuals using the same facility to also be from their neighborhood, which makes it more likely to bump into friends and acquaintances. In clustered federated learning, the centroids may represent the models collaboratively learned by the different clusters of agents. An agent may care about both the model being effective for their own data distribution and the other agents in their cluster having data distributions similar to their own, such cohesion can be important to inducing trust and cooperation within the cluster.
It may even be the case that agents' preferences formed out of combination of centroid and non-centroid losses that are induced by completely different metric spaces. When a teacher groups students together for final class projects, students' preferences for which group they placed in would depend on the project topic that group is assigned (centroid) and which other students are in that group (non-centroid). Two students may be very close friends but have completely different opinions on project topics.
This motivates us to initiate the study of proportional faimess for natural generalization of centroid and non- con-centooid clustering that we term semi-centroid clustering, in which the loss of each agent is function of both the cluster of agents C it is part of (i.e., i C₂) and the centroid z; assigned to this cluster.
By leveraging approaches common in the works of Chen et al. [1] and Caragiannis et al. [2], along with novel and intricate techniques we develop, we are able to attain desirable proportional fairness guarantees for semi-centroid clustering.
1.1 Our Results
Dual Metric Loss
Weighted Single Metric Loss
Core
FJR
Core
FJR
Existential Upper Bound
3
min(?/X,
Efficient Upper Bound
3 + 2
min (2/x, fx}
(4,,,4
Lower Bound
2
1
max(gg.
2(1-A) 2X+1
Table 1: Core and FJR approximations for semi-centroid clustering under dual metric loss and
weighted single metric loss. Here, fA = +13 and gA = 22--2455-+11
2-21

---

clustering algorithm takes set of n data points (agents) as input and returns both a A (Ci..... C&)) of the data points and the corresponding centroids (Z1,...,<x)) The loss of partition
each agent E C2 is measured by a loss function (,C,, 24), which depends both on the cluster C2 it
belongs to and its centroid 7++- While some of our results apply to arbitrary loss functions, most focus on two structured families. Dual metric loss measures the sum of agent i's distance to its centroid a according to a metric d' and its maximum distance to any agent j E C, in its cluster according to a different metric d'a Weighted single metric loss is the special case in which both metrics are scaled versions of a common metric, i.e., d= = (1 - X) d and dm A for some metric d and À E [o, 1].
We investigate (multiplicatiiee approximations of) two proportional faimess criteria studied in prior work on centroid and non-centroid clustering: the core, and its relaxation, fully justified representation (FJR). Intuitively, when forming k clusters given n data points, the core demands that there is no set S of at least n/K agents, who proportionally deserve to able form cluster, and a feasible centroid y such that every member of 5 prefers (S, y) to its currently assigned cluster. FJR puts a greater demand on successful violations: even the maximum loss of any agent E for (S. y) should be lower than the minimum loss of any agent i E S under the algorithm's 's clustering.
First, we show that none of the algorithms developed in prior work for centroid or non-centroid clus- tering work in our more general paradigm of semi-centroid clustering, even for the restricted family of weighted single metric loss. Then, for both loss families, we obtain core and FJR approximation guarantees, both existential and polynomial-timg time attainable, by designing novel algorithms, and prove (existential) lower bounds. Our main results are summarized in Table 1.
Finally, we also evaluate the performance of our algorithms on real-world datasets in Appendix F. We observe that our algorithms consistently achieve hear-perfect approximations of the fairness notions we consider, beating both the theoretical worst-case bounds we establish, and the performance of classical clustering algorithms such as k-means++. We also show that they achieve these guarantees while sacrificing classical clustering objectives only slightly. This generalizes similar observations for centroid and non-centroid clustering in prior work [1, 2].
1.2 Related Work
As mentioned above, there are several existing papers studying proportional fairness in clustering. Chen et al. [1] are the first to introduce the notion of the core for centroid clustering, and use the Greedy Capture algorithm to achieve (1 + apppoxxpoinnnoooonn to the core. Micha and Shah [14] improve the approximation factor to 2 for the Euclidean I.2 metric in the "unconstrained setting" where the centroids can be placed anywhere in R Aziz et al. [15] observe that in this unconstrained setting, instead of the infinitely many possible centroid locations, one can focus on just the n agent locations and achieve a constant approximation to the core in polynomial time. Li et al. [16] study a stronger criterion than the core. Caragiannis et al. [2] study proportional fairness in non-centroid clustering, and use variation of the Greedy Capture algorithm the maximum- -iinuunne loss. They also study FJR as a weakening of the core. Ebadian and Micha [17] use the centroid clustering framework to study the problem of sortition. In this setting, they make the set of possible centroids equal to the set of agents, and look for a lottery over centroid clusterings with the property that each agent has an equal probability of being selected centroid in the chosen clustering. They achieve such a lottery with ex-post proportional fairness guarantees using an algorithm inspired by Greedy Capture.
achieve 2-core with respect to
Li et al. [18] study a similar graph-based problem of partitioning friends into groups, which is equivalent to non-centroid clustering, albeit when each person has a utility (rather than a loss) of I for every friend of theirs placed in their cluster. Arkin et al. [19] look at the muulti-dimensioall geometric stable roommates problem, which is equivalent to the non-centroid clustering model of [2], but focus on special cases such as & n//s.
Finally, other fairness notions have also been investigated for clustering (see the survey by Chhabra et al. [20]). The most prominent one assumes that every data point belongs to one of many classes, and certain protected classes must have equal representation across the clusters [21, 22).
3

---

2 Preliminaries
2.1 Clustering Model
semi-centroid clustering instance is a tuple (A, M., MM,,,,, where N is a set of n agents; M is of possible cluster centers; & {C N : C) M R2 is the loss function of agent i E N, with (, x) being the loss incurred when it is part of cluster C' and assigned cluster center x; and k E N is the number of clusters to be returned by the algorithm.
clustering algorithm takes such an instance and returns a clustering X ((C1, ((CI, (()(CC.))).....C (CK, where (C1, ..... (C...... for all distinct L, l' E [R:). We refer to each tuple (c) ) E X as cluster, with Ct as the member set (and the agents in C. as the members) of the cluster and I; as the center assigned to the cluster.
Ck) is disjoint partition of the set of agents N (so, UsE[k] C2 N and Cince =
Given a clustering X' and an agent i E N, let (i) denote the (unique) index of the cluster of which is a member (i.e., i E Cras) The loss incurred by each agent E A under clustering X' is e;( (CCr))) (x)()), which, with slight abuse of notation, also write as (2t) for brevity.
2.2 Loss Functions
Some of our results hold for arbitrary loss functions as defined above. However, the more interesting results are obtained for two structured families of loss functions that naturally combine previously- studied loss functions for centroid and non-centroid clustering.
Dual metric loss: We are given two distance metrics.' ! a centroid metric de : x M - R30 and a non-centroid metric dmm : x N Rgz-- Given clustering X' and agent E A,, the centroid metric induces its centroid loss (x) & (ix))))))) which measures the distance of agent é to its assigned center, and the non-centroid metric induces its non-centroid loss (x"(X) maxjeCxm1 d' (i) which measures the maximum distance of agent i to any other agent in its cluster. The former the canonical loss function used for centroid clustering [1, 14, 15, 23] while the latter is loss function for which appealing fairness guarantees have been derived for non-centroid clustering [2].
The overall dual metric loss of agent é is the sum of the centroid and non-centroid parts:
(x(x) (X) + (x)) max d' (i.jj + d' (1,
jECx()
is worth remarking that adding scaling factors so that (x))) a CTH (x) + 3- (x)( for some a, B > 0 would not make the family any more general; one can instead just use d = dm and d= B dd as the new non-centroid and centroid metries, respectively.
Weighted single metric loss: A special case of dual metric loss is where both centroid and non- centroid losses use (scaled versions of) the same metric d (W U M) x (N M) + RR Rzo- That is, for some À E [0, 1), we have d (i. X- d(i, j) for all i.j E N and (i, = (1 A) d((i for all i E N and x E M,, so that the overall loss is given by
(x(X) = X max d(i.j) + (1- d(i, x(i)) jECx()
Once again, note that using arbitrary non-negative scaling factors a and / instead of and does not offer any further generalization one can equivalently use X a+3
Non-centroid and centroid clustering are easily seen special cases of the weighted single metric loss (which is, in turn, a special case of the dual metric loss) with À = and X = 0, respectively. Hence. the semi-centroid clustering algorithms we design for dual metric loss and for weighted single metric loss can be used for both centroid and non-centroid clustering.
2.3 Proportional Fairness Guarantees
We focus on two proportional fairness criteria prominently studied by prior work.
MMore precisely, these are pseudometrics. A pseudometric d: X x X + R20 satisfies d(x, x) = 0 for all E X. d(x,, y) d(y.z) for all y X, and d(z, & d(x, z) + d(z,, a) for all x, y, X.

---

Definition 1 (The Core). For > 1, clustering X' = if there is no group of agents S C .V' with |s| > n/k and feasible center y M such that a (S < (x) for all i E S (if this happens, we say that coalition S deviates with center y).
is in the a-core
In words, no group S of at least n/4 agents, which proportionately deserves a cluster center represent- ing it, can unilaterally improve by being a cluster of its own with a feasible center
The second criterion is relaxation that imposes higher bar on deviating coalitions.
Definition 2 (Fully Justified Representation (FJR)). For a > 1. a clustering X =
{(C2, (C2, } is a-FJR if there is group of agents S C .V with |S| > n/k and feasible center y E M such that a (, y) < minjes (2*) for all i E S.
That is, the new loss for each member of the deviating coalition, scaled by a, should not only be less than its own loss prior to deviation, but less than the loss of any deviating member prior to deviation. It is then clear that a-FJR is a relaxation of a-core for all a 2 1.
Proposition For every a S 1, every clustering in the a-core is also a-FJR.
Due to space constraints, proofs missing from each section of the main body are presented in the correspondingly titled section of the appendix.
3 Greedy Capture Algorithms
In prior work on proportionally fair clustering, the Greedy Capture algorithm has been the go-to way to achieve a constant approximation of proportional fairness criteria in both the centroid and non-centroid worlds. Chen et al. [1] introduce it for centroid clustering and Caragiannis et al. [2] adapt it to non-centroid clustering. The centroid and non-centroid variants, presented formally as Algorithms 2 and respectively in Appendix B, share many similarities. In both variants, every agent starts off as "uncaptured" and a number of balls start growing at the same rate. As soon as a ball covers at least "/k uncaptured agents, captures them and becomes "open" (and in the centroid variant, the center of the open ball is added as one of at most &s cluster centers to be selected by the algorithm). But the two variants differ in three key dimensions.
1. Where the balls grow: In the centroid version, a ball grows around every feasible cluster center. In the non-centroid version, which has centers, one grows around each agent.
2. Whether open balls keep growing: In the centroid variant, a ball continues to grow after it opens, capturing any uncaptured agents as soon as it covers them. In the non-centroid variant, a ball stops growing once it opens. This is intuitive because an open ball that grows and captures an agent far away would not worsen previously-captured agents in the centroid paradigm, but would do so in the non-centroid paradigm.
3. Whether agents switch clusters in the end: In the centroid variant, the algorithm simply returns set of (up to) lo cluster centers and each agent's loss is their distance the nearest cluster center. Note that this may not be the center of the ball that captured it as the algorithm may have added a closer center afterwards. Hence, the set of agents captured by ball when it opens may not form a single cluster. In the non-centroid variant, there is no "switching" in the end and the set of agents captured by ball together do form a cluster. This is again because allowing an agent to switch to a different cluster she prefers could significantly worsen existing agents in that cluster.
Chen et al. [1] prove that centroid greedy capture yields clustering in the (1 + 22)-core in the centroid paradigm, and Caragiannis et al. [2] prove that non-centroid greedy capture yields a clustering in the 2-core in the non-centroid paradigm. This naturally raises the question: Can some variant of greedy capture get a constant approximation to the core in the semi-centroid clustering paradigm?
Unfortunately, we can show that solving the semi-centroid paradigm is not that simple. To see why. it is sufficient to consider the restricted case of the weighted single metric loss, in which the loss function is characterized by a single metric d and a parameter À E [0. 1]. Note that the greedy capture algorithms only take in d as input, and not X. Thus, for (some variant of) greedy capture to achieve a-core with respect to the weighted single metric loss (for any À E [0. 1)). it must achieve a-core with respect to the non-centroid loss (A = 1) and the centroid loss (A = 0) simultaneously. In our first result, we show that no algorithm can achieve such simultancous guarantee.
5

---

Theorem 1. For every a > 1 and 5 > 1, there exists semi-centroid clustering instance in which no clustering simultaneously the a-core with respect to the centroid loss and in the B-core with respect to the non-centroid loss.
4 The Core
Given Theorem switch our attention rules that do simply take single metric d as input; that is, for the weighted single metric loss, they also take À as input, and for the more general dual metric loss, they take both the centroid and non-centroid metrics, de and dm inputs.
In Section 4.1, we present results for the dual metric loss. Later, Section 4.2, we present improve- ments for the restricted case of the weighted single metric loss.
4.1 Dual Metric Loss
Algorithm 1: Dual Metric Algorithm
Input:
Set of agents N, set of feasible cluster centers M, non-centroid metric d'x centroid metric d", number of centers k2 growth factor e > 1, MCC approximation factor a 21)...,,,.CA
Output: Clustering X'
Initialize: N" N, X < 0, t
// Phase 1: Build a tentative clustering X
2 while N" * do
// Uncaptured agents remain // Find an a-MCC cluster (c), and save its maximum loss as rt
(2),, < An a-most cohesive cluster (of threshold n/k) from N", rt f max ((C,,
// Add the cluster to X and mark agents as captured X 8U x(C),
NO - Cr:
1+1+1:
// Phase 2: Selectively allow agents to switch to better cluster
Vt E [k]. C. Cr: for i N do
t + 8(1;;
// Clusters agent can switch to without harming its members too much
V, + e E [k] Vj Cv,d'(j,ze) d'" crrr;;
// Among them, agent picks one minimizing an upper bound on its loss
1" + arg argmineev; (d mN) +e.ry + minjed, (d'" ((,,))
di
12
// And switches to it if that improves the upper bound on its loss if df + r-r + min (d." d'(j < c then
C. C. (i);
15
C + C-- (i):
16 return = ((C1, (..
The following two are the most significant and the most intricate results of our work.
Theorem 2. For the dual metric loss, there always exists clustering in the 3-core.
Theorem 3. For the dual metric loss, a clustering in the (3 + 22/3) can be computed in polynomial time.
To understand Algorithm 1, first we need to introduce the Most Cohesive Cluster problem, defined by Caragiannis et al. [2] for non-centroid clustering. Adapted to our semi-centroid clustering setting, it simply requires finding the cluster (C, .)) with Cl > n/2 that minimizes the maximum loss incurred by any agent in C. This is defined and approximated for arbitrary loss functions follows.

---

Definition 3 (a-MCC), For > 1, and given set of agents N, a set of centers M, a loss function L, and a threshold (typically */k), cluster (C S N. E M) with |C] min([W]0 is an a-approximate most cohesive cluster (in short, an a-MCC cluster) if maxiec (C,,z) & a maxies (,(S,y) y) for every cluster (S C N. E M) with |S| > min((M))0). When a 1, it is simply called most cohesive cluster.
Caragiannis et al. [2] use this in place of the greedy capture subroutine, which finds the cluster (C, x) with the smallest radius maxec d(i, 2)), in order to obtain improved fairesss guarantees. Theorems 2 and 3 are both obtained using Algorithm I, which calls a subroutine that finds an a-MCC cluster; Theorem 2 is obtained by inefficient subroutine that finds an MCC cluster, while Theorem 3 is obtained by plugging in an efficient subroutine we design for computing a 4-MCC cluster.
Algorithm description: Algorithm I is split into two phases. Phase I works by iteratively finding an a-MCC cluster with respect to the dual metric loss and adding it to a tentative solution. We denote the clustering found in Phase by X = {(C1, Tn .i),..., (Cs, 3=a)]. For each cluster (C,, E &, the algorithm stores the maximum loss of any agent in that cluster as rz = max & (C zt).
Phase takes the clustering & as a starting point and allows each agent E NN to switch from its t-th cluster to any f'-th cluster subject to two careful constraints:
Bound the loss of the agents in the new cluster: We know the original loss of every E Cy. was at most rv. If agent i switches to this cluster, it can increase j's loss to d' (j.zz) dmh (j, We need this to be at most c-re for some constant given as input to the algorithm.
Bound own loss: We show that the expression in Line 12 12-d" ax)) + c Tr minjee, (d (i, -
as an upper bound on the loss of agent when switching to the t'-th cluster, regardless of which other agents switch to the t'-th cluster during Phase 2. This ensures that agent i's decision to switch (or not) is independent of the decisions made by the other agents in Phase 2, and the loss of agent i, who was originally in C. remains bounded by c Tr throughout Phase 2, regardless of Phase 2 decisions. Agent i makes a switch only if the new loss upper bound is lower than c Tt-
The key establishing an approximate core guarantee lies in this selective switching administered in Phase 2. Intuitively, this can be seen as striking a middle ground between the centroid greedy capture, which allows an agent switch any other cluster because it cannot increase the centroid loss of the agents in that cluster, and the non-centroid greedy capture, which forbids such switches completely lest it might harm the agents in the cluster being switched to. The growth factor carefully controls the balance, and optimally setting this factor allows us to derive the following bound. Its proof, our most technically deep result, is presented in Appendix D.I.
Lemma 1. Given a subroutine for computing a-approximate most cohesive cluster, Algorithm 1, 3x++ 30++ va(a48) .fndds a clustering in the (a Va(a + 8) + cooe Aa
with the growth factor set to c with respect to the dual metric loss.
From Lemma 1, the proof of Theorem 2 follows easily.
While Theorem 2 ensures the existence of a clustering in the 3-core, its computation relies on itera- tively finding the most cohesive cluster, which is already NP-hard in the non-centroid paradigm [2]. Luckily, Lemma I yields fairness guarantee even if we can find only an approximate most cohesive cluster during Phase of Algorithm 1.
Next, we show how to compute a 4- 4-approximate most cohesive cluster in polynomial time. The algorithm, presented
Algorithm 4 in Appendix D.I, works as follows. For each feasible cluster center y E M, it runs the non centeeido greedy capture with a crafted distance metric dy given by d nm (i, + d' y) + d' ((j for all i E A, until it produces the first cluster Cy. Then, it returns (3") with the lowest maximum loss, i.e with y" E arg mingeM maxiec, Ca(C y)-
Lemma 2. For the dual metric loss, Algorithm 4 computes a 4-approximate most cohesive cluster in polynomial time.
Plugging this into Lemma gives us Theorem 3, a constant approximation to the core in polynomial time.
7

---

Lower bounds: One may wonder how good these approximations are. As stated previously, semi- centroid clustering more challenging than both centroid and non-centroid clustering. Specifically, one can trivially import lower bound from either paradigm by setting dmd 0 or d = (where distance metric being zero means all pairwise distances are zero), which makes the dual metric loss coincide with the centroid or non-centroid loss, respectively. For the non-centroid loss, Caragiannis et al. [2] do not offer any lower bounds; that is, the existence of an exact core clustering with respect to the (maximum distance) non-centroid loss remains open question. However, Chen al. [1] establish a lower bound of 2-core with respect to the centroid loss, which we can import. Somewhat surprisingly, we unable to derive lower bound better than 2 despite reasonable effort.
4.2 Weighted Single Metric Loss
In this section, we focus on improving the core approximation guarantees for the restricted case of the weighted single metrie loss. Recall that this is parametrized by a single metric and a parameter E [0. 1] such that, for any i E N and cluster (C, x),, we have e, e, æ)) = X maxjec d(i, A) d(ii, 2). We devise two algorithms that offer improvements.
The first algorithm takes non-centroid greedy capture (Algorithm 3), which grows balls around agents, and adapts it to the semi-centroid world by assigning each cluster the cluster center nearest the agent whose ball captured the cluster. The resulting efficient algorithm is presented as Algorithm 5 in Appendix D.2, and achieves the following guarantee.
Lemma 3. For the weighted single metric loss with parameter À E (0, 1], Algorithm finds clustering in the X- -core in polynomial time.
The second algorithm, presented formally as Algorithm in Appendix D.2, is similar to Algorithm 1: in Phase 1, agents are partitioned into an initial clustering, and in Phase 2, agents are allowed to switch to a different cluster that reduces their loss and does not significantly increase the loss of the agents in that cluster. However, there are two key differences. First, Algorithm 6 uses the centroid greedy capture subroutine instead of the (approximate) most cohesive cluster subroutine used by Algorithm I to iteratively find clusters in Phase 1. Second, due to having single metric, the switching condition is much simpler and leads to better bounds for some values of X. A careful analysis yields the following guarantee.
Lemma 4. For the weighted single metric loss with parameter À E [0, 1), Algorithm 6 finds clustering in the 22x 1132413+3 -core in polynomial time.
2-21
Combining the bounds from Lemmas and 4, together with the existential 3-core (Theorem 2) and the polynomial (3 2 (Theorem 3) guarantees that we can import from dual metric loss, yields the following existential and efficiently attainable bounds.
Theorem 4. For the weighted single metric loss with parameter À E [0. 1]. clustering in the min{? 2 X. 3)-core always exists, and a clustering in the min{? 2 V2X- 11-11x++13+4 A can be found in polynomial time.
X 2-2X
Similarly, also derive two lower bounds on the core approximation under the weighted single metric loss. The first bound interpolates between (v5 + 1)/2 at À = 0 (centroid) and at = (non-centroid). Since Chen et al. [1] prove a lower bound of 2 for (centroid), which is better than (v5 + 1)/2, adapting their counterexample to semi-centroid clustering yields a better lower bound when À is close to O.
Lower bounds:
Theorem 5. For the weighted single metric loss with parameter À E [0, 1]. no clustering algorithu can achieve a core approximation better than max vX VX--2X43 A+1 2(1-X)
2A-1 }.
Fully Justified Representation
Let us turn our attention to the weaker criterion of fully justified representation (FJR), a relaxation of the core originally introduced by Peters et al. [24] in the context of participatory budgeting. While we can already achieve (small) constant approximation to the core even under the dual metric loss (Theorems 2 and 3), we show that this relaxation offers several advantages.
8

---

Caragiannis et al. [2] study FJR for non-centroid clustering. and show that iteratively finding an a- approximate most cohesive cluster produces an a-FJR clustering, even under arbitrary loss functions. The same result, with an almost identical proof, holds in our more general semi-centroid clustering setup. For completeness, in Appendix E, we formally present the algorithm as Algorithm 7 and provide a complete proof. This gives us the existence of a 1-FJR clustering under arbitrary loss functions, and polynomial time computation a 4-FJR clustering under the dual metric loss when plugging in our polynomial-time algorithm for computing 4-MCC cluster (Lemma 2).
Theorem 6. For arbitrary losses and a e I, Algorithm 7, which iteratively finds an a-approximate most cohesive cluster, returns an o-FJR clustering. Hence, a 1-FJR clustering exists for arbitrary losses and, due to Lemma 2, a 4-FJR clustering can be computed in polynomial time for the dual metric loss.
In Section 3, we noticed that for clustering, being in the a-core with respect to both centroid and non-centroid losses simultaneously (trivially) a necessary condition for to be the a-core with respect to the weighted single metric loss for all À E [0, 1].
For FJR, this is clearly still the case, and unfortunately, we can show that a simultaneous FJR approximation with respect to centroid and non-centroid losses induced by two different metrics is still infeasible.
Theorem 7. For any a 2 1 and 3 > there exists an instance in which no clustering is both o-FJR with respect to the centroid loss and B-FJR with respect to the non-centroid loss, when the two loss functions are allowed use different metrics.
When both losses are induced by a common metric d, a surprisingly simple algorithm turns out to achieve constant approximation FJR with respect to both centroid and non-centroid losses. This is in contrast to the core, for which no simultaneous finite approximation is feasible, even for single metric (Theorem 1).
The algorithm is Algorithm 5, which runs non-centroid greedy capture with metric d followed by a greedy centroid selection step. We presented it in Section 4.2 and proved that it yields 2/x-core for all E [0. 1). Note that this achieves 2-core (and hence, 2-FJR) with respect to the non-centroid loss (A= 1). However, its approximation to the core becomes unbounded as À approaches 0 (the centroid loss), which is inevitable given Theorem 1. However, we show that its approximation to the weaker criterion of FJR still remains bounded by 5.
Theorem 8. Algorithm 5, given metric d, finds, in polynomial time, clustering that is 5-FJR with respect to the centroid loss and 2-FJR with respect to the non-centroid loss, both defined using d.
6 Discussion
Our work leaves open a number of immediate technical questions, which can be gleaned from the gaps between upper and lower bounds in Table 1. Future work can also investigate generalizations such as non-additive combinations of centroid and non-centroid losses and several exciting applications.
One particularly important special case of this model that we leave largely unexplored is when M = W. As mentioned previously, this restriction applied to centroid clustering what Ebadian and Micha [17] use to model the problem of sortition (randomly selecting a committee of agents that represents the whole population), and also be used model many problems where wishes to group a set of n datapoints into it clusters, and return a single point to serve as representative point for that cluster. This can have numerous applications such as coreset selection [25]. scalable LLM fine-tuning [26]. feature selection [27]. and dimensionality reduction [28]. However, our semi-centroid algorithms offer no guarantees that the centroid it selects for a cluster will be a point that is in that cluster, which may be desirable in all these cases. Exploring algorithms with this additional constraint would be an interesting future direction.
Some of these applications may be large scale, for which our polynomial- time algorithms may not suffice and near-linear time algorithms may need to be devised. Investigating proportional fairness guarantees attainable via such ultra-fast algorithms remains an uncharted territory.

---

Acknowledgments and Disclosure of Funding
This work supported by an NSERC Discovery Grant and NSERC-CSE, Research Communities Grant. Researchers funded through the NSERC-CSE Research Communities Grants do not represent the Communications Security Establishment Canada the Government of Canada. Any research, opinions or positions they produce as part of this initiative do not represent the official views of the Govermment of Canada.
References
[1] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 1032-1041, 2019.
[2] Ioannis Caragiannis, Evi Micha, and Nisarg Shah. Proportional fairness in non non-centroid clustering. Proceedings of the 38th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 19139-19166, 2024.
[3] Javier Perote and Juan Perote-Peña. Strategy-proof estimators for simple regression. Mathemat- ical Social Sciences, 47:153-176, 2004.
[4] Ofer Dekel, Felix Fischer, and Ariel D. Procaceia. Incentive compatible regression learning. Journal of Computer and System Sciences, 76(8):759-777, 2010.
[5] Reshef Meir, Ariel D. Procaccia, and Jeffrey S. Rosenschein. Algorithms for strategyproof classification. Artificial Intelligence, 186: 156. 2012.
[6] Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah. Strategyproof linear regression high dimensions. In Proceedings of the 19th ACM Conference on Economics and Compulation (EC), pages 9-26, 2018.
[7] Safwan Hossain and Nisarg Shah. The effect of strategic noise in linear regression. Autonomous Agents and Multi-Agent Systems, 35(2):21, 2021.
[8] Maria-Florina Balcan, Travis Dick, Ritesh Noothigattu, and Ariel D Procaccia. Envy-free classification. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS), pages 1238 1248, 2019.
[9] Anilesh Krishnaswamy, Zhihao Jiang, Kangning Wang, Yu Cheng, and Kamesh Munagala. Fair for all: Best-effort fairness guarantees for classification. Proceedings of the 24th International Conference Artificial Intelligence and Statistics (AISTATS), pages 3259-3267 2021.
[10] Bhaskar Ray Chaudhury, Aniket Murhekar, Zhuowen Yuan, Bo Li, Ruta Mehta, and Ariel D Procaccia. Fair federated learning via the proportional veto core. In Proceedings of the 41st International Conference Machine Learning (ICML), pages 42245-42257, 2024.
[11] Safwan Hossain, Evi Micha, and Nisarg Shah. Fair algorithms for multi-agent multi-armed bandits. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 24005-24011 2021.
[12] Ziming Fan, Nianli Peng, Muhang Tian, and Brandon Fain. Welfare and fairness in multi- objective reinforcement learning. In Proceedings of the 22nd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1991-1999, 2023.
[13] Guojun Zhang. Saber Malekmohammadi, Xi Chen, and Yaoliang Yu. Proportional faimess in federated learning. Transactions on Machine Learning Research, 109(4):219-22) 2023.
[14] Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), pages 15:168 2020.
[15] Haris Aziz, Barton E Lee, Sean Morota Chu, and Jeremy Vollen. Proportionally representative clustering. In Proceedings of the 20th Conference on Web and Internet Economics (WINE), 2024. Forthcoming.
10

---

[16] Bo Li, Lijun Li, Ankang Sun, Chenhao Wang, and Yingfan Wang. Approximate group faimess for clustering. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 6381-6391, 2021.
[17] Soroush Ebadian and Evi Micha. Boosting sortition via proportional representation. In Pro- ceedings of the 24th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 667 667766752220 2025.
[18] Lily Li, Evi Micha, Aleksandar Nikolov, and Nisarg Shah. Partitioning friends fairly. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5747-5754, 2023.
[19] Esther M. Arkin, Sang Won Bae, Alon Efrat, Kazuya Okamoto, Joseph SB Mitchell, and Valentin Polishchuk. Geometric stable roommates. Information Processing Letters, 109(4): 219-224, 224, 2009.
[20] Anshuman Chhabra, Karina Masalkovaité, and Prasant Mohapatra. An overview of fairness in clustering. IEEE Access, 9:130698-130720 2021.
[21] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Proceedings of the 30th Anmual Conference on Neural Information Processing Systems (NeurIPS), pages 5029-5033 5039-5007,450 2017.
[22] Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NeurlPS), pages 4955-4966, 2019.
[23] Leon Kellerhals and Jannik Peters. Proportional faimess in clustering: A social choice perspec- tive. In Proceedings of the 37th Annual Conference Neural Information Processing Systems (NeurIPS), pages 11 11129-1111317 2024.
[24] Dominík Peters, Grzegorz Pierezyúski,, and Piotr Skowron. Proportional participatory budgeting with additive utilities. In Proceedings of the 34th Annual Conference Neural Information Processing Systems (NeurlPS), page 12726-12737, 2021.
[25] Chengliang Chai, Jiayi Wang, Nan Tang. Ye Yuan, Jiabin Liu, Yuhao Deng, and Guoren Wang. Efficient coreset selection with cluster-based methods. In Proceedings of the 29th International Conference on Knowledge Discovery and Data Mining (KDD), pages 167-178, 2023.
[26] Yu Yang, Siddhartha Mishra, Jeffrey Chiang, and Baharan Mirzasoleiman. Smalttolarge (s21): Scalable data selection for fine-tuning large language models by summarizing training trajec- tories of small models. In Proceedings of the 37th Annual Conference on Neural Information Processing Systems (NeurlPS), pages 83465 83496, 2024.
[27] Huawen Liu, Xindong Wu, and Shichao Zhang. Feature selection using hicrarchical feature clustering. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM), pages 979-984, 2011.
[28) D Napoleon and S Pavalakodi. new method for dimensionality reduction using k-means clus- tering algorithm for high dimensional data set. International Journal of Computer Applications, 13(7):41-45 2011.
[29] Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. The UCI machine learning repository. https://archive. ics. uci edu, 2025. Accessed: 2025-05-15.
[30] Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Matthäus Kleindessner, Jamie Morgenstern, Pattara Sukprasert, and Ali Vakilian. Individual preference stability for clustering, 2022. URL https://arxiv.org wwwg//g/g////////////////// 22002226772.2....
11

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide proof's for all the theoretical claims that we make, and provide results for the experiments we talk about the introduction and abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, discuss limitations of our model in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
12

---

Justification: We provide a detailed and formal description of our model in Section 2, and provide formal theorem statements and proofs for each claim that we make.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, we outline detail the setup of our experiment, include which datasets were used, how we sampled from those datasets, and how we implemented the algorithms we were testing. Our experiments can be fully reproduced.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
13

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes)
Justification: We provide our code as part the supplementary material, and the datasets we use are openly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //tpps.ccpppblleee wwtpccccpppccccccccccccccccccccc gwwp//u///////eee/// CoodeSummesscc ssi assionPolccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, outline all the parameters of our experiments in detail.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Yes, for our expierments, we plot the mean of number of trials, and include confidence intervals in plots.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
14

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative еттоr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, our experiments do not require a large amount of compute and can be executed on personal computer. the section where we outline our experiments, mention the steps that were computational bottlenecks, but even these were not a large undertaking run on laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics ttttp::/neerrps... http://neuurip.scpppiiiiiccc /eteiic//heeeeeee cituiielineess
Answer: [Yes]
Justification: Yes, our results are mainly theoretical and contain no ethics violations. Our experiments are against commonly used, publicly available datasets and also cause no ethical issues.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We talk about the impacts and applications of our work in Sections and
Guidelines:
The answer NA means that there is no societal impact of the work performed.
15

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Yes, we cite the datasets that we use for our experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
16

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
17

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were only used for editing and formatting purposes.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //terr//s...../e ///CCo/ferencee/2255//LLL for what should or should be described.
18

---

Appendix
A Missing Proofs from Section 2
Proposition 1. For every a 2 1, every clustering in the a-core is also a-FJR.
Proof. For contradiction, assume this is false. For some instance, there is a clustering X' ((C1, (Ck, rz}} and an a 3 such that & is in the a-core, but is not a-FIR. By the FJR definition, this means that there is a group of agents S S N with |S| > a/t and a center M such that a y) minjes (2t) for all i S.
is simple to see that for each E S, a..alla &(S, y) < minjes (x')) implies that a a (., < (x)). meaning that (S,y) induces a-core violation as well, yielding contradiction.
B Greedy Capture Algorithms
Algorithm 2: Centroid Greedy Capture [1]
Algorithm 3: Non-Centroid Greedy Capture [2]
Input: K,M.d. M.d.K. k;
Input: N, d, k;
Output: X [[1 (( ..., (Ck, xx)}.
Output: X (CI...., Cx). Initialize: N/ N'
Initialize: N² + N. + 0, d +0
0,
// Uncaptured agents remain
// Uncaptured agents remain
while A" * do
while N' * / do
Increase 8 smoothly
Increase smoothly
// Ball opens at a center
// Ball opens at an agent
3r E EM,CCN s.t. |C] > n/4 and d(i,x) & for all E C C then
if 3 E C s.t.
|C| > min([N"], n/x) and d(i, & 8 for
X XU ((C) A N
all i' E C then
X x
N ~
// Open balls keep growing (C, e X,i e N" s.t.
Open balls don't grow
d(i,z) < then
// Agents don't switch clusters
(C,x) + (CU (1),z)
return X'
N'
// Agents switch clusters
P + {a E M: (C,z) E X' for some C}
Vi E N,
mig d(i,x)
VI E P.O, + (ieN:
X ((CE)))=EEP)
return
In the three dimensions discussed in Section 3, which induce eight variants of greedy capture, centroid greedy capture (Algorithm 2) makes the following choices:
(1) The balls grow around the centroids.
After a ball "captures" a group of n/k points and opens, it continues to grow and capture any uncaptured points as soon as contains them.
(3) After all agents have been captured, each agent gets an opportunity to switch to the cluster containing the centroid that is closest to it.
We can show that the (1 -2)-core guarantee of this algorithm with respect to the centroid loss is retained even when disabling one the features (2) and (3).
Theorem 9. Consider a variant of greedy capture in which balls grow around the agents, and open balls keep growing and/or agents are allowed to switch clusters at the end of the algorithu (at least
19

---

one of the two holds). Then, it always returns a clustering in the (1 + -ooe with respect to the centroid loss.
Proof. For contradiction assume this is false, let X' = ((CI, (Ck, (x)} be the clustering found by such an algorithm, and suppose that there is deviating cluster (S, y) where |S| > [ and
(1+ + 22) d(i.y) < d(i, xx()) for every i S.
Let arg minges e x(')) be the first agent in S that was captured by the algorithm, and let
t = X()). We know that dt o or i would clearly not be part of the deviating cluster S. Let j = arg max d(j'. y) be the agent in S that is farthest from y. and let X(j) = =t'
First, note that we must have d(j. y) e d(i, z2). If this were false, and d(j. y) < d(i, my), then by the
way that greedy capture functions, the cluster (S,y) would be captured prior to i being captured by Ir, which would give contradiction.
With the above inequality, we can show that t + t'. If this were not the case, and t = t', then we could say the following:
(1+ V2) d(j.v) < d(j,ze) d(j. x1)
< 2(i, + d(i, y) + d(j. u) //Triangle inequality
1
x4) + 1+ v/2
d(i, x.)) + d(j.v) v)
1
1 + v2 +2) d(j.y).
Hence, 1 + /2 < 1+v2 + + 22, which is contradiction.
We can also show that d(j, > d(j, xr). We can do this by considering two cases.
Case 1: Open balls keep growing. If open balls keep growing in the greedy capture variant under consideration, and if d(j, d(j. < d(j. xr), then the fact that He captures prior to ze capturing j implies that at the point in the algorithm when Zy captures j. 2, will have already captured i, and will have already been in the radius of 2; 's ball at a previous value of This would mean that æt must have initially captured j. But this would contradict x() t', since regardless of if agents allowed to switch clusters in the last step of the algorithm, j could not end up in the t'-th cluster at the end of the algorithm.
Case 2: Agents can switch clusters. If agents can switch clusters at the end of the greedy capture variant under consideration, and if d(j, 24) < d(j, 3.),, then regardless of whether open balls continue to grow, j would always want to switch to ø, over Zy, contradicting the fact that X() = t'.
With this incquality, we can say the following:
(1 + 22) d(j.v) < d(j, zx)
d(j, xx)
< d(i, xz) + d(i,,)) + d(y.i)
d(i,
x1) + d(j.v)
1 V2
+ /2 + d(j.v).
Again yielding 1+ /2
1 +2 1+v2
v2, which is contradiction.
C Missing Proofs from Section 3
Theorem 1. For every 2 1 and B 2 1, there exists semi-centroid clustering instance in which no clustering is simultaneously the a-core with respect to the centroid loss and in the B-core with respect to the non-centroid loss.
20

---

p
p
Figure 1:
A semi-centroid clustering instance in which no clustering yields finite approximation to the core with respect to both the centroid and non-centroid losses simultaneously.
Proof. Fix any a 2 1, 1, and > max Consider the instance in Figure 1. Here = {a. b, e, M= shown in the diagram," with each distance that is not shown assumed to be the maximum possible allowed under the triangle inequality. Since n/k 2. deviating coalition must contain more agents.
and let d'n d d. where di is defined by the distances
For contradiction, assume that there exists clustering in this instance that is simultaneously in the a-core in the centroid paradigm and in the 3-core in the non-centroid paradigm.
Non-centroid B-core: We claim that {a, b) must be one of the clusters. If not, then either and b are each cluster with a different agent, or at least one of them a singleton cluster. the former case, {a, b} can deviate and improve the non-centroid loss of cach member by factor of 8, which is contradiction. In the latter case, since cluster C' with C > 3 (which means C' (d, e, f] & 0). If If {a, b, c} /f 0, then the larger of C' fa, b, c} and C {d, e, f), which must contain at least two agents, can deviate and each of its members would improve by an infinite factor, again a contradiction. The only remaining possibility is that C = {d. e, f}. in which case fe, f) can deviate and improve each member by a factor of p > B, contradiction.
3, by the pigeonhole principle, there must exist
Hence, {a, b} must one of the clusters. By symmetry, (e, f must also be cluster, so the remaining cluster must be {c, d]. Thus, the only clustering that can be in the B-core in the non-centroid paradigm is {(1a, x1). (fc, d), x2), (fe, x3)} for some æ1, Ø2, 23 E N.
Centroid a-core: If x1 & {a, b). then {a, b) can deviate with either of or b as the cluster center and improve the centroid loss of each by a factor at least p > a, a contradiction. Without loss of generality, assume 21 = a. Similarly, assume without loss of generality that D2 E {a, b, c) or 22 E {d, e. f). In the former case, {d. f) can deviate with a center at f. and in the latter case, {b, c} can deviate with a center at b, in each case improving each member by a factor at least p > a, which a contradiction.
Now, either
This concludes the proof.
D
Missing Proofs from Section
D.1 Dual Metric Loss
Here, we present the missing proof our central result, Lemma 1, which establishes an approx- oracle for a-approximate maximum
imate guarantee for Algorithm 1 with access cohesive cluster. In the main body, we use it to prove our existential and polynomial-time time attainable approximate core guarantees for the dual metric loss (Theorems 2 and 3). Let us recall the statement. Lemma 1. Given a subroutine for computing an a-approximate most cohesive cluster, Algorithm 1,
3a+ /ala+t) finds clustering in the 1 (a + Vala 8) + 2)-rrre
with the factor set with respect to the dual metric loss.
We begin by establishing several useful properties of Algorithm 1. These properties bound the loss incurred by the agents when they (or other agents) switch (or choose not to switch) clusters during Phase 2 of Algorithm 1.
Recall that Phase 1 produces tentative clustering &, with rt max C,(,,, 23)) being the maximum loss in the t-th tentative cluster, (Ō,, .T). Then, in Phase 2, each agent i E C₁ is given the
'The infinite distances can be replaced by very large distances without affecting the proof, but we keep them infinite for simplicity.
21

---

opportunity to switch to the t'-th cluster for every t' E V, For each such cluster, the agent evaluates the expression (ii a di (i, + c. r min (d' - xe))))
JEC,
picks its minimizer t" E arg ein O(i. t²), and switches to it ((i,t)) < c. The following claims shed light into the reasoning behind this specific step.
The first lemma establishes that an agent is part of the 1-th cluster at the end of both Phase 1 and Phase 2 (i.e., it does not switch clusters during Phase 2), then its loss, which is at most r. at the end of Phase 1, remains bounded by c Tt at the end of Phase 2. The increase may come from other agents possibly switching into the t-th cluster during Phase
Lemma 5, For each E N, if (1) = (1) = t, then (₂(x) = (,( C.
Proof. Our goal is to show that d' 2i. d (i, & c.r, for all j C. Consider any E C2.
Case 1: j C. Cr. By the definition of re, we must have di,,, the last inequality holds because c > 1. In words, such an agent does not increase the loss of agent i even slightly.
x4) + (i, & re & C. Tt, where
Case 2: j C. Cr.. Because agent j was allowed to switch to the t-th cluster, must have E Vj- Then, Line 11 in Algorithm 1 ensures that di, xx) + d (1. & c. c.ry this is the condition that forbids an agent from joining cluster if it would significantly hurt "core member" of that cluster.
This concludes the proof.
The next lemma shows that if agent i switches to the -th cluster during Phase 2, its final loss (,) would be bounded by (ii t"). Lemma 6. For each E N. if = =t" + 2i), then
ex(x) (,(C < ((1, d' (i, x1) + rr min (d") (j, jEC.-
Proof. Let H' = arg max (i. be the agent in Ct. that is the farthest from i. Then, we
have (,(Cr-, x--) = d' (1-) di ('). We want to show that this is at most (i, t²). Let
j' = arg min C (d (i.j) - d' dj xx) so o(i, = d' xe- te + d (i,j*) d' x+-)
Let us simplify our goal:
d' di dmh (i, & d' (i, r. + d'' (1,5") ((",,,))
+ d (i, & c r. d (i.j") di I..))
(1)
Case 1: 1 Ör.. Then, by the fact that jr Cr. is also true, we must have that d' xx-) dmh ("",)²²²) & (,,( vx-) & rı,, which yields dmm (j", i') & r2- - d' dj" (z)))
+
Case 2: & Cz.. Then, since agent i' switched to the th cluster during Phase 2, we must have I" E Vv. Line 11 of Algorithm and the fact that j E Cr- ensure that d' d'" xe) ("*,
+ ddd d''(j" i!) <
e- Ter, i.e. (""(i""')) & TT. dd(j" ; J.-). Since c > 1. we get dth (j* 8)) C. d' dj" xx)) in both cases. Using the triangle inequality,
we get
di" & dth (i,j*) + d (j*, f < d" (i.5") + tc.re- -
which is the desired Equation (1), concluding the proof.
Here is what we know now. During Phase 2, if agent remains in its original cluster {(() = t, its loss remains upper bounded by c-r, (Lemma 5), and if it switches to cluster t' E V,, its loss remains upper bounded by (i,, ('). This explains why agent switches to the cluster 1" E arg mingev; (fi, only if (i,, < c. re: the agent is simply picking the cluster that offers the smallest upper bound on its eventual loss. This is captured by the next lemma.
Lemma 7. For each E N and 1' E Vo we have 1x(x) & ((1,1)) = di(i,ze) + c. re min (d (i. d' d'(j xx)).
22

---

Proof. Let L (2) and t* E arg ev f(i,t'. If agent i switches to the t"-th cluster during Phase of Algorithm then the claim follows from the fact that ((i, & o t') for all t' V,, If agent i does not make switch during Phase 2 and remains in the 1-th cluster, this must be because e- rr. < $(i, (") due Line 13 of Algorithm 1. The claim again follows from Φii, (*) & ((i,t") for all t' E V,-
L
Similarly to the proof of Lemma 7, we can see that if agent was in the f-th cluster at the end of Phase I, then e r also remains an upper bound on its eventual loss, regardless of whether the agent stays in the I-th cluster or switches to 1" cluster during Phase 2. This is because the agent only switches to the (" cluster if it provides a smaller upper bound on the loss.
Lemma 8. For each E NN, if (i) = t, then (xx) & Te.
Proof. If (()) t (i.e., the agent stays in the t-th cluster during Phase 2), then the claim reduces to Lemma 5. If X()) = t' + t, then by Lemma 6, we have (2(2)) < ((i, ((), However, due to Line 13, agent only switches to the t" cluster i t*) < c. TE, which implies (x() & c. re- as needed.
Together, Lemmas 7 and give us two different ways to upper bound the loss of agent in terms of the f-th cluster that agent i was part of at the end of Phase I, and in terms of every t'-th cluster in V; that agent had the opportunity to switch to during Phase 2. With these bounds, are ready to prove the central lemma.
Proof. Proof of Lemma 1
Fix an and let , = =a va(a+8) +) 2).
For contradiction, assume that in some clustering ((C1, (Ck, returned by the algorithm, there is some deviating cluster (S, y) such that for all E S,4(S.v) < 3 (X)) Let
i = arg min (i) be the agent from this deviating cluster that was captured first during phase 1 of Algorithm| 1. Let (() f. Let arg maxjes (5 y) be the agent from S that has the highest loss among all agents in the deviating cluster.
First note that it must be the case that (, v) > dr.. If this were not the case, it would contradict the fact that (C,, xz) was a a-approximation of the most cohesive cluster at that step of the algorithm.
Next, we can show that {() + t. and that j did not have the opportunity to switch into the t-th cluster during the second phase of the algorithm.
Showing that {(j A t is easy. If {j) (x)) & c Tr. Since j wants to deviate to (S, y). we also must have that (, v) < ( & $ By plugging in the correct values of B and c, it can be seen that B whenever > 1, so this would contradict that (S, y) >> !r.-
were true, then by Lemma 8, we must have that
With bit more work, we can also show that j did not have the opportunity to switch to the t-th cluster during the second phase of the algorithm. If j did have this opportunity, then by Lemma 7 we must have that (2) < ()) + + min (dm((', - ((('xx)), Since i E C. this also gives us (x)x) < (j. +c. (i.j) - d' (i,
By the triangle inequality, we have that d') & d' d'.vv) + (i, (i, Plugging this into our bound on j's loss gives us:
((x) < Se. of (i,) (j.))) + d' (i.
Notice that since and j are both in S, d di di. < (S, Also, we must have that v) &(S,v) y) < (x() & fra, where the last inequality follows from Lemma 8. Plugging these in our inequality gives us:
(xx) (() + c 5 Tt. 3
23

---

This implies that when j deviates to (S, v), it can only improve its loss by a factor of at most:
(s(, + c+
E,(S,
The fact that (j(S,y) > r. allows us to upper-bound this as
Tt c+ 1 re = =1+c.a (1+
By substituting in the values of e and 3 in terms of a, this comes out to be fa + va(a + 8) + 2). which gives contradiction.
Thus, must be the case that j does not have the opportunity to switch the f-th cluster during the second phase the algorithm. Therefore, there must be some E C2 such that d' xx) + dmn (i', j) > Tr, which can be rearranged to get d' di" (i'.j) > C- di',,, xz). As the final part of the proof, we can show that this also leads to contradiction.
By the triangle inequality, we have that d' (t',j) & d'' + d'' (i.j). This can be rearranged get dtm (i. > d (i' dd (i' (i', Plugging d'm (d', .)) c-rt d' ((',x) 24) into this inequality gives us d (1,5) > c- (d' xz) + (i', Since and are both in C₁ we have that d'(i', 2x) + (d"((")) & & (C,, & Tt, which gives dmh (i.j) (c (c-1)r: 1)r,. Since and are both S, this tells us that (S. dmh (1,5) (c - 1)rz-
Finally, since i C. by Lemma 8 we know that (xx < c. Tt. This means that when deviates to (S, y). they are only improving their loss by a factor less than c. (o-1)r = ( + Va(a + 8) + 2).
giving another contradiction and completing the proof.
From Lemma 1, the proof of Theorem follows rather easily.
Theorem 2. For the dual metric loss, there always exists clustering in the 3-core.
Proof of Theorem 2. Set = 1 (i.e., let Algorithm iteratively compute most cohesive cluster in Phase 1) Lemma 1, which sets the growth factor to e = 3/2 and yields a 3-approximation to core.
Next, we present Algorithm 4, which efficiently computes a 4-MCC cluster for the dual metric loss by running the non-centroid greedy capture algorithm on a carefully crafted distance metric, once for each feasible center.
Algorithm 4: 4- d-Approximate Most Cohesive Clustering Algorithm
Input: Set of agents N, set of feasible centers M, non-centroid metric d'x centroid metric d'. number of clusters k
Output: Cluster (C,x)
for y E M do
Vi,j E A (t. d'a (i. d' + d'(jyy);
// Craft the metric // Run greedy
C t First cluster produced by Algorithm 3 with input (N, dy. k);
capture
Ty t- maxiec, (i(Cy,
11 e, dual metric loss
3" < mrg Ty;
// Best center
return (Cy,,8")
The proof of its approximation guarantee follows. Lemma 2. For the dual metric loss, Algorithm 4 computes a 4-approximate most cohesive cluster in polynomial time.

---

Proof. For any instance, fix some y E M and let dy be metric distance function over N, where for any distinct j.j E =N, diy(j..) = d (i.j) + di y) + (j. (if
then we assign dy (i.j) 0).
We can first show that dy indeed induces a metric space over N. To show this, we just need to show that the triangle inequality holds, as clearly dy will meet the other two metric axioms.
For any i, j E EN, we should have that dy (i & dy + dz j). By the definition of dy, this is equivalent to saying d' (i, + d' y) + d' (1.2) & d (i, di y) + d y) d (7' () d1', y) + (i. y). By the fact that d is a metric, we have that di.(i. < d (1, d J). Therefore, just need to show that d' v) + d di.jy) & (i. + d' (i', y) + d v) d (j.y).
Clearly, this holds as well, since d' d' v) + d' (j. y) appears on the right-hand side of the inequality.
Algorithm 4 runs the non-centroid greedy capture algorithm on the agents, using the distance metric dy. for every y E M, then considers that cluster in the original dual metric setting with y as its center, and selects the most cohesive cluster found this way.
For contradiction, assume that Algorithm does not find a 4-approximation of the most cohesive cluster. Let (S, y) be the most cohesive cluster for an instance inputted to Algorithm 4. Define r maxiss (S, y) as the maximum loss felt by any agent in S. Assume that Algorithm 4 returns the cluster (C",z"), xx",, where r" max (,(C", .x") > 4r.
Take the distance metric dy. and let Cy be the non-centroid cluster that Algorithm 4 finds while using dy as its distance function. First, note that max,ec, Ce(C,g, y) > r". Otherwise, Algorithm 4 would have returned (C,, y) rather than (C*, x).
Next, consider the maximum non-centroid loss with respect to dy for any agent in the mem- ber set S. We will have Vi S, max dg (i,j) = maxjes (i. + di y) + di y)} < maxjes dd (i, + (i, + maxjes d'(j. y) E r + maxjes d' (j. v). For all j E S, we must have that d' (j.y) y) < r, which gives us maxjes dy (i < 2r.
Caragiannis et al. [2] prove that in any non-centroid clustering instance, Algorithm 3 achieves a 2-approximation of the most cohesive cluster with respect to non-centroid loss for that instance. Since Cy was found by running Algorithm 3 on N with distance function dy. Cy must be a 2-approximatton to the most cohesive non-centroid cluster in that instance. Particularly, this implies that the maximum non-centroid loss with respect to d, loss felt by any agent in Cy must be no more than two times the maximum such loss felt by an agent in any member set C² C N with [C'| n/k. With respect to S, this implies that jaxijec, dy (1. < 2 jes (i,j) & 2((r) = 4r.
Finally, note that for any member set of agents C, the maximum non-centroid loss for that member set felt by any agent i E C' with respect to the metric dy will be an upper bound on the dual- metric loss agent i will feel under the cluster (C,y). To see this, note that i's non-centroid loss under C with respect to dy will be equal to maxjec (i,j) = max (d (i. + di y) d' v)) maxjec ddh (i.j) + d (i, C,(C, y)- In the case of Cy. this tells that r" & max4ec, (,(C,,,) v) & mmaxie,, maxjec, dy (i.j) & 4r, which gives a contradiction, concluding the proof.
Plugging this into Lemma gives us a constant approximation to the core in polynomial time.
Theorem 3. For the dual metric loss, a clustering in the (3 + 2v/3)-core can be computed in polynomial time.
Proof. From Lemma 2, Algorithm 4 computes a 4-MCC cluster. Let Algorithm iteratively use it in
Phase and set a = 4 in Lemma 1. Then, the growth factor is set to c = 3 + v/3 and we obtain a core approximation of } + /48 + 2) + 2/3. Each call to Algorithm 4 runs in polynomial time, and it is clear that the rest of Algorithm 1 also runs in polynomial time.
D.2 Weighted Single Metric Loss
Lemma For the weighted single metric loss with parameter E (0, 1), Algorithm finds clustering in the 2 &-core in polynomial time.
25

---

Algorithm 5: Non-Centroid Greedy Capture With Greedy Centroid Selection
Input: Set of agents NN, set of feasible centers M, metric d, number of clusters Output:
Initialize: N"' N, X' < 0,6 f (G.........
Clustering X' = [[
// Uncaptured agents remain
while A' + 0 do Increase 8 smoothly;
// Non-centroid ball found
M"a s.t. |C] min(W")), and d(i, & for all i' E C then if E e C N x +- arg M d(i,r); // Centroid closest to the ball's center X - X ((C,a)) N² + N" C:
8 return
Proof. For contradiction, assume this false, and there exists some instance such that the greedy clustering solution X' = (1),... (Ca, xx is not in the 3-core. This means there exists some deviating cluster (S, v) such that for all i S, (S, < (x)).
Let = arg minges X²'(') be the first agent from captured by Algorithm 5. Let x() Let j E C, be the agent that "captured" the cluster C2 (meaning that at the time when C2 was captured by the algorithm, d(i',) ))= & for all i' E C2 was true), and let ra = maxiec, ((,, be the value of 5 at the point when C, was captured.
Due to the triangle inequality, we have that for any E Cr, ((,) d(i,)) + ((j,8) < 2r.. With this, we have that (x) < (1 A)d(i, x4) + X2r..
Note that there must be some i' S with d(i,i') > rt. If this were not the case, then Algorithm would have captured S prior to capturing Ce. with i being the "capturing" agent of S. Thus, we also have that (5., y) > (1 - A)d(i, v) Are.
Due to the way that Algorithm 5 greedily selects a center for each cluster, it must be the case that d(j. y) > d(j,zz), since otherwise, y would have been selected the center for C₁ rather than 2,, From the triangle inequality, we have that d(i, xx) < d(i,,) + d(j. x.) < r + d(j.y) < + j( + d(i. v) & 2r + d(i, v). This allows us conclude that ((1, 2r + d(i.
The above inequality allows us to bound (x) < (1 X)d(i, 2x)) + A2r < (1 2) + d(i y)) A2r 2r + (1 A)d(i, y). This means that improves their loss by deviating at most factor of:
2r. + (1 A)d(i,))
-)r +15
(2 A)re
+1
(1 - A)d(i, y) Ar (1- 2)d(1, v) Ar
Ar
This gives the desired contradiction.
Lemma 4. For the weighted single metric loss with parameter X E [0, 1), Algorithm 6 finds clustering in the V2X- 1PA-114413+3- core in polynomial time.
2-21
Proof. When running Algorithm 6, we set the growth factor c= 3. where 22 -2 122-1112413+001
Let X' ((C1, (Ck, æx)} be the clustering returned by Algorithm 6. Further, let & [(C), (Ox, } be the clustering found by Algorithm after has completed phase 1.
First, we will show that for any agent é E N, if 2()) = t, then (x(x') will no more than (1- (1-A))(í, + X(d(i, 21) + Ir)) ((i, + This can be seen by analyzing how the second phase of the algorithm works.
In phase 2 of Algorithm 6, each agent i E / can choose to switch from the cluster they were originally assigned to by the algorithm, to a new cluster. However, they can only switch cluster (Cv, 2v) if d(i, we) cre. In the algorithm, i called the "growth factor", as the second phase can
26

---

Algorithm 6: Semi-Ball-Growing Algorithm
Input: Set agents NV, set of feasible centers M, distance metric d, parameter [0,1].
number of clusters k. growth factor c > 1
Output: Clustering X' {(C1,71) (C,, (C,,
Initialize: N" < N,,, X <- + 0,1+00
// Phase 1: Build tentative clustering via centroid greedy capture // Uncaptured agents remain
while N # # do Increase å smoothly;
if Ex, E M,C, CW s.t. 1 minn(W"),,%/ and d(i, mi) & for all i E Cg then X a))(;
Tt t 8;
N" N Gi t+t+1
// Phase 2: Selectively allow agents to switch clusters
vt [k), C, Cis
10 for i E N do
// Allowed cluster with the best upper bound on loss
11
< arg min (id(t.))) ((1 A) d(i, xx) + c A 2r,);
8()::
12
1/ Switch if it improves the upper bound on loss
13
if (1- A)dd(i, xe) + + 2r < d(i, t X Tr then
14
Cr - Cr (i);
15
C+ - Ce (i}:
16
return = ((C1, (C,,
be thought of the radius of each of the cluster balls increasing by factor of c, then each agent choosing to change to a new cluster that they are within the radius of. Also note that each agent judges whether some new cluster (Cr) will provide it less loss than its current cluster based on the worst-case loss i could possibly feel after switching to (Cr, Tyy). ). This is reflected in the term A 2r, on Line 11 of Algorithm 6. Due to the fact that the non-centroid part of each agent's loss function will change based on which clusters other agents choose to switch into during the second phase of the algorithm, each agent will only switch to new cluster if, regardless of how other agents switch, their loss under that new cluster is still guaranteed to be less than their current loss.
For any i E A' with (t) t, if were to not switch to new cluster in the second phase of the algorithm, then can show that its final loss will be less than d(i, + q Tt. To see this, assume does not switch clusters in phase 2, and thus X(ii) = f. Because we know that did not switch, it must be the case that the distance from to the centroid of its final cluster is d(i,
Tt. Further, from the way that agents were allowed to switch clusters in the second phase, we know that all for any j E C., we must have d(j, ...) < e-r.. . By the triangle inequality, this means that for j = maxjec, d(j, i), the agent from C, that is farthest away from i, we must have d(i, & d(i,zz) (2))+d(5 +d(j,an an)) & d(i, ((i,r))
Putting these together and plugging in that & we have that:
4(x) (1 d(i, - < (1 A) d(i, + X- (d(i, + +c. d(i, x4) + +q.r re
Similarly, we can bound i's loss if they do choose to switch clusters in phase 2. Assume now that i does switch such that after the second phase the algorithm (ii) = tt.
By similar logic as above, we can upper bound i's loss as:
(xx) (1 A)d(i,ze) + NeT (2) & X)d(i, A2cry (1 X)d(i, (c) + 2gre
27

---

Here, the second transition follows from the fact that every agent in Cp is at most a distance of cre away from Zp, This along with a similar triangle inequality argument as above allows us to bound ( & 2ere. Notice that this is worse than the bound we were able to establish on i's non-centroid loss in the case when did not switch. This because when i did not switch, we knew that da) & T.. where in the case where i did switch, all we know is the weaker bound of d(i, ze) < c. Tt-
From line 13 of Algorithm 6, we can see that an agent i will only switch from their first phase cluster to new cluster if the upper-bounded' loss from this new cluster is less than the upper- loss of their original cluster. Thus, no matter what i does during the second phase, we can guarantee that their loss will not be more than d(i,, xz2) + q Tt-
With this bound on each agent's loss established, we can prove the required core guarantee. Assume for contradiction that this is false, and that Algorithm 6 produces clustering X' such that there is some
deviating cluster (S,y) y) with S - W, > [x] and y E .M with v2X -21-11122 11 (((S, y) < (x) for all i E S.
2-24
Let i = minge R(i be the agent from S that was captured first by phase 1 of the algorithm, and let (i) = t. We know that d(i, .x.) & Tr. Let j = arg maxjes d(j, y) be the agent in S that is farthest away from y. We know that d(i. y) 2 rt must be true, otherwise, the first phase of the algorithm would have captured (S, prior to capturing 2t),
First, we will consider the case where d(j, 24) & C-T;, This means that in the phase 2 of the algorithm, j will have the opportunity to switch to the f-th cluster. The maximum loss that j could feel under the cluster centered at Iy is (1 - A)d(j, 2x) + 2qra, and since will switch to the cluster with the lowest upper-bounded loss, this means that j deviating to (S, y) can improve its loss by at most a
factor of [1 11-A))((.r.+++ +2me, Note that this can be upper bounded as (1 X)d((.))
(1 A)d(j, + 2qr
(d))(d(j. v) + d(i, v) + d(i, 2()) + 2qr
(1 (-))d(i.))
(1 A)d(j. v)
A)d(j.)) v) + (1 x) u) + r.) + 2gr (1 x)d(i. u)
(1 A)re + (1 - ()(i,, v) + r2)) + 2qr (1 A)r
(2(1 A) + +24)re + (1 - 2)d(t,y)
(1 Aire
2(1 A) + 24
+ d(i,y)
(1 (1-A) A)
For i, we must have that ( v) > (1 A)d(i, v), and e.Th (X)) cannot be more than i's upper- bounded loss under (t), meaning that deviating cannot improve its loss by more than factor of
d(i,zt) + < (1- x)
(1 + q)rl
(3)
(1 - X)d(i,y)
Combining Equations (2) and (3), we get the following bound:
1+g g X d(i.v) (1 -1-30 X)
Tt. 2(1 A) + 2g
d(i, vi
+ 1 X (1-
1 g
2(1 2(1 2q
min+
+
< max min 230
Tt
2
- - + 1) + - 22 + - x
where the last transition can be derived by equating the two expressions in & and solving the resulting quadratic equation in z. Substituting the chosen value of q and simplifying gives the following bound:
22 11X + 13+3-X
2 2A
28

---

This yields contradiction. This shows that it must be true that d(j. 21) > c. Tt, meaning that cannot switch to the f-th cluster during the second phase of Algorithm 6.
Using this along with the triangle inequality, we can say that {r: < d(j, & d(j.i) + d(i, &
d(j,)) i) rs. Rearranging get that d(i,j) (3 1)r:
(
xxxx )r
With this, we can say that (, v) > Ad(i,)) , -a A)re.
Combining this with the fact that (x)) < d(i, x1) -.. $ (g + 1)r, we get that in this case, i deviating to (S. y) cannot improve its loss by more than a factor of g+1
g-x'
Substituting in our chosen value of q and simplifying once again gives us:
V2A 1112 13
2 2 22
which is a contradiction, and concludes the proof.
Lemma 9. For the weighted single metric loss with parameter À E [0, 1], no clustering algorithm can achieve core approximation better than -X--2X45-XX
Proof. We will analyze the instance in Figure 1, with p = 1/2- 24+5++11111 We will limit our analysis
2A
to the section of the instance containing {a, b, c), where, since it 3, assume without loss of generality that one cluster center is placed.
If the cluster (fa, b, c). b) is initially selected, then will have a loss of (1 A)d(a, b) + Ad(a, c) (1- + Ap. and b will have a loss of (1 A)0+ + Ap Ap. If and b deviate the cluster (fa, b}. b). then they will improve their loss by factor of (1 - X) + Ap and respectively. This deviation will lead to violation of core with a factor of (1 - A) + Ap - The same argument can show that (fa. b, c}, a) would also not work as a cluster, and clearly, (fa, b, c), e) would also not work, as a and b's losses would only get worse then before.
If the cluster (fa, b), b) is initially selected, then note that will have a loss of (1 A)d(a, b) Ad(a, b) In contrast, under the clustering (fa, e), a), a will have loss of - x)0++
Ap. This means that by deviating, a will decrease its loss by a factor of 1
Ap - -X--2A464X-1
- -+1 Since we assume that only one point from {a, b,c) is selected as center, this deviation must also improve c's loss by an infinite factor. Note that the same analysis holds if a was selected as the centroid in the initial cluster rather than b. Again, clearly the center e would not work with this cluster either, as it would just make both agents no better off.
Next, note that the cluster (a.cc).a a) cannot be selected. would have loss of (1 X)0 + Ap Ap. But under the clustering (fa, b). a) a's loss would be (1 - X)0 + X = X, so deviating would improve a's loss by factor of p > 2 b would also improve their loss by an infinite factor. Clearly trying this cluster with any other center would not help, as it would only make a's initial loss worse. This argument can also be used to show that the cluster with member set {b, c} will not work.
This eliminates the possibility of any cluster of the 3 agents of size greater than 1. Finally, we cannot have more than 2 of these agents involved in a singleton cluster, as since k = 3, all the agents on the other side would have to all belong to the same cluster, and we could apply a similar argument as the second paragraph of this proof to find deviating set there.
For the weighted single metric loss with parameter À E [0, 1), no clustering algorithm can achieve core approximation better than 2(1-X)
Lemma 10.
2x+1
Proof. Take the instance from Claim of Chen et al. [1]. .V =
(yi...., va):E k The distances between agents are given as d(ai, 02) = d(a), 03) = d (22 0z) = 3 and d(u4, (s)) = d(a4, da) d(as, u6) 3, with all other pairs having distance xo. The distances between agents and centers are given by the below table (which can also be seen in claim of Chen et al. [1]).
29

---

y/1
3/4
3/5
1/6
Q1
4
2
00
00
OC
02
2
1
03
00
00
0C
04
00
00
00
4
00
00
2
4
1
2
4
Chen et al. [1] show that in this instance, is impossible to achieve a centroid core approximation better than 2.
Fix some clustering X I1), (C2, #2), (C3, 13))- From Chen et al. [1], there must be some pair of agents that would want to deviate in the centroid world for core improvement of at least More specifically, since there are clusters, and the instance consists of two "groups" of agents/centers, which separated by distance of oo, one of the groups must have at most 1 center from that group selected as one of the centers in X.
Without loss of generality, assume that the group {a1, 02. 4s} only has one center from their group selected by X, and assume y1 that center (because of the symmetry of the instance, we could pick either group, and any center of that group, and an identical argument would hold). In this scenario, the other two centers from X' are distance no away from d1 and 02. d1 d2 are either the cluster with V1. or in a cluster with center farther away from them than 7/1 Therefore, we must have that la (x)= > (1 A)d(a1, v1) = 4(1 A) and laz (X) 2 (1 X)d(a2. v1) 2(1-A).
Now consider the deviating cluster (S {a1. a2) va). aj and 02 will have the following losses under that cluster:
la (S. ys) Xd(a1, 02) (1 A)d(a1, Us) 32 2(1 - X) la (S, = Ad(a1, 02) (1 A)d(a2, ys) = 3A + 1(1 - A)
These, along with our lower bounds on the agents' loss under X' allow us conclude that would be 4(1-A)
able make improvement of at least 3X+2[1-]] by deviating, and a2 would an improvement of at least 3X+1(1-X)
2(1-A)
can easily be verified that 4(1 3 2(-A))
3X+2(1-X) 31+1(1-X) for all [0, 1]. meaning that this would lead 31-1(1-X]
to core violation of 2(1-A) = 2x-1
2(1-A) completing the proof.
With the above two lower-bounds. we can make the following general statement.
Theorem 5. For the weighted single metric loss with parameter À E [0, 1), no clustering algorithm achieve core approximation better than max yx2 2A45
A+1 2(1
2
Proof. The result for À E (0, 1) follows directly from Lemmas 9 and 10. The edge cases follow from known lower bounds from the centroid (lower bound of 2 [1]) and non-centroid (lower bound of [2]) worlds.
E
Missing Proofs from Section 5
First, we provide the missing proof of Theorem 6, which shows that Algorithm yields an a-FIR clustering, guarantecing the existence of an (exact) FJR clustering for arbitrary loss functions and the polynomial-tn -imee computability of 4-FJR clustering for the dual metric loss.
Theorem 6. For arbitrary losses and a. 2 1, Algorithm 7, which iteratively finds an a-upproximate most cohesive cluster, returns ox-FJR clustering. Hence, a 1-FJR clustering exists for arbitrary losses and, due to Lemma 4-FJR clustering can be computed polynomial time for the dual metric loss.
30

---

Dritess (EcerSARs
Loverdaa
4.-
16
Figure 2: Single Metric Core Bounds Visualized as À varies from 0 to For exact bounds, see Table 1
Algorithm 7: Iterative a-MCC Clustering
Input:
Set of agents N,, of feasible centers M, agents' loss functions (Ci)iENs number of centers k; approximation factor a > 1;
Output: Clustering X'
(C,,)),(
Initialize: N² < W, X' < 0;
// Uncaptured agents remain
while No # do
(C,x) <
An a-MCC cluster (with threshold n/k) from N M // Find an a-MCC
cluster
X X [(C,))); A" N" C;
// Add the clustering // Mark its agents as captured
return X
Proof. For contradiction, assume that Algorithm 7 does not always yield an a-FJR clustering. Then, there exists instance in which the clustering X' Algorithm admits a deviating cluster (S. y) such that for E S.
(Ck, 24)) returned by
a (.(S,y) < minjes (2())
(4)
Let 5" E arg minies X1ii) be the first agent in S that was "captured" (i.e., removed from N') by the algorithm, ties broken arbitrarily. Let = ((*).. Then, from Equation (4), we get that for all E S,
a (S. y) < minjes (x( & (x & maxsec, ((X)) = maxsec, (,(C,,
Hence, a max,es (S) < max;ec, ((C,, Since all agents in S were uncaptured prior to (C), being added to X, this contradicts (Ce, 21) being an a-MCC cluster at that time. This concludes the proof that Algorithm 7 always yields an a-FJR clustering.
Since an MCC cluster exists by definition, plugging in a yields the existence of an FJR clustering. And for the dual metric loss, since 4-MCC cluster can be computed efficiently via Algorithm (Lemma 2), we obtain that a 4-RJR clustering can be computed in polynomial time.
D
Next, we provide the missing proof of Theorem 7, which shows that such a simultaneous approxima- tion is impossible when using different centroid and non-centroid metrics.
Theorem For any a > 1 and 3 > there exists an instance in which no clustering is both a-FJR with respect to the centroid loss and B-FJR with respect to the non-centroid loss, when the two loss functions are allowed to use different meirics.
f), e, Proof. Consider an instance with set of 6 agents N = fa, b. c, d,
set of two feasible cluster
centers M {21, and i 3.
Non-centroid metric: Let d (a, b) = (c d) = (e, = 0, and let the non-centroid distance between every other pair of agents be oo.3
Here, for the ease of exposition, but it be replaced suitably large number.
31

---

Centroid metric: Let (a, = d'(c,z1) = de(e, = 0, let db()) = d'(d, x22) d' x2) O, and let the centroid distance between every other agent-center pair be oc.
Finite non-centroid FJR approximation: First, note that the only clustering that leads to a finite FJR approximation with respect to the non-centroid loss is the one that partitions the set of agents as ='= 6), d), f).
To see this, consider any C' X. If C' is "broken" (i.e., not cluster by itself), then at least one member of C must be a singleton cluster; the only other possibility would be that C' is a strict subset of cluster, in which case C' can deviate, improving both its members from infinite loss to zero loss, yielding infinite FJR approximation.
Hence, every unbroken pair in X' forms a cluster of size two, and (at least) one member from every broken pair in X' forms a singleton cluster. Since there are three pairs in X, this already uses up k = 3 clusters, leaving the other members from the broken pairs in X' not included in the partition, which is impossible. Hence, there must not be any broken pairs, which shows that the partition must be X = [[aa b), {e, d), {e. f}}.
Finite centroid FJR approximation: Now, let us try to assign center to each cluster in X' in way that yields finite approximation with respect to the centroid loss. Since there are only two feasible centers I1 and T2. at least one of them must be assigned to at most one of the clusters in X. Without loss of generality, assume this center is Z1. There are three agents, a, C, and e, which are at distance O away from I1 under the centroid metric. However, they are different clusters. Hence, at least two of them must be assigned to 22, and can deviate together with 21 and improve both their centroid losses from non-zero to zero, resulting in an infinite FJR approximation with respect to the centroid loss. If we had assumed 22, we could have made the same argument with agents b, d, and f.
This shows that there is no clustering that achieves finite FJR approximations with respect to both the centroid and non-centroid losses, concluding the proof.
Next, we provide the missing proof of Theorem 8, which shows that simultaneous approximation is possible if both centroid and non-centroid losses use the same underlying metric. Since our algorithm (Algorithm 5) builds on non-centroid greedy capture, its FJR approximation with respect to the non-centroid loss is borrowed easily; the key difficulty is establishing its FJR approximation with respect to the centroid loss.
Lemma 11. Algorithm 5, given metric d, yields a clustering that is 5-FJR with respect to the centroid loss induced by d.
Proof. For contradiction, assume this is false. Then, there exists an instance in which Algorithm 5 returns a clustering X' = {(Ci, 21),..., (Ck, }x)) that admits a deviating cluster (S, y) such that
Aq E S: 5 d(g. y) < min (x).
(5)
PES
Let i E S be the agent from S that was captured first by Algorithm 5. Denote the cluster containing agent as (C,z) & (Cx(o). xx())) for brevity. Because Algorithm 5 runs non-centroid greedy capture to create the partition of the set of agents, C must have been captured by a ball centered at some agent j E C. Note that the center selected by Algorithm 5 for C' must be the closest feasible center to agent j. Let r = max d(j, '') be the radius of the ball centered at when it captured C.
First, we show that d(i, z) & 2r + d(i, v). To see this, note that
dii, & j) + x(j & d(i,j) d(j.v) v) & d(i,)) d(i,)) d(i,v) < 2r d(i, v), where the first and third inequalities use the triangle inequality, the second inequality uses the fact that x is the closest center to agent (hence, d(j,x) & d(j. v)), and the last inequality follows from the definition of r.
Now, from Equation (5), we have that
bq E S: 5 d(g. < min (2) < (x( d(i,z) < 2r + ddii PES
In particular, substituting q i, we get that 5 d(i < 2r + d(i v). which yields d(i v) < 1/2. Then, for every other agent q E S, we have that d(g, 9) < 2r + d(i.y) < 25r/2, which yields d(g. v) 7/2.
32

---

By the triangle inequality, we have that, for all p.g S, d(p.g) q) & d(p.y) + d(g.y) < 1//2+ +/2 = But this is contradiction because this would imply that the execution of Algorithm the ball centered at any agent in S would have captured S before the ball centered at agent j captured C. I
The proof of our simultaneous FJR approximation guarantee (Theorem 8) is now straightforward. Theorem 8. Algorithm 5, given metric d, finds, in polynomial time, clustering that is 5-FJR with respect to the centroid loss and 2-FJR with respect to the non-centroid loss, both defined using d.
Proof. 5-FJR with respect the centroid loss e is established in Lemma 11.
Caragiannis et al. [2] show that non-centroid greedy capture achieves 2-FJR with respect to the non-centroid loss f It is easy to see that because Algorithm 5 runs non-centroid greedy capture and uses the partition (CI,.... Ck) of the set agents N that it produces, retains this 2-FJR guarantee with respect to the non-centroid loss pm
F Experiments
In this section, our goal is to empirically compare proportionally fair algorithms designed in this work to classical clustering methods, in terms of both proportional fairness metrics and traditional metries that the classical methods optimize.
Because the classical methods take only a single distance metric d as input, we limit our empirical analysis to weighted single metric loss, which depends single metric d along with a parameter E [0, 1].
Algorithms. We evaluate four algorithms.
GC: Algorithm 5, which runs non-centroid greedy capture followed by greedy centroid selection, and attains 3 -ccore (Lemma 3). We denote it by 'GC'.
SemiBall: Algorithm 6, which mimics centroid greedy capture but with limited cluster switching, and attains 13
(Lemma 4). We denote it by 'SemiBall'. k-means++: This classical algorithm approximately optimizes the k-means objective, EiEN (1))?
2-2A
k-medoids: This classical algorithm approximately optimizes the k-medoids objective, ΣIEN
The k-means++ and k-medoids implementations are based on the Scikit-learn package in Python."
It is worth remarking that three of the four algorithms GGC, k-means+++ and k-medoids-take only the distance metric d as input and not the parameter A. Hence, the clustering returned by these methods is independent of X, although its approximations to proportional fairness metrics would depend on X.
Datasets.
We use three datasets from the UCI Machine Learning Repository [29]: Iris, Pima Indians Diabetes, and Adult. These are the three datasets used by Caragiannis al. [2] for their experiments with non-centroid clustering.
The Iris dataset contains 150 data points with measurements of sepal and petal dimensions across three species iris flowers.
The (Pima Indians) Diabetes dataset includes health-related indicators such as insulin dosage, glucose level, and number of pregnancies.
The Adult dataset consists of 48.842 instances, with both categorical features (such as race and education) and numerical features (such as age and hours worked per week). It is typically used for the classification task of predicting whether an individual's income
"Scikit-lean learn: https://scikittleeaa
33

---

GC
SemiBall
k-means+
k-medoids
16
Core Violation
FJR Violation
Weighted Loss Parameter À
Weighted Loss Parameter À
witt momtin-LLiuu Luuurerrr Listance
k-mpans Objectiv
k-medoids Objedvvv
2.0
1.00
2.5
0.50
57
2.8
37
5.6
03
0.8
Weighted Loss Pararneter
Weighted Loss Parameter
Weighted Loss Paramneter A
Core Violation
FJR Violation
4-
10
10
15
Number of Clusters k
Number of Clusters k
Aithin-Clusted Distance
lemeans obj dojective
Iomedoids Objective
2.4
1.4
10
15 Number of Clusters k
Number of Clusters k
Number of Clusters k
Figure 3: Results for the Adult (Census Income) dataset. The common legend appears at the top. The top five plots compare the algorithms on our five metrics when varying X E {0.1, 11,0... 0.2...., 0.9] and fixing 15, and the bottom five plots correspond to fixing À 0.5 and varying (5,6. (5.6....,255 25).
exceeds a specified threshold, but here is used for clustering the individuals. We apply one-hot encoding all categorical features."
'Categorical features encoded as numerical values (e.g., 1,2,3, 3, yield misleading distances the absence of the one-ho hot encoding.
34

---

GC
SemiBall
k-means
k-medoids
Core Violation
FJR Violation
9
6-
6
3
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Weighted Loss Parameter
Weighted Loss Parameter
Within Cluster Distance
Kemreans Objective
k-medoids Objective
1500
75:00-
1:50
60000-
1200
720
640
30000
08
Weighted Parameter
Weighted Parameter
Weighted Loss Parameter
Core Violation
FJR Violation
3
3
10
15
20
25
10
15
20
25
Number of Clusters
Number of Clusters
3200
Within Cluster Distance
Kemeans Objective
150000
-2000
2000
390000
k-medoids
3300
350000
Figure 4: Results for the Diabetes dataset. The common legend appears at the top. The top five plots compare the algorithms on our five metrics when varying À E (0.1, 0.2,..,, 0.9. and fixing 15, and the bottom five plots correspond to fixing À 0.5 and varying & {5, .5......220.. 25).
Metrics. We evaluate the four algorithms above five metrics.
35

---

GC
SemiBall
k-means+
k-medoids
Core Violation
FJR Violation
12
8
0.4
0.6
0.8
0.6
0.8
Weighted Loss Parameter À
Weighted Loss Parameter À
k-meeas Objective
k-medoids Objjectivv
10-
Within
Weighted Loss Parameter
Weighted Loss Parameter
Weighted Loss Parameter
12
Core Violation
FJR Violation
9
6
3-
Number of Clusters k
Number of Clusters k
242
k-meanios Dbyectie
Within Distance
K-means
122
Number Clusters
Number Clusters
Number Clusters
Figure Results for the Iris dataset. The common legend appears the top. The top five plots compare the algorithms on our five metrics when varying À E (0.1, 0.2,..,, 0.99 and fixing h 15. and the bottom five plots correspond fixing À 0.5 and varying & E (5.6....,25 25).
The first two metrics are core and FJR violations (i.e., the smallest a such that the clustering is in a-core a-FJR); these two are proportional fairness metrics. We compute the exact violations of core and FIR by solving integer linear programs, which, given a clustering, find deviating cluster (C, z)) recording the largest possible violation of the corresponding metric.
36

---

The next three metries are the k-means objective (stated above), the k-medoids objective (stated above), and average within-cluster distance, Ee [o Eijec, d(i.j) [30], which is another popu- lar objective; these three can be considered efficiency metrics. These metrics are easy to compute given a clustering.
Experimental setup. Following Chen al. [1], Caragiannis et al. [2]. we assume /V =M, and use the Euclidean Lg distance metric. We vary two parameters: the number of clusters k E {5, 6.... 25} and the weighted loss parameter À E {0.1, 0.2...., 0.9}. Specifically, we report experimental results when varying À E {0.1, 0.2. 0.9} while fixing h = 15, and when varying k E (5, ...... 25} while fixing 0.5.
While our algorithms (and the traditional baselines) scale well, solving integer linear programs to compute the exact core and FJR violations of the clustering they return is computationally intensive. Hence, for the two larger datasets, namely Adult and Diabetes, we randomly sample 100 data points in each of 40 independent trials. For the Iris dataset, since k-means++ uses randomized initialization step, we run it 20 times. Our plots show the five metrics above on average along with 95% confidence intervals.
The results for Adult, Diabetes, and Iris datasets are presented in Figures to 5, respectively, The qualitative takeaways are similar across the three datasets, so we use the Adult dataset (Figure 3) as an example to illustrate them.
Results.
First, our two algorithms, GC and SemiBall, achieve near-exact core and FJR, which is significantly better than their worst-case approximation guarantees from Lemmas and 4. The classical algorithms, k-means++ and k-medoids, admit notable core and FJR violations, and their fairness deteriorates as increases; this may be because le is still less than n/2, so an increase in k increases the number of small coalitions (of size close to n/ks) that can deviate. In particular, k-means++ is highly unfair, especially for larger values of l and smaller values of X (i.e., when the centroid loss is dominant). Interestingly, k-medoids is reasonably fair; Caragiannis et al. [2] observe it to be unfair for the setting of \ (non-centroid loss), but our results show that its fairness improves as À decreases, and becomes almost as fair as GC and SemiBall, producing near-exact core and FJR clustering, when
+ 0 (centroid loss).
The increased fairness of GC and SemiBall comes at the cost of decreased efficiency metrics as compared k-means++ and k-medoids. The efficiency loss is, however, small, especially when either k is large or X is small. Among our two algorithms, SemiBall seems to consistently perform better in efficiency metrics (and equal in fairness metries).
Hence, our main takeaway is that SemiBall and m-medoiss are compelling algorithmic choices for semi-centroid clustering; the choice between the two may rely on the value of k and X, well the principal's 's desired fairness-fffiienng tradeoff.
G Impossibility Results for Balanced Clustering
In this section, we provide two impossibility results for balanced clustering in our semi-centroid world. Informally, balancedness dictates that the partition of the set of agents contain clusters of roughly equal size. In many applications such creating groups of students for class projects or designing oral presentation sessions at a conference, this may be a desirable criterion.
Formally, one may refer to clustering X' {(C1, x æ1).... (CR, xR)} as balanced if |C,] E [L*/e], [ for all i E [k] (equivalently, ||C,| - |Cril < for all 1, E [k)). However, both our impossibility results hold even under the following weaker criterion.
Definition (Balanced Clustering). We call a clustering X' = ((C1, (Ck) balanced if, when & divides n. |C, n/le for all t [k]]
may be encouraging that non-centroid greedy capture indeed produces a balanced clustering under this weak version. The centroid greedy capture, however, offers such guarantees. This is because, while it still opens balls as soon as they capture [n/s]] uncaptured agents, (i) open balls continue to
'It may be possible that as soon as a ball covers at least [n/s]] uncaptured agents, it actually covers many more agents due to them being equidistant from the center. However, in this case, one can modify the algorithm to let the ball capture exactly [>/x] of the uncaptured agents contained in the ball, leaving the rest the boundary
37

---

grow and capture more agents, and (ii) agents are reassigned to the nearest center in the end. At least the second aspect is retained to some degree in both our algorithm for the dual metric loss (Algorithm 1) and one of our algorithms for the weighted single metric loss (Algorithm 6). This makes the final sizes of the clusters rather unpredictable (and not necessarily roughly equal).
That said, Algorithm 5, which runs non-centroid greedy capture followed by a greedy centroid selection step, does in fact produce balanced clustering and achieves 3 --core with respect to the weighted single metric loss. Unfortunately, this becomes unbounded when À approaches 0 (the centroid world). The next result shows that this is impossible to avoid when requiring a balanced clustering. Hence, our use of Algorithm 6, which computes an imbalanced clustering to achieve a finite core approximation in the small À regime (thus yielding a finite core approximation across the entire spectrum of X E [0, 1J) is necessary.
Theorem 10. For the weighted single metric loss with parameter À E [o, 11, there exists an instance in which no balanced clustering is in the a-core for any a VX
Proof. Consider the instance from Figure 1. Note that k 3 divides n 6, Set p 1. For
7X contradiction, assume that there exists a balanced clustering X' = (1),, (C2, 22), (C3, az)) with |C1] |C2| |Cal = 2, which is in the a-core for some < -
First, note that {a. b) must be one of the clusters. Suppose for contradiction that this is not the case. Then, at most one of agents a and b can be clustered with (i.e., at most one of (a) = (c) and (b)) (c) is true). Without loss of generality, suppose that agent a is clustered with e (a symmetric argument holds when agent is clustered with c). Then, to (2)) > A.p= = Vx; this lower bound holds due to the non-centroid loss part alone. Since agent b is clustered with an agent in {dl e, }} that it is infinitely far from, (x) = xc. Then, consider the deviating cluster ((a, b), a). which yields (a((, (a, a) À and Eo(fa, b), a) 1. Compared to X, agent b improves its loss by an infinite factor and agent a improves its loss by a factor of vx 1. which contradicts the fact A vx
that X is in the a-core for some a < Vx
Therefore, {a. b) must be one of the clusters and at least one of agents a and is not the centroid of this cluster. Without loss of generality, assume that the centroid is not at agent b. Then, consider the deviating cluster (fb, c), b). ((b,, b) = x.p= VX and (ob,,, c), b) p. In contrast, (x(X) > 1, so agent b improves by a factor of at least Vx Further, since {a, b) is a cluster, agent e must be clustered with agent from fd, e, f) that it is infinitely far from, yielding tx(x)) co. This means agent improves by an infinite factor. This contradicts the fact that X' is in the a-core for some This completes the proof.
Since the broader class of dual metric loss contains the weighted single metric loss for all X E [0, 1]. it follows that one cannot hope to design a balanced clustering algorithm that achieves any finite approximation to the core with respect to the dual metric loss.
Theorem 11. Under the dual metric loss, no algorithm that always produces a balanced clustering can achieve a-core for any a ? 1.
Proof. Suppose for contradiction that there exists an algorithm that always produces a balanced clustering in the a-core with respect to the dual metric loss. Then, consider the instance from Figure 1, and set the non-centroid metric as d = X d and the centroid metric as de = (1 - A) d for any À 1/a2. The induced dual metric loss is (,C, x:) X maxjec d(i..j) j) + (1 - -) xr). which is precisely the weighted single metric loss induced by distance metric d and parameter X. From Theorem 10, the core approximation achieved by any balanced clustering, including the one produced by the algorithm, must be at least
VX > a, which is the desired contradiction.
be captured by other balls in the future. This modification does not affect any of the guarantees achieved by the algorithm. Further, it produces balanced clustering as per Definition 4. Note that when & does not divide n, the last non-empty cluster may contain fewer than even [*/k] agents.
38


Reviews:
[{"review_id": "YRZA6f2OSz", "reviewer": "Reviewer_wHCe", "summary": "This paper introduces and investigates a generalized clustering framework called semi-centroid clustering, which unifies the two previously studied paradigms in proportionally fair clustering: centroid-based clustering (where loss is defined by distance to a cluster centroid) and non-centroid clustering (where loss depends on distances to other agents in the cluster). By simply combining the two associated cost functions under different settings, the authors initiate study on two important concepts for clustering, the core and fully justified representation (FJR). The major contribution in balancing these two clustering notions is a non-trivial polynomial-time constant approximation algorithm for the core under different loss functions for the two (simultaneous) objectives.", "questions": "How should a practitioner choose between different values of $\\lambda$ in a real application? How sensitive are the algorithms to the choice of metric or to approximation factors in MCC computation?\n\nHow do these algorithms scale in practice / what is their runtime guarantee?\n\nHow might general loss formulations might be captured in future work?", "limitations": "While the paper acknowledges that simultaneous core approximation is infeasible, it would be valuable to better discuss practical implications", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGTHS\n\nThis paper makes a significant theoretical contribution by bridging two previously distinct lines of research in proportionally fair clustering.\nThe dual and weighted metric loss models serve as natural and flexible interpolants between existing paradigms, readily allowing extension beyond the two main directions of clustering algorithm design.\nThe technical results are nontrivial, with the core approximation algorithm under dual metric loss is a highlight.\nIn the weighted single metric loss setting, the authors provide a nuanced analysis with a full picture of the approximation frontier as parametrized by a trade-off.\nThe authors further validate their problem definition and algorithm with experimental results, though these are entirely deferred to the appendix.\n\nWEAKNESSES\n\nMy main concern is that, while the results and framing are very interesting, the complete paper is largely contained in the appendix and suggests the work may actually be better situated for a more theory heavy conference.\nA short section in the main body summarizing key empirical findings would improve accessibility and demonstrate the algorithms’ relevance to real-world clustering scenarios.\nThe paper focuses on linear interpolation between the two cost metrics. The work does not explore alternatives to these, or discuss more expressive models\n\nThe one writing weakness I found is that the algorithm descriptions are a bit hard to parse for a non-expert in the field. If possible (with a longer page limit) more intuitive examples or figures to illustrate algorithm behavior would be beneficial to the reader.\n\n\nMINOR FIXES:\n- some inconsistency in the text with \"semi centroid\" vs \"semi-centroid\"\n- the presentation of Algorithm 1 is very cumbersome with notation\n- no figures or presentation of experimental results in main text", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and helpful review.\n\nWe will fix the typos you found and simplify the presentation of Algorithm 1 in the camera-ready version of the paper.\n\n**Regarding experiments:** While we would have liked to include them in the main body, we were restricted by the page length. In the camera-ready version, we will significantly expand on the paragraph in Section 1.1 that mentions the experiments to include a summary of our key findings. \n\n**To address your questions:**\n\n**Q1: Choosing $\\lambda$, metric, and MCC approximation.** \n\n*Choosing $\\lambda$:* In real-world scenarios, the correct value of $\\lambda$ would likely be very context dependent. For example, when clustering conference papers into sessions, it is presumable that the non-centroid loss (similarity between papers presented in the same session) matters significantly more than the centroid loss (relevance of a session's title to a paper in that session), leading the conference chair to select $\\lambda$ close to $1$. However, when clustering students for group projects, the centroid loss (how much a student prefers to work on a given project idea) may matter just as much as the non-centroid loss (how much two students like working with each other), leading the educator to select a more intermediate value of $\\lambda$. In general, the practitioner would use their insight as to which factor matters more (or if they both matter equally) and choose $\\lambda$ to reflect that. (See also our response to Reviewer SNW3's question.)\n\n*Choosing the metric(s):* There are two ways to understand your comment about sensitivity to the choice of the metric(s). \n\n1. *What if a practitioner feeds slightly distorted metrics $\\hat{d}^c$ and $\\hat{d}^m$ that are at most a $1+\\epsilon$ (multiplicative) factor off from the true $d^c$ and $d^m$ in measuring any pairwise distance?* In this case, we have checked that all our approximation guarantees scale gracefully in $\\epsilon$. The distortion factor just carries through all the equations. If the reviewers feel that this would be helpful, we will be happy to add formal robustness results in the appendix of the camera-ready version.\n\n2. *Could the approximation factors improve for specific choices of $d^c$ and $d^m$?* Prior work of Micha and Shah [2020] shows that for centroid clustering, the core approximation of GreedyCapture improves under the $L_2$ distance in a Euclidean space. It would not be surprising if the same holds in our semi-centroid setting. This would require novel arguments and is left to future work. \n\n*Choosing MCC approximation factor:* For our algorithms, an $\\alpha$ approximation of MCC smoothly translates to an $\\alpha$ approximation of FJR and a $\\frac{1}{2}(1+\\sqrt{\\alpha(\\alpha+8)}+2)$ approximation of the core (see Theorem 6 and Lemma 1, respectively). That said, a practitioner would likely only choose one of two values: $\\alpha=1$, if running time is not a concern and the practitioner is willing to solve a simple MILP with $O(|N|+|M|)$ variables and constraints to find a $1$-MCC cluster, and $\\alpha=4$, if polynomial running time is a concern and the practitioner wishes to use Algorithm 7.\n\n**Q2: running time.** With $n=|N|$ and $m=|M|$ (and noting that $k \\le n$), a simple implementation of GreedyCapture runs in $O(n m \\log (nm))$ time. Algorithm 4 for computing a $4$-MCC cluster runs GreedyCapture $m$ times, meaning Phase 1 of Algorithm 1 runs in $O(n m^2 \\log (nm))$ time. Phase 2 of Algorithm 1 runs in $O(n^2)$ time. This puts the overall runtime of Algorithm 1 at $O(n m^2 \\log (nm))$. Our algorithms for the single-metric setting have similar runtimes. Algorithms 5 and 6 both rely on greedy capture and can be implemented in $O(n^2 \\log n + km)$ and $O(n m \\log (nm) + kn)$ time, respectively. We will add these details in the camera-ready version.\n\nEmpirically, we observed that our algorithms are slower than k-means and k-medoids. As an example, the table below shows the runtimes (in seconds) of Algorithm 6, k-means and k-medoids on the Adult dataset subsampled to different sizes, fixing the default values of $k=15$ and $\\lambda=0.5$. Please see the Appendix E for details of the experimental setup and implementation. Designing faster (perhaps even near-linear time) algorithms with provable proportional representation guarantees remains an exciting open question for future research. \n\n| # Points | Alg 6   | k-means | k-medoids |\n| -------- | ------- | ------- | -------   | \n| 800      | 0.254s  | 0.137s  | 0.025s    |\n| 6400     | 13.75s  | 1.155s  | 3.283s    |\n| 25600    | 291.25s | 3.401s  | 128.85s   |\n\n**Q3: general losses.** For arbitrary loss functions, the core remains inapproximable to any finite degree, even in non-centroid clustering [Caragiannis et al., 2024], whereas (exact) FJR remains feasible (Theorem 6). An interesting future direction would be to find families of loss functions that are more general than our dual metric loss, but still allow a reasonable approximation of the core."}, {"review_id": "zaEmgYYxCx", "reviewer": "Reviewer_SNW3", "summary": "In this paper the authors explore two notions of fairness in a clustering model that lies between centroid and non-centroid clustering. The task is to partition a set of $n$ data points (agents) into $k$ clusters, each defined by a center point and a group of assigned agents. An agents loss is defined as the sum of the distance to its assigned center and the maximum distance to any other agent within the same cluster. A clustering is considered unfair if there exists a group of $\\frac{n}{k}$ agents who could form their own cluster in which each member would experience a (by some amount) lower loss.\n\nThe authors analyze two fairness notions—the 'core' and 'fully justified representation'— and provide both upper and lower bounds on their approximation. They distinguish between two settings: one where the distance towards the center and the distance to other agents are measured using different metrics and another where the two metrics are identical, up to a constant factor. For both settings, the paper presents efficient algorithms that achieve constant-factor approximations of the fairness notions.", "questions": "What is the motivation for allowing two different metrics in the loss function? Why would an agent measure the distance to the center differently than the distance to the other agents?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The authors approach a natural question: Given existing fairness results for both centroid and non-centroid clustering, what if an agent cares about both being close to the center as well as to other members of their cluster? While the application-based motivation is somewhat weak, the problem itself is interesting and bridges the gap between different approaches in the literature.\nThe paper is well written and gives a clear overview of prior related work. The results seem significant and contribute to the understanding of fairness in clustering. With most of the proofs in the appendix, the authors generally succeed in conveying the key ideas behind their results and algorithms. That said, Theorem 1 would benefit from including the example instance from the proof in the main body. For Theorem 4 and 5 (or result summary table) a figure plotting the upper and lower bounds as a function of $\\lambda$ would greatly enhance clarity and help readers to interpret the bounds and the gap between them. \n\nTypo in line 226: with respect the -> with respect to the", "was_revised": true, "final_justification": "My questions were nicely answered. While they did not fully resolve my slight concerns about the practical relevance of the topic, I still recommend acceptance.", "rebuttal": "Thank you for your review.\n\n**Regarding the example in Theorem 1:** Indeed, the counterexample used to prove Theorem 1 is insightful as we later reuse it to prove Theorems 5 and 9 too. We'll be happy to add it to the main body.\n\n**Plot of upper and lower bounds:** This is a great idea. We will be happy to add such a plot to the main body.\n\n**Q1: Motivation for two different metrics.** There are several scenarios where having different metrics can be helpful. We briefly describe the motivation in Section 6, but agree that this belongs to the introduction and will move it there in the camera-ready version.\n\nOne such application is assigning students to groups for a class project. In this setting, the agents would be the students, and the centroids would be project topics. The non-centroid metric space would represent the friendships of the students, while the centroid metric would represent students' preferences over project topics. It may be impossible to embed both these preferences in a single metric space, as we may have two students who are very close friends, but have very different preferences over project topics. The dual metric model allows us to take this into account and find a grouping of the students that balances placing friends in the same group with assigning students to topics of their liking."}, {"review_id": "BN7PDVpn5A", "reviewer": "Reviewer_sbW8", "summary": "Motivated by the fact that the main algorithms for proportional non-centroid and centroid clustering (called Greedy Capture) look almost the same,\nthe authors consider a clustering variant where one simultaneously computes a non-centroid and a centroid clustering, for possibly separate metrics.\nThe resulting problems partitions the given points into k clusters and maps a center point to each of these clusters.\nThe goal is to find such a clustering that is (approximately) proportional simultaneously for the centroid-based and the non-centroid based loss function, i.e.,\nthe distance to the center and the maximum distance to any other point in the same cluster.\nThe authors present a modification of the Greedy Capture algorithm, where one first builds a tentative cluster and then allows some agents to swap clusters and makes use of a subroutine that is NP-hard to compute, but efficiently approximable.\nAssuming access to optimal solutions to the subroutine, the authors show that there always exists a clustering in the 3-core,\nand using the approximate subroutine, the authors show that one can efficiently compute a clustering in the (3+2sqrt(3))-core.\n\nThe authors further show some results for the case that centroid and non-centroid clustering use the same metric and also consider a relaxation of the core notion called FJR.\nThese results are based mainly on small variations of existing algorithms.", "questions": "- What is the best factor alpha obtainable by Algorithm 1 when only focusing only on the centroid loss or only on the non-centroid loss?\n- Suppose that you are given a non-centroid clustering in the alpha-non-centroid core. Is it possible to extend this to a semi-centroid clustering that is in the alpha*beta-core for some constant beta?\n\n- I suggest that you slightly extend on the motivation for federated learning. It seems pretty plausible, but needs to be more detailed if the greater audience should be able to follow.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- From a theoretical perspective, the authors approach the intriguing question why almost the same algorithm works for two quite different variants of clustering (albeit with similar fairness notions) and find a satisfying answer: For optimizing both notions at the same time, one needs to deviate a bit further from the Greedy Capture approach. The practical motivation via federated learning also seems plausible in the sense that, if I would rather deviate to another model, then I also need to find a group of peers who would join me in the deviation.\n- The paper presents itself very well, the proofs are clearly written and easy to verify.\n\nWeaknesses\n- While the theoretical motivation is very strong, the practical motivation is a bit faltering to me. I do believe that the federated learning motivation could somehow be interesting, and I like the idea of having the centroids represent a model. I do believe that it would help add more details to this motivation.\n- Overall, the technical depth of the work is not too high. The new Algorithm 1 is a nice modification from Greedy Capture, but still lends many elements from the algorithms by Chen et al. and Caragiannis et al., such as the most cohesive cluster subroutine.\n- The impact of the work is not too high. In all, the work seems a bit niche and incremental.", "was_revised": true, "final_justification": "I increase my score mainly due to a slightly new perspective on the paper.\nThe idea of combining the non-centroid and centroid versions of Greedy Capture itself already deserves some credit: While maybe a theoretical thought process, it nicely ties the two directions within proportional clustering together. It now just happens that this also works for two different metrics.", "rebuttal": "Thank you for your detailed review.\n\n**Q1: Best factor for centroid or non-centroid clustering.** The approximation guarantees of Algorithm 1 are closely controlled by the growth factor $c$. Recall that $c$ dictates how much an agent $i$ is allowed to hurt the losses of other agents when switching into their cluster for its own benefit during Phase 2 of the algorithm.\n\nTheorem 2 indicates that setting $c=3/2$ can already recover $3$-core guarantee for each of centroid and non-centroid clustering (by setting the other distance metric as $0$). However, setting different values of $c$ can recover optimized guarantees in each setting from prior work. \n\nSpecifically, when we set $c=0$, agents will not be allowed to switch away from their original cluster if it hurts the agents in that cluster at all. This essentially means that Phase 2 of the algorithm will be skipped, and Algorithm 1 will roughly mimic the behaviour of the non-centroid GreedyCapture of Caragiannis et al. [2024] to achieve $2$-core for non-centroid clustering. Similarly, if we set $c=\\infty$ (formally, if in Phase 2 we say that every agent can simply switch to its favourite cluster, regardless of the loss it causes other agents), then the algorithm would mimic the centroid GreedyCapture of Chen et al. [2019] to achieve $(1+\\sqrt{2})$-core for centroid clustering.\n\nWith these respective growth factors, the only difference between our Phase 1 and the GreedyCapture algorithms for these settings is that Algorithm 1 finds the Most Cohesive Cluster at each step rather than finding the clusters by growing a ball around each agent or cluster center. By analyzing the original greedy capture proofs in both settings, it is easy to see this difference does not impact any of the guarantees.\n\n**Q2: Extending non-centroid clustering to semi-centroid clustering.** That's a great question. The answer is no. This follows from the fact that the non-centroid GreedyCapture of Caragiannis et al. [2024] computes a balanced clustering (where each cluster is of size at most $\\lceil n/k \\rceil$) in the 2-core (i.e., $\\alpha=2$ in your question). However, in Appendix F, we show that there are instances of semi-centroid clustering in which every balanced clustering has core approximation at least $1/\\sqrt{\\lambda}$. Hence, when $\\lambda = o(1)$, one cannot guarantee a constant $\\beta$ in your question.\n\n**Q3: Motivation**: Indeed, we will expand our federated learning motivation to explain the setup more in detail. That said, our goal was to demonstrate that the motivations used by prior work for centroid and non-centroid clustering may already involve *at least a slight* semi-centroid consideration. We discuss new motivating examples in Section 6 that more directly align with semi-centroid clustering, which we plan to discuss early in Section 1 in the camera-ready version (see also our responses to Reviewer wHCe's Q1 and SNW3's Q1)."}, {"review_id": "HSFekpLxoF", "reviewer": "Reviewer_ZM2J", "summary": "The paper studies proportional clustering. In particular, it studies a setting generalizing both centroid and non-centroid clustering. That is, the goal is to partition a set of points (like in non-centroid clustering) and assign each partition to a center (like in centroid clustering) at the same time, with the loss of each agent being a combination of its centroid and non-centroid loss. The objective studied in the paper is proportional fairness. That is, ideally, with n points and k cluster centers approximately n/k points should deserve their own partition and center. The paper introduces several definitions of proportional fairness (depending on the loss function of the points and the strength of the deviating coalitions) and gives algorithms and lower bounds for achieving these proportional fairness definitions.", "questions": "I would be interested to hear answers to the two questions I had in my weaknesses section. \n\n1. Are you aware of any other papers studying this setting or a related setting where one might need both centroid and non-centroid clustering?\n2. In the setting in which N = M, for a given cluster (C, x) the cluster center x must not necessarily be a part of C (and this is also not enforced by the algorithms as far as I can see). Do the results still hold if this is enforced or might this not even be desirable?\n\nWith sufficient answer to these questions (in particular the first question) I am willing to upgrade to an accept.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: Proportional fairness is an interesting topic and this paper makes a novel contribution to it that should be of interest to the researchers working on proportional fair clustering. In fact, I have  asked myself something similar akin to Theorem 1 while reading through the paper of Caragiannis et al. and am happy that there is a nice simple (albeit negative) solution to this. I also find the study of combining centroid and non-centroid clustering to be somewhat interesting and novel. The algorithms presented throughout the paper seem are for the most part non-trivial and clearly presented, and I think the authors largely do a good job at making the paper readable. The results also seem technically interesting, and I think the two-phase Algorithm 1 is a nice twist on the usual Greedy Capture based algorithms.\n\nWeaknesses: \n\nI think one obvious weakness of the paper is the setting. In particular (while seemingly novel), I find the study of both centroid and non-centroid clustering at the same time to be slightly unnatural, and I think it could have been better motivated in the paper. Are you aware of any other papers studying this setting or a related setting where one might need both centroid and non-centroid clustering?\n\nSecondly, one thing I found a bit unnatural, is that in the setting in which N = M, for a given cluster (C, x) the cluster center x must not necessarily be a part of C (and this is also not enforced by the algorithms as far as I can see). Do the results still hold if this is enforced or might this not even be desirable?\n\nThe presentation of the paper could be improved at times. In particular, I think the bounds presented in Lemma 4, Theorem 5, Theorem 6 should be explained. For further things, see detailed comments later. \n\nFinally, while I usually think that a theory paper does not need experiments, I think they would be nice. In fact, the paper even has experiments and I would have loved to see them in the main text. In particular, I would have been interested to see whether the worst case presented in Theorem 1 actually happens in real world instances.\n\nDetailed Comments:\n-The equivalence between the two forms of k-means presented at the start of the paper do not hold for the setting here, in which there is separate candidate set.\n- “which is a principle at the heart of our democratic institutions.“ I am not a fan of this phrasing. Proportionality is not even at the heart of American institutions. \n-I find Table 1 to be quite unreadable without context. In particular, I think that every variable in a table should be introduced to make the table understandable.\n-”approximation to the core” without context, it is not known what kind of “approximation” this is supposed to be\n- For stylistic purposes, the order of the losses should be the same in lines 129 and 136\n- I think sorted references are easier to access for the reader. Also, you currently have abbreviated first names for some, and spelled out for others, papers 13 and 17 are no longer forthcoming, and paper 28 has a conference version.", "was_revised": true, "final_justification": "Solid paper, interesting theory (also interesting experiments, albeit a bit hidden, but I trust the authors to highlight this better)", "rebuttal": "Thank you for your detailed and helpful review. \n\n**Comments:**\n\n* *Equivalence between two forms of k-means*: We agree that this phrasing was misleading. We meant to provide only an example setting (where $\\mathcal{M}$ is the entire Euclidean space and $d = L_2$) in which the \"centroid\" and \"non-centroid\" k-means become equivalent. We will clarify this detail in the camera ready version.\n\n* *Regarding proportionality principle wording:* We agree with your comment and will revise this as: \"which is a principle inspired from the democratic ideal of proportional representation that aims to give groups influence proportional to their size and cohesion.\" \n\n* We will also make the changes to the references and the stylistic changes you suggested.\n\n* *Regarding experiments:* As we mentioned to Reviewer wHCe, we will update Section 1.1 in the camera-ready version to include a more detailed synopsis of our empirical findings.\n\n**Questions:**\n\n**Q1: Motivation for semi-centroid clustering**: Please see our responses to Reviewer wHCe's Q1, SNW3's Q1, and sbW8's Q3. In Section 6, we discuss motivating applications such as assigning students to group projects and scheduling talks of papers accepted to a conference, where both non-centroid and centroid losses matter simultaneously.\n\nQuoting from our response to Reviewer SNW3:\n\n> One such application is assigning students to groups for a class project. In this setting, the agents would be the students, and the centroids would be project topics. The non-centroid metric space would represent the friendships of the students, while the centroid metric would represent students' preferences over project topics. It may be impossible to embed both these preferences in a single metric space, as we may have two students who are very close friends, but have very different preferences over project topics. The dual metric model allows us to take this into account and find a grouping of the students that balances placing friends in the same group with assigning students to topics of their liking. \n\nFor scheduling talks of papers accepted to a conference, the non-centroid loss would model the (dis)similarity between two papers, while the centroid loss would model the (ir)relevance of a session's title to a paper in that session. \n\nWhile there are several real-world applications where agents are grouped into clusters and each cluster is assigned a \"centroid\", coming to your question, we are not aware of any technical papers or settings studied in prior work that model both the non-centroid and centroid aspects simultaneously. This speaks to the conceptual novelty of our work.\n\n**Q2: The case of $\\mathcal{M}=\\mathcal{N}$.** This is an extremely interesting question. Due to space constraints, we were only able to allude to this special case in the Discussion (see line 366).\n\nFor the dual metric setting, Algorithm 1 with $\\mathcal{M}=\\mathcal{N}$ indeed does not guarantee that the centroid for each cluster will be an agent from that cluster because the MCC computed at a step may select a centroid from outside the cluster. It is easy to see that this is inevitable if one wishes to prevent clusters of the form $(C,x)$ with $x \\notin C$ from deviating and significantly improving. However, if the desideratum is weakened to approximate core against only deviating clusters $(C,x)$ that satisfy $x \\in C$, we do not know if it can be achieved for the dual metric setting.\n\nHowever, whenever $\\mathcal{M} = \\mathcal{N}$, it is presumable that both centroid and non-centroid losses are represented by the same metric, meaning that we are in the case of weighted single metric loss. Here, it is worth noting that one of our algorithms, Algorithm 5, naturally achieves your desideratum: Algorithm 5 simply runs non-centroid GreedyCapture (where balls grow around the agents) and then assigns each cluster the centroid closest to the agent $i \\in C$ at the center of the ball that captured the cluster. When $\\mathcal{M} = \\mathcal{N}$, we are guaranteed to have $x=i$ WLOG, meaning that the centroid will always be an agent in the cluster. Algorithm 5 gets a core approximation of $\\frac{2}{\\lambda}$, which is reasonable for all lambda values that are not too close to 0. \n\nThat said, Algorithm 6, which allows us to achieve finite core approximation for the regime of $\\lambda$ close to $0$ under weighted single metric loss, does not always select a centroid from within the cluster. Whether this can be enforced remains an interesting open question. \n\nWe will add this discussion to Section 6."}]

Author rebuttal:

Meta-review: The paper unifies two versions of an algorithm called greedy capture for proportionally fair clustering. Fair clustering is a big trend and the submission is very interesting. While the reviewers are not fully convinced of the practical motivation, the technical contribution convinced all reviewers and the area chair to recommend acceptance of the paper.
Decision: Accept (spotlight)