Doubly Constrained Fair Clustering
Authors: John P Dickerson
Seyed A. Esmaeili
Jamie Heather Morgenstern
Claire Jie Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Fairness
Clustering
Approximation Algorithms
TL;DR: Many different fairness notions have been introduced in fair clustering in a disjoint manner. We show the first algorithm that can satisfy two specific fairness constraints simultaneously and prove their incompatibly with other constraints.

Abstract: The remarkable attention which fair clustering has received in the last few years has resulted in a significant number of different notions of fairness. Despite the fact that these notions are well-justified, they are often motivated and studied in a disjoint manner where one fairness desideratum is considered exclusively in isolation from the others. This leaves the understanding of the relations between different fairness notions as an important open problem in fair clustering. In this paper, we take the first step in this direction. Specifically, we consider the two most prominent demographic representation fairness notions in clustering: (1) Group Fairness ($\textbf{GF}$), where the different demographic groups are supposed to have close to population-level representation in each cluster and (2) Diversity in Center Selection ($\textbf{DS}$), where the selected centers are supposed to have close to population-level representation of each group. We show that given a constant approximation algorithm for one constraint ($\textbf{GF}$ or $\textbf{DS}$ only) we can obtain a constant approximation solution that satisfies both constraints simultaneously. Interestingly, we prove that any given solution that satisfies the $\textbf{GF}$ constraint can always be post-processed at a bounded degradation to the clustering cost to additionally satisfy the $\textbf{DS}$ constraint while the same statement is not true given a solution that satisfies $\textbf{DS}$ instead. Furthermore, we show that both $\textbf{GF}$ and $\textbf{DS}$ are incompatible (having an empty feasibility set in the worst case) with a collection of other distance-based fairness notions. Finally, we carry experiments to validate our theoretical findings.

Doubly Constrained Fair Clustering
John Dickerson 1.2 Seyed A. Esmaeili Jamie Morgenstern', and Claire Jie Zhang*
University of Maryland, College Park
2 AArthur
3 Simons Laufer Mathematical Sciences Institute
' *University of Washington
Abstract
The remarkable attention which fair clustering has received in the last few years has resulted in significant number of different notions of fairness. Despite the fact that these notions well-justified, they are often motivated and studied in a disjoint manner where one fairness desideratum is considered exclusively isolation from the others. This leaves the understanding of the relations between different fairness notions as an important open problem fair clustering. In this paper, take the first step in this direction. Specifically, we consider the two most prominent demographic representation fairness notions in clustering: (1) Group Fairness (GF), where the different demographic groups supposed have close to population-level representation in each cluster and (2) Diversity in Center Selection (DS), where the selected centers supposed have close population-level representation of each group. We show that given a constant approximation algorithm for one constraint (GF or DS only) we can obtain a constant approximation solution that satisfies both constraints simultancously. Interestingly, prove that any given solution that satisfies the GF constraint can always be post-processed at a bounded degradation to the clustering cost additionally satisfy the DS constraint while the reverse is not true given a solution that satisfies DS instead. Furthermore, we show that both GF and DS are incompatible (having an empty feasibility set in the worst case) with collection of other distance-basee faimess notions. Finally, we carry experiments to validate our theoretical findings.
1 Introduction
Algorithms' deployment in consequential settings, from their use in selecting interview candidates during hiring, to criminal justice systems for risk assessment, making decisions about where public resources should be allocated [39, 28, 11, 18, 12], have led to an explosion in interest of developing classification and regression algorithms designed to have equitable predictions. More recently, these questions have been extended to unsupervised settings, with the recognition that algorithms which behave as subroutines may have downstream impacts on the ability of system make equitable decisions. For example, while personalized advertising seems to be a much lower-risk application than those mentioned above, the advertisements in question might pertain lending, employment, or housing. For this reason, understanding the impact of unsupervised data pre-processing. including dimensionality reduction and clustering, have been of recent interest, despite the fact that many mathematical operationalizations of fairness do not behave nicely under composition [19].
Clustering is canonical problem in unsupervised learning and arguably the most fundamental. is also among the classical problems in operations research and used heavily in facility location well as customer segmentation. As result, fairness in clustering has also been well-studied
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in recent years [8]. Much of this work has identified that existing clustering algorithms fail to satisfy various notions of fairness, and introduce special-purpose algorithms whose outcomes do conform to these definitions. As in supervised learning, list of mathematical constraints have been introduced as notions of fairness for clustering (more than seven different constraints so far). For example, Chierichetti et al. [17] show algorithms that are guaranteed to produce clustering outputs that prevent the under-representtaiio of demographic group in a given cluster, hence being compliant to the disparate impact doctrine [22]. Brubach et al. [13] show algorithms that bound the probability of assigning two nearby points to different clusters, therefore guaranteeing a measure of community cohesion. Other algorithms for well rell-motivated faimess notions have also been introduced, such as minimizing the maximum clustering cost per population among the groups [24, 1J. assigning distance-tor to-eetttteeeer values that are equitable 41,, and having proportional demographic representation in the chosen cluster centers [32].
These constraints and others may be well-justified in variety of specific application domains, and which are more appropriate will almost certainly depend on the particular application at hand. The dominant approach in the literature has imposed only one constraint in given setting, though some applications of clustering (which are upstream of many possible tasks) might naturally force us to reconcile these different constraints with one another. Ideally, one would desire single clustering of the data which satisfies collection of faimess notions instead of having different clusterings for different fairness notions. similar question was investigated in fair classification [31, 18] where was shown that unless the given classification instance satisfies restrictive conditions, the two desired fairness objectives of calibration and balance cannot be simultaneously satisfied. One would expect that such guarantee would also hold in fair clustering. For various constraints it can be shown that they are in fact at odds with one another. However, it is also worthwhile on the other hand to ask if some fair clustering constraints are more compatible with one another, and how one can satisfy both simultaneously?
Our Contributions: In this paper, take first step towards understanding this question. In particular, we consider two specific group fairesss constraints (1) GF: The group fair clustering (GF) of Chierichetti et al. [17] which roughly states that clusters should have close to population level proportions of each group and (2) DS: The diversity in center selection (DS) constraint [32] which roughly states that the selected centers in the clustering should similarly include close to population level proportions of each group. We note that although these two definitions are both concerned with group memberships, the fact that they apply at different "levels" (clustered points selected centers) makes the algorithms and guarantees that are applicable for one problem not applicable to the other, certainly not in an obvious way. Further, both of these notions are motivated by disparate impact [22] which essentially states that different groups should receive the same treatment. Therefore, it is natural consider the intersection of both definitions (GF DS). We show that by post-processing any solution satisfying one constraint then we can always satisfy the intersection of both constraints. At a more precise level, we show that an a-approximation algorithm for one constraint results in an approximation algorithm for the intersection of the constraints with only constant degradation to approximation ratio a. Additionally, we study the degradation in the clustering cost and show that imposing DS on GF solution leads to a bounded degradation of the clustering cost while the reverse not true. Moreover, we show that both GF and DS are incompatible (having an empty feasible set) with set of distance-based fairness constraints that were introduced in the literature. Finally, we validate our finding experimentally. Due to the space limits we refer the reader to Appendix C for the proofs as well as further details.
2 Related Work
Fairness in clustering: GF and DS. In the line of works on group-level faimesss Chierichetti al. [17] defined balance in the case of two groups to require proportion of a group in any cluster to resemble its proportion in input data, They also proposed the method of creating fairlets and then run generic clustering algorithm on fairlets. Bera et al. [9] generalized the notion of balance to multiple groups, and considered when centers are already chosen how to assign points to centers so that each group has bounded representation in each cluster. While only assuming probabilistic group assignment, Esmaeili et al. [21] presented algorithms that guarantee cluster outputs satisfy expected group ratio bounds. Also working with bounded representation, Esmaeili et al. [20] showed how to minimize additive violations of faimess constraint while ensuring clustering cost is within given upper

---

bound. Besides center-based clustering, group fairness constraint is also applied to spectral clustering
[33]. Recent work due to Wang et al. [41] speeds up computation in this setting. Ahmadi et al. [2] applied group faimess to correlation clustering. As a recent follow-up, Ahmadian and Negahbani [4] generalized the setting and improved approximation guarantee. Ahmadian et al. [6] and Chhabra and Mohapatra [16] introduced group fairness in the context of hierarchical clustering, with work due to Knittel et al. [35] proposing an algorithm with improved approximation factor in optimizing cost with fairness setting. Diversity in center selection was first studied in Kleindessner et al. [32] for data summarization tasks. The authors presented an algorithms that solves the fair k-centers problem with an upproximation factor that is exponential in the number of groups and with running time that is linear in the number of input points. A follow-up work Jones et al. [29] improved the approximation factor to constant while keeping the run time linear in number of input points. Concerned with both the diversity in selected center and its distortion of the summary. Angelidakis et al. [7] proposed an approximation algorithm for the k-centers problem that ensures number of points assigned to each center is lower bounded. Recent work due to Nguyen et al. [37] generalized the problem to requiring group representation in centers to fall in desired range, which is the setting this work is using.
Other fairness considerations clustering. Besides fairness notions already mentioned, other individual fairness notions include requiring individual points to stay close to points that are similar to themselves in output clusters such as that of [34, 13]. The proportionally fair clustering based on points forming coalitions [15]. A notion based on individual faimess that states that points should have centers within a distance R if there are n// points around it within R [36, 30]. Newer fairness notions on clustering problems were introduced recently in Ahmadi al. [3] and Gupta and Dukkipati [26]. For the interested reader, we recommend a recent overview due to Awasthi et al. [8] for exhaustive references and accessible overview of fair clustering research.
3 Preliminaries and Symbols
We are given a set of points C along with a metric distance d(...). The set of chosen centers is denoted by S C C and the assignment function (assigning points to centers) is é C + S. We are concerned with the k-center clustering which minimizes the maximum distance between point and its assigned center. Formally, we have:
min S:IS Sk.ó JEC
max d(j, ((j))
In the absence of constraints, the assignment function ((-) is trivial since the optimal assignment is to have each point assigned to its nearest center. However, when the clustering problem has constraints this is generally not the case.
In fair clustering, each point j E C is assigned a color by a function x(j) = h E H. to indicate its demographic group information, where H. is the set of all colors. For simplicity, we assume that each point has one group associated with and that the total number of colors m = H is a constant. Moreover, the set of points with color are denoted by Ch. The total number of points n = |C| and the total number of points of color h is ny, =Ich J. It follows that the proportion of color is Th = nA Finally, given a clustering (S, Φ), we denote the set of points in the 2th cluster by C. and the subset of color h by Ch = C, nchh
We now formally introduce the group fair clustering (GF) and the diverse center selection (DS) problems:
Group Fair Clustering [17, 10, 9, 5]: Minimize objective (1) subject to proportional demo- graphic representation in each cluster. Specifically, Vi S, vh E H. : 3, C. s C. S an, C, where 3n and a% are pre-set upper and lower bounds for the demographic representation of color h in given cluster.
Diverse Center Selection [32, 29, 371: Minimize objective (1) subject to the set of centers satis- fying demographic representation. Specifically, denoting the number of centers from demographic (color) h by kn, = |5 ch J, then as done [37] must satisfy ky S kn. S kg where ky, and ky are lower and upper bounds set for the number of centers of color h. respectvily.
3

---

Importantly, throughout have vh H 88 > O. Further, for GF consider solutions that could have violations to the constraints as done in the literature [9, 10J. Specifically, a given a solution (S, 6) has an additive violation of p GF if p is the smallest number such that the following holds: vi S, vh E H. | p - IC I C p. We denote the problem of minimizing the k-center objective while satisfying both the GF and DS constraints as GF+DS.
Why Consider GF and DS in Particular? There are two reasons to consider the GF and DS constraints in particular. First, from the point of view of the application both GF and DS are concerned with demographic (group) fairness. Further, they are both specifically focused on the representation of groups, i.e. the proportions of the groups (colors) in the clusters for GF and in the selected center for DS. Second, they are both "distance-agnostic" i.e. given clustering solution one can decide if satisfies the GF or DS constraints without having access to the distance between the points.
4 Algorithms for GF+DS
4.1 Active Centers
We start by observing the fact that if we wanted to satisfy both GF and DS simultaneously. then we should make sure that all centers are active (having non-empty clusters). More precisely, given solution (S, 6) then the DS constraints should be satisfied further vi E $ :Cc:] > 0, i.e. every center in S should have some point assigned to it and therefore not forming empty cluster. The following example clarifies this:
Consider Figure 1. Suppose we have k = 2 and we wish to satisfy the GF and DS constraints with equal red to blue representation. DS requires one blue and one red center. Further, each cluster should have CCblue = CT
Example:
1 Cil to satisfy GF. Consider the following solution S = (2,4) 4) and Φ1 which assigns all points to point including point 4. This satisfies GF and DS. Since we have one blue center and one red center. Further, the cluster of center 4 has no points and therefore
0 = CChlue| Credi Cry. Another solution would have S₂ S (2.4) 4) but with 62 assigning points and to center 2 and points 1 and
Figure 1: In this graph the distance between the points is defined the path distance.
4 to center 4. This would also clearly satisfy the GF and DS constraints.
There is a clear issue in the first solution which is that although center 4 is included in the selection it has points assigned to it (it is empty cluster). This makes it functionally non-existent. This is why the definition should only count active centers.
This issue of active centers did not appear before in DS [32, 37], the reason behind this is that is trivial to satisfy when considering only the DS constraint since each center is assigned all the points closest to it. This implies that the center will at least be assigned to itself, therefore all centers in a DS solution are active. However, we cannot simply assign each point to its closest center when the GF constraints are imposed additionally as the colors of the points have to satisfy the upper and lower proportion bounds of GF.
4.2 The DIVIDE Subroutine
Here we introduce the DIVIDE subroutine (block 1) which is used in subsections 4.3 and 4.4 in algorithms for converting solutions that only satisfy DS or GF into solutions that satisfy GF+ DIVIDE takes a set of points C' (which is supposed to be a single cluster) with center i along with subset of chosen points Q (Q C). The entire set of points then divided among the points Q forming [Q] many new non non-empty (active) clusters. Importantly, the points of each color are divided among the new centers in Q so that the additive violation increases by at most 2. See Figure 2 for an intuitive illustration.
Here use the symbol y index a point in the set Q. Importantly, the numbering starts with 0 and ends with IQ| - 1.
We prove the following about DIVIDE:

---

DIVIDE
41
Figure Illustration of DIVIDE subroutine.
Algorithm DIVIDE
Input: Set of points C' with center E C, Subset of points Q (Q C C) of cardinality (Q)- 2: Output: An assignment function C² - Q.
3: if [Q] 1 then
4: Assign all points C' to the single center in Q.
5:
else
6:
Set firstIndex = 0.
7:
for h H do
8:
Set: T3 IC*1
Q bn Th - [T.]]]]] count
9:
Set: g = firstIndex
10:
while count < [Q]
1 do
by then
12:
Assign [7h]] many points of color h in C' to center q.
13:
Update bn = by
14:
Update firstIndex (firstIndex + 1) mod [Q]-
else
16:
Assign [Th.] many points of color h in C' to center q.
17: end
18:
Update (q + 1) mod [Q], count count + 1.
19: end while
20:
end for
21:
end if
Lemma 1. Given a non-empty cluster C' with center i and radius R that satisfies the GF constraints at an additive violation of p and subset of points Q (Q C C). Then the clustering (Q, Φ) where o DIVIDE(C, Q) has the following properties: (1) The GF constraints are satisfied at an additive violation of at most P + (2) Every center Q is active. (3) The clustering cost at most 2R. If
QQ
IQ] = 1 then guarantee (1) is for the additive violation is at most p.
4.3 Solving GF+DS using a DS Algorithm
Here we show an algorithm that gives a bounded approximation for GF+DS using approximation algorithm for DS. Algorithm 2 works by first calling an ops "us-approximation algorithm resulting in solution (S, 5) that satisfies the DS constraints, then it solves an assignment problem using the ASSIGNMENTGF algorithm (shown
3) where points are routed the centers S satisfy GF constraint. The issue is that some of the centers in 5 may become closed and as result the solution may no longer satisfy the DS constraints. Therefore, we have a final step where more centers opened using the DIVIDE subroutine satisfy the DS constraints while still satisfying the GF constraints at an additive violation and having a bounded increase to the clustering cost.
ASSIGNMENTGF works by solving linear program (2) to find clustering which ensures that (1) each cluster has least 3, fraction and at most an aj fraction of its points belonging to color h, and (2) the clustering assigns each point to center that is within a minimum possible distance R. While the resulting I. solution could fractional, the last step of ASSIGNMENTGF uses MAXFLOOWCE which is an algorithm for rounding an LP solution valid integral assignments at bounded degradation to the GF guarantees and no increase the clustering cost. See Appendix B for details on the MAXFLOWGE GF and its guarantees.
5

---

Algorithm 2 DSTOGF+DS
1: Input: Points C, Solution (S, Φ) with clusters {C ..... C2) satisfying the DS constraints with [S] = k S k of approximation ratio ons for the DS clustering problem.
2: Output: Solution (S, () satisfying the GF and DS constraints simultaneously.
3: (") #ASIIGNMENTGF(S
4: Update the set of centers S' by deleting all non-active centers (which have no points assigned to them). Let (C',...,CC) C,, } be the (non-empty) clusters of the solution (S', x²) with |S'| k' s k.
5: Set Wh H. Sh |S' n ch Set E S Q, {
6: while 7h H such that 8h < k4, do
7:
Pick color ho such that Sho hho
8:
Pick center i S' where there exists point of color ho- Pick point Jhg of color bi in cluster C₁
9:
10: Set Qi = QQ:U (jng) )-
11: Update Sho = Sho + 1.
end while
13:
for i E S" do
Φ DDVIDED, Qi).
15: Vj C Set )(j) (j)..
end for
17: Set S = S' U (Uies Q.).
Algorithm 3 ASSIGNMENTGE
1: Input: Set of centers S, Set of Points
2: Output: An assignment function - S.
3: Using binary search the distance matrix, find the smallest radius R such that LP(C, S, R) in (2) is feasible and call the solution x".
4: Solve MaXFLoWGFFx* S) and call the solution x*.
LP(C,S,
VjE C, S. =0
if d(i > R
(2a)
Vh HiEiVES: Σ
Ti Σ Tij S 0hh
Zij
(2b)
JEC
jEC
Vj C: Σ Izj =1
(2c)
İES
Vj VJECVIEES : Ti E [0.1]
(2d)
To establish the guarantees we start with the following lemma:
Lemma 2. Solution (S', d') of line (3) in algorithm 2 has the following properties: (1) It satisfies the GF constraint at additive violation of 2, (2) It has clustering cost of at most (1 + aps ) Ri where ROPADS the optimal clustering cost (radius) of the optimal solution for GF+DS, (3) The set of centers 5" subset (possibly proper subset) of the set centers S, i.e. S S.
Theorem 4.1. Given an up aps-approiination algorithm for the DS problem, then we can obtain an 2(1 + aps) apprrximaainnnn algorithm that satisfies GF additive violation of 3 and satisfies DS simultaneously.
Remark: If in algorithm no center is deleted in line (4) because it forms empty cluster, then by Lemma 2 the approximation ratio is + ops which is an improvement by a factor of 2. Further, the additive violation for GF reduced from 3 to 2.

---

4.4 Solving GF+DS using GF Solution
Algorithm 4 GFTOGF+DS
1: Input: Points C, Solution (5, Φ) with clusters (C,,..., C satisfying the GF constraints with
[S] = k k.
2: Output: Solution (S, () satisfying the GF and DS constraints simultaneously.
3: Initialize: AA E H. 54 = V. Q = =
4: ior E 8 do
5: if 3h H < ky then
6: Let hg be a color such that Sho < khp
7:
else
8:
Pick ho such that Shg + S kig
9:
end if
10:
Pick point Jhp of color ha in cluster C₃
Set Q2 = (Jho
12: Update Sh,, Sho + 1.
13: end for
14: while 3h E H: < kl, do
15: Pick color ho such that Sho 1
16: Pick center i S with cluster C2 where there exists point of color ho not in Q2
17: Pick point Jho of color bn in cluster C₁
18: Set Qi = = {jng]-
19: Update 8ho = Sho +1.
20: end while
21: Set S = UiesQi.
22: for E $ do
DIVIDE(C,, Q:). 24: Vj E C:: Set Φ(j) = di()). (Assignment to center is updated using DIVIDE.
23:
25:
end for
Here start with solution (S, の) of cost R that satisfies the GF constraints and want to make satisfy GF and DS simultaneously. More specifically, given any GF solution we show how it can be proc-sdde to satisfy GF+DS at bounded increase its clustering cost by factor of (see Theorem 4.2). This implics as a corollary that we have an aG aappaoxxxxiiiionn algorithm for GF then obtain a dece-approi algorithm for GF+DS (see Corollary 1).
The algorithm essentially first "covers" each given cluster Č, of the given solution (S,ō) by picking point of some color h to be future center given that picking point of such a color would not violate the DS constraints (lines(4-13)). If there are still colors which not have enough picked centers (below the lower bound k),), then more points are picked from clusters where points of such colors exist (lines( 14-20)). Once the algorithm has picked correct points for each color, then the DIVIDE subroutine is called to divide the cluster among the picked points.
Now we state the main theorem:
Theorem 4.2. If we have solution (5, of cost R that satisfies the GF constraints where the number of non-empty clusters [ & k. then we can obtain a solution (S, ②) that satisfies GF at additive violation of and DS simultaneously with cost R < 2R.
Corollary 1. Given an ocr-approximation algorithm for GF, then we can have a 20Gr approximation algorithm that satisfies GF at additive violation of and DS simultaneously.
the given GF solution has the number of cluster h;, then output will have an additive violation of zero, i.e. satisfy the GF constraints exactly. This would happen DIVIDE would always receive Q with IQ:| = and therefore we can use the guarantee of DIVIDE for the special case of Ql 1.
Remark:

---

Unconstrained (Agnostic) Clustering
Unbounded PoF even if
Unbounded PoF
additive violation allowed for GF
DS Constrained
GF Constrained
Unbounded PoF if additive violation is allowed for
Bounded PoF violation of 2 for GF
additive
GF DS Constrained
Figure 3: Figure showing the PoFF relation between Unconstrained, GF, DS, and GF+DS clustering.
5 Price of (Doubly) Fair Clustering
Here we study the degradation in the clustering cost (the price of fairness) that comes from imposing the fairness constraint on the clustering objective. The price of fairness PoF, is defined as PoF.
Clustering Cost subject to Constraint
[20, 9]. Note that since we have two constrains here GF and DS, we Clustering Cost of Aynostic Solution
also consider prices of fairness of the form Po
Clustering subject Constraints сı og which Clustering Cost subject Constraint es
equal the amount of degradation in the clustering cost if we were to impose constraint in addition constraint 6₁ which is already imposed. Note that we are concerned with the price of fairness in the worst case. Interesingly, we find that imposing the DS constraint over the GF constraint leads to bounded PoF if we allow an additive violation of for GF while the reverse true even if allow an additive violation of Q ) for GF.
We find the following:
Proposition 5.1. For any value of k 2 2, imposing GF can lead to an unbounded PoF even if we allow an additive violation of S2 )
Proposition 5.2. For any value of k imposing DS lead unbounded PoF.
Proposition 5.3. For any value of k 2 2, imposing GF a solution that only satisfies DS can lead to an unbounded increase in the clustering cost even if we allow an additive violation of (+)) n))
Proposition 5.4. Imposing DS on a solution that only satisfies GF leads to a bounded increase in the clustering cost of most (PoF <. if we allow an additive violation of 2 in the GF constraints.
Incompatibility with Other Distance- Fairness Constraints
In this section, we study the incompatbiility between the DS and GF constraints and family of distance-based fairness constraints. We note that the results of this section do take into account the clustering cost and are based only on the feasibility set. That is, we consider more than one constraints simultaneously and see if the feasibility set is empty or not. Two constraints are considered incompatible if the intersection of their feasible sets is empty. In some cases we also consider solution that could have violations to the constraints. We present two main findings here and defer the proofs and further details to the Appendix section'.
Theorem 6.1. For any value k > 2, the fairness in your neighborkood [30], socially fair constraint [1, 24] are each incompatible with GF even if we allow an additive violation of 2 constraint. For any value even if we allow an additive violation of ((()) in the GF constraint.
v. ) in the GF the proportionally fair constraints [15] incompatible with GF
Theorem 6.2. For any value k 2 3, the fairness in your neighborhood [30], socially fair [1, 24] and proportionally fair [15] constraints are each incompatible with DS.
Note that socially fair clustering [1. 24] is defined as an optimization problem not constraint. However, it straightforwardly turned into constraint, the Appendix for full details.

---

7 Experiments
We use Python 3.9, the CPLEX package [38] for solving linear programs and NetworkX [27] for max-flow rounding. Further, Scikit-learn is used for some standard ML related operations. We use commdity hardware, specifically a MacBook Pro with an Apple M2 chip.
We conduct experiments over datasets from the UCI repository [23] to validate our theoretical findings. Specifically, we use the Adult dataset sub-sampled to 20,000 records. Gender is used for group membership while the numeric entries used to form a point (vector) for each record. We use the Euclidean distance. Further, for the GF constraints we set the lower and upper proportion bounds to 3h = (1 6) and ou (1 + 8),% for each color h where Th is color hts proportion in the dataset and we set 8 = 0.2. For the DS constraints, since we do not deal with a large number of centers we set ky, 0. and Kj ri,k
We compare the performance of 5 algorithms. Specifically, we have (1) COLOR-BLIND: An implementation of the Gonzalez k-center algorithm [25] which achieves 2-approximation for the unconstrained k-center problem. (2) ALG-GF: A GF algorithm which follows the sketch of [9], however the final rounding step is replaced by an implementation of the MAXFL.OWGF rounding (3) ALG-DS: An algorithm for the DS problem recently introduced by [37] for which also has an approximation of (4) GFTOGFDS: An implementation of algorithm 4 where we simply use the GF algorithm just mentioned to obtain a GF solution. where DS algorithm is used as a starting point instead.
subroutine. This algorithm has a 3-approximation for the GF constrained instance.
(5) DSTOGFDS: Similarly an implementation of algorithm 2
The price of faimnss of the algorithm. Note that we always calculate the price of fairness by dividing by the COL.OR- COI.OR-BI.IND clustering cost since it solves the unconstrained problem. (2) CFF-Violation: Which is the maximum additive violation of the solution for the GF constraint as mentioned before. (3) DS- Violation: Which
Throughout we measure the performance of the algorithms in terms of (1) PoF:
is simply the maximum value of the under-repreeeentaiin or over-representation across all groups in the selected centers.
(
(b)
3.20
2.00
1.2
Figure Adult dataset results: (a) PoF comparison of algorithms, with COLOR-BLIND as baseline; (b) GF-Violation comparison; (c) DS- OS-Violation comparison.
Figure shows the behaviour of all 5 algorithms. In terms of PoF, all algorithms have significant degredation in the clustering cost compared to the COLOR- BLIID baseline except for ALG-DS. However, ALG-DS has very large CioVillatinn. In fact, the GF-Violation of ALG-DS can be more than times the GF-Violation of COILOR-BIIINE small clustering cost, it can give very bad guarantees for the GF constraints. Finally, in terms of the DS-Violation we see that the ALG-GF and the COLOR- --LIDD solution can violate the DS constraint. Note that both coincide perfectly on each other. Further, although the violation is is very significant since unlike the GF constraints the number of centers can be very small. On the other hand, we see that both GFTOGFDS and DSTOGFDS give the best of both worlds having small values for the GF- VF-Violation and zero values for the DS- and while their price of fairness can be significant, it is comparable to ALG-GF, Interestingly, the GFTOGFDS and DSTOGFDS are in agreement in terms of measures. This could be because our implementations of the "GF part" of DSTOGFDS (its handling of the GF constraints) has similarities the GFTOGEDS algorithm. We show further experiments in the appendix.
This indicates that while ALG-DS has

---

References
[1] Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equitable group representations, 2020.
[2] Saba Ahmadi, Sainyam Galhotra, Barna Saha, and Roy Schwartz. Fair correlation clustering. 2020.
[3] Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Matthäus Kleindessner, Jamie Morgenstern, Pattara Sukprasert, and Ali Vakilian. Individual preference stability for clustering. arXiv preprint (rXXi:2207.03600 2022.
[4] Sara Ahmadian and Maryam Negahbani. Improved approximation for fair correlation clustering. In International Conference on Artificial Intelligence and Statistics, pages 9499-9516. PMLR, 2023.
[5] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. In International Conference on Knowledge Discovery and Data Mining, 2019.
[6] Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Ben- jamin Moseley, Philip Pham, Sergei Vassilvtiskii, and Yuyan Wang. Fair hierarchical clustering. In Neural Information Processing Systems, 2020.
[7] Haris Angelidakis, Adam Kurpisz, Leon Sering, and Rico Zenklusen. Fair and fast k-center clustering for data summarization. In International Conference on Machine Learning, pages 669-702. PMLR, 2022.
[8] Pranjal Awasthi, Brian Brubach, Deeparnab Chakrabarty, John P. Dickerson, Seyed Es- maeili, Matthäus Kleindessner, Marina Knittel, Jamie Morgenstern, Samira Samadi, Ar- avind Srinivasan, and Leonidas Tsepenekas. A tutorial and resources for fair clustering. com/ Accessed: 2023-05-16.
https: htap::://ww.aaiccusseereee
[9] Suman Bera, Deeparna Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Neural Information Processing Systems, 2019.
[10] Ioana O Bercea, Martin GroB, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. 2019.
[11] Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):
3-44, 2021.
[12] Anna Brown, Alexandra Chouldechova, Emily Putnam Haatmm--onttein,. Andrew Tobin, and Rhema Vaithianathan. Toward algorithmic accountability public services: A qualitative study of affected community perspectives algorithmic decision- in child welfare services. In Proceedings of the 2019 CHI Conference on Human Factors Computing Systems, pages 1-12, 2019.
[13] Brian Brubach, Darshan Chakrabarti, John Dickerson, Samir Khuller, Aravind Srinivasan, and Leonidas Tsepenekas. A pairwise fair and community- community-preserving approach to k-center clustering. 2020.
[14] Darshan Chakrabarti, John P Dickerson, Seyed A Esmacili, Aravind Srinivasan, and Leonidas Tsepenekas. A new notion of individually fair clustering: a-equitable k-center. International Conference on Artificial Intelligence and Statistics, pages 6387-6408. PMLR, 2022.
[15] Xingyu Chen, Brandon Fain, Charles Lyu, and Kamesh Munagala. Proportionally fair clustering. 2019.
[16] Anshuman Chhabra and Prasant Mohapatra. Fair algorithms for hierarchical agglomerative clustering. In 2022 2/ IEEE International Conference on Machine Learning and Applications (ICMLA), pages 9.1-211. IEEE, 2022.
10

---

[17] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Neural Information Processing Systems, 2017.
[18] Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
[19] Cynthia Dwork and Christina Ilvento. /rXiv:/806.0612 2018.
Fairness under composition.
arXiv preprini
[20] Seyed Esmaeili, Brian Brubach, Aravind Srinivasan, and John Dickerson. Fair clustering under bounded cost. Advances in Neural Information Processing Systems, 11114345-143557 2021.
[21] Seyed A Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John P Dickerson. Probabilistic fair clustering. In Neural Information Processing Systems, 2020.
[22] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkata- subramanian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259-268, 2015.
[23] A Frank. Uci machine learning repository, irvine, ca: University of california, school of information and computer science. http://archive. ics. uci. edu/ml, 2010.
[24] Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair k-means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountability and Transparency, pages 438 448, 2021.
[25] Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293-306, 1985.
[26] Shubham Gupta and Ambedkar Dukkipati. Consistency of constrained spectral clustering under graph induced fair planted partitions. Advances in Neural Information Processing Systems, 35: 13527-13540 2022.
[27] Aric Hagberg, Dan Schult, Pieter Swart, D Conway, L Séguin-Charbonnen C Ellison, B Ed- wards, and J Torrents. Networkx. high productivity software for complex networks. Webová sirá nka https://network.. lanl, gow/wiki, 2013.
[28] White House. Big data: report on algorithmic systems, opportunity, and civil rights. executive office of the president, 2016.
[29] Matthew Jones, Huy LE Nguyên, and Thy Nguyen. Fair k-centers via maximum matching. In International Conference on Machine Learning, 2020.
[30] Christopher Jung, Sampath Kannan, and Neil Lutz. A center in your neighborhood: Fairness in facility location. 2019.
[31] Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination risk scores. arXiv preprint arXiv:1609.05807 2016.
[32] Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern Fair k-center clustering for data summarization. 2019.
[33] Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstern. Guarantees for spectral clustering with fairness constraints. In International Conference Machine Learning, pages 3458-3467. PMLR, 2019.
[34] Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstemn. A notion of individual fairness for clustering. 2020.
[35] Marina Knittel, Max Springer, John P. Dickerson, and MohammadTaghi Hajiaghayi. Gen- eralized reductions: Making any hierarchical clustering fair and balanced with low cost. In International Conference Machine Learning, 2023.

---

[36] Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering. In International Conference on Machine Learning, 2020.
[37] Huy Lé Nguyen, Thy Nguyen, and Matthew Jones. Fair range k-center. arXiv:2207. / 1337, 2022.
arXiv preprint
[38] Stefan Nickel, Claudius Steinhardt, Hans Schlenker, and Wolfgang Burkart. Ibm ilog cplex optimization studio- a primer. In Decision Optimization with IBM ILOG CPLEX Optimization Studio: A Hands-O0 -On Introduction to Modeling with the Optimization Programming Language (OPL), pages 9-21. Springer, 2022.
[39] Manish Raghavan, Solon Barocas, Jon Kleinberg, and Karen Levy. Mitigating bias in algorith- mie hiring: Evaluating claims and practices. In Proceedings of the 2020 conference on fairesss accountabilliry, and transparency, pages 469-481, 2020.
[40] Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. arXiv preprint arXiv: 1XXi::882..0299 2018.
[41] Wang, Ding Lu, Ian Davidson, and Zhaojun Bai. Scalable spectral clustering with group fairness constraints. In International Conference on Artificial Intelligence and Statistics, pages 6613-6629. PMLR, 2023,
12

---

A
Useful Facts and Lemmas
Fact A.l. Given non-negative numbers a1, .2...... .... On and positive numbers b1, ..., , then:
Eie(n] ai EiEln] by
min *E[n]
S xE[u]
B MAXFLOWGF
We start with the following Lemma. First, note that Jnj a decision variable æni then point j is assigned to center and if æaj 0 then it is not. In an integral solutions Jigj. E {0, 1), but fractional LP solution could instead have values in [0, 1]. We use the bold symbol x for the collection of value (Fa) JEQUEC:
Lemma 3. Given a fractional solution ftc that satisfies the GF constraints at an additive violation of at most p. then if there exists an integral solution xlites that satisfies:
V
Σ
frac
Σ jEC
I
integ
q3
frac 9s
(3)
jEC
JEC
Ag E Q, H:
Σ
Σ
intes
frac 2
(4)
jECK
jECK
JECK
Then this integral solution integ satisifies the GF constraints at an additive violation of at most p p+ 2.
Proof. Since the fractional solution satisfies the GF constraints at additive violation of p. then have the following:
p
(Bh
frne Eig
frnc
<
0hh
Σ
Frac I
+
P
jEC
jEC
JEC
We start with the upper bound:
integ D
T
TEC
jeCk
Frac
+ 1
jeCh
$ 0%
T q)
frac
+ p + 1
IEC
0%
Σ
integ
+ 1) + p+1
jEC
0%
Σ JEC
integ
9)
(ar +
< 0/h
intog
+ (p 2)
9j
1EC
13

---

Now do the lower bound:
Σ
intog
Σ
43
JEC
LECK
jECK
B
I qj
frac
1
JEC
B
I qi
intog
1) - (p + 1)
JEC
B
integ Q2
(3p + p + 1)
JEC
I
intog 93
(p 2)
JEC
The LP solution given MAXFLOWGF satisfies the GF constraints additive violation of p. want to show that the output integral solution satisfies the above conditions of Eqs (3 and 4). The MAXFLOW GF(x! C.Q) subroutine is similar to that shown in [20, 5, 10]. Specifically, given an LP solution x" {21P) JEQ set of points C, and set of centers Q and color assignment function X - H which assigns each point in C exactly one color in the set of colors H.
construct the flow network (V, A) according to the following:
1. V = (s,t)ucu ((a l4 E Q, H}.
2. = A U 12 U A3 U A4 where A1 = {(s,))li E C} with upper bound of 1. A2 =
{(i, (q. )") E C,z > 0} with upper bound of The are set A3 = {(lg, l²) 4)1g
Q E H} with lower bound Ejec>
I.I.P and upper bound of Ejeca 9J
_IP 4j
As for
A4 = ((g, t)]g E Q} the lower and upper bounds are Ejec LP qj
and Ejec +
In the above all lower and upper bounds of the network are integral, therefore if can show feasible solution to the above then there must exist an integral flow assignment which also satisfies the constraints. By the construction of the network have the following fact about any max flow integral solution integ
Fact B.1.
V
Σ
LP
Σ
lnter
(5)
JEC
JEC
JEC
4q E EEEE
Σ
Σ jECH
intes
Σ LPP
(6)
JECA
JECK
Accordingly, the following theorem immediately holds:
Theorem B.1. Given an LP solution to MAXFL.OWGF that satisfies the GF constraints at an additive violation of and clustering cost of R. then the output integral solution satisfies the GF constraints additive violation of + 2 and a clustering cost of at most R.
Proof. The guarantee for the additive violation of GF follows immediately from Lemma 3 and Fact B.I. The guarantee for the clustering cost holds, since point (vertex) is not connected to center vertex (q. g²) unless zgj > 0 which can only be the case if d(j, q) $ R.
14

---

C OMITTED PROOFS
We restate the following lemma and give its proof:
Lemma 1. Given non-empty cluster C' with center i and radius R that satisfies the GF constraints at an additive violation of and subset of points Q (Q C C). Then the clustering (Q, Q) where DIVIDE(C, Q) has the following properties: (1) The GF constraints are satisfied at an additive violation of at most ( + 2. (2) Every center in Q is active. (3) The clustering cost is at most 2R. If
[Q] then guarantee (1) is for the additive violation is at most p.
Proof. We first consider the case where [Q] > 1. We prove the following claim":
Claim 1. For the fractional assignment { IqEQUjEC such that:
V Q Σ
frc
Th
QQ
jECK
frac holds that: (g) E Q Ejec frac qs 2 1, (2) GF constraints are satisfied at an additive violation
e of
[QI
Proof. Now we prove the first property
Trac
Σ
Σ
Trec
ch
(since C C)
Q
jEC
jECh
GEH
Since the GF constraints given center are satisfied at an additive violation of then we have:
Vh E H - 3.ICI |C*| S ot |cx
(8)
Therefore, since the amount of color for each center in Q with the fractional assignment can be obtained by dividing by [Q), then we have:
vh H. Q
Ql
P
Bh
frac 40
Σ
frac
0.h
frac
[Q]
P
JEC
jECK
JEC
Therefore the GF constraints are satisfied at an additive violation of [Q]
Denoting the assignment é resulting from DIVIDE by f holds:
integ
IEEQSEE then the following claim
Claim 2.
E
Σ
frac
intez 9)
frae yj
jEC
JEC
jEC
4g E Q, H::
Σ jECK
prac qi
I
intes
frae 93
jECh
JECK
Proof. For any color h we have [Op] ax|Q1 + bn where as and by non-negative integers and bn is the remainder of dividing Cvl by Q (br, E {0, (,.., |Q1
13). It follows that Σjeca x frac
q)
Th an +
DIVIDE gives each center either Ejeca J [
ba
integ a [Th. Ejecr or
frac
Ejech 2
integ aa +1 [h Ejeck
2.t This proves the second condition.
For the first condition, note that |C| E (an|Q) + bx) = (EER an) QI + a|Q1 + where we set ΣnEn by [2 + with a and being non-negative integers. is the remainder and has values
II notation æaz [0, 1] denotes the assignment of point j center
15

---

in (0, 10.1,...,,11111 Accordingly, the sum of the remainders across the colors is Q + Since the remainders are added "successivly" across the centers (see Figure 2) and a is divisible by [Q], then for
any center y E Q either Ejec "0j inleg
CEEE un) + a Ejec Fgj =EhEN as) + +1 1. Note
inleg
that Ejec 2 ΣNER Tn = =EhEE an) +a+ Q Therefore, EEEc ..fie = CEhe an) +a
and Ejec frac = (EhEH an) a + 1. This proves, the first condition.
By Claim 2 and Lemma follows that for each center g E Q the assignment {a JeeQ satisfies the GF constraints at an additive violation of P + 2, this proves the first guarantee.
inleg
By Claim 2 and guarentee (1) of Claim I, then Vg E Q Ejec
Dai
integ
Eysc 1
di 2 1.
Therfeore, every center q E Q is active proving the second guarantee. Guarantee (3) follows since Vj E C:: :d(, - d(j.i) d(i, o())) S 2R.
Now if [Q] 1, then guarantee (2) follows since the cluster C' is non-empty. Guarantee (3) follows similarly to the above. The additive violation in the GF constraint on the other hand is since the single center Q has the exact set of points that were assigned to the original center i.
We restate the next lemma and give its proof:
Lemma 2. Solution (S', Φ') of line (3) in algorithmm 2 has the following properties: (1) It satisfies the GF constraint at an additive violation of 2, (2) It has clustering cost of at most (1 + ops) Ba where Re is the optimal clustering cost (radius) of the optimal solution for GF+DS, (3) The set of centers S is subset (possibly proper subset) of the set of centers S, i.e. S C S.
Proof. We begin with the following claim which shows that there exists solution that only uses centers from S to satisfy the GF constraints exactly and at a radius of at most (1 + R Note that this claim has non-constructive proof, i.e. it only proves the existence of such solution:
Claim 3. Given the set of centers S resulting from the opss approxiixinnaoo algorithm, then there exists an assignment @u from points in C to centers in 5 such that the following holds: (1) The GF constraint is exactly satisfied (additive violation of 0). (2) The clustering cost is at most (1 + aps) Ror=D>
Proof. Let (SGFDDs o² GF be an optimal solution the GF+DS problem. Vi E F let (()) = arg minges d(i, i), i.e. N(i) is the nearest center in $ to center i (ties are broken using the smallest index). do is formed by assigning all points which belong to center E Streps to (1).. More formally, Vj E C o² (r) than one center in -DF to have the same nearest center in S. We will now show that do satisfies the GF constraint exactly. Note first that if center i E Š has not been assigned any points by do. then it is empty and trivially satisfies the GF constraint exactly. Therefore, we assume that has non-empty cluster. Denote by - the set centers i E Str-ns for which is the nearest center, then using Fact A. and the fact that every cluster in (SGFDDs: GF+DS) satisfies the GF constraint exactly we have:
we set ()()) (2).. Note that it is possible for more
ICA |C, SEN-I()
E
EieN-
C C,
ch |C
C [
Bn < min
S
S max iEN-
S O'h
(10)
ΣieN-
The proves guarantee (1) of the lemma. Now prove guarantee (2), we denote by Ris the optimal clustering cost for the DS constrained problem. We can show that Vj E C:
d(j. (o())) < d(j, o" craDs()) (i)) + d(ø cxnns()),
s d(j. o" GF-Ds (j)) + d(ø (F, GF+Ds()))) (since (b(()) N(6" Gr+ns(j)))
< Re + Ris
(since S is ops approximation for DS
< (1 + ans) R
Where the last holds since Ris & R because the set of solutions constrained by DS is a subset of the set of solutions constrained by GF+DS.
D
16

---

Now can prove the lemma. By the above claim, it follows that when ASSIGNMENTGF is called, the LP solution from line (3) of algorithm block 3 satisfies: (1) The GF constraints exactly and (2) Has a clustering cost of at most (1 + &ps RG This is because LP (2) includes all integral assignments from C to S including pu. Since this LP assignment is fed to MAXFLOWGF it follows by Theorem B.1 that the final solution satisfies: (1) The GF constraint at an additive violation of 2, (2) Has clustering cost of most (1 + ons) R.--S Guarantee (3) holds since some centers may become closed (assigned no points) and therefore S' C S (possibly being proper subset).
We restate the following theorem and give its proof:
Theorem 4.1. Given an ops approximation algorithm for the DS problem, then we can obtain an 2(1 + ops) approximmaion algorithm that satisfies GF at an additive violation of 3 and satisfies DS simultaneously.
Proof. By Lemma 2 above, the set of centers S' is a subset (possibly proper) subset of S and therefore
the DS constraints may no longer be satisfied. Algorithm 2 select points from each color h so that when they are added to S', then for each color h the set of centers is at least 3, Since these new centers are opened using the DIVIDE subroutine then it follows that they are all active (guarantee (2) of Lemma 1).
Further, by guarantee (3) of Lemma for DIVIDE have for any point assigned to new center g that d(j. 9) I 2d(j. d'))) s 2(1 + aps) GFDDS
Finally, by guarantee (1) of Lemma DIVIDE is called over cluster that satisfies GF an additive violation of 2 and therefore the resulting additive violation is at most max [Q:
2 + 2}. Since
2 2 2 Q1
+ 2 + 2 The additive violation is at most 3.
We restate the next theorem and give its proof:
Theorem 4.2. If we have solution (5, σ) of cost R that satisfies the GF constraints where the number of non-empty clusters is S = k S k, then we can obtain a solution (S, の) that satisfies GF at an additive violation of 2 and DS sinultaneously with cost R $ 2R.
Proof. We point out the following fact:
Fact C.1. Every cluster in (5,Ø) has at least one point from each color.
Proof. This holds, since given center i S we have |C&| > 0 and therefore wh H 1C 3.1C,] > 0 and therefore lCh1 > 1 since it must be an integer.
We note that the values (Bh, an JEE and & must lead to a feasible DS problem, i.c. there exist positive integers 9h. such that ΣnER 9h k and Yh E H. 3gk S Ih S ag,, Accordingly, since lines (4-13) in algorithm 4 can always pick a point of some color such that the upper bound og is not exceeded for every cluster i. Therefore the following fact must hold
Fact C.2. By the end of line (13) we have Vi E S: 1Qd 2 1.
Further, the final Sh. values are valid for DS:
Claim 4. By the end of line (13) the values of sh. satisfy: (1) EnEN sh k (2) H Bak S 8h S ark.
Proof. Lines (4-13) add values sy the lower bound B k for color h not satisfied. If the lower bound is satisfied for all colors, then points of some color h are added provided that adding them would not exceed the upper bound of or l (see line 5). Therefore, by the end of line (13) for any color h E H S/ S a and either 8s. 2 3r or 8,, < 1r,k3.
If by the end of line (13) we have Yh 7 8%, 2 Ba then the algorithm moves to line (22). Otherwise, it will keep picking points and incrementing until Vh E H 8A 2 3yk.
'To see why we could have St. < k.k, consider the case where &e < l and therefore there would not be enough clusters that can add points for each color.
17

---

Further, since such valid DS values exist must be that the above satisfies ΣNER 8h S and Aa E H 84 I ogk. This concludes the proof for the claim.
By Lemma for DIVIDE the new centers U are active (guarantee 2 of DIVIDE) and since the values of are valid (Claim 4 above), therefore S satisfies the DS constraints.
Since the assignment in each cluster in the solution (S, Φ) is formed using DIVIDE the clusters of (5, 6) then by guarantee of DIVIDE, each cluster (S, Φ) satisifes GF at an additive violation of 2. Finally, the clustering cost is most R S 2R (guarantee 3 of DIVIDE).
We restate the following corollary and give its proof:
Corollary 1. Given an OGF approximation algorithm for GF, then we can have 20GF approximation algorithm that satisfies GF at an additive violation of and DS simultaneously.
Proof. Using the previous theorem (Theorem 4.2) the solution (S, 6) has cost of R S OGF OPToF. The post-processed solution that satisfies GF at an additive violation of 2 and DS simultancously has cost of It < 2R < 2u OPTer I 2agr OPT The last inequality follows because OPTer I OPT which the case since both problems minimize the same objective, however by definition the constraint set of GF + DS is subset of the constraint set of GF.
Before we proceed, we define the following clustering instance which will be used in the proof:
Definition 1. t-Community Instance: The l-community instance is a clustering instance where the set of points can be partitioned into & communities (subsets) {Cf), ,.... CCT) of coinciding points (points within the same community are separated by a distance 0f Further, the communities are of equal size, i.e. Vi e | = Moreover, the distance between any two points belonging to different communities in the partition is at least R > 0.
R
R
R
R
Figure 5: An E-community instance to show Price of Fairness (GF) and incompatibility between GF and other fairness constraints when is even.
R
R
R
R
T
t-1
Figure 6: An Ê-community instance to show Price of Fairness (GF) and incompatibility between GF and other fairness constraints when is odd.
Figures and 6 show two examples the E-community instances. When clustering with a value of k the given f-community instance with is arguably the most "natural" clustering instance where the clustering output is the communities {CC) CCT),
The following fact clearly holds for any f-community instance:
18

---

for both color, we must have Fact C.3. wewe cluster an l-community instance with k- E then: (1) The set of optimal solutions are (Ser, (C1) where Ser has exactly one center from each community {CT) x.....Ck Further, points are assigned to a center in the same community. (2) Clustering cost of (Scr, is O. (3)
Any solution other than (ScI, Φc1) has a clustering cost of at least R > 0.
We restate the following proposition and give its proof:
Proposition 5.1. For any value of k 2 imposing GF can lead to an unbounded PoF even if allow an additive violation of 52 ).
Proof. Consider the case where & 2 2 even and refer to Figure where we have & communities that alternate from red to blue color. Further, by Fact C.3 the optimal solution has a clustering cost of 0. The optimal solution would have one center in each of the = communities, and assign points to its closest center.
we set the lower and upper proportion bounds to 1 for both colors, then to satisfy GF each cluster should have both red and blue points. There must exists a cluster C; of size C2 E. it follows that to satisfy the GF constraints at additive violation of p. then |Chlue|
C p n p and
similarly we would have |C 2 n p. By setting p
e for some constant e >> 0, then we
have Caller, IC > 0. This implies that point will assigned to center a distance R > 0 and
therefore the PoF is unbounded.
For value of is that is odd, see the example of Figure 6. Here instead the last community has the same number of red and blue points. We call the cluster whose center is in the last community Clast- If I + E. then there are points assigned the center of Cisst from other communities incurring cost R >> 0 or points in the last community are assigned to other centers at distance R > O. If points, k centers are
|Cisal = + then in the remaining k k- 1 communities with total of chosen. There must exists a cluster C₁ of size |C,l 2 E. We then follow the same argument as in the even & case, which to satisfy GF with additive violation p = 2
n
n
|C [Crull > 0. This means at least a point will be assigned to a center at a distance R > 0 and therefore the PoF is unbounded for the odd k case well.
We restate the following proposition and give its proof: Proposition 5.2. For any value of k 2 3, imposing DS can lead to an unbounded PoF.
Proof. Consider a case of the community instance shown Figure 7 where k 2 3 and k = f. Here all communities are blue, except for the last which has an red points and green points. Similar to the previous proposition since is a community instance with e = k, then by Fact C.3 the optimal solution has clustering cost of 0 and would have center in each community and assign each point to its closest center.
Suppose for DS we set k H ky color. This implies that we can have at most k blue center, therefore there will be a community (composed of all blue points) where no point is picked as center. Therefore, the clustering cost is R > 0 and the PoF unbounded.
green > 0, this implies that we should pick center of each
R
R
R
R
t-1
Figure 7: An É-community instance to show Price of Fairness (DS) and incompatibility between DS and other fairness constraints.
We restate the following proposition and give its proof:
19

---

Proposition 5.3. For any value of k 2 2, imposing GF on a solution that only satisfies DS can lead to an unbounded increase in the clustering cost even if we allow an additive violation of }
Proof. The proof follows similarly to Proposition 5.1. For k 2 2 and k is even. Consider the same case as in Figure where we have & = k. In this case, we set the upper and lower proportion bounds for both GF and DS to 2- This implies to satisfy DS the number of red and blue centers should each be 5. Thus solutions that satisfy the DS constraint are the optimal unconstrained solutions as specified in Fact C.3. The rest of the proof proceeds exactly as the proof for the even & case in Proposition 5.1.
For k 2 3 and k is odd, consider the same case as in Figure 6. In this case, we set the upper and lower proportion bounds for GF to 1 And we set the upper and lower bound for number of centers in DS constraint as 2
k-1 + 1 and k-1 respectively for both colors. Note that an optimal solution specified in
2 Fact C.3 which chooses either red or blue point in the right most community as center satisfy this DS constraint. The rest of the proof proceeds exactly as the proof for the odd & case in Proposition 5.1.
We restate the following proposition and give its proof:
Proposition 5.4. Imposing DS on a solution that only satisfies GF leads to a bounded increase the clustering cost of at most 2 (PoF < 2) if we allow an additive violation of 2 in the GF constraints.
Proof. This follows from Theorem 4.2 since we can always post-process a solution that only satisfies GF into one that satisfies both GF at an additive violation of 2 and DS simultaneously and clearly from the theorem we would have PoF clustering cost GF post-procesed solution clustering cost GF solution
2 clustering cost of GP solation clustering of GF solution
2.
D Omitted Proofs, Additional Results, and Details for Section 6
In this section, we provide more details and proofs for theorems and facts that appeared in Section 6. We present proof for theorem 6.1. We begin by giving the full definitions of the relevant fairness constraints.
Definition 2. Neighborhood Radius [30]: For given set of points C to cluster and a given number of centers k, the neighborhood radius of a point is the minimum radius r such that at least |C)/K/ l of the points in C are within distance of j: NRc, (i) min(r (BB(5) n C1 2 |CC/k), wheree B,(j) is the closed ball of radius r around j.
Definition 3. Fairness in Your Neighborhood Constraint [30]: For given set of points C with metric d(.,.), .), a clustering (S, 5) is foxn-fair for all j E C. d(j) I oxn (J)
Definition 4. Socially Fair [1, 24]: For clustering problem with k. centers on points C which are from H groups and Useu Ch C, the socially fair clustering optimization problem is to minimize
the maximum average clustering cost across all groups:
min S.SiSko
max
Σ O' (())))))*
KEH.
Chh
JECK
Note that socially fair does not optimize over assignment functions because it assumes assignment follows optimal rule: a point is assigned to the cluster center closest to it.
Definition 5. An oss--oocalll fair solution to a clustering problem is a solution of cost at most OsF of the optimal socially fair solution.
This definition allows us to bound the clustering cost of an ass-SSciallly Fair solution (Sa, da) as:
Σ Li (i) S asF min max SUSISk NEH
Σ d' (()))())).
max NEH 1h
Ch
jECK
JECh
Definition Approximately proportional[15): Given a set of centers S C with |S| k. is [u] and for all y C.
oxp-aprroximately proportional (ow--proportional) iU C and [U] 2 there exists E U with CAP d(i, v) Z d(i, o(1)).
'p 1 for the m-meiaa and p = for the m-mmans
20

---

We restate the following theorem and give its proof:
Theorem 6.1. For any value l 2 2, the fairness in your neighborkood [30], socially fair constraint [1, 24] are each incompatible with GF even if we allow an additive violation of ())) in the GF constraint. For any value k 2 5, the proportionally fair constraints [15] is incompatible with GF even if we allow an additive violation of ((()) in the GF constraint.
Proof. We show incompatibility of GF with the three Fairness notions. Recall that we consider GF and another fairness constraint at the same time, and incompatible means there are cases where no feasible solution exists that satisfies both constraints at the same time.
Lemma 4. For any k 2 2, there exist clustering problem where no feasible solution exists that satisfies both Fairness in Your Neighborhood and GF even if we allow an additive violation of ( in the GF constraint.
Proof. Consider the case where k 2 2, and consider the clustering problem on a Ê-community instance with k We consider the case where lower and upper proportion bound of GF are set to for both colors.
Claim 5. On the above mentioned clustering problem, an fxx solution in the Fairness in Your Neighborhood notion for finite ONN is solution in the set of optimal solutions (Sc1, @c1).
Proof. By Definitions 1 and 2, for any point j E C, its neighborhood radius is (Rc,(j) = min(r: [B, [C|/k) 0. This is because each point in one of the subset, and by definition, the subset is of size = E. and points in the same subset are separated by a distance 0.
For solution a f-community instance (S, 6) (ScI, for any point C, because S contains a center in the community where j is, S) =0
By definition of o fairnnsss,,, this means on f-community instance, any solution in (Scr, Φc1) is aNR--fair with a finite ONR- This is because for any (S, o) E (ScI, @c1), d(j,
S ONR
NRc, (J) holds for onn equal any finite value.
In any solution that is not in (Scr, der), there is least point which is assigned to center not
in the point's ' own community. Thus for such solution (S, ø), there exist j E C, d(i, S) = R.
Thus for (S, o) & (ScI, Φc1), for some C, there is no finite aNR such that d(j, o()) R < ANR (R).&() ( holds.
This shows that solution that achieves a cewn-fairess for finite oNn must be solution from the set of solutions (Sc1,0c1).
Thus we have shown that any solution that satisfies the fairness in your neighborhood constraint approximately do not assign points to centers not in its original community.
To characterize the set of solutions that satisfy GF with additive ( violation, we consider two cases separately: k is even and k is odd.
Consider the case where k > 2 is even and refer to Figure 5 where we have e = k communities that alternate from red to blue color.
Since the lower and upper proportion bounds are set to for both colors, then to satisfy GF each
cluster should have both red and blue points. There must exists a cluster C, of size |C| 2 n it follows E.
that to satisfy the GF constraints at an additive violation of p. then [Cblue| 2 1 ||C, - p = 2k
n2.
By setting p = मे e for some constant e > O, then we have |Chlle,, [Crud| > 0. This implies that a point need be assigned to a center at distance R > 0 for the solution satisfy GF with additive (2()) violation. Therefore such a solution is not in the solution set that satisfies fairness in your neighborhood.
and similarly we would have Creel| Z II
For value of k that is odd, the example Figure 6. Here instead the last community has the same number of red and blue points. We call the cluster whose center is in the last community Cias-
If |Cisal| * - then there are points assigned to the center of Cinst from other communities incurring cost R 0 or points in the last community are assigned to other centers at distance > 0. In both cases there is at least point assigned to center not in its community. If [Cnst] x then
21

---

in the remaining k communities with total of n points, k centers are chosen. A solution satisfying GF has one cluster C; with least k-1 (n - } points. Then we follow the same argument as in the even l case. That is, to satisfy GF with p additive violation on the C,. n
[Chlue] 2 2. - -
12 2k P. |C 2 26 P, with 2 for some constant > 0, at least Thus such solution is not in the set of solutions
point will be assigned center distance R (ScI, (c1). Thus the set of solutions that satisfies fairness in your neighborhood has no overlap with the set of solutions that satisfies GF with ((E) additive violation.
Lemma For any 2 2, there exist a clustering problem where no feasible solution exists that satisfies both Socially Fair and GF even if we allow additive violation of 32 ( to the GF constraint.
Proof. We follow similar line of argument as in Lemma 4. Consider the case when k: 2 and consider the clustering problem on É-community instance with k = f. We consider the case where lower and upper proportion bound of GF are set for both colors.
Claim 6.
On the above mentioned clustering problem, ass-faair solution in the Socially Fair notion finite Oss is solution in the set of optimal solutions (Sc1, Φc1).
Proof. Denote the clustering cost of an optimal solution to the a Socially Fair clustering problem as SP. By definition,
OPT
min
max
Σ d' ((,)))) JECK
Sk HEH
C*
We can formulate problem that aims to find ass-socially fair solution as constrained opti- mization problem. We use a dummy objective function f. The constraint can be set up as requiring maximum clustering costs across all colors to be upper-bounded by OsF times that of the optimal socially fair solution OPTsF-
The constrained program can be set up as below:
min f S:SIS
s.t. max REH
Σ jECA
d'(j.((f)) OPT
ch
For clustering problem with & centers on the é-community instance with k: = f, in solution (S, Φ) that has one center in each subset, d(j. Φ(j)) = for each point j E C. Thus this solution has clustering cost for each color h Ejecn d' (())= O. Which implies that OPTsF = 0.
Thus on the é-community instance, feasible solutions to the asp-socially fair problem, for finite asF. have maxieH J Ejeco d' Φ(j)) 0. We now show (Scr, Φcτ) is the only of solutions that have max EeEC d(()) = O. Thus, they will be the only feasible solutions.
For any solution (S, Φ) that is not in (Ser, deer), there must be a point assigned to a center that is not in its own community. For such point d(j, x()) R. Thus max Te Σjech d' di Φ(j)) 2
maxkg | Therefore, an oss-faiir solution in the socially fair notion for finite osF must be solution in the set of optimal solutions (Scr, (Scr,der).
At this point, similar to proof of Lemma 4, we had shown that any solution that satisfies socially fair approximately do not assign points centers not in its original community on the E-community instance. The remaining of the proof is the same as that part of the proof in Lemma 4. We can use the same examples for even and odd to show that any solution that satisfies GF with Ω additive violation any k > 2 is not in the set of solutions (Scr, Φcr), ). Thus the set of solutions that satisfies socially fair has no overlap with the set of solutions that satisfies GF with 2 2 additive violation.
D
22

---

Lemma 6. For any k. 2 5, there exist clustering problem where no feasible solution exists that satisfies both Proportional Fairness and GF even if we allow an additive violation of 92 g in the GF constraint.
Proof. For given value of OA for the proportionally fair constraint, consider Figure 8. For the GF constraints, the upper and lower bounds for each color to and the total number of points a is always even. Consider some k 2 5. It follows that the sum of cluster sizes assigned to centers either the right side or the left side would be at least 2. WLOG assume that it is the left side and denote the total number of points assigned clusters on the left size by |Crss and let S1s be the centers on the left side. The total number of points on the left side may not be assigned to a single center but rather distributed among the centers SLS. To satisfy the GF constraints at an additive violation of it follows that the number of red points that have to be assigned to the left side is at least Lies (2) p) 2 4 kp. Set p
n 1, then it follows that least 22 red points
are assigned to a center on the left at a distance of at least R. Since the maximum distance between
any two red points by the triangle inequality is 2r < oAr
it follows that this set of points forms
blocking coalition. Iee., these points would also have lower distance from their assigned center they were instead assigned to red center.
2
:
R
T
= 10 (even)
T
T
2
2
k 7 (odd)
....
<
GAP
Figure 8: Instances to show incompatibility between Proportional Fairness and GF. We always have n/2 blue points on the left and n/2 red points the right. For even & we would have k/2 locations for the blue and red points each. For odd l we have [k/2] blue locations and [k/2] red locations. For each color, there is always location at the center distance from the other locations. Points of different color are at a distance of at least R from each other. For any value of O&A for the proportionally fair constraint, we < 20
We restate the following theorem and give its proof:
Theorem 6.2. For any value k 2 3, the fairness in your neighborhood [30], socially fair [1, 24] and proportionally fair [15] constraints are each incompatible with DS.
Proof. Consider case of the É-community instance where the first e 1 communities consist of " points of only blue points. And the last community contains " points of red points and 2/ points of green color. This é-community instance is illustrated in Figure 7. Consider the clustering problem where k = l and DS constraint hotue, kred, kigren > O. We establish below two claims.
28
Claim 7. On the above mentioned clustering problem, an fair solution the Fairness Your Neighborhood notion for finite ONR is solution in the set of optimal solutions (Sc1, @C1).
23

---

Claim 8. On the above mentioned clustering problem, an ossr-fair solution in the Socially Fair notion for finite Osr is a solution in the set of optimal solutions (Sc1, 9c1).
Those two claims can be proved with the same argument in claim 5 and claim 6.
However, satisfying DS on this with kylue; kiedd Kigrenn > 0 requires center of each color be picked. Thus a solution from the set of optimal solutions (SCI, ΦC1) ) does not satisfy DS because it will only pick one point from the right most subset as a center. Thus either green points or red points will not appear in the set of centers.
On the other hand, since a solution satisfying DS has at least one center of each color, will contain two centers, one green, one red chosen from the right most subset. And there are k 2 centers allocated the 1 communities on the left. By pigeon hole principle, one of the communities of all blue points will have no center allocated. All blue points in this subset are then assigned to a center in a nearby community, thus a DS satisfying solution is not the set (Scr, Φcr). Thus the set of DS satisfying solutions has no overlap with the set of solutions that satisfy either one of the two fairness constraints.
Below we use the same example to show incompatibility between DS and Proportional Fair.
Claim 9. On the above mentioned clustering problem, there is no feasible solution exists that satisfies both Proportional Fairness and DS.
Proof. We show a DS satisfying solution on above example is not proportional fair. As argued above, a solution satisfying DS can allocate k centers for the 1 ccommunities on the left. There will be a community of size " of which all points are assigned to a nearby center not in its community. This community forms a coalition of size " center in their own community. Therefore a DS satisfying solution is not proportional fair.
&
k and would have smaller distance if they get assigned a
For each of the above proofs we constructed an example which is parametric in the number of centers k. Moreover, for these examples for the optimal unconstrained k-center objective to equal 0 at least & centers have to be used. Le., the points are spread over at least & locations. Furthermore, it is not difficult to see in each of the above examples that optimal solution for the unconstrained k-center objective satisfies fairness in your neighborhood, socially fair, and the proportionally fair constraints. In fact, it is easy show that any k-center which has radius of 0 immediately satisfies fairness in your neighborhood, socially fair, and the proportionally fair constraints. However, the same is not true for GF or DS. This indicates that the above distance-based fairness constraints can be aligned with the clustering cost whereas the same cannot be said about GF DS.
Remark:
Compatibility between GF and DS: One can easily show compatibility between GF and DS. Specifically, consider some values for the centers over the colors (ki hew that satisfies the DS constraints, i.e. vh E H kg S k2 & ky and has k K2 S k. Then simply pick set Qn of kn points of color h. Now if we give DIVIDE the entire dataset C and the set of centers UneR Qn as inputs, i.c. call DIVIDE(C, Qn), then by the guarantees of divide each center would be active and each cluster would satisfy the GF constraints at an additive violation of 2.
Our final conclusions about the incompatibility and compatibility of the constrains are summarized in Figure 9.
E Example for Running DIVIDE:
Consider the following example running the DIVIDE subroutine. Specifically, we have set of points
with a total of n = CI = 38 points. We have 3 colors (blue, red, and green) with the following
points: [Cblue| = 15, Crrd = 14, and [Crreea] = We have Q C C' with a total size of 4 (Q) 4). Accordingly, we have Tilue 16 3. Trad = 14
T. 3/. and T green
9 21- Therefore, in the 3
beginning of the iteration for each color h (line (8) in algorithm block 1) we have bplue 3, hes = 2,
bgreca 1. Following the execution of the algorithm, the first three centers q O receive
24

---

DS
GF
Faimess Your Neighborhood
Proportionally Fair
Socially Fair
Figure 9: (In)Compatibility clustering constraints. Red arrows indicate empty feasible set when both constraints are applied, while green arrows indicate non-empty feasibility set when both con- straints are applied.
[Totee] many blue points, the last (q [Q] 1) and first center (g = points, and center y receives [Tgreen] All other assignments would be the floor of Th. Figure 10 illustrates this.
0) receive [Tied many red
[Q| =4
batue =3
Bred
x
Ogreen
Figure 10: Diagram illustrating how DIVIDE would run over the example. The "tape" has different centers (cells) starting from q and ending with g |Q| - 1. We go over the tape for each color h E H. In given row h, centers marked with an X are assigned [7,] points, otherwise they are assigned [Th] points.
Additional Experiments Results
Here we show additional experimental results. As a reminder, the lower and upper proportion bounds for any color h to am 61+r and 9n. (1 - d)r,, for some 8 [0, 1]. Further, the DS constraints are set to kj, [0r,k] where 0 E [0, 1] and k. = le for every color h H.
We call also, run another experiment (B-Adult) over the Adult where we set 5 = 0.05 and 0 = 0.9. Figure 11 shows the new results. We do not see change qualitatively. It is perhaps noteworthy that the DS-Violation values for COLOR-BL.N BLIND and ALG-GF are even higher as well as the GF-Violation for ALG-DS. On the other hand, we find that our algorithms that satisfy GF+DS have very low (almost zero) values for GF-Violation and DS- Violation at a moderate PoF that is comparable to ALG-GF which satisfies only one constraint.
over the Adult dataset in Section 7 as (A-Adult). In that run 5 0.2 and 0 0.8. We
D1
1d
Figure 11: B-Adult results: (a) PoF comparison of algorithms, with BOLORRBBLIND as baseline; (b) GF-Violation comparison; (c) DS-Violation comparison.
25

---

Additionally, we show results over the Census1990 dataset where we age as the color (group) membership attribute. As done in [20] we merge the 9 age groups into 3. Specifically, groups (0, 1, 2] (4 63. and {7, 8} are each merged into one group leading total of 3 groups. Further, we sub- sample 6, 000 records from the dataset. We run two experiments where in the first (A-Census19900
we have d 0.05 and 0 = 0.7 whereas in the second (B-Census 1990) we have å = 0.1 and 0 = 0.8. We also use different cluster values. In terms of the 3 objective measures of PoF, GF-Violation, and DS-Violation, we do not see a qualitative change as can be seen from Figures 12 and 13. Specifically. the DS algoruthim (ALG-DS) DS) has a low PoF but high Vioiiiotnonn. Further, COLOR- BLLDD and ALG-GF have significant Vi-viala values. On the other hand our algorithms for GF+DS have low values for both GF- Violatinn and DS- Violation and a moderate PoF.
[b
[4]
140
Sharrson
00ae/ts voldi
Figure 12: A-Census1999 results: (a) PoF comparison of 5 algorithms, with COLOR- as
baseline; (b) GF- Vio-aiotn comparison; (c) DS- VisViioation comparison.
16
Coor Bedivoatoe
tame celircone
Chedfto
32-
Figure 13: B-Census19990 results: (a) PoF comparison of 5 algorithms, with COLOR-BLIND as
baseline; (b) GF- Vrolatio comparison; (c) Violatiti comparison.
Tun-Time: Here we show some run-time analysis results. We first calculate the "incremental" run time over GF. Specifically, given a solution from the ALG-GF (the algorithm for the GF constraints) we see that the additional run-time to post-process it to satisfy the GF+DS is very small in proportion. We measure fGF->GFDDS over all 4 runs. We see that the additional run time is constantly at least two orders of magnitude smaller than the time required to obtain GF solution. The fact that added run-time is small further encourages decision maker to satisfy the DS constraint given a solution that satisfies GF only.
Time to process GF Solution to satisfy GF+DS and show the results in Figure 14 obtain GF Solyuoon
4200
600
Figure 14: fGF->GF+DS over the runs of (A-Adult), (B-Adult), (A-Census1990), and (B- Census1990).
26

---

If were do the same using the ALGG-DS we find the opposite. Specifically, measure dDs DDSD Time process DS Solution to satisfy GF+DS and find that the additional run-time required to Time to obiaun DS Solation
satisfy GF+DS starting from a DS solution is orders of magnitude higher in comparison to the time required satisfy DS as shown in Figure 15. We conjecture that the reason is that ALG-DS is highly optimized in terms of run-time since it rums in O time [37]. On the other hand, the post-processing step processnnn a DS solution although is done in polynomial time, can be more costly in terms of run time.
GF+DS) requires solving an LP which
(A Coroun1990)
Figure 15: Ins IDS->GF+DS over the 4 runs of (A-Adult), (B-Adult), (A-Census1990), and (B- Census1990).
Finally, we show full run-time comparison between GFTOGFDS which starts from GF solution and DSTOGFDS which starts from a DS solution. We find that the run-times are generally comparable with one algorithm at times being faster than the other.
Figure 16: Full run-time comparison between GFTOGFDS and DSTOGEDS over the 4 runs of (A-Adult), (B-Adult), (A-Census1990), and (B-Census1990),
Our implementation of GF follows Bercea et al. [10] and Bera et al. [9] which would violate the GF constraints by at most 2. Empirically, this may cause issues for the GFTOGFDS algorithm since it requires GF algorithm with zero additive violation and therefore assumes that every cluster has at least one point from each color. However, would not cause issues as long as the resulting solution satisfies condition of having least one point from each color in every cluster which would be the case if min
Using a Bi-Criteria Algorithm as ALG-GF:
3, [/IC.] > 2 where S met, then it reasonable think that
the GF solution and C₂ is its 7th cluster. If the condition the value of h was set too high or that the dataset includes outlier points since the cluster sizes are very small. Furthermore, using GF algorithm with an additive violation of lead final GF+DS having GF violation of at most 4 if the condition is satisified. However, empirically we find the GF violation to be generally smaller than Finally, note that we treat the GF algorithm as a block-box and therefore it can be replaced by other algorithms such as those of [17, 40] which have no violation for GF. In our experiments, we run our algorithms over datasets and value of k where the condition is satisifed.
27


Reviews:
[{"review_id": "am7UZlSacX", "reviewer": "Reviewer_Q947", "summary": "This paper considers two common notions of fairness in clustering: (I) Group Fairness (GF) and, (II) Diversity in Data Selection (DS). The authors show how to boost an approximate algorithm that satisfies only GF/DF to an approximate algorithm that satisfies them both (with constant violations and constant times cost enlargement). Experiments also support the main claims of the paper.\n\nGF and DF are two popular notions to capture group fairness, I am happy to see that actually they can mostly be satisfied simultaneously without paying much effort. I think the results are an interesting addition to the study of fair clustering.", "questions": "1. What is your running time of algorithms in Theorem 4.1 and 4.2? ", "limitations": "The algorithms may violate some groups' fairness constraints in the worst case. Will it be an issue in some cases?", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The first results link different notions of group fairness constraint in clustering.\n\n2. Algorithms are easy to follow.", "weaknesses": "1. The algorithms heavily depend on existing approximate algorithms for clustering with GF or DF. So the result should mostly be regarded as an enhancement of the existing algorithms.\n\n2. The simultaneous guarantees may violate some group constraints. I am worried that in some cases this feature actually contradicts fairness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for making these points. \n\n>  The algorithms heavily depend on existing approximate algorithms for clustering with GF or DF. So the result should mostly be regarded as an enhancement of the existing algorithms.\n\nThere are a collection of technical details which distinguish our work. First, the notion of active centers (forming non-empty clusters) mentioned in Section 4.1 is trivial to satisfy in **DS** and not needed for **GF**. But once both **GF** and **DS** are considered simultaneously it has to be satisfied but is also not trivial to satisfy since the **GF** constraint implies that points of different colors have to be assigned in the correct proportions to the center. Furthermore, our **Divide** subroutine (Section 4.2) is carefully designed to run in linear time (this is not difficult to see but we will add this and emphasize it in the paper).   \n\nFurthermore, since our setting generalizes previously introduced problems, it is perhaps not surprising that it borrows elements from the **GF** and **DS** literature. We consider that to be an advantage since our final algorithm is built in a modular manner which is a much preferable algorithmic design approach. Further, the method of using existing algorithms as subroutines to handle a more complicated variant of the problem appears frequently in the literature. In fact, some **GF** and **DS** algorithms involve a step where an unconstrained (agnostic) clustering algorithm is used as a subroutine and where the output is then post-processed to satisfy **GF** or **DS** (see e.g, Kleindessner et al 2019, Bera et al 2019, Ahmadian 2019, Esmaeili et al 2020). \n\n\n> The simultaneous guarantees may violate some group constraints. I am worried that in some cases this feature actually contradicts fairness.\n\n> The algorithms may violate some groups' fairness constraints in the worst case. Will it be an issue in some cases?\n\nWe note that in many fairness papers the fairness constraint might be slightly violated. Note for example some common notions like envy-free-up-to-1-element (EF1) or near-feasible stable matching with couples (Nguyen and Vohra, 2018) where the violation is at most 4 couples, and stability is the fairness notion.\n\n In our setting we only have a violation for GF but it is always bounded by at most 3 in the worst case. There have been papers for the GF constraint with a similar guarantee. In general, the guarantee is not consequential since a violation of only 3 points is negligible if the size of the cluster is large (consider a cluster of 1,000 points). In fact, if this small violation of 3 points causes an issue, then it would imply that there is a cluster of a very small size. In most practical settings the existence of a very small cluster likely implies that $k$ (number of clusters) was chosen to be too high. Finally, we are not the first to consider such a bounded violation in **GF**, see for example  Bercea et al 2018. Finally, we note that the recent work of Hotegni et al in ICML 2023 has considered violations in **DS** for the $k$-median and means whereas we satisfy them without any violation.\n\n> What is your running time of algorithms in Theorem 4.1 and 4.2?\n\nFor Theorem 4.1, note that it uses an LP based algorithm. In general, when LP based methods are used, papers tend not to mention the exact run-time or simply note that it is polynomial. An issue lies in the fact that the optimal run-time for solving LPs remains a topic of ongoing research. Using a known result by Vaidya et al , 1989 would lead to a run-time of $O((nk)^{2.5})$ using his algorithm. However, we use the Simplex algorithm as done in most settings. While the worst case run-time of the Simplex algorithm is exponential, empirically it is very fast. We note that the impressive run-time of the Simplex algorithm had generated interesting work in beyond the worst case analysis. Please see the work of Spielman and Teng on smoothed analysis. One can get an idea about the run-time of the LP from its size (number of variables and constraints).  \n\nWe will now give a more detailed description about Thorem 4.1’s run-time. In **AssignmentGF** the LP has a total of $nk$ variables with the number of constraints being at most $O(nk)$. The size of the LP is close to or better than some LPs in clustering that can be as large as $O(n^2)$. Note that we use binary search over the values in distance matrix, so we run the LP algorithm $O(log_{}{n})$ which is again standard for the $k$-center problem. Further, the  **MaxFlowGF** algorithm is a special construction of the max flow problem with $|V|=O(n)$ and $|E|=O(nk)$. Using a standard algorithm such as the Ford-Fulkerson or Edmonds-Karp would lead to a run-time of $O(n^2 k)$. We note that this is not slower than previous methods in fair and constrained clustering. The rest of the steps in algorithm 2 are bounded by $O(n)$. Please Appendix F for empirical run-times.   \n\nTheorem 4.2 using algorithm 4 takes $O(n)$ a major ingredient in this fast run-time is our efficient **Divide** subroutine. We will add notes about this in the paper.  \n\n\n"}, {"review_id": "1oM8WWIDRm", "reviewer": "Reviewer_dBjW", "summary": "The paper investigates the relationship and intersection between two constraints for fairness clustering: Group Fair, in which populations should be fairly represented in each cluster, and Diversity Selection, in which centers should be fairly selected. It is shown that a solution for one of the constraints can be post-processed into a solution for the other with a constant degradation in results, but also that both constraints are incompatible with other, distance-based fairness constraints introduced in the literature.", "questions": "-  Do you believe the same results would be replicated for other datasets?\n- What would happen (in terms of guarantees, results, running times) if the constraints must be guaranteed for more than two groups?\n- Were you able to verify the claim in the supplementary material that the overhead in the DS to GF+DS algorithm is due to the necessity of solving an LP?", "limitations": "I believe the running time issues should be discussed in the main body of the paper. If there is space for it, it would be interesting to also expand on the consequences of these constraints not being compatible with distance-based ones.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The theoretical results are very interesting, in terms of showing how it is possible to achieve (with some degradation) both kinds of fairness in clustering but also, and perhaps even more interestingly, when showing how these constraints are incompatible with other fairness settings. ", "weaknesses": "Experimental results are somewhat weak, with a single dataset being analyzed in the main text and an additional one presented in the supplementary material. The running time of the post-processing method to adapt a DS-compliant solution into a GF+DS-compliant one is very high when compared to the running time of the DS algorithm, but this is only mentioned in the supplementary material as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. \n\n> Do you believe the same results would be replicated for other datasets?\n\nWe have run the dataset over a reasonable number of datasets as followed in previous fair clustering papers (see e.g, Kleindessner et al 2019, Esmaeili et al 2021). Furthermore, we have added a third dataset (Diabetes), please see the message above and the attached pdf. \n\n> Run-time issue \n \nBefore we discuss the run-time it is important to note that the **DS** algorithm we use is from the recent publication of Nguyen et al, 2022. The original run-time of **DS** was in fact $O(n^2)$ (see Chen et al, 2016 “Matroid and knapsack center problems”) and was improved to $O(nk)$ recently by Nguyen et al, 2022 for the general **DS** setting. So a contributing factor was the fact that the **DS** the algorithm we use is very fast, hence not representing a bottleneck. Had we used Chen et al, the conclusion would’ve been very different.   \n\nSecond, we would argue that there is not really a run-time issue. Since the constraint involves **GF+DS** we are lower bounded in terms of run-time by the max run-time of **GF** and **DS**. The incremental run-time over the GF algorithm is completely negligible (Figure 14), therefore our final solution is not time-consuming. Further, the final run-times shown in Figure 16 are within what is expected for a solution satisfying GF in the literature. So the time for **DS → DS+GF** is not more than what would be considered reasonable.  \n\nOur new results on the Diabetes dataset show similar conclusions. We cannot think of a reason why the results would not hold over other datasets.  LP based methods tend to be more time consuming than other combinatorial ``non-LP’’ approaches. This is not a general rule since a non-LP method could possibly have $O(n^5)$ run-time. But for example our combinatorial approach for **GF→ GF+DS** is indeed quite efficient and can be shown to run in linear time.\n\nIt is not trivial to satisfy the **GF** for arbitrary bounds through a purely combinatorial approach since the **GF** constraint is in some sense more complicated than **DS** and has to take into account the colors of all of the points in the dataset, not just the selected centers. \n\nPlease also see the last section in the response to reviewer Q947 about the run-time as it may help. \n\n> What would happen (in terms of guarantees, results, running times) if the constraints must be guaranteed for more than two groups?\n\nOur algorithms and theoretical guarantees hold for multiple colors. In Appendix F, the census dataset uses more than two groups. Only in Sections 5 and 6 do we show results on two colors, but these results are impossibility results not guarantees of an algorithm. Could the reviewer please clarify this point since can already accommodate more than two groups? \n\n\n### References: \n\nM. Kleindessner, P. Awasthi, and J. Morgenstern, ‘‘Fair k-center clustering for data summarization,’’ in Proc. Int. Conf. Mach. Learn., 2019, pp. 3448–3457.\n\nS. A. Esmaeili, B. Brubach, A. Srinivasan, and J. P. Dickerson, ‘‘Fair clustering under a bounded cost,’’ 2021, arXiv:2106.07239. \n\nChen, D. Z., Li, J., Liang, H., and Wang, H. Matroid and knapsack center problems. Algorithmica, 75:27–52, 2016.\nNguyen, H. L., Nguyen, T., and Jones, M. Fair range k- center. arXiv preprint arXiv:2207.11337, 2022.\n\n"}, {"review_id": "hD4UoWu0jk", "reviewer": "Reviewer_nxpJ", "summary": "This paper studies how to combine several notions of fairness together in one clustering. Fairness is a popular notion in the context of clustering, however most of previous works had focused on a single notion of fairness at once. This paper studies two specific notions of fairness which are called group fair clustering (GF), and diverse center selection (DF). They give various algorithms that give a constant factor approximation to the k-center problem under the GF+DS constraints (i.e. the clustering has to satisfy both DS and GF constraints). They also study the relationship of these two notions of fairness to other notions that also appear in the literature. More precisely, they show the following.\n\n1)\tFrom a GF fair solution which is a constant factor to the GF problem, one can obtain a constant factor approximation to the GF+DS objective (in polynomial time), assuming a slight violation of the GF constraints.\n2)\tSimilarly, from a DS fair solution which is a constant factor to the DS problem, one can obtain a constant factor approximation to the GF+DS objective (in polynomial time), assuming a slight violation of the GF constraints. \n3)\tIt is also shown that the DS and GF objectives are both incompatible with several other notions of fairness. \n4)\tThey validate their algorithms with experiments.\n", "questions": "Line 2 in pseudocode page 6: the output is stated to satisfy the GF fairness constraint but in fact there is an additive violation. This happens in several other places where the reader first thinks that GF constraint are satisfied exactly without violation. I would encourage to rephrase a little bit.\n\nTypos/minor comments: \nLine 138: extra k in equation\nLine 211: guarantees\n", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think this is a conceptually interesting paper. To the best of my knowledge, this is the first paper that combines different fairness criteria together.", "weaknesses": "Althought the results are nice, the techniques do not seem very novel.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We will fix the typos in lines (138, 211). We will also be explicit about the violation in GF. Furthermore, we believe we presented an elegant solution to the problem and that our modular approach of applying GF or DS algorithms to finally solve both GF+DS can inspire similar future work that considers multiple constraints simultaneously in fair clustering. \n"}, {"review_id": "TJniV5Ujao", "reviewer": "Reviewer_scu4", "summary": "The paper investigates the fair $k$-center problem and considers the combination of two fairness notions: Group Fairness (GF) and Diversity in Center Selection (DS). The authors show that a constant approximation algorithm for one constraint (GF or DS only) can be extended to a constant approximation algorithm for both constraints simultaneously. Moreover, the authors show that both GF and DS are incompatible with a collection of other distance-based fairness notions. ", "questions": "Could you say anything about fair $k$-median/means?", "limitations": "No, the authors should include a discussion on limitations and societal impact.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Due to the importance of fair clustering and multiple fairness notions, it is interesting to study the relationship between different fairness notions.\n- The theoretical results show a separation between DP notions (GF and DS), and distance-based notions, which look interesting to me.\n", "weaknesses": "- The studied objective is fair $k$-center, which is less used in machine learning. The extension of the paper to fair $k$-median and fair $k$-means would be more interesting.\n- It lacks a discussion of the limitations and future works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. \n\n> What about $k$ median and means?\n\nWe would like to note that DS for the k-median and k-means was only solved very recently in the paper “Approximation Algorithms for Fair Range Clustering” which appeared in ICML 2023 (a couple of months ago). Therefore, at the time of the writing the problem seemed premature to fully consider. \n\nWe note that there have been papers in fair clustering focused on a specific clustering objective such as the k-center (please see e.g. Kleindessner et al 2019, Chiplunkar et al 2020, Jones et al 2020, Harb and Lam 2020) so we do not think that this should be seen as a shortcoming especially given the novelty of the problem which for the first time considers multiple fairness constraints simultaneously in clustering. \n\nFurthermore, we have in fact thought about generalizing the current approach to $k$-median and $k$-means as well. One issue is that not all centers would be active (being assigned a non-empty cluster as described in Section 4.1) and at the same time satisfy GF. However, we believe it is a very interesting problem for future work.  \n\n### References:\n\nM. Kleindessner, P. Awasthi, and J. Morgenstern, ‘‘Fair k-center clus- tering for data summarization,’’ in Proc. Int. Conf. Mach. Learn., 2019, pp. 3448–3457. \n\nA. Chiplunkar, S. Kale, and S. N. Ramamoorthy, ‘‘How to solve fair k- center in massive data models,’’ in Proc. Int. Conf. Mach. Learn., 2020, pp. 1877–1886.\n\nM. Jones, H. Nguyen, and T. Nguyen, ‘‘Fair k-centers via maximum matching,’’ in Proc. Int. Conf. Mach. Learn., 2020, pp. 4940–4949.\n\n "}]

Author rebuttal:
We thank the reviewers for their careful reading and constructive criticism. 

## Experiments and Datasets: 
We note that we have tested our algorithms on two datasets from the UCI repository: Adult shown in Section 7 and Census1990 shown in Appendix F. Further, please see the message below with the attached PDF for new results on the UCI Diabetes dataset. We find that the results for Diabetes are similar qualitatively with the  Adult and Census1990. 


## Ethical and Limitation Concerns 
The reviewers have raised important points about the limitations of our work and its societal impact. Following the suggestion of reviewer SpBP, we propose the following draft below to be added to the paper to discuss ethical issues and possible limitations:

``Similar to the vast literature in fair clustering, our work is mainly theoretical. We note that Group Fairness and Diversity in Center Selection are two of the most common fairness formalizations in clustering that operationalize legal doctrine such as the notion of disparate impact. There are other fairness formalizations proposed by the fair machine learning community. However, there is still possibly a gap between fairness notions proposed by the research community and industry practitioners in a particular application (see, e.g. Holstein et al. 2019). And in some cases, the stakeholders and practitioners may not fully discern between fair approaches. The application of our algorithms and their effects in a given application would (as most settings in fairness) be a complicated enterprise which should involve significant investigation into the model and the implications of the algorithms as well as consultation with stakeholders.

It is possible that a naive application of a fair algorithm that does not take sufficient considerations into account would result in possible harm. This is not unique to our setting or even fair clustering in general (see e.g., Liu et al, ICML 2018). As an example for possible harm caused by some of the fairness notions we considered, consider the application of **GF** clustering in a biomedical setting. It is possible that agnostic (color-blind) clustering would show correlations between some clusters and a group membership like race. I.e., some groups might be over and/or under represented in some clusters. Through further analysis this cluster might be discovered to be associated with a bad outcome and therefore some groups might be more susceptible than others to this bad outcome. A decision maker would consider this an important discovery since a certain group is overrepresented in the bad outcome cluster. However, the application of fair clustering would make all groups represented in each cluster in close to population level proportions. Therefore, the application of **GF** clustering might not be suited for such an application. One can devise similar examples for **DS** as well. Furthermore, if the decision maker is certain that only **GF** or **DS** is needed then **GF+DS** would not give an advantage and possibly only degrade the clustering cost“. 

## Additional Experiments on the Diabetes Dataset

We show additional experimental results on the Diabetes dataset from the UCI repository. This dataset was used in Backurs et al ICML 2019 and Chierichetti et al NeurIPS 2017, we take a sample of 20,0000. Note that only use 1,000 points were used in both papers. Similar to what was done in Backurs et al we use ''age'' and  ''time in hospital'' as the numeric entries where the group membership is ''gender'' which has two values in this dataset. Further, we follow a similar setting to that in the experiments section (Section 7 and F). Specifically, for **GF** the lower and upper proportion bounds for any color $h$ is set to $\alpha_h = (1+\delta) r_h$ and $\beta_h = (1-\delta) r_h$ with $\delta =0.05$. Further, for the **DS** constraints we set $k^l_h = \lceil{\theta r_h k}$ where $\theta \in [0,1]$ and $k^u_h=k$ for every color $h$ with $\theta=0.9$. The results are shown in the figures in the PDF. 

Figure 1 shows the **PoF**, **GF-Violation**,and **DS-Violation** similar to previous experiments. We do not see a qualitative change

Figure 2 shows the incremental time. Similar to what we found before the incremental run-time for **GF** is small while it is not for **DS**. 

Finally Figure 3 shows the full runtime for both **GF+DS** algorithms and find like on previous datasets that they are comparable. 





### References:

Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daum ́e III, Miro Dudik, and Hanna Wallach. Improving fairness in machine learning systems: What do industry practitioners need? In Proceedings of the Conference on Human Factors in Computing Systems (CHI), 2019.

Lydia T. Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt. Delayed impact of fair ma- chine learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3150–3158, Stock- holmsma ̈ssan, Stockholm Sweden, 10–15 Jul 2018. PMLR.

Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In International Conference on Machine Learning, pages 405–413, 2019.

Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems, pages 5029–5037, 2017.



Meta-review: This paper considers how to incorporate several notions of fairness into one clustering. The results of the paper were viewed as conceptually interesting and it will be of interest to the community to see how different notions of fairness can be traded off. The technical novelty of the paper was a potential shortcoming, but the results were still interesting.
Decision: Accept (poster)