Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
35,224 characters · 10 sections · 22 citation commands
An Outcome Test of Discrimination for Ranked Lists
Researchers are often interested in testing whether a human or algorithmic decision-maker is biased against members of a protected group (e.g. race or gender). Substantial attention has been paid to the case where the decision is binary -- e.g., whether or not to grant a loan, accept a student to college, hire a job candidate, etc. However, in a variety of relevant domains, the decision-maker produces a ranked list of candidates. Ranked lists are particularly relevant in the context of online platforms: LinkedIn provides recruiters with an ordered list of candidates, Google returns an ordered list of search results, and Facebook and Twitter provide users with an ordered feed of posts. Ranked lists are relevant in other domains, as well: for example, hospitals participating in the National Residency Match Program (NRMP) provide a listwise ranking of candidate residents roth_evolution_1984, and experiments in behavioral economics have asked participants to rank which of the other participants they would like to be grouped with castillo_discrimination_2010.
We consider the setting where an Auditor observes ranked lists of candidates produced by a Ranker. The Auditor observes each candidate's group status $G$ and outcome $Y$. Importantly, the Auditor does not observe all of the features $X$ that are available to the decision-maker. This reflects a realistic limitation to (human or algorithmic) audits in a variety of domains. When the decision-maker is human, it is nearly always the case that there are factors that are observed by the decision-maker but not by the auditor -- for example, an auditor of the NRMP would not be able to observe everything that occurred during the candidate's interview. Likewise, external auditors of tech platforms will almost never have access to all of the features used by the algorithm. Even internally within tech platforms it is often difficult to retrospectively reconstruct all of the features used by an algorithm, since all of the relevant user data may not be saved for privacy reasons. Moreover, even if all the data were observed, the covariates may be so high-dimensional that it is difficult to condition on the full set of covariates in any practical analysis.
We then ask how the Auditor can test whether the Ranker is biased against a protected group in forming their rankings. Our notion of bias extends Becker1957's notion of tase-based discrimination to the context of listwise rankings. In particular, we will say that the Ranker is unbiased if they sort candidates to maximize an objective function that values placing candidates with better outcomes earlier in the list, regardless of their group status. As we show, this form of objective nests the Net Discounted Cumulative Gain (NDCG) objective commonly used for search algorithms. It can also be motivated by a simple model in which the objective is to maximize total engagement, and engagement with a post is an increasing function of its quality and rank in the list.
Our first main theoretical result is that the null hypothesis of no bias implies a system of moment inequalities. Intuitively, these moments impose that whenever we see a particular configuration of the candidates (e.g. a woman first, man second, etc.), we should not be able to flip the order of some of the candidates and improve the objective function. For instance, we should not be able to increase the objective on average by flipping the position of the first two candidates whenever the first-ranked candidate is male and the second is female.
Our second main theoretical result is that this system of moment inequalities is a sharp testable implication of the hypothesis of no bias. Specifically, whenever the moment inequalities are satisfied, there exists a distribution for the unobserved covariates such that the observed data corresponds with the utility maximization of an unbiased decision maker.
Our theoretical results allow us to leverage a large econometrics literature on testing moment inequalities to develop statistical tests of bias in settings with list-wise rankings (see canay_practical_2017, molinari_chapter_2020 for reviews of the moment inequality literature). We discuss several practical considerations, including: reducing the dimension of the large number of implied inequalities; adjusting for position effects -- wherein a candidate's realized position has a causal effect on their outcome; and incorporating observed features about the candidates.
Finally, we showcase our proposed procedure in a validation exercise using data from the InstaJobs algorithm at LinkedIn. The InstaJobs algorithm is an algorithm for determining whether to send users a notification about a job they may be interested in. The algorithm generates a predicted score for each candidate, and sends notifications to candidates above a threshold. We use the scores constructed by the algorithm for each job to create a listwise ranking of the candidates, and apply our proposed tests to this ranking data. This construction allows us to validate the listwise outcome test by comparing its results to what we would obtain by directly examining the score used to generate the ranking (which is not typically available for a ranking algorithm in practice). We find using the listwise outcome test that when a female and male candidate are in adjacent ranks, the lower-ranked male candidate systematically has better outcomes than the higher-ranked female candidates. This finding accords with a direct examination of the scores used for rankings, which show that the algorithm is under-calibrated for men relative to women.
Our results relate to a large literature on detecting discrimination in economics, computer science, and other fields. See lang_race_2020 for a recent review of the economics literature on discrimination, which has primarily focused on the case where the decision-maker makes individual-level decisions (e.g. give out a loan, hire a candidate) rather than produce listwise rankings.\footnote{One exception to this is castillo_discrimination_2010, who conduct a lab experiment in which participants rank whom they would like to be grouped with. castillo_discrimination_2010 focus on differences in average ranks across groups.} Several notions of fairness for listwise ranking algorithms have been considered previously in the computer science literature, as reviewed in pitoura_fairness_2021. Multiple papers have considered demographic parity constraints, which require that exposure (i.e. the distribution of rankings) be similar across groups zehlike_fair_2017,celis_ranking_2017,singh_fairness_2018,geyik_fairness-aware_2019, ghosh_when_2021. Other work has considered the notions of disparate treatment and disparate impact, which restrict that exposure be proportional to average group-level utility or outcomes singh_fairness_2018. beutel_fairness_2019 propose a notion of fairness that extends the notion of equal opportunity hardt_equality_2016 to the listwise ranking setting: this requires that the probability that a candidate is ranked below another candidate with a worse outcome does not differ across groups. The notion of fairness we consider here is distinct, and is based on the question of whether the ranking is consistent with maximizing an objective function that does not depend on group status directly. As discussed in corbett-davies_measure_2018 and rambachan_economic_2020 in the context of binary classification problems, decision rules that maximize an unbiased utility function may violate demographic parity or equalized odds if the distribution of risks differs across populations, a problem known as inframarginality. Similar distinctions arise in the context of listwise rankings.
The model we consider consists of a Ranker and an Auditor. The Ranker -- which could be either an algorithm or human -- observes an unordered list of candidates and their characteristics, and produces a ranked list of the candidates. The Auditor then observes the ranked list of candidates and their outcomes, and wants to test whether the Ranker is biased.
\paragraph{Data-generating Process.} The Ranker is presented with queries indexed by $q$ in which they are asked to rank $J$ candidates with characteristics $X_{1q},...,X_{Jq}$ and group status $G_{1q},...,G_{Jq}$. We denote by $\mathcal{I}_q = \{ (X_{jq}, G_{jq} \}_{j=1}^J$ the information provided to the Ranker for query $q$. After observing $\mathcal{I}_q$, the Ranker produces a ranked list of the candidates -- formally this is a map $j_q: \{1,...,J\} \rightarrow \{1,...,J\}$ where $j_q(r)$ corresponds with the index of the candidate in rank $r$. Rank $1$ is the best rank, and we suppose that there are no ties in the rankings, so that $j_q$ is one-to-one. After the candidates are ranked, they realize outcomes $Y_{1q},...,Y_{Jq}$. We suppose for now that the outcomes $Y_{jq}$ do not depend on the rankings, and return to the scenario where outcomes may be affected by the rankings in Section (ref).
\paragraph{Auditor.} There is an Auditor tasked with evaluating whether the Ranker is biased. For each query $q$, the Auditor sees the rank-ordered list of outcomes $Y_q = (Y_{j_q(1)q},...,Y_{j_q(J)q})$ as well as the group statuses by rank, $G_q = (G_{j_q(1)q},...,G_{j_q(J)q})$. Importantly, the Auditor does not see the characteristics $X_q = (X_{j_q(1)q},...,X_{j_q(J)q})$ used to form the rankings. We show that similar results arise if the Auditor observes a subset of the variables in $X_q$ in Section (ref).
We now describe the notion of unbiasedness that we will test, which extends the logic of Becker1957 to the setting of list-wise rankings. Specifically, we will be interested in testing the hypothesis that the Ranker chooses the ranking $j_q(\cdot)$ to maximize
where the $w_r$ are a strictly decreasing sequence of positive weights. Intuitively, the fact that the $w_r$ are decreasing means that the Ranker prefers to place candidates with higher values of $Y$ earlier in the list. This corresponds with expected utility maximization if the Ranker's utility function is $U(Y_q,G_q) = \sum_r w_r Y_{j_q(r)q}$, which depends only on the rank-ordered outcomes for the candidates, and not directly on their group-status $G_q$.
It is straightforward to show that an unbiased Ranker chooses the order $j_q(\cdot)$ that corresponds with sorting the candidates based on their expected outcomes given the Ranker's information set ($E[Y_{jq} | \mathcal{I}_q]$).
An important type of violation of this hypothesis is when the Ranker instead maximizes expected utility for the utility function
so that the outcome is effectively penalized by $\tau$ for candidates from group $G=1$ relative to group $G=0$. When the decision-maker is human, such a utility function may arise owing to racial animus against the $G=1$ group. This is thus a natural extension of Becker1957's notion of taste-based discrimination to the setting of listwise rankings. Although an algorithm will not typically have explicit racial animus, an algorithm may (approximately) maximize such an objective if there are biases in the training data so that the expected value of the outcome in the training data for $G=1$ is $\tau$ below its value in the target population.
We now provide two main theoretical results. First, we show that unbiasedness by the Ranker implies a system of conditional moment inequalities. Second, we show that these moment inequalities are a sharp implication of unbiased behavior.
It is straightforward to show that the change in the objective from permuting the candidates in positions $a$ and $b$ is proportional to $Y_{j_q(a)q} - Y_{j_q(b)q}$. Proposition (ref) thus intuitively states that if the Ranker is unbiased, then we shouldn't be able to permute the position of the candidates in positions $a$ and $b$ whenever we see $G_q = g$ and improve the objective. In other words, higher ranked candidates should always have higher values of $Y$ on average, regardless of the group orientation of the query.
Our next result formalizes the notion that the inequalities in Proposition (ref) are the only testable implication of unbiasedness by the Ranker. It states that if the observed data satisfies the moment inequalities in Proposition (ref), then there exists a latent distribution for the covariates $X_q$ such that the observed distribution corresponds with unbiased behavior by the decision-maker.
We now discuss how one can test the hypothesis that a Ranker is unbiased given a sample of queries $q=1,...,Q$. For simplicity, we will focus on the case where the queries $q$ are i.i.d., although the approach we describe will extend easily to clustered or weakly dependent data.
\paragraph{Pointwise tests.} We first note that for fixed values of $a,b$ and $g$, the hypothesis that equation ((ref)) holds is simply the hypothesis that the population mean of $Y_{j_q(a)q} - Y_{j_q(b)q}$ is larger than zero among the population of queries with $G_q = g$. This individual hypothesis can be tested with a standard one-sided $t$-test for the mean of the population with $G_q = g$. Such tests will be asymptotically valid under standard regularity conditions that allow for an application of a central limit theorem. These individual tests for fixed values of $(a,b,g)$ are useful in that they can help identify where (if anywhere) the Decisionmaker appears to be making biased decisions, which may be useful in addressing any detected bias.
\paragraph{Joint tests.} Although the individual tests described above will be valid for each individual hypothesis for a fixed $(a,b,g)$ combination, it is well known that there is a problem of multiple hypothesis testing if such tests are conducted for each possible value of $(a,b,g)$. Fortunately, a large literature in econometrics has developed joint tests for a system of moment inequalities such as ((ref)) for all relevant $(a,b,g)$; see, for instance, canay_practical_2017, molinari_chapter_2020 for recent reviews.
\paragraph{Choice of Moments.} One important practical point for implementation is that the dimensionality of the vector $G_q$ can be quite large in practice: for example, if $g$ takes on two values and there are 30 candidates in the query, then there are $2^{30} \approx 10^9$ possible values of $G_q$. To reduce the dimensionality in our implementation below, when comparing the outcomes of rank $a$ to rank $b$, we condition on the group membership of the candidates in ranks $a$ and $b$ (i.e. $G_{q,a},G_{q,b}$), but not on the group status of the other candidates in the list, which substantially reduces the dimensionality. Although in theory this may reduce the power of the test, we suspect that most of the pertinent information about the outcomes for ranks $a$ and $b$ is captured by their own group status, and not by the group status of other candidates in the query. In our implementation we also only test moments comparing adjacent ranks, which as discussed in Remark (ref), is equivalent to the null hypothesis across all ranks.
\paragraph{Position effects.} Our analysis so far has assumed that the outcome for candidate $j$ does not depend on their rank in the query. In practice, however, there may be causal effects of position on the outcome, e.g. the same candidate may get more clicks if ranked higher in a search on LinkedIn. If the Auditor knows the causal effect of position -- e.g., from an experiment that randomizes search order -- the inequalities can be adjusted to account for this. In particular, suppose the Auditor knows that putting a candidate in position $a$ increases outcomes by a factor of $(1+\gamma)$ relative to ranking the same candidate in position $b$. Then the change in the objective from swapping the candidate in positions $a$ and $b$ would be proportional to $(1 + \gamma) Y_{j_q(b)q} - Y_{j_q(a)q}$, i.e. a comparison of the outcomes that each candidate would have reached if they had been placed in position $b$. Optimizing behavior by the Ranker implies that this swap can't improve the objective, and thus yields the inequality $$E[ Y_{j_q(a)q} - (1+\gamma) Y_{j_q(b)q} \,|\, G_q = g] \geq 0$$ instead of ((ref)). Note that this is equivalent to testing ((ref)) where the outcome used is the “position-adjusted” outcome rather than the observed outcome, as in Example (ref).
\paragraph{Partially observed features.} Our analysis so far has assumed that the features $X$ are completely unobserved by the auditor. In practice, a subset of the features used by the decisions-maker may be observed: that is, $X_q = (X^O_q, X^U_q)$, where $X^O_q$ are features observed by the auditor and $X^U_q$ are unobserved features. In this case, the same arguments above can be applied within each group of candidates with the same observable features -- i.e, conditional on $X^O_q$. Thus, the sharp testable implication of unbiased rankings in this case is that $$E[ Y_{j_q(a)q} - Y_{j_q(b)q} \,|\, G_q = g, X^O_q = x] \geq 0$$ for almost-every $(g,x)$. Such inequalities can be tested using methods for conditional moment inequalities andrews_inference_2013.
We now provide a validation exercise using data from LinkedIn's InstaJobs algorithm.\footnote{The version of this algorithm studied in this paper has subsequently been deprecated.}
\paragraph{Background.} InstaJobs is an algorithm that sends LinkedIn members (candidates) a notification about a job posting that they may be interested in.\footnote{Here “candidates” refers to LinkedIn members who are candidates for receiving a notification regarding a job posting.} The algorithm uses features about the job posting and the candidates to predict the probability the candidate will apply for the job as well as the probability the application will receive attention from the recruiter. Specifically, the algorithm scores candidates based on the predicted value for the outcome
where $\alpha \in (0,1)$ is a (proprietary) scalar parameter that determines the relative weight placed on applications versus recruiter attention. All candidates with a score above a certain threshold are sent a notification.
\paragraph{Creating Listwise Rankings.} Importantly, InstaJobs is not a listwise ranking algorithm, but rather a pointwise classification algorithm that creates a score and takes a binary decision based on this score. However, we can generate data as if InstaJobs were a list-wise ranking algorithm by rank-ordering the candidates for each job by the score the InstaJob algorithm assigned them. An advantage of this approach is that, since we have access to the true scores underlying the InstaJobs algorithm, we can validate the listwise approach by investigating whether it produces similar answers to a direct investigation of the scores generating the rankings. Also, since InstaJobs is not actually a ranking algorithm, its results should not be subjected to potential position bias.
\paragraph{Practical Implementation.} We have data on the InstaJobs algorithm scores for approximately 193,000 jobs. We create a ranked list of the top 11 candidates for each job based on the InstaJobs score.\footnote{We restrict only to candidates who receive a notification, since outcomes are only available for these candidates. Thus, some queries will have fewer candidates if fewer than 11 people were notified for a given job.} (We use the top 11 candidates so that we can make 10 comparisons between adjacent ranks.) We then implement the listwise outcome test, using gender as the group variable and NDCG as the objective (see Example (ref)). We construct tests for each individual comparison using one-sided $t$-tests, and joint tests based on moment inequality tests with least-favorable critical values that assume all moments have mean-zero (e.g. andrews_inference_2010).\footnote{Formally, we create unconditional moments of the form $E\left[ \left(Y_{j_q(a)q} - Y_{j_q(a+1)q} \right) 1[G_{q,a} = g_1, G_{q,a+1} = g_2] \right] \geq 0 $, where $Y$ is the relevance score $Y^*$ normalized by the IDCG, as in Example (ref).} For comparison, we also can look directly at whether the score is calibrated to check whether marginally-notified candidates have the same outcomes regardless of their gender, where the outcome is the algorithm's objective function given in equation ((ref)).
\paragraph{Results.} Figure (ref) shows estimates of the moments comparing adjacent ranks. The left panel compares the average value of $Y$ for women in one rank relative to men in the adjacent rank below, with the x-axis denoting the rank of the woman. We see that the point estimate is negative for all ranks, indicating that the lower-ranked men actually have better outcomes than the women ranked immediately above them, which means that we could improve the objective function (NDCG) by swapping their ranks. Moreover, the differences are individually statistically significant for 8 of the 10 ranks, and we can jointly reject the hypothesis that all of differences are non-negative ($p < 0.01$; see Table (ref) for exact $p$-values). The right panel of Figure (ref) makes similar comparisons, except between higher-ranked men and lower-ranked women, and finds only positive differences. In contrast to the results in the left panel, we see that men ranked above women do tend to have better outcomes. The listwise outcome test thus suggests that the algorithm is systematically ranking men below women despite having better outcomes. Since our data allows us to look at the scores generating the ranks, we can validate the listwise outcome test by looking at the outcomes by score directly: the binned scatter plot in Figure (ref) shows that men with a given score do indeed have systematically higher outcomes than women with the same score, confirming the conclusion of the listwise outcome test.\footnote{This is true even if we impose a linear control for variation of scores within each score decile.}
This paper considers how to test for discrimination when the decision-maker (which could be a human or algorithm) produces a listwise ranking. We show that a sharp testable implication of unbiased behavior is a system of moment inequalities, and discuss how these can be tested in practice. We validate the methodology using the InstaJobs algorithm at LinkedIn. In future work, we plan to apply this methodology to other listwise rankings algorithms at LinkedIn.
\counterwithin{figure}{section} \counterwithin{table}{section}