Proportional Fairness in Non-Centroid Clustering
Authors: Ioannis Caragiannis
Evi Micha
Nisarg Shah
Venue: NeurIPS 2024 poster (2024)
Keywords: clustering
proportional fairness
core
fully justified representation
auditing
Primary area: fairness

Abstract: We revisit the recently developed framework of proportionally fair clustering, where the goal is to provide group fairness guarantees that become stronger for groups of data points that are large and cohesive. Prior work applies this framework to centroid-based clustering, where points are partitioned into clusters, and the cost to each data point is measured by its distance to a centroid assigned to its cluster. However, real-life applications often do not require such centroids. We extend the theory of proportionally fair clustering to non-centroid clustering by considering a variety of cost functions, both metric and non-metric, for a data point to be placed in a cluster with other data points. Our results indicate that Greedy Capture, a clustering algorithm developed for centroid clustering, continues to provide strong proportional fairness guarantees for non-centroid clustering, although the guarantees are significantly different and establishing them requires novel proof ideas. We also design algorithms for auditing proportional fairness of a given clustering solution. We conduct experiments on real data which suggest that traditional clustering algorithms are highly unfair, while our algorithms achieve strong fairness guarantees with a moderate loss in common clustering objectives.

Proportional Fairness in
Non-Centroid Clustering
Ioannis Caragiannis Aarhus University iannis@cs. au.d.
Evi Micha Harvard University emi chi@seasss hww.aard.ddd...................d edu
Nisarg Shah University of Toronto nisargocs. toronto. edu
Abstract
We revisit the recently developed framework of proportionally fair clustering, where the goal is to provide group fairness guarantees that become stronger for groups of data points (agents) that are large and cohesive. Prior work centroid clustering, where the loss of an agent is
applies this framework its distance to the centroid assigned to its cluster. We expand the framework to non-centroid clustering, where the loss of an agent a ionction of the other agents in its cluster, by adapting two proportional fairness criteria. the core and its relaxation, fully justified representation (FJR) to this setting.
We show that the core can be approximated only under structured loss func- tions, and even then, the best approximation we are able to establish, using an adaptation
the GREEDYCAPTURE algorithm developed for centroid clustering [1, 2], is unappealing for natural loss function. In contrast, we design a new (inefficient) algorithm, BRREDYCCOHSVVECLUSTEEEN which achieves the relaxation FJR exactly under arbitrary loss functions, and show that the efficient GREEDYCAPTURE algorithm achieves a con- stant approximation of FJR. We also design an efficient auditing algorithm, which estimates the FJR approximation of any given clustering solution up constant factor. Our experiments tional clustering algorithms are highly unfair, whereas CAPEDYR is considerably fairer and incurs only a modest loss in common clustering objectives.
real data suggest. that tradi-
Introduction
Clustering is a fundamental task in unsupervised learning, where the goal is to partition a set of n points into clusters C = (C1,..., Ck) in such way that points within the same cluster are close to each other (mcasured by a distance function d) and points in different clusters are far from each other. This goal is materialized through variety of objective functions, the most popular of which is the k-means objective: Σ |ि. En.yec, d(x,y)².
When the points are in Euclidean space, the k-mcans objective can be rewritten as E Exec, d(x, p4)2, where 14 [ Exec, I is the mean (also called the centroid) of cluster C,,² This gives rise to centroid clustering, where deciding where to place the k cluster centers is viewed as the task and the clusters are implicitly formed when each point is assigned to its nearest cluster center.
CCentroids can be defined in non-Enclidean spaces, e.g., as μ4 = arg min, 1
led Exec, d(a, v)
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

In the literature on fairness in centroid clustering, the loss of each data point (hereinafter, agent) is defined as the distance to the nearest cluster center [1]; here, the cluster centers do not merely help rewrite the objective, but play an essential role. This is reasonable model for applications such as facility location, where the loss of an agent indeed depends on how much they have to travel to get to the nearest facility.
But in other applications of clustering, we simply partition the agents and agents prefer to be close to other agents in their cluster there are no "cluster centers" that they prefer to be close to. For example, in clustered federated learning [3], the goal to cluster the agents and have agents in each cluster collaboratively learn a model; naturally, agents would want other agents in their cluster to have similar data distributions, so the model learned is accurate on their own data distribution." 2 Other examples where we want to cluster nearby points together without defining cluster centers include document clustering (6), image segmentation for biomedical applications [7], and social network segmentation [8].
While there exist plenty of clustering objectives which do not require defining cluster centers (such as the first formulation of the k-means objective above), in order to reason about fairness we need define the loss of each agent under non-centroid clustering and explore the tradeoff between the losses of different agents. We initiate the study of proportional fairness in non-centroid clustering.
We follow the idea of proportional fairness outlined in a recent line of work [1, 2, 9, 10), which ensures that no group of at least n/k agents should "improve" (formalized later) by forming a cluster of its 3 Our main research questions are:
Can we obtain compelling proportional fairness guarantees for non-centroid clustering with centroid clustering? Do the algorithms known to work well for centroid clustering also work well for non-centroid clustering? Can we audit the proportional fairness of a given algorithm?
1.1 Our Contributions
In non-centroid clustering, we are given a set N of n points (agents) and the desired number of clusters k. The goal is to partition the agents into (at most) clusters C = (Ci...., C Each agent i has a loss function E,, and her loss under clustering C' is (C(()), where C(i) denotes the cluster containing her. We study both the general case where the loss functions of the agents can be arbitrary, and structured cases where the loss of an agent for cluster is the average or maximum of her distances - according to a given distance metric to the agents in the cluster. In the latter case, our theoretical results hold for general metric spaces, as they rely solely on the satisfaction of the triangle inequality.
We study two proportional fairness guarantees, formally defined in Section 2: the core [11] and its relaxation, fully justified representation (FJR) [12]. Both have been studied for centroid clustering [1, 2, 10), but are the first to study them in non-centroid clustering.
A summary of selection of our results is presented in Table 1, with the cell values indicating approximation ratios (lower is better, 1 is optimal).
Loss Functions
Core UB
Core LB
FJR
Arbitrary
X
1
Average
O(*/a) (polytime)
1.3
1 (4 in polytime)
Maximum
2 (polytime)
1
1 (2 in polytime)
Table 1: The feasible core and FJR approximation guarantees, both existentially and in polynomial time. In each case, we can obtain a better FJR approximation than the core approximation.
"Prior work formulates this as centroid clustering [4, 5). where the principal also chooses a model for each cluster, but this goes against the federated learning setting. Groups with fewer than n/k agents are not deemed to be eutitled to form cluster.
2

---

Our results show the promise of FJR: while it is a slight relaxation of the core, it is satisfiable even under arbitrary loss functions, whereas the core can be unsatisfiable even under more structured loss functions. The existential result. for FJR is achieved using a simple (but inefficient) algorithm we design, CHERRDYCOHRSSVFFLLTSTTRER
which is an adaptation of the Greedy Cohesive Rule from social choice theory [12]. The core approximations as well as efficient FJR approximations are achieved using an efficient version of it, which turns out to be adaptation of the GREEDYCAPTURE algorithm that has been introduced for centroid clustering [1, 2). We show that the FJR approximation achieved by FREEDYCAPTURE stems from the fact that its key subroutine achieves constant approximation of that of the algorithm.
Next, we turn to auditing the FJR approximation of a given chustering. Surprisingly, we show that the same technique that we use to algorithmically achieve a constant approrimattin of FJR can be used to also estimate the FJR approrimation of any given clustering, up to constant factor (4 for the average loss and 2 for the maximum loss).
We compare GREEDYCAPTURE to popular clustering methods, k-means+++ and k-medoids, on three real datasets. We observe that in terms of both average and maximum loss, GreedYCAPtURE provides siguificantly better approximations to both FJR and the core, and this fairness advantage comes at only a modest cost in terms of traditional clustering objectives, including those that k-means++ and k-medoids are designed to optimize.
1.2 Related Work
In recent years, there has been an active line of research related to fairness in clustering [13]. With a few exceptions, most of the work focuses on centroid-based clustering, where each agent cares about their distance from the closest cluster center. Mostly related to ours is the work by Chen et al. [1], who introduced the idea of proportionality through the core in centroid clustering. Their work has been revisited by Micha and Shah [2] for specific metric spaces. More recently, Aziz et al. [10] also introduced the relaxation of the core, fully justified representation, in centroid- based clustering. While one of our main algorithms, GREEDYCAPTURE is a natural adaptation of the main algorithm used in all these works, there are significant differences between the two scttings.
First, in centroid-based clustering, GREEDYCAPTURE provides a constant approximation to the core[1], while in the non-centroid case this approximation is not better than ((n/)) for the average loss function. Second, in centroid-based clustering, CAPTURE returns a solution that satisfies FJR exactly[10]. Here, for the nou-centroid case, even though we know that an exact FJR solution always exists, GREEDYCAPTURE is shown to just provide an approximation better than 4 for the average loss and 2 for the maximum loss. In more specific metric spaces, Micha and Shah [2] show that a solution in the core always exists in the line. Here, we demonstrate that while this remains true for the maximum loss, is not the case for the average loss, where the core can be cmpty. Finally, Chen et al. [1] conducted experiments using real data in which +-means++ performs better than However, for the same datasets, we found that GREEDYCAPTURE significantly oulperforms k-means++ the non-centroid seiting.
Fairness in ron-centroid clustering has received significantly less attention. Ahmadi et al. [14] recently introduced a notion of individual stability which indicates that no agent should prefer another cluster over the one they have been assigned to. Micha and Shah [2] studied the core when the goal to create a balanced clustering (i.e. all clusters have almost equal size) and the agents have positive utilities for other agents. More generally, the hedonic games litcrature (o.g., see [15] for an carly survey on the topic and [16] for a recent model that is close to the current paper) is also relevant to non-centroid clustering as it examines coalition formation. While the core concept has been extensively studied in hedonic games, there are two main differences with our work. First, subsets of any size can deviate to form their own cluster, rather than only proportionally eligible ones, and second, no approximate guarantees to the core have been provided, to the best of our knowledge.
3

---

2 Model
For 1 E N, let [t] (1,.... (1)..., f). We are given a set N of agents, and the desired number of clusters k. Each agent E N has associated loss function & 2 2 + Rgo, where (,( is the cost to agent i for being part of group S. k-chustering" C = (Ci,..., Cx) is a partition of N into & clusters, 5 where C n CC = 9 for t * and - C2 = N. With slight abuse of notation, denote by C(i) the cluster that contains agent i. Then, the loss of agent i under this clustering is (C((i))
Loss functions. We study three classes of loss functions; for each class, we sook fairness guarantocs that hold for any loss functions the agents may have from that class. A distance metric over N is given by d: N x N Rzo, which satisfics: (i) d(2, i) 0 for all i E N, (ii) j(i,j) = i(j.i) for all i,j E N, and (iii d(i,j) & d(i,k) + d(k; for all i.j. N (triangle inequality).
Arbilrary losses. In this most general class, the loss (5) can be an arbitrary non-negative number for each agent i E N and cluster S3i.
Average loss. Here, we are given a distance metric d over N, and (((S) = [ST Ejes d(i,,) for each agent E N and cluster S 3 i. Informally, agent prefers the agents in her cluster to be close to her on average.
Marimum loss. Again, we are given distance metric over N, and ((S) = maxjes j) for each agent i E N and cluster S 3 i. Informally, agent i prefers that no agent her cluster be too far from her.
3 Core
Perhaps the most widely recognized proportional fairness guarantee is the core. Informally, an outcome is in the core if no group of agents S N can choose another (partial) outcome that (i) they are entitled to choose based on their proportion of the whole population (IS)/MN)),
and (ii) makes every member of group S happier. The core was proposed and widely studied in the resource allocation literature from microeconomies [11, 17, 18], and it has been adapted recently to centroid clustering [1, 2]. When forming clusters out of n agents, group of agents S' is deemed worthy of forming a cluster of its own if and only if |S| > n/k. In centroid clustering, such a group can choose any location for its cluster center. In the following adaptation to non-centroid clustering, no such consideration is required.
Definition (a-Core). For a 2 1, a k-clustering C = (C1...., Ck) is said to be in the a-core if there is group of agents S S N with |S| > n/k such that a L,(S) L((((i) for all i E S. We refer to the 1-core simply as the core.
Given clustering C, if there exists a group S that demonstrates a violation of the a-core guarantee, i.e., S has size at least n/s and the loss of each i E for S lower than 1/a of her own loss under C, we say that S deviates under C and refer to it as the deviating coolition. We begin by proving a simple result that no finite approximation of the core can be guaranteed for arbitrary losses.
Theorem 1. For arbilrary losses, there exists an instance in which no a-core clustering crists for any finite a.
Next, for the more structured average loss function, we prove that the core can still be empty, albeit there is now room for finite approximation. The proof, with intricate construction, is delegated to Appendix A.
Theorem 2. For the average loss, there erists an instance in which no a-core clustering crists for a < 1tv3 = 1.366.
2
To complement Theorems 1 and 2, we show the existence of clustering in the O(n/s)-core (resp., 2-core) for the average (resp., maximum) loss. Despite significant effort, we are unable
'We simply call it clustering when the value of k is clear from the context. Technically have up to k clusters as Ct is allowed to be empty for any E [k].

---

ALGORITHM 1: CreeDDYCOHESVVCLLLSTEEEEAA
Input:
Set of agents N, metric d, number of clusters
Output: k-clustering C' = (Ci....Ce C+)
N' N;
// Remaining set of agents
j 1;
// Current cluster number
while N' + 0 do
C A(N, d, [w/+]);
// Find and remove the cohesive cluster
N N' As;
J j+
end
Cj Cjt C2 f 0;
return C = (CI...., Ck);
ALGORITHM 2: SMALLESTAGENTBALL
Input: Subset of agents N' C CN,, metric d, threshold integer т
Output: Cluster S
then return S t S:N;; for E N' do
if [NN &
& + r-th closest agent in N' to agent i;
// Ties are broken arbitrarily
r d(i; // Smallest ball centered at agent capturing at least 7 agents
end
< arg min Ti:
return S t the set of closest agents in N' to agent i":
to determine whether the core is always non-empty for the maximum loss, or whether a constant approximation of the core can be guaranteed for the average loss, which we leave as tantalizing open questions.
Open Question 1: For the maximum loss, does there always exist clustering in the core?
Open Question 2: For the average loss, does there always exist clustering in the a-core for some constant a??
Our algorithms. For the positive result, design simple greedy algorithm, GREEDYCO HESIVECLUSTERING (Algorithm 1). It uses a subroutine A, which, given a subset of agents N' N, metric d, and threshold т, finds a "cohesive" cluster S. Here, the term "cohesive" informally used, but we will see a formalization in the next section. The threshold т is meant indicate the smallest size at which group of agents deserve to form cluster, but A can return a cluster of size greater, equal, or less than T.
The algorithm
as A in this section is given SMALLESTAGENTTBM (Algorithın 2). finds the smallest. ball centered at agent that captures least т agents, and returns set of 7 agents from this ball. We call this algorithm with the natural choice of T = [,/h], so
iteratively finds the smallest agent-centered ball containing [*/k] agents and removes [n/k] in that ball, until fewer than
[*/k] agents remain, at which point all remaining agents are put into one cluster and any remaining clusters are left empty.
Overall,
is an adaptation of the GREEDYCAPTURE algorithm proposed by Chen et al. [1] for centroid clustering with two key differences our non-centroid case: (i) while they grow balls centered at feasible cluster center locations, grow balls centered al the agents, and (ii) while they continue to grow ball that already captured [n/k]] agents (and any agents captured by this ball in the future
placed in the same cluster), we stop a ball as soon it captures [*/]] agents, which

---

is necessary in our non-centroid case, 6 Nonetheless, due to its significant resemblance, we refer to the particular instantiation as GREEDYCAPTURE hereinafter. The following result is one of our main results, with an intricate proof found in Appendix A.
Theorem 3. For the average (resp., marimum) loss, the GREEDYCAPTURE algorithm is guaranteed to return a clustering in the (2- [1/k]] core (resp., 2-core) in O(kn) time complenity, and these bounds are (almost) tight.
In many applications of clustering, such clustered federated learning, the average loss is realistic because the agent's loss depends on all the agents in her cluster, and not just on single most distant agent. Hence, it is little disappointing that the only approximation to the core that we are able to establish in this case is a = O(*/s), which is rather unsatisfactory. We demonstrate two ways to circumvent this negative result. First, that any deviating coalitions show that any consland next section, we explore a different approach: we relax the core to a slightly weaker fairness guarantee, which we show be satisfied exactly, even under arbitrary losses.
consider demanding of size at least 8 n/v for some 5 > 1. In Appendix B, we 1 reduces the approximation factor to constant. In the
4 Fully Justified Representation
Peters et al. [12] introduced fully justified representation (FJR) as relaxation of the core in the context approval-based committee selection. The following definition is its adaptation to non-centroid clustering. Informally, for deviating coalition S, the core demands that the loss (,) of each member i after deviation be lower than her own loss before deviation, i.., E(C(()).. FJR demands that it be lower than the mánimumn loss of any member before deviation, ie., minjee (C(())
Definition 2 (a-Fully Justified Representation (a-FJR)). For a 3 1, a k-clustoring C (CI...., Cx) satisfies a-fully justified representation (a-FJR) if there is no group of agents C N with |S| > 2/4 such that a a (5)) < minjes (x(()) for each E S, ie.,, a maxies (S) < minjes ((C())). We refer to 1-FJR simply as FJR.
We easily see that a-FJR is a relaxation of a-core. Proposition 1. For a > 1, a-core implies o-FJR for arbilrary loss funclions.
Proof. Suppose that a clustering C in the a-core. Thus, for every S C N with |S] > n/k, there exists i S for which L(()) (,((i)) > minjes ()(C))), so the clustering is also a-FJR.
4.1 Arbitrary Loss Functions
We prove that an (exactly) FJR clustering is guaranteed to exist, even for arbitrary losses. For this, we need to define the following computational problem.
Definition (MoST COHESIVE CLUSTER). Given set of agents N and a threshold т, the MOST COHESIVE CLUSTER problem asks to find cluster S C N of size at least such that the maximum loss of any i E for S is minimized, i.e. find arg mins maxies (S)).
For > a >-approximate solution S satisfies maxies (.)) & max (s for all S' C N with |S > т, and a >-approximation algorithm returns a X-approximate solution on every instance.
We show that plugging in X-approximation algorithm A to the MOST COHESIVE CLUSTER problem into the yiclds X-JJR clustering. In order to work with arbitrary losses, need to consider
algorithm designed the previous section
i In centroid clustering, additional agents captured later on do not change the loss of the initial [n/k]] agents captured as loss is defined by the distance to the cluster center, which does not change. However, in non-centroid clustering, additional agents can change the loss of the initially captured agents, from zero to positive, causing infinite approximation when these agents deviate.

---

slightly generalized l as imput instead of a metric d, and passes these loss functions to algorithm A.
algorithm, which takes the loss functions
Theorem 4. For arbitrary losses, a and an a-approzimation algorithm A for the MOST COHESIVE CLUSTER problem, BRREDDCCOHSIVECLUSSTEE
is guaranteed to return a Q-FJR clustering. Hence, an (ezactly) FJR clustering is guaranteed to exist.
Proof. Suppose for contradiction that the k-clustering C= (C(C C returned by GREEDY- CohEsIvELLUSTERINGLAA on instance is not a-FJR. Then, there exists a group S S N with |S] 3 "/K such that a maxes (SS) < minges (x(C()). Let i' be the first agent in S that was assigned to cluster during the execution of CREEIDYConISSveCLoSSS ING, by calling A on a subset of agents N'. Nole that S S N'. Then, we have that max ((C(i)) > & (C(())) approximation al for the MOST COHESIVE CLUSTER problem. Hence, GREEDYCO- HESIVECLUSTERINGAA must return an a-FJR clustering.
maxies (S), which contradiets A being a-
Using an exact algorithm A for the MOST COEESIVE CLUSTER problem (egg, the inefficient brute-force algorithm), get that 1-FJR clustering is guaranteed to exist.
4.2 Average and Maximum Loss Functions
Lel A" be exact algorithm for the MOST COHESIVE CLUSTER problem for the average (resp., maximum) loss. First, we notice that we cannot expect it to run in polynomial time, even for these structured loss functions. This is because it can be used detect whether given undirected graph admits a clique of at least a given size," which is an NP-complete problem. Hence,
an inefficient algorithm.
One can casily check that the proof of Theorem 3 extends to show that it achieves not only 1-FJR (Theorem 4), but also in the O(n/k)-core (resp., 2-core) for the average (resp., maximum) loss. For the core, GREEDYCAPTURE is an obvious improvement as it achicves the same approximation ratio but in polynomial time. For FJR, we show that GREEDYCAPTURE still achieves a constant approximation in polynomial time. We prove this by showing that the AGENTBAAA algorithm used by GREEDYCAPTURE achieves the desired approximation to the MOST COHESIVE CLUSTER problem, and utilizing Theorem 4.
Lemma 1. For the average (resp., marimum) loss, SMAlLeST AGENTBAlL a 4- approcimation (resp., 2-approzimation) algorithm for the MOST COHESIVE CLUSTER problem, and this is tight.
Plugging in Lemma 1 into Theorem 4, we get the following.
Corollary 1. The (efficient) GREEDYCAPTURE algorithm is guaranteed to return a clustering that is 4-FJR (resp., 2-FJR) for the averoge (resp., mazimum) loss.
Determining the best FJR approximation achievable in polynomial time remains an open question.
Open Question 3: For the average (or maximum) loss, what is the smallest for which an a-FJR clustering can be computod in polynomial time, assuming P + NP?
Also, while Theorem 4 shows that exact FJR is achievable for the average and maximum losses, a single clustering may not achieve FJR for both losses simultancously (the algorithm used in Theorem 4 depends on the loss function). In contrast, GREEdYCAPTURE does not depend on whether we are using the average or the maximum loss. Thus, the clustering it produces is simultaneously 4-FJR for the average loss and 2-FJR for the maximun loss (Corollary 1); this is novel even as an existential result, ignoring the fact that can be achieved using an efficient algorithm GREEDYCAPTURE We do not know how much this existential result can be improved upon.
"To detect whether an undirected graph G (V, E) has a clique of size at least t, we run .A' with each node being an agent, the distance between two agents being if they are neighbors and 2 otherwise, and A- = n/t. A clique of size at least t exists in G if and only if a cluster S exists with |S| 3 n/k = and maxies (SS)

---

Open Question 4: What the smallest a such that there always exists clustering that is simultaneously o-FJR for both the average loss and the maximum loss?
4.3 Auditing FJR
Next, we turn to the question of auditing the FJR approximation of a given clustering. In particular, the goal is to find the maximum FJR violation of a clustering C, iee, the largest for which there exists group of agents of size at least n/k such that, if they were to form their own cluster, the loss of each of them would be lower, by a factor of at least a, than the minimum loss of any of them under clustering C. Because guarantees such the and FJR are defined with exponentially many constraints, it is difficult to determine the exact approximation ratio achieved by given solution efficiently, which is why prior work has not studied auditing for proportional fairness guarantees. Nonetheless, we show that the same idcas that we used find an (approximately) FJR clustering can also be used to (approximately) audit the FJR approximation of any given clustering.
Definition 4 (A-Approxinate FJR Auditing). We say that algorithm A is X-approximate FJR auditing algorithm if, given any clustering C, it returns 0 such that the exact FJR approximation of C (i.e., the smallest such that C a-FJR) is in [0, (. 0].
ALGORITHM 3: AUDITFJR(A)
Input: Set of agents N, metric d, number of clusters k, clustering C
Output: Estimate 0 of the FJR approximation of C // Remaining agents, current FJR apx estimate
N" <- N: < 0:
while [N > n/k do
S - A(N' dd,%%))
// Find cohesive group $ // Update using the FJR violation due to // Remove the agent with the smallest current loss
0 max minses ((CO)) );
maxies (()
i* - arg min (C(i)) N' N' (T)
end return 0:
We design another parametric algorithm, AUDITFJR(A), presented as Algorithm 3, which iteratively calls A to find a 'cohesive' cluster S, similarly to GREIDYCOHESVECLUSTEENN But while CEREDDYCOOISSVVRCASSVRRRRR sideration, AUDITFJR removes only the agent in S with the smallest loss under the given clustering C from further consideration. Thus, instead of finding up & cohesive clusters, finds up to n cohesive clusters. It returns the maximum FJR violation of C demonstrated by any of these n possible deviating coalitions (recall that the exact FJR approximation C' is the maximum FJR violation across all the exponentially many possible deviating coalitions of size at least [*/x]).
removes all the agents in from further con-
We show that if AA was A-approximation algorithm for the MOST COHESIVE CLUSTER problem, then the resulting algorithm is X-approximate FJR auditing algorithm. In particular, if we were to solve the MOST COHESIVE CLUSTER problem exactly in each iteration (which would be inefficient), the maximum FJR violation across those n cohesive clusters found would indeed be the maximum FJR violation across all the exponentially many deviating coalitions, an apriori nontrivial insight. Fortunately, we can at least plug in the SMALLEST AGENT ALL algorithm, which we know achieves constant approximation to the MOST COHESIVE CLUSTER problem (Lemma 1).
Theorem 5. For X > 1, if A is a X-approzimation algorithm to the MOST CohE- SIVE CLUSTER problem, then AUDITFJR(A) is a X-approzimate. FJR auditing algo- rilhm. Given Lemana 1, il follows that for the average (resp., marimum) loss, AUDIT- AAGTSSAAAASTTAETTTBTAAAA is an efficient 4-approrimatee (resp., 2-approcimate) FJR auditing algorithm.
8

---

(a) Core violation, average loss
(b) FJR violation, average loss
4.0
Greedy Capture
3.5
Greedy Capture
kmeans++
means++
kmeddoid
3.0-
k-medoids
3.0
2.5-
2.5
2.0
2.0
15-
1.5
1.0
1.0-
10
10
20
(c) Core violation, maximum loss(d) FJR violation, maximum loss (e) Avg within-cluster distance
Greedy Capture
Greedy Capture
k-means++
W
k-meany++ +
W
100
Core Volaton
k-medolds
PiR violorton
k-medolds
80
60
Greedy Capture
2-
k-means++
k-medoids
Figure 1: Census Income Dataset
Unfortumately, the technique from Theorem 5 does not extend to auditing the core. This because requires upper bounding minigs &IC()) (instead of minses (x(C(()) maxtes (s( ); this can be upper bounded by (C(())) but we cannot lower bound 4,- (5). The fact that A approximates (.))
(s(
the MOST COHESIVE CLUSTER problem only lets us lower bound maxies (S). We leave it
as an open question whether an efficient, constant-appree approxiaapp core auditing algorithm can be devised.
Open Question 5: Does there exist polynomial-time, a-approximate core auditing algorithm for some constant a?
For the maximum loss, we can show that our 2-approximate FJR auditing algorithm is the best can hope for in polynomial time; the proof is in Appendix A. The case of average loss remains open.
Theorem 6. Assuming P + NP, there does not exist a polyoomial time X-opprozimate FJR auditing algorithm for the marimam loss, for any X < 2.
Experiments
In this section, empirically compare GREEDYCAPTURE with the popular clustering algorithms k-means++ and k-medoids on real data. Our focus is on the tradeoff bet ween fairness (measured by the and FJR) and accuracy (measured by traditional clustering objectives) they achieve.
Datasets. We consider three different datasets from the UCI Machine Learning Reposi- tory [19], namely Census Income, Diabetes, and Iris. For the first two datasets, each data point corresponds to a human being, and it is reasonable to assume that each individual prefers to be clustered along with other similar individuals. We also considor the third datasct for an interesting comparison with the empirical work of Chen et al. [1], who compared the same algorithms but for centroid clustering.
The Census Income dataset contains demographic and economic characteristics of individuals, which are used to predict whether an individual's anmual income exceeds threshold. For our experiments, keep all the numerical features (ie. age, education -nmm capital-gain,

---

capital-loss, and weers along with sex, encoded as binary values. There are in total 32,561 data points, each with sample weight attribute (fnlwgt). The Diabetes dataset contains numerical features, such as age and blood pressure, for about 768 diabetes patients. The Tris dataset consists of 150 records of numerical features related to the petal dimensions of different types of iris flowers.
Measures. For fairness, we measure the true FJR and core approximations of each algorithm with respect to both the average and maximum losses. For accuracy, we use three traditional clustering objectives: the average within-cluster distance ΣiE(A) |cll EEjec, d(i.j), termed cost by Ahmadi et al. [14), as well as the popular h-means and k-medoids objectives.
1.
Experimental setup. We implement the standard k-means++ and k-medoids clustering algorithms from the Scikit-learn project", averaging the values for each measure over 20 runs, as their outcomes depend random initializations. The computation of GREEDYCAPTURE neither uses randomization nor depends on the loss function with respect to which the core or FJR approximation is measured. Since calculating core and FJR approximations requires considerable time, for both the Census Income and Diabetes datasets, we sample 100 data points and plot the means and standard deviations over 40 runs. For the former, we conduct weighted sampling according to the fnlugt feature.
Results. In Figure 1, we see the results for the Census Income dataset; the results for k- means and k-medoids objectives for this dataset, along with results for the other two datasets, are relegated to Appendix D due to being qualitatively similar to the results presented here. According to all four fairness metrics, GREEdYCAPTURE is significantly fairer than both k-means++ and k-medoids, consistently across different values of k. Notably, the FJR approximation of GREEdYCAPTURE empirically stays very close to 1 in all cases, in contrast to the higher wosst-case bounds (Corollary 1). Remarkably, the significant fairness advantage of GreEdyCAPTURE within-cluster distance, k-means, and k-medoids) achieved by than twice those of k-means+ and k-medoids, across all values of and all three datasets!
comes at a modest cost in accuracy: all three objective values (average
CAPTURE are less
Lastly, our results are in contrast to the experiments of Chen et al. [1] for centroid clustering, where GreedYCAptUrE provides a worse core approximation than k-means+++ on Iris and Diabetes datasets; demonstrated in Appendix D, this is not the case in non-centroid clustering.
Discussion
We have initiated the study of proportional fairness in non-centroid clustering. Throughout the paper, we highlight several intriguing open questions. Probably the most important of these are whether can achieve better approximation than (n//k) of the core for the average loss, and whether the core is always non-empty for the maximum loss. In an effort to answer the latter question, in Appendix C.1 show that the core is always non-empty for the maximum loss when the metric space I-dimensional (i.e., a line). This contrasts with the average loss, for which the core remains empty even the line (see Appendix C.2).
In our work, we have shown that there are remarkable differences between centroid and non- centroid clustering settings. One can consider a more general model, where the loss of agent depends on both her cluster center and the other agents her cluster. Investigating what proportional fairness guarantees can be achieved in this case is exciting direction. Another intriguing question is whether we can choose the number of clusters à intrinsically; this seems challenging proportional fairness guarantees seem to depend fixing & in advance to define which coalitions can deviate. Lastly, while classical algorithms such as k-means and k-centers are incompatible with the core and FJR in the worst case (see Appendix E), it is interesting to explore conditions under which they may be more compatible, and whether fair clustcring can be computed efficiently in such cases.
10

---

Acknowledgements
Caragiannis was partially supported by the Independent. Research Fund Denmark (DFF) under grant 2032-00185B. Shah was partially supported by an NSERC Discovery grant.
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 Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In Proceedings of the 47th Internalional Colloquiam on Aulomala, Languages, and Programming (ICALP), pages 85:1 85:16, 2020.
3] Felix Sattler, Klaus- Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints. IEEE Transactions on Neural Nelworks and Learning Systems, 32(8):3710 3722, 2020.
[4] Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang, Bo Li, and Ruta Mehta. Fairness in federated learning via core-stability. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 5738 5750, 2022.
5 Bhaskar Ray Chaudhury, Aniket Murhekar, Zhuowen Yuan, Bo Li, Ruta Mehta, and Ariel D Procaccia. Fair federated learning via the proportional veto core. Tn Proceedings of the 41st International Conference on Machine Learning (ICML), 2024. Forthcoming.
6 R Janani and S Vijayarani. Text document clustering using spectral clustering algorithm with particle swarm optimization. Expert Systems with Applications, 134:192 200, 2019.
[7] Hong Huang, Fanzhi Meng, Shaohua Zhou, Feng Jiang, and Gunasckaran Manogaran. Brain image segmentation based on fem clustering algorithm and rough set. IEEE Access, 7:12386 12396, 2019.
[8] Hsuan- Wei Lee, Nishant Malik, Feng Shi, and Peter J Mucha. Social clustering in cpidemic spread coevolving networks. Physical Review E, 99(6):062301, 2019.
19] Leon Kellerhals and Jannik Peters. Proportional fairness in clustering: A social choice perspective. arXiv:2310.18162, 2023.
[10] Haris Aziz, Barton E Lee, Sean Morota Clu, and Jeremy Vollen. Proportionally representative clustering. arXiv:2304.13917, 2023.
[11] Donald Bruce Gillies. Some theorems n-person games. Princeton University, 1953.
[12] Dominik Peters, Grzegorz Pierczyúski, and Piotr Skowron. Proportional participatory budgeting with additive utilities. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 12726-12733 2021.
[13] Anshuman Chhabra, Karina Masalkovaité, and Prasant Mohapatra. An overview of fairness in clustering. IEEE Access, 9:130698 130720, 2021.
[14] Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Matthäus Kleindessner, Jamie Morgen- stern, Pattara Sukprascrt, and Ali Vakilian. Individual preference stability for clustering. Proceedings of the 23rd International Conference on Machine Learning (ICML), pages 197 246, 2022.
[15] Haris Aziz and Rahul Savani. Hedonic games. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, pages 356 376, Cambridge University Press, 2016.
[16] Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. Fractional hedonic games. ACM Transactions on Economics and Compulation, 7(2):6:1-6:2 2019.
11

---

[17] Hal R Varian. Equity, envy and efficiency. Journal of Economic Theory, 9:63-91, 1974.
[18] Vincent Conitzer, Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan. Group fairness for the allocation of indivisible goods. In Proceedings of the 33rd AAAI Conference on Arlificial Intellignnce (AAAI), pages 1853 1860, 2019.
[19] D. Dua and C. Graff. UCI machine learning repository, 2017. URL http://archhie. ics. edummm.
12

---

Appendix
A Missing Proofs
A.1 Proof of Theorem 1
Theorem 1. For arbitrary losses, there evists instance in which a-core clustering crists for any finite a.
Proof. Consider an instance with a set of n = 4 agents {0, 1,233 and & == 2. Note that any group of at least 2 agents deserves to form cluster. For E {0, 1,2,, the loss function of agent i is given by
x
i = (0. 1,2) or 3 S
4(S)
if | 2 and i i+1 1 mod $ S,
if S {i,
mod 3).
In words, agent i E {0, 1, 1, only wants to be in a cluster of size 2 that does not include the undesirable agent 3; any other cluster has infinite loss. In an ideal such cluster (loss 0), agent 0 prefers to be with agent 1, agent prefers to be with agent 2, and agent 2 prefers to be with agent 0. The remaining clusters size have loss 1.
Consider any clustoring C = (C1, C2). Without loss of generality, say 3 E Ct. We take three cases.
1. If |C1|=1, then C2 {0, 1. Then, group S containing any two agents from C2 can deviate, and each i S would improve from infinite loss finite loss.
2. If C1 > 3, then a group S containing two agents from C1 other than agent can deviate, and each i E S would improve from infinite loss to finite loss.
3. Supposc |C1] = 2 and let (i
{t}. Then, the group $ = {i, (i - 1) mod 4} can deviate: agent i would improve from infinite loss finitc loss, and agent (i - 1) mod would improve from loss of 1 to loss of 0.
In each case, every deviating agent improves by an infinite factor, yielding the desired result.
A.2 Proof of Theorem 2
Theorem 2. For the average loss, there erists an instance in which no a-core clustering crists for a < L+v3 2
R 1.366.
Proof. Let construct an instance with even number A: > 2 of clusters. Let 1+v3 We set the number of agents to be multiple of k such that 2 k max { 1 + 4,44).. Our construction has k/2+1 areas, each consisting of a few locations (points), with several agents placed on each them. particular, area has a single location Mo with k/2 agents. For i 1,,,...., k/2, area i consists of location Mt hosting single agent, a left location Ly and right location R, each hosting //k- - agents. We use L,, R, and M, to denote both the corresponding points well the set of agents located in them. For i a. from point M,. distance between points L, and R, while both points are at distance The distance between any two points in different areas is infinite.
1,2, .... k/2, the
Zkn
Consider a k-clustering C of the agents. We call bad any cluster of that contains agents from different areas; notice that all points in such a cluster have infinite cost. A good cluster has all its points in the same area and, hence, the agents contained Notice that C has al most. l: - good clusters that contain points from areas 1, 2, ..., k/2. mong these areas, let be the one with the minimum number of good clusters. Thus, area t either has all its agents in bad clusters contains one good cluster that includes some of
it have finite cost.
13

---

We distinguish between three cases. The first one is when the good cluster does not contain the agent in My. Among R& and Lt, assume that Lt has at most as many agents in the good cluster as Rg (the other subcase is symmetric). Then, the cost of all agents of Le in the good cluster is at least 1/2. The deviating coalition consisting of all agents in Le and the agent of Mr (i.c., "/k agents in total) improves the cost of all agents by a multiplicative factor at least a. Indeed, the cost of the agent in Mt improves from infinite to finite while the cost of any agent in Le improves from at least 1/2 to 1, since any such agent has distance a to 2n its agents. If at least "//e of its agents belong to bad clusters in C, deviating coalition of them would improve their cost from infinite to finite. So, in the following, we assume that clustering C contains exactly one good cluster with at least n/4 agents from area t.
2ha
the agent in M,, and is colocated with the other agents in the deviating coalition.
The second case is when the good cluster contains all agents in area In this case, the cost of the agents Le and Rg is
- 4a +2 - (the second inequality follows by the definition of n). Then, each agent in the deviating coalition containing ž agents from Le and
2-/4-1 26g +"/41 > 4a + 2(2%/=11 3 1
a agents from Rg improves their cost to 1/2, i.e, by a factor of at least 2
2a -
The third case is when the good cluster contains the agent in Mt but does not contain some agent i from L, or Rr. We will assumee that agent belongs to Le (the other subcase is symmetric). Notice that the cost of the agents in Rs is at least 2n/42 Ia To see why, notice that the claim is trivial for those agents of Rs that belong to bad clusters while cach of the agents of R₂ in the good cluster is at distance Tee n to the agent in M, and there are at most 2n/4 2 in the cluster. The deviating coalition of all agents in Re together with decreases their cost to just k/n, i.e., by a factor of at least The R a (the inequality follows by the definition of n), while the cost of agent i improves from infinite to finile.
So, there is always a deviating coalition of at least 7/k agents with each of them improving their cost by multiplicative factor of min aa, + 2a - E] a, as desired. The last equality follows by the definition of a and E.
A.3 Proof of Theorem 3
Theorem 3. For the average (resp., marimum) loss, the GREEDYCAPTURE algoritim is guaranteed to return a clustering in the (2- [[/Ak] - 3o-e (resp., 2-core) in ((kn) time complerity, and these bounds are (almost) tight.
Proof. Let = (CI.... C&} be the k-clustering returned by GREEDYCAPTURE. Let SCN be any set of at least n/s agents such that their average loss satisfies
(c(C(i) (2 [M/]] 3) (S))
(1)
for every E S.
Let 1" be the agent that was the first among the agents in S that was included in some cluster by the algorithm. Consider the time step before this happens and let i C(i') be the agent that had the minimum distance R from the [*/ agent in C(i*) among all agents that had not been included to clusters by the algorithm before. Then,
4, (c(")))) C(T)
Σ
d(i",
(EC(!)
ddi",
(d(i",z) d((,))) (EO
Σ
C(+*)
3 [n/h]]
2
R.
(2)
The first inequality follows by applying the triangle inequality. The second inequality follows since C(ir) has [n/e]] agents and, thus, the RHS has 2[m//]] - 3 terms representing distances of agents in C(i") from agent i', each bounded by R.
14

---

A
B
C
D
E
F
-00
1
2
Figure 2: The instance used to show the lower bounds in Theorem 3 and Lemma 1.
Now, recall that, at the time step the algorithm includes cluster C(i*) in the clustering, none among the (at least [*/]] agents of have been included any clusters. Then, S contains at most [w/k]] - agents located at distance less than R from agent i"; if this were not the case, the algorithm would have included agent i' together with [n/k]] other agents of S in a cluster instead of the agents in C(i"). Thus, S contains at least |S| - [*/x]] + agents at distance at least R from agent. i". Thus,
R. The second inequality follows since |S| > [n/A]] Now, Equation (2) and Equation (3) yield 4-- (C(()) & (2. 12 3) (S), contradicting Equation (1)-
(-(())
1
Σ d(i",)) EE
[S| [u/k]] +1
R
1
(3)
|S]
[T/A]
Now, assume that there exists set S S of at least "/4 agents such that their maximum loss satisfies
((C(i)) > 2 2,S).
for every E S. Again, let 1" be the agent that was the first among the agents in S that was included in some cluster by the algorithm. Consider the time step before this happens and let i' e C(i*) be the agent that had the minimum distance R from the [*/+]-tt 1 agent in C(i") among all agents that had not been included to clusters by the algorithm before. Then, the maximum loss of agent i* for cluster C(i*) is
4. (C(it)) max d(i", i)) & max iEC(i*)
d(', (d(i",')+d(( 2.
iEC(i*)
The first inequality follows by applying the triangle inequality and the second since all agents in C(i)) are at distance at most R from agent i. We also have
& (S) max d(i", ,0) > R. :ES
otherwise, the algorithm would include a subset of [m/k]] agents from set in the clustering instead of C(i*). Together, Equation (5) and Equation (6) contradict Equation (4). This completes the proof of the upper bounds.
We now show that the analysis is tight for both the average and the maximum loss functions using the instance depicted in Figure with one agent at locations A, D, and E, two agents at location B, n1/2 -3 3 agents at location C, and n/2 2 agents at location F. Suppose that = 2. It is easy to see that GREEDYCAPTURE returns a 2-clustering with the agents located at points A, B, and C in one cluster and the agents located at points D, E, and F in another. Notice that the agents at locations and C. have infinite loss under both loss functions, while the agent located at position D has maximum loss 2(1 E) and average loss (n 3)(1=s) Now, consider the deviating coalition of the n/2 agents at locations B, C, n/2
and D. The agents at B and C' improve their loss from infinite to finite, while the agent located at C' improves her maximum loss to 1 + and her average loss to 2+(n/2-1); 1)s for n/2
multiplicative improvements approaching and n/2 3/2 as E approaching
Since GREEDYCAPTURE calls SMALLESTAGENTBALLL at most times and SMALLESTA- GENTBALL does at most n iterations in each call, we casily that the time complexity of GREEDYCAPTURE is (kk)..
A.4 Proof of Lemma 1
Lemma 1. For the average (resp., marimuum) loss, approcimation (resp., 2-approrimation) algorithm for the MOST COHESIVE CLUSTER problem, and this is tight.
is 4-
15

---

Proof. For some N Ç N, let S be the most cohesive cluster and let S' + S be the cluster that SMALLESTAGENTIE AGENTBALL returns. Suppose that S' consists by the [*/a] closest agents in N" to some agent 1" and the distance of i" to her [n/4]-th closest agent in N' is equal to R. From the triangle inequality, we get that every two agents in S' have distance at most 2R, and therefore, under both loss functions, we get that (. 2. R.
We show that there are two individuals in S, i and i2, such that the d(i,, > R. Indeed if for each i, E S, d(i, 2") < R, then 8* would not be the agent in N' with the smallest distance to her [*/4]-th closest agent in N' and SMALLESAAGETBALL would not return S. From this fact, we immediately get a 2-approximation for the maximum loss, since m > R.
Now, for the average cost, note that
|S| d(i, = Σ iES
E(
& Σ iES
+ d(1,
From this get, that either Lies d(ii, i) > |S| d(i i2)/2 2 E Lies d(i2.)) i) > (51-d((1: 12) Therefore, either Lú (S) 2 d(i1, /2) > R/2 or lig (S) 2 d(i,, 22) > R/2. This means that mas:esf((5) > R/2 and the lemma follows.
Next, we show that there are instances for which SMALLESTAGENTLE these bounds. Consider the instance showing in Figure/ 2, For kt = 2, suppose there are 1 point at position A, n/4 points at position B, n/4-1 1 at position C, 1 point at position D, I point at position E position D, and n/2 2 points at position F. It is not hard to see that SMALLEST reduce the average loss by a factor equal to and the maximum loss by factor equal as n grows and goes to 0.
achieves exactly
will return the cluster $ = ED F). But S' = {B, C, can
A.5 Proof of Theorem 5
Theorem 5. For X > L, if A is a X-approzimation algorithm to the MOST COHE- SIVE CLUSTER problem, then AUDITFJR(A)) is X-approzimate FJR anditing algo- rithm. Given Lemma 1, it follows that for the average (resp., mazimum) loss, AUDIT- (ARASAALESTAGETTBAL. is an efficient 4-opprozimate (resp., 2-approzimate) FJR audiling algorithm.
Proof. Suppose A is a >-approximation algorithm for the MOST COHESIVE CLUSTER problem. Consider any clustering C on which AUDITFJR(A) returns O. Let p minies (C(()) be the exact FJR approximation of C. First, it is easy (a maxies (8)
to check that p > f because is computed by taking the maximum of the same expression as P is, but over only some (instcad of all possible) S. Hence, it remains to prove that p & X A.
Consider any group S N with |S] > n/s. Let i" be the first agent in that was removed by AUDrTFJRR JR, say when A returned group S containing it; there must be one such agent because |S] > n/2 and when AUDIrFJR stops, fewer than n/e agents remain in N'. Now, we have that
minzes ((C(i)) maxies ((())
4. (C(i)) maxis (SS) < (C(()()) X- minies ((((i)) maxies 4(')) O
maxies ((S')
where the second inequality holds because A is X-approximation algorithm for the MOST COHESIVE CLUSTER problem, which implies maxess (s() & X max,es (S); the next equality holds because agent i" was selected for removal when S' was returned, which implies i" E arg min; (c((()); and the final incquality holds because / is updated to be the maximum of all FJR violations witnessed by the algorithm, and violation due to S' is one of them.
Finally, using the approximation ratio bound of AMALLESTAGENTBAA AGENTBALL for the MOST
COHESIVE CLUSTER problem from Lemma 1, we obtain the desired approximate auditing guarantee of AUDITE (R(SMALLESTACCNTTAA))
16

---

A.6 Proof of Theorem 6
Theorem 6. Assuming P + NP, there does not exist a polmnomial-time X-approzimate FJR auditing algorithm for the marimam loss, for any À < 2.
Proof. We show that such an algorithm can be used to solve the CLIQUE problem, which asks whether a given undirected graph G = EV admits a clique of size at least t. The problem remains hard with & > 3, so we can assume this without loss of generality. Given (G,t), we first modify G = EV into G' EV) as follows. To cach v E V, we attach t-2 new (dummy) nodes, and to one of those dummy nodes, we attach yet another dummy node. In lotal, for each v E V, are adding - dummy nodes, so the final number of nodes |V
Next, we create an instance of non-centroid clustering with n = |V| agents, one for each E V. The distance d(u, v) set as the length of the shortest path between and v. Set k= --
Consider clustering C' in which each real node e E V is put into a separate cluster, along with the - dummy nodes created for it. Note that (C(C)) = for cach real node e E V (due to the dummy node attached to a dummy node attached to v) and (.(C(v)) (2.3) for each dummy node V E V \ V. Let us now consider possible deviating coalitions S.
If dummy node is included in S, then in order for an FJR violation, its maximum loss would have to be strictly reduced. Tf (C(v)) = 2, then we must have (S) 1, but no dummy node has at least > 3 nodes within a distance of 1. If (o((()) = 3, then in order to find at least nodes within a distance of at most 2 (and the set not be identical to one of the clusters), S must include at least one real node v' that is not associated with the dummy node v. However, in this case, la (S) > whereas e. (C(v") = 2, so no FJR violation is possible.
The only remaining case is when S consists entirely of real nodes. Since (C(v)) for every real node v E V, an FJR violation exists if an only if max.es (s))) 1, which happens and only if S is a clique of real nodes size at least
Thus, we have established that the FJR approximation of C is if there exists a clique of size at least in G, and otherwise. Since >-approximate auditing algorithm with X >< can distinguish between these two possibilities, it can be used to solve the CLIQUE problem. O
B Bicriteria Approximation of the Core
Here, consider a general definition of the core.
Definition 5 ((a, o)-Coe). For a 2 1, a k-clustering C= (a,, -)-ror if there is no group of agents S N with |S| 5. n// such that a (.(S) < L(C(i) for all E S.
is said to be in the
Theorem GREEDYCAPTURE relurns a clustering solution in the (8, ) for any 8>1.
Proof. Let C= (CI....Ck C be a solution that GREEDYCAPTURE returns. Suppose for contradiction that there exists S N with |S] > 8 8-nk such that
28
eiE S, 4(C(i) > 5-1 L(S)).
Let i" be the agent that was the first among the agents S that was included in some cluster by the algorithm. Consider the time step before this happens and let i' E C(²*) be the agent that had the minimum distance R from the [*/k]-th agent in C(i*) among all agents that had not been included to clusters by the algorithm before. With sinilar arguments as in the proof of Theorem 3, we conclude that
3
l- (c((C(t)) < 2
R < 2. R.
[m/k]/
17

---

Label the agents from 1 to n', starting with the leftmost agent and moving to the Again, with very similar arguments in the proof of Theorem 3, we can conclude that that contains least
|.|| - [*/k]] agents distance at least from agent i* Thus,
|S| [m/k]] +1
|
8 R
4.- (S)
d(i
R
R.
S
[S]
8
where the second inequality follows since |S| > 8 n/k and the theorem follows.
C
Line
C.1
Non- Non-Emptie Con-Emmtiness of the Core for Maximum Loss
ALGORITHM 4: SMALLESTDIAMETER
Input: N' C N, metric d, k L
Output: S
if IN' < then
S+;;;
else
right;
dmin t d(1, n');
i' s*11 1;
for ==1 to n' - do
if d(i,i i < dman then
dmin t d(i, i i 1); 8+ i;
end
cnd
end
S t ( + +}:
Theorem 8. For the marimum loss in the line, GREEDY GREEDY ConnSSvVCCLSTEERNN (SMALL- ESTDIAMETER) returns solution in the core in O(k) time complexity.
Proof. Let C= (CI,..., be the solution that the algorithm returns. Suppose for contradiction that there exists a group N, with [ > "/k such that ((((i)) 4(S) for all i S. We denote the leftmost and rightmost agents in S by L and R, respectively. Let be the first agent S that was assigned to some cluster. If we denote with N' the set of agents that have not been disregarded before this happens, this means that S C Nº. We denote the leftmost and rightmost agents in C(i*) by L* and R*, respectively.
Note that i' has incentives to deviate if and only if either d(i', LL) < d(i", R) d(i", R"), since otherwise 4 (S) max(d(i", L), d(r", R)} > le (C(i) = max TT", "(i" R²)). Without loss of generality, assume that d(i", < d(i IT). Given the way that the algorithm operates, included in C(i*) and L is located between L and it, then L is also included in C(r). Denote with H' the [n/s]-th agent to the right of in N'. We notice that the algorithm returns C(i*) instead of S, because d(L", (*) d(L, R²) < d(L, Rt.. But this means that
or
not hard to see that since L and are
(L(((())) (L((())) < d(L',R") < d(L, R) E2(S)
and we reach in contradiction.
Since GREEDY CwnSSIIE calls SMALLESTDIAMETES at most & times and DiAA does most. iterations in each call, we easily see that the time complexity of GREEDYCCRESVVCCISTRRRR (SMALLESTDIAMETER is O(kn).
D
18

---

C.2 Emptiness of the Core for Average Loss
Theorem 9. For and the average loss, there crists an instance in the line where the core is empty.
Proof. Consider the instance with even n > 24, where one agent, denoted by a, located at position O, n/2 -1 agents, denoted by the set S1, are located at position 2, n/2 1 agents, denoted by the sct S2, are located at position 3 and the last agent denoted by b located at position +00.
Let C (C1,C)) C2) be any clustering solution. Without, loss of generality, suppose that Ci contains This means that all the agents that are part of C have loss equal to infinity. Note that if |C2] n/2 1, then C (S, U U2 U {a})) 2 n/2+11 which means that n/k agents from S1 L S2 U {a} could reduce their loss arbitrary much by deviating to their own cluster. Hence, |C2] > n/2. Next, distinguish to two cases:
this case, for each agent in St, we have that ((C(i)) > n-I 2 1/4. Moreover, note that always prefers to be in cluster that consists by agents in S1. Therefore, we have that if a and S1 deviate to their own cluster, then for each i E Si (51 (a]) n/2 1/4, where the last incquality follows from the fact that 8.
Case I: |C2 n S2l e n/4. n/4
Case II: |C2 0 S2l < n/4.
Since [C2 > n n/2, we have that |C2 (C2) > n/4. In this case, for each agent i in S2, we have that (C())
n/4 n-1 1/4.
Now, we distinguish to two further subcases. First, suppose that belongs to C1. Then, the agents in S2 and deviate to their own cluster, we have that for each E S2, 4sS2 U(a)) n/2 1/4, where the last inequality follows from the fact that > 24. If a is assigned to C2, then all the agents in S have incentives to deviate with agent from S2 that assigned to C1.
D More Experimental Results
We conducted our experiments on server with 32 cores 64 threads at 4.2 GHz and 128 GB of RAM.
(a) k-means objective
(b) k-medoids objective
Greedy Capture
400
k-means++
150
k-medoids
k-means
300
k-medoids
100
200
50
Greedy Capture
100
k-means++
k-medoids
5
10
15
20
25
10
15 k
20
25
Figure 3: Remaining figures for the Census Income Dataset
E
Incompatibility of FJR and Core with Classical Objectives
Consider Example 1 from Chen et al. [1]. Classic algorithms such as k-center, k-means++ and k-median would cluster all points at positions and b together. But if the points at
19

---

(a) Core violation, average loss
(b) FJR violation, average loss
Greedy Capture
Greedy Capture
+-means++
k-means++ + k-medoids
Core Violation
k-medoids
FIR Violation
5
10
15
20
25
5
10
15 k
20
25
k
(c)
Core violation, maximum loss
(d) FJR violation, maximunn loss
2.2
Greedy Capture
Greedy Capture
2.0
k-means++
2.0
k-means+
Core Violation
k-medoids
FIR Violation
k-medoids
1.8
1.6
1.4
1.4
1.2
1.2
1.0
1.0
5
10
15
20
25
5
10
15
20
25
k
k
(e) Avg within-cluster distance
(f) k-means objective
(g) A-medoids objective
150
Greedy Capture k-means +
medoldss
100
kmmars
250
Groady
200
200
Greecy
25
kie sro++
kmmedodds
50
k-means+++
mecolds
Figure 4: Diabetes dataset
deviate by forming a cluster, each of them improves from infinite loss to finite loss. Therefore, these algorithms do not provide a finite approximation to the core or FJR.
20

---

(a) Core violation, average loss
(b) FJR violation, average loss
1.8
Greedy Capture
Greedy Capture
k-means++
k-means++
Core Violation
1.6
k-medoids
FIR Violation
k-medoids
1.4
1.2
1.2
1.0
1.0
5
10
15 k
20
25
5
10
15
20
25
k
(c) Core violation, maximum loss
(d) FJR violation, maximum loss
Greedy Capture
Greedy Capture
2.5
k-means++
2.5
k-means++
Core Vielation
k-medoids
FIR Violation
k-medoids
2.0
1.5
1.0
1.0
5
10
15
20
25
5
10
15
20
25
k
k
(e) Avg within-cluster distance
(f) k-means objective
(g) k-medoids objective
250
Greedly Capture
80
2:0
60
l-medoios
100
Gruadl Capture
Gruadl Capture k-mans--4
20
k-menns--
50
kemecoids
Figure 5: Iris dataset
21

---

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:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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.
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 other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
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 in 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 results often depend on implicit assumptions, which should be articulated.
few datasets or with few runs. In general, empirical
The aut hors 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 or images are taken in low lighting. Or a 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 algo- rithms and how they scale with dataset size.
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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honcsty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
22

---

Answer: [Yes]
Justification:
Guidelinos:
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 the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided 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 experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
If the contribution is dalaset 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 varions ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to replicate the model with the same dataset, or provide access to the model, In general. releasing code and data is 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 a large language model), releasing of model checkpoint, other means that are appropriate to the rescarch performed.
either make possible for others
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, 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 to have some path to reproducing or verifying the results.
23

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sulficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (attps://nips.
for more details.
While we encourage the release of code and data, understand that this might not 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 submis- sion guidelines for more details.
The authors should provide instructions on data access and preparation, in- cluding how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they 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 supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Detall
Does the paper specify all the training and test details (e.g,, data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
J Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
24

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test tten/ split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of crrors 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 are out of range (e.g. negative error rates).
If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the correspouding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, docs the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
Guidelincs:
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 well as 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 make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics /tteur//neurrps
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in 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:
Guidelines:
The answer NA means that there is societal impact of the work performed.
25

---

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 socictal impacts include potential malicious or unintended uses (o.g., disinformation, generating fake profiles, surveillance, fairness consid- crations (o.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational rescarch and not tied to particular applications, let alone deployments. However, if there direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for finmmtooot 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 lechnology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to 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 data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards by requiring that users adhere to usage guidelines or restrictions to access the model implementing safety filters.
allow for controlled use of the model, for example
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 is 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
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, proporly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing asscts.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
26

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithcods 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. this information not available online, the authors are encouraged reach out to the asset's 8 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:
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/ /ctd//moee/ee model as part of their submissions via structared templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was 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 filc.
14. Crowdsourcing and Rescarch 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 as details about compensation (if any)?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution 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 Rescarch 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
27

---

Depending on 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.
We rocognize that the procedurcs for this may vary significantly between insti- tutions and locations, and we expoct authors to adhere to 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.
28


Reviews:
[{"review_id": "Oo6fk7XYAi", "reviewer": "Reviewer_YYLK", "summary": "This paper considers the proportional fairness in non-centroid clustering, where the loss of an agent is a function of the other agents in its cluster. It is the first work to study the proportional fairness guarantee in non-centroid clustering. It is interesting to consider the non-centroid clustering under the core and its relaxation. For the non-centroid clustering, authors study three different loss functions including arbitrary loss, average loss and maximum loss, respectively. For arbitrary loss, authors prove that no finite approximation of the core can be guaranteed. For the average and maximum loss, authors present a greedy capture algorithm that achieve $O(n/k)$-core and 2-core in $O(nk)$ time, respectively. The greedy capture algorithm is an adaptation of the algorithm developed for the centroid clustering under proportional fairness constraints. Additionally, for the fully justified representation (FJR), which is the relaxation of the core, authors provide constant approximations returned by the greedy capture algorithm. Moreover, authors turn to auditing the FJR approximation of a given clustering, and show that the used same technique achieves a constant approximation of FJR, which can be used to estimate the FJR approximation of any given clustering, up to a constant factor. Experiments on real data show that traditional clustering algorithms are highly unfair, whereas the greedy capture algorithm is considerably fairer and incurs only a modest loss in common clustering objectives.", "questions": "Q1: As the authors mentioned, in other applications of clustering, i.e., federated learning, there are no “cluster centers”. What is the practical background in studying the non-centroid clustering of fairness?\n\nQ2: The authors give the first work studying the proportional fairness in non-centroid clustering. Is it fair to compare the proposed method with centroid-based methods, i.e., $k$-means++, in experiments? Therefore, the experimental result shown in Figure 1 is normal, in which the greedy capture method is significantly better than both $k$-means++ and k-medoids for the Census Income dataset.\n\nQ3: As the authors mentioned, the proposed algorithm of this paper is an adaptation of the algorithm developed for the centroid clustering in [1]. The technique used in this paper is similar to that of [1], with a slight difference in stopping a ball as soon as it captures $n/k$ agents. What are the technical novelties of this paper? Please highlight it.\n\nQ4: Why not compare the running time of algorithms in experiments? Why the experiments are conducted on smaller datasets? Is it possible to test on larger datasets, e.g., millions or even hundreds of millions?\n\nQ5: The one of the main results of this paper is an $O(n/k)$-core for the average loss by the proposed greedy capture algorithm. Can the $O(n/k)$-core be improved using other technique?", "limitations": "The broader impacts have been discussed in the last paragraph of the paper and I don’t expect any negative societal impacts for the proposed methods.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.This paper introduces the non-centroid clustering under two proportional fairness criteria, i.e., the core and its relaxation, and provide some approximation algorithms. \n\n2.For the FJR, the approximation results show that while it is a slight relaxation of the core, it is satisfiable even under arbitrary loss functions, whereas the core can be unsatisfiable even under more structured loss functions.", "weaknesses": "1.For the average loss, the $O(n/k)$-core loss returned by the greedy capture algorithm is large, compared with the 2-core of the maximum loss.\n\n2. The practical background of the non-centroid clustering under proportional fairness constraints is unknown. And, it is unfair that in experiments, authors compare the proposed algorithms with $k$-means++ and k-medoids, which cannot obtain solutions satisfying proportional fairness. \n\n3. The running time of algorithm is not compared in experiments, and the datasets have small sizes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and constructive review.\n\n**Regarding Q1 (practical background of fairness in non-centroid clustering)**\n\n* Fairness has been studied in clustered federated learning [1-3], where the idea is to be fair to the agents during the grouping. But fairness has also been studied in federated learning more broadly [4-5], where the idea is still the same: making sure that the model learned is fair to the agents. In our work, the loss of an agent for her group serves as an estimate of the loss of the agent for the model that will be learned by her group. \n* Team formation is another relevant application where fairness has been studied practically [6-7]. \n\n[1] A Fair Federated Learning Framework based on Clustering. J Zhang, A Ye, Z Yao, M Sun. IEEE NaNA, 2022. \n\n[2] Proportional Fair Clustered Federated Learning. M. Nafea, E. Shin, A. Yener. IEEE ISIT, 2022.\n\n[3] A cluster-based solution to achieve fairness in federated learning. F. Zhao, Y. Huang, A.M.V.V. Sai, Y Wu. IEEE ISPA, 2020.\n\n[4] Fairness in federated learning via core-stability. B. R. Chaudhury, L. Li, M. Kang, B. Li, R. Mehta. NeurIPS, 2022.\n\n[5] FairFed: Enabling Group Fairness in Federated Learning. Y.H. Ezzeldin, S. Yan, C. He, E. Ferrara, A.S. Avestimehr. AAAI, 2023. \n\n[6] Partitioning friends fairly. L. Li, E. Micha, A. Nikolov, N. Shah. IJCAI, 2023. \n\n[7] Relaxed Core Stability in Fractional Hedonic Games. A. Fanelli, G. Monaco, L. Moscardelli. IJCAI, 2021. \n\n**Regarding Q2 (comparison to $k$-means++ and $k$-medoids)**\n\nWhile $k$-means++ and $k$-medoids are usually described as centroid clustering algorithms, both can be viewed as non-centroid clustering algorithms as well as they minimize the sum of the pairwise distances and squared pairwise distances of points in the same clusters, respectively. \n\nAlso, the goal of our experiments is not to demonstrate that GreedyCapture is fairer than k-means++ and k-medoids. The latter two are unfair because they're designed for accuracy, not fairness. It is, therefore, unsurprising that GreedyCapture performs better in fairness metrics while k-means++ and k-medoids perform better for accuracy metrics. What is surprising is how little accuracy GreedyCapture has to sacrifice to gain significantly more levels of fairness compared to the other two algorithms.\n\n**Regarding Q3 (technical novelties)**\n\nThe technical novelties of the paper lie along three axes.\n\n1) **Algorithmic:** While you are correct that our GreedyCapture is only slightly different from that in [1], our auditing algorithm AuditFJR (Appendix A.5) is entirely novel. The fact that a technique designed to *design* a fair clustering algorithm can also be used to *audit* the fairness of *any* clustering algorithm is quite surprising to us.\n2) **Upper bounds:** Even for the core approximation guarantee of GreedyCapture, which is studied in [1] for centroid clustering, its analysis for non-centroid clustering (Proof of Theorem 3) is very different. For the centroid case, the center to which each agent is assigned plays a crucial role in the analysis. In our case,  the argument involves the distance of an agent from any other agent in a deviating group $S$ and from any other agent to the clustering that they included under the algorithm (see, for example, lines 473 and 481).  Proof of its FJR satisfaction is also novel. In particular, for the average cost n Lemma 1, we use two individuals in deviating group $S$ that are sufficiently far away from each other to lower bound the cost of at least one of them for S. This is a completely novel argument. \n3) **Lower bounds:** Our lower bounds and their constructions we derive for non-centroid clustering share no similarity to those for centroid clustering in [1].\n\n**Regarding Q4 (running times)**\n\nWe did not include running times because our focus was on the fairness-accuracy tradeoff. That said, in the attached PDF file (see the common response), we include the running times. \n\nRegarding small datasets, all three algorithms are extremely fast and can scale easily to millions of data points. As we mention in line 325, the bottleneck in the experiments is measuring the exact core and FJR violation of these algorithms, which we do using an integer linear program that does not scale. For FJR, we could use the auditing algorithm we discuss in Section 4.3, but for the core, it is quite unclear whether its violation can be measured faster.\n\n**Regarding Q5 (core approximation)**\n\nThis is an extremely intriguing question and one that we spent a lot of time and effort on. Some of us believe that a constant approximation should be possible, and the rest believe that $\\Theta(n/k)$ should be the best possible. We were able to find an $\\Omega(n/k)$ example for every technique we could think of, but no general construction worse than that in Theorem 2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mLnnNNimQk", "reviewer": "Reviewer_UU1a", "summary": "This paper considers the proportional fair clustering for the non-centroid clustering. They consider three types of clustering loss for each agent in a cluster: arbitrary loss, average loss, and maximum loss. The average (maximum) loss is the average (resp. maximum) distance from this agent to other agents in the cluster. \n\nThey first consider the alpha-core for proportional fairness, which requires a clustering such that no group with size at least n/k satisfies every agent in the group has a loss at most the current loss divided by alpha. For arbitrary cost, they show an instance in which there is no alpha core clustering for any finite alpha. For average loss, they show a 1.366 lower bound and provide an O(n/k)-core clustering algorithm. For maximum loss, they show a 2-core clustering algorithm.\n\nThen, they consider a relaxation of the core clustering, fully justified representation (FJR). It only requires the clustering satisfies there is no group with size at least n/k such that every agent in the group has a loss at most the minimum loss in its current cluster divided by alpha. \nThey first show that for arbitrary loss, there exists a 1-FJR clustering. Then, they show an efficient algorithm that finds 4-FJR and 2-FJR for average loss and maximum loss respectively.\nThey also show an efficient 4-approximation and 2-approximation FJR auditing algorithm for average loss and maximum loss.", "questions": "-", "limitations": "Yes, they mentioned the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow.\n2. The paper extends the proportional fairness to non-centroid clustering, which is reasonable and interesting. They provide interesting algorithms that achieve approximation for the core clustering and the FJR clustering. \n3. Their algorithm and analysis can potentially be used for other clustering problems.", "weaknesses": "Minor: \nLine 215: lambda_i(S’) should be l_i(S’).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We will implement your correction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4r54xpYFk2", "reviewer": "Reviewer_pibV", "summary": "This paper studies proportionally fair non-centroid clustering under the fairness criteria core and fully justified representation (FJR). \nBoth notions are well-studied in the context of centroid clustering. However, the authors claim that they are the first to consider them in the non-centroid setting.\n\nThey study the fairness criteria of the core and FJR and approximations to them under different agent-based loss functions\n\t- arbitrary (non-negative) losses\n\t- average loss (average distance of an agent to the other agents in her cluster)\n\t- maximum loss (maximum distance of an agent to the other agents in her cluster)\n\nAn $\\alpha$-approximation to the core (or $\\alpha$-core) is defined as a clustering where no entitled group of agents would want to deviate to a new coalition unless the loss of any agent in the new coalition would be at most an alpha-fraction of the former cost.  \n\nFor the core under arbitrary loss functions, they prove approximation hardness for any constant factor. Even for the case of average loss, they show that there is no constant-factor approximation better than $(1+\\sqrt{3})/2$.\nOn a positive side, they constructively show existence of a clustering in the O(n/k)-core under the average loss function and existence of a clustering in the 2-core under maximum loss. If the metric space is 1-dimensional, they can even prove existence of a clustering in the 1-core under maximum loss.\n\nAn alpha-FJR clustering requires that no eligible group of agents would want to deviate unless every agent in the new coalition would have at most an $\\alpha$-fraction of the loss of the agent with the least initial loss.\n\nThey start by constructively showing existence of FJR clusterings using the slow GreedyCohesiveClustering algorithm. To achieve polynomial-time running times they give the faster GreedyCapture algorithm that, using the SmallestAgentBall subroutine, achieves 4-FJR for average loss and 2-FJR for maximum loss simultaneously.\nFinally, they give an auditing algorithm (AuditFJR) which returns an estimate of the approximation ratio. Plugging in the right subroutine, they get approximation factors of 4 for average loss and 2 for maximum loss. They complement this by showing hardness of approximation beyond a factor of 2 for FJR auditing under maximum loss.\n\nIn a practical evaluation, they compare the efficient GreedyCapture algorithm with k-means++ and k-medoids on real data under the objective values of average within-cluster distance, k-means, and k-medoids. Their experiments reveal that the actual FJR approximation of GreedyCapture is close to 1 in practice. Further, for any of the objective functions under consideration, they find that GreedyCapture yields values at most twice that of k-means++ and k-medoids, respectively.", "questions": "- definition of the $\\lambda$-approximate solution in lines 215-216: should the $\\lambda$ not be on the other side of the inequality? \n- do your results hold for general metric spaces or only for Euclidean metric spaces? Please write this more clearly.\n- what is the notion of dimension here?\n- what is the formal definition of core/FJR violation?", "limitations": "The authors discuss limitations of their work by providing a comprehensive list of open problems.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies an interesting set of problems and the authors claim to be the first to study the fairness criteria core and FJR for non-centroid clustering. From this point of view, it is interesting to see that the methods from centroid-clustering translate nicely to the non-centroid setting.\nThey achieve good approximation factors for FJR. In practice, their deterministic polynomial-time algorithm GreedyCapture even beats these approximation factors (the actual approximation factor stays close to 1 on the considered real data).\nOverall, the paper is nicely written and well understandable.", "weaknesses": "The proposed algorithms are only slight adaptations from an algorithm proposed in [1], which was formulated for centroid clustering. It would be interesting to see whether one can think of novel approaches leveraging properties characteristic for the non-centroid setting.\n\n_Typos_\n- line 53: \"clsutering\"\n- line  207: missing dashes around $S$\n- line 215: right side of the inequality: $l_i$ instead of $\\lambda_i$\n\n_Small Remark_\nI think it would enhance readability if you restate the theorems you prove in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and constructive review. We will correct the typos and use the thm-restate package to restate theorems. And yes, it would indeed be interesting to devise entirely different techniques for non-centroid clustering (although see our response to Reviewer YYLK regarding our technical novelty). Regarding your questions:\n\n> definition of the $\\lambda$-approximate solution in lines 215-216: should the $\\lambda$ not be on the other side of the inequality?\n\nYes, sorry for the typo.\n\n> do your results hold for general metric spaces or only for Euclidean metric spaces? Please write this more clearly.\n\nThe theoretical results hold for general metric spaces as all we use is the triangle inequality. (And the proof of Theorem 4 does not even use the triangle inequality, and thus holds for arbitrary non-metric losses as well!). We will emphasize this clearly.\n\n> what is the notion of dimension here?\n\nAs our results hold for general metric spaces, we have minimized the use of the term \"dimension\" in the paper. In Appendix C, we provide stronger results for the special case of a 1-dimensional Euclidean line metric.\n\n\n> what is the formal definition of core/FJR violation?\n\nThe core (resp., FJR) violation of a clustering $C$ is the smallest $\\alpha$ for which it is in the $\\alpha$-core (resp., $\\alpha$-FJR). In other words, the core (resp., FJR) violation of a clustering $C$  is the smallest $\\alpha$ for which there exists a group of agents of size at least $n/k$ such that, if they form their own cluster, the loss of each of them is lower by a factor of at least $\\alpha$ than their own loss before  deviation (resp.,  than the minimum loss of any of them before  deviation). We will clarify this in our revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m2sJ9s2ava", "reviewer": "Reviewer_X5mR", "summary": "The papers study two notions of proportional fairness in clustering, namely:\n  1) The core as introduced by Chen et al.\n   2) Fully Justified Representation (FJR), which is a relaxation of the above and was introduced by Peters et al.\n\nThe novelty of the paper lies in studying these problems in clustering setting that you are not required to choose clusters centers. In that context the authors start by formally defining the clustering objectives. In the case of the core, they show that arbitrary objectives are not tractable, and that an adaptation of the Chen et al. algorithm can achieve satisfactory approximation results (for the average and maximum objectives). For FJR they show a cute reduction to choose-a-single-cluster problem, and by plugging in this algorithm to the Chen et al. one they once again achieve  strong approximation results. This reduction even produces results for arbitrary objective functions.", "questions": "Some of you non-centroid objectives remind me of Single-Link HC clustering (see Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints for example). Do you think that these algorithms could be easily adapted for proportional fairness?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) Studying notions of fairness in a non-centroid context makes a lot of sense from a practical perspective\n2) The paper is very well-written and easy to follow.\n3) The theoretical results are sound and properly accompanied by an experimental evaluation.", "weaknesses": "The techniques are not particularly novel, but I don't think that's a major weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and constructive review. Please see our response to Reviewer YYLK regarding our technical novelty.\n\n**Regarding Single-Link HC clustering**\n\nThank you for pointing out this family of algorithms. We considered it during our search for a better approximation to the core. Unfortunately, these algorithms fail to detect cohesive groups when we greedily merge groups with minimum spacing. To see this, consider an instance with $k=2$ and an even $n$ with the following distances: \n1) For  $i \\in$ {$1,\\ldots, n/2-1$}, $d(i,i+1)=1$, \n3)  For  $i \\in$ {$n/2+1, \\ldots, n-1$}, $d(n/2,i)=2$\n4)  For $i \\in$ {$1,\\ldots, n-1$}, $d(i,n)=\\infty$ \n\nAll the remaining distances are induced by the triangle inequality.\n\nIt is not hard to see that a single-link type of algorithm will first cluster the first $n/2$ agents together. Then, if we want to maintain some kind of balancessness, either tha last $n/2$ agents will be clustered together, or otherwise the first $n-1$ agents will be clustered together and the last agent that is far away from any other agent will be clustered in its own cluster. In both cases, under the average cost (resp., max cost), all the agents in {$n/2,\\ldots, n-1$} have cost at least equal to $\\Omega((n/k)^2)$ (resp. $\\Omega(n/k)$). \n\nHowever, if they  form their own cluster (they are eligible to do as the size of the group is equal to $n/k$), all of them would have cost $O(1)$ for the new cluster. Thus, the approximation to both FJR and core is $\\Omega((n/k)^2)$ (resp. $\\Omega(n/k)$), which is significantly worst than that of GreedyCapture. \n\nIntuitevely, while this group is very cohesive, a single-link algorithm fails to find it. In constrast, GreedyCapture would be able to find it as the ball centered at $n/2$ would be the first one that would capture sufficiently many agents.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their useful feedback. We attach a PDF file with the running times of the three different algorithms.

Meta-review: This paper studies how to adapt the notion of proportional fairness to the setting of non-centroid clustering, and new nontrivial algorithmic results are given. As also agreed by the reviewers, the new notion is natural and is the major novelty of this paper which may have broader impact. The algorithmic result is nice to have, although it is not technically strong. 

Overall, I recommend an acceptance due to its potential impact in the fair clustering research.
Decision: Accept (poster)