Comparing Fair Ranking Metrics

Introduction

Ranked lists are frequently used in information retrieval (IR) to present items in response to users’ information needs. Through the ranked list, a system exposes items (and their providers) to users, and this visibility affects what users discover, consume, and purchase. Further, exposure is not always evenly or fairly distributed (Diaz et al., 2020). Inequitable exposure can disadvantage content providers individually (when an item receives more or less exposure than other items of comparable relevance) or on a group basis (when a group of items or providers are systematically under- or over-exposed). Fairness in IR is a broad topic encompassing many concerns, including the concerns of multiple stakeholders (Burke, 2017) and variety of fairness objectives that may be pursued (Zehlike et al., 2021). Fairness is also a complex and contested social construct (Selbst et al., 2019), so there is not one fairness goal that can be achieved; rather, fairness objectives and metrics need to be selected for a particular application and set of concerns. For a fuller treatment of fairness, Mitchell et al. (2021) provide an overview of general concepts of fairness in machine learning systems, and Ekstrand et al. (2021) systematize fairness in IR.

In the last few years, several metrics have been proposed to measure the fairness of rankings in this sense, along with various goals for what it means for a ranking to be fair or unfair towards items and their providers. These metrics have typically been tested on a different applications and data sets, some in IR but many in the contexts of college rankings or university admissions. Kuhlman et al. (2021) compare selected fair ranking metrics for measuring the statistical parity of rankings (whether they provide equal exposure to different groups), and Zehlike et al. (2021) provides a thorough conceptual survey of fair ranking constructs, but there has not yet been a systematic comparison of group fairness metrics for ranked IR outputs (where the system provides different rankings in response to for different information needs — both prior comparisons focus on rankings for a single need), or direct comparisons within the same data set and experiment. Applying fair ranking metrics to real IR experiment data reveals challenges with their practical applications, including incomplete data (for both relevance and group membership) and the occurrence of edge cases such as groups with no relevant (or retrieved) items.

In this work we specifically consider ways of assessing if the rankings a system produces are fair or unfair to content providers from particular (often demographic) groups; this is provider-side group fairness (Burke, 2017). We adopt the common frame inspired by United States anti-discrimination law of a “protected group”: a class of people who share a trait upon which a retrieval or classification should not be discriminatory (Xiang and Raji, 2019). Our goal is to provide insight on how to measure the provider-side group fairness of the ranked outputs in actual IR experiments (search and recommendations) using metrics from the existing literature, comparing them and documenting limitations in their practical application. This paper has three contributions:

We describe rank fairness metrics in a unified notation for IR applications, identifying design points, similarities, and differences.

We identify gaps between the conceptual form of the metrics and the practicalities of applying them search and recommendation experiments.

We directly compare metric results with the same data and systems across multiple search and recommendation data sets.

Fair Ranking Metrics

We begin by describing the fair ranking metrics, summarized in table 1, in a common framework and notation. This enables direct comparison of their designs and theoretical behavior, and facilitates easier implementation in IR experiments. In some cases, we assign new name for metrics based on their functionality, purpose, and comparability within our synthesis.

We consider an IR system that retrieves a ranked list $L$ of $n$ documents $d_{1},d_{2},\dots,d_{n}$ $\in D$ in response to requests (query in a search system or a user in recommender system) $q_{1},q_{2},\dots,q_{n}\in Q$ (notation summarized in table 2). Documents may have an associated request-specific relevance score $y(d|q)$, and the system may estimate this by a predictor $\hat{y}(d|q)$. Providers are associated with one (or more) of $g$ groups. We represent this by giving each document an alignment vector $\mathcal{G}(d)\in^{g}$ (s.t. $\|\mathcal{G}(d)\|_{1}=1$) indicating its group association; generalizing from a categorical variable to a vector allows soft association (mixed or partial membership) or uncertainty about membership (Sapiezynski et al., 2019). We generalize $g$ to a list function, with $\mathcal{G}(L)$ denoting an $n\times g$ alignment matrix whose rows correspond to the documents of $L$ and columns are groups. In the case of definitively-known membership in a binomial pair of groups, $\mathcal{G}^{+}(L)$ denotes the set of documents in $L$ in the “protected” group and $\mathcal{G}^{-}(L)$ the remaining documents.

Our goal is to measure exposure (sometimes called attention) each document, content provider, or group receives, and assess the fairness of this distribution to ensure demographic or statistical parity (ensures comparable outcomes across groups or equality of opportunities (ensures equal treatment based on merit or utility irrespective of the group membership). Accounting for the decreasing attention users are likely to pay to documents at deeper rank positions (position bias) requires a browsing model; some metrics build this implicitly into their structure, while others explicitly model it as a position weight vector $\mathbf{a}_{L}$ for $L$. Table 3 describes the various weighting schemes used by the metrics we survey. The resulting exposure is then sometimes compared with a target distribution $\hat{\textbf{p}}$ that represents across groups. There are several ways of computing $\hat{\textbf{p}}$, including strict group equality, an estimate of the distribution of actual or potential content providers, or the distribution among providers of relevant documents.

2. Statistical Parity in Single Rankings

We begin with metrics that assess the fairness of a single ranking and only measure exposure equity without considering relevance (that is, they target statistical parity). These metrics can be aggregated over the rankings produced by a system, e.g. by taking the mean, to produce an overall system fairness score.

FAIR limits applicability into binomial distribution and fixed group association.

3. Statistical Parity in Multiple Rankings

Singh and Joachims (2018) and Diaz et al. (2020) each propose metrics for measuring statistical parity over ranking policies. Neither metric incorporates a target distribution; they are optimal when all groups are equally exposed. Demographic parity (DP, Singh and Joachims, 2018) measures the difference in exposure between two groups:The original paper presented a constraint, not a metric, for demographic parity; we have implemented it as a ratio to be consistent with the other metrics.

Expected exposure disparity (EED, Diaz et al., 2020) ensures well-distributed exposure by measuring the inequality in exposure distribution across groups with the $L_{2}$ norm:

4. Equal Opportunity in Multiple Rankings

So far, none of the metrics we have discussed account for the utility of the ranked results — rankings do well by exposing providers regardless of the utility of their items. The intuition behind incorporating utility, articulated independently by Singh and Joachims (2018) and Biega et al. (2018), is that exposure should be proportional to relevance: if an item or a group contributes 10% of the relevance to a request (user and/or query), it should receive approximately 10% of the exposure. This is a ranked analog of the equality of opportunity construct from fair classification (Hardt et al., 2016): outcome is conditionally independent of group given utility.

EUR and RUR do not allow multinomial protected groups and soft associations.

Biega et al. (2018) present the amortized attention construct to measure exposure over the sequence of rankings. This compares rank exposure with expected utility $\hat{\Upsilon}$ (computed with system-predicted utility $\hat{y}(d|q)$) instead of ground truth relevance assessments $y(d|q)$), measuring whether the system allocates exposure proportional to the utility it estimates items to have. Deviations from this goal are measured by taking the $L_{1}$ norm of the group exposure-utility differences, yielding the Inequity of Amortized Attention (IAA) metric:

Neither IAA nor the EE metrics distinguish between group over- or under-exposure; for both, is perfectly fair and larger values are unfair, with no preferential treatment given to a protected group. The common thread between these metrics, articulated by Diaz et al. (2020), is that for a fixed information need, differences in exposure between items with the same relevance grade results in unfair outcomes. The only way to address this inequity in practice is by varying the rankings returned by the system, as with a stochastic policy.

5. Pairwise Metrics

Beutel et al. (2019) and Narasimhan et al. (2020) take an entirely different approach by defining fairness objectives over pairwise orderings instead of entire rankings. Pairwise fairness is then defined in terms of the pairwise accuracy for ranking relevant items in different groups:

A ranking satisfies pairwise equal opportunity(Narasimhan et al., 2020) if pairs of documents are equally likely to be ranked consistently with their relevance regardless of the group membership of the items in the pair. This can be measured by the group’s pairwise accuracy with respect to all items ($A_{G^{i}>:})$, its inter-group accuracy ($A_{\mathcal{G}^{1}>\mathcal{G}^{2}}$), or its intra-group accuracy ($A_{\mathcal{G}^{1}>\mathcal{G}^{1}}$). Given protected and unprotected groups, we can define a fairness metric as the difference in pairwise accuracy:

6. Assessing Metric Design

Rendering metrics in a common notation elicits that the metrics are quite similar in their basic concepts. The fundamental construct — weighted exposure — is the same across most metrics (pairwise fairness being an exception), and they differ primarily in how they relate exposure to relevance and how they aggregate and compare exposure distributions. The following questions help identify more precisely what their salient differences are and how those may relate to particular IR applications and experimental settings.

Does the metric incorporate relevance? EEL, EER, EUR, RUR, IAA, and PAIR directly incorporate relevance into the metric; others strictly measure statistical parity. It is desired depending on the precise task and evaluation goal. Statistical parity metrics are useful for measuring relative fairness of rankings already optimized for utility, particularly when there is no relevance information available or large relevant sets available. They can also be used to detect discrepancies that may indicate unfairness in relevance data. However, using such metrics in isolation for evaluation or optimization may reduce ranking quality.

How does it handle missing data? Real-world data sets are often incomplete, missing relevance and/or group labels for many documents. Metrics that are less vulnerable towards that problem will be easier to apply in such cases. Missing relevance data affects EUR, RUR, EER, and EEL like it does classical IR evaluation metrics such as nDCG; the straightforward but biased approach is to treat items with unknown relevance as irrelevant ($y=0$). IAA’s use of system-estimated relevance allows it to sidestep missing relevance problem.

Empirical Comparison

To complement our comparison, we implement the metrics to measure the fairness of systems from prior experiments in search and recommendation.

Table 5 summarizes our experimental data. For search experiments, we used submitted runs and evaluations from the TREC Fair Ranking Track 2019 (Biega et al., 2019) and 2020 (Biega et al., 2020). These runs covered three tasks across two years, all on scholarly search: re-ranking tasks from 2019 and 2020 and an ad-hoc retrieval task from 2020. Each document has a soft association with the economic development level of its author(s), and we consider each submitted run as an individual system and used the given sequences of rankings for each system.

For the recommendation task, we re-used the experiment and code from Ekstrand and Kluver (2020) to measure 4 algorithms from the LensKit software (Ekstrand, 2020) on data from GoodReads (Wan and McAuley, 2018), modifying the experiment to use 5 interactions per user as test data instead of the original 1. Group membership is binary, with female authors as the protected groupBinary gender membership is a limitation of the original study; see Ekstrand and Kluver (2020) for details.; membership is unknown for some items. We sampled 5000 users, each of which had at least 10 book interactions, for our experiment, holding out 5 interactions per user as test data for assessing relevance in the resulting recommendations. We measured the fairness of the recommendations produced for these users by four collaborative filtering (CF) algorithms: user-based CF (UU, (Herlocker et al., 1999)), item based CF (I-I, (Deshpande and Karypis, 2004)), matrix factorization (WRLS, (Takács et al., 2011)), and Bayesian Personalized Ranking (BPR, (Rendle et al., 2012)), using algorithms and hyper-parameter tunings from Ekstrand and Kluver (2020).

2. Metric Implementations

We implemented metrics from Section 2 in Python to measure the fairness of the runs from the experiments we consider.

We did need to make some further decisions and adjustments to the remaining metrics in our experiment:

For IAA and the EE* metrics on the recommendation experiment, we treat unknown gender as a third author group.

PAIR do not depend only on the top-$N$ list — they are functions of the system’s overall ranking between items. Therefore, instead of computing them from ranked output we directly measured the recommendation model’s scores for a sample of items. For each test item, we sampled 10,000 items not rated by the target user as negative examples, and used these to estimate the probability of correct orderings. This proved relatively efficient for our experiment size. We could not test these metrics on FairTREC because we do not have access to full rankings or the systems’ relevance scores.

3. Empirical Results

Conclusion, Recommendations, and Future Directions

Many metrics have been proposed for measuring the fairness of ranked outputs. Through analytically and empirically comparing fair ranking metrics, we have identified several of their key commonalities and differences, assumptions and crucial design decisions, and have presented them in a form amenable to implementation in IR experiments. Our empirical results highlight the need for further research to identify the implications of these metrics’ disagreements, as well as the impact of specific design decisions and configurations, but our analytical comparison (Section 2) and implementation experience allow us to make some preliminary recommendations for selecting a metric:

Demographic Parity in Sequences Again, due to support for multinomial groups and soft association, along with edge-case problems in ratio-based metrics, EED looks like the best current choice for this case.

Equal Opportunity in Sequences We currently recommend using EEL and EER because they allow multinomial groups with soft association, and selectable target distribution. If sparse relevance judgments are a problem, IAA is a good choice and can be applied with multinomial groups and soft associations.

There is significant further work needed to advance the robust measurement of ranking fairness. Data sparsity and ambiguity are a significant problem; there has been work on allowing missing (Kırnap et al., 2021), ambiguous, or multiple group associations (Ghosh et al., 2021) that needs to be incorporated into flexible metrics. We also need further study on the implications of specific design and parameter choices; our empirical results have shown notable disagreement between metrics, but we do not yet know which of the various design decisions is responsible for these differences, or how metric values change in response to particular aspects of the data set or system rankings.

We believe our synthesis and comparison will lay a valuable foundation for this vital and ongoing work.

References