Fair Clustering Under a Bounded Cost
Authors: Seyed A. Esmaeili
Brian Brubach
Aravind Srinivasan
John P Dickerson
Venue: NeurIPS 2021 Poster (2021)
Keywords: Fairness
Unsupervised Learning
Clustering
Approximation Algorithms

Abstract: Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space. A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness. In this model, the cost of the clustering objective increases due to enforcing fairness in the algorithm. The relative increase in the cost, the ```````''price of fairness,'' can indeed be unbounded. Therefore, in this paper we propose to treat an upper bound on the clustering objective as a constraint on the clustering problem, and to maximize equality of representation subject to it. We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective. We derive fundamental lower bounds on the approximation of the utilitarian and egalitarian objectives and introduce algorithms with provable guarantees for them. For the leximin objective we introduce an effective heuristic algorithm. We further derive impossibility results for other natural fairness objectives. We conclude with experimental results on real-world datasets that demonstrate the validity of our algorithms. 

Fair Clustering Under a Bounded Cost
Seyed Esmaeili University Maryland esmaei 1 liecs. umd. edu
Brian Brubach Wellesley College bb100@wellesley. edu
Aravind Srinivasan
University of Maryland asrinivas @umd edu
John P. Dickerson University of Maryland johnd@umd. edu
Abstract
Clustering is fundamental unsupervised learning problem where dataset is partitioned into clusters that consist of nearby points in a metric space. A recent variant, fair clustering, associates color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness. In this model, the cost of the clustering objective increases due to enforcing fairness in the algorithm. The relative increase in the cost, the "price of fairness," paper we propose to treat an upper bound on the clustering objective as a constraint on the clustering problem, and to maximize equality of representation subject it. We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well the group leximin objective which generalizes the group egalitarian objective. We derive fundamental lower bounds on the approximation of the utilitarian and egalitarian objectives and introduce algorithms with provable guarantees for them. For the leximin objective we introduce an effective heuristic algorithm. We further derive impossibility results for other natural fairness objectives. We conclude with experimental results on real-world datasets that demonstrate the validity of our algorithms.
indeed be unbounded. Therefore, in this
Introduction
Machine learning algorithms are increasingly being applied to settings that directly influence human lives. This has spurred a growing fair machine learning community [9], which develops machine appropriate learning algorithms that are made to satisfy certain fairness criteria. Choosing definition of fairness-and and even deciding if explicitly defining fairness is appropriate to begin with is a morally-laden and ipplicatiionspeciinn rather, we focus on a commonly-used and often legally-backed family fairness fairness-in in the context of clustering, arguably the most fundamental unsupervised learning problem.
decision [28, 43). We make no normative statements here;
recent group-membership fairness definition, called fair clustering in the literature, has received significant interest [20, 10, 11, 2, 31, 22, 8, 3, 33, 1]. In fair clustering, each point has a color that designates its group membership. and clustering objective such as k-median or k-means is given. The goal is to find a clustering that minimizes the objective subject to the constraint that each cluster has each color represented within some pre-specified proportions. For example, there may be two colors, red and blue, and the constraint could require per-color representation between 40% and 60%.
An acknowledged fact in fair clustering- indeed, in many allocation and matching settings is that the fairness (e.g., proportion) constraint could cause degradation in the clustering objective [12, 19]. A point may be assigned to further away center (cluster) satisfy the proportion constraint [20].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The degradation in the objective due to the imposed faireess constraint is called the price of fairness (PoF), mathematically defined as PoF (cost fair solution) (cost of agnostic solution).
Unlike some examples in the literature [12, 21I. the price of fairnsss in the case of fair clustering is unbounded, seen in Figure 1. By enforeing a form of group fairess requiring an even split across colors in each cluster, a fair clustering algorithm would perform arbitrarily poorly as the two groups of points separate in space, while a "color- blind" algorithm would remain unchanged (bottom- left and bottom-right of Figure I, respectively). The possibly unbounded increase in the clustering cost (unbounded price of fairness) indicates that fair clustering can yield clusters consisting of points that are far apart in the metric space instead of combining nearby points- often the main motivation behind clustering in machine learning and data analysis. Furthermore, the legal notion of disparate impact does not force an organization to output fair clustering if it can justify unfair one due to "business necessity," i.e., potential loss in quality [45, 44]. This possible conflict between the clustering objective and the faimnsss constraint indicates the need for fair clustering algorithms that operate in setting where the clustering cost cannot exceed a pre-set upper bound.
Group Fair
Color-blind
Figure 1: Comparison between group fair (left) and color-blind (right) clustering. Un- like color-blind clusters, group fair clusters may combine faraway points (bottom-left).
Our Contributions. In this paper, we address fair clustering under an exogenous threshold on the clustering objective. We formulate the problem mathematically in a general setting that captures all of the traditional k-clustering objectives, i.e. k-center, k-median, and k-means. Throughout, we focus on two general formulations of group fairness: PROUP-UTILITARIAS and GROUP-EGALITARIAN along with the GROUP-LEXIMIN objective which generalizes the traditional GROUP-EGALITARIAY definition. We show that these objectives lead to problems that are NP-hard in general. Further, assuming P + N we derive lower bounds on the additive approximation of any polynomial time algorithm for the GROUP-UTILITARIA bi-criteria approximation algorithms for the GROUP-UTILITARIA UTILITARIAN and GROUP-EGALITARIAN objectives in which the constraint has a bounded violation and the objective is bounded from the optimal value by additive error. For the GROUP-LEXIN heuristic. Further, we consider other possibly more "flexible" fairness objectives, but demonstrate inapproximability results for them. Finally, we test the performance of our algorithms collection of datasets and see that we obtain good solutions with low "fairness violations." " We note that due to the page limit, all proofs are placed in Appendix A.
and GROUP- EGALITARIAN objectives. We provide
objective we provide effective
2 Related Work
The metric clustering problems k-center, k-median, and h--maans are fundamental in unsupervised learning and operations research. All are NP-hard with a long line of research on approximation algorithms. For k-center, two distinct algorithms achieve 2-approximation which is tight assuming P # NP [26, 23, 27]. The current best approximation for k-median a (2.675 apprroxxiiitioon in log(/e)))) time [18], and for k-means, there is a -357-approximmation [4].
The fair clustering problem with group faimess constraints was proposed by [20]. They studied
k-center and k-median in a setting with only two colors. Followup work by [11, 10, 7, 31] gave extensions to the k-means objective, more than two colors, multi-color points (i.e.. intersecting demographic groups), and scalability. Other works by [38, 15, 16] look at non-group- definitions; the former investigates individual fairness, while the latter two address probabilistic fairness guarantees for pairs or communities of points. The aforementioned works optimize the clustering objective subject to fairness constraints; however, satisfying the fairness constraints may come at the expense of significant increase in the clustering objective. Accordingly [48] and very recently [37] explored the cost/faimess tradeoff, but using a multi-objective approach. Unlike our work they do not establish approximation guarantees. Further, the fairness objectives used are different from ours, i.e. in [48] the fairness objective is penalized for proportions that are not precisely equal to the population level while in [37] it is penalized for color ratios that are not equal to 1. Moreover, in [48] the cost/fairness tradeoff is a non-monotone function of a parameter which the user must adjust, while [37] only focuses on the k-means objective and provides convergence guarantees only for smoothed version of the original problem.

---

We focus on the formal tradeoff between fairness and the clustering objective. We note that the clustering objective can be replaced by the price of fairness (PoF). However, in our setting, the results are clearer if we refer to the clustering objective instead of the PoF. Ultimately higher PoF corresponds to weakly higher fair clustering objective and vice versa. In fact, they are multiples of one another: PoF (cost of fair solution) / (cost of agnostic solution). This tradeoff between fairness and efficiency manifested the PoF concept, in operations research by [12] and simultaneously in computer science by [19]. showing general approaches to defining and measuring it. Similar to work, others have adapted PoF as hard constraint in emergency response [30], organ allocation [39], and rideshare [36, 42], and partial constraint in scarce resource allocation for kidney dialysis [29] and organ exchange [40]. We propose a framework for balancing PoF for a traditional "efficient" objective in clustering, which finds application in areas such advertising, network analysis, and data summarization.
3 Preliminaries
In a clustering problem, we are given a set of points C in a metric space. A distance function d(i, ji specifies the distance between each pair of points i,j E C. Furthermore, d is symmetric, non-negative, and satisfies the triangle inequality. Common clustering cost (loss) functions (e.g., k-means or
1/p where l is the number of clusters, S is the set of cluster centers chosen from candidate set of centers S, and 6: C C 5 is an assignment function that assigns points to cluster centers. The value determines the type of clustering, i.e., p o0, 1, and 2 for k-center, k-median, and k-means, respectively.
k-median) can be written as min
(C) = min (Ejee (Ece((i.()))
S:|Sikk.
In fair clustering, each point has a color associated with to indicate its group membership. Specifi- cally, we have function X: C - H where H is the set of possible colors. We denote the set of all points of color h by Ch. The fair clustering problem (FC) [20, 10, 11, 2, 7, 31, 8] to minimize the clustering objective while satisfying additional fairness constraints:
1/P
min S:1SEkK
<E dd d(.(v))))
(1a)
JEC
S.t. VI
3x1C; S 1 Cn|
(lb)
where C; is the set of points in cluster i and C¹ C. is the subset of points in cluster i with color h. 3g, and an are pre-specified lower and upper proportion bounds for color h, respectively. Clearly, 0 < B, S az. < 1.
In "unfair" clustering problems, the assignment function 6 maps points to the nearest center in S, ie., o(j) = argmin.es d(i,,) since this minimizes the objective. However, satisfying the added constraints in fair clustering may cause points to be assigned clusters that are farther away. This motivates the fair assignment problem (FA), in which the set of centers S is given and the objective is to minimize the clustering cost subject to fairness constraints:
1/P
min Σ d' ((())())
(2a)
JEC
S.L. VI E S.E B,IC, S |c+| cn
(2b)
The only difference between the fair assignment (2) and fair clustering (1) problems is that S is not an optimization variable in the fair assignment problem.
4 Fair Clustering Under a Bounded Cost (FCBC)
The fundamental idea of fair clustering under a bounded cost (FCBC) is to minimize a measure of unfaireess subject an upper bound on the clustering cost:
min Unfairness
(3a)
s.t. Clustering Cost < Given upper bound
(3b)
Next, we transform (3a) and (3b) above into clear mathematical optimization problem.
The Constraint (3b): The clustering cost is EjEc dd (())( 1/P Let U denote the exogeneous
upper bound on clustering cost. Then, (3b) becomes (Ejec di ((j,((()) (()))) 1/p S U. Note that for the case of the k-center where p = oc, the constraint reduces to a simpler form, specifically dj E C, d(j. (())) < U.
3

---

The Objective (3a): In prior work, a given clustering is considered fair if for each cluster, the proportions of each color lie within pre-specified lower and upper bounds, i.e.: Vi S, h E 8.IC. c. I onl C; J. However, bounding the clustering cost may make impossible to have a fair feasible solution. Therefore, we instead set a measure of unfairness for each color and try to minimize this measure. Let A,, denote the worst proportional violation across the clusters for color h. Specifically, for a given clustering. An. E [0. 1J is the minimum non-negative value such that:
Vi E S: (3x- AA) s Ic,) S (as + A+)|C;
Clearly, if A,, = O, then color h is within the desired proportion in every cluster. Having set A to be measure of the unfair treatment that group h receives, we are faced with the question of setting the fairness objective, for which there are many reasonable options. We consider two prominent and intuitive fairness objectives [14]:
GROUP-UTILITARIAN = min
EAn- GROUP-EGALITARIAN = min max A AEH
NEW
The PROUP-UTILITARIA objective minimizes the sum of proportional violations for all of the colors, treating all points of specific color single player in game. The GROUP-EGALITARIAN objective minimizes the maximum proportional violation across the colors. We also consider a more generalized version of the the GROUP-LEXTMIT objective minimizes the maximum (worst) violation, but it goes further minimizes the second-wors violation, then the third-wors violation, and so on until no further improvement can be made. We now state the fair clustering under a bounded cost problem (FCBC):
objective, the
objective. Like
GROUP-EGALITARE
min S:18|sk.d
UNFAIRNESS- DEFAIRNESS-OBJECCIVV OBJECTIVE
(5a)
( 1/ SU JEC
s.t.
(5b)
where the UNFAIRNESS OBIEECTVVEEEEE could equal PROUP-UTILITARIAN GROUP- GROUP-EGALITARIIN, GROUP-LEXIMIN. Similar to the fair assignment FA problem (2), we may define the fair assignment under bounded cost (FABC) problem as:
min CERAAIRNESS-OBJJECTI
(6a)
( //0 SU
s.t.
(6b)
JEC
where similarly the optimization is over the assignment function & while the set of centers S is fixed.
5 Hardness of FCBC & FABC
First, we formally state the hardness of the fair clustering FC and the fair assignment FA problems.
Theorem 5.1. The fair clustering FC (1) and fair assignment FA (2) problems are NP-hard.
We now establish the hardness of fair clustering under bounded cost FCBC and fair assignment under a bounded cost FABC. We note that these hardness results follow for all objectives (GROUP- UTILITARIAN, BRAUP-EGALI and
Theorem 5.2. Fair clustering under bounded cost FCBC and fair assignment under bounded cost FABC are NP-hard.
Although we have shown that both the fair clustering and fair assignment problems under bounded cost are NP-hard, the reductions rely on setting the upper bound U to a small enough value, precisely that of the optimal fair clustering cost. It seems reasonable expect both problems transition into being polynomial time solvable the upper bound becomes sufficiently large. We show in Section 8 approximation for fair clustering
that such result is not easy to establish and would lead which is yet to be produced in the fair clustering literature for arbitrary metric spaces and arbitrary lower and upper color proportion bounds.
For a given clustering cost U, there are many clusterings (solutions) of cost not exceeding U. Let St be the set of those solutions, i.e. if (S,, Φ1) E Su, then (S,, Φx) is clustering with cost that does not exceed U. Further, let L, be the size of the smallest non-empty cluster in the clustering (S,, Φ1),
An empty cluster is cluster with no points assigned to it. This could happen if for example the assignment function o does not map any point to given center including the center itself.

---

then we define L(U) to be the size of the smallest cluster across all clusterings of cost not exceeding U. i.e. L(U)= = (S. since Su, S SU.. We can conclude the following fact from the definition of L(U):
L, Clearly. for U/ and U2 such that U2 2 U,. then L(U2) S L(U1)
Fact 5.1. For a given upper bound U, no clustering with cost less than or equal to U can have less than L(U) many points in non-empty cluster.
We show that the quantity L(U) plays fundamental role. In fact, lower bounds the additive approximation" for the proportional violations and fairness objectives are related to LU)) as shown in the following theorem:
Theorem 5.3. For a given instance of the FCBC or FABC problem with an arbitrary upper bound U. unless P = NP no polynomial time algorithm can produce a solution with a cost not exceeding U that satisfies any of the following conditions: (a) The proportional violation of any color h E H is 1
Dn < 8L(Uy. (b) The additive approximation for the GROUP- UTILITARIAN objective is less than [H| BL(U)" (c) The additive approximation for the GROUP-EGALITARII objective is less than SLUU
1
6 Algorithms for FCBC
Our main result for the FCBC problem is the following theorem which follows as direct conse- quence of the guarantees of Theorems 6.2, 6.4, 6.5, 6.6 and 6.7:
Theorem 6.1. For any clustering objective, given a bound U the clustering cost, Algorithm I solves the fair clustering under a bounded cost FCBC problem at a cost of al most U' = (2 + o:U where the approximation ratio of the color-blind clustering algorithm. The additive approximation is | H ((+ BuUgy for the GRRUP-UUTLITARIE objective and e L(U7 for the GROUP-EGALLTARIAN objective.
2
From the theorem above, it is clear that the additive approximation guarantees we have improve when the cost does not permit small clusters. Indeed, in the absence of outlier points and for reasonable values of k, small clusters are unlikely to exist, Further, empirically we verify the smallest cluster size and find that the smallest cluster size 159 points (see Section 9.3). See Appendix C for more discussion.
We now provide our general algorithm for fair clustering under a bounded cost FCBC which we denote by ALG-FCBC(U, SENFAIRNESS-OBJECTVVV the dependence of ALG-FCBC on the given cost upper bound U and the desired UNFAIRNESS- OBJEcTIVE which could either be the PROUP-UTILLTARIAN,GEE SAOAHIANNGGGGOO-EGLLAAAAAAAAAAA EGALITARIAN, or GROUP- LEXIMIN objective.
where we have made explicit reference to
ALG-FCBC(U, SAAAIREESS-OBECCTIVE (see Algorithm 1) involves two steps, in step (1): we color-blind approximation algorithm find the cluster centers S, in step (2): call the algorithm ALG-FABBCIC U", ENFAARRNESS-OBJECCTVV noted that we have fed ALG-FABC the set of centers S from step (1), further the cost upper bound for ALG-FABC is set to U' = (2 + a while the UNFAIRNESS-OBJERR
for the FABC problem. It should be
remains unchanged. We further note that ALG-FABC will have the same clustering objective as ALG-FCBC. e.g. if is given the k-median objective so well ALG-FABC.
Clearly, from algorithm ALG-FCBC the FCBC problem is closely related the FABC problem. In fact, we establish the following general theorem for all clustering objectives: k-center, k-median, and k-means that shows that an algorithm which solves the FABC problem with provable guarantees can be used to solve the FCBC problem with provable guarantees:
Theorem 6.2. For any clustering objective and both the GROUP- UTILITARIAN and GROUP- EGALITARIAN objectives, given an algorithun that solves fair assignment under a bounded cost FABC with additive approximation μ. the fair clustering under bounded cost FCBC problem can be solved with an additive approximation of a and at a cost of at most (2 + a)U,, where a is the approximation ratio of the color-blind clustering algorithm.
2 An algorithm for a minimization problem with additive approximation > 0, returns value for the objective that is most OPT +/ where OPT is the optimal value.
5

---

Algorithm 1 :LLG- UNFAIRNESS-
1: Choose set of centers S by rumning color-blind clustering algorithm of approximation ratio
2: Set U" = (2 + a)U and call ALG-FABC(SSU) U", SHFAIRNESS-OBJECTIO
6.1 Fair Assignment Under Bounded Cost
Algorithm block 2 shows the steps of our algorithm ALG-FABC for the FABC objective. In step (1): we search for the optimal proportional violations given the bound on the clustering cost U using LPs. Having found the near-optimal solution, in step (2): we round the possibly fractional solution to feasible integer solution using netowk flow algorithm. We note that the details of the search done in step (1) depend on the objective, i.e., GROUP-UTILITARRIS or AROOU-EGALITARIAAN
Algorithm 2 ALGG FABC(S, U, CEW.AIRNNNSS-OJEETTVVVE
1: Given the UNFAIRNESS- OBJECTIVE, search for the optimal proportion violation values A at cost upper bound of U using the feasibility I.Ps of (7).
2:
Apply network flow rounding to the LP solution with the optimal value.
3: return the set of centers and the assignment function Φ (resulting from the rounded LP solution).
We note that in fair assignment under bounded cost FABC the set of centers S has already been chosen and the optimization done only over the assignment á of points to centers. We let Tiy be
decision variable that equals 1 if point j is assigned to center E S and O otherwise. Note that the
values of Zij are a way to represent the assignment function Φ. Regardless of the objective that being minimized, the following set of constraints must hold:
Σ 4
d' (i, UP
(7a)
EJEC:
Σ 1,
myj E 10,
(7b)
ES
Vi An E []
(7c)
hh E S. (8, - An)
Σ Ttb m Σ
Jy S (as + Ax)
Σ Tes
(7d)
JECK
SEC
For the k-center problem, the first constraint (7a) is replaced by Vjj E Izg = 0f d(i > U. Note that in the above we have Zij E [0, 1] which is relaxation of T.j {0,1), 1). as the latter would result in an intractable mixed-integer program. With our variables being Tij and A,, it is reasonable to consider convex optimization approach. That is, could choose to minimize the objective GROUP-UTILITARIAN or the objective GROUP-EGALITARE
and the with our set of constraints being (7). objectives, is
Looking the form of the GROUP-UTILITARII not difficult to see that they are linear (and therefore convex) in the parameters Tij and An. however the following theorem shows, the constraint set (7) is not convex. In fact, either of the proportion bounds alone constraint (7d) would lead to a non-convex set. The non-convexity of the constraint set implies that the resulting optimization problem would also be non-convex:
Theorem 6.3. The constraint set (7) is not convex.
Although the constraint set (7) is not convex, if we fix the values of A, then we clearly have a simple feasibility LP with variables Taj- We therefore take approach where for given objective or GRROU-EEGALITARE
we search for the corresponding optimal values of A by running the feasibility LP of (7). Note that with a given set of values for An. we can objectives
obtain the corresponding value for the GROUP-UTILITARIAN or GROUP-EGALLTARIU and therefore the LP does not need an objective: a feasibility check suffices. Further, since we only use non-trivial values for A. E [0, 1]. constraint (7c) can be omitted. Sections 6.1.1 and 6. 1.2 detail how we use the feasibility LPs of (7) to obtain LP solutions that are approximately optimal and GROUP- EGALITARIAN objectives, respectively. Since these resulting LP solutions could contain fractional values, i.e., it is possible to have value Jaj E {0, 1). the approximately optimal LP solution would have to be rounded to an integral solution. This rounding further degrades the approximation, but we show that this degradation is not large and can be bounded. The details of the rounding are shown
(having bounded additive approximation from the optimal) for the

---

in Section 6.1.3. The search algorithms of Sections 6.1.1 and 6.1.2, followed by the rounding of Section 6.1.3, lead an algorithm for FABC.
6.1.1 Search Algorithm for the GROUP- UTILITARIAN Objective
We are searching for the optimal proportional violations 4 E [0, 1] for the GROUP-UTILITARIAN objective. The first step we take is to discretize the space by a parameter (0, For convenience,
we set E = where E Z+. i.c. r is a positive integer. Accordingly, instead of interacting with the continuous interval [o, 1] for the proportional violations, we instead interact with E. {e, 2e, .e,......... ( 1 1}. with E,
_. Therefore, we have set of (+) K| many possibilities
for the proportional violations and we can obtain the optimal solution for the
objective through exhaustive search by checking the feasibility of LP (7) and picking the feasible combination of proportional violations which leads to the smallest value for the GROUP-UTILITE objective, i.e., GROUP- UTILUIARAAAA
ΣnEH An.
The above approach would take O((5))*1) many LP runs. Therefore, we show a faster search that tries instead (( The key to this speed up comes from the fact that for the two-color case, we only need to evaluate ! many possibilities.
Theorem 6.4. For FABC with PROUP-UTILITARIAS objective, can use 0 ((1) LP runs to obtain an LP solution with additive approximation H |e.
-maay
Furthermore, for the important two-color case with symmetric upper and lower bounds show search algorithm that requires only O log } LP runs. The two color case with symmetric upper and lower bounds that where the two colors hi and l22 are present with proportions r1 and r2 in the dataset, and the proportion bounds are set to a; T; + Xe 3, T4 X for i {1,2] 2} and some valid A1, 22 E [0, 1]. The key observation for the two-color symmetric case is that the proportion of one color implies the proportion of the other; hence, we can run binary search over the set E.,
Theorem 6.5. For FABC with two colors, symmetric lower & upper bounds, and the GROUP- UTILITARIAN objective, we can use (l))((t) -many LP runs get solution with an additive approximation of H |e 2e.
6.1.2 Search Algorithm for GROUP-EGALITARIAN and GROUP-LEXIMIN Objectives
For the
objective we follow the same discretization step as for the GROUP-
UTILITARIAN objective. For all colors, their violation An is set to the same value and the optimal solution is found simply by doing binary search over the set E, by running the feasibility LP (7).
Theorem 6.6. For FABC with the GROUP-EGALITARIAN objective, we can use O Olog loog (:))-
many LP runs to get a solution with an additive approximation ef..
We provide heuristic algorithm for the GROUP-LEXIMIN objective; a rough sketch follows. In the first step, it obtains the cannot improve beyond the current optimal violation; if more than one color is found, then one of these colors is randomly picked. The algorithm then looks for the optimal violation for the remaining colors, having the violations of the previous colors fixed. These steps followed until no color can have its proportional violation improved. See Appendix B for the full details.
solution. Then, it proceeds by finding a color that
6.1.3 The Rounding Scheme and ALG- Guarantees
Having obtained the optimal LP solutions for either the PROUP-UTILITARIAS EGALITARIAN objectives, we now round the solutions to integral values at a bounded increase to the additive approximation. To do the rounding, apply the network flow method of [11] (see Ap- pendix E for details), although other rounding methods are applicable. Given the LP solution Tij and its associated proportional violations A,, if we denote the rounded integral solution by Zij and An. then flow rounding guarantees the following: (i) Σx, dP dP(i, (i,s) S Eis ji, (iii) Vh E H. Vi [k] Ejeca 2nj] s
GROUP-
(ii) Vi E [k]: Ejec Zij
$ Ejec Tij S EEEc Miy5
EjEch Tiz S EyEch Nezs

---

Property (i) ensures that the clustering objective will not increase beyond the LP value, and thus, provided the LP cost does not exceed the upper bound on the cost U, the cost of the rounded assignment will not exceed U as well. Property (ii) guarantees that the total number of points assigned to a cluster will not vary by more than point. Property (iii) guarantees that the total number of points of given color assigned to cluster will not vary by more than 1 point. We can use the above properties along with with the lower bound on the size of any cluster L(U) to establish the following theorem:
Theorem 6.7. For the FABC problem, the rounded solution has cost of at most U and an additive
approximation of: (1) [H Tur)) for the GROUP-UTILITARIAN objective and (2) c + riry for
the PRROUP-GGALITARIAS objective.
Recalling the additive approximation lower bounds of Theorem 5.3 for the FABC problem, we see that we obtain a solution for FABC of cost most U with near-optimal additive approximation. Specifically, our additive approximations for the URIUT-UTILITARIA and GROUP-EGALITARIA respectively.
are L(U)
2 H and 2 L(U)
compared to their lower bounds of 8Z(U)
|H| and (L(
A randomized extension. We also briefly mention a randomized rounding algorithm's 's guarantees; the description of this algorithm (which is motivated by an approach of [35]) is detailed in Appendix G. This algorithm efficiently constructs a random vector X with entries Xi, in (0, 1) such that: (a) Properties (ii) and (iii) hold with probability 1, and (b) the expected value ['X equals Ti for all (i. This has three consequences: (b1) the fairness guarantee for each cluster and color become better in expectation: for all h E H and for all i E S: E/EjEC* X.y] indeed lies between
(Bn - -An)( (Ejec miy) and (ag, + An) Ejec m..) (b2) The expected value of the objective function (the left-hand side in (i)) is at most the right-hand side of (i). (b3) Even if we had multiple linear objective functions, they will all be preserved in expectation.
7 Fairness Across the Clusters is not Possible
It is tempting to modify both the GROUP-UTILITARIAN and GROUP-EGALITARIAN (or GROUP- LEXIMIN) objectives to sum across the clusters instead of taking the maximum violation across the clusters. More specifically, we can replace the objectives by the following: GROUP-UTILITARIAN-SUUS which equals Σ A and GROUP-EGALITARIAN-
which
(EH,
equals min max Σ Aj. where Aj, is the violation of color h in cluster i; clearly the previously- NEW kE[k]
considered violation A, is max Ai. It can be seen that such an objective is more flexible For sE(R]
example, the maximum violations might occur in a cluster that cannot be improved within the given bound on the clustering cost, while it may be possible to improve it for other clusters. The original and GROUP-EGALITARIA objectives may bring no improvement in such a situation but their above modifications could. We prove a negative result. Specifically, while we were able to approximate FABC by small additive values for the original objectives (Theorem 6.7), for the new objectives we cannot efficiently approximate the FABC problems within even relatively-large additive approximations:
Theorem 7.1. For FABC, the objectives SAUUU-UTILITAIAN-SSUUE SUM and SUM that sum across the clusters cannot be approximated in polynomial time to within an additive approximation of Onn) where 8 is constant in [0, 1), unless P N.P.
8 Solving the Problem Optimally for a Sarge-Enougle Cost
It seems reasonable assume that when the upper bound on the cost U is large enough, the problem becomes solvable in polynomial time. It is not difficult to devise such guarantees for some special cases. However, in the theorem below we show that an algorithm with such guarantee would imply true approximation for fair clustering. Since fair clustering has remained resistant to a true polynomial tittoiial-tmme approximation for general metric spaces and arbitrary lower- and upper- proportion bounds [13, 8), this suggests that the problem is indeed nontrivial. Furthermore, we also show the converse, i.e., true approximation algorithm for fair clustering would imply an exact algorithm for fair clustering under a bounded cost FCBC.
3 A true approximation algorithm yields a solution that approximates the optimal objective value with no constraint violation, in contrast bi-criteria algorithms which have a bounded violation in the constraints.
8

---

Theorem 8.1. Suppose that there is polynomial time algorithm which can obtain the optimal solution for FCBC for the upper bound of U if 2 a(I) (PT where I is a specific instance of FCBC and cP (I) is the optimal cost of its color-blind clustering. Then we have a true polynomial time approximation algorithm for fair clustering. Further, a true polynomial time a' d'(I) apprrxxixaiin algorithm for fair clustering implies that FCBC can be solved optimally in polynomial time for U 2 a' (I) OPTrc(I).
9 Experiments
We validate our algorithms on datasets from the UCI repository [24]. The results here are for k-means clustering; additional experiments are in Appendix F.
Hardware, Software, and Algorithms: We only use commodity hardware for all experiments with our programs running on Python 3.6. For the color- k-means clustering, we use the k-means+-- algorithm [5] which has approximation ratio of (log k). Our LPs are solved using CPLEX [32]. Scikit-learn [46] is called for subroutines such as k-means + The network-flow rounding is handled using NetworkX [25].
Datasets: We use all 32,561 entries of the Adult dataset [34]. For the Census 1990 dataset [41], because of its large size (over 2 million points) we sub-sample the dataset to range similar to that considered in the fair clustering literature [20, 10]: specifically we use 20,000 data points. We also use the CreditCard dataset [47] which has 30,000 points (results are in Appendix F). For all datasets we use the numeric attributes to assign the coordinates in the space and the distance between any two points is set to the Euclidean distance.
1ct Setting and Measurements: Each color h E H. has proportion rh. i.e., Th TeT We set the upper and lower bounds for each color to or (1 + r)r, and B3 (1 - 8)r, This means that each cluster should have each color with the same proportion as in the population with a possible deviation of 5.
We first do color-blind clustering using the k-means++ algorithm. The clustering cost we obtain from the k-means+++ is a proxy of the lowest possible value of the clustering cost (since the hardness of clustering forbids the calculation of the true optimal value). We gradually increase the upper bound cost from the color-blind cost to higher values and for each choice of the upper bound, we minimize or GROUP- LEXIMIN objectives using our algorithms and record the
either the objective value. For better interpretation. instead of showing the value of the upper bound, we show its ratio to the color-blind clustering, which is the PoF. Further, for all experiments we discretize the space by e = < 0.008.
9.1 GROUP-UTILITARIA Experiments
We use the Adult and Census1990 datasets with self-reported gender (male or female) as the attribute. We note that both datasets explicitly use categorical labels for this socially-complex concept, and acknowledge that this is reductive [17]. Figure/ shows the PoF versus the achieved GROUP- UTILITARIAN objective, with 5 = 0.1. As expected, as the price of faimess increases (higher bound on the cost), we can further minimize the proportional violations. Eventually the GROUP- UTI.ITARIAN objective becomes less than 0.1 and even very close to zero. We also observe that at given cost upper bound, we can achieve lower values for the GROUP-UTHLLTARI objective when the number of clusters (k) is lower.
Adult
Consus
0.30
clusters clusters
0.8
custers dusters
Groug Colg-Uiltannnn Objcavve
025
Utttrrtt Utpeciive
0.8
0.0
0.55
02
8.10
Figure 2: PoF the GROUP-UTILITARIAN objective for the Adult and Census 1990 datasets.

---

9.2 GROUP-EGALITARIAN and GROUP-LEXIMIN Experiments
We again use the Adult and Census 1990 datasets. However, for Adult, we set the fairness attribute to which- in this dataset, and with the same inherent social caveats the categorization of gender-har 5 groups (colors). For Census1990, we set the fairness attribute to age where we have three age groups." We set 8 0.05 and k 10 for Adult and 6 = 0.1 and Figure 3 shows the results of our algorithm. We notice that for some colors smaller violations are harder achieve and we need set the maximum allowable clustering to larger values to reduce their violations.
for Census1990,
Adult
Census
0.04
Proportoral Proprttorllviiae Vilitton
Prosertoral Vitation
0.5
0.03
0.4
0.02
0.1
0.0
1.01
1.02
1.00
1.04
1.05
Figure 3: PoF versus the proportional violation for different groups (each colored graph is a group) in the Adult and Census 1990 datasets.
9.3 Checking the Size of the Smallest Cluster
As mentioned in Section 5 and Theorem 6.1 our approximations are dependent on the size of the smallest cluster in the solution. While not tractable to obtain the value of LUU) for given U, we can still empirically check the size of the smallest cluster in the cost bounded clusterings we obtain. We note that, throughout, we do not impose any lower bound on the cluster size in our algorithm. For the above experiments we considered, we find that the minimum cluster size (across all choices of kt) are as follows: Adult (159 points). Census1999 (171 points). The fact that the size achieving small (accurate) additive approximations
of the smallest cluster is large means that with ncar-optimal objective values and when we obtain large objective value is because of how stringent the cost upper bound is.
Acknowledgments. Seyed Esmaeili and John Dickerson were supported in part by NSF CAREER Award ASS-1846237, NSF D-ISN Award #2039862, NSF Award CCF-1852352, NIH ROI Award RMM-01009-001 3039-01, NIST MSE Award #20126334, DARPA GARD #HR001 12020007, DoD WHS Award #HQ003420F0033, and a Google Faculty Research award. Aravind Srinivasan was supported in part by NSF awards 174964 and CCF-1918749, as well as research awards from Adobe, Amazon, and Google. We thank the anonymous reviewers for helpful feedback.
NLM-01
References
[1] S. Ahmadian, A. Epasto. M. Knittel, R. Kumar, M. Mahdian, B. Moseley, P. Pham, S. Vassil- vtiskii, and Y. Wang. Fair hierarchical clustering. arXiv preprint arXiv:2006.1023 10221, 2020.
[2] S. Ahmadian, Epasto, R. Kumar, and M. Mahdian. Clustering without over-represennatioo. In International Conference on Knowledge Discovery & Data Mining (KDD), 2019.
[3] S. Ahmadian, A. Epasto, R. Kumar, and M. Mahdian. Fair correlation clustering, In International Conference on Artificial Intelligence and Statistics, pages 4195-420S PMLR, 2020.
[4] Ahmadian, A. Norouzi-Fart O. Svensson, and J. Ward. Better guarantees for k-means and cuclidean k-median by primal-dual algorithms. SIAM Journal on Computing, (0):FOCS17-97, 2019.
'Census1990 actually has age groups. For better interpretability of the results, we merge nearby groups (0, 1, (3, 4,5), 5). and (7, 8) form groups
10

---

[5] D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1027-1035, 2007.
[6] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal computing, 33(3):544- 562, 2004.
[7] A. Backurs, P. Indyk, K. Onak, B. Schieber, A. Vakilian, and T. Wagner. Scalable fair clustering.
In International Conference on Machine Learning (ICML), pages 405-413, 2019.
[8] S. Bandyapadhyay, F, V. Fomin, and K. Simonov. On coresets for fair clustering in metric and euclidean spaces and their applications. arXiv preprint 2Xiv:2007.101377 2020.
[9] S. Barocas, M. Hardt, and A. Narayanan. Fairness and Machine Learning. fairmlbook.org. 2019. http://w/pee http://www.fairmlllm foormbboooo.ooooooooooooooooooo. org.
[10] S. K. Bera, D. Chakrabarty, and M. Negahbani. Fair algorithms for clustering, In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[11] I. O. Bercea, M. GroB, S. Khuller, A. Kumar, C. Rösner, D. R. Schmidt, and M. Schmidt. On the cost of essentially fair clusterings. In International Conference on Approximation Algorithmss for Combinatorial Optimization Problems (APPROX-RANDOM) 2019.
[12] D. Bertsimas, V. F. Farias, and N. Trichakis. The price of fairesss. Operations Research, 59(1):17-31, 2011.
[13] M. Böhm, A. Fazzone, S. Leonardi, and C. Schwiegelshohn. Fair clustering with multiple colors. arXiv preprint EXXiv:0022.07822 2020.
[14] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia. Handbook of computational social choice. Cambridge University Press, 2016.
[15] B. Brubach, D. Chakrabarti, J. P. Dickerson, S. Khuller, A. Srinivasan, and L. Tsepenekas. pairwise fair and community preserving approach k-center clustering, In International Conference on Machine Learning (ICML), 2020.
[16] B. Brubach, D. Chakrabarti, J. P. Dickerson, A. Srinivasan, and L. Tsepenekas. Fairness, semi- supervised learning, and more: A general framework for clustering with stochastic pairwise constraints. AAAI Conference on Artificial Intelligence (AAAI), 2021.
[17] Buolamwini and Gebru, Gender shades: Intersectional accuracy disparities in commercial gender classification. In ACM Conference Fairness, Accountability, and Transparency (ACM FAceT), pages 77-91, 2018.
[18] J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan, and K. Trinh. An improved approximation for k-median, and positive correlation budgeted optimization. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 737-756. SIAM, 2014.
[19] Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. The efficiency of fair division. International Workshop on Internet and Network Economics (WINE), 2009.
[20] Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems (NeurIPS), pages 5029-5037, 2017.
[21] J. Dickerson, A. D. Procaccia, and T. Sandholm. Price of faimess in kidney exchange. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1013-1020, 2014.
[22] A. Esmacili, B. Brubach, L. Tsepenekas, and J. Dickerson. Probabilistic fair clustering, In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[23] T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 1985.

---

[24] G. Gunduz and E. Fokoue. Uci machine learning repository. Irvine, CA: University of California. School of Information and Computer Science. 20, 2013.
[25] A. Hagberg, D. Schult, P. Swart, D. Conway, L. Séguin-Charbomeeau, C. Ellison, B. Ed- wards, and J. Torrents. Networkx. high productivity software for complex networks. http://wwwwwook...g.u..... 2013.
[26] D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res., May 1985.
[27] D. S. Hochbaum and D. B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. ACM, May 1986.
[28] K. Holstein, J. Wortman Vaughan, H. Daumé III, M. Dudik, and H. Wallach, Improving faimess in machine learning systems: What do industry practitioners need? In ACM Conference on Human Factors in Computing Systems (CHI), pages 1-16, 2019.
[29] N. Hooker and H. Williams. Combining equity and utilitarianism in a mathematical programming model. Management Science, 188-11362,, 2012.
[30] K. Huang, Y. Jiang, Y. Yuan, and L. Zhao. Modeling multiple humanitarian objectives in emergency response to large-scale disasters. Transportation Research Part E: Logistics and Transportation Review, 75:1-17, 2015.
[31] L. Huang, S. Jiang, and N. Vishnoi. Coresets for clustering with fairness constraints. In Advances in Neural Information Processing Systems (NeurIPS), pages 7587-7598. Curran Associates, Inc., 2019.
[32] IBM. IBM CPLEX user's manual, version 12 release 7. IBM ILOG CPLEX Optimization, 2016.
[33] M. Kleindessner, S. Samadi, Awasthi, and Morgenstemn Guarantees for spectral clustering with fairness constraints. In International Conference on Machine Learning, pages 8458-3467. PMLR, 2019.
[34] R. Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pages 402-207, 1996.
[35] V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. A unified approach to scheduling on unrelated parallel machines. ACM, 56 2009.
[36] N. S. Lesmana, X. Zhang, and X. Bei. Balancing efficiency and fairness in on-demand ridesourcing. In Advances in Neural Information Processing Systems (NeurIPS), pages 5310- 5320, 2019.
[37] S. Liu and L. N. Vicente. A stochastic alternating balance k-means algorithm for fair clustering. arXiv preprint wrXiv:2105.14177 2021.
[38] S. Mahabadi and A. Vakilian. (individual) fairness for k-clustering. In International Conference on Machine Learning (ICMI.), 2020.
[39] N. Mattei, A. Saffidine, and T. Walsh. Fairness in deceased organ matching. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society (AIES), pages 236-242, 2018
[40] D. McElfresh and J. P. Dickerson, Balancing lexicographic fairness and a utilitarian objective with application to kidney exchange. In AAAI Conference on Artificial Intelligence (AAAI), 2018.
[41] C. Meek, B. Thiesson, and D. Heckerman. The learning- sampling method applied to model-based clustering. Journal of Machine Learning Research, 2(Feb):397-418, 2002.
[42] V. Nanda, P. Xu, K. A. Sankararaman, J. P. Dickerson, and A. Srinivasan. Balancing the tradeoff between profit and faimess in rideshare platforms during high-demand hours. AAA/ Conference Artificial Intelligence (AAAI), 2020.
12

---

[43] D. Saha, C. Schumann, D. C. McElffesh, J. P. Dickerson, M. L. Mazurek, and M. C. Tschantz. Measuring non-expee non-expert comprehension of machine learning fairness metries, In Proceedings of the International Conference on Machine Learning (ICML.. 2020.
[44] Supreme Court of the United States. 13-1371 - Texas Department of Housing and Community Affairs v. The Inclusive Communities Project, Inc., Jan. 2015.
[45] United States Senate. S. 1745 102nd Congress: Civil Rights Act of 199, 1991.
http:::/www.govteee
us/ httpe/sss/billll1//////////
[46] G. Varoquaux, Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, et al. Scikit-leamn Machine learning in python. Mach Learn Res, 12:2825-2830, 2011.
[47] I.-C. Yeh and C.-h. Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2):2473- 2480, 2009.
[48] I. M. Ziko, E. Granger, J. Yuan, and B. Ayed. Variational fair clustering. In AAAI Conference on Artificial Intelligence (AAAI), 2021.
13


Reviews:
[{"review_id": "bWJDecmT9-K", "reviewer": "Reviewer_aWDm", "summary": "This paper derives the theoretical bound of fair clustering based on porotype based algorithms. Generally speaking, the authors expect to minimize the unfairness under the given upper bound. In this paper, the authors consider two types of fairness and two fairness clustering setting. Based on this, the authors derive the upper bound of the unfairness and design the corresponding algorithm. The major contributions of this paper lie in theoretical analysis. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Here are my detailed comments.\n\n1. The authors expect to provide a comprehensive understanding on the research problem with different objective functions and different porotype clustering algorithms. In the current version, there are two research problems and three objective functions. The authors elaborate the whole paper in a parallel way. Unfortunately, it makes this paper messy and difficult to follow. I suggest the authors to only focus on the simplest scenario, and first provide the complete procedure from problem definition to bound cost to algorithm. Then, other scenarios can be delivered as extensions. \n2. Figure 1 is not easy to understand. I read this part for more than three times. Maybe only the bottom example?\n3. I was wondering for several days whether the problem addressed in this paper is meaningful. In Paper \"Fair Algorithms for Clustering\", they minimize the clustering cost with fairness constraints, while the authors of this paper formulate the problem to minimize the unfairness under the clustering cost. It seems that these two settings should achieve the similar results. However, the problem in this paper might impractical and even inflexible. I have two points on this.  (a) cluster analysis is an unsupervised task, the clustering cost is not a focused measurement due to its unachievable OPT; therefore it is difficult to set the upper bound. The authors introduce the concept of PoF, where k-means++ is used as a proxy of the lowest possible value of the clustering cost. What does PoF=1.1 mean in practical? (b) Although the authors introduce \\delta_h to relax the original optimization problems in Eq. (1) or (2), there still exists the empty solution. In light of this, I would like to support the setting that minimizes the clustering cost with fairness constraints, rather than the one of this paper. For this point, I need to discuss with other reviewers.\n4. The presentation is a little messy. Theorem 6.1 talks about Algorithm 1, while Algorithm 1 comes behind Theorem 6.1.\n5. In Line 197, what does the \"small\" mean?\n6. I am confused on ALG-FCBC. According to its formulation, the set of centers S are not fixed, which should be optimized during the clustering procedure. However, ALG-FCBC first calls a color-blind clustering algorithm to obtain S, and keeps S unchanged.\n7. The essence of ALG-FABC is multiple LPs. In my eyes, the solution is almost brute-force. The authors do not provide the time complexity analysis. \n8. This paper focuses on theoretical analysis. Moreover, these theorems cannot be verified by experiments. The experimental section can be removed. Instead, a conclusive section is needed.\n\nWith the below discussion with authors, my major concern on problem setting is addressed and I would like to increase my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the checklist, the authors confirm that they include the limitations and societal impact in the main paper. I do not find them in both main paper and supplementary document.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns on this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}, {"review_id": "SU6fEp2Fg8b", "reviewer": "Reviewer_cQa8", "summary": "The paper studies the fair clustering (with balanced clusters requirement) and the goal of authors is to achieve the “fairest” possible clustering achievable with cost at most U. The idea here is that we know that PoF can be unbounded, and it is unrealistic to assume that in practical applications we cannot sacrifice the clustering quality for fairness with no limit.\nAn important component is how to measure the amount of unfairness and then the goal is to minimize it while not violating the upper bound on affordable clustering cost. They have defined three notions called GROUP-UTILITARIAN, GROUP-EGALITARIAN and GROUP-LEXIMIN. Basically, in fair clustering, for each color h, we are given lower and upper bounds $\\alpha_h, \\beta_h$ and the goal is to guarantee that in each cluster the number of point from color h is at least $\\alpha_h \\cdot  |C_i|$ and is at most $\\beta_h \\cdot |C_i|$. Now, the amount of unfairness is defined by a new set of parameters $\\Delta_h$ such that instead of satisfying the fair clustering requirements exactly, we have that the number of points from color h is at least $(\\alpha_h - \\Delta_h) \\cdot  |C_i|$ and is at most $(\\beta_h + \\Delta_h) \\cdot |C_i|$. The authors consider $\\min \\max_h \\Delta_h$ and $\\min sum_h \\Delta_h$ objectives (GROUP-LEXIMIN is a lexicographical minimizing of \\Delta_h: the top priority is to minimize the min value, then among those with the same min value, minimize the second min value and so on).\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theoretical guarantees of the paper are for both fair clustering with bounded cost and the fair assignment under bounded cost (i.e., a set of centers is given, and the goal is to find the best possible fair assignment under bounded cost). Both problems are NP-hard. Further they showed that the violation (which is a function of $\\Delta_h$) cannot be set to arbitrarily small values (the values depend on the size of smallest non-empty cluster across all clusterings of bounded cost); otherwise, the problem becomes NP-hard (the actual bounds are given in Thm 5.3). \nOn the algorithmic side, they provide a (semi-)bicriteria approximation for fair clustering under bounded cost: the algorithm finds a solution of cost at most $(2+ \\gamma) OPT$ (where $\\gamma$ is the approximation factor for the used color-blind clustering algorithm) with almost additive approximation optimal w.r.t. $(2+ \\gamma) OPT$ and the bounds given in Thm 5.3. The approach is via a reduction from the fair algorithms under bounded cost.\n\n**Questions for Authors**\n1)\tDo you have any evidence showing the bound of Thm 6.1 is reasonable? L(U’) can be arbitrarily smaller than L(U). Do you have any evidence that such dependence is required? I would like to get a sense how tights your approach is.\n\n**Minor Comments**\n1.\tIn abstract: “price of fairness,” -> “price of fairness”,\n2.\tTheorem 6.1 is not mentioning the exponential dependence on \\eps in the running time. Alternatively, you can mention the number of colors is a constant.\n3.\tLine 198. Providing 159 without mentioning the other parameter in the dataset (e.g., number of points, centers) may not be very helpful.\n4.\tLine 203. A space is needed after GROUP-UTILITARIAN,\n5.\tLine 225. Netwok -> network\n6.\tLine 340 and 341 does not seem very informative. Also reference [8] does not provide any such evidence for fair clustering. Maybe you meant the result of [10]?\n7.\tIn section 9.3, it is not clear how you are computing L(U)? Ho do you consider all possible clustering of certain bound (even approximately)? Would be helpful to elaborate more here.\n8.\tIn the second line of the equation after line 732, \\phi(i) -> \\phi(j)\n9.\tRephrase line 735\n10.\tLine 750. Isn’t the proof of Theorem 6.3 trivial? Given that we need to satisfy both upper and lower bound? In fact, why is it important to know the non-convexity for the case we are ignoring the upper bounds? \n11.\tLine 822. theorem Theorem -> Theorem\n12.\tLine 905. Rephrase and fix the typo\n13.\tLine 911. We havewe no -> we have no\n\nThe problem statement and the techniques used in the paper are interesting. The drawback is that it is not clear why the result cannot be (easily) improved. Authors’ feedback on this point can be very helpful for the decision process.\n\n=====================================================\n\nI would like to thank the authors for their helpful response. I will keep my score for this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper works on theoretical foundation of fairness and I do not see any immediate potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Ch9h9NuEViJ", "reviewer": "Reviewer_9wxQ", "summary": "The paper studies a new variant of fair clustering for different fairness (group utilitarian, group egalitarian, group leximen) and clustering objectives(k-center, k-median, k-means). The main approach is to optimize the fairness objective under the constraint that the clustering cost are bounded by some value U. The main result can be thought of as a bi-criteria approximation: If we allow that U is violated by a factor of (2+alpha) (where alpha is the approximation ratio of some clustering algorithm for the given objective) then we can get an additive approximation on the fairness objective. \n\nIn addition to this algorithmic upper bound, the authors also give a number of complexity theory lower bounds for different variants of the problem. \n\nThe authors also provide a proof-of-concept study of their algorithm.\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The newly introduced variant of fair clustering is interesting and the proposed solutions are non-trivial. They provide a nice new approach to the fair clustering literature.\n\nI would have loved to see some more details of the proof of Theorem 6.2 (maybe instead of some of the lower bounds). It seems that this is a central step in the paper and it would be helpful to have additional details in the main body of the paper. Also, how does this theorem relate to earlier fair clustering algorithms (for example, for 2 colors how does it relate to fairlets and similar ideas)?\n\nIn the experimental section there is no comparison to earlier work. I understand that the main results of the paper are the algorithmic/theoretical results and that the problem is somewhat different from the standard problem formulation, but I would still appreciate some comparision.\n\nOverall, I like the paper and I recommend to accept it.\n\n-----------------------------------------------------------------------\nThank you for your feedback. I will keep my score.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6YVTk-3B5rM", "reviewer": "Reviewer_xNaF", "summary": "EDIT: I increased my score following the discussions and rebuttal.\nThe main question in the paper is how can we cluster data so that we optimize for some fairness desiderata. In other words, if we have a target for the amount of clustering cost we are aiming for, how can we find the most fair solution, subject to that cost constraints? Put differently, the authors address the problem of minimizing the amount of \"unfairness\" subject to the clustering cost being below a certain threshold. The two desiderata put forth by the authors in terms of fairness have to do with \"group utilitarian\" objective and with \"group egalitarian\" (they also further study a generalization called \"group leximin\" objective. The authors give both positive results and some impossibility results. Finally, they run some experiments to validate their findings.\n\nThese three objectives are desiderata that have been studied in the past. Briefly, the group utilitarian objective minimizes the sum of all fairness violations, whereas the group egalitarian objective minimizes the maximum fairness violation. Going a step further, the leximin (LM) objective minimizes the maximum fairness violation first, then minimizes the second worst etc. \n\nOne of the hardness results they prove is that for all three objectives, both fairly clustering and fairly assigning points to fixed centers is NP-hard.\n\nOn the positive side, they give an approximation algorithm that yields a (2+a)U-approximation where U is an exogenous parameter that is the upper bound on the clustering cost and a is the approximation ratio of a color-blind clustering algorithm. The algorithms presented for the different objectives depend on some assumptions about the sizes of the clusters. The idea behind the algorithms is to first run a color blind clustering algorithm to select centers, followed by an LP to get a fair assignment and a flow computation.\n\nThe authors perform some computational experiments on the adult and the census data sets to evaluate how their fairness guarantees look like.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The reviewer believes the paper studies an interesting problem which has received a lot of attention recently by both theory and ML communities however the execution brought forth by the authors is done in a manner that has several caveats.\n\nThe reviewer overall is not convinced that the problem formulation itself yields interesting insights and it does feel a bit artificial. There are many prior works on fair clustering recently and to some extent the paper doesn't adequatly compare results: A paper here \"Clustering without over-representation paper\" (Ahmadian et al.) seems to be relevant and one natural question is, whether changing the representation parameters until a solution returned has value smaller than U would yield comparable results?  Could the authors provide experimental evidence to show their method significantly outperfoms prior methods?\n\nRegarding other weaknesses, the paper has an exogenous parameter U for the bound in the clustering cost which is not clear how to get it in practice, and also the Assumption 6.1 makes their main result weaker than one would expect especially in the presence of outliers or misreported values. Can the Assumption 6.1 be removed or will the proof break down completely? What about the analysis of the LP then?\n\nOverall, the theory here could be strong if the final theorems were cleaner but this is not the case. The paper has interesting directions and is currently a collection of small results but further work is needed to have a solid Neurips contribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes new formulations of (and algorithms for) fair clustering. Instead of minimizing clustering cost under fairness constraints, the paper considers a dual problem where the clustering cost is given and the goal is to maximize fairness. 

The reviewers found the formulation of fairness to be interesting and potentially leading to a follow-up line of research. Almost all reviewers recommended acceptance, sometimes strongly so.  At the same time, there was a concern that the approximation factors depend inversely on the cluster size, so they could be large. However, overall, the reviewers felt that the positives outweigh the negatives.

Decision: Accept (Poster)