Proportional Fairness in Clustering: A Social Choice Perspective

Authors: leon  kellerhals
jannik  peters
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 10:46:16

Abstract: We study the proportional clustering problem of Chen et al. (ICML'19) and relate it to the area of multiwinner voting in computational social choice. We show that any clustering satisfying a weak proportionality notion of Brill and Peters (EC'23) simultaneously obtains the best known approximations to the proportional fairness notion of Chen et al., but also to individual fairness (Jung et al., FORC'20) and the ``core'' (Li et al., ICML'21). In fact, we show that any approximation to proportional fairness is also an approximation to individual fairness and vice versa. Finally, we also study stronger notions of proportional representation, in which deviations do not only happen to single, but multiple candidate centers, and show that stronger proportionality notions of Brill and Peters imply approximations to these stronger guarantees.

Main paper: 
 relations between proportional fairness notions: 
 In this section, we prove the relations between proportional fairness [Chen et al., 2019] , individual fairness [Jung et al., 2020] , and the transferable core [Li et al., 2021] . We first define the notions.The idea of proportional fairness is the following: If there is a candidate c such that at least n k agents are closer to c by a factor α than to their closest cluster center in the outcome W , then we say that the agents will deviate to c. If there is no such candidate, the outcome satisfies α-proportional fairness.Definition 1. For α ≥ 1 an outcome W satisfies α-proportional fairness, if there is no groupN ′ ⊆ N of agents with |N ′ | ≥ n k and c / ∈ W such that α • d(i, c) < d(i, W ) for all i ∈ N ′ .While (2 -ε)-proportional fair outcomes need not exist (for any ε > 0), 1 + √ 2 -proportional fair outcomes can be computed for any metric space [Chen et al., 2019, Micha and Shah, 2020] .To define individual fairness, denote by r N,k (i) be the radius of the smallest ball around an agent i ∈ N that encloses at least n k agents, i.e., rN,k (i) = min{r ∈ R : |B(i, r) ∩ N | ≥ n k }.We drop the subscripts N and k if clear from context. For this definition to properly work, we additionally need the assumption that N ⊆ C, i.e., any agent can be chosen as center. Otherwise, a secluded group of agents without any possible cluster centers around them would never be able to get a center close to them in the outcome. Indeed, this is a plausible restriction in metric clustering, as oftentimes the centers may be picked from the (infinite) set of points in the metric space.Definition 2. For an instance with N ⊆ C, for β ≥ 1 an outcome W satisfies β-individual fairness if d(i, W ) ≤ βr N,k (i) for all i ∈ N .It is known that an outcome satisfying 2-individual fairness always exists, while there are instances with no (2 -ε)-individually fair outcome [Jung et al., 2020] .The transferable core2 notion is based on the concept of transferable utilities from game theory. Comparing to proportional fairness, the notion considers the average utility for each group.Definition 3. For γ, α ≥ 1, an outcome W is in the (γ, α)-transferable core if there is no group of agents N ′ ⊆ N and candidate c / ∈ W with |N ′ | ≥ γ n k and α i∈N ′ d(i, c) < i∈N ′ d(i, W ).It is known that the for any γ > 1 there are outcomes in the (γ, max(4, 3γ-1 γ-1 ))-transferable core while there need not be outcomes in the (γ, min(1, 1 γ-1 ))-transferable core [Li et al., 2021] .Example 1. Consider the instance depicted in Figure 1 (right) with k = 5 and the associated graph distance metric. Assume that cluster centers can only be placed on the depicted agents. We have n k = 2; thus any two agents are able to deviate to another center. The outcome W = {1, 2, 3, 6, 9} satisfies 1-proportional fairness: The agents 1, . . . , 4 have distance 0 to a center, while every remaining agent has distance at most 1 to a center.To see the difference between proportional fairness, individual fairness, and the transferable core, consider the same instance with k = 4, so n k = 2.5. Here, the outcome W = {1, 2, 6, 7} satisfies 1-proportional fairness, however it does not satisfy 1-individual fairness. Agent 8 could look at their 2 closest neighbors, 5 and 9, both at a distance of 1. However, the distance of 8 to the outcome is 2.Observe that W also is not in the (1, 1)-transferable core. Here, for the group N ′ = {8, 9, 10} and candidate c = 9, we havei∈N ′ d(i, c) = 2 < i∈N ′ d(i, W ) = 4. ⋄We first show that proportional and individual fairness are the same up to a factor of at most 2. Proof. Let W ⊆ C be an outcome satisfying α-proportional fairness, j ∈ N be any agent, andTheorem 1. Let α, β ≥ 1. If N ⊆ C,N j = {i ∈ N : d(i, j) ≤ r(j)}. As N ⊆ C, there is an i ∈ N j with d(i, W ) ≤ αd(i, j);otherwise the coalition N j deviates to candidate j. Thus, by the triangle inequality,d(j, W ) ≤ d(i, j) + d(i, W ) ≤ (1 + α)d(i, j) ≤ (1 + α)r(j), and hence W satisfies (1 + α)-individual fairness. Now suppose the outcome W satisfies β-individual fairness. Let N ′ ⊆ N with |N ′ | ≥ n k and c / ∈ W be an unchosen candidate. Take i * ∈ N ′ to be the agent in N ′ furthest away from c. If N ⊆ C, then the radius r(i * ) containing ⌈ n k ⌉ agents is at most as large as the most distant agent in N ′ , i.e., there is an i ′ ∈ N ′ with r(i * ) ≤ d(i * , i ′ ) ≤ d(i * , c) + d(c, i ′ ). Then d(i * , W ) ≤ βr(i * ) ≤ β(d(i * , c) + d(c, i ′ )) ≤ 2βd(i * , c). If N = C, then, since |N ′ | ≥ n k , we have r(c) ≤ d(c, i * ); thus d(c, W ) ≤ βd(c, i * ). Therefore, d(i * , W ) ≤ d(i * , c) + d(c, W ) ≤ (1 + β)d(i * , c), and thus W also satisfies (1 + β)-proportional fairness. Indeed, we also show that all three provided bounds are tight. Theorem 2. For every α, β ≥ 1 and ε > 0, there are instances with N = C for which there exists (1) an outcome which satisfies α-proportional fairness, but not (1 + α -ε)-individual fairness, and (2) an outcome which satisfies β-individual fairness, but not (1 + β -ε)-proportional fairness. Moreover, there are instances with N ⊆ C for which there exists (3) an outcome which satisfies β-individual fairness, but not (2β -ε)-proportional fairness.It is easy to see that the (1, α)-transferable core implies α-proportional fairness. For γ > 1 however, the (γ, α)-transferable core does not imply any meaningful proportional fairness approximation (consider n k agents on one point and (γ -1) n k agents "far" away). Hence, we focus on the other direction and show that a proportional fairness approximation implies one to the transferable core.Theorem 3. An outcome satisfying α-proportional fairness is in the γ, γ(α+1) γ-1 -transferable core for any α ≥ 1 and γ > 1.Proof. Let W ⊆ C satisfy α-proportional fairness. Let N ′ ⊆ N be a group of agents of size n ′ ≥ γ n k , c /∈ W , and shorten η = ⌈ n k ⌉. Further, assume the agents N ′ = {i 1 , . . . , i n ′ } are ordered by their increasing distance to c, i.e., d(i j , c) ≤ d(i j+1 , c) for every j ∈ [n ′ -1]. Let J 0 = {i 1 , . . . , i η } and j 0 ∈ J 0 such that d(j 0 , W ) ≤ αd(j 0 , c); such an agent must exist due to α-proportional fairness. Next, for λ = 1, . . . , n ′ -η, we inductively define J λ = {i 1 , . . . , i η+λ } \ {j 0 , . . . , j λ-1 }, and choosej λ ∈ J λ such that d(j λ , W ) ≤ αd(j λ , c) ≤ αd(i η+λ , c) (note that |J λ | = η). Thus, n ′ -η λ=0 d(j λ , W ) ≤ α n ′ z=η d(i z , c) ≤ α i∈N ′ d(i, c).(1)Next, for each i ∈ N ′′ = N ′ \ {j 0 , . . . , j n ′ -η }, we can bound the distance to W as follows:d(i, W ) ≤ d(i, c) + d(c, j 0 ) + d(j 0 , W ) ≤ d(i, c) + (1 + α)d(i η , c). (2) Note that d(i η , c) ≤ 1 n ′ -|N ′′ | n ′ z=η d(i z , c) as each of the summands is at least d(i η , c). Thus, i∈N ′′ d(i, W ) ≤ i∈N ′′ d(i, c) + (1 + α)d(i η , c) ≤ (1 + α) |N ′′ | n ′ -|N ′′ | n ′ z=η d(i z , c) + i∈N ′′ d(i, c).(3)Asn ′ ≥ γ n k and |N ′′ | = η -1 ≤ n k , we have |N ′′ | n ′ -|N ′′ | ≤ 1 γ-1 . In all, i∈N ′ d(i, W) is the sum of (1) and (3), which is at mostα+1 γ-1 + α + 1 i∈N ′ d(i, c) = γ(α+1) γ-1 i∈N ′ d(i, c). (4) Hence, W is in the γ, γ(α+1) γ-1 -transferable core.We remark that the denominator 1 γ-1 in α is inevitable. This is because for γ ≤ 2, the γ, 1 γ-1transferable core may be non-empty [Li et al., 2021, Theorem 18] . We complement the above upper bound with an asymptotically tight lower bound. Theorem 4. For any α ≥ 1, γ > 1, and ε > 0 there exists an instance in which an α-proportional fair outcome is not in the γ, γα+1 γ-1 -ε -transferable core.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We discuss several lower bounds and incompatibilities throughout the paper. We do not really make any assumptions (except being given a metric space), run no experiments, and we discuss computational issues in Section 3.4 Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
fairness notions for multiwinner voting axioms: 
 In this section we show a connection between the research on computational social choice, specifically approval-based multiwinner voting (also known as approval-based committe (ABC) voting) and the fairness notions for clustering. We will first give a primer on ABC voting and introduce our metric JR axioms. We then focus on two of those axioms and show that (1) they are satisfied by existing, simple algorithms, and (2) they imply the best known approximation guarantees to proportional and individual fairness, the transferable core, and the q-core (see Definition 5 below). For the latter two notions, we are even able to improve upon the best currently known approximation guarantees.Finally, we will focus on the case when the candidate set is infinitely large (i.e., when we are in the Euclidean space and every point is a candidate): In this setting, the above algorithms become hard to compute. We combine two approaches to maneuver around this hardness and again match upon the best known approximation guarantees for proportional fairness and the q-core.In ABC voting [Lackner and Skowron, 2022] , we are given a set N of voters (or agents), a set C of candidates, and a committee size k. For each voter i ∈ N we are given a subset A i ⊆ C of candidates they approve. For such preferences, we call a setN ′ ⊆ N of voters ℓ-large if |N ′ | ≥ ℓ n k , and ℓ-cohesive if | i∈N ′ A i | ≥ ℓ.We say that a committee satisfies JR if for every 1-cohesive and 1-large group N ′ there exists ani ∈ N ′ with |A i ∩ W | ≥ 1; PJR if for every ℓ ∈ [k] and ℓ-cohesive and ℓ-large group N ′ it holds that | i∈N ′ A i ∩ W | ≥ ℓ,and remark that there are many further proportionality axioms [Lackner and Skowron, 2022] . Here, JR is short for justified representation. To define our metric JR axioms for voters and candidates in a distance metric, we follow Brill and Peters [2023] (who lifted these axioms for weak ordinal preferences and called them rank-Π) and generalize their notions to look at each distance separately. Definition 4 (Metric JR axioms). Let (X , d) be a distance metric, let N, C ⊆ X . Let Π be a proportionality axiom. An outcome W satisfies mΠ (short for metric) if for all y ∈ R ≥0 , for the ABC voting instance in which each i ∈ N has the approval set B(i, y) ∩ C, the outcome W satisfies Π.For example, an outcome W satisfies mJR if for every y ∈ R and for every group N ′ ⊆ N of at least n k agents whose ball of radius y all contain a common candidate (| i∈N ′ B(i, y) ∩ C| ≥ 1), there exists an agent i ∈ N ′ whose ball of radius y contains a center c ∈ W . We want to point out that mJR is significantly weaker than mPJR. Indeed, to satisfy mPJR, an outcome W may need to contain several candidates c such that d(i, c) > d(i, W ) for all agents i ∈ N , i.e., c is no-ones "first choice" among W ; mJR does not have this property. This makes mJR the more sensible of the two axioms for "vanilla" clustering, in which one only cares about the closest center to each agent. mPJR however, is a natural axiomatic choice for settings such as sortition or even social choice in general: Here, agents may benefit from having more than a single representative. We provide some intuition for mJR and mPJR and this property in the example below.Example 2. To see the differences between the proportionality axioms, consider the instance depicted in Figure 1 (right). First consider instance (a) on the left with N = C = {1, . . . , 10}, k = 4, and the outcome W = {1, 2, 3, 6}. Here, n k = 2.5. First, we note that this outcome does not satisfy 1-proportional fairness: The agents 8, 9, 10 are closer to 9 than they are to the closest winner in W . It does however satisfy mJR: Among every group of at least three agents that have a common candidate within distance y, there is one agent that has a cluster center w ∈ W within distance y. For example, 8, 9, 10 have candidate 9 at distance 1, and the distance of 9 to the closest center is also 1. This outcome does not satisfy mPJR though, since the group 5, . . . , 10 would deserve at least two candidates within distance 1 in W . An outcome satisfying mPJR is W = {1, 2, 3, 9}. For y = 0, only the group {1, . . . , 4} shares a candidate, but also have a center at distance 0.If k = 5, then, to satisfy mPJR, an outcome must contain at least two of the four candidates. But there are outcomes satisfying mJR that contain only one of 1, . . . , 4. This property of mPJR makes it suited for settings in which agents may want to be represented by multiple candidates, e.g., in political settings, in which the candidates end up possessing voting power to represent the agents. ⋄ Independently of Brill and Peters [2023] , Aziz et al. [2024] introduced two notions they call Proportionally Representative Fairness. The first notion is called "discrete" (DPRF), and the second is called "unconstrained" (UPRF). Indeed, DPRF is equivalent to mPJR. UPRF was introduced to tackle the case when the candidate space is unbounded. We discuss how it relates to mPJR and the other fairness notions in the full version [Kellerhals and Peters, 2023] . Aziz et al. [2024] show that an outcome satisfying DPRF (mPJR) also fulfills 1 + √ 2 -proportional fairness. We show hereafter that this already holds for the (much weaker) mJR axiom.We now prove the approximation guarantees implied by mJR. We remark that the bound for the transferable core below improves upon the analysis of Li et al. [2021] . The proof is deferred to the full version [Kellerhals and Peters, 2023] .Theorem 5. Let W be an outcome satisfying mJR. Then it also satisfies 1 + √ 2 -proportional fairness, 2-individual fairness, and is in the γ, 2γ γ-1 -transferable core for any γ > 1.If the candidate space is finite, then an outcome satisfying mJR can be computed in polynomial time by the GREEDY CAPTURE algorithm [Chen et al., 2019 , Micha and Shah, 2020 , Li et al., 2021] . We briefly recall its procedure:GREEDY CAPTURE starts off with an empty clustering W . It maintains a radius δ (initially δ = 0) and smoothly increases δ. If there is a candidate c such that at least n k agents have distance at most δ to c, it adds c to W and deletes the n k agents. If an agent has distance at most δ to a candidate in W , then it is deleted as well. This is continued until all agents are deleted. Example 3. Consider the instance in Figure 2 . Here, with k = 4, GREEDY CAPTURE, would first open one of 1, . . . , 4 with δ = 0 and remove all agents from 1, . . . , 4. Then for δ = 1 it could either open 6 or 9, removing all adjacent agents to it. Then there are two agents remaining, which would be assigned to either 6 or 9 for δ = 2. Thus, in this instance, GREEDY CAPTURE only opens two clusters. ⋄ Proposition 6. Any outcome returned by GREEDY CAPTURE satisfies mJR.Recall that mPJR is equivalent to the DPRF notion by Aziz et al. [2024] . To satisfy their notion, they designed a generalization of the expanding approvals rule from multiwinner voting [Aziz and Lee, 2020, 2021] (in which the agents' preferences over the candidates are ordinal) to the setting of proportional clustering. They refer to this generalization as SPATIAL EXPANDING APPROVALS. As Aziz et al. show, SPATIAL EXPANDING APPROVALS can be computed in polynomial time for finite candidate spaces.In general, SPATIAL EXPANDING APPROVALS behaves similarly to GREEDY CAPTURE. It also starts off with an empty clustering W and a radius δ = 0 as well and additionally gives each agent a budget b i = k n . It then smoothly increases the radius δ. When there is a candidate c / ∈ W for which the agents at a distance of at most δ have a budget of at least 1, it decreases the budget of these agents collectively by exactly 1 and adds c to W . Example 4. Consider the instance in Figure 2 . Here, with k = 4, SPATIAL EXPANDING APPROVALS would give each agent a budget of 4 10 = 2 5 . For δ = 0, it will open a cluster from 1, . . . , 4 and decrease their budgets by exactly 1, for instance it could set the budget of 1 and 2 to 0 and of 3 to 1 5 . Then for δ = 1 it could again open 6 and 9, for instance by removing the budget of 6 and 9 to 1 5 and of 5, 7, 8, 10 to zero. The remaining budget is exactly 1, which would be spent for δ = 10 on 5. Thus, one possible final outcome is {1, 5, 6, 9}. ⋄Remarkably, as shown by Aziz et al. [2024] , it does not matter in which way the budget is subtracted and which candidate meeting the budget is selected; the outcomes of the algorithm will satisfy mPJR in any case. Proposition 7. Any outcome returned by SPATIAL EXPANDING APPROVALS satisfies mPJR.We now turn to fairness measures implied by mPJR. As any outcome satisfying mPJR also fulfills mJR, the results in Theorem 5 also hold for mPJR. Indeed, mPJR is stricter in the sense that larger groups must also be represented justly by a proportional number of candidates: an α percentage of the population should roughly be close to an α percentage of the centers.This property makes mPJR fit well into metric social choice settings such as sortition. For this, Ebadian and Micha [2024] introduced a fairness notion that measures proportionality in this setting by considering for each agent not only the closest center, but the first q closest centers. In that, their notion called α-q-core naturally generalizes α-proportional fairness; the two are equal when q = 1. Definition 5. For α ≥ 1 an outcome W is in the α-q-core, if there is no ℓ ∈ N and noN ′ ⊆ N with |N ′ | ≥ ℓ n k and set C ′ ⊆ C with q ≤ |C ′ | ≤ ℓ such that α • d q (i, C ′ ) < d q (i, W) for all i ∈ N ′ . Example 5. Consider the instance in Figure 2 with k = 5 and the outcome W = {1, 2, 3, 6, 9}. As mentioned above, W satisfies 1-proportional fairness. For the 3-core however, consider the set N ′ = {5, . . . , 10} deviating to C ′ = {6, 9, 10}. The distance of any member of N ′ to 6, 9, or 10 is at most 3, while the distance to the third most distant center in the outcome is at least 10. Thus, when considering the distances to the third most distant candidate in C ′ , every agent in N ′ would improve by at least a factor of 10 3 . Thus, W is only in the 10 3 -3-core. ⋄We mention in passing that we introduce similar gerneralizations for individual fairness and the transferable core, in which each agent is represented by q candidates instead of one. The definitions and obtained results can be found in the full version of this paper [Kellerhals and Peters, 2023] . Ebadian and Micha [2024] show that, if N = C (every agent is a candidate and vice versa), for a given q, one can compute a 5+ √ 41 2 -q-core outcome. 3 We show that mPJR (or DPRF) provides a better guarantee for the q-core, for all values of q simultaneously. Theorem 8. If an outcome satisfies mPJR, then, for every q ≤ k, it is in the 5-q-core.To prove the theorem, we use two lemmas. The first was first observed by Ebadian and Micha [2024, Lemma 1] and is proven here in a shorter fashion.Lemma 9. Let ℓ ≥ q ≥ 0, let N ′ ⊆ N be a set of agents with N ′ ≥ ℓ n k , and let C ′ ⊆ C be a set of q ≤ |C ′ | ≤ ℓ candidates such that d q (i, C ′ ) ≤ d q (i, W ) for any i ∈ N ′ . Then there is a set N ′′ ⊆ N of at least q n k agents and a candidate c ∈ C ′ such that d(i, c) ≤ d q (i, C ′ ) for all i ∈ N ′′ .Proof. Assume that each agent marks each of their top q choices among C ′ . Then there are at least q|C ′ | n k marks on the candidates. Thus, there is one c ∈ C ′ with at least q n k marks.The next lemma bounds the α-q-core once we find two agents with specific bounds on their distances.Lemma 10. Let ρ 1 , ρ 2 , σ 1 , σ 2 ≥ 0 and let W ⊆ C be an outcome. If for any set N ′ ⊆ N of at least ℓ n k agents and any candidate setC ′ ⊆ C with q ≤ |C ′ | ≤ ℓ there are i 1 , i 2 ∈ N ′ such that d q (i 1 , W ) ≤ ρ 1 d q (i 1 , C ′ ) + ρ 2 d q (i 2 , C ′ ) and d q (i 2 , W ) ≤ σ 1 d q (i 1 , C ′ ) + σ 2 d q (i 2 , C ′ ), then W is in the α-q-core, where α ≤ ρ 1 + 1 2 σ 2 -ρ 1 + (ρ 1 -σ 2 ) 2 + 4σ 1 ρ 2 .Proof of Theorem 8. Let N ′ ⊆ N be a group of agents with|N ′ | ≥ ℓ n k and let C ′ ⊆ C with q ≤ |C ′ | ≤ ℓ such that d q (i, C ′ ) ≤ d q (i, W ) for any i ∈ N ′ . By Lemma 9 there is a candidate c being ranked in their top q among C ′ by q n k many agents N ′′ ⊆ N ′ . Out of N ′′ , let i 1 be the agent maximizing d(i 1 , c) and i 2 be any other agent in N ′′ . Also, let C ′′ ⊆ C ′ be the set of the q candidates closest to i 2 . Then, for every c ′ ∈ C ′′ and every i ∈ N ′′ , we haved(i, c ′ ) ≤ d(i, c) + d(c, i 2 ) + d(i 2 , c ′ ) ≤ d(i 1 , c) + 2d q (i 2 , C ′ ) =: y. In other words, | i∈N ′′ B(i, y) ∩ C| ≥ q. Now mPJR implies that | i∈N ′′ B(i, y) ∩ W | ≥ q. Thus, for every i ∈ N ′′ there is an agent i ′ ∈ N ′′ such that d q (i, W ) ≤ d(i, i ′ ) + y. Since the distance of i 1 to any other agent i ′ ∈ N ′′ is d(i 1 , i ′ ) ≤ d(i 1 , c) + d(c, i 1 ), we have d q (i 1 , W ) ≤ 2d(i 1 , c) + y ≤ 3d q (i 1 , C ′ ) + 2d q (i 2 , C ′ ).As the distance of i 2 to any other agent i ′ ∈ N ′′ is at mostd(i ′ , c) + d(c, i 2 ) ≤ d(i 1 , c) + d q (i 2 , C ′ ), d q (i 2 , W ) ≤ d(i 1 , c) + d q (i 2 , C ′ ) + y ≤ 2d(i 1 , c) + 3d q (i 2 , C ′ ) ≤ 2d q (i 1 , C ′ ) + 3d q (i 2 , C ′ ).Applying Lemma 10 with ρ 1 = σ 2 = 3 and ρ 2 = σ 1 = 2 yields the stated 5-q-core.Whenever the candidate space C is finite, it is straightforward to implement GREEDY CAPTURE and SPATIAL EXPANDING APPROVALS in polynomial time. However, as shown by Micha and Shah [2020] , once C is unbounded and the metric space is only implicitly given (e.g., some distance norm over C = R t ), computing GREEDY CAPTURE can become NP-hard. For Euclidean distances over C = R t , Micha and Shah [2020, Theorem 12] were nevertheless able to give an approximate version of GREEDY CAPTURE, which approximates proportional fairness up to a factor of 2 + ε for any ε > 0 in this special metric space. For general metric spaces, Micha and Shah [2020, Theorem 11] show that in an instance with N ⊆ C, any outcome which is α-proportionally fair when restricted to the instance with candidate set N is 2α-proportionally fair in the whole instance. Aziz et al. [2024] used a very similar approach to this and showed that running SPATIAL EXPANDING APPROVALS on the agents results in a 3-proportionally fair outcome. Combining both approaches, we show that any outcome W satisfying mJR when restricted to the instance with candidate set N ∪ W satisfies 3-proportional fairness in the entire instance. Thus, GREEDY CAPTURE restricted to the agents yields a 3-proportionally fair outcome. The same also applies to mPJR and the q-core.Theorem 11. Consider an instance I with N ⊆ C and an outcome W and let I ′ be the instance with agent set N and candidate set N ∪ W . If W satisfies mJR in I ′ , then W satisfies 3-proportional fairness. If W satisfies mPJR in I ′ , then W is in the 4-q-core for all q ≤ k.4 Stronger fairness bounds for sortition Ebadian and Micha [2024] introduced FAIR GREEDY CAPTURE, a randomized generalization of GREEDY CAPTURE for the setting of sortition. It works in the setting in which N = C and is parameterized by some parameter q ≤ k. Like GREEDY CAPTURE it smoothly increases a radius around each agent/candidate. Once this radius contains at least q n k agents, it selects q of them uniformly at random and deletes in total ⌈q n k ⌉ of these agents. Together with an adequate final sampling step, one can show that this selects each agent with a probability of exactly k n . Ebadian and Micha show that any clustering returned by the algorithm is in the 3+ √ 17 2 -1-core when parameterized by q = 1 and in the 5+ √ 41 2 ≈ 5.7-q-core when parameterized by q > 1. 4 We improve upon their analysis (with a simpler proof) and show that FAIR GREEDY CAPTURE satisfies a better bound for every parameter q ≤ k. Theorem 12. Let N = C and q ≤ k. Then any outcome W returned by FAIR GREEDY CAPTURE parameterized by q is in the 3+ √ 17 2 -q-core.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: This is a purely theoretical owrk. We do not think that any of the examples listed below fit to be discussed here. 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
conclusion and future work: 
 In this paper, we studied proportional clustering from a social choice perspective and showed that our new metric JR axioms enable near-optimal approximations of fairness notions for clustering. An interesting open question, both relevant to social choice and clustering is related to a different relaxation of proportional fairness (or core fairness) introduced by Jiang et al. [2020] . Instead of bounding the factor by which the agents can improve, they bound the size of the deviating coalition (similar to the transferable core). In that sense, no group of size γ n k should exist, who could all deviate to a candidate they like more. In their work, they show that there are instances for which no solution with γ < 2 can exist while for any ε > 0 a solution with γ = 16 + ε exists. Since these results only care about the relative ordering of the candidates, they also translate to clustering. Closing this bound, or improving it for certain metric spaces, seems like an interesting problem. It would be also intriguing to study the probabilistic analog of the core [Cheng et al., 2020 , Jiang et al., 2020] , especially if the results generalize to the q-core and if certain metric spaces admit simple algorithms to compute it.Further, SPATIAL EXPANDING APPROVALS (Section 3.3) is more of a family of algorithms, parameterized by how candidates are selected and how budgets are deducted. Is there any way to axiomatically (or quantitatively) distinguish its different parameterizations? In the context of approval-based multiwinner voting, the Method of Equal Shares [Peters and Skowron, 2020] can be seen as an instantiation of SPATIAL EXPANDING APPROVALS which provides stronger proportionality guarantees than other algorithms in the family. Is something similar possible for our setting, e.g., can one go from proportionality axioms inspired by PJR to axioms inspired by the stronger EJR axiom [Aziz et al., 2017] ? As shown by Brill and Peters [2023, Example 7] the straightforward extension of studying mEJR (or rank-EJR in their notation) is not possible, as outcomes satisfying mEJR may easily fail to exist. However, the metric variant of the PJR+ axiom of Brill and Peters [2023] may be of greater interest in the clustering setting. It is easy to see that SPATIAL EXPANDING APPROVALS satisfies mPJR+. Is it also possible to derive better proportionality or core approximations from mPJR+? Naturally, our work still leaves several open questions when it comes to the approximation factors of our notions. What are the best attainable factors for proportional fairness and the q-core? Further, the questions of Jung et al. [2020] whether the bound of 2 on individual fairness can be improved for Euclidean spaces and of Micha and Shah [2020] 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. 
safeguards: 
 Question: Does the paper describe 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, or scraped datasets)?Answer: [NA] Justification: We do not see any potential high risk.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 a best faith effort.12. Licenses for existing assets 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: [NA] Justification: We do not use any assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
: 
 Fairness notions in clustering usually depend on one decision: whether one takes demographic information (such as gender, income, etc.) into account or whether one is agnostic to it. A large part of work on fair clustering has focused on incorporating such demographic information, starting with the seminal work of Chierichetti et al. [2017] who aimed to proportionally balance the number of people of a certain type in each cluster center. However, not all work on fair clustering relies on demographic information. Independently, and in different contexts, Jung, Kannan, and Lutz [2020] and Chen, Fain, Lyu, and Munagala [2019] instead tried to derive fairness notions from the instance itself. For Jung et al. this lead to their notion of individual fairness: Given a population of size n, with k cluster centers to be opened, every agent should be entitled to a cluster center not further away than their n k -th neighbor. While this is not always achievable, Jung et al. gave a simple algorithm achieving a 2-approximation to this notion. Chen et al. were motivated not by being fair towards individual members of the population (or agents), but towards groups of agents, defining their notion of proportional fairness: no group of size at least n k should be able to suggest a cluster center they all would be better off with. This notion is also not always achievable, and Chen et al. gave a simple 1 + √ 2 -approximation for it.So far, the individual and proportional fairness notions (and some other related fairness notions) have existed in parallel, with similarities between the two being acknowledged but not formalized. 1 In their survey, Dickerson et al. [2023b] highlight this as a general issue in fair clustering: "each notion that was introduced [...] does not refer to or consider the interaction with the previously introduced fairness notions in clustering". Moreover, they call for "other fairness notions in clustering that are also compatible with one another" and "general notions which possibly encompass existing ones".We follow this call and prove proportional and individual fairness, as well as a fairness notion by Li et al. [2021] which we will call the transferable core, to be tightly related to another. In an effort to encompass these three notions, we make use of proportionality axioms from multiwinner voting, an area in computational social choice [Lackner and Skowron, 2022] . Here, given the votes of n agents, the goal is to elect a size-k committee which fulfills some proportionality guarantee. We lift one of the simplest proportionality guarantees (JR) to work with metric distances and prove that any clustering fulfilling our guarantee also fulfills the best approximations for the three notions, all simultaneously.Moreover, such a clustering can be computed in polynomial time. Taking the multiwinner voting approach further, we also look at the lifted version of a stronger proportionality guarantee (PJR). This changes how points (agents) interact with cluster centers as they become represented not by one, but possibly multiple centers. While this is not standard for "vanilla" clustering, it is very fitting for more democratic settings, where the chosen "centers" end up possessing voting power to represent the agents. The resulting proportionality guarantee indeed highly relates to work by Ebadian and Micha [2024] who, motivated by sortition (the randomized selection of citizens' panels [Flanigan et al., 2021] ), introduced a generalization of the proportional fairness notion. Indeed, the multiwinner voting perspective allows us to prove better approximation guarantees for their fairness notion.Our contributions. As our first main result, we provide a simple bridge between proportional fairness and individual fairness (see Section 2). Any approximation of the former is also an approximation of the latter. In particular, for any α, β ≥ 1 we show that (i) any α-approximation to proportional fairness is also an (1 + α)-approximation to individual fairness and (ii) any β-approximation to individual fairness is also a 2β-approximation to proportional fairness. These approximations are tight. We also prove a similar connection between proportional fairness and the transferable core.Our connections imply for instance that bi-criteria approximations that optimize k-means and, say, individual fairness [Vakilian and Yalçıner, 2022, Bateni et al., 2024 ] also maintain approximations guarantees to the other fairness notions. Further, if one wants to show incompatibility of a different clustering notion with approximate proportional or individual fairness, it is sufficient to show this for one of the two notions, instead of creating instances for both (as done by Dickerson et al. [2023a] ).Secondly, in Section 3, we draw a connection to the area of multiwinner voting and reinterpret proportionality notions introduced by Brill and Peters [2023] to work with distance metrics; we call the resulting guarantees mJR and mPJR. Both of these are efficiently computable when the space of possible centers is finite. Remarkably, with simple proofs, we are able to show that any clustering satisfying mJR achieves the best known approximations to individual and proportional fairness notions and the transferable core. For the transferable core, we even improve upon the bound derived by Li et al. [2021] . Finally, motivated by settings such as sortition and multiwinner voting in which agents do not only care about their closest cluster center but are represented by multiple centers, we show that a strong core stability guarantee (introduced by Ebadian and Micha [2024] ) can be achieved by any clustering satisfying mPJR. We also deal with the case in which the center candidate space is unbounded (e.g., in Euclidean clustering settings), in which the above-mentioned algorithms can become intractable. Here, we show that satisfying the proportionality guarantees only for the set of agents is sufficient to obtain constant-factor approximations to proportional fairness and the core stability guarantee by Ebadian and Micha [2024] .Lastly, in Section 4, we focus on sortition: Here, the set of agents and cluster candidates is equal and each agent must be chosen with equal probability. Employing techniques from the above results, we are able to give a simpler proof achieving a better approximation guarantee for the core notion by Ebadian and Micha [2024] .Figure 1 (left) gives an overview over our results and our achieved approximation guarantees. Proofs of some results are deferred to a full version of this manuscript [Kellerhals and Peters, 2023] . and the α-q-core. See Sections 2 and 3 for the corresponding definitions and results. If A → Π, then algorithm A produces outcomes satisfying Π. If Π → Γ, then any outcome satisfying Π also satisfies Γ. If Γ takes a parameter α, then the label specifies the parameter that can be satisfied (for the transferable core, the result holds for all γ > 1). Right: The metric space for the examples used throughout the paper. Edges without labels have length 1, the distance between any two points is given by the length of the shortest path between them.mPJR mJR SPATIAL EXPANDING APPROVALS GREEDY CAPTURE FAIR GREEDY CAPTURE β-IF α-PF (γ, α)-TC α-q-core γ(α+1) γ-1 1 + α 2β 2γ γ -1 2 . 4 1 2 5 3 .Related work. Individual fairness was introduced by Jung et al. [2020] . Since then, follow-up work mainly focused on bi-criteria approximation guarantees [Mahabadi and Vakilian, 2020 , Negahbani and Chakrabarty, 2021 , Vakilian and Yalçıner, 2022 , Chhaya et al., 2022 , Bateni et al., 2024] . Additionally, Han et al. [2023] studied individual fairness for clustering with outliers and Sternbach and Cohen [2023] incorporated demographic information into individual fairness. The individual fairness notion was also carried over to the setting of approval-based multiwinner voting [Brill et al., 2024] . We mention that the name "individual fairness" is also used for other (unrelated) fairness notions [e.g. Kar et al., 2023 , Chakrabarti et al., 2022] .Proportional fairness was first studied by Chen et al. [2019] . Micha and Shah [2020] showed that the GREEDY CAPTURE algorithm by Chen et al. achieves better approximation guarantees in certain metric spaces (including the Euclidean space with the 2-norm) and studied its complexity. Li et al. [2021] introduced notions inspired by Chen et al., which are related to the transferable core concept from algorithmic game theory. Aziz et al. [2024] introduced proportionality axioms and rules directly inspired from social choice theory to proportional clustering. Among other things, they showed that every outcome satisfying DPRF (see Section 3.1) achieves an 1 + √ 2 -approximation to proportional fairness. Further connections to social choice or relations between the above fairness notions of Jung et al. [2020] or Li et al. [2021] remain unexplored, though. Ebadian and Micha [2024] study proportionality in the setting of sortition (see e.g., Flanigan et al. [2021] ), proposing a generalization of proportional fairness and a refined variant of GREEDY CAP-TURE. This variant and its proportionality were used by Caragiannis et al. [2024a] to construct panels whose decisions align with that of the underlying population. The most recent work directly related to ours was created independently and in parallel to ours by Kalaycı et al. [2024] . They study proportional fairness and the transferable core in an incomplete information setting and show that just knowing the order of the distances to between agents and center candidates suffices to achieve a 5.71-approximation to proportional fairness. Caragiannis et al. [2024b] study proportional fairness in a non-centroid based fair clustering setting, in which points are not assigned to cluster centers. Instead they are grouped into clusters and derive utility based on the other agents in their cluster. For this setting, Caragiannis et al. [2024b] also build on the proportional fairness framework studied in this work and also take inspiration from concepts from multiwinner voting: in their case, they adopt the FJR axiom of Peters et al. [2021] . The setting of non-centroid clustering is closely related to the study of hedonic games, with the difference being that in hedonic games, the number of clusters is not pre-determined. See for instance, Fanelli et al. [2021] , Demeulemeester and Peters [2023] , and Fioravanti et al. [2023] for recent works on approximate core stability in hedonic games. Ahmadi et al. [2022] , Aamand et al. [2023] , and Mosenzon and Vakilian [2024] further studied a notion of individual stability for clustering, in which individual agents should not be able to deviate from their clusters. This, however, is unrelated to group stability as studied in this work.Multiwinner voting is the branch of computational social choice theory dealing with selecting multiple instead of just one candidate as a winner. A main branch herein focuses on proportionality. While much of the literature on proportionality, starting with Aziz et al. [2017] , focuses on approval preferences (see Lackner and Skowron [2022] for a recent book on this topic), proportionality notions also exist for ordinal preferences [Dummett, 1984] . These notions were recently strengthened by Aziz and Lee [2020, 2021] and Brill and Peters [2023] , with the latter forming the basis for the proportionality axioms we discuss in this paper. We are further closely related to the works of Caragiannis et al. [2022] and Ebadian et al. [2022] who studied the representation of a given committee by investigating the distances of agents to their q-closest committee member.Model and notation. Let (X , d) be a (pseudo)-metric space with a distance function d :X ×X → R satisfying d(i, i) = 0, d(i, j) = d(j, i) and d(i, j) + d(j, k) ≥ d(i, k). Let i ∈ X be a point. For r ∈ R, define B(i, r) = {j ∈ X : d(i, j) ≤ r} to be the ball of radius r around i. For W ⊆ X , let d(i, W ) = min c∈W d(i, c). For q ≤ |W |, d q (i, W ) is distance to the q-th closest point in W to i. Note that d 1 (i, W ) = d(i, W ) and that d q (i, W ) ≤ d(i, j) + d q (j, W ) for i, j ∈ N .Throughout the paper, we are given a set of agents N = [n] and a (possibly infinite) set of candidates (facilities) C, both of which lie in a metric space (X , d), and a number k ∈ N + . A clustering or outcome is a subset W ⊆ C of at most k candidates. The elements c ∈ W are called centers. Our examples use the (weighted) graph metric in which the points are the vertices of a graph with edge lengths, and the distance between two points is the length of a shortest path between them. 
 
 Appendix: Preprint. Under review.For instance, in a recent tutorial on fair clustering[Awasthi et al.,2022], the two notions were treated as separate unconnected paradigms.We remark thatLi et al. [2021] call this notion just "core", we rename it to avoid confusion with the core notion ofEbadian and Micha [2024].In addition, their randomized algorithm selects each agent with the same probability, a desirable property in the context of sortition, i.e., the randomized selection of citizen assemblies[Flanigan et al., 2021].Recall that the algorithm receives q as a parameter in the input; thus, as opposed to our Theorem 8, the bounds only hold for one q at a time. In a recently updated version of their preprint,Ebadian and Micha [2024] modified their initial version of FGC to additionally satisfy the 6-q core for all q simultaneously. 


Decision: The authors establish interesting connections between different notions of fairness in clustering and also relate this notion to the area of multi-winner voting in computational social choice. All the reviewers agreed that the technical contributions are novel, and some results e.g. the metric variants of axioms have potential for follow-up works. Although the machine learning community mainly studies statistical and algorithmic aspects of fairness, I believe a paper on the axiomatic framework and connections can be useful to the community. Therefore, in addition to the changes suggested by the reviewers, I encourage the authors to discuss/motivate further the implications of various axioms (e.g. mJR or mPJR) on the theory and practice of machine learning fairness.

Reviews: review: paper_summary: paper_summary: This paper provides a methodological contribution by bridging three different notions of fairness in clustering: Individual (where every agent is assigned a cluster center no farther from the $\frac{n}{k}$ neighbor), proportional fairness (no group of size $\geq$ $\frac{n}{k}$ should be able to propose a center that would improve their situation collectively),  and core-fairness (k-clustering is in the core if no group containing $\geq \frac{n}{k}$ agents can strictly decrease their total distance by deviating to a new center). The paper shows that any approximation to proportional fairness is also an approximation to individual fairness and core-fairness and vice-versa. The paper also draws connections to multi-winner voting from computational social science and reinterprets the proportionality fairness notions, leading to efficiently computable metrics (distance-based) under some constraints.
strength_weakness: strength_weakness: I am mostly satisfied with the paper, and I don't see any major weaknesses. It's a decent methodological contribution.
questions: questions: I don't have any specific questions for the authors.
limitations: limitations: yes
paper_summary: paper_summary: The authors study the setting of clustering problem where voters and candidates lie in the metric space and the goal is to elect k candidates representing groups of voters. The authors show interesting connections between this setting and the setting of proportional approval-based committee elections, i.e., they show that the known proportionality axioms can be easily adapted to this setting, yielding the best possible approximations of the notions of proportional fairness and individual fairness defined for the clustering model. In their work, the authors also study the connections between proportional fairness and individual fairness, and analyze the sortition problem.
strength_weakness: strength_weakness: I was a bit surprised that the authors chose to extend the axioms of JR and PJR to their setting, skipping the stronger axioms of EJR, EJR+ and PJR+ mentioned in the same paper of Brill and Peters 2023 that they cite. I think this decision should be explained in the text. But I do not see this as a major weakness of the paper.
questions: questions: 1. Do you think that the axioms of EJR, EJR+ and PJR+ can be adapted to your setting as well?
limitations: limitations: The authors adequately addressed the limitations and there are no potential negative societal impact of their work.
paper_summary: paper_summary: The paper unifies several definitions of fairness in clustering and relates them through approximation ratios. The paper provides theoretical results that 'translate' a definition into another, providing tight bounds for proportional and individual fairness metrics. The paper concludes with a series of results derived from multiwinner voting theory that relate fairness to justified representation.
strength_weakness: strength_weakness: It would be worth discussing the asymmetry in some of the theoretical results (e.g. individual and proportional fairness relate asymmetrically). The alpha-PF -> (gamma, alpha)-TC edge visualization in Fig 1 is slightly confusing: would be good to mention that the gamma(alpha + 1)/(gamma-1) is about relating the alphas.
questions: questions: 1. It would be good to discuss the problem of clustering when the cluster centers are not part of the data but are a la k-means algorithms, found from some continuous space: are any of the results or methods transferable? 

2. It would be great to discuss applications of the work in the context of fair clustering, especially since multi-winner voting is mentioned: what decision-making processes would entail using one vs. more fairness definitions, and how would potential trade-offs derived from the approximation bounds affect the outcome on the population?
limitations: limitations: It would be great to include a more comprehensive discussion on limitations.
paper_summary: paper_summary: This paper studies three different related notions of fair clustering that have been proposed in the literature for metric centroid clustering: (1) proportional fairness, (2) individual fairness, and (3) transferable core. Prior work has separately defined, motivated, and studied the existence and computation of clusterings optimizing all of these notions of fairness. 

The present work attempts to synthesize these different notions in two senses. First, the paper shows that up to [small] constant factors, approximate proportional fairness implies approximate individual fairness and vice versa, and approximate proportional fairness implies approximate transferable core. 

Second, the paper considers metric adaptations of the concepts of justified representation (mJR) and proportional justified representation (mPJR) from approval-based committee selection, an important fair representation problem in computational social choice, and show that these imply approximations of the aforementioned fair clustering concepts. Specifically, any solution satisfying mJR simultaneously satisfies the best known approximations to individual and proportional fairness, and to the transferable core. The paper shows that the Greedy Capture algorithm from prior work on proportional fairness satisfies this mJR property and thus is simultaneously approximately fair in all three senses. Furthermore, the Expanding Approvals algorithm from prior work satisfies the stronger mPJR property. The paper turns to the implications of mPJR for another generalized notion of proportional fairness (the q-core) in contexts where agents measure cost by distance to the q’th most distant center (q=1 being the typical centroid clustering setting) motivated by prior work in sortition (selecting a fair and representative sample of a population), showing that mPJR implies a 5-approximation for all q.

Finally, the paper shows two additional results extending prior work. First, that the known efficient algorithms (e.g., Greedy Capture and Expanding Approvals) can be extended to handle the case of an infinite number of center candidates (e.g., can select any points in the real plane) by simply considering the set of agents as the candidates, and that this restriction preserves small constant approximations of fairness. Second, that the analysis of the Fair Greedy Capture algorithm from recent work on sortition can be tightened to yield a better constant bound on the approximation of the q-core.
strength_weakness: strength_weakness: The work is largely incremental within the fair clustering space, focusing on the relationship between prior notions of fairness, the existence and computation of which have already been studied. The algorithmic contribution is limited in this sense as well, focusing mostly on tightening or demonstrating relationships between guarantees and analysis. In these senses, the impact of the paper may be limited.

Post-rebuttal clarification to the above: The weakness discussed is really with respect to algorithmic contributions, and I agree that connecting different work in the field is a valuable contribution.

A minor comment: In Lemma 9, lines 315-316, I think it should be “…let C’ be a set of…candidates” and “…there is a set $N^{''} \subseteq N^{'}$...”
questions: questions: No pressing questions, though if the authors feel that I have misunderstood the potential of the work for improving clustering algorithms in my weaknesses, I would be happy to hear different perspectives.
limitations: limitations: No concerns.

Comments: comment: Thanks for the answers!
Thank you for the response. Indeed it would be good to discuss this in conclusion.
I acknowledge that I have read the author rebuttal. I appreciate the perspective and agree that the work contributes a helpful connection between different considerations of fairness notions.