Proportional Fairness in Clustering: A Social Choice Perspective
Authors: Leon Kellerhals
Jannik Peters
Venue: NeurIPS 2024 poster (2024)
Keywords: clustering
fair clustering
proportional clustering
social choice
fairness
multiwinner voting
Primary area: algorithmic_game_theory
TL;DR: We show that several previously unrelated fairness notions from clustering are related to each other and to notions from social choice.

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.

Proportional Fairness in Clustering: A Social Choice Perspective
Leon Kellerhals Technische Universität Clausthal leon. www.eelerhhllssu--caasssttaaaaae
Jannik Peters
National University of Singapore petersênus edu. sg
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 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 individual fairness (Jung al., FORC'20) and the fact, we show that any approximation to proportional fairness is also an approximation to individual faimeess 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.
"core" (Li et al., ICML'21).
Fair clustering
Fair decision-making crucial research area in artificial intelligence and machine learning. To ensure fairness, a plethora of different fairness notions, algorithms and settings have been introduced, studied, and implemented. One area in which fairness has been applied extensively is (centroid) clustering: We are given a set of n data points which we want to partition into & clusters by choosing "centers" and assigning each point to center by which is represented well. Fairness now comes into play when, e.g., the data points correspond to human individuals.
Fairness notions in clustering usually depend 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 incorporating such demographic information, starting with the seminal work of Chierichetti et al. [2017] who aimed to proportionally balance the number of people of certain type in each cluster center. However, not all work on fair clustering relies demographic information. Independently, and in different contexts, Jung, Kannan, and Lutz. [2020] and Chen, Fain, Lyu, and Munagala [2019] instead tried derive faimesss notions from the instance itself. For Jung et al. this lead to their notion of individual fairness: Given a population of size n, with & cluster centers be opened, every agent should be entitled cluster center not further away than their F F-th neighbor. While this is not always achievable, Jung et al. gave simple algorithm this notion. Chen 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 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 simple (1 + /2) -aproxxmation for it.
achieving a 2-approximation
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

So far, the individual and proportional fairness notions (and some other related faimess notions) have existed in parallel, with similarities between the two being acknowledged but not formalized.' In their survey, Dickerson et al. [2023b] highlight this as 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 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 simultaneouslyy Moreover, such clustering can be computed in polynomial time. Taking the multiwinner voting approach further, we also look at the lifted version of 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 al., 2021J), 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 simple bridge between proportional fairness and individual fairness (see Section 2). Any approximation of the former is also an approxima- tion of the latter. In particular, for any a, B 2 we show that (i) any a-approximation to proportional fairness is also an (1 + a) 11)++-pppppeaa >approximation to individual fairness and (ii) any 3-approximation to individual fairness is also
ai-aaproximation 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çmer, 2022, Bateni et al., 2024] also maintain approximations guarantees the other fairesss notions. Further, if one wants show incompatibility of 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; 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, clustering satisfying mJR achieves the best known approximations to individual and proportional fairness notions and the transferable core. For the transferable core, 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 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 (c.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].
able to show that any
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 (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].
For instance, in recent tutorial on fair clustering [Awasthi et al., 2022], the two notions were treated as separate unconnected paradigms.
2

---

GREEDY CAPTURE
SPATIAL EXPANDING APPROVALS
FAIR GREEDY CAPTURE
1 2
3 4
3 3.56
10
mJR
mPJR
8
2.41
2/3
9 9-6 6
8-IF
a- a-PF
(
a-q--cre
+
((++1)
10
Figure 1: Left: An overview over connections between and bounds fairness notions, i.e., a- proportional fairness (a-PF), 3-individual faimess (B-IF), the (7, a) -transferabee core ((7, TT-TC), and the a-g-core. See Sections and 3 for the corresponding definitions and results. If A + 11. then algorithm A produces outcomes satisfying 11. If II + I, then any outcome satisfying II also satisfies I. If takes parameter a, 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 the distance between any two points is given by the length of the shortest path between them.
Related work. Individual fairees was introduced by Jung 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şmer, 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 Fuclidean space with the 2-norm) and studied 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 proportional clustering. Among other things, they showed that every outcome satisfying DPRF (see Section 3.1) achieves an (1 + v2) approxxmation 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 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 parallel to ours by Kalayeı et al. [2024]. They study proportional faimess 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 achieve a 5.71 -lapproxximaiion to proportional fairness.
Caragiannis al. [2024b] study proportional faimess 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 al. [2024b] also build on the proportional fairness framework studied in this work and also take inspiration from concepts from multiwinner voting: their case, they adopt the FJR axiom of Peters 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 not pre-determined. See for instance, Fanelli et al. [2021], Demeulemcester 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 notion of individual stability for clustering, in which individual agents should not be able to deviate from their clusters. This, however, unrelated to group stability as studied in this work.
3

---

Multiwinmer 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 given committee by investigating the distances of agents to their q-closest committee member.
space with distance function d: X'X R satisfying d(i, i) = 0, d(i. j) = d(j.t) 1) and d(i. j) + d(j. k) 2 d(i, k). Let é E X' be a point. For r E R. define B(i, r) {j E X: ji S r) to be the ball of radius around i. For W X, let d(i, () = min d(i, c). For S [W] (i W) is distance to the q-th closest point in W to i. Note that d' (i, W') = d(i,, W) and that (i, W) S d(i,.) di W) for i, N.
Model and notation. Let (X,d) be (pseudo)
Throughout the paper, we are given set of agents N = [r]] and (possibly infinite) set of candidates (facilities)) C, both of which lie in a metric space (X' d), and number & N A clustering or outcome is a subset W S C of at most & candidates, The elements e E 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.
2 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 candidate such that at least i agents are closer to by factor a than to their closest cluster center in the outcome W, then we say that the agents will deviate to If there is such candidate, the outcome satisfies c-proportional fairness.
an outcome W satisfies a-proportional faimesss, if there is no group N' S N Definition 1. For a and e & W such that a d(ii c) < d(i, W) for all i E N'. of agents with |N'| 2
I
While (2- e proportional fair outcomes need not exist (for any > 0). (1 + v2) v proportional fair outcomes can be computed for any metric space [Chen et al., 2019, Micha and Shah, 2020].
To define individual fairness, denote by FNA (i) be the radius of the smallest ball around an agent i E N that encloses at least I agents, i.e., a = min(r E I: [B(i, r) n 2 }). We drop the subscripts N and le if clear from context. For this definition properly work, additionally need the assumption that N S C, i.c., 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 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 instance with N C C, for / 2 an outcome W satisfies B-individual fairness if d(i, W) < (,) (i) for all i E N.
is known that an outcome satisfying 2-individual fairness always exists, while there are instances with no (2 - -idiiiiduull fair outcome [Jung et al., 2020].
The transferable core² notion is based on the concept of transferable utilities from game theory. Comparing to proportional faimesss the notion considers the average utility for each group.
Definition 3. For 2 1, an outcome W is in the (7,a)) -taannseereee core if there is no group of agents N' C N and candidate e é W with |N| 2 7 and ΣiEN' d(i, c) < > d(i, W).
It known that the for any 7 > 1 there are outcomes in the (y, max(4, 4, while there need not be outcomes in the (7, min(1, ا-1) -)-trrasfeeeebble core [Li et al., 2021].
2y-1 ) -transferable core 7-1
We remark that Li et al. [2021] call this notion, just "core", we rename it to avoid confusion with the core notion of Ebadian and Micha [2024].

---

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 E = 2; thus any two agents are able to deviate to another center. The outcome W {1, 2, 6,9) satisfies 1 1-proportional fairness: The agents 1, ,,...,, 4 have distance 0 to a center, while every remaining agent has distance at most to center.
To see the difference between proportional fairness, individual fairness, and the transferable core, consider the same instance with k = 4, so F 2.5. Here, the outcome W = {1, 6, 7 satisfies 1- p-rroportional fairness, however does not satisfy 1 1-individual fairesss. Agent could look their 2 closest neighbors, 5 and 9, both at distance of 1. However, the distance of 8 to the outcome is 2. Observe that W also is not in the (1, 1) -taansfeerbbee core. Here, for the group N' ={8,9, 9, 10) and candidate = 9, we have ΣIEN d(i, c) = 2 < EveNy d(i, W) = 4.
2.1 Proportional and individual fairness
We first show that proportional and individual fairness are the same up to a factor of most 2. Theorem 1. Let 3 2 1. N _ C, then an outcome that satisfies a-proportional fairness also satisfies (1 + -iidiiiidllll faimess, and an outcome that satisfies 3-individual fairness also satisfies 23 23-proportional fairness. If N C, then an outcome that satisfies 3-individual fairness also satisfies (1 + propprrtil fairness.
fainnss.
Proof. Let W S C be an outcome satisfying a-proportional fairesss, j N be any agent, and N₂ = li E N: j(i,j) S r(j)}. As N C C. there is an i E N, with d(i, W) S ad(i, j): otherwise the coalition N2 deviates to candidate j. Thus, by the triangle inequality, d(j, W) S d(i,))+ + d(i, W) S (1 +1+a)d +a)d(ii))) & (1 +a)r((()) and hence W satisfies (1 + + -iniiiiiidl fairness.
Now suppose the outcome W satisfies 3-individual faimess. Let N' S N with [N'] 2 & and & W be an unchosen candidate. Take i" e N' to be the agent in N' furthest away from c. If N C. then the radius r(i*) containing [ agents is at most as large as the most distant agent in i.e., there is i' E N' with r(i*) I d(i", ,') I d(i", c) + d(c,t'). Then d(i", W) S (B((i)) s 3(d(i" c)= + d(e, z')) S 23d(i", c). If N = C, then, since [N'|
n we have r(c) S d(c, i"); thus 2 b.
d(c, W) I Bd(c,;"). Therefore, d(i", WW d(i", .c) + d(c, W) (1 + 3)d(i", c), and thus W also satisfies (1 + 3) 3))proportional fairness.
Indeed, we also show that all three provided bounds are tight.
Theorem 2. For every B.B3. 221 and & > O, there are instances with N = C for which there exists (1) an outcome which satisfies a-proportional fairness, but not (1 + a ---iniividual fairness, and (2) outcome which satisfies B 8-individual fairness, but not (1 + 3 s)-proportional fairness. Moreover, there are instances with N S C for which there exists (3) an outcome which satisfies 8 3-individual fairness, but not (23- E) proporrtooal fairness.
2.2 Proportional fairness and the transferable core
It is easy to see that the (I, a transferabbe core implies a- a-proportional fairness. For > however, the (y, ox) transsferaeee core does not imply any meaningful proportional fairness approximation (consider " agents on one point and (y 1) 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 c-proportional is in the (7, ((a+1)) -transferable core for any a 2 and 7 1.
Proof. Let W C C satisfy a-proportional fairness. Let N' C N be group of agents of size n' 2 T e & W, and shorten 1 = - Further, assume the agents N' = {i....., in } are ordered by their increasing distance to c, i.c., d(ij,c) S d(iz+1,c) c) for every j E [n' - 1]. Let Jn = fe.,... in) and jo Jo such that d(jo, W) < ad([jn c); such agent must exist due a-proportional fairness. Next, for = 1, 1...., n¹' - y,. we inductively define JA = (ii,..., x (jo,- ........jj-j 1.. and choose jx JA such that d(jx, W) S ad(ix. c) S ad(iptA;c) e) (note that [Jal 1)). Thus,
Ex - d(ix, W) S a L'' d(iz, c) Elex
(I)
5

---

Next, for each E N" = No \ (oo. .w -w we can bound the distance to W as follows:
d(i,w) _ d(i,c) c) + d(c, Jo) d(jo. w) s d(i, c) + (1 a)d(in, c).
(2)
Note that d(b c) S --| Σ n" = d( 11 c) as each of the summands is least d(fg: c). Thus,
Σ d(i, W S Σ (d(i, c) + + a1+a)d(inn) c)) S (1 + a) n²- Nº Σ d(ii c) + + d(i, c). VEN"
IN
(3)
IEN"
IEN"
As n' 2 k and | = 1j - 1 S
n x we have
n'-IN" S
14
1 7-1
In all, ΣiEN d(i, W) is the sum of
(1) and (3), which is at most
( + + 1) Σ d(i,c) 2(++1)
E d(i,c).
(4)
7-1
IEN
EeN
Hence, W in the (7. [(+1] 7-1
-transferable core.
We remark that the denominator 7 in a is inevitable. This is because for y S 2, the 7: 7-1
transferable 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 a 2 1, 7 > 1, and E > 0 there exists an instance in which an a-proportional fair outcome is not in the (7, T-T 8) transferable core.
2a+1
3 Fairness notions for multiwinner voting axioms
In this section we show a connection between the research computational social choice, specifically approval-based multiwinner voting (also known as approval-basse -based committe (ABC) voting) and the fairness notions for clustering. We will first give a primer 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 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 g-core.
3.1 Metric JR axioms
In ABC voting [Lackner and Skowron, 2022], we are given a set N of voters (or agents), a set C of candidates, and committee size k. For each voter N we are given subset A; C of candidates they approve. For such preferences, we call a set N' C N of voters É-large if [N' > T. and e-cohesive if INENN A,l 2 f. We say that committee satisfies
JR if for every 1 1-cohesive and 1-large group N' there exists an i E N' with |4: n W 2 1; PJR if for every e [k]] and Ê-cohesive and É-large group N' it holds that IUiEN A, n W 2
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 distance metric, we follow Brill and Peters [2023] (who lifted these axioms for weak ordinal preferences and called them rank-II) 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 C X. Let II be proportionality axiom. An outcome W satisfies mIll (short for metric) if for all y E R20, for the ABC voting instance in which each i N has the approval set B y) n C. the outcome W satisfies II.
For example, an outcome W satisfies mJR if for every y E R and for every group N' C N of at least agents whose ball of radius y all contain a common candidate (1 NseN' B(i n ncI 2 1), there exists an agent e N whose ball of radius y contains center E W.

---

8
9
10
1 2
10
5
7
3 4
Figure 2: Metric space for some of the examples. Edges without labels have length 1.
We want to point out that mJR is significantly weaker than mPJR. Indeed, to satisfy mPJR, outcome W may need to contain several candidates с such that d(íi.) > d(í, W) for all agents E N. i... 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 natural axiomatic choice for settings such sortition or 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 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 and the outcome W = (1, 2, 3, 6). Here, n = 2.5. First, we note that this outcome does not satisfy 1 1-proportional fairness: The agents 8, 10 are closer to 9 than they are 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. 9, 10 have candidate 9 at distance 1, and the distance of to the closest center is also 1. This outcome does not satisfy mPJR though, since the group 5...., ., 10 would deserve 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 4) shares a candidate, but also have a center at distance
E
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 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 represent the agents.
Independently of Brill and Peters [2023], Aziz et al. [2024] introduced two notions they call Pro- portionally Representative Fairness. The first notion is called "discrete" (DPRF), and the second called "unconstrained"" (UPRF). Indeed, DPRF is equivalent 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 + v2) propporiol fairness. We show hereafter that this already holds for the (much weaker) mJR axiom.
3.2 Fairness bounds for mJR outcomes
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+ + 22) proportional
27 fairness, 2-individual fairness, and is the (7, 5ー -trunsferuble core for any y >> 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 5 (initially 8 = 0) and smoothly increases 8. there is a candidate such that at least &8r agents have distance at most to it adds to W and deletes the F agents. If an agent has distance at most d to 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 8 = and remove all agents from 1, ...., 4. Then for 8 = 1 could either open 6 9, removing all adjacent agents to it. Then there are two agents remaining, which would
7

---

be assigned to either 6 or 9 for 8 = 2. Thus, in this instance, GREEDY CAPTURE only opens two clusters.
Proposition Any outcome returned by GREEDY CAPTURE satisfies mJR.
3.3 Fairness bounds for mPJR outcomes
Recall that mPJR is equivalent to the DPRF notion by Aziz 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 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.
ordinal) the setting of
In general, SPATIAL EXPANDING APPROVALS behaves similarly to GREEDY CAPTURE. also starts off with an empty clustering W and a radius 8 = 0 as well and additionally gives each agent a budget b. n. It then smoothly increases the radius 8. When there candidate & W for which the agents at distance of at most ó have budget of at least 1, it decreases the budget of these agents collectively by exactly 1 and adds to W.
Example 4. Consider the instance in Figure 2. Here, with = 4, SPATIAL EXPANDING APPROVALS
would give each agent a budget of TO Z. For 5 = 0, it will open cluster from 1, ...... 4 and decrease their budgets by exactly 1, for instance it could set the budget of and 2 to 0 and of 3 to f. Then for å = 1 could again open and 9, for instance by removing the budget of 6 and 9 to | and of 5, 7, 8, 10 to zero. The remaining budget is exactly 1, which would be spent for d = 10 on 5. Thus, one possible final outcome is (1, 5, 6, 9).
Remarkably, as shown by Aziz et al. [2024], does not matter in which way the budget 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 proportional number of candidates: a 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 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 a-q-core naturally generalizes a-proportional fairness; the two are equal when =
Definition 5. For a 2 1 an outcome W is in the a-q-core, if there is no & N and no N' S NN with |N'] 2 f and set C" C C' with q S |C|| l such that d' di, C") di W) for all i E N'.
Example 5. Consider the instance in Figure 2 with A: = 5 and the outcome W 21, 3, 6, 9). As mentioned above, W satisfies 1-proportional fairness. For the 3-core however, consider the set N' 15, .... 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 the third most distant candidate in C", every agent in N' would improve 3 -3-core.
by at least a factor of 10. Thus, W is only in the 10 3
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 candidate and vice versa), for given q, one can compute a 5+VJI -q-core outcome, 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 S k. it is in the 5-q-core.
II addition. their randomized algorithm selects each agent with the same probability, desirable property in the context of sortition, ie., the randomized selection of eitizen assemblies [Flanigan al., 2021].
8

---

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 O, let N' C N be a set of agents with N' 2 l and les C' C C be a set of q S |C*| I candidates such that (ū, C*) S. di, W) for any i E N'. Then there is a set N" S N
of at least o agents and candidate E C' such that d(i, c) S di(i, for all E N
Proof. Assume that each agent marks each of their top g choices among C'. Then there are at least q(C'p R marks on the candidates. Thus, there one C" with at least t marks.
The next lemma bounds the a-q-core once we find two agents with specific bounds on their distances.
Lemma 10. Let PL, P2, 02,02 2 O and let W S C be outcome. for any set N' S N of at least E agents and any candidate set C" _ with q S |C"| S there are i,,12 E N such that (i1, W) S (11 C²) + p2d C²) and d' (iz, W) S 01, (i),C') + o2d"(1y C"), then W is in the a-q-core, where a pi + 02 P + (pI 02)² + 40102
Proof of Theorem 8. Let No C N be a group of agents with |N' 2 & and let C' C C with S. =1C|| S f such that ("(i,C") < di, W) for any i E N'. By Lemma 9 there is a candidate e being ranked in their top q among C" by 9% many agents N" C'.. Out of N" let be the agent maximizing d(i,,e) e) and i2 be any other agent in N Also, let C" C' be the set of the g candidates closest to 12. Then, for every e' E C" and every E N", we have
d(i,c') S c(i,c) + d(c, 12) + d(i2, c') S d(i1. c) + (22 C²) y.
In other words, NENN" B(i,y) 3) ncI 2 q. Now mPJR implies that UIEN" B(i, y) nw 2 g. Thus, for every E N" there is an agent i' E N" such that di W) S d(i,?) + y. Since the distance of i to any other agent i' E N" is d(ii, i') S d(i c) + d(c, 11), we have
d ( W) 2d c) + y 3d (11, C") + 2d C").
As the distance of in to any other agent i' E N is at most d(i', c) + d(c, S d(i,, + (iz, C"). d' (12, W) S d(ii, c) + d' (iz, C²) + y S 2d( (1, c) + 34 3d C*) < 2d (i,, C²) + 3d (i2, C²).
Applying Lemma 10 with P1 d2 3 and P2 01 = 2 yields the stated c-q-
3.4 Dealing with unbounded candidate sets
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 = Rt), computing GREEDY CAPTURE can become NP-hard. For Euclidean distances over C = R 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 + e for any e > in this special metric space. For general metric spaces, Micha and Shah [2020. Theorem 11] show that in an instance with N C C, any outcome which is a- prropoortonnllyy fair when restricted to the instance with candidate set N is 2c- co-pprportionnall 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 3- prropoortionall fair outcome. Combining both approaches, any outcome W satisfying mJR when restricted to the instance with candidate set N U W satisfies 3 propportional 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.
show that
Theorem 11. Consider an instance I with N C C and an outcome W and let I' be the instance with agent set N and candidate set N W.W. If 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 S. 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 S k. Like GREEDY CAPTURE it smoothly increases a radius around each agent/candidate. Once this radius contains at least 9% agents. it selects q of them uniformly at random and deletes in total [ of these agents. Together with an adequate final sampling step, one can show that this selects each agent with probability of exactly &
Ebadian and Micha show that any clustering returned by the algorithm is in the 3+v -1-----crre when parameterized by q = 1 and in the م x 5.7-q-core when parameterized by > 1.* We improve upon their analysis (with simpler proof) and show that FATR GREEDY CAPTURE satisfies better bound for every parameter q S k.
2
Theorem 12. Let N C and q k. Then any outcome W returned by FAIR GREEDY CAPTURE parameterized by is in the 2+v17 -Q-core.
2
5 Conclusion and future work
In this paper, studied proportional clustering from 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 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 y 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 y < 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 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
Further, SPATIAL EXPANDING APPROVALS (Section 3.3) is more of a family of algorithms, parameter- ized by how candidates are selected and how budgets deducted. Is there any way axiomatically (or quantitatively) distinguish its different parameterizations? In the context of approval-base multi- winner 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 propor- tionality 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 EXPA APPROVAL.S 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] whether for (unweighted) graph metrics with N = C' a 1-proportional fair clustering always exist, are still open.
References
A. Aamand, J. Chen, A. Liu, S. Silwal, P. Sukprasert, and A. Vakilian. Constant approximation for individual preference stable clustering. In Proceedings of the 36th Conference Neural Information Processing Systems (NeurIPS), pages 43646 436611 2023.
'Recall that the algorithm receives g as a parameter in the input: thus, as opposed to our Theorem 8, the bounds only hold for one g at a time. In recently updated version of their preprint, Ebadian and Micha [2024] modified their initial version of FGC to additionally satisfy the 6-g core for all q simultaneously.
10

---

S. Ahmadi, P. Awasthi, S. Khuller, M. Kleindessner, J. Morgenstern, P. Sukprasert, and A. Vakilian. Individual preference stability for clustering. In Proceedings of the 39th International Conference on Machine Learning (ICMI.), pages 162: 2022.
P. Awasthi, B. Brubach, D. Chakrabarty, J. P. Dickerson, S. A. Esmaeili, M. Kleindessner, M. Knittel, Morgenstem, S. Samadi, A. Srinivasan, and L. Tsepenekas. Fairness in clustering. https: com/, 2022.
//www. www.rfaaaairrrrrrrer
H. Aziz and B. E. Lee. The expanding approvals rule: improving proportional representation and monotonicity. Social Choice and Welfare, 54:1-45, 2020.
H. Aziz and B. E. Lee. Proportionally representative participatory budgeting with ordinal preferences. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5110-5118. AAAI Press, 2021.
H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48(():461-485, 2017.
H. Aziz, B. Lee. S. Morota Chu, and J. Vollen. Proportionally representative clustering. In Proceedings of the 20th International Workshop Internet and Network Economics (WINE), 2024. Forthcoming.
M. Bateni, V. Cohen-Addad, A. Epasto, and S. Lattanzi. A scalable algorithm for individually fair k-means clustering. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3151-3159, 2024.
M. Brill and J. Peters. Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the 24th ACM Conference on Economics and Computation (ACM-EC), page 301. ACM, 2023. Full version arXiv:2302.01989 [cs.GT].
M. Brill, J. Israel, E. Micha, and J. Peters. Individual representation in approval-based committee voting. Social Choice and Welfare, 2024. Forthcoming.
I. Caragiannis, N. Shah, and A. A. Voudouris. The metric distortion of multiwinner voting. Artificial Intelligence, 313:103802, 2022.
Caragiannis, Micha, and Peters. Can a few decide for many? The metric distortion of sortition. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 235:5660-5677 PMLR, 2024a.
I. Caragiannis, E. Micha, and N. Shah. Proportional fairness in non-centroid clustering, In Proceedings of the 37th Conference Neural Information Processing Systems (NeurIPS), 2024b. Forthcoming.
D. Chakrabarti, J. P. Dickerson, S. A. Esmaeili, A. Srinivasan, and L. Tsepenekas. A notion of individually fair clustering: a-equitable k-center. In Proceedings of the 25th International Conference on Artificial Intelligence and Statisties (AISTATS), pages 6387-6405 2022.
X. Chen, Fain, L. Lyu, and K. Munagala. Proportionally fair clustering. Proceedings of the 36th International Conference on Machine Learning (ICML), pages 1032-1041, 2019.
Y. Cheng, Z. Jiang, K. Munagala, and K. Wang. Group Faimess in Committee Selection. ACM Transactions on Economics and Computation, 8(4))23:1-23:11 2020.
R. Chhaya, A. Dasgupta, J. Choudhari, and S. Shit. On coresets for fair regression and individually fair clustering. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 9603-9625, 2022.
F. Chicrichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In Proceedings of the 30th Conference on Neural Information Processing Systems (NeurIPS), pages 5029-5037, 2017.
T. Demeulemeester and J. Peters. Relaxed core stability for hedonic games with size-dependent utilities. In Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), pages 41:1-41:14 2023.

---

J. P. Dickerson, S. A. Esmaeili, J. Morgenstem, and C. J. Zhang. Doubly constrained fair clustering. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), pages 13267-13293, 2023a.
J. P. Dickerson, S. A. Esmaeili, J. Morgenstern, and C. J. Zhang. Fair clustering: Critique, caveats, and future directions. Neurips 2023 Workshop on Algorithmic Fairness through the Lens of Time, 2023b. Full version arXiv:2406. 15960 [cs.LG].
M. Dummett. Voting Procedures. Oxford University Press, 1984.
S. Ebadian and E. Micha. Boosting sortition via proportional representation. Technical report, arXiv:2406.00913 [es.GT], 2024.
Ebadian, G. Kehne, E. Micha, A. D. Procaccia, and N. Shah. Is sortition both representative and fair? In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), pages 3431-3443, 2022.
A. Fanelli, Monaco, and L. Moscardelli. Relaxed core stability in fractional hedonic games. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 188, 2021.
Fioravanti, M. Flammini, Kodric, and G. Varricchio. e-fractional core stability hedonic games. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), pages 21723-28734, 2023.
B. Flanigan, P. Gölz, A. Gupta, B. Hennig, and A. Procaccia. Fair algorithms for selecting citizens' assemblies. Nature, 596:548-5555 552, 2021.
L. Han, D. Xu, Y. Xu, and P. Yang. Approximation algorithms for the individually fair k-center with outliers. Journal of Global Optimization, 87(2):603-618, 2023.
Z. Jiang, K. Munagala, and K. Wang. Approximately stable committee selection. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 462-472. ACM, 2020.
C. Jung, S. Kannan, and N. Lutz. Service your neighborhood: Fairness in center location. In Proceedings of the 1st Symposium on Foundations of Responsible Computing (FORC), pages 5:1-5:15, 2020.
Y. H. Kalayeı, D. Kempe, and Kher. Proportional representation in metric spaces and low-distortion committee selection. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9815-9823, 2024.
D. Kar, M. Kosan, D. Mandal, S. Medya, A. Silva, P. Dey, and S. Sanyal. Feature-based individual fairness in k-clustering. In Proceedings of the 22nd International Conference Autonomous Agents and Multiagem Systems (AAMAS), pages 2772-2774, 2023.
L. Kellerhals and J. Peters. Proportional faimness clustering: A social choice perspective. Technical report, arXiv:2310.1811 [cs.LG], 2023.
M. Lackner and P. Skowron. Multi- Winner Voting with Approval Preferences. Springer, 2022.
B. Li, L. Li, A. Sun, C. Wang, and Y. Wang- Approximate group fairness for clustering. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 6381-6391, 2021.
S. Mahabadi and A. Vakilian. Individual fairness for k-clustering. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 6586-6596, 2020.
E. Micha and N. Shah. Proportionally fair clustering revisited. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), pages 85:1-85:16, 2020.
R. Mosenzon and A. Vakilian. Scalable algorithms for individual preference stable clustering. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS). pages 1 101-1116. PMLR, 2024.
12

---

M. Negahbani and D. Chakrabarty, Better algorithms for individually fair k-clustering. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), pages 13340-13351, 2021.
D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of the 2 ACM Conference on Economics and Computation (ACM-EC), pages 793-794. ACM, 2020.
D. Peters, G. Pierczyúski, and P. Skowron. Proportional participatory budgeting with additive utilities. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 12726-12737,
2021.
H. Sternbach and S. Cohen. Fair facility location for socially equitable representation. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2775-2777, 2023.
A. Vakilian and M. Yalqmer. Improved approximation algorithms for individually fair clustering. In Proceedings the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 8758-8779, 2022.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims including claimed approximation guarantees and connections are shown via proofs
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss several lower bounds and incompatibilities throughout the pa- per. 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 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 separate "I "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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend 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 low or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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 complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
We provide proofs (or references) for all theoretical results given.
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 a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Our work does contain any experimental results.
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 be necessary to either make it 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 to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
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 to reproduce that algorithm.
algorithm, the paper should make it clear how
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
new model (e.g., large language model), then there should
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
We provide no experimental results and use no data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce cc/
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: //ipp..coo ccppppccpppullc///eeecc cerblliicggides....e /CodeSubmia ssionPolicy) 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. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
We provide no experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: We provide no experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, 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 are 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.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state 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 to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
We provide no experimental results.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs 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 NeurIPS Code of Ethics https::/ httpp//pss.ppplllcccccccceetdddd
Answer: [Yes]
Justification: We do not work with human subjects, nor create datasets. We do not see any overlap with the described potential ethics violations.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there 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: [NA]
Justification: This is 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.
17

---

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 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not see any potential high risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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. Lieenses 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 any assets.
Guidelines:
The answer NA means that the paper does 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 (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not any assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip 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 screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No experiments are performed in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor 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.
According the NeurIPS Code of Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No experiments are performed in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 we expect authors to adhere to the NeurlPS 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.
19


Reviews:
[{"review_id": "PcW5grn2fM", "reviewer": "Reviewer_e2hb", "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.", "questions": "I don't have any specific questions for the authors.", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper tackles an interesting topic\n\n+ The paper is well-written, and it makes a significant methodological contribution\n\n+ The methodology is adequately sound and well-explained. Particularly, the connections to multi-winner settings are novel.", "weaknesses": "I am mostly satisfied with the paper, and I don't see any major weaknesses. It's a decent methodological contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "I6WC2HXXqN", "reviewer": "Reviewer_M2yM", "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.", "questions": "1. Do you think that the axioms of EJR, EJR+ and PJR+ can be adapted to your setting as well?", "limitations": "The authors adequately addressed the limitations and there are no potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This is a very good paper. The idea of metric variants of justified representation axioms is interesting and novel - I believe it has a potential to be further studied in follow-up works. The paper is clearly written and the results are technically sound.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for pointing this out. Of course, this deserves a discussion in the conclusion, and we want to add this in the next version.\nIndeed, the Expanding Approvals algorithm satisfies the stronger mPJR+.\nHowever, we were not able to show mPJR+ implies stronger bounds than mPJR.\nAs for EJR and EJR+, it follows from Brill and Peters [2023] that these do not always exist.\nHence, we chose to focus on mJR and mPJR. We also believe that it is interesting that already these weak axioms imply the best approximations to individual and proportional fairness, and to the transferable core.", "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": "XRRnPJVim2", "reviewer": "Reviewer_g3Lo", "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.", "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? \n\n2. 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": "It would be great to include a more comprehensive discussion on limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very-well written, with substantial theoretical contributions. The relationship with prior work is comprehensive and clear, and it does a great job of extracting methods in order to relate and unify different definitions of fairness. The problem posed is important, as fairness in clustering may require different definitions, and as such, knowing how they relate to each other provides insight into the potential trade-offs. I appreciate the examples that show tight bounds for individual and proportional fairness.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Yes, we discuss this in section 3.4. Recall that the agent set N corresponds to the point set in k-means, and the centers are chosen from the candidate set C.\nIn section 3.4, we discuss results for the case that the candidate set is infinite. This also covers e.g. the case when the centers may be chosen from all of the Euclidean space.\n\n2. Generally speaking, fairness notions such as individuality or proportionality are efforts towards modeling what is considered fair. Our work shows that these notions are highly related to another. That is, if my goal is to have a proportionally fair solution, then I implicitly also obtain a solution that is (approximately) individually fair.\nConsidering for example any solution that satisfies mJR, it fulfills the best known approximations to individual and proportional fairness at the same time, so there is not really any trade-off that we are aware of.\nWe hope that this roughly answers your question. Of course, we are happy to further discuss this in the discussion period.\n\nAlso, thank you for the weaknesses you pointed out. We will make sure to improve on these two points in the next version.", "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": "LnjZguO9XG", "reviewer": "Reviewer_qn3s", "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. \n\nThe 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. \n\nSecond, 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.\n\nFinally, 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.", "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": "No concerns.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper does a very good job of providing a comprehensive survey connecting different fair clustering desiderata that have been considered separately in the literature. The result is a convincing story that there is a more “general” phenomenon of proportionality at work in all these group-agnostic structural notions of fairness in clustering. The greatest contribution may therefore be in clarifying the state of the field for future work seeking to extend or build on these notions. It is also nice to see a formal connection between the last several years of work on fair approval-based committee selection in computational social choice and the work in the ML clustering space.\n\nGenerally the writing and discussion is clear. Effort has clearly been put into communicating ideas effectively in the forms of the results diagram in figure 1, illustrative examples, and extensive consideration of related work and the connections between other work and the current.\n\nResults are well substantiated by the formal arguments, and claims are all measured and accurate to what is shown.", "weaknesses": "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.\n\nPost-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.\n\nA 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^{'}$...”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you kindly for the minor comment, you are absolutely correct.\nWe agree that our work has a clear focus on creating relations between the fairness measures.\nHowever, we believe that providing connections and (in-)compatibility between fairness notions is of great importance, and something that has not been considered enough. \nAs we mention in the introduction, this belief is also shared by Dickerson et al. [2023b]; (their manuscript since has been published on arXiv: https://arxiv.org/abs/2406.15960).\nAlso, with the connection to multiwinner voting, we create a new pathway for future work on clustering with fairness measures a la individual or proportional fairness.", "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 would like to express our gratitude to the reviewers for taking the time to carefully review our submission.
We address each of the reviewer's comments and questions below and look forward to further discussions in the coming days.

Meta-review: 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.
Decision: Accept (poster)