The Fairness-Quality Tradeoff in Clustering
Authors: Rashida Hakim
Ana-Andreea Stoica
Christos Papadimitriou
Mihalis Yannakakis
Venue: NeurIPS 2024 poster (2024)
Keywords: clustering
algorithmic-fairness
multiobjective-optimization
Primary area: fairness
TL;DR: We propose new algorithms for recovering the Pareto Front of the clustering problem with fairness considerations.

Abstract: Fairness in clustering has been considered extensively in the past; however, the trade-off between the two objectives --- e.g., can we sacrifice just a little in the quality of the clustering to significantly increase fairness, or vice-versa? --- has rarely been addressed. We introduce novel algorithms for tracing the complete trade-off curve, or Pareto front, between quality and fairness in clustering problems; that is, computing all clusterings that are not dominated in both objectives by other clusterings. Unlike previous work that deals with specific objectives for quality and fairness, we deal with all objectives for fairness and quality in two general classes encompassing most of the special cases addressed in previous work. Our algorithm must take exponential time in the worst case as the Parero front itself can be exponential. Even when the Pareto front is polynomial, our algorithm may take exponential time, and we prove that this is inevitable unless P = NP. However, we also present a new polynomial-time algorithm for computing the entire Pareto front when the cluster centers are fixed, and for perhaps the most natural fairness objective: minimizing the sum, over all clusters, of the imbalance between the two groups in each cluster.

The Fairness-Quality Trade-off in Clustering
Rashida Hakim Columbia University
Ana-Andreea Stoica Max Planck Institute for Intelligent Systems, Tübingen
Christos H. Papadimitriou Columbia University
Mihalis Yannakakis Columbia University
Abstract
Fairness in clustering has been considered extensively in the past; however, the trade-off between the two objectives e-g., can we sacrifice just little the quality of the clustering to significantly increase fairness, or vice-versa? - has rarely been addressed. We introduce novel algorithms for tracing the complete trade-off curve, Pareto front, between quality and fairness in clustering problems; that is, computing all clusterings that are not dominated both objectives by other clusterings. Unlike previous work that deals with specific objectives for quality and fairness, we deal with all objectives for fairness and quality in two general classes encompassing most of the special cases addressed in previous work. Our algorithm must take exponential time the worst case as the Pareto front itself be exponential. Even when the Pareto front is polynomial, our algorithm may take exponential time, and we prove that this is inevitable unless P= NP. However, also present
polynomial-time algorithm for computing the entire Pareto front when the cluster centers are fixed, and for fairness objective that minimizes the sum, over all clusters, of the imbalance between the two groups in each cluster.
Introduction
Clustering a fundamental problem in unsupervised learning with many applications, in which data points must be grouped into clusters that the quality cost of the clustering optimized where the cost can be i-median or k-center, among long array of different quality objectives treated the literature. In some of these applications, the data points being clustered are people - for example, when households are clustered to determine the location of bus stop or a hospital - and in those cases considerations such as fairness and equity come into play. In recent work, various frameworks and methods have been proposed for improving the representation of different sensitive groups in clustering, in cases where optimizing for clustering cost alone may be quite unfair. In such works, the fairness criterion is often set as a constraint, for which we must compute the optimal solution. This is generally an intractable computational problem even for the simplest fairness objectives, since clustering on its own is NP-hard. The best one could hope for is an approximate solution based on a vanilla approximation algorithm for clustering that improves fairness; such approaches have indeed been recently proposed, e.g., Esmaeili et al. (26). see Chhabra et al. [18] for survey.
We take more general approach fair clustering: We aim to recover the entire Pareto front of clustering cost and fairness, rather than a single point of that front (such as the best-quality clustering under fairness constraint). Our work aims enable practitioner choose any trade-off point, rather than computing one of them. We give general sufficient conditions for which we can recover the Pareto front, up to an approximation inherited from the clustering problem itself, and encompassing variety of quality and fairness objectives used in the literature.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1 Our Contributions
We present a novel family of algorithms for tracing the Pareto front between quality/cost objective and a fairess objective, where each objective can belong in general class that encompasses most of the ones previously proposed in the literature. Our algorithm requires that the fairnsss objective satisfy an intuitive property: that it is pattern-based. Informally, a fairness objectíve is pattern-based if it is solely a function of the number of nodes of different attributes in each cluster (see Definition ). Many fairness objectives used in the literature are pattern- -ased, from the well-known balance [9 to objectives that measure the proportional violation of pre-specified upper and lower bounds for a 32 22]. For the quality objective, we consider metric-based cost functions. We study the computation of the quality/fairness trade-off in two settings: in the assignment problem, the centers of the clusters are given and the cost is the sum of the distances of the data points from their cluster center; whereas in the clustering problem, determining the centers is part of the problem. We show that our algorithm finds the exact Pareto front of the assignment problem, and an approximation of the Pareto front of the clustering problem (Theorems (3.4 3.5). with an approximation ratio that depends on the baseline approximation ratio (denoted o)) for the minimum
sensitive attribute within cluster [T0 40 2 9 26
cost clustering problem without fairness objective. The running time is O(km"(k-1)) D)), where k is the number of clusters, is the number of sensitive attribute values, and n is the size of the dataset.
Our Pareto front algorithms take time exponential in l and k. and this is necessary. One reason is that the Pareto front may be exponential in size. For many fairness objectives the Pareto front is provably polynomial in size, but even in those cases exponential time is still necessary in general because the baseline problem NP-hard. Importantly, we also present the first nontrivial algorithmic result for the quality/fairness Pareto front problem in clustering: A molynomial-fime algorithm for computing the Pareto front for a new fairness objective, namely the one minimizing the sum (or the maximum), over all clusters, of the deviations from parity of the two protected attributes in each cluster (see Theorem 3.6).
We empirically explore faster methods for computing an approximate Pareto front by adapting constraint optimization methods from fair clustering (26) in Section These experiments explore the trade-off between accuracy and speed for our problem by comparing the tighter approximation obtained through our proposed algorithms with the looser Pareto front approximation obtained using faster methods.
We believe that work is the first to address and carry the computation of the entire Pareto front, and also the first to simultaneously cover a large range of quality and fairness criteria. In comparison, extant literature on fair clustering typically optimizes one objective subject to a constraint on the other objective, with an individualized approach for each combination. Our work is particularly applicable in cases where decision-maker may be willing to be suboptimal in one objective in order to achieve a better value in a second objective, but does not know a priori what bounds to set on either objective. Our algorithms allow them to explore the entire trade-off, from the highest quality clustering all the way down to the fairest clustering. Finally, our polynomial- -ime algorithm for computing the Pareto front when the fairness objective is the sum or maximum of imbalances (see Theorem 3.6 is another novel contribution to the subject of fair clustering.
1.2 Related Work
Our work is inspired by a plethora of recent studies on fair clustering that propose various metrics for improving the representation of different sensitive attributes within clusters. Unsupervised clustering known to be NP-hard even in simple settings 4. A variety of algorithms have been proposed to ap-
proximate the best possible clustering, with approximation ratios differing for different cost objectives (c.g., k-manns [3] k-median [14, k-center (38) Fair clustering goals range from maximizing the worst ratio between two groups across clusters 11), to minimizing the discrepancy between cluster representation and proportional representation of a group a population
T0
22
32
26, 40),
and to equalizing the clustering cost for various groups 77 [5] 31 50
54
62 Many of these
works focus on building specialized approaches for each of the fairness objectives defined, and their objective is to find the best quality clustering that satisfies specified faimess constraint. Optimizing even for simplest fairness objectives can be NP-hard (26), with approximation guarantees involving a multiplicative and additive factor, which may depend on the particular objective form and data topology. Our work differs in two significant ways: first, we compute the entire trade-off curve rather than single optimization point on the curve; second, we provide algorithms that are agnostic

---

to the specific objectives used, giving sufficient conditions on the objectives. We note that our conditions favor most group- objectives defined in the literature. We discuss extensions to other definitions of fairness and limitations of our work in Section 5
Our work takes different approach, by aiming to compute the entire Pareto front between seemingly opposing objectives. Knowing the entire Pareto front can aid decision-makers when faced with choosing optimal trade-offs. Many real-world applications are faced with such trade-offss: for example, in facility location problems where a central agent decides on the location of facilities (e.g.. buses, hospitals, etc.) based on the location of individuals within a certain region. It is well-known that people of lower socio- economic status often travel longer distances [57] and have fewer health facilities in their region [2)]. A decision maker has multiple objectives to balance: minimal travel time for the entire population and equal access to facilities for different populations. The Pareto front allows the decision maker to balance these objectives in the optimal way: how much improvement can group of people gain by moving facility slightly away from the solution given by a single objective (e.g., by performing k-means)? Computing the Pareto front for facility location problems with multiple objectives has long history motivated by such questions, with real-world case studies in the Singapore road network [39] and ambulance placement in Barbados [35] Further applications
are found in extensive surveys 28
From a theoretical standpoint, computing the entire Pareto front remains difficult problem. When an underlying Lingl-objecctive optimization problem is NP-hard, such as in many combinatorial optimization problems, computing an approximation for the Pareto front is the best one could hope for 55 for example for the multi-objective shortest path problem [1
64] zero one knapsack problem (25 42 (3), the multi-objective spanning tree problem g 21 55 among others. To our
36
44
knowledge, our work is novel in proposing algorithms for solving a bi-objective optimization problem based on clustering and fairness objectives which require only general properties for the fairness objectives to recover approximate Pareto front with theoretical guarantees.
More generally, multi-objective optimization has seen variety of methods for computing points close to the Pareto front in various domains, with methods ranging from evolutionary
algorithms 220 56
61
65 to gradient-basee
methods [12 47 49 [I], and more recently to 60] (often requiring inputting a preference vector of the objective values
hypemeetorks 66 37
48
that will output point on the Pareto front). These methods have also been applied to a problem
closely related to clustering: that of facility location with multiple objectives (34 58 59 considering
specific objectives and without theoretical approximation guarantees.
2 Preliminaries
We denote by X' the set of data points in Rd. Assume that X' = "eri...,,TJ] and for j S define X; = (xi,...,,r,)) A clustering map is defined as Φ : X + 5, where a set of l cluster centers in IRd and ie the number of clusters, considered fixed. cluster C, is defined as all the data points for which ((x)= 8t, where 8; E S is the center for the i-th cluster. We call clustering C the set of all clusters C; (so |C| k), and by the set all possible clusterings. Finally, we denote by X [!] the map between data points and set of sensitive attributes, indexed from 1 to / (which may represent demographic groups, interest groups etc). We denote by Ca the set of data points in cluster C' with attribute a, and by x the set of data points with attribute
Clustering and Assignment Problems. Unsupervised clustering optimizes clustering cost objec- tive c, often defined as the sum of distances between points and a set of candidate cluster centers. In a general form, the cost of a clustering is (Eaşx dl (z, ((x))) 1/p for metric d and some value of p. We call such objectives metric-based. By varying = 1,2, co we can obtain the k-median, k- k-means, and k-center objectives, respectively. The clustering problem is thus finding the clustering that has the minimum cost, over all possible sets of centers and maps from X' to the set of centers. Since the clustering problem hard, one often considers, as a stepping stone, the assignment problem, where the centers have been fixed. We shall consider both problems in this paper. In the fair clustering problem we have two objectives, the clustering cost objective e, and a fairness objective f, that aims to balance the representation of sensitive attributes in clusters, further detailed below.
3

---

Pareto Front. Consider the set of all clusterings I. of X, and the two objectives e (the cost objective) and f (the faimess objectivd each mapping K to R. We say that clustering dominates clustering C' if c(C) I c(C"). ((C) SC"), and one of the inequalities is strict. Intuitively, if clustering C' is dominated, it unworthy of further consideration, because it lags behind in both objectives of interest. If however a clustering C is undominated, that is, there is no clustering in K. that is simultancously better on both fronts, then it is part of the solution. The Pareto front is the set of all undominated clusterings.
Fairness Objectives. Our main contribution is an algorithm for computing the Pareto front of the clustering and assignment problems for any metric-based quality function, and any fairness objective always function to be minimized- that satisfies the following general condition.
Definition 2.1 (Pattem-baseed objectives). For a clustering C E K. i E [k:]. and a E [1], let its pattern po [1, a] be the number of data points in cluster C; with attribute value a. A faireess objective f that maps K. to called pattern-
if f(C) only depends on the values in [t.
Definition 2.2 (Mergeable objectives). Consider two clusterings C' and C². We say that C' is the result of a merging of C (or C is refinement of C') if every non-empty cluster of C' is the union of clusters of C. A fairness objective f that maps K. to IR is called mergeable if, whenever C' is the result of merging of C, f(C") S f(C).
We discuss the pattern- and mergeability properties in Appendix B where we give examples of fairness objectives that are not pattern-base or mergeable. Below, we introduce several fairness objectives commonly found in the literature, which we use in our experiments. All of these objectives are pattern-basee and mergeable, as proved formally in Appendix B.1]
Balance objective (Definition in Chierichetti et al. [T]]): For sensitive attributes that can take two values, indexed and 2, the balance of a cluster C' is defined as BALANCE(C) = The balance objective for a clustering C is then defined as
min
BALANCH(C) max BALANCE(C) CEC
(1)
The aim is to maximize balance, equivalently. to minimize the negative balance F(C) = BALANCC((). BALANCE has been used in fair clustering as a measure of equalizing proportions of different groups across clusters [99. In practice, optimizing BALANCE is both difficult and does not measure how far the proportions of sensitive groups in clustering are from their true proportions in the population. For this reason, objectives based on proportional violation have been proposed, allowing a central decision-male maker to input upper and lower bounds for desired proportions of groups in each cluster, and measured the deviation from these bounds 2 9 10 22
26 32 40).
Proportional violation objectives: As defined in Esmaeili et 26), for every sensitive attribute E [1]. define upper and lower bounds aa and 3g with the aim of satisfying Ba|CI < |C*| < oa C|
for all clusters C' E C. Since this is not always feasible, we define the worst proportional violation of attribute in cluster C' as the minimum non-negative value A E [0, 1] such that
(3. - A |C| s |Ca9 < (a. + 44) Then, the proportional violation-based objectives are defined as:
(2)
GROUP UTILITARIAN min
Σ
max AC CEC
GROUP UTILITARIAN-SUM min
Σ
AC
aEl[]
aE(1)CEC
(3)
GROUP EGALITARIAN = min max
AC aEL
GROUP EGALITARIAN-SUM = min max
C
&El()
CEC
These objective operationalize utilitarian and egalitarian concepts from social choice
13
minimizing
either the sum of proportional violations or the worst violation across attributes.
Sum of imbalances objective: Finally, for two interest groups in the population (1= (2 the following objective is quite natural:
SUM OF IMBALANCES
Σ
-
RE
We will treat f as minimization objective, thus minimizing the unfairness of clustering.

---

that is to say, the sum of the deviations from equality between the two attribute values in the clusters. This objective is most appropriate when datasets contain relatively equal proportions of the two groups. Rather remarkably, the Pareto front for this objective can be computed in polynomial time.
3 Algorithms for Computing the Pareto Front
3.1 A Dynamic Programming Algorithm for Recovering the Assignment Pareto Front
We shall now present the main Algorithm. Define an X' X'pattern P to be a k-tuple of 1-tuples of non- negative integers such that Zxe(k] P(i, a) | Va [7]. Pli, a) specifies the number of data points in cluster i of attribute That is, d'-pattern is a clustering except only the attribute values of the points have been specified Complete proofs to subsequent results can be found in Appendix
Algorithm Dynamic Programming Algorithm for Computing the Assignment Pareto Front
Input: Number of clusters k, a of n data points X' with / attribute values, centers S {s1...., s J, and metric-based cost objective parameterized by d.
2: Output: A table T, containing the solutions of the assignment problem for X' for all X' X'-pateens.
3: Method: Dynamic programming. We shall compute To. ......Ty
4: Initialize To to contain the null pattern with cost and the empty clustering.
5: for
to do
6: Generate all X -yttpttesss, where X; (-.1....,,.)) ..
7: For each X' Xy-pattern P. and for each cluster i such that Pli, a] >> O, where is the attribute value of zy, look up in - the cost of the pattern P., which is with æj omitted from cluster i, and compute - (P,) + dl (I). 8:).
8:
9:
10:
Let i* be the cluster index that minimizes (P;) + (I(),
11: Set (P)
TP: d'' (z), 8.,)
12: Store at T, (P) the clustering from ][,,,), with 2, added at cluster i"
return T.
At the conclusion of the algorithm, the table T, contains the lowest cost clustering C for each X' X'-pattem P. such that pa = P, together with its cost c(C). Then, we can find the Pareto front by first sorting these clusterings for all X' T-patterss P in increasing c, and then traversing them in order, computing the unfairness of each pattem, remembering the smallest unfairness we have seen so far, and omitting any pattern that has unfairness larger than the smallest seen so far.
Remark 3.1. The above calculation of Tn can be achieved alternatively by simpler to state but slightly slower algorithm: first generate all X X-patterns, and then compute the optimum assignment of each by min-cost flow.
Theorem 3.2. Algorithu finds the Pareto front of the assignment problem in time O(kn'(k-1)) for any metric-based clustering objective and any pattern-hased fairness objective.
We prove this theorem by finding an invariant of Algorithm ! Tr [P] stores the lowest cost assignment of X, that maps to pattern P. We maintain this invariant as we build up our table by searching over possible smaller patterns that we can add our next datapoint x, to and creating the lowest cost assignment that maps to P. Therefore, the assignments stored at T, (P) are the candidate points for the Pareto front. A simple filtering heuristic, as described above, removes the dominated points from this set of candidates. In terms of running time, the number of possible patterns of total size up to n is upper bounded by n (k-1), since each of the Ik entries of P takes values between 0 and n. and the tuple corresponding to the last cluster k is fully determined by the other clusters.
Proof Sketch:
For each considered pattern, we need to look up at most k previous entries of the table T..
3.2 Approximating the Pareto Front for the Clustering Problem
As we saw, Algorithm| | computes the Pareto front of the Assignment problem exactly for any input centers S. We next show that it also provides approximation for the Pareto front of the clustering problem. For this purpose, we first use a vanilla clustering algorithm A for the single-objective
Fach clustering C maps pattern Pe, with many different clusterings mapping the same pattern.
5

---

problem of minimizing the cost e, to obtain the set S of cluster centers, and then apply Algorithm ! with this set of centers S. Let a be the approximation ratio of algorithm A.
Definition 3.3 (W-approximation of the Pareto Set for clustering). For parameters W (we, wyy we define the W-approximation of the Pareto set Xp as a set of feasible points Xy, such that Vr E Xp, Drd E X such that c(x') S w. - c(x) and fxx) S Wy f(x).
This definition is a direct generalization of e-approximate Pareto set defined by Papadimitriou and Yannakakis [55]. One may recover the e-approximate definition by setting e = max wy)
Theorem 3.4. Algorithm D finds (2 + a, -)ppproxiimaiion of the Pareto set of the clustering natter-based based and mergeable fairness objective f.
problem with a metric-based cost objective e and a pattern
Proof Sketch: We argue that for any clustering map o' with centers S in the Pareto set for clustering, there exists assignment to the centers S found by an approximate vanilla clustering algorithm that achieves the same or better fairness and at most (2 + a) times the clustering cost. Then, since Algorithm [ finds the Pareto set of the assignment problem, we are guaranteed the stated approximation. We construct this assignment using a "routing" argument, first introduced in Bera et al. (9] create an assignment ø' by routing all points in o² with center 8 *S the center in S' nearest to s". Given that the clustering cost is metric-based, we use the triangle inequality on the cost objective argue that the cost of o' w.r.t. S is not more than (2 + a) times the cost of 6" w.r.t. S*. Then, we use the mergeability property of the fairness objective to argue that o' has a weakly better faimess than Φ- We can, in fact, modify Algorithm I to include non-meggeable fairness objectives, guaranteeing the same approximation ratio and time complexity:
Theorem 3.5. We can compute a (2+a,) 1) approximation of the Pareto set for the clustering problem with a metric-based cost objective e and a pattern-based fairness objective f in time Okkn"(k-1))
The trick here is to transform non -on-eeeeebll fairnsss objectives into mergeable ones, and then apply Algorithm| T In doing so, we control this transformation through re-assigning the cen- ters of potentially empty clusters (which become an issue in non-mergeable fairesss functions). Specif- ically, for patterns that have empty clusters, we search for the best possible fairness over all ways to re- assign the empty clusters' centers other centers' locations and divide up the points in the non-empty centers. A detailed description and proof for this modified algorithm can be found in Appendix A
Proof Sketch:
3.3 Intractability
The running time of [ for computing the Pareto front has the parameters ks, I in the exponent of n. What evidence do we have that this computation is necessary?
One reason would be that the sheer size of the Pareto front may be exponential, For some objectives, including the BALANCE and the GROUP EGALITARIAN objectives defined Section [2] the Pareto front is provably of polynomial size. The reason is that all possible values of these objectives are rational numbers involving integers that are all smaller than n, and there are O(n²) possible different such rational numbers. For other objectives, there may be instances of exponential Pareto fronts, as the objectives that sum over the clusters.
However, a different argument provides a justification of the algorithm's 's exponential performance: In several papers in recent literature (e.g., see (26 (2)), it is shown that, for a variety of cost functions e and fairness objectives (including all mentioned proportional violation based objectives), it is NP-hard to find the assignment& C that has the smallest e(C) under the constraint that (CC < F (for some bound F). We conclude that, unless P = NP, there is no polynomial-time algorithm for outputting the Pareto front, for at least some combinations of c and f. As a footnote to this discussion, the above complexity argument rules out polynomial algorithms, but not exponential algorithms of the form, for example, O(2*n²). which is much more benign than ())). These would be ruled out, subject to complexity conjectures, the problem of finding the least costly clustering subject to fairnss constraints were shown to be W-complete, a more severe form of complexity that rules out this more benign exponential performance 23). We leave this as an interesting open question in the theory of the faimess-cost trade-off of clustering.

---

3,4 A Polynomial Algorithm for the Pareto Front of the Sum of Imbalances
For specific cost and fairness objectives, there is still hope that polynomial-tima algorithms exist. As we show below, for simple objective derived from the BALANCE objective, such an algorithm possible. For the SUM OF IMBALANCES fairness objective and a clustering objective defined in Section 2 we want to compute the Pareto front when | = 2. Surprisiglly, it turns out that this problem can be solved polynomial time by a reduction to the weighted matching problem.
Theorem 3.6. Ifl = 2 and the fairness objective f the sum of imbalances f(C) 1 Eie(y IC| -C,).
then the Pareto front of the assignment problem can be computed in polynomial time.
The image of f is contained in the integer set {1.-... ,n). For each potential value j. we construct graph Gj that contains X' as nodes and another j 'dummy' nodes. We put an edge (u, v) between every V E X' with different sensitive attribute value with weight equal to the cost min (u, a) + d' (e( a)). Between every data point u E X and dummy point v put an edge (u, r) with cost min, d 8x). Finding the minimum cost perfect matching in this graph gives the minimum cost of an assignment with fairness value j. The same result can be shown similarly for the MAX IMBALANCE objective, max4e[M] IC} C? (Theorem A.5
Proof Sketch:
Remark 3.7. These objectives are quite natural extensions of the BALANCE objective, as they minimize the sum or max, over the k clusters, of the deviation from equality between the two groups. It is worth noting that slight modification of these objectives place the problem back in the NP-complete space: A construction of Bercea et al. [IO] (see also Esmaeili et al. (26), Theorem 5.1) implies that for minimizing the deviations not from equality (1 1) but from the ratio 1 3, is NP-complete to find even the point of the Pareto front with the best faireess value.
4 Experiments
We implement our proposed algorithm (Algorithm I for finding the Pareto front on three real-world datasets and five fairness objectives, as detailed below.
Datasets: We use the following real-world datasets for our experiments: the Adult dataset and the Census dataset retrieved from the UCI repository (as the Census 1990 version) [43 46), and the BlueBike trip history dataset The Adult and Census datasets contain numeric attributes such as income, age, education level, often used in applications of fair clustering [6 19 26). The BlueBike dataset contains the starting location, ending location, as well various user attributes for users of the BlueBike bike sharing system in the Boston area. We use as features the starting and ending longitude and latitude values for all rides during period of a week in May. 2016. These routes are a proxy for common traffic patterns, for which clustering can inform of high-density areas, with new locations for bike stations or public transportation. Clustering and related framings have long been used in facility location problems, for which fairnsss is a central question [I 41 53 62). As the datasets are prohibitively large, we sample from each 1, 000 data points. Further details about the datasets can be found in Appendix C
the purpose of deciding
Objectives: We implement the k-means clustering objective and five different fairness objectives, as defined in Section 2 (BALANCE, GROUP UTILITARIAN, GROUP UTILITARIAN-SON SUM, GROUP EGALITARIAN, and GROUP EGALITARIAN-SUMT SUM)..
Experimental details: We first note that our approach for finding the Pareto front is agnostic to
the specific vanilla clustering algorithm used. For our datasets, we use the k- k-means++ clustering algorithm as the vanilla clustering that has an approximation ratio of ((lgg()) (k)) [5) All datasets have numeric attributes, allowing a direct embedding into Euclidean space and using k-means++ directly on the features. We use the self-reported gender (male or female) as the sensitive attribute for all datasets. Each sensitive attribute a has a proportion Pa in the general population. For the proportional violation objectives, we set upper and lower bounds as 8-deviation from the true proportions (po)a:
ag = (1 + 6) Sa = (1 - d)... We set d E [0.005, 0.05] for all experiments and i: = 2 clusters. Additional experiments for k = 3 are reported in Appendix E noting qualitatively similar results. All experiments are run on local computers, using Python 3.9, k-means++ [1) NetworkX 33 and
The BlueBike trip history dataset is retrieved from ftttp:://bluebikes.comm
7

---

CPLEX for the implementation of the FCBC algorithm [52 26 with e = 2- 10 and N = 50 runs. An
empirical analysis of the running time for Algorithms |
and can be found in Section D Figure
4.1 Pareto Front on Real-Worle Data
Figure Dillustaatt the Pareto front recovered by our dynamic programming approach (Algorithm I on the real-world datasets: the curves obtained are an exact recovery of the Pareto front for the assignment problem (as we are not re-computing the clusters centers during the implementation), and thus an approximation for the true Pareto front of the clustering problem. We note that the BALANCE objective and the proportional violation objectives differ: higher balance is considered fairer, whereas lower proportional violation is considered fairer, hence the different shapes of the Pareto fronts. From an evaluation point of view, for each assignment found on the Pareto front, we compute its clustering cost with respect to its actual centers, rather than the initial centers found by k-means++.
We note that the Pareto front is often, but not always strictly convex or concave, as it simply contains all the undominated points. We note that the proportional violation values will always be worse for the summed objectives than for their min-max equivalents, since the worst proportional violation A is always non-negative, Va E [1] C.
A particular advantage of finding the entire Pareto front is visible for the BALANCE objective in all datasets: as the clustering cost increases, the gain the BALANCE objective becomes negligible; thus, a practitioner wishing to achieve some level of fairness may gain a lot in quality by allowing BALANCE to decrease by a minimal amount.
A6-1
16:
MP
0.28
039
1.50
028
0.7
(a) Balance
(b) Group Util
(c) Group Util-Sum
(d) Group Egalit
(e) Group Egalit-Sum
Certul
3.80
1213
1300
6500
AU801
Curarin C0
ABDO
53500 5U00
Clabiing
save
10000
5006 0200
Quarting cort
30166 sanse
X000 ATDO woss nusi
Curangg die
43.00 4010
Cluwiing
KIKS
(f) Balance
(g) Group Util
(h) Group Util-Sume Suil-Sum
(i) Group Egalit
(j) Group Egalit- Sum
Blardhe
th Mike
0.00
8.0
5.0
500
6.20
0.00
200
2301
226 230 2002
2207
2200
2010
230
2018
2009
2000
2000
21:0
1200 21RE
1227
$200
2at
(k) Balance
(1) Group Util
(m) Group Util-Sum
(n) Group Egalit
(o) Group Egalit- Sum
Figure I: Pareto front recovered by Algorithm | for the Adult, Census, and BlueBike datasets (by row), for various faimess objectives (by column), for k = 2 clusters.
4.2 Exploring Faster Pareto Front Approximations
We explore faster algorithms for recovering the Pareto front for the clustering problem. In particular, we leverage a recently proposed linear programming approach that imposes an upper bound on the clustering objective and optimizes fairness objective, the FCBC algorithm proposed by Esmaeili et al. 26). For the GROUP UTILITARIAN and GROUP EGALITARIAN objectives with a clustering
All code and data used in the paper can be found at this link
8

---

cost upper bound input U, FCBC presents polynomial -imee approach for finding approximation of a point z on the Pareto front that has a clustering cost upper bounded by a quantity (2 + a)U with fairness additive approximation of Here, is the approximation ratio of a vanilla clustering algorithm for the clustering objective, and 1) an additive approximation for the fairness objective. Thus, we can extend the W-approximation of a Pareto set definition (Definition 3.3) to include an additive approximation term: for parameters W = ((we, ve), (wy, (r)), we can define the (W, V)- approximation of the Pareto set Xp as set of feasible points X such that Vz Xp, 3z' X
such that c(x') I We : c(x) + Ue and f(x') S Wy f(x) + Vy. We note that Algorithm I gives only a multiplicative approximation, so U2 2/ = 0. In contrast, for a point E Xp the true Pareto front, FCBC recovers ((2 oz 0). (1, m)) aaprrxximaxiinooon 5
We extend the FCBC algorithm by allowing sweep over the clustering cost upper bound U, thus, in theory, obtaining an approximation of the Pareto front in polynomial time (for detailed description,
see Algorithm 2
in Appendix D)
Figure[]showe that repeated FCBC (Algorithm 2 recovers few points on the Pareto front recovered by Algorithm [ sometimes it recovered the vanilla clustering cost and fairness (the upper most left point in panels b,c.e,f), whereas in other cases it recovers dominated clustering assignments (in panels a-d). We attribute this inaccuracy in recovery the additive approximation in the fairness objective. Furthermore, whereas both our dynamic programming approach and repeated FCBC have an approximation ratio of (2 + a) in the clustering objective, dynamic programming often gets a strictly better cost for similar fairness values. In other words, where repeated FCBC gains in running time | it loses in recovery accuracy and clustering cost. This is particularly problematic when the only point recovered by FCBC is the vanilla clustering assignment: this means that even when a practitioner may be willing to trade-off significant clustering cost in order to improve fairness, that trade-off is not realizable in practice solely through FCBC.
Furthermore, the FCBC algorithm does not work for objectives summing over the clusters, such as GROUP UTILITARIAN-S polynomial time algorithm that can recover the Pareto front to within additive approximation of O(n"), for& 8 E [0, 1) (see Theorem 7.1 in Esmacili et al. (26). Our approach, however, can also include such objectives, as we show both in theory and in practice.
and GROUP EGALITARIAN-SS
For such objectives, there is no
5 Discussion
Overall, our work shows the versatility of our proposed algorithms for a variety of fairness and clustering objectives. We provide simple properties sufficient in theory for the recovery of the Pareto front for the (clustering, quimess)-bioojectiss optimization problem, with extensive experiments on real-world datasets. We discuss limitations and future directions of our work in this section.
First, while our approach has the advantage of being agnostic to specific objectives, it loses in running time compared to approaches that optimize for specific faimness objectives. While previous work provides approximation algorithms for optimization clustering under a fairness constraint, none offers method for computing the Pareto front. On the question "can we have faster algorithms with worse approximation bounds?', the answer is yes. Our paper provides (the first, to our knowledge) such ex- ploration: We show in Section 4.2 that we can adapt such polynomial-time methods compute an ap- proximation of the Pareto front; however, what we gain in runtime, we lose in approximation bounds: the repeated FCBC algorithm has an additive approximation on the fairness objective that can get large in practice (we get a different Pareto front, with points quite far away in the objective cost, compared to the dynamic programming approach), and with no theoretical bounds on the additive approximation.
A future direction could study faster algorithms that can recover a similar approximation of the Pareto front. Interesting theoretical open questions emerge: while our analysis ruled out polynomial algorithms for general objectives, are there exponential algorithms (i.e. of the form ((2* ((2*n²) )) that still provide an improvement from ((n()))))) of algorithms? And, are there other objectives
'I particular, is dependent on the fairness objective, on U, and on the specific instance of the fair clustering problem (see Theorem 6.1 in Esmacili et al. (26).. A potential limitation of this approximation is that is not efficiently computable in closed- form for particular instance.
'The FCBC algorithm uses linear programming through the simplex method, with casst-case running time of O(2"): ); in practice, it is faster than that, noted in the Appendix.

---

BlueBike
0.10
Dyn Progr FCBc
Dyn Progr FCBc
0.04
Dyn Progr
vidaaioo
Proportonal volatton
0.04
Proportoonll vitolaion
FCaC
0.08
0.03
0.03
0.08
0.02
0.02
0.01
0.01
0.00
0.00
4200
4225
4250
4278
4300
55000
67500
60000 62500
66000
2388
2386
2290
2391
Clustoring cost
Glustoring cost
Clustering cost
(a) Group Util
(b) Group Util
(c) Group Util
Adult
Census
BlueB
Prosortonal vtiiaan
0.00
FCBC
0.05
FCBC
Dyn Progr
Propotional violaton
FCBC
Progr
0.04
00.015
Proponional
0.03
0.010
0.02
0.00
0.00
0.000
4250
54600
Clustering cost
Clustering cost
(d) Group Egalit
(c) Group Egalit
(f) Group Egalit
Figure 2: Pareto front recovered by Algorithm (labeled 'Dyn Progr', blue) and by Algorithm
(labeled 'FCBC', orange), for k = 2 clusters.
that admit polynomial-tin timee algorithms for computing an approximate Pareto, aside from SUM/MAX IMBALANCES? Furthermore, future work could investigate algorithms for recovering the Pareto front for fairness objectives that are not pattern which is a prerequisite for our algorithms. We provide some examples of such objectives in the Appendix.
Our approach is best suited for group fairness definitions. Extending this work to other definitions would be excellent avenue for future work. We that for some individual faimeess definitions, the notion of Pareto front does not apply: for example, the socially fair k-means clustering notion proposed by Ghadiri et al. (31) defines single optimization objective that already incorporates fairness (by minimizing the max distance between points in each group and their cluster centers). With this definition, the fairness objective and the clustering objective are not separated in multi-objective optimization problem, but rather combined in a single objective. Therefore, there no Pareto front, since this notion applies to a multi-objective optimization problem. For other definitions of individual fairness, such as recent adaptations of individual fairness under bi-criteria optimization problems (50). one can apply repeated approximation algorithm under an upper bound on one of the objectives (similar to the repeated-FCBe algorithm). In doing so, one would obtain loose approximation guarantees (see, for example, the approximation guarantee for individual fairness proved by Mahabadi and Vakilian (50). Dynamic programming approaches would not directly apply; however, we think this would be an excellent avenue for future work.
Finally, we assumed that the sensitive attributes are disjoint. For overlapping attributes, one could assign new sensitive attribute every overlap set and apply our approach, however, with significant increase in running time. Future work could investigate alternative approaches that optimize rumning time for overlapping attributes.
Acknowledgments and Disclosure of Funding
The authors would like to thank Vivian Y. Nastl for valuable feedback on earlier drafts of the paper. A.-A acknowledges support from the Tübingen AI Center. M. Y. acknowledges support from NSF grants CCF-2332922 and CCF-2212233,
10

---

References
[I] Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramaniin. Fair clustering via equitable group representations. In Proceedings of the 2021 ACM Conference Fairness, Accountability, and Transparency, pages 504-514, 2021.
[2] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 267-275, 2019.
[3] Sara Ahmadian, Ashkan Carouzi-Fard. Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49 (4)=FOCS17-97, 2019.
[4] Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. NP-hardness of Euclidean sum-of-squares clustering. Machine learning, 75:245-243 2009.
[5] David Arthur, Sergei Vassilvitskii, et al. k-means++: The advantages of careful seeding. In ACM-SIAM Symposium on Discrete Algorithms,, volume 7, pages 1027-1035, 2007.
[6] Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In International Conference Machine Learning, pages 405-413. PMLR, 2019.
[7] NohammadHossiie Bateni, Vincent Cohen-Addad, Alessandro Epasto, and Silvio Lattanzi. scalable algorithm for individually fair k-means clustering. In International Conference on Artificial Intelligence and Statistics, pages 3151-3159. PMLR, 2024.
[8] Cristina Bazgan, Laurent Gourvès, and Jérôme Monnot. Approximation with fixed number of solutions of some multiobjective maximization problems. Journal of Discrete Algorithms, 22: 19-29, 2013.
[9] Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32, 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. arXiv preprint 1rXiv:1811.10319 2018.
[11] Fritz Bökler and Markus Chimani. Approximating multiobjective shortest path in practice. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX), pages 120- 133. SIAM, 2020.
[12] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[13] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, 2016.
[14] Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms (TALG), 13(2):1 2017.
[15] Darshan Chakrabarti, John Dickerson, Seyed A Esmaeili, Aravind Srinivasan, and Leonidas Tsepenekas. A new notion of individually fair clustering: a-equiiable k-center. In International Conference on Artificial Intelligence and Statistics, pages 6387-6408. PMIR, 2022.
[16] Weiyu Chen and James Kwok. Multi-objective deep learning with adaptive reference vectors. Advances in Neural Information Processing Systems, 35:32723-32735. 2022.
[17] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In International Conference on Machine Learning, pages 1032-1041. PMLR, 2019.
[18] Anshuman Chhabra, Karina Masalkovaité, and Prasant Mohapatra. overview of fairness in
clustering. IEEE Access, 221130988-307220 2021.

---

[19] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi. and Sergei Vassilvitskii. Fair clustering through fairlets. Advances Neural Information Processing Systems, 30, 2017.
[20] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182-197, 2002.
[21] Ilias Diakonikolas and Mihalis Yannakakis. Small approximate Pareto sets for biobjective shortest paths and other problems. SIAM Journal on Computing, 3904):134-1131, 2010.
[22] John Dickerson, Seyed Esmaeili, Jamie H Morgenstern, and Claire Jie Zhang. Doubly con- strained fair clustering. Advances in Neural Information Processing Systems, 36, 2024.
[23] Rodney G Downey and Michael Ralph Fellows, Parameterized complexity. Springer Science & Business Media, 2012.
[24] Jack Edmonds. Maximum matching and a polyhedron with 0,1 vertices. J. Res. Nat. Bur. Standards, 69B:125-132 1965.
[25] Thomas Erlebach, Hans Kellerer, and Ulrich Pferschy. Approximating multiobjective knapsack problems. Management Science, 48(12):1603-1612 2002.
[26] Seyed Esmacili, Brian Brubach, Aravind Srinivasan, and John Dickerson. Fair clustering under bounded cost. Advances in Neural Information Processing Systems, 144144355-4337, 2021.
[27] Seyed A Esmaeili, Sharmila Duppala, John Dickerson, and Brian Brubach. Fair labeled clustering. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 327-335, 2022.
[28) Reza Zanjirani Farahani, Maryam SteadieSeifi, and Nasrin Asgari. Multiple criteria facility location problems: survey. Applied mathematical modelling. 34(7):1689-170 1709, 2010.
[29] Laurie E Felland, Johanna R Lauer, and Peter J Cunningham. Suburban poverty and the health care safety net. Center for Studying Health System Change Washington (DC), 2009.
[30] Harold N. Gabow. Data structures for weighted matching and extensions to b-matching and f-factors. ACM Trans. Algorithms, 143):39:1139:80 2018.
[31] Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair k-means clustering. In Proceedings of the 2021 ACM Conference Fairness, Accountability, and Transparency, pages 438 0003-48,222 2021.
[32] Shivam Gupta, Ganesh Ghalme, Narayanan C. Krishhaan, and Shweta Jain. Efficient algorithms for fair clustering with new notion of fairness. Data Mining and Knowledge Discovery, 37(5): 1999-1997, 2023.
[33] Aric Hagberg, Dan Schult, Pieter Swart, Conway, Séguin-Charbomen Ellison, B Ed- wards, and J Torrents. Networkx. high productivity software for complex networks. Webová strå nka https://networks. lanl. gov/wiki, 2013.
[34] Vahid Hajipour, Parviz Fattahi, Madjid Tavana, and Debora Di Caprio. Multi-objective multi- layer congested facility cccation-allocatin problem optimization with Pareto-based meta- heuristics. Applied Mathematical Modelling, 40(7-8), 2016.
[35] SI Harewood. Emergency ambulance deployment in barbados: multi-objective approach. Journal of the Operational Research Society, 53(2):185-192, 2002.
[36] Mordechai I Henig. The shortest path problem with two objective functions. European Journal of Operational Research, (5(2))281-2211 1986.
[37] Long P Hoang, Dung D Le, Tran Anh Tuan, and Tran Ngoc Thang. Improving Pareto front learning via multi-sample hypernetworks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 7875-7883, 2023.
12

---

[38] Dorit S Hochbaum and David B Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM (JACM). 33(3):533-5500 1986.
[39] Bo Huang, Fery, L Xue, and Y Wang. Seeking the pareto front for multiobjective spatial optimization problems. International Journal of Geographical Information Science, 22(5): 507-526, 2008.
[40] Lingxiao Huang, Shaofeng Jiang, and Nisheeth Vishnoi. Coresets for clustering with fairness constraints. Advances in Neural Information Processing Systems, 32, 2019.
[41] Christopher Jung, Sampath Kannan, and Neil Lutz. A center in your neighborhood: Faimness in facility location. arXiv preprint arXiv:1908. 190,0099,,, 2019.
[42] Kathrin Klamroth and Margaret M Wiecek. Dynamic programming approaches to the multiple criteria knapsack problem. Naval Research Logistics (NRL), 47(1):57-76, 2000.
[43] Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, volume 96, pages 202-207, 1996.
[44] Michael M Kostreva and Malgorzata M Wiecek. Time dependency in multiple objective dynamic programming. Journal of Mathematical Analysis and Applications, 173:289-289, 1993.
[45] Bo Li, Lijun Li, Ankang Sun, Chenhao Wang, and Yingfan Wang. Approximate group fairness for clustering. In International Conference on Machine Learning, pages 6381-6391 PMLR, 2021.
[46] Moshe Lichman. UCI machine learning repository, 2013.
[47] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing- Fu Zhang, and Sam Kwong. Pareto multi-task learning. Advances in Neural Information Processing Systems, 32, 2019.
[48] Xi Lin, Zhiyuan Yang, Qingfu Zhang, and Sam Kwong. Controllable Pareto multi-task learning. arXiv preprint arXiv:2010.06313, 2020.
[49] Suyun Liu and Luis Nunes Vicente. The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning. Annals of Operations Research, pages 1-30, 2021.
[50] Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering. International Conference Machine Learning, pages 6586-6599 PMLR, 2020.
[51] Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in Pareto optimization. In International Conference on Machine Learning, pages 6597-6607. PMLR, 2020.
[52] IBM CPLEX User's Manual. Version 12 release 7. IBM ILOG CPLEX Optimization, 2016.
[53] Michael T Marsh and David A Schilling. Equity measurement in facility location analysis: A review and framework. European Journal of Operational Research, 74(1):1-17, 1994.
[54] Maryam Negahbani and Deeparnab Chakrabarty. Better algorithms for individually fair k- clustering. Advances Neural Information Processing Systems, 11:113300-3335 2021.
[55] Christos H Papadimitriou and Mihalis Yannakakis. On the approximability of trade-off's and optimal access of web sources. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 86.92. IEEE, 2000.
[56] Konstantinos Parsopoulos and Michael N Vrahatis. Particle swarm optimization method in multiobjective problems. In Proceedings of the 2002 ACM Symposium on Applied Computing. pages 603-607 607, 2002.
[57] John Preston and Fiona Rajé, Accessibility, mobility and transport-related social exclusion. Journal of transport geography, 15(3):151-160, 2007.
13

---

[58] Seyed Habib A Rahmati, Vahid Hajipour, and Seyed Taghi Akhavan Niaki. A soft-computing Pareto-based uuta-heeuisticc algorithm for multi-objective multi-server facility location prob- lem. Applied Soft Computing, 1324):1728-1740, 2013.
[59] Juana L Redondo, José Fernández, José Domingo Álvarez Hervás, Aránzazu Gila Arrondo, and Pilar M Ortigosa. Approximating the Pareto-front of a planar bi-objective competitive facility location and design problem. Computers & Operations Research, 62:337-349, 2015.
[60] Michael Ruchte and Josif Grabocka. Scalable Pareto front approximation for deep multi- objective learning. In 2021 IEEE International Conference Data Mining (ICDM), pages 1306-1311. IEEE, 2021.
[61] Hisashi Tamaki, Hajime Kita, and Shigenobu Kobayashi. Multi-objective optimization by genetic algorithms: review. In Proceedings of IEEE International Conference Evolutionary Computation, pages 517-522. IEEE, 1996.
[62] Ali Vakilian and Mustafa Yalciner. Improved approximation algorithms for individually fair clustering. In International Conference on Artificial Intelligence and Statisties, pages 8758- 8779. PMLR, 2022.
[63] Bernardo Villarreal and Mark H Karwan. Multicriteria integer programming: A (hybrid) dynamic programming recursive approach. Mathematical programming, 21:204-223, 1981.
[64] Arthur Warburton. Approximation of Pareto optima in multiple-objective, shortest-pan path prob-
lems. Operations research, 35(1):70-79, 1987.
[65] Qingfu Zhang and Hui Li. MOEA/D: A multiobjective evolutionary algorithm based
decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712-731, 2007.
14

---

A Complete Proofs
Proof of Theorem 3.2 Define Vp as the set of clusterings C that have the pettern pc = P and C is a clustering of X,. Let be the metric-based cost function for the assignment centers S, which is parameterized by a distance function d and non-negative exponent p. We will argue that, for all j. the clustering C stored at [P] has the property that C arg minc c(C'). We will show that this invariant always holds by induction on the number of data points in the current level of the table j (equivalenty, the number of points clustered by C in the main loop of Algorithm IT. The base case is j = O, where we store the empty clustering, the unique clustering of 0 points.
Suppose we have some pattern P for the set of the first points in arg mincev, yp c(C), so C* is optimal cost for P. Point zj must be in some cluster C, E C The clustering C; of the remaining points (which are exactly the first j 1 points from the data) induces some pattern P = pe: which an X; Since C* was assumed to be of optimal quality, the clustering C must have the property that C. = arg mincev,, pf c(C). Otherwise, C₁ could be replaced in C with the lower cost clustering that has the same pattern and reduce the cost of C* contradiction).
ordering, X, Let C
We have shown that C = C,, where C. = C; + x. is generated by assigning the first j - points according to C₁2, and then adding point 2i cluster By the inductive assumption Tj 1 [ correctly stores the optimal C₁-
Since Algorithm I minimizes e(C;) over cluster indices we correctly compute the optimal clustering of j points that maps to P. All candidate points for the Pareto set of the assignment problem are stored in Tn, meaning that every clustering C' of X' is weakly dominated by some clustering in Tn. This is because every clustering C E K. must map to some X' X-pattern P. By our algorithm invariant, C E T, [P] is the clustering that minimizes assignment cost across clusterings that have fairness
pattern P. and thus c(C*) ) < c(C). In addition, since pe pe and f is a pattern- objective, f(C*) = f(C). So, C is weakly dominated by C E Tn. Therefore, filtering dominated points out of the clusterings in T, gives us the complete Pareto set for the assignment problem with pattern- based fairness objectives and metric-based cost objectives on n data points. Note that the output of Algorithm (ecoovrrs the Pareto set {C} as well as the Pareto front {c((C) f(C), since the Pareto front is just the image of the Pareto set under the two objectives.
Proof of Theorem 3.4 Theorem 3.2 states that Algorithm I finds (exactly) the Pareto front of the
assignment problem. Let , S that satisfy a particular fairness bound F. Let σ, S be the clustering map and set of centers found by a vanilla clustering algorithm A, which achieves an a-approximation to the best clustering cost. We define a new assignment ø' S. by applying a "routing" argument, first introduced in Bera et al. [9] and reused in Esmacili et al. [27].
be the optimal cost clustering map and set of centers, respectively,
Define function nrst(s*) = arg minses dP(s, s*) which returns the nearest center in S to an input center 8*. Now define an assignment map ø' where vertices are routed from their center s7 E S* to nrst(s?) E S. In other words, for every point v, d'(x) = mrst(c> (a:)). Now we can write:
d'(x, ((x, ('xx)) d (st,, nrst( (x)))) d'(a, x (x) (x) + d' (x)(x) nrst(o (z)))
S dz x
(x) (x)
+ d' o(x))
2d (z. x0 (z)) + d (z. ((x))
The first and third inequalities follow from the triangle inequality on d² and the second in- equality is due to the definition of the nest function. In addition, a (E. d2 o (x))) > (E, (x, d(r) since & is the clustering found by the vanilla clustering algorithm A. Ap- plying our previous inequality together with the triangle inequality on the p-norm:
1/p
Σ 2d (z, (2,, ((a)))
1/p + Ed((o,((a))
1/P
[d(a,((()))
<
1/8
[ Ed((E
< (2 a))
15

---

This implies that 5'S is an assignment map with respect to centers S that has at most (2 + a) times the cost of 6² with respect centers S*
In addition, the clustering C' associated with d' can be generated by, for each 8, E S, merging all clus- ters C E C* such that nest(s;)) = 8z- This procedure be done by sequentially merging pairs of clusters. Since the fairness objective is mergeable (see Def. 2.2). this implies that f(C*) 2 f(C"). So, the assignment map o' with respect to centers also satisfies the fairness bound F'. There exists an as- signment to centers S that is a (2+a,, ->approximmttion to ø-, S", so the Pareto front of the assignment problem is (2 + a, approxxiaationnn the Pareto front of the clustering problem as desired.
Proof of Theorem 3.3
We describe in detail the algorithm modification needed compute the Pareto front for non-mergeable fairness objectives. First, we give some necessary preliminaries:
Definition A.1 (Refinement of pattern and refinement DAG D). Consider the directed graph D with the X' X-patterns as nodes and edges (Pi, P2) if merging two nonempty rows of the pattern P3 yields the pattern Pt- A pattern P' is refinement of another pattern P iff there is path from P to P' in D, i.e. if P can be obtained from P' by merging different parts of p', Note that D is directed acyclic graph (DAG). Let Rp be the set of pr that are refinements of P.
Similarly, one can define the refinement of clustering C. Note that if a clustering C' is refinement of another clustering C, then its pattern pC is refinement of the pattern of cluster C, pC
Next, we define a modified fairness function created from the non mergeeeee function f. with the purpose of reducing it to mergeable function and applying Algorithm
Definition A.2 (Modified fairness function). f is pattern-basee based fairness function, define its associated modified function of to be f(P) = minp'e (f(')) for every pattern P.
Note that f is still required to be pattern-based, and thus modified function is well-defined. By definition, f is mergeable function. Furthermore, if is mergeable then f
Lemma A.3. We can compute in (n time the modified function f for all X-patterns P, and compute for each P a refinement P' such that f(PP) = f(P).
Proof. We compute f bottom up in the DAG D. We also compute for each node a pointer to its refinement pattern that has the minimum faimess cost. At the sinks P (patterns that have no outward edge pointing from them to other patterns), f(P) f(P) and P points to itself only. For every non-sink node P. we set (PP) min f() where N(P) is the set of neighbors of P. and we set the pointer of P to the descendant pointed by the neighbor v of P with the minimum f(v).
The total time complexity is linear in the number of nodes and edges of D. The number of edges is at most 22 times the number of nodes, since every node p' has most k22 incoming edges (there are at most 2 choices for the two parts of P' that are merged to form a parent pattern). The number of nodes of D, i.e. X' X-patterns, is at most 4k ) ((k-1)) All the components of all the rows of a pattern P. except possibly at most two components, are less than n/2: furthermore, specifying A rows of P determines also the last row because the sum for each attribute value must match the given set of
points. From the bounds on the number of nodes and edges of D, follows that the time complexity (k-1())))
Recall that in clustering we associate center with each cluster, and the cost of clustering is puted from the distances of the points from the center of their cluster. We allow different clusters to have the same point their center. We show the following result, needed in the proof of Theorem 3.5
Lemma A.A. If we are given a clustering C with centers S and P' is refinement of PC then we reffineee can compute efficiently a clustering C' with centers S', which we call a center reassignment of C. such that pe' P' and c(C',S)) = c(C, S). The centers St will be a subset of the points in S but with multiplicity (i.e. different clusters may have the same center).
16

---

Proof. Suppose that row i of pattern P is formed by merging a set J; of two or more nonempty parts of P'. Then we split the cluster C, of C into a set of | subelusters, one for each part in Jr, and we place in each subcluster number of points from C, for each attribute value that matches the corresponding entry in the row of P'; we assign to all the subclusters the same center as the center of C..
After performing the above splitting for all parts i of P that are refined in the pattern P', we obtain a clustering C' such that pe* P'. Since the subclusters created from splitting a cluster C, of C are assigned the same center as the center of C₁ it follows from the definition of a metric-based cost function, that C. and C' have the same cost.
We now describe the algorithm modification for non-mergeable fairness objectives. For non-mergeable faimess objective fet f= minp'eR, (fP')) be its associated modified function. Apply the algorithm of Lemma A.3 to compute ((P) for every X'ppttern P. and the corresponding pointer to its optimal refinement P". As before, use vanilla clustering approximation algorithm A to compute a clustering that approximates the minimum cost. Use the centers of this clustering in Algorithm I to construct the dynamic programming table T,. Process the patterns P as before in order of increasing cost, but now use the modified funetion f as the faimess objective to filter out dominated patterns, and for each undominated pattern P. replace the clustering C in T, [P] by the center reassignment clustering C' constructed in Lemma [A.4] The algorithm returns the set of these center reassignment clusterings C' for all undominated patterns. By the definition of the modified faimess function and Lemma A.4 these are undominated clusterings for the original (non- - fairness function f and the clustering cost c.
From our timing analysis, the time complexity of the algorithm is (kn(((-1))
The proof of the approximation follows the proof of Theorem 3.4 We define ,²' -S"'.. o, S. and H' similarly as before. Observe that in the construction of ø', we simply merged clusters from o² and gave them new centers. Since the pattern of a clustering is independent of the identities of the centers, the pattern of ø" a refinement of the pattern of ø'. So by Lemma o" that is a center reassignment of ø' and has the same pattern as Φ".
A.4 there exists a clustering
Therefore, &", which is one of the reassignments and c(C") = c(d') (here, we used interchangeably the clustering cost function e applied to the clustering or the clustering assignment map, which equivalent). Since d' has most 2 + a worse cost than ø² (see proof of Theorem (34), so does C". Therefore, the Pareto front computed by the algorithm a (2 a, -paapproximation the Pareto front of the clustering problem, as desired. O
search over in the algorithm, has S(C") = f(Ø")
Proof of Theorem 3.6 First we notice that in this case f can take at most n + values: If = | is even, then it can take only values the even integers between 0 and n, and if it is odd all odd integers between 1 and n 1. We shall treat the case of even n, the case of even n being very similar.
Given dataset X, metric d, and exponent p. for each even number F between and n we must compute the best assignment that has fairness F. Once this is done, we only have to sort with respect to fairness and remove the dominated assignments (in a similar vein to the filtering heuristic of Algorithm| D]. Clearly, this step is polynomial time since we can sort the points in O(n log(n)) and then make a single pass over them to remove the dominated points. All that remains to show is that we can compute the best assignment with faimesss F also in polynomial time. We do as follows.
Given an even number F, we construct a weighted graph GF with n nodes corresponding to the data points, plus F dummy nodes. We join every data point with every dummy node z by an edge of weight mingeja d' (z,,s). We join any two data points x, with different attribute value (recall that there are only two attribute values) by an edge of length m (z. s:) + dP 8:)). We call an edge of Gp to be of type E [k] if the i-th cluster achieves the minimum that defines the weight of the edge. (In other words, i is the argmin of the minimization expression.)
A perfect matching in graph is a set of disjoint edges that includes all the nodes. The weight of matching M is defined as the sum of the weights of edges that are contained in the matching: w(M) =
Eeen Ms w(e). Compute the minimum weight perfect matching M in the graph GF. This can be done
17

---

in polynomial time using Edmonds' algorithm [24], specifically in time O(N(E - N log N)) for graph with N nodes and E edges (30;; our case the graph GF has at most 2n nodes and 2n edges.
We will show that the minimum weight of a perfect matching is equal to the minimum cost of a clustering with fairness F, and furthermore we can derive minimum cost clustering from the minimum weight matching M.
Consider any clustering C with f(C) = F. Starting from C. we construct a perfect matching M of Gp as follows: For each cluster C E C. choose the attribute value that has fewer nodes in C' (breaking ties arbitrarily). Now, match these nodes of attribute a in C' arbitrarily with nodes of the larger attribute group in C. Finally, match any remaining nodes of the other group (the larger attribute group) to dummy nodes.
We claim that such matching M is possible, because the total number of nodes that cannot be matched is precisely F, the number of dummy nodes. We claim now that the weight of this matching w(M) is at most the cost of the clustering, c(C); that is, w(M) S c(C).
The weight of the matching is at most the clustering cost for the following reason: each matched pair I, contributes to c(C) at least the weight of the corresponding matched edge; and any data point matched to a dummy node again contributes to e(C) at least the weight of the matched edge.
Now consider the minimum weight perfect matching M of the weighted graph Gp. Clearly, w(M) S c(C). Construct from M a corresponding clustering é as follows: any matched data point whose edge is of type i is placed in cluster i, while any data point matched in M with a dummy node with an edge of type i is added to cluster i. This clustering satisfies c(C) = w (M I c(C). Since
C. was assumed to be an arbitrary clustering with f(C) = F. Ć is the optimum such clustering. O
The same result can be shown for the MAX IMBALANCE objective.
Theorem A.5. If = 2 and the fairness objective f is the max imbalance f(C) = ma [IC)] IC? l, then the Pareto front of the assignment problem can be computed in polynomial time.
Proof. The objective can take again at most n values (more precisely, at most 1 1+ 1x22) values). For each possible value F, construct weighted graph Gr, whose set NF of nodes consists of n nodes corresponding to the given set X' of data points, set D, of F dummy nodes for each i E [k], and if n + kF is odd, then Np has one more dummy node so that the total number of nodes is even. The edge set Ep of GF consists of the following edges: for each pair 2, y of data points with different attribute values, we include an edge (æt, y) with weight min (Ir, 8:) + dP dP 8:)) and associate with the edge as its type the index E [4] that achieves the minimum in the weight; for each
data point and dummy node 2 in D;, we include edge (x. with weight d' d'(x, s;) and associate type to the edge; for every pair 2, w of dummy nodes we include an edge (z, w) with weight 0 (we do not associate type with these edges).
We then compute the minimum weight perfect matching M of the graph Gp. Just like in the proof of Theorem 3.6 the minimum weight perfect matching can be found in polynomial time. The matching M induces an assignment ê of the data points: every point æ is assigned to the cluster i corresponding to the type of the edge of MM incident to x. By construction, the cost of the assignment is equal to the weight wi( (MT) of the matching. Furthermore, for every cluster i E [k], the number of data points in the cluster that are matched with dummy nodes in D; is at most F, hence ||ć!|| - C& < F. Therefore the fairness cost of the assignment is at most F.
Conversely, any assignment C with faimess F induces a perfect matching M of Gr, as follows: For each cluster match data points of cluster C2 in C with opposite attribute values arbitrarily in pairs, and match the remaining |CH |C data points to dummy nodes in D.. The rest of the dummy nodes that are not matched to data point are matched arbitrarily in pairs. The weight of this matching M is then at most the cost of the clustering C, w(M) < c(C). Therefore, c(C) Z w(M) c(C). that is, any assignment C with fairness dominated by the assignment Ć that we derived from the minimum weight perfect matching.
18

---

B Analyzing Fairness Objectives
B.1 Balance and proportional violation-based objectives are pattern-based and mergeable
Proposition B.1. The fairness objectives BALANCE, SUM OF IMBALANCES, GROUP UTILITARIAN, GROUP UTHLITARIAN-SUM, GROUP EGALITARIAN, and GROUP EGALITARIAN-SUN are pattern- based and mergeable.
Proof. Balance- based Objectives: As defined in equation ! the BALANCE objective is always pattern-based by definition. As above, say that we have two sensitive attributes (as this objective is originally defined for ( = 2), called R and B. Then, for a cluster C' E C, |C and |C$ are the number of R and B data points in cluster C, respectively. For two clusterings C and C' that induce the same pattern p. it means that we can pair each C E C with different cluster C" E C' such that |C = | and |C |C*B]. Thus BALANCE(C) BALANCE(C") for all such pairs, and thus BALANCE(C) BALANCE(CY.
We show that BALANCE is also mergeable through simple induction over the number of clusters to be merged. For the base case, take a clustering C and construct a clustering C' in which two clusters
from have been merged (assume without loss of generality that C = {C1, C2. C and C" {0, U2 ...., (C,)). For case of notation, denote by = |Cf$), b = C - |C2 d |C I. Then,
[C1 C2) 6 d [C1 C1) Note that all variables are non-negative. We assume that neither C₁ and C2 are empty. We need to show that the fairness objective is at least as good for the merged clustering than for the original clustering. It is sufficient show that
a () min
c d' )
(a (a+c c + d' b bdd d' a c
min min
< min
(5)
First, this property is true as we can easily prove by considering possible cases:
If a S and c S d
+ 3 = min (+ (), - min (g. a) #ts min
ame budd b.d a+c
Without loss of generality & = min (f. 5). Then, it is easy to see that ab + ad S ab + be + ad < be + 1 5.
atc
b+C
2. If a 2 b and
min (5, 9) min (g. 2)
btd atc
min
b+d a+c
Then,
b+d
the argument from the first case follows identically.
3. If a < b and 2 d, then need to show that min (#, 4) < min
atc b ato
b+d
Without
loss of generality, 64d min
atc b+d b+d+ a-c) Now have cases:
If g < d then < et
atc + ab + ad S ab + ac + ad < be + of S S. which is true btd
since a S
e
d'
g d then
d
c s
ate + bd de s ac ac c², which true since bd S ac +> a bid
e'
b
and 1 < 2 e dee.
4. If a 2 b and c < d, then the proof follows identically to case 3.
Then, if equation 5 holds, then BALANCE(C) S BALANCE(C'). To see this, we there is cluster index i 2 for which BALANCE(C) = BALANCE(C.). Then, BALANCE(CG) (i)) < min (min (8. m (g, 9), so BALANCE(C") = BALANCE(C.)) +
min
BALANCE (C) = BAL. If there is no such cluster i > 2. then BALANCE(C) = min (min (g. b) min (a. ()) I BALANCE(C.). Vi > 2. Then, it follows that BALANCE(C) S (A"
The SUM OF IMBALANCES and MAX IMBALANCE objectives are derived from the BALANCE objective. As they are only a function of the number of data points of different attributes in each cluster, they are also clearly patter-based. To see that SUM OF IMBALANCES is also mergeable,
19

---

consider again the base case of the induction proof. for 2 clusters. For the SUM OF IMBALANCES
objective, note that |C; C + |C; -c |C; C2 + C - the triangle inquality for any clusters C₁ Cj. In merging two clusters C; and Cj from a clustering C, obtaining clustering C', the contribution to the objective of C, U C and the empty cluster is exactly |C; - - + C C (an empty cluster has an imbalance of 0). Since all other clusters remained unchanged, we conclude that SUM OF IMBALANCES(C) 2 SUM OF IMBALANCES(C)) and thus, merging two clusters can only improve the objective.
Remark B.2. As note, the MAX IMBALANCE objective is not mergeable. As a simple objective, take the follwing clustering each of the clusters C1 and C2 has one data point of attribute 1 and two data points of attribute 2. Then, MAX IMBALANCE(C) = 1. The clustering C' obtained by merging clusters C₁ and C2 has MAX IMBALANCE(C")
Finally, for the induction step, mergeability holds for merging a set of wo clusters, then holds for merging set of w + 1 clusters well, by reducing the base case: without loss of generality, denote the w + clusters to be merged by Ci, C. By the induction hypothesis, mergeability holds for merging any clusters, so for UsElu Cj. Then, the base case applies for the clusters Ujeln] C2 and Cw+1-
Proportional violation objectives: First, we easily note that for any two clusterings C and C' that induce the same pattern A we pair each cluster C E C. with different cluster C' E C' such that [C] C"I and |Ca| = |Caal for all attributes a E [4]. Thus, from equation 2 it follows that AC = A C" Va E [t]. Since all proportional violation- based objectives defined are only a function of (A%),.c follows that all clusterings that have the same pattern will also have the same objective value for all four of the proportional violation-based objectives.
a
Finally, will show that they are also mergeable. We show this again by induction over the number of merged clusters for each the objectives. We start with the base case of two clusters, denoted without loss of generality by Ci and C2. We assume that neither C₁ and C2 are empty. We say that G and C2 are part of a clustering C, and we aim to show that the clustering C' in which C1 and C2 got merged will have OBJECTIVE(("") S OBJECTIVE(C)) for OBJECTIVE is one of the GROUP UTILITARIAN, GROUP UTILITARIAN -UMM, GROUP EGALITARIAN, GROUP EGALITARIAN-SUM
objectives. For a sensitive attribute a E [I] assume without loss of generality that C < the following property holds, also known as the mediant inequality:
Then,
IC Cil
C
C2
C
(6)
|C
C2
To see this, note that the left hand side equivalent to:
c G
[C +
C9
<<
+ |CT| - |C1 +
|C
|C2]
|CT| +G/
C1
+ C2l
CC
C
|C
|C2
G1l
[C
11
C2
The right hand side is equivalent to:
CC +
C3
Ca CC2
<
|C |C22
[C2|+1C9]
|Ca/
1C + C
G + C2
(8)
|C9
C2
|Cf|
|C2
<
|C1
|C
[C
C22
By the definition from equation
we have
C
8.
C <
< Oa + A
C
(9)
|
8,
C2 <
< 0g + C
C22
20

---

for clusters C1. C. As C1 and C2 got merged in C", they got replaced by the empty cluster Cp and the merged cluster C₁ U C2 in C². We note that Au Ba. while AC, is the minimum value that satisfies
C9 C2 [1
3 A
I aa CIUC
(10)
+
C21
Using inequalities and 10 with the mediant inequality, we get that
C1
C2
Ba A <
Oa A
[Ci] + C2
(1I)
[C1 + [02
Ba ( 2
Oa m A
[1 + C22
Since by definition, CiUCss is the minimum value that satisfies equation 10 we get that
, I max(A2' ,A..)
(12)
Note that the empty cluster will have A O, Va E [4, so max A ACUC)) = ACUC, This also implies that max A max A. Since the attribute E [4] was chosen arbitrarily, we also get that CEC
C'EC
max Σ
C 2
max AC Σ
(13)
CEC
CEC
aE
[E
and thus the GROUP UTILITARIAN objective cannot increase by merging two clusters. Similarly, for the GROUP UTILITARIAN-SUM since A < min(A A and A C,UC, < max(A > and all other clusters have the same proportional violation both clusterings, we also get that Σ A 2 Σ A Since the attribute [4] was chosen arbitrarily, we also get that CEC
OEC
ΣΣA2ΣΣA eEV| CEC aE([] CEE
(14)
and thus the GROUP UTILITARI UTILITAAIAN-SUS objective can also not increase by merging two clusters.
Furthermore, equation 12 implies that max(A ACCCC> S max(Açi A which in turn implies
that max A max
Since this holds for any arbitrary a E [1]. it also implies that
CEC
CEC
max AC CE( aE(1),CEC'
AC Z
(15)
and thus the GROUP EGALITARIAN objective cannot increase by merging two clusters. Finally, since
0 = A < min A and A CLCCs < max(Aç) A and all other clusters have the same Since CEC
proportional violation in both clusterings, also get that Σ AC Z Σ AÇ Since the attribute
CEC
was chosen arbitrarily, also get that
max Σ A aEI)
max (
Σ AC
a:
(16)
CEC
CEC
and thus the GROUP EGALITARIAN-SUM objective cannot increase by merging two clusters.
For the induction step, the proof is identical to the proof for the BALANCE objective: if mergeability holds for merging set of clusters, then it holds for merging set of + clusters well, by reducing to the base case: without loss of generality, denote the w + 1 clusters to be merged by Ci,... Cw++1. By the induction hypothesis, mergeability holds for merging any clusters. for USe[w] Cj. Then, the base case applies for the clusters UsE[w] Cj and C for all objectives.
21

---

Ct'
11
12(e,
BBR
BBR
X
Pr(-1,0)
Ps(1,0)
X
Pa(-1,0)
BBR
BBR
C2
C2'
P
Pa(e. -1)
(b)
Figure 3: (a) An illustration of clustering under for non-patter based fairness objectives. (b) An illustration of the (P)) sets for non-mergeable fairness objectives.
B.2 A discussion on pattern- based and mergeability properties
Example non-pattern based fairness objectives. As mentioned in the introduction, informally, pattern-based fairness objective computes per-cluster fairness quantity that only depends on the number data points from each sensitive attribute. practice, many fairness objectives satisfy this property, they aim operationalize different versions of proportional representation. with the goal of having balanced clusters among different sensitive attributes. Objectives that define fairness through the proportion of ie-centers that closest to them not pattern -aaeed-baaed, since they do not depend on the number of other nodes of different attributes the same cluster but rather on equalizing the proportions of k-center assignments to different attributes [17 41 45) the average distance between points of different groups to their centers [1.. For example, the definition in Ghadiri et al. [31] states that for groups R (red) and B (blue), the faimess objective is defined for a clustering C' as
(f(S,C)X*) f(S,Cn [3]
(SS,C) max
(17)
R
where A is the subset of points from X' with attribute A. Take the following set of points: 3 over- lapping points 3 32, 2g, with 31 B, B, E R, and 3 overlapping points T4, 35, 34, 26 different coordinates than the first 3, with 24, 25 B, E R. Then, the clustering C1
{x1 ve h C2 (I3, I4,25, 25 has non-zero fairness objective value with respect its true centers (by computing the centroids). The clustering C₁ (I1, I2, æ3}. C²23 {x Iy, J. however, has the same pattern as (C1, C2), but fairness objective value with respect its true centroids. Even we evalute (C1, C2) with respect to the centroids of (C,, C2), it still has a non-zero fairness objective value. See Figure 3 (a) for illustration.
Example of non-mergeable fairness objectives. As discussed in the introduction, a mergeable objective means that the objective value only improve stay the same when merging any number of clusters. While many fairness objectives are mergeable, we give an example below of non-mergeable objectives. We note that objectives that enforce minimum number of data points in each cluster tend to not be mergeable. For example, the 7-ratio objective defined by [32 is non-mergeable, where the objective is defined as:
Σ I1x; E C))(((())=)2TT Σ I(x; (la,CCp C,) Vj [k] and Va [4]
(18)
The 7-ratio enforces minimum number of the total points that must go in each cluster, so empty clusters violate the mergeability condition on the fairness objective (since the number of clusters k is fixed).
Pareto front approximation gap gets arbitrarily large without mergeability. We rely on the assignment problem to provide approximation for the clustering problem when computing the
22

---

Pareto front, which works for pattern based and mergeable fairness objectives. However, for fairness objectives that are pattern- based but are not mergeable, if we apply directly Algorithm II without using a modified fairness function to filter the dominated patterns and adjust the clusterings, as we did in the proof of Theorem 3.5 then the resulting approximation ratio no longer necessarily bounded, as we show in the example below. We showcase this for the r-ratio objective.
We construct dataset X such that [ 8m that contains 8 sets of points each on the plane. Each point has a sensitive attribute, denote by b (blue) or (red). We denote these sets by (P: (e))) constructed in the Euclidean space with the following coordinates (see Figure (b) for an illustration):
Pi contains 2m 1 blue points situated at coordinates (-c, 1)
P2 contains 2m 1 red points situated at coordinates at (c, 1)
P3 contains 1 blue point situated at coordinates (1,0)
Pa contains 1 red point of situated at coordinates (1,0) 0)
Pg contains 2m 1 blue points situated at coordinates (c, -1)
P' contains 2m 1 red points situated at coordinates (-c, -1)
Py contains 1 blue point situated at coordinates (-1,0)
* Ps contains 1 red point situated at coordinates (-1,0)
Set e < 1 and &o = 4. Then, the cost of not assigning the points at (1,0) and (-1,0) centers outweighs the benefits of assigning 2 centers the points clustered near (0, 1) or (0. -1). Therefore, the best k-means and k-median clustering yields centers S {(0, 1), (1, (0,-1),)))),)
their own 8m
We set T = 1/ as our fairness constraint, which constrains every center to have exactly m red points and exactly blue points. Observe that the optimal quality way & to assign such points to sq is to assign m - 1 of the red points in P2 and m - 1 of the blue points in P3 to S2 (in addition to the two points assigned to 82 by the unfair /-mmens/mmedins clustering). So the center at $2 clusters together points separated by distance 2 on the plane. Even if we allow moving the location of 82 after the assignment, the clustering cost still lower bounded by(2m - 2)1/P, since the best center is unit distance from 2(m 1) points. Symmetrically, we do the corresponding assignment to 84 and get a clustering cost lower bound of 2(2m 2)P
2 sets of m
Setting our centers be S {00, 1), (0, 1), (0, -0),1,, (0, (0,-1)}, the assignment function d* with optimal quality under the fairness constraint maps m points from each of Pı and P2 to s and maps the remainder of the points from P1 and Pz. as well as the points in P3 and P1 to s². Symmetrically, we do the corresponding assignment to sğ and s with the points from Ps. Po. Pr, and Ps. This clustering achieves clustering cost at most ((8m-4) 4 (2))) where the first term comes from the 8m 4 points in sets Pt: P2, Po. Pg and the second term comes from the points in sets P3, P4. Py. Pg.
Let & be the lowest cost assignment to centers S, and let 5th be the best possible centers for ø. Then we have that:
S
2(2m 1/
(19)
((8m - 2) + 44 4(V2))))//
Considering the k-means the k-median clustering objectives, get (8m 4)e" < 1, since set
e < 1 Therefore,
8m.
c(o, St c(0 S*)
lim
(20)
Thus, for any constant b, the assignment Pareto set is not (b, 1) multiplicative approximation for the clustering Pareto set for non-mergeable fairness functions. This justifies the need for modified algorithm for mon-mergeable fairness objectives that can change the set of centers while searching for the best assignment, described in Appendix A
23

---

C Datasets details
For all datasets, we subsample 000 data points, as the datasets sizes are prohibitively large. For the Adult and Census datasets, we use all numerical features available in the data and embed them in Euclidean space. For the BlueBike dataset, we use the starting and ending latitude and longitude as coordinates, directly embedded in Euclidean space. For all datasets, the gender of users is self-reported. [able[] the characteristies of all datasets.
Table 1: Data and experimental details.
# of features
Sensitive attribute
6
Adult Census1999
5
Gender
0,05
66
Gender
0,001
BlueBike 4
Gender 0,01
We note that some datasets naturally cluster into fairer clusters than others. For this reason, setting 5 too high renders a single point the Pareto front, since the vanilla clustering itself will be fair for proportional violation-based objectives. fact, the proportional violation value will be equal to For this reason, we experiment with various values of ò, reported in Table for the experiments presented in the main text.
D Repeated-FCBC: Experimental Details
As described in the main text, we investigate alternatives for faster recovery of the Pareto front in the case of two objectives: clustering cost and fairness. We employ a re- cently proposed linear programming method that bounds the clustering objective and optimizes a fairness objec- tive, up to an approximation, denoted the FCBC algorithm (Algorithm in Esmacili et al. (26)). We implement the FCBC algorithm repeatedly by discretizing over the clus- tering cost space. We perform sweep over the upper bound U values, setting its minimum value equal to the clustering cost of vanilla clustering algorithm and its max value equal constant times the clustering cost of a vanilla clustering algorithm, for some chosen constant. We deseribe the approach formally in Algorithm 2 with an illustration in Figure
FCBOUs
Falmesa Objective
FCBCIU))
Clustering Objective
Figure 4: An illustration of implement- ing the repeated FCBC algorithm as the clustering cost upper bound U varies.
We compare the Pareto front recovered from Algorithm 2 with the Pareto front recovered from the dynamic programming approach in Algorithm on all the real-world datasets in Figure in Section 4 setting Unax = Umin C, where Umin is the clustering cost of a vanilla clustering a algorithm (in our case, k- k-means++), C 1.5, and N = 50. We note that setting C equal to 1 is equivalent to constraining the clustering cost in the FCBC algorithm to be equal to the vanilla clustering algorithm cost.
Running time comparison. We illustrate in Figure 5 the running time comparison between the dynamic programming approach from Algorithm [ labeled as 'Dyn Progr', and the repeated FCBC approach from Algorithm labeled 'FCBC', for samples of different sizes of all the datasets. We showcase two objectives, GROUP UTILITARIAN and GROUP EGALITARIAN, since the original FCBC algorithm (26 is designed only for these two, among the five objectives we described in Section 4 We note that Algorithm [Tass similar running time for all other objectives. The experimental running time follows the analysis presented in Section 3 for A 2 clusters and 2 sensitive attributes, one would expect a running time of On²)).
24

---

Algorithm 2 Repeated FCBC for recovering the Pareto Front
Input:
Umin Umax, N, CLUSTERING-OBI FAIRNESS-OBI.
Step Discretize the interval [Umin: Umax]: j: set lj (Umax Umax) /N and
for i < to N do
Set U, = mmn 1
Step 2: apply the FCBC algorithm for the discretized clustering cost bound sequence (U;), adding
results to the recovered Pareto front approximation XFOBC, initialized to X 0:
for 4- to do
XF < FCBB ((PBC(UU CLUSTERING-OBIA CLUSTRRNNGODD,,FFARTRTSSSSOOL,
Output: X
Adult
Census
BlueB kc
Running (seconde)
200
Dyn Progr FCBc
Running time (swconde))
250
Dyn Progr
FCBC
Running time (sarondi))
Dyn Progr FCBC
1000
230
1100
100
1000
50
50
100
200
300
400
500
100
200
300
400
500
100
230
300
400
800
Datasel
Datasol si2e
Delasel size
Group Util
(b) Group Util
(c) Group Util
Adult
Census
BlueBkk
Dyn Progr
Dyn Progr
Dyn Progr
Running lime (seconde)
200
FCBC
Running time (secondd))
FCBC
Running Emno (bacands)
200
FCBC
200
1500
1:50
100
1:00
100
50
80
100
200
300
400
500
100
200
300
400
500
100
200
300
400
600
Dalasel size
Datasel size
Dataset size
(d) Group Egalit
Group Egalit
(f) Group Egalit
Figure 5: Running time comparison with our dynamic programming approach from Algorithm 1 la- beled as 'Dyn Progr', and the repeated FCBC approach from Algorithm labeled as 'FCBC' for each dataset (by column) and for the GROUP UTILITARIAN and GROUP EGALITARIAN objective (by row).
E
Additional Experiments
We present experimental results the three datasets and the five fairness objectives defined in Section & = 3 clusters in Figures 6 a We note that results are qualitatively similar as for k 2 clusters. As mentioned in the main text, we note that the Pareto front need not be strictly convex for two minimization objectives, nor strictly concave for a minimization objective and maximization objective (as in the of the clustering objective and the balance objective), since it simply consists of the undominated points.
For the interested reader, also showcase the Pareto front for the SUM OF IMBALANCES objective, for all three datasets, for A = 2 and = 3, in Figure g We note that since this objective is best suited for data with relatively equal proportions between the two groups, subsample equal proportions of each gender for each of the three datasets, Adult, Census, and BlueBike.
25

---

Add
0.2
0.8
710
Chslnein
100
313
725
(a) Balance
(b) Group Util
(c) Group Util-Sum
(d) Group Egalit
(c) Group Egalit-Sum
Cartu
Campue
0100
00000
Curampg CIE
1302
Claterigg.o car.
Quakiing 2011
Curraing Cc
Chateingoo car
(f) Balance
g Group Util
(h) Group Util-Sum
(i) Group Egalit
i Group Egalit-Sum
DuaOhe
0.8
202
022
Chuakinn
Clacsinggo
(k) Balance
() Group Util
(m) Group Util-Sum (n) Group Egalit
(o) Group Egalit-Sum
Figure 6: Pareto front recovered by Algorithm I for the Adult, Census, and BlueBike datasets (by row), for various faimess objectives (by column), for ls = 3 clusters.
Adult
Census
BlueBlke lik
1.0
Dyn Progr FCBc
Dyn Progr FCBc
Dyn Progr FCBC
Proportioral violation
0.8
Progertional violalion
Proportonnal violatin
0.25
0.20
0.6
0.4
0.10
0.38
0.0
0.0
0.00
700
725
750
775
800
5000
10030
11000
410
420
430
440
Clustering coet
Clustering cost
Cluster ing cost
(a) Group Util
(b) Group Util
(c) Group Util
Adull
Census
BlueBike
Dyn Progr
0.5
Dyn Frogr FCBc
Proportional vielation
0.6
FCBC
Proportional viclelion
0.4
Progortonnll vioiation
0.15
0.4
0.9
Dyn Progr
0.10
FCBC
0.2
0.05
0.0
0.0
0.00
720 Clustering cost
8600 Clustoring cost
10000
420
Clustering
(d) Group Egalit
(e) Group Egalit
(f) Group Egalit
Figure 7: Pareto front recovered by Algorithm I (labeled as 'Dyn Progr', in bluc) and by Algorithm 2 (labeled as 'FCBC', in orange) for the Adult, Census, and BlueBike datasets (by column) and for the GROUP UTILITARIAN and GROUP EGALITARIAN objectives (by row), for clusters.
26

---

BlueBike
Sum Imbea mibaknnees
5
Sum of limba Imbsatances
60
60
of
20
4200
2300
2310 Clustering cost
Clustering cost
Clustering cost
(b)
(c)
Adult
BlucBike
Sum inbalennce
Sum of Intrllances
20
20
15
16
10
10
Clustering cost
Clustering cost
Clustering cost
(d)
(c)
(f)
Figure 8: Pareto front recovered for the SUM OF IMBALANCES objective for the Adult, Census, and BlueBike datasets (by column), for k: 2 (top row) and i = 3 (bottom row) clusters.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We provide clear summary of our results in the abstract and introduction, stating all conditions needed for the results to hold, We summarize the experiments presented in the paper, with details in the main section and the Appendix.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper discusses all the necessary conditions for the results hold. In particular, all our algorithms require that the first objective (the clustering objective) is based on metric and that the second objective (the fairness objective) is pattern-based. Algorithm also requires that the fairness objective is mergeable. We give theoretical bounds for the rumning time of all algorithms and we showcase the rumning time empirically for the algorithms present in the experimental section. We clearly state the datasets and parameters used. We discuss limitations the discussion section in detail.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
28

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All our theoretical results clearly state the necessary conditions in the body of the theorems (e.g.. Theorems (32233) require a clustering objective based on a metric and a pattern-based fairness objective, while Theorem 33.4 requires mergeable fairness objective. The main paper contains sketches of all proofs and the Appendix contains all the detailed proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems. The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the pseudocode of all algorithms used in the paper and the Appendix, with detailed parameters choices, instantiation details, and number of runs. All the code and data is available at (tiis link
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
29

---

(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the code and data is available this link All experimental details provided the main paper as well as in the Appendix for reproducibility of results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
public/gust wwtec//ggigs//eeeeeeeeeeeeeeeeee http///eeeeeieoonooooooioeeeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all experimental details (choices of input, parameter settings, data details, and number of runs) in the main paper well the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
30

---

Answer: [No]
The results do not require error bars, as there is always the same set of Pareto points recovered for the Pareto front for the assignment problem when using standard vanilla k-means clustering algorithm (in our case, k-means++) as an input to our algorithms. We subsample the data once and regarded fixed from there on.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide details on the machines used to run the experiments, the libraries needed, as well as empirical running time analysis in the paper, both in the Experiments section as well as in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttps://eurrpss.. httpet//iittt//////p/.poppppppaa
Answer: [Yes]
Justification: The paper conforms to the NeurIPS Code of Ethics. In particular, the datasets used are open widely used in related work; we do not use human participants; we discuss societal implications of our method with the purpose of improving fairness in clustering.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
31

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the broader impact of our paper, in particular potential use cases by practitioners who wish to use our method for decision-making choosing an optimal trade-off between clustering and fairness objectives, in cases where the data points represent people.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
32

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite all the datasets used, noting that they are open for use. We cite any code used for the implementation Algorithm properly. All other code written and owned by the authors.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We describe all datasets used, with proper documentation of parameters used, algorithms, and code instructions. All datasets and code are made available at this link
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
33

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "7Q0Ve3gAVr", "reviewer": "Reviewer_eL7E", "summary": "The paper is concerned with finding the Pareto front in fair clustering. Specifically, the clustering cost along with a fairness objective are considered simultaneously. Algorithms that can approximate the Pareto front are shown. The run-time is exponential however for the special fairness notion of sum of imbalances it can be done in polynomial time. The papers also conducts experiments on real world datasets and compares against some baselines.", "questions": "Please respond to the issues under the Weaknesses section above.", "limitations": "Limitations are adequately addressed.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-The objective of the paper is interesting and arguably is what one would like to see in fairness work as it matures. Instead of just satisfying the fairness constraint we would have a full trace of the Pareto front. \n\n-As shown in section 2, the paper considers a number of fairness notions.", "weaknesses": "-The major weakness of the paper is that the results are somewhat unsatisfying theoretically. In particular, the run-time of the algorithm is exponential. It is argued in section 3.3 that this intractability is inherent to the problem. I suspect that some hardness result actually exists but the argument here is not formal. What would be better is to give a theorem that states something like even when the Pareto front is of polynomial size, it cannot be approximated to (2+alpha,1) in polynomial time. \n\n-Further, since the run-time is exponential. Why not consider algorithms that approximate the fairness objective as well, i.e. the approximation would be (2+alpha,beta) where beta is not equal to 1. Unfortunately, the run-time of Theorem 3.2 seems very expensive $n^{O(k)}$ so such approximations might run much faster. Although, there might still exist a hardness result that even forbids such approximations, but it would be very interesting to prove them. \n\nThe following points are more minor: \n\n-Sum of Imbalances objective is a bit restrictive since it ignores proportionality. For example, it would achieve the same value even if the imbalance is large over a large cluster (so small proportional violation) or large over a small cluster (large proportional violation).\n\n-Does this paper have any new implications to the setting of Esmaeili [26]? For example, better approximations or faster run-time? \n\n-FCBC algorithm in page 7 is not elaborated on? It refers to the algorithm in [26], correct?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful questions and comments! \n\n**Theoretical results:** We appreciate the reviewer’s suggestions and we also think that an excellent direction would be some negative/hardness results that can decisively address what approximations can and cannot be obtained in poly-time. Currently, such results are difficult to obtain for the clustering problem for the following reasons: \n\n1. First bottleneck: much of the literature obtains theoretical approximation bounds by solving the *assignment objective as a proxy* for the clustering objective. In doing so, we obtain the $(2 + \\alpha)$-approximation on the clustering cost. Subject to this method, we know of theoretical results stating the we cannot get a $(2+\\alpha,1)$-approximation on the Pareto front for (clustering objective, fairness objective) in poly-time for a range of fairness objectives (Thm 7.1 [26] for fairness objectives that sum across the clusters). \n2. Second bottleneck: the assignment problem is also computationally hard (Thm 5.1 in [26]). This result implies that even a polynomially-sized Pareto curve is hard to compute for the (assignment, fairness) objectives. Even approximating fairness objectives with an additive approximation of $O(n^{\\delta})$, $\\delta \\in [0,1)$ is NP-hard (Thm 7.1 [26]), therefore, an approximation of $(1, O(n^{\\delta}))$ for the (assignment, fairness) objectives is hard.\n\nIn other words, all the guarantees we get are based on **not** relaxing the cost approximation from $(2 + \\alpha)$ to something looser. Allowing a relaxation on the cost approximation may lead to theoretical guarantees on the fairness approximation (e.g. obtaining a $(c + \\alpha, 1)$-approximation for $c > 2$). We think this is an excellent direction for future work, but would require fundamentally different techniques for solving the clustering objective that do not necessarily use the assignment objective as a proxy. We believe this would make for an entire paper on its own, and as such, this is beyond the scope of our paper. \n\n**Potential approximations on the fairness objective:** The repeated-FCBC algorithm does indeed involve an approximation on the fairness objective as well, $(2+\\alpha, c + \\eta)$. Its purpose is precisely to explore the tradeoff between approximations and runtime: what we gain in runtime (FCBC is polynomial), we lose in approximation guarantees. The additive approximation eta on the fairness objective provided by FCBC has no known theoretical bound. We describe this issue further down in this response. In particular, no objectives that sum a measure of unfairness across the clusters allow a poly-time approximation of the form $O(n^{\\delta})$ (Thm 7.1 [26]). Other objectives, such as sum and max of imbalances, allow even a polynomial time algorithm for computing the entire Pareto front (Thms 3.6 and A.5, our work). Such differences in the complexity of different objectives makes it difficult to have a general result that encompasses all objectives. Instead, our dynamic programming technique provides sufficient conditions on the objectives to get a good approximation guarantee of the Pareto front. \n\n**For this paper, we believe that this is the first work to start exploring the tradeoff between approximation guarantees and the runtime complexity for computing the Pareto front.** We think the reviewer’s suggestion of further exploring this tradeoff is an excellent avenue for future work.\n\n---\n\nFor the more minor points:\n\n**Sum of Imbalances:** indeed, this objective ignores proportionality. Its purpose is to demonstrate that the complexity in computing the Pareto front comes exactly from requiring proportionality in the fairness objective. The reason for this difficulty can be explained by a reduction of fair assignment from the exact 3-cover problem [26], which shows that it is NP-hard to find an assignment of minimum cost where all clusters have red and blue points in proportion to the dataset ratio of 1:3. In contrast, simpler objectives that only compute the difference between the number of nodes in each sensitive group across clusters allow poly-time algorithms. \n\n**FCBC algorithm:** described in lines 312-317, 326-328, FCBC is a polynomial-time algorithm for computing a clustering that has a cost bounded by $(2 + \\alpha)U$, for an upper bound on the cost $U$ that is fixed a priori, and a fairness additive approximation, using an LP-type method, indeed proposed by [26] as the reviewer noted. This algorithm computes a single point on the approximated Pareto front. We will include a detailed description of the FCBC algorithm in the final version of the paper. \n\n**Implications for Esmaeili et al [26]:** A contribution of our paper is to adapt FCBC for computing the entire Pareto front by allowing the cost upper bound $U$ to vary: in doing so, we explore the runtime-approximation tradeoff. Although FCBC has a polynomial runtime, in practice, the approximations are far from the true Pareto front. Figure 2 has the following implications: we can gain in runtime by adapting the FCBC algorithm to compute an approximated Pareto front; however, the approximation is quite loose in practice, with no guarantees on the fairness additive approximation factor. The additive approximation factor depends on a particular quantity, $L(U)$, which is the size of the smallest cluster across all clusterings of cost not exceeding $U$. This quantity has no theoretical guarantees and is computationally very expensive to compute in practice (it means iterating over all possible clusterings). In our experiments, repeated-FCBC leads to a very different approximated Pareto front than the one computed by our dynamic programming approach (Figs 2 and 7 from our paper). We consider this insight a contribution of our paper: we adapted FCBC to compute the Pareto front, and we compare it in practice with the Pareto front obtained by dynamic programming.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lTqVTUXc3E", "reviewer": "Reviewer_TW4o", "summary": "This paper considers the Pareto-front between quality and fairness in clustering problems, which captures the trade-off between these two objectives. A clustering is on the Pareto front if its clustering cost and fairness objectives are strictly worse than the pair of other clustering. \n\nThey first consider the assignment problem. Given n data points with group labels and k centers, the goal is to assign data points to centers to form clustering on the Pareto front. They provide a dynamic programming algorithm which computes the Pareto front of the assignment problem in O(kn^{l(k-1)}) time.  \n\nNext, they consider the clustering problem. They first use a vanilla clustering algorithm that achieves an alpha approximation on the cost and then use the algorithm for the assignment problem on computed centers. They show that this algorithm achieves a (2+alpha, 1) approximation on the Pareto front, which means for each algorithm solution, there exists a solution on the Pareto front such that the cost of the algorithm solution is 2+alpha approximation and the fairness objective is strictly better. \n\nThey also show that if the fairness objective is the sum of imbalances for two groups, the Pareto front of the assignment problem can be computed in poly time.", "questions": "1. For the FCBC algorithm, can it be modified such that it can optimize the fairness objective subject to both upper and lower bound on the clustering cost?", "limitations": "Yes, they mentioned the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow. \n2. This paper provides a XP algorithm for the Pareto front for the assignment problem and utilizes it to achieve a (2+alpha, 1) approximation for the Pareto front for the clustering problem.\n3. The algorithm works for a general metric based cost objective and pattern based fairness objective.", "weaknesses": "1. The DP algorithm for the assignment problem is quite straightforward and has a large running time. Although it is NP-hard even for computing the minimum cost clustering with a fairness objective constraint, previous fairness clustering work provide approximation algorithms and FPT algorithms for some fairness objectives.  \n2. The sum of imbalances and the max imbalances objectives seems quite restrictive since they make sense to me for almost balanced two groups.\n\nMinor:\n\n1. Line 254 cost min_i (d(u,i)+d(v,i)) should be min_i (d(u,s_i)+d(v,s_i))\n2. Line 546, formula second inequality d(phi(x), phi^*(x)) should be d(x, phi^*(x))\n\n\n----------------\nafter the response:\nThe comparison of their DP algorithm and the FCBC algorithm for the Pareto front is fair and shows the strength of their algorithm in computing the Pareto front task.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and question! \n\n**Question about FCBC:** we’re not sure why a lower bound on the clustering cost would be desirable, since the clustering cost objective is a minimization objective (hence, lower cost is better). To modify FCBC with a lower bound on the cost guarantee, one can turn the cost minimization objective into a cost maximization objective by switching the sign of the objective and solving k-means clustering by gradient ascent methods; with the inverted objective, FCBC should follow a similar analysis. We note that the focus of our paper is not the FCBC algorithm per se, rather, we adapt it to explore the approximated Pareto front that it can obtain. \n\n**Runtime:** while previous work provides approximation algorithms for optimization clustering under a fairness constraint, none offers a method for computing the Pareto front. We show in Section 4.2 that we can adapt such polynomial-time methods to compute an approximation of the Pareto front; however, what we gain in runtime, we lose in approximation bounds: the repeated FCBC algorithm has an additive approximation on the fairness objective that can get large in practice (we get a different Pareto front, with points quite far away in the objective cost, compared to the dynamic programming approach), and with no theoretical bounds on the additive approximation. \n\nOur main theoretical contribution gives tight approximation bounds to the true Pareto front, needing only some general conditions on the objective functions. In other words, we are agnostic to the specific objective functions used. Furthermore, for some fairness objectives, prior work has shown that there is no polynomial-time algorithm that can offer a $O(n^{\\delta})$-approximation: Thm 7.1 [26] for fairness across clusters objectives. \n\nWhile prior work provides approximation algorithms for clustering objectives with fairness constraints, these methods do not all readily extend to computing the Pareto front. A contribution of our paper is to adapt one such method for computing the entire Pareto front: we adapted the FCBC algorithm [26] that optimizes fairness under a bounded clustering cost by varying the bound on the clustering cost. In doing so, we explore the runtime-approximation tradeoff. We consider this a contribution of our paper: we adapted FCBC to compute the Pareto front, and we compare it in practice with the Pareto front obtained by dynamic programming. Although FCBC has a polynomial runtime, in practice, the approximations are far from the true Pareto front. \n \n**Sum/max of imbalances:** We agree with the reviewer that the sum of imbalances and max imbalances objectives are quite restrictive; in fact, we only give them as examples of objectives for which there are poly-time algorithms for computing the Pareto front. These objectives exemplify where the difficulty of computing the Pareto front arises from: fairness objectives that require clusters to match the group proportions present in the general population are difficult to optimize for even with approximation algorithms (Esmaeili et al [26] and our work). The reason for this difficulty can be explained by a reduction of our problem from the exact 3-cover problem, detailed by Esmaili et al [26] which shows that it is NP-hard to find an assignment of minimum cost where all clusters have red and blue points which match a dataset ratio of 1:3. In contrast, simpler objectives that only compute the difference between the number of nodes in each sensitive group across clusters allow poly time algorithms. We would be glad to clarify this point in the final version of the paper. \n\n**Minor comments:** we thank the reviewer for noticing these minor issues, we will fix them in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5hhdXFQnmw", "reviewer": "Reviewer_RJfp", "summary": "The authors consider an important problem in the realm of fair clustering in this work-- is it possible to output the entire Pareto fairness-utility frontier when undertaking fair clustering? This can allow practitioners to answer questions of the form-- \"how much utility can be sacrificed to improve fairness of the model?\" and constitutes a problem setting where the practitioner is willing to be suboptimal in one objective to allow for gains in the other. This is an overlooked yet pertinent problem and the authors provide novel approaches for outputting the entire Pareto fairness-quality curve for fair clustering. More specifically, the authors define two general classes to cover fairness and utility notions in clustering, and then propose exponential algorithms for tracing the Pareto frontier under these definitions. Notably, they provide an intractability result with regards to their algorithm taking exponential time in the worst case. Finally, they also propose a polynomial time algorithm under a specific fairness notion for the assignment (not clustering) problem, where the cluster centers are assumed to be fixed.", "questions": "Please see the weaknesses section. Each of the points above can be considered a question. Also note that owing to the strengths and weaknesses listed above, the paper's contributions currently constitute a technically solid, moderate-to-high impact work, which forms the basis for my score.", "limitations": "The authors have sufficiently discussed limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper formulates and studies an important problem of outputting the entire fairness-utility Pareto frontier. The authors propose a number of novel algorithms for the clustering/assignment problems under general definitions they provide (pattern based objectives and mergeable objectives) that generally encapsulate fairness notions. \n- I also appreciate the authors providing the intractability result showcasing that exponential time is the best we can do in the worst case for the general problem, even if the Pareto frontier itself is polynomial. \n- The experiments conducted validate the efficacy of the proposed algorithms.", "weaknesses": "- I am somewhat unsure of how general the definitions of the fairness notions are-- for instance, can the authors discuss whether other popular notions such as social fairness by Ghadiri et al (https://arxiv.org/pdf/2006.10085) fall into the proposed categorization? Currently, the definitions seem to mostly apply to Balance and the notions covered in Esmaeili et al (https://arxiv.org/pdf/2106.07239), so more discussion on what other fairness definitions (given the vast literature in fair clustering) follow the assumptions of the paper (pattern based objectives and mergeable objectives) would be useful information to have for readers.\n- In the abstract the authors state: \"for perhaps the most natural fairness objective: minimizing the sum, over all clusters, of the imbalance between the two groups in each cluster\". I am curious about where this statement comes from? To my best knowledge, no other prior work has considered this definition of fairness in fair clustering, but I would be happy to be corrected if I am mistaken. Either way, it would be good to discuss why the authors make this statement.\n- While a minor issue, multiple idiosyncracies and issues have been identified with the Adult dataset (https://arxiv.org/pdf/2108.04884) and it would be better to use more recent versions of the US Census data (such as from the folktables package) if possible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the questions and positive feedback! \n\n**Definitions of fairness:** The notions of fairness we discuss cover a range of fairness definitions used in a significant part of the literature, focused on group fairness notions. We would be glad to include a discussion on additional definitions in the final version of our paper. For some definitions, the notion of a Pareto front does not apply: for example, the socially fair k-means clustering notion proposed by Ghadiri et al 2021 [29] defines a single optimization objective that already incorporates fairness (by minimizing the max distance between points in each group and their cluster centers). With this definition, the fairness objective and the clustering objective are not separated in a multi-objective optimization problem, but rather combined in a single objective. Therefore, there is no Pareto front, since this notion applies to a multi-objective optimization problem. For Ghadiri et al, the problem is about how close an algorithm can approximate the optimal solution. For other definitions of individual fairness, such as recent adaptations of individual fairness under bi-criteria optimization problems (Mahabadi and Vakilian 2020 [46]), one can apply a repeated approximation algorithm under an upper bound on one of the objectives (similar to the repeated-FCBC algorithm we proposed). In doing so, one would obtain loose approximation guarantees (see for example the $(\\beta, \\gamma)$-approximation guarantee for individual fairness proved by Mahabadi and Vakilian 2020 [46]). Dynamic programming approaches would not directly apply, however, we think this would be an excellent avenue for future work.\n\n**Sum/max of imbalances:** The sum of imbalances and max of imbalances objectives are indeed not previously defined in the literature: we introduce them as simple examples of objectives for which the Pareto front can be computed in polynomial time using a novel approach that adapts a graph matching argument to our clustering setting. We denoted them as natural due to their simplicity and we use them to exemplify that not all fairness objectives render the Pareto front problem difficult. We are happy to clarify this point in the final version of the paper.\n\n**US Census datasets:** We appreciate the reviewer’s suggestion of using newer versions of the Census data — we would be glad to include an empirical analysis on the data obtained from the folktables package in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6ZzOE9uBjI", "reviewer": "Reviewer_95VK", "summary": "The paper studies fair clustering from a novel and quite fresh perspective. So far in the literature, fairness in clustering has been mostly defined as an additional constraint the solution should satisfy. Given that definition, algorithms are trying to optimize the clustering objective (usually some metric objective) subject to the fairness constraints (with the exception of the Esmaeili et al. NeurIPS 2021 paper that reverses the roles of fairness and objective). On the other hand, the paper at hand tries to create the Pareto front of the clustering solutions. This is merely a set that contains all solutions that are not dominated at at least one objective (either clustering cost or fairness value) by any other solution.\n\nAt first the authors define the necessary characteristics of the fairness notions their framework can capture, while giving plenty of examples of specific notions that can be handled by their algorithm. Then, they given a DP algorithm that solves exactly the assignment version of the problem (cluster centers are fixed). This algorithm runs in exponential time. Moving forward, they show how any approximation algorithm for the vanilla clustering problem can be combined with the DP algorithm in order to give approximations of the Pareto front for the general problem. Furthermore, they show that in the general case you cannot hope to get an algorithm that runs in polynomial time for their problem. Finally, for a newly introduced fairness notion they demonstrate that the Pareto front can be computed efficiently.", "questions": "Do you think that your framework can be expended to capture notions of individual fairness as well?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) I believe that this new perspective on fair clustering is interesting.\n2) The theoretical results are solid and are adequately accompanied by experimental evaluation.\n3) The presentation is clean.", "weaknesses": "1) The paper would benefit from more motivation on why the Pareto front would be helpful in real life applications of fair clustering.\n2) The main results are not really practical from a runtime perspective.\n3) It seems like the framework cannot capture any notions of individual fairness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and positive feedback! \n\n**Individual fairness definitions:** To first answer the question: we think our framework is best suited for notions of group fairness, where there is some additional information about the nodes aside from their features used in the clustering objective. For individual fairness definitions, the only information available are the features themselves, making individual fairness and clustering objectives correlated (improving individual fairness in a clustering also makes the clustering cost smaller). Under some such definitions, the problem can be thought of as a single-objective optimization problem (e.g. Jung et al 2019 [37], Ghadiri et al 2019 [29]). For such problems, there is no Pareto front. For recent adaptations of individual fairness under bi-criteria optimization problems (Mahabadi and Vakilian 2020 [46]), one can apply a repeated approximation algorithm under an upper bound on one of the objectives (similar to the repeated-FCBC algorithm we proposed). In doing so, one would obtain loose approximation guarantees (see for example the $(\\beta,\\gamma)$-approximation guarantee for individual fairness proved by Mahabadi and Vakilian 2020 [46]). Dynamic programming approaches would not directly apply, however, we think this would be an excellent avenue for future work. \n\n**Motivation for computing the Pareto front:** Computing the Pareto front would be helpful for central decision makers who are balancing different objectives: for example, in facility location problems where a central agent decides on the location of facilities (e.g. buses, hospitals, etc) based on the location of individuals within a certain region. It is well-known that people of lower socio-economic status often travel longer distances [1] and have fewer health facilities in their region [2]. A decision maker has multiple objectives to balance: minimal travel time for the entire population and equal access to facilities for different populations. The Pareto front allows the decision maker to balance these objectives in the optimal way: how much improvement can a group of people gain by moving a facility slightly away from the solution given by a single objective (e.g. by performing k-means)? \n\nComputing the Pareto front for facility location problems with multiple objectives has a long history motivated by such questions, with real-world case studies in the Singapore road network [3] and ambulance placement in Barbados [4]. Further applications are found in extensive surveys [5]. We would be happy to include a more comprehensive motivation including real-world applications in the final version of the paper. \n\n[1] Preston, John, and Fiona Rajé. \"Accessibility, mobility and transport-related social exclusion.\" Journal of transport geography 15, no. 3 (2007): 151-160.\n\n[2] Felland, Laurie E., Johanna R. Lauer, and Peter J. Cunningham. \"Suburban poverty and the health care safety net.\" Washington (DC): Center for Studying Health System Change, 2009.\n\n[3] Huang, Bo, P. Fery, L. Xue, and Y. Wang. \"Seeking the Pareto front for multiobjective spatial optimization problems.\" International Journal of Geographical Information Science 22, no. 5 (2008): 507-526.\n\n[4] Harewood, S. I. (2002). Emergency ambulance deployment in Barbados: A multi-objective approach. Journal of Operations Research Society, 53, 185–192.\n\n[5] Farahani, Reza Zanjirani, Maryam SteadieSeifi, and Nasrin Asgari. \"Multiple criteria facility location problems: A survey.\" Applied mathematical modelling 34, no. 7 (2010): 1689-1709.\n\n**Runtime:** We think exploring faster algorithms is an excellent direction for the future. In this first analysis of the Pareto front for clustering and fairness objectives, we uncover the following complexities: \n- Some objectives are more difficult than others: fairness objectives that sum over clusters do not allow a good poly-time approximation (Thm 7.1 [26]), whereas sum/max of imbalances objectives allow poly-time computation of the Pareto front through a reduction to a matching problem (Thms 3.6 and A.5 in our work). \n- Overall, our main theoretical contribution gives tight approximation bounds to the true Pareto front, needing only some general conditions on the objective functions. In other words, we are agnostic to the specific objective functions used.\n- We explored faster heuristics by adapting approximation algorithms that optimize fairness under a bounded clustering cost to recover the entire Pareto front; while such algorithms are polynomial, the approximation bounds are worse than what we obtain by dynamic programming; in practice, such algorithms obtain a very loose approximation of the Pareto front. We consider this a contribution of our paper: we believe that this is the first work to start exploring the tradeoff between approximation guarantees and the runtime complexity for computing the Pareto front.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate all reviewers’ suggestions and positive comments. In particular, reviewers found our proposed problem **novel** and **interesting**, and with **solid theoretical contributions**.  

In this general response, we’d like to comment on a few main threads opened by reviewers:  

**Runtime**: one of the main comments is on the runtime of our proposed dynamic programming algorithm in computing the Pareto front. We note the following:

1. While previous work provides approximation algorithms for optimization clustering under a fairness constraint, none offers a method for computing the Pareto front. On the question ‘can we have faster algorithms with worse approximation bounds?’, the answer is yes. Our paper provides (the first, to our knowledge) such exploration: We show in Section 4.2 that we can adapt such polynomial-time methods to compute an approximation of the Pareto front; however, what we gain in runtime, we lose in approximation bounds: the repeated FCBC algorithm has an additive approximation on the fairness objective that can get large in practice (we get a different Pareto front, with points quite far away in the objective cost, compared to the dynamic programming approach), and with no theoretical bounds on the additive approximation. 
2. For fixed number of clusters and number of sensitive attributes, the runtime of our dynamic programming algorithm is polynomial; the complexity arises from allowing the number of attributes and the number of clusters to vary. In related work on computing Pareto fronts in multiobjective optimization problems, objectives considered in these problems do not run the problem of an additional varying quantity, such as the number of clusters in our case. As a side note, recent faster approaches such as MOEA/D reduce the running time by dividing the problem in subproblems and solving them simultaneously (Zhang and Li 2007 [60]); this approach works best for objectives with continuous and convex Pareto fronts, as well as for linearly separable objectives. In our problems, we do not benefit from such properties, since the Pareto front need not be convex, and the clustering cost is not separable: reassigning a point to a different cluster changes the centers of both the original cluster and the new cluster. We would be glad to include a more extensive discussion on related work and running time in the final version of the paper.
3. Overall, our main theoretical contribution gives tight approximation bounds to the true Pareto front, needing only some general conditions on the objective functions. In other words, we are agnostic to the specific objective functions used. Both theoretical and empirical analysis highlight the complexity of this problem: certain objectives do not allow even a good poly-time approximation (objectives that sum fairness across clusters, as seen in previous work), whereas other objectives allow a poly-time algorithm (objectives such as sum/max of imbalances, as exemplified by our work). 

**Limitations of sum/max of imbalances:** A few reviewers have pointed out limitations of the sum/max of imbalances objectives. We agree that such objectives are simple and only apply in limited settings; we do not propose them as ideal objectives, but rather give them as examples for which we can compute the Pareto front in polynomial time. These objectives exemplify where the difficulty of computing the Pareto front arises from: fairness objectives that require clusters to match the group proportions present in the general population are difficult to optimize for even with approximation algorithms (Esmaeili et al [26] and our work); in contrast, simpler objectives that only compute the difference between the number of nodes in each sensitive group across clusters allow poly-time algorithms. 

Our paper is agnostic to specific objectives chosen; we highlight the main contribution of our paper as giving sufficient conditions for general classes of fairness and clustering objectives in order to be able to compute the Pareto front — the choice of which objectives may be of most use lies with a central decision-maker who can adjust the objective design based on of specific applications of clustering with fairness considerations.

We agree with all reviewers that this work opens several follow-up questions, from obtaining faster algorithms with even looser approximation guarantees on either the clustering or fairness objective, to extending this work to individual fairness objectives. We believe this to be a testament to an interesting problem that opens new avenues for research.

Meta-review: This paper initiates the study of reporting the Pareto front of the fairness-quality tradeoff for fair clustering, under various notions of fairness.

As agreed by the reviewers, the topic is new and well motivated. However, as also pointed out by the reviewers, the major weakness is that the main result, which is an algorithm to report the (approximate) Pareto front, is exponential time. This makes the algorithm completely impractical. 

Nonetheless, the suggested quantitative study of the tradeoff between fairness and quality is important, and may potentially generate high impact/many followup works. The conceptual value of the proposed new direction deserves to be presented in the conference.
Decision: Accept (poster)