Fairness in Ranking under Uncertainty
Authors: Ashudeep Singh
David Kempe
Thorsten Joachims
Venue: NeurIPS 2021 Poster (2021)
Keywords: fairness
ranking
uncertainty
posterior distribution
individual fairness

Abstract: Fairness has emerged as an important consideration in algorithmic decision making. Unfairness occurs when an agent with higher merit obtains a worse outcome than an agent with lower merit. Our central point is that a primary cause of unfairness is uncertainty. A principal or algorithm making decisions never has access to the agents' true merit, and instead uses proxy features that only imperfectly predict merit (e.g., GPA, star ratings, recommendation letters). None of these ever fully capture an agent's merit; yet existing approaches have mostly been defining fairness notions directly based on observed features and outcomes.

Our primary point is that it is more principled to acknowledge and model the uncertainty explicitly. The role of observed features is to give rise to a posterior distribution of the agents' merits. We use this viewpoint to define a notion of approximate fairness in ranking. We call an algorithm $\phi$-fair (for $\phi \in [0,1]$) if it has the following property for all agents $x$ and all $k$: if agent $x$ is among the top $k$ agents with respect to merit with probability at least $\rho$ (according to the posterior merit distribution), then the algorithm places the agent among the top $k$ agents in its ranking with probability at least $\phi \rho$.

We show how to compute rankings that optimally trade off approximate fairness against utility to the principal. In addition to the theoretical characterization, we present an empirical analysis of the potential impact of the approach in simulation studies. For real-world validation, we applied the approach in the context of a paper recommendation system that we built and fielded at the KDD 2020 conference.

Fairness in Ranking under Uncertainty
Ashudeep Singh Cornell University Ithaca, NY 14850 ashudeep@cs.com corpeell..oooell...ccccccc
David Kempe
Thorsten Joachims Cornell University Ithaca, NY 14850 t ceecs cornell
University Southern California
Los Angeles, CA 90089 david. m. wempp@@mall...mmmmmmmmmmmmmmmm.. com
Abstract
Fairness has emerged as important consideration in algorithmic decision making. Unfairness occurs when an agent with higher merit obtains a worse outcome than an agent with lower merit. Our central point is that primary cause of unfairness is uncertainty. A principal or algorithm making decisions never has access to the agents' true merit, and instead uses proxy features that only imperfectly predict merit (e.g., GPA, star ratings, recommendatton letters). None of these ever fully capture an agent's 's merit; yet existing approaches have mostly been defining fairness notions directly based on observed features and outcomes.
Our primary point is that it is uncertainty explicitly. The role of observed features is to give rise to a posterior distribution of the agents' merits. We use this viewpoint approximate fairness ranking. We call an algorithm ó-fair (for ø E [o, 1)) if it has the following property for all agents æ and all k: if agent is among the top k agents with respect to merit with probability at least p (according to the posterior merit distribution). then the algorithm places the agent among the top k agents in its ranking with probability at least op.
principled to acknowledge and model the
define notion of
We show how to compute rankings that optimally trade off approximate fairness against utility to the principal. In addition to the theoretical characterization, we present empirical analysis of the potential impact of the approach in simulation studies. For real-world validation, we applied the approach in the context of paper recommendation system that we built and fielded at the KDD 2020 conference.
Introduction
Fairness is an important consideration in decision-making. in particular when limited resource must be allocated among multiple agents by a principal (or decision maker). widely accepted tenet of fairness is that if an agent B does not have stronger merits for the resource than A, then B should not get more of the resource than A. Depending on the context, merit could be a qualification (c.g., job performance), a need (e.g., disaster relief), some other measure of eligibility.
The motivation for our work is that uncertainty about merits a primary reason that a principal's allocations can violate this tenet and thereby lead to unfair outcomes. Were agents' merits fully observable, would be both fair and the principal's 's best interest rank agents by their merit. However, actual merits are practically always unobservable. Consider the following standard algo- rithmic decision making environments: (1) An e-commerce or recommender platform (the principal) displays items (the agents) in response to user query. An item's 's merit is the utility the user would derive from it, whereas the platform can only observe numerical ratings, text reviews, the user's past history, and similar features. (2) A job recommendation site employer (the principal) wants to recommend/hire one or more applicants (the agents). The merit of an applicant her (future) performance the job over period of time, whereas the site employer can only observe (past) grades, test scores, recommendation letters, performance in interviews, and similar assessments.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In both of these examples - and essentially all others in which algorithms are called upon to make allocation decisions between agents uncertainty about merit is unavoidable, and arises from multiple sources: (1) the training data of machine learning algorithm is random sample, (2) the features themselves often come from a random process, and (3) the merit itself may only be revealed in the future after a random process (e.g., whether an item is sold or an employee performs well). Given that decisions will be made in the presence of uncertainty, it is important to define the notion of fairness under uncertainty. Extending the affrrmentioned tenet that "if agent B has less merit than A, then B should not be treated better than A," we state the following generalization to uncertainty about merit, first for just two agents:
Axiom 1. If A has merit greater than equal to B with probability at least p. then a fair policy should treat A at least as well as B with probability at least p.
This being an axiom, we cannot offer a mathematical justification. It captures an inherent sense of fairness in the absence of enough information, and it converges to the conventional tenet as uncertainty reduced. In particular, consider the following situation: two items A, B with 10 reviews each have average star ratings of 3.9 and 3.8, respectively, or two joo applicants A, B have GPAs of 3.9 and 3.8. While this constitutes some (weak) evidence that A may have more merit than B, this evidence leaves substantial uncertainty. The posterior merit distributions based on the available information should reflect this uncertainty by having non-trivial variance; our axiom then implics that A and B must be treated similarly to achieve fairness. In particular, it would be highly unfair to deterministically rank A ahead of B (or vice versa). Our main point is that this uncertainty, rather than the specific numerical values of 3.9 and 3.8, is the reason why mechanism should treat A and B similarly.
1.1 Our Contributions
We study fairness in the presence of uncertainty specifically for the generalization where the principal must rank n items. Our main contribution is the fairness framework, giving definitions of fairness in ranking in the presence of uncertainty. This framework. including extensions approximate notions of fairness, is presented and discussed in depth in $ 2 We believe that uncertainty of merit is one of the most important sources of unfairness, and modeling it explicitly and axiomatically is key to addressing it.
Next, in S 3) we present algorithms for principal to achieve (approximately) fair ranking distributions. simple gorithh the principal may use achieve approximate fairness to mix between an optimal (unfair) ranking and (perfectly fair) Thompson sampling. We show that this policy is not optimal for the principal's 's utility, and we present an efficient LP-based algorithm that achieves an optimal ranking distribution for the principal, subject to approximate fairness constraint.
We next explore empirically to what extent a focus on fairness towards the agents reduces the principal's utility. We do so with two extensive sets of experiments: one described in S 4 on existing data, and one described in 3 "in the wild." In the first set of experiments, we consider movie recommendations based on the standard MovieLens dataset and investigate to what extent fairness towards movies would result lower utility for users of the system. The second experiment was carried out at the 2020 ACM SIGKDD Conference on Knowledge Discovery and Data Mining, where we implemented and fielded a paper recommendation system. Half of the conference attendees using the system received rankings that were modified to ensure greater fairness towards papers, and we report on various metrics that capture the level of engagement of conference participants based on which group they were assigned to.
The upshot of our experiments and theoretical analysis is that in the settings we have studied, high levels of fairness can be achieved at a small loss in utility for the principal and the system's 's users.
Due to space constraints, essentially all proofs, well detailed discussion of related work, given in the supplementary material. Alternatively, a reader may want to read the full version (Singh
al. 202T
2 Ranking with Uncertain Merits
We are interested ranking policies for a principal (the ranking system, such as an e-commerce platform or a job portal in our carlier examples) whose goal is to rank set X' of n agents (such as

---

products or applicants). The principal observes some evidence for the merit of the agents, and must produce distribution over rankings trading off fairness to the agents against the principal's ss utility. For the agents, a higher rank is always more desirable than lower rank.
2.1 Rankings and Ranking Distributions
We use Σ(A²) to denote the set of all rz! rankings, and (x') for the set of all distributions over E(Y) We express a ranking a E [()) in terms of the agents assigned to given positions, i.e., (kk) is the agent in position k. A ranking distribution x E [I()') can be represented by the n! probabilities (o) of the rankings a E E(X). However, all the information relevant for our purposes can be represented
more compactly using the Marginal Rank Distribution: we write Pa.k Eo=o())= (o) for the b, denote
probability under и that agent x E X in position i in the ranking. We let p(a) (p b,,
the n X n matrix of all marginal rank probabilities.
The matrix p(=) is doubly stochastic, i.e., the sum of each row and column is 1. While uniquely defines p(*), the converse mapping may not be unique. However, given doubly stochastic matrix P. the Birkhoff-von Neumann decomposition (Birkhoff) 1946) can be used to compute some distribution π consistent with P. i..., p(r) P; any consistent distribution will suffice for our purposes.
2.2 Merit, Uncertainty, and Fairness
The principal must determine a distribution over rankings of the agents. This distribution will be based some evidence for the agents' merits. This evidence could take the form of star ratings and reviews of products (combined with the site visitor's partially known preferences), or GPA, test scores, and recommendation letters of applicant. Our main departure from past work on individual fairness (following (Dwork et al. 2012)) is that we do not view this evidence as having inherent meaning; rather, its sole role is to induce posterior joint distribution over the agents' merits.
The merit of agent x is v E R, and we write v (V/ )rxx for the vector of all agents' merits. Based on all observed evidence, the principal can infer a distribution I over agents" merits using any suitable Bayesian inference procedure. Since the particular Bayesian model depends on the application, for our purposes, we merely assume that posterior distribution I was inferred using best practices and that ideally, this model is open to verification and audit.
We write I(v) for the probability of merits under r. We emphasize that the distribution will typically not be independent over entries of v - for example, students' merit conditioned on observed grades will be correlated via common grade inflation if they took the same class. To avoid awkward tie- die-breaking issues, we assume that v * for all distinet x. y E X' and all in the support of T. This side-steps having to define the notion of top-k lists with ties, and comes at little cost in expressivity, as any tie-breaking would typically be encoded in slight perturbations to the U2 anyway.
We write (n) for the event that under v, agent x is among the top & agents with respect to merit, i.e. that Ha' 2,k Ugr > H < k. We now come to our key definition of approximate faireess Definition 2.1 (Approximately Fair Ranking Distribution). A ranking distribution x is ø-fair iff
26. POr
P
[
for all agents and positions At That is, the ranking distribution æ ranks at position k above with at least a e fraction of the probability that æ is actually among the top agents according to Furthermore, π is fair iff it is l-fair.
The reason for defining ø- d-approximately fair ranking distributions (rather than just fair distributions) is that fairnsss typically comes at cost to the principal (such as lower expected clickthrough or lower expected performance of recommended employees). For example, if the V. are probabilities that a user will purchase products on an e-commerce site, then deterministically ranking by decreasing Er [t.] the principal's optimal ranking under common assumptions about user behavior; yet, being deterministic, it is highly unfair. Our definition of approximate fairness allows, e.g., a policymaker to choose a trade-off regarding how much fairness (with resulting expected utility loss) to require from the principal. Notice that for ó 0, the principal is unconstrained.
3

---

We remark that the merit values Ug only matter insofar as comparison is concerned; in other words, they are used ordinally, not cardinally. This is captured by the following proposition.
Proposition 2.1. Let - R be any strictly increasing function. Let I" be the distribution that draws the vector (J(vz)) with probability [(w) for all v; that is, it replaces each entry v with f(,)). Then, ranking distribution π is ø-fair with respect to I' if and only if it is ø-fair with respect to I%.
Proof. Because f is strietly increasing, Peer MM (w) immediately implies the claim by examining Definition
Peury [M[]]] for all x and k. This
Proposition 2.1 highlights a key aspect of our fairness definition: we avoid expressing any notion of fairesss when "one agent has just 'a little' more merit than the other." instead arguing that fairness is only truly violated when an agent with more merit is treated worse than one with less merit. In other words, faimess is inherently ordinal in our treatment. This viewpoint has implications for principal seeking "high-risk high-reward" agents, which we discuss in more depth in $ B.2
2.3 The Principal's Utility
The principal's utility can be the profit of an e-commerce site the satisfaction of its customers. We assume that the utility for a ranking a with agent merits v takes the form U(ar | = -i= where wk. is the position weight for position k in the ranking, and we assume that the wx are non-increasing, i.e., the principal derives the most utility from earlier positions of the ranking.
We (k))
The assumption that the utility from each position is factorable (i.e., of the form wy (k)))) is quite standard in the literature (Järvelin and Kekäläinen, [002 Taylor et al. 2008). The assumption that the utility is linear in (o(k) is in fact not restrictive at all. To see this, assume that the principal's utility were of the form w (Vr(K)) for some strictly increasing function f. By Proposition 2.1 the exact same faimness guarantees are achieved when the agents' merits U, are replaced with f(uz); doing so preserves fairness, while in fact making the principal's utility linear in the merits. Some common examples of utility functions falling into this general framework are DCG with W. loga (1+ +)), Average Reciprocal Rank with wt = 1/k, and Precision @ K with wy 1 S KJ/K.
When the ranking and merits are drawn from distributions, the principal's 's utility is the expected utility under both sources of randomness:
( (T) Ea v~r (U(o w)]
(2)
2.4 Discussion
Our definition is superficially similar to existing definitions of individual fairness (e.g.. (Dwork eet al. 2012; Joseph et al. 2016)), in that similar observable features often lead to similar outcomes. Importantly, though, it side-steps the need to define a similarity metric between agents in the feature space. Furthermore, it does not treat the observable attributes (such star ratings) themselves as any notion of "merit." Instead, our central point is that agents' features should be viewed solely as noisy signals about the agents' merits and that comparison of their merits and the principal's uncertainty about the merits - should determine the agents' relative ranking. That moves the key task of quantifying individual fairness from articulating which features should be considered relevant for similarity, to articulating what inferences can be drawn about merit from observed features.
Merit as an Abstraction Boundary between Data and Fairness. One may argue, rightfully, that from an operational perspective. our approach simply pushes the normative decisions into determining I. For example, if the distribution I' were biased in favor of or against a particular group, then the decisions of a supposedly fair algorithm (with respect to H) would in fact be unfair to that group. However, our main point that normative decisions should indeed be encoded in the distribution r. To appreciate the conceptual approach, first notice that any algorithm implicitly encodes normative decisions, merely in the outputs it produces, which will favor some agents over others. The key question is how these normative decisions are encoded, how they can be articulated, and whether they could possibly be audited. If they are encoded in ad hoc algorithmic choices, articulating and auditing them may be difficult.

---

As an example, consider an admissions officer at a university, who believes that the GPA or SAT scores of affluent applicants may be higher due access to tutors, rather than true academic potential. One approach to compensate for this advantage could be to subtract some (wealth-dependent) amount from an applicant's 's scores. A more principled approach - and the one we advocate - is for the admissions officer to explicitly express the possible distribution of merits given the test scores and wealth. The suitable notion of fairness is then derived by our framework, rather than as an ad hoc choice. A substantive discussion can then be had around the assumptions that go into the admission officer's particular choice of distribution, whether a different distribution would be more suitable, etc.
In a sense, the notion of merit, and distributions thereof, serves as a clean abstraction boundary between available data, and the desired fairess and utility. We argue that frequently, the difficult question to address is not so much what is "fair," but what the data truly reveal about an agent's 's merit, The latter should be articulated by domain experts, whereas the role of computer science is to provide frameworks for deriving fair algorithms given the merit distributions, as well as statistical approaches that may guide the derivation of I from data.
Randomization, Fairness, and Single-Shot Scenarios. In the introduction, we discussed two possible applications in which fairness is desirable: ranking of products in online e-commerce, and ranking of job applicants. We note that these two settings differ along an important dimension: e-commerce sites typically display/rank the same set of products many times over a short period of time, and the stakes each time are fairly low. On the other hand, any one particular job is one-shot setting with high stakes. Intuitively, it "feels" like the use of randomization as a means to achieve fairness is more natural in the former setting than the latter. We discuss this issue in more depth.
First, we consider two practical reasons for randomization being more natural in repeated low-stakes settings: (1) In high-stakes situation, a principal may be less willing to trade off utility for faimess, and (2) If fairness is required of the principal (rather than the principal's own goal), in a single-shot setting, it is much more difficult to verify that decision was indeed made probabilistically; in contrast, for a repeated setting, statistical tools can be employed to keep the principal honest.
More fundamentally, the two settings differ in the point in time at which fairess is guaranteed. For concreteness, consider the simplest setting: two agents with identical posterior distributions vie for one position. In this case, a coin flip is ex ante fair: before the coin flip is realized, both agents have the same probability of being selected. However, is not fair ex post: despite both having equal merit, one was selected, and the other was not. Contrast this with the alternative in which the same two agents compete multiple times, and a coin is flipped each time. Ex ante fairness is of course preserved, but even ex post, each agent was selected approximately the same number of times. This example may explain why randomization "feels" more fair for repeated than one-shot settings.
The fact that for one-shot setting, a coin flip is only ex ante fair, however, does not obviate the need for making fair decisions in one-shot settings. There will be situations in which a principal is faced with multiple essentially indistinguishable agents and not enough positions for all of them []] While ex ante fairness may not be completely satisfactory, it still guarantees "more" fairness than arbitrary deterministic tie- brebbraking. Indeed, one may argue that the goal of many principals is not so much to make fair decisions as to make defensible ones. For example, applicants are ranked strictly by GPA, choosing applicant with GPA of 3.91 over one with GPA of 3. 3.90 is essentially random tie- breakink, but with a rule that can be defended. Our point here is that randomization should be considered as viable alternative, if the true goal is to achieve fairness.
Other Considerations. In extending the probabilistic fairness axiom from two to multiple agents in Equation ( we chose to axiomatize fairness in terms of which position agents are assigned to. An equally valid generalization would have been to require for each pair æ, y of agents that if x has more merit than y with probability at least p. then x must precede y in the ranking with probability at least Φ The main reason why we prefer Equation (T) is computational: the only linear programs we know for the alternative approach require variables for all rankings and are thus exponential (in n) in size. Exploring the alternative definition is an interesting direction for future work.
Due to space constraints, additional properties of our fairness definition are discussed in $ B of the supplementary material. In particular, we discuss how fairness requirements give the principal
For example, in college admissions, qualified applicants typically outnumber available slots, and differences among the qualified applicants are frequently very small.
5

---

stronger incentives for obtaining, more accurate estimates of agents' merits, and how to align the ordinal nature of our definition with a principal's interest selecting high-risk high-reward agents.
3 Optimal and Fair Policies
For distribution over merits, let of be the ranking which sorts the agents by expected merit, i.e., by non-increasing E [v,]. The following well-known proposition follows because the position weights wy are non-increasing.
Proposition 3.1. of is mixiii-maximizing ranking policy for the principal.
If the principal's expected utility can be evaluated efficiently, computing of only requires sorting the agents by utility, and thus takes time only On O(1lop log n). While this policy conforms the Probability Ranking Principle (Robertson, 1977p, it violates Axiom [ for ranking fairness when merits are uncertain. We define a natural solution for a I-fair ranking distribution based on Thompson Sampling:
Definition 3.1 (Thompson Sampling Ranking Distribution). Define of TS as follows: first, draw a vector of merits ~ I, then rank the agents by decreasing merits in V.
That o is 1-fair follows directly from the definition of fairness. By definition, it ranks each agent in position & with exactly the probability that x has k--th highest merit.
Proposition 3.2. xf is 1-fair ranking distribution.
Furthermore, computing - only involves sampling from and then sorting the agents by merit, so it can be efficiently performed in time (n logn). n).
3.1 Trading Off Utility and Fairness
One straightforward way of trading off between the two objectives of fairness and principal's 's utility is to randomize between the two policies T and n²
Definition 3.2 (OPT/TS- The OPT/TS-Mixing ranking policy x Mix, randomizes between TTS and o with probabilities Φ and 1 o, respectively.
This policy inherits runtime of On log n) from TH and TF. The following lemma gives guarantees for such randomization (but we will later see that this strategy is suboptimal).
Lemma 3.1. Consider two ranking policies मy and 72 such that m is Φn-fair and 22 is d2-fair. A policy that randomizes between कı and ma with probabilities q and q. respectively, is at least (go1 + (1 4)02) -fair and obtains expected utility qU(m ( (T) + (1 ())((T (T).
Corollary 3.1. The ranking policy x Mix.o is f--air.
By definition, n Mix.0=0 has the highest utility among all O-fair ranking policies. Furthermore, all 1-fair policies achieve the same utility since the fairness axiom for ø 1 completely determines the marginal rank probabilities.
Lemma 3.2. All I-fair ranking policies have the same utility for the principal.
While n. d00 and x Mix, have the highest utility among 0-fair and 1-fair ranking policies, respectively, n M will typically not have maximum utility among all d- ranking policies for other values of @ E (0, 1). We illustrate this with a concrete example with n = 3 agents in in|$1 D
3.2 Optimizing Utility for şi-Fair Rankings
We now formulate a linear program for computing the policy L.P.o that maximizes the principal's utility, subject to being d-fair. The variables the linear program are the marginal rank probabilities (m)
Pz.k of the distribution to be determined. Then, by Equation (2) and linearity of expectation, the
principal's expected utility be written U(TT [) = ExEx Es P.T EE-r [by] wy- We use this linear form of the utilities to write the optimization problem the following LP with variables

---

Pa.k (omitting from the notation):
Maximize
Σ Pu,k EDET [vo] Wk
[ s.k
subject to
===1 Pa,k' 2 0 P Port
for all ar k for all x for all k for all ar k.
#= Po.k =1 n Pa,k
S P2,k S
In the LP, the first set of constraints captures d-approximate fairness for all agents and positions, while the remaining constraints ensure that the marginal probabilities form doubly stochastic matrix.
As a second step, the algorithm uses the Birkhoff-von Neumann (BvN) Decomposition of the matrix P = (Pa. (P,,k),,& to explicitly obtain distribution и over rankings such that и has marginals Pz.k- The Birkhoff-von Neumann Theorem (Birkhoff, (946) states that the set of doubly stochastic matrices is the convex hull of the permutation matrices, which means that we can write = E. 9a P(*), where p(*) is the binary permutation matrix corresponding to the deterministic ranking a, and the qo form probability distribution. It was already shown by Birkhofi (1946) how to find polynomially sparse decomposition in polynomial time.
Having to solve linear program obviously makes the computation of L.P. less efficient. It is still efficient enough to be feasible for several hundred agents, An interesting direction for future work would be whether the specific LP can be solved more efficiently, either exactly or approximately, by using algorithms other than the standard ones (Ellipsoid or Interior Point Methods).
M for all i and k. For some In order to solve the Linear Program 3 one needs to know P
distributions I (e.g., Example these quantities can be calculated in closed form. For others, they can be approximated using Monte Carlo sampling. Small approximation errors only have small impact on the final solution as captured by Propositions C.I and C.2 in the appendix.
4 Experimental Evaluation: MovieLens Dataset
To evaluate our approach in a recommendation setting with a realistic preference distribution, we designed the following experimental setup based on the Movielens 100K (MI--100K) dataset. The dataset contains 100,000 ratings, by 600 users, on 9,000 movies belonging to 18 genres (Harper) and Konstan 2015). In our setup, for each user. the principal is recommender system that has to generate a ranking of movies Sy for one of the genres (c.g., Horror, Romance, Comedy) according notion of merit of the movies we define as follows.
Modeling the Merit Distribution. We define the (unknown) merit em of a movie as the average rating of the movie across the user p this merit is unknown because most users have not scen/rated most movics. To be able to estimate this merit based on ratings in the ML-100K dataset, and to concretely define its underlying distribution and the corresponding fairness criteria, define generative model of user ratings. The model assumes that the rating of movie E S drawn from a multinomial distribution over {1, 3, 4, 5} with parameters 6m (fm,1..... 6m.a). Assuming Dirichlet prior, from the dataset in closed form, using merely the counts of each rating for each movie in the dataset. (See 3 E. for details.) Based this definition of merit and its uncertainty, define and compare different ranking policies for this experimental setup as follows.
infer the posterior distribution of the ratings (and hence the merit)
Utility Maximizing Ranking (T"): We use the DCG function (Burges et al., 2005) with position weights Wy (1+k) as our utility measure. Since the weights are indeed strietly decreasing, as described in $ 3 the optimal ranking policy n² sorts the movies (for the particular query) by decreasing expected merit, which is the expected average rating E, - Ep-pjo.. D) [um (0) under the posterior Dirichlet distribution in our case; here, e., (0) is the average rating of movie m corresponding to the parameter vector 0 sampled from the posterior.
For a personalized ranking application, an alternative would be to choose each user's (mostly unknown) rating as the merit criterion instead of the average rating across the user population.
7

---

Expected Merits Fey
1.000
0.188
Flr to
Mixxs
6.900
0184 T8
1.0
(9)
(a)
(b)
Figure 1: (a) Posterior distribution of ratings (merit) for subset of "Comedy" movies, (b) Tradeoff between Utility and Fairness, as captured by
Fully Fair Ranking Policy (i J): A fair ranking, in this case, ensures that, for all positions k, a movie is placed in the top k positions according to the posterior merit distribution. In this setup, fully fair ranking policy TSS is obtained by sampling the multinomial parameters On, for each movie m Sg and computing Um (f.) rank them:
TS argsort,, Um (0..) s.t. 9m. P(0..
OPT/TS-Mixing Ranking Policy (n Mix.)t)): The policies Mix, randomize between the fully fair and mullit-mmaxmizzing ranking policies with probabilities á and 1 &, respectively.
LP Ranking Policy (P):: The é-fair policies LPLP require the principal to have access to the probabilities Pe-r [M()) m,k] which we estimate using 5 10* Monte Carlo samples, so that any estimation error becomes negligible.
Observations and Results. In the experiments presented, we used the ranking policies n², TS π M and LP to create separate rankings for each of the genres. For each genre, the task is to rank random subset of 40 movies from that genre. To get posterior with interesting degree of uncertainty, we take a 10% i.i.d. samples from to infer the posterior for each movie, observe that the results qualitatively consistent across genres, and we thus focus detailed results for the genre "Comedy" as a representative example. Its posterior merit distribution over a subset is visualized in Figure a). Note that substantial overlap exists between the marginal merit distributions of the movies, indicating that as opposed to x" (which sorts based on the expected merits), the policy TS will randomize many different rankings.
Observation We evaluate the cost of fairness to the principal in terms of loss in utility, as well the ability of T.P. to minimize this cost for 6-fair rankings. Figure bb shows this cost in terms of expected Normalized DCG (i.e., NDCG = DCGj DCG/maxxDCCC max((D)) as in (Järvelin and Kekälänen 2002)). These results averaged over 20 runs with different subsets of movies and different traming samples. The leftmost end corresponds to the NDCG of x while the rightmost point corresponds to the NDCG of the 1-fair policy n T'
The drop in NDCG is below one percentage point, which is consistent with the results for the other genres. We also conducted experiments with other values of s, data set sizes, and choices of wai even under the most extreme conditions, the drop was at most 2 percent. While this rather small drop may be surprising at first, we point out that uncertainty in the estimates affects the utility of both T and TS. By industry standards, a 2% drop in NDCG is considered quite substantial; however, is not catastrophic and hence bodes well for possible adoption.
Observation 2:
Figure [bb also compares the trade-off in NDCG in response to the fairness approximation parameter for both Mix,e and LLP',,, We observe that the utility-optimal policy π LP' provides gains over n Mix.e especially for large values of Φ. Thus, using LP, can further reduce the cost of faimess discussed above.
Observation
To provide intuition about the difference between Mix and LP Figure in E.3 visualizes the marginal rank distributions Pm.k, i.e., the probability that movie m ranked
8

---

at position k. The key distinction is that, for intermediate values of o, T_PP, exploits non- non-linear structure in the ranking distribution (to achieve a better trade-off) while Mix,0 merely interpolates linearly between the solutions for & 0 and &
Based on these observations, in general, the utility loss due to faimess is small, and can be further reduced by optimizing the ranking distribution with the LP-based approach. These results are based on the definition of merit as the average rating of movies over the entire user population. A more realistic setting would personalize rankings for each user, with merit defined as the expected relevance of a movie to the user. In our experiments, the results under such a setup were quite similar, and are hence omitted for brevity and clearer illustration.
5 Real- Experiment: Paper Recommendation
To study the effect of deploying fair ranking policy in a real ranking system, we built and fielded a paper recommendation system at the 2020 ACM SIGKDD Conference on Knowledge Discovery and Data Mining. The goal of the experiment is to understand the impact of fairness under real user behavior, as opposed to simulated user behavior that is subject to modeling assumptions. Specifically, we seek answer two questions: (a) Does fair ranking policy lead more equitable distribution of exposure among the papers? (b) Does fairness substantially reduce the utility of the system to the users?
The users of the paper recommendation system were the participants of the conference, which was held virtually in 2020. Signup and usage of the system was voluntary. Each user was recommended personalized ranking of the papers published at the conference. This ranking was produced either by a² or by π Ts and the assignment of users to treatment (π 15) control (o*) was randomized.
Modeling the Merit Distribution. The merit of a paper for a particular user is based on a relevance score Pa,s that relates features of the user (c.g., bag-of-words representation of recent publications, co-authorship) to features of cach conference paper (e.g., bag-of- representation of paper, citations). Most prominently, the relevance score Ma,s contains the TFIDF-weighter cosine similarity between the log-offwords representations.
To model the uncertainty in Hu,i we make the assumption that since all papers were accepted to the conference, they must have been deemed relevant to at least some fraction of the audience by the peer reviewers. Hence, papers with uniformly low relevance scores Pu,s across users (e.g.. ones introducing new research directions or bringing in novel techniques) must have higher uncertainty in their relevance score. This assumption leads us to define the uncertainty as a normal distribution around the mean Pu.s with standard deviation d; defined such that, for paper i, there exists at least one user who finds the paper highly relevant to their interests with high probability. (See [ F.2 for details on how 6, is calculated.)
Ranking Policies. Users in the control group Ur received rankings in decreasing order of pa,i- Users in the treatment group MyTS received rankings from the fair policy that sampled scores from the uncertainty distribution, مu. (Mu,, 5z), and ranked the papers by decreasing jhn,i.
Results and Observations. We first analyze if the fair policy provided more equitable exposure to the papers. In this real-world evaluation, exposure is not equivalent to rank, but depends on whether users actually browsed given position in the ranking. Users could browse their ranking in pages of 5 recommendations each; we count a paper as exposed if the user scrolled to its page.
Figure 2 compares the histograms of exposure of the papers in the treatment and control groups. Under the fair policy, the number of papers in the lowest tier of exposure is roughly halved compared the control condition. This verifies that the fair policy does have an impact on exposure in a real-world setting, and it aligns with our motivation that a fair ranking policy distributes exposure more equally among the ranked agents. This is also supported by comparing the Gini inequality coefficient Gini 1936) for the two distributions: G(T*) = 0.3302, while C(TTT) = 0.2996 (where smaller coefficient means less inequality in the distribution).
Observation 1:
Observation 2: To evaluate the impact of fairness on user engagement, we analyze range of engagement metrics as summarized in Table While a total of 923 users signed up for the system ahead of the conference (and were randomized into treatment and control groups), 462 never came to

---

Number of Users with activity
Average Activity Per User
Expreim popecc
n
TS
Total Number of users
213
248
Num. of pages examined
10.8075
10.7984
Read Abstract Add to Calendar
92
101
3.7230
2.6774
25
51
50
1.4366
0.8508
0.0
0.1
0.2
0.3
0.4
Read PDF Bookmark
52
0.5258
0.5323
Car Suatane with Pops
13
0.3192
0.6129
Figure 2: Distribution of the exposure of pa- pers in treatment and control.
Table 1: User engagement under the two conditions n" and TTS. None of the differences are statistically significant. (For user actions, this is specifically due to the small sample size).
the system after all. Of the users that came, 213 users were in (,. and 248 users were in MgTs. Note that this difference is not caused by the treatment assignment, since users had no information about their assignment/ranking before entering the system. The first engagement metric we computed is the average number of pages that users viewed under both conditions. With roughly 10.8 pages (about 54 papers), engagement under both conditions was almost identical. Users also had other options to engage, but there no clear difference between the conditions, either. On average, they read more paper abstracts and added more papers to their calendar under the control condition, but read more PDF and added more bookmarks under the treatment condition. However, none of these differences is significant at the 95% level for either a Mann- HhhnnWh U test or a two-sample t-test. While the sample size is small, these findings align with the findings on the synthetic data, namely that fairness did not appear to place large cost on the principal (here representing the users)
6 Conclusions and Future Work
We believe that the focus on uncertainty we proposed in this paper constitutes a principled approach to capturing the intuitive notion of faimess to agents with similar features: rather than focusing the features themselves, the key insight is that the features' similarity entails significant statistical uncertainty about which agent has more merit. Randomization provides way fight fire with fire, and axiomatize fairness in the presence of such uncertainty.
Our work raises wealth of questions for future work. Perhaps most importantly, as discussed in 2.44 to operationalize our proposed notion of fairness, it is important to derive principled merit distributions I' based on the observed features. Our experiments were based on "reasonable" notions of merit distributions and concluded that fairness might not have to be very expensive to achieve for principal. However, much more experimental work is needed to truly evaluate the impact of fair policies on the utility that is achieved. It would be particularly intriguing to investigate which types of real-world settings lend themselves to implementing fairness at little cost, and which force steep trade-off between the two objectives.
Our work also raises several interesting theoretical questions. In B.1 we show one setting in which forcing the principal to use a fair policy drastically increases the principal's incentives to form a more accurate posterior I for minority group. We did not prove general result in this vein. We ask: will the incentives of a principal to learn a better posterior always (weakly) increase the principal is forced to be fairer? If true, this would provide fascinating additional benefit of fairness requirements.
Another interesting question concerns the utility loss incurred by using the policy OPT/TS-Mixing As shown in S D OPT/TS-Mixine is in general not optimal. However, in the example from S D as well as in our experiments in $ 4 the loss in utility was quite small. An interesting question would be to bound the worst-case loss in the utility of OPT/TS Mixiig, compared to the L.-based policy. In particular, this question is of interest due to the simplicity of the OPT/TS-Mixing policy; it does not require the computationally expensive solution of an LP or an explicit estimate marginal rank probabilities under I'.
10

---

Acknowledgements
This research was supported in part by NSF Award IIS-2008139 and UIS-1901166 We thank Aleksandra Korolova, Cris Moore, and Stephanie Wykstra for useful discussions and feedback. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
References
Asudehy, A., Jagadishy, H., Stoyanovichz, J., and Das, G. (2019). Designing fair ranking schemes. SIGMOD.
Barocas, and Selbst, A. D. (2016). Big data's disparate impact. Cal. Rev.
Beutel, A., Chen, Doshi, T., Qian, H., Wei, L.., Wu, Y., Heldt, I.,, Zhao, Z.,, Hong, L., Chi, E. H., al. (2019). Faimess in recommendation ranking through pairwise comparisons. In KDD.
Biega, A. J., Gummadi, P., and Weikum, (2018). Equity of attention: Amortizing individual fairesss in rankings. In SIGIR.
Birkhoff, G. (1946). Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman.
Burges, C., Shaked, T., Renshaw, E.,, Lazier, A., Deeds, M., Hamilton, N., and Hullender, G. (2005). Learning to rank using gradient descent. In ICML, pages 89-96.
Calders. T., Kamiran, F., and Pechenizkiy, M. (2009). Building classifiers with independency constraints. In Data mining workshops, ICDMW, pages 13-18.
Calmon, P., Wei, D., Vinzamuri, B., Ramamurthy, K. N., and Varshney, K. R. (2017). Optimized pre-processing for discrimination prevention. In NIPS.
Carbonell, J. and Goldstein, J. (1998). The use of MMR, diversity-basee -based reranking for reordering documents and producing summaries. In SIGIR.
Celis, L. E., Mehrotra, A., and Vishnoi, N. K. (2020). Interventions for ranking in the presence of implicit bias. In Proceedings of the Conference on Fairness, Accountability, and Transparency.
Celis, L. E., Straszak, D., and Vishnoi,
(2018). Ranking with fairness constraints. ICALP.
Clarke, C. L., Kolla, M., Cormack, G. V., Vechtomova, O., Ashkan, A., Büttcher, S., and MacKinnon, I. (2008). Novelty and diversity in information retrieval evaluation. In SIGIR.
Diaz, F., Mitra, B., Ekstrand, M. D., Biega, A. J., and Carterette, B. (2020). Evaluating stochastic rankings with expected exposure. In CIKM.
Dvoretzky, A., Kiefer, J., and Wolfowitz. J. (1956). Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Annals of Mathematical Statistics, 27(3):642-669.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012). Fairness through awareness. In ITCS. ACM.
Dwork, C., Kim, M. P., Reingold, O.,, Rothblum, G. N., and Yona, G. (2019). Learning from outcomes: Evidence-based rankings. In FOCS.
Ghosh, A., Dutt, R., and Wilson, C. (2021). When fair ranking meets uncertain inference. arXiv preprint 2055:2200..00011.
Gini, C. (1936). On the measure of concentration with special reference income and statistics. Colorado College Publication, General Series.
Hardt, M., Price, E., and Srebro, N. (2016). Equality of opportunity in supervised learning. In NIPS.
Harper, F. M. and Konstan, J. A. (2015). The MovieLens datasets: History and context. ACM TIIS.

---

Heidari, H. and Krause, A. (2018). Preventing disparate treatment in sequential decision making, In IJCAI.
Järvelin, K. and Kekäläinen, (2002). Cumulated gain-based evaluation of techniques. TOIS.
Joseph, M., Kearns, M., Morgenstern, J., and Roth, A. (2016). Fairness in learning: Classic and contextual bandits. In NIPS.
Kallus, N. and Zhou, A. (2019). The fairness of risk scores beyond classification: Bipartite ranking and the XAUC metric. NeurIPS.
Kearns, M., Roth, A., and Wu, Z. S. (2017), Meritocratic fairness for cross-population selection. In ICML.
Kilbertus, N., Carulla, M. R., Parascandolo, G., Hardt, M., Janzing, D., and Schölkopf, B. (2017).
Avoiding discrimination through causal reasoning. In NIPS.
Kim, M. P., Ghorbani, A., and Zou, J. (2019). Multiaccuracy: Black-box post-processing for fairness in classification. In AAAI Conference AI, Ethics, and Society.
Kleinberg, J. and Raghavan, M. (2018). Selection problems in the presence of implicit bias. In ITCS.
Kusner, M. J., Loftus, J., Russell, C., and Silva, R. (2017). Counterfactual fairness. In NIPS.
Lahoti, P., Gummadi, K. P., and Weikum, G. (2019). Operationalizing individual fairness with pairwise fair representations. VLDB Endowment.
Liu, Y., Radanovic, G., Dimitrakakis, C., Mandal, D., and Parkes, D. C. (2017). Calibrated fairness in bandits. FATML.
Lum, K. and Johndrow, (2016). A statistical framework for fair predictive algorithms. FATML..
Massart, P. (1990). The tight constant in the Dvoretzky- Probability,
inequality. Annals of Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, A. (2019). survey on bias and faimess in machine learning. arXiv preprint arXiv: 17Xiv:1908.09635.
Mehrotra, A. and Celis, L. E. (2021). Mitigating bias in selection with noisy protected attributes. In Proceedings of the ACM Conference on Fairness, Accountability, and Transparency.
Mehrotra, R., McInerney, J., Bouchard, H., Lalmas, M., and Diaz, F. (2018). Towards a fair marketplace: Counterfactual evaluation of the trade-off between relevance, faimess & satisfaction in recommendation systems. In CIKM.
Morik, M., Singh, A., Hong, J., and Joachims, T. (2020). Controlling faimess and bias in dynamic learning-to-re to-rankk. In SIGIR.
Narasimhan, H., Cotter, A., Gupta, M., and Wang, (2020). Pairwise fairness for ranking and regression. In AAAI.
Patil, V., Ghalme, G., Nair, V., and Narahari, Y. (2020). Achieving fairness in the stochastic multi-armed bandit problem. In AAAI.
Penha, G. and Hauff, C. (2021). On the calibration and uncertainty neural learning rank models. arXiv preprint arXiv:2101.0433
Pleiss, G., Raghavan, M., Wu, F., Kleinberg, J., and Weinberger, K. Q. (2017). On faimess and calibration. NIPS.
Prost, F., Awasthi, P., Blumm, N., Kumthekar, A., Potter, T., Wei, L.,, Wang, X., Chi, H., Chen, J., and Beutel, A. (2021). Measuring model fairness under noisy covariates: A theoretical perspective. arXiv preprint arXiv:2105.099 109.09985.
Radlinski, F., Bennett, N., Carterette, B., and Joachims, T. (2009). Redundancy, diversity and interdependent document relevance. In ACM SIGIR Forum.
12

---

Robertson, S. E. (1977). The probability ranking principle in IR. Journal of documentation.
Schumann, C., Lang, Z. Mattei, N., and Dickerson, J. P. (2019). Group fairness in bandit arm selection. arXiv preprint 1912:0992..0800..
Singh, A. and Joachims, T. (2018). Fairness of exposure in rankings. KDD.
Singh, A. and Joachims, T. (2019). Policy learning for faimesss in ranking. In NeurlPS.
Singh, A., Kempe, D., and Joachims, T. (2021), Fairness in ranking under uncertainty. arXiv preprint 2107.06720.
Soufiani, H. A., Parkes, D. C., and Xia, L. (2012). Random utility theory for social choice. In NIPS.
Taylor, M., Guiver, J., Robertson, S., and Minka, (2008). Softrank: optimizing non-smooth rank metrics. In WSDM.
Woodworth, B., Gunasekar, S., Ohannessian, M. I,, and Srebro, N. (2017). Learning discriminatory predictors. COLT.
Yang, K. and Stoyanovich, J. (2017). Measuring fairness in ranked outputs. SSDBM.
Zafar, M. B., Valera, I., Gomez Rodriguez, M., and Gummadi, K. P. (2017). Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In www.
Zehlike, M., Bonchi, F., Castillo, C., Hajian, S., Megahed, M., and Baeza- Yates, R. (2017). Fatir: fair top-k ranking algorithm. CIKM.
Zehlike, M. and Castillo, C. (2020). Reducing disparate exposure in ranking: A learning rank approach. In The Web Conference.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. (2013), Learning fair representations, In ICML.
Zliobaite, (2015). On the relation between accuracy and fairness in binary classification. FATML Workshop at ICML.
13


Reviews:
[{"review_id": "r1oo9XTJq51", "reviewer": "Reviewer_xirY", "summary": "This paper studies the problem of fair ranking under a new notion of fairness. The main point of the paper is that uncertainty is a primary reason for the lack of fairness. In defining this new notion of fairness, authors base their arguments on the axiom that if $A$ has merit greater than or equal to $B$ with probability at least $p$, then a fair policy should treat $A$ at least as well as $B$ with probability at least $p$. Based on this, they say a ranking policy is fair if the probability that it ranks an agent in the first $k$ positions is at least the probability that it actually is among the top $k$ agents. They similarly say an algorithm is $\\phi$-fair if the probability that it ranks an agent in the first $k$ positions is at least a $\\phi$ fraction of the probability that it actually is among the top $k$ agents. \nAuthors then try to design algorithms for fair ranking. They first propose two very simple algorithms which achieve fair and approximately fair ranking without considering its impacts on the utility of the principal. They then show how to compute rankings that optimally trade-off approximate fairness against utility to the principal. Finally, they conduct empirical studies to evaluate the impact of their approach on a paper recommendation system that they built and fielded at a large conference.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I find this new notion of fairness very interesting. The authors do a good job of explaining why thinking about fairness in this way is useful and how uncertainty plays a significant role in getting unfair policies. The main technical contribution of the paper is designing ranking policies which are quite trivial (So, the paper is not very technically strong). However, using empirical studies, the authors show that these simple algorithms give good results. In conclusion, I believe that the paper meets the bar for a NeurIPS publication mostly due to its novelty (studying this new notion of fairness). \n\nA minor comment for the authors: There is a typo in the abstract “compute,rankings”.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't believe that there is any negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "Wos2q7XDR9S", "reviewer": "Reviewer_7pR9", "summary": "The paper proposes a new definition of fairness in rankings. An LP-based algorithm is given for finding best (max utility) ranking for a given fairness level. Two empirical evaluations of the proposed frameworks are given 1) based on ranking movies from a public dataset and 2) an experiment was run during a large virtual conference in which participants were given paper recommendations according to a ranking.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main assumption (or belief) behind this paper is that there is inherent uncertainty in the ranked items' merits which are observed by the ranker. This uncertainty is modelled by a probability distribution over merits that is given as input to the ranker. Also the solution is then not a single permutation over items but rather a whole distribution over them. A (candidate solution) distribution over rankings is said to be \\phi-fair if for every item x and every position k in the ranking, the probability of x being ranked in top-k is at least \\phi times the probability of x being top-k according to the given distribution of merits.\n\nWhat is important to point out is that for the standard setting of a ranking problem, where *a single ranking must be produced* based on some kind of data, this framework does not seem applicable -- the main point of having a probabilistic solution is that one samples from it repeatedly, multiple times, and not just once. It is mentioned in the paragraph 180-185 that because of this issue the applicability of this approach is limited. In the reviewer's opinion this is a rather strong limitation, and the paper makes the impression as if the \"framework\" was very general -- it would be certainly beneficial to state upfront what is the setting the framework is expected to be applied to, because it is certainly not the most common one.\n\nThe mathematical formulation of the fairness notion proposed by the authors is quite nice and ellegant. This ellegance also translates to a very natural LP formulation of the problem that the authors give as a solution method. However, several natural questions come to mind:\n1) The knowledge of Prob[M^{(v)}_{x, k}] is a very strong assumption, it is not at all convincing that this can be obtained -- and even if it can by MC, then the error can significantly impact the optimal solution.\n2) There is no discussion of other, perhaps combinatorial approaches to solve this problem. Is it obviosly hard? Is LP somehow necessary?\n3) Even if LP is necessary, and no greedy approach works, then giving a practical algorithm for ranking that involves solving an LP does not sound right. It would be great if the authors discussed some possible practical, efficient algorithmic approaches (or at least heuristics) for solving this linear program that could allow avoiding a general LP-solver.\n\n\nWhen it comes to the experiments, first of all the reviewer is impressed by the Real World Experiment on paper recommendation (during a virtual conference). This is a great piece of work which deserves appreciation as it certainly required a lot of effort to implement. That being said, even though this single part of the paper makes a great, positive impression, the reviewer's overall feedback on the experiments, or rather the whole proposed \"framework\" is not quite positive. The main objection is that the premise of uncertainty and probabilistic modelling of the problem feels rather artificial and does not seem to arise naturally in real-world examples. This is unfortunately confirmed by the design forced in both experiments: in each of them, some kind of artificial randomness must be injected just so that the assumption of \"uncertainty\" is met. If this assumption was correct and natural, why would there ever be need to inject artificial randomness into the data?\n\n\nTo conclude, the paper is well written and the considered idea for a framework for ranking seems reasonable from the mathematical perspective. Also the obtained algorithm is natural, and the performed experiments are strong parts of the paper. However, the reviewer is of the opinion that the main assumption made in this paper -- that uncertainty is inherent in ranking problems -- in the way it is modelled in this framework, is doubtful, and somehow even the experiments reinforce this doubt (injecting artificial randomness) instead of proving the opposite.\n\n\nMinor comments:\n\n1. typo in abstract, line 17 'compute,rankings'\n2. there are multiple papers that are referenced via arxiv, but have been published in conferences in the meantime", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "9TRXa58M6-x", "reviewer": "Reviewer_4iKN", "summary": "This paper studies the fairness issue in algorithmic decision-making caused by uncertainty. Since the actual merits are hard to observe, the authors propose a new notion to capture the uncertainty, named approximate fairness in ranking. Based on the notation, they propose different algorithms to achieve approximately fair ranking distributions. In addition to the theoretical analysis, extensive empirical studies are conducted to evaluate their approach.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written and studies an interesting problem, which is well explained in the introduction. To some extent, it will provide a new perspective for the related research communities to explore the fairness issue under uncertainty. This paper is technically sound for me and the empirical studies are versatile which including data-driven simulation and real implementation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. It would be better to show the running time of the proposed algorithm in the experimental section.\n2. Comparisons with other state-of-the-art algorithms are missing, thus readers cannot see whether the proposed algorithms can outperform the related work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "1KRtl2PHqie", "reviewer": "Reviewer_gSPf", "summary": "The paper considers ranking given access to posterior distributions on true scores. They propose a notion of fairness based on these posterior distributions, essentially requiring that probability of inclusion among the top $k$ scale with the probability of being ranked in the top $k$ according to the posterior distributions. These posterior distributions are presumed to be fair, in the sense that an algorithm which is fair (according to this definition) need only be fair with respect to the posterior distributions.\nThey show that a convex combination of Thompson Sampling and ranking by means is approximately fair but can be suboptimal in terms of utility. They give an optimal algorithm (subject to their fairness constraint) by formulating the problem as a linear program. Finally, they run an experiment on a movie recommendation dataset and implement their algorithm in a real-world paper recommendation setting, comparing their two algorithms and measuring cost of fairness.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and clear, presenting simple algorithms that can be easily implemented in practice. The biggest contribution is the notion of fairness, which requires that ordinal probabilities be bounded based on posterior distributions. This is a novel notion of fairness in ranking to my knowledge. The biggest drawback of the paper is that the technical (theory) contribution is somewhat weak.\n\nSome concerns that arise due to the definition of fairness: \n- A notion of fairness based purely on posterior distributions might enhance inequities in the society, simply due to the fact that the initial observations for certain agents might be luckier than for other agents. \n- How are the posterior distributions computed? How might these distributions account for systemic biases? I wonder if the paper is simply by-passing the key issue in evaluation metrics by considering posterior distributions. \n- Randomness -- probabilistic definition of ranking -- why does a probabilistic definition even make sense, when providing a single ranking for agents, for applications such as admissions, hiring, etc?\n- A lot of references on rankings seem to be missing -- for e.g., Kleinberg and Raghavan (subset selection under bias), Bower et. al (individually fair rankings), Gupta and Salem (selection under poset model), Celis and Mehrotra (subset selection with noisy protected attributes), Celis Mehrotra Vishnoi (ranking under implicit bias), etc. \n\nMinor comment: The discussion of error decay in lines 244-249 should be written formally as a proposition.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As noted in the paper, bias mitigation—if it were to happen—would take place in choosing the posterior distributions, not in choosing the ranking. Some discussion on how one might mitigate a bias by choosing an appropriate posterior distribution would be helpful.\n\n", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 (by me), 3 (by my student)"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After discussion, the reviewers were all in favor of accepting the paper. The discussion of related work should be expanded (in particular, KRW seems to ask for a very similar notion of fairness in rankings, although as you point out, the actual setting considered is distinct). Thanks for the strong submission!
Decision: Accept (Poster)