Controlling Fairness and Bias in Dynamic Learning-to-Rank

Introduction

We consider the problem of dynamic Learning-to-Rank (LTR), where the ranking function dynamically adapts based on the feedback that users provide. Such dynamic LTR problems are ubiquitous in online systems — news-feed rankings that adapt to the number of ”likes” an article receives, online stores that adapt to the number of positive reviews for a product, or movie-recommendation systems that adapt to who has watched a movie. In all of these systems, learning and prediction are dynamically intertwined, where past feedback influences future rankings in a specific form of online learning with partial-information feedback (Cesa-Bianchi and Lugosi, 2006).

While dynamic LTR systems are in widespread use and unquestionably useful, there are at least two issues that require careful design considerations. First, the ranking system induces a bias through the rankings it presents. In particular, items ranked highly are more likely to collect additional feedback, which in turn can influence future rankings and promote misleading rich-get-richer dynamics (Adamic and Huberman, 2000; Salganik et al., 2006; Joachims et al., 2007; Joachims et al., 2017). Second, the ranking system is the arbiter of how much exposure each item receives, where exposure directly influences opinion (e.g. ideological orientation of presented news articles) or economic gain (e.g. revenue from product sales or streaming) for the provider of the item. This raises fairness considerations about how exposure should be allocated based on the merit of the items (Singh and Joachims, 2018; Biega et al., 2018). We will show in the following that naive dynamic LTR methods that are oblivious to these issues can lead to economic disparity, unfairness, and polarization.

In this paper, we present the first dynamic LTR algorithm – called FairCo – that overcomes rich-get-richer dynamics while enforcing a configurable allocation-of-exposure scheme. Unlike existing fair LTR algorithms (Singh and Joachims, 2018; Biega et al., 2018; Singh and Joachims, 2019; Yadav et al., 2019), FairCo explicitly addresses the dynamic nature of the learning problem, where the system is unbiased and fair even though the relevance and the merit of items are still being learned. At the core of our approach lies a merit-based exposure-allocation criterion that is amortized over the learning process (Singh and Joachims, 2018; Biega et al., 2018). We view the enforcement of this merit-based exposure criterion as a control problem and derive a P-controller that optimizes both the fairness of exposure as well as the quality of the rankings. A crucial component of the controller is the ability to estimate merit (i.e. relevance) accurately, even though the feedback is only revealed incrementally as the system operates, and the feedback is biased by the rankings shown in the process (Joachims et al., 2007). To this effect, FairCo includes a new unbiased cardinal relevance estimator – as opposed to existing ordinal methods (Joachims et al., 2017; Agarwal et al., 2019a) –, which can be used both as an unbiased merit estimator for fairness and as a ranking criterion.

In addition to the theoretical justification of FairCo, we provide empirical results on both synthetic news-feed data and real-world movie recommendation data. We find that FairCo is effective at enforcing fairness while providing good ranking performance. Furthermore, FairCo is efficient, robust, and easy to implement.

Motivation

Consider the following illustrative example of a dynamic LTR problem. An online news-aggregation platform wants to present a ranking of the top news articles on its front page. Through some external mechanism, it identifies a set ${\mathcal{D}}=\{d_{1},...,d_{20}\}$ of 20 articles at the beginning of each day, but it is left with the learning problem of how to rank these 20 articles on its front page. As users start coming to the platform, the platform uses the following naive algorithm to learn the ranking.

Executing this algorithm at the beginning of a day, the platform starts by presenting the 20 articles in random order for the first user. It may then observe that the user reads the article in position 3 and increments the counter $C(d)$ for this article. For the next user, this article now gets ranked first and the counters are updated based on what the second user reads. This cycle continues for each subsequent user. Unfortunately, this naive algorithm has at least two deficiencies that make it suboptimal or unsuitable for many ranking applications.

The first deficiency lies in the choice of $C(d)$ as an estimate of average relevance for each article – namely the fraction of users that want to read the article. Unfortunately, even with infinite amounts of user feedback, the counters $C(d)$ are not consistent estimators of average relevance (Salganik et al., 2006; Joachims et al., 2007; Joachims et al., 2017). In particular, items that happened to get more reads in early iterations get ranked highly, where more users find them and thus have the opportunity to provide more positive feedback for them. This perpetuates a rich-get-richer dynamic, where the feedback count $C(d)$ recorded for each article does not reflect how many users actually wanted to read the article.

The second deficiency of the naive algorithm lies in the ranking policy itself, creating a source of unfairness even if the true average relevance of each article was accurately known (Singh and Joachims, 2018; Biega et al., 2018; Asia Biega, 2019). Consider the following omniscient variant of the naive algorithm that ranks the articles by their true average relevance (i.e. the true fraction of users who want to read each article). How can this ranking be unfair? Let us assume that we have two groups of articles, $G_{\text{right}}$ and $G_{\text{left}}$, with 10 items each (i.e. articles from politically right- and left-leaning sources). 51% of the users (right-leaning) want to read the articles in group $G_{\text{right}}$, but not the articles in group $G_{\text{left}}$. In reverse, the remaining 49% of the users (left-leaning) like only the articles in $G_{\text{left}}$. Ranking articles solely by their true average relevance puts items from $G_{\text{right}}$ into positions 1-10 and the items from $G_{\text{left}}$ in positions 11-20. This means the platform gives the articles in $G_{\text{left}}$ vastly less exposure than those in $G_{\text{right}}$. We argue that this can be considered unfair since the two groups receive disproportionately different outcomes despite having similar merit (i.e. relevance). Here, a 2% difference in average relevance leads to a much larger difference in exposure between the groups.

We argue that these two deficiencies – namely bias and unfairness – are not just undesirable in themselves, but that they have undesirable consequences. For example, biased estimates lead to poor ranking quality, and unfairness is likely to alienate the left-leaning users in our example, driving them off the platform and encouraging polarization.

Furthermore, note that these two deficiencies are not specific to the news example, but that the naive algorithm leads to analogous problems in many other domains. For example, consider a ranking system for job applicants, where rich-get-richer dynamics and exposure allocation may perpetuate and even amplify existing unfairness (e.g. disparity between male and female applicants). Similarly, consider an online marketplace where products of different sellers (i.e. groups) are ranked. Here rich-get-richer dynamics and unfair exposure allocation can encourage monopolies and drive some sellers out of the market.

These examples illustrate the following two desiderata that a less naive dynamic LTR algorithm should fulfill.

The algorithm should not be biased or subject to rich-get-richer dynamics.

The algorithm should enforce a fair allocation of exposure based on merit (e.g. relevance).

With these two desiderata in mind, this paper develops alternatives to the Naive algorithm. In particular, after introducing the dynamic learning-to-rank setting in Section 4, Section 5 formalizes an amortized notion of merit-based fairness, accounting for the fact that merit itself is unknown at the beginning of the learning process and is only learned throughout. Section 6 then addresses the bias problem, providing estimators that eliminate the presentation bias for both global and personalized ranking policies. Finally, Section 7 proposes a control-based algorithm that is designed to optimize ranking quality while dynamically enforcing fairness.

Related Work

Ranking algorithms are widely recognized for their potential for societal impact (Baeza-Yates, 2018), as they form the core of many online systems, including search engines, recommendation systems, news feeds, and online voting. Controlling rich-get-richer phenomena in recommendations and rankings has been studied from the perspective of both optimizing utility through exploration as well as ensuring fairness of such systems (Yin et al., 2012; Schnabel et al., 2016; Abdollahpouri et al., 2017). There are several adverse consequences of naive ranking systems (Ciampaglia et al., 2018), such as political polarization (Beam, 2014), misinformation (Vosoughi et al., 2018), unfair allocation of exposure (Singh and Joachims, 2019), and biased judgment (Baeza-Yates, 2018) through phenomena such as the Matthew effect (Adamic and Huberman, 2000; Germano et al., 2019). Viewing such ranking problems as two-sided markets of users and items that each derive utility from the ranking system brings a novel perspective to tackling such problems (Singh and Joachims, 2018; Abdollahpouri et al., 2019). In this work, we take inspiration from these works to develop methods for mitigating bias and unfairness in a dynamic setting.

Machine learning methods underlie most ranking algorithms. There has been a growing concern around the question of how machine learning algorithms can be unfair, especially given their numerous real-world applications (Barocas and Selbst, 2016). There have been several definitions proposed for fairness in the binary classification setting (Barocas et al., 2018), as well as recently in the domains of rankings in recommendations and information retrieval (Celis et al., 2017; Singh and Joachims, 2018; Biega et al., 2018; Beutel et al., 2019). The definitions of fairness in ranking span from ones purely based on the composition of the top-k (Celis et al., 2017), to relevance-based definitions such as fairness of exposure (Singh and Joachims, 2018), and amortized attention equity (Biega et al., 2018). We will discuss these definitions in greater detail in Section 5. Our work also relates to the recent interest in studying the impact of fairness when learning algorithms are applied in dynamic settings (Liu et al., 2018; Ensign et al., 2018; Tabibian et al., 2019).

In information retrieval, there has been a long-standing interest in learning to rank from biased click data. As already argued above, the bias in logged click data occurs because the feedback is incomplete and biased by the presentation. Numerous approaches based on preferences (e.g. (Herbrich et al., 2000; Joachims, 2002)), click models (e.g. (Chuklin et al., 2015)), and randomized interventions (e.g. (Radlinski and Joachims, 2006)) exist. Most recently, a new approach for de-biasing feedback data using techniques from causal inference and missing data analysis was proposed to provably eliminate selection biases (Joachims et al., 2017; Ai et al., 2018). We follow this approach in this paper, extend it to the dynamic ranking setting, and propose a new unbiased regression objective in Section 6.

Learning in our dynamic ranking setting is related to the conventional learning-to-rank algorithms such as LambdaRank, LambdaMART, RankNet, Softrank etc. (Burges, 2010; Taylor et al., 2008). However, to implement fairness constraints based on merit, we need to explicitly estimate relevance to the user as a measure of merit while the scores estimated by these methods don’t necessarily have a meaning. Our setting is also closely related to online learning to rank for top-k ranking where feedback is observed only on the top-k items, and hence exploration interventions are necessary to ensure convergence (Radlinski et al., 2008; Hofmann et al., 2013; Zoghi et al., 2017; Li et al., 2018). These algorithms are designed with respect to a click-model assumption (Zoghi et al., 2017) or learning in the presence of document features (Li et al., 2018). A key difference in our method is that we do not consider exploration through explicit interventions, but merely exploit user-driven exploration. However, explicit exploration could also be incorporated into our algorithms to improve the convergence rate of our methods.

Dynamic Learning-to-Rank

We begin by formally defining the dynamic LTR problem. Given is a set of items ${\mathcal{D}}$ that needs to be ranked in response to incoming requests. At each time step $t$, a request

arrives i.i.d. at the ranking system. Each request consists of a feature vector describing the user’s information need $\bm{x}_{t}$ (e.g. query, user profile), and the user’s vector of true relevance ratings $\operatorname{\mathbf{r}}_{t}$ for all items in the collection ${\mathcal{D}}$. Only the feature vector $\bm{x}_{t}$ is visible to the system, while the true relevance ratings $\operatorname{\mathbf{r}}_{t}$ are hidden. Based on the information in $\bm{x}_{t}$, a ranking policy ${\pi}_{t}(\bm{x})$ produces a ranking $\bm{\sigma}_{t}$ that is presented to the user. Note that the policy may ignore the information in $\bm{x}_{t}$, if we want to learn a single global ranking like in the introductory news example.

After presenting the ranking $\bm{\sigma}_{t}$, the system receives a feedback vector $\operatorname{\mathbf{c}}_{t}$ from the user with a non-negative value $\operatorname{\mathbf{c}}_{t}(d)$ for every $d\in{\mathcal{D}}$. In the simplest case, it is $1$ for click and for no click, and we will use the word ”click” as a placeholder throughout this paper for simplicity. But the feedback may take many other forms and does not have to be binary. For example, in a video streaming service, the feedback may be the percentage the user watched of each video.

After the feedback $\operatorname{\mathbf{c}}_{t}$ was received, the dynamic LTR algorithm $\operatorname{{\mathcal{A}}}$ now updates the ranking policy and produces the policy ${\pi}_{t+1}$ that is used in the next time step.

An instance of such a dynamic LTR algorithm is the Naive algorithm already outlined in Section 2. It merely computes $\sum\operatorname{\mathbf{c}}_{t}$ to produce a new ranking policy for $t+1$ (here a global ranking independent of $\bm{x}$).

A key challenge of dynamic LTR lies in the fact that the feedback $\operatorname{\mathbf{c}}_{t}$ provides meaningful feedback only for the items that the user examined. Following a large body of work on click models (Chuklin et al., 2015), we model this as a censoring process. Specifically, for a binary vector $\operatorname{\mathbf{e}}_{t}$ indicating which items were examined by the user, we model the relationship between $\operatorname{\mathbf{c}}_{t}$ and $\operatorname{\mathbf{r}}_{t}$ as follows.

Coming back to the running example of news ranking, $\operatorname{\mathbf{r}}_{t}$ contains the full information about which articles the user is interested in reading, while $\operatorname{\mathbf{c}}_{t}$ reveals this information only for the articles $d$ examined by the user (i.e. $\operatorname{\mathbf{e}}_{t}(d)=1$). Analogously, in the job placement application $\operatorname{\mathbf{r}}_{t}$ indicates for all candidates $d$ whether they are qualified to receive an interview call, but $\operatorname{\mathbf{c}}_{t}$ reveals this information only for those candidates examined by the employer.

A second challenge lies in the fact that the examination vector $\operatorname{\mathbf{e}}_{t}$ cannot be observed. This implies that a feedback value of $\operatorname{\mathbf{c}}_{t}(d)=0$ is ambiguous – it may either indicate lack of examination (i.e. $\operatorname{\mathbf{e}}_{t}(d)=0$) or negative feedback (i.e. $\operatorname{\mathbf{r}}_{t}(d)=0$). This would not be problematic if $\operatorname{\mathbf{e}}_{t}$ was uniformly random, but which items get examined is strongly biased by the ranking $\bm{\sigma}_{t}$ presented to the user in the current iteration. Specifically, users are more likely to look at an item high in the ranking than at one that is lower down (Joachims et al., 2007). We model this position bias as a probability distribution on the examination vector

Most click models can be brought into this form (Chuklin et al., 2015). For the simplicity of this paper, we merely use the Position-Based Model (PBM) (Craswell et al., 2008). It assumes that the marginal probability of examination $\operatorname{\mathbf{p}}_{t}(d)$ for each item $d$ depends only on the rank $\operatorname{rank}(d|\bm{\sigma})$ of $d$ in the presented ranking $\bm{\sigma}$. Despite its simplicity, it was found that the PBM can capture the main effect of position bias accurately enough to be reliable in practice (Joachims et al., 2017; Wang et al., 2018; Agarwal et al., 2019b).

2. Evaluating Ranking Performance

We measure the quality of a ranking policy ${\pi}$ by its utility to the users. Virtually all ranking metrics used in information retrieval define the utility $U(\bm{\sigma}|\operatorname{\mathbf{r}})$ of a ranking $\bm{\sigma}$ as a function of the relevances of the individual items $\operatorname{\mathbf{r}}$. In our case, these item-based relevances $\operatorname{\mathbf{r}}$ represent which articles the user likes to read, or which candidates are qualified for an interview. A commonly used utility measure is the DCG (Järvelin and Kekäläinen, 2002)

or the NDCG when normalized by the DCG of the optimal ranking. Over a distribution of requests $\operatorname{P}(\bm{x},\operatorname{\mathbf{r}})$, a ranking policy ${\pi}(\bm{x})$ is evaluated by its expected utility

3. Optimizing Ranking Performance

The user-facing goal of dynamic LTR is to converge to the policy ${\pi}^{*}=\operatorname{argmax}_{\pi}U({\pi})$ that maximizes utility. Even if we solve the problem of estimating $U({\pi})$ despite our lack of knowledge of $\operatorname{\mathbf{e}}$, this maximization problem could be computationally challenging, since the space of ranking policies is exponential even when learning just a single global ranking. Fortunately, it is easy to show (Robertson, 1977) that sorting-based policies

are optimal for virtually all $U(\bm{\sigma}|\operatorname{\mathbf{r}})$ commonly used in IR (e.g. DCG). So, the problem lies in estimating the expected relevance ${R}(d|\bm{x})$ of each item $d$ conditioned on $\bm{x}$. When learning a single global ranking, this further simplifies to estimating the expected average relevance ${R}(d)=\int\operatorname{\mathbf{r}}(d)\>d\operatorname{P}(\operatorname{\mathbf{r}},\bm{x})$ for each item $d$. The global ranking can then be derived via

In Section 6, we will use techniques from causal inference and missing-data analysis to design unbiased and consistent estimators for ${R}(d|\bm{x})$ and ${R}(d)$ that only require access to the observed feedback $\operatorname{\mathbf{c}}_{t}$.

Fairness in Dynamic LTR

While sorting by ${R}(d|\bm{x})$ (or ${R}(d)$ for global rankings) may provide optimal utility to the user, the introductory example has already illustrated that this ranking can be unfair. There is a growing body of literature to address this unfairness in ranking, and we now extend merit-based fairness (Singh and Joachims, 2018; Biega et al., 2018) to the dynamic LTR setting.

The key scarce resource that a ranking policy allocates among the items is exposure. Based on the model introduced in the previous section, we define the exposure of an item $d$ as the marginal probability of examination $\operatorname{\mathbf{p}}_{t}(d)=\operatorname{P}(\operatorname{\mathbf{e}}_{t}(d)=1|\bm{\sigma}_{t},\bm{x}_{t},\operatorname{\mathbf{r}}_{t})$. It is the probability that the user will see $d$ and thus have the opportunity to read that article, buy that product, or interview that candidate. We discuss in Section 6 how to estimate $\operatorname{\mathbf{p}}_{t}(d)$. Taking a group-based approach to fairness, we aggregate exposure by groups $\mathcal{G}=\{G_{1},\dots,G_{m}\}$.

These groups can be legally protected groups (e.g. gender, race), reflect some other structure (e.g. items sold by a particular seller), or simply put each item in its own group (i.e. individual fairness).

In order to formulate fairness criteria that relate exposure to merit, we define the merit of an item as its expected average relevance ${R}(d)$ and again aggregate over groups.

In Section 6, we will discuss how to get unbiased estimates of ${Merit}(G_{i})$ using the biased feedback data $\operatorname{\mathbf{c}}_{t}$.

With these definitions in hand, we can address the types of disparities identified in Section 2. Specifically, we extend the Disparity of Treatment criterion of (Singh and Joachims, 2018) to the dynamic ranking problem, using an amortized notion of fairness as in (Biega et al., 2018). In particular, for any two groups $G_{i}$ and $G_{j}$ the disparity

measures in how far amortized exposure over $\tau$ time steps was fulfilled. This exposure-based fairness disparity expresses in how far, averaged over all time steps, each group of items got exposure proportional to its relevance. The further the disparity is from zero, the greater is the violation of fairness. Note that other allocation strategies beyond proportionality could be implemented as well by using alternate definitions of disparity (Singh and Joachims, 2018).

Exposure can also be allocated based on other fairness criteria, for example, a Disparity of Impact that a specific exposure allocation implies (Singh and Joachims, 2018). If we consider the feedback $\operatorname{\mathbf{c}}_{t}$ (e.g. clicks, purchases, votes) as a measure of impact

then keeping the following disparity close to zero controls how exposure is allocated to make impact proportional to relevance.

We refer to this as the impact-based fairness disparity. In Section 7 we will derive a controller that drives such exposure and impact disparities to zero.

Unbiased Estimators

To be able to implement the ranking policies in Equation (5) and the fairness disparities in Equations (10) and (12), we need accurate estimates of the position bias $\operatorname{\mathbf{p}}_{t}$, the expected conditional relevances ${R}(d|\bm{x})$, and the expected average relevances ${R}(d)$. We consider these estimation problems in the following.

Learning a model for $\operatorname{\mathbf{p}}_{t}$ is not part of our dynamic LTR problem, as the position-bias model is merely an input to our dynamic LTR algorithms. Fortunately, several techniques for estimating position-bias models already exist in the literature (Joachims et al., 2017; Wang et al., 2018; Agarwal et al., 2019b; Fang et al., 2019), and we are agnostic to which of these is used. In the simplest case, the examination probabilities $\operatorname{\mathbf{p}}_{t}(d)$ only depend on the rank of the item in $\bm{\sigma}$, analogous to a Position-Based Click Model (Craswell et al., 2008) with a fixed probability for each rank. It was shown in (Joachims et al., 2017; Wang et al., 2018; Agarwal et al., 2019b) how these position-based probabilities can be estimated from explicit and implicit swap interventions. Furthermore, it was shown in (Fang et al., 2019) how the contextual features $\bm{x}$ about the users and query can be incorporated in a neural-network based propensity model, allowing it to capture that certain users may explore further down the ranking for some queries. Once any of these propensity models are learned, they can be applied to predict $\operatorname{\mathbf{p}}_{t}$ for any new query $\bm{x}_{t}$ and ranking $\bm{\sigma}_{t}$.

2. Estimating Conditional Relevances

The key challenge in estimating ${R}(d|\bm{x})$ from Equation (6) lies in our inability to directly observe the true relevances $\operatorname{\mathbf{r}}_{t}$. Instead, the only data we have is the partial and biased feedback $\operatorname{\mathbf{c}}_{t}$. To overcome this problem, we take an approach inspired by (Joachims et al., 2017) and extend it to the dynamic ranking setting. The key idea is to correct for the selection bias with which relevance labels are observed in $\operatorname{\mathbf{c}}_{t}$ using techniques from survey sampling and causal inference (Horvitz and Thompson, 1952; Imbens and Rubin, 2015). However, unlike the ordinal estimators proposed in (Joachims et al., 2017), we need cardinal relevance estimates since our fairness disparities are cardinal in nature. We, therefore, propose the following cardinal relevance estimator.

The key idea behind this estimator lies in a training objective that only uses $\operatorname{\mathbf{c}}_{t}$, but that in expectation is equivalent to a least-squares objective that has access to $\operatorname{\mathbf{r}}_{t}$. To start the derivation, let’s consider how we would estimate ${R}(d|\bm{x})$, if we had access to the relevance labels $(\operatorname{\mathbf{r}}_{1},...,\operatorname{\mathbf{r}}_{\tau})$ of the previous $\tau$ time steps. A straightforward solution would be to solve the following least-squares objective for a given regression model ${\hat{R}^{\scalebox{0.7}{w}}}(d|\bm{x}_{t})$ (e.g. a neural network), where $w$ are the parameters of the model.

The minimum $w^{*}$ of this objective is the least-squares regression estimator of ${R}(d|\bm{x}_{t})$. Since the $(\operatorname{\mathbf{r}}_{1},...,\operatorname{\mathbf{r}}_{\tau})$ are not available, we define an asymptotically equivalent objective that merely uses the biased feedback $(\operatorname{\mathbf{c}}_{1},...,\operatorname{\mathbf{c}}_{\tau})$. The new objective corrects for the position bias using Inverse Propensity Score (IPS) weighting (Horvitz and Thompson, 1952; Imbens and Rubin, 2015), where the position bias $(\operatorname{\mathbf{p}}_{1},...,\operatorname{\mathbf{p}}_{\tau})$ takes the role of the missingness model.

We denote the regression estimator defined by the minimum of this objective as ${\hat{R}^{\scalebox{0.6}{Reg}}}(d|\bm{x}_{t})$. The regression objective in (14) is unbiased, meaning that its expectation is equal to the regression objective $\mathcal{L}^{\operatorname{\mathbf{r}}}(w)$ that uses the unobserved true relevances $(\operatorname{\mathbf{r}}_{1},...,\operatorname{\mathbf{r}}_{\tau})$.

Line 2 formulates the expectation in terms of the marginal exposure probabilities $\operatorname{P}(\operatorname{\mathbf{e}}_{t}(d)|\bm{\sigma}_{t},\bm{x}_{t})$, which decomposes the expectation as the objective is additive in $d$. Note that $\operatorname{P}(\operatorname{\mathbf{e}}_{t}(d)=1|\bm{\sigma}_{t},\bm{x}_{t})$ is therefore equal to $\operatorname{\mathbf{p}}_{t}(d)$ under our exposure model. Line 3 substitutes $\operatorname{\mathbf{c}}_{t}(d)=\operatorname{\mathbf{e}}_{t}(d)\operatorname{\mathbf{r}}_{t}(d)$ and simplifies the expression, since $\operatorname{\mathbf{e}}_{t}(d)\operatorname{\mathbf{r}}_{t}(d)=0$ whenever the user is not exposed to an item. Note that the propensities $\operatorname{\mathbf{p}}_{t}(\bm{\sigma})$ for the exposed items now cancel, as long as they are bounded away from zero – meaning that all items have some probability of being found by the user. In case users do not naturally explore low enough in the ranking, active interventions can be used to stochastically promote items in order to ensure non-zero examination propensities (e.g. (Hofmann et al., 2013)). Note that unbiasedness holds for any sequence of $(\bm{x}_{1},\operatorname{\mathbf{r}}_{1},\bm{\sigma}_{1})...,(\bm{x}_{T},\operatorname{\mathbf{r}}_{T},\bm{\sigma}_{T})$, no matter how complex the dependencies between the rankings $\bm{\sigma}_{t}$ are.

Beyond this proof of unbiasedness, it is possible to use standard concentration inequalities to show that $\mathcal{L}^{\operatorname{\mathbf{c}}}(w)$ converges to $\mathcal{L}^{\operatorname{\mathbf{r}}}(w)$ as the size $\tau$ of the training sequence increases. Thus, under standard conditions on the capacity for uniform convergence, it is possible to show convergence of the minimizer of $\mathcal{L}^{\operatorname{\mathbf{c}}}(w)$ to the least-squares regressor as the size $\tau$ of the training sequence increases. We will use this regression objective to learn neural-network rankers in Section 8.2.

3. Estimating Average Relevances

The conditional relevances ${R}(d|\bm{x})$ are used in the ranking policies from Equation (5). But when defining merit in Equation (9) for the fairness disparities, the average relevance ${R}(d)$ is needed. Furthermore, ${R}(d)$ serves as the ranking criterion for global rankings in Equation (7). While we could marginalize ${R}(d|\bm{x})$ over $\operatorname{P}(\bm{x})$ to derive ${R}(d)$, we argue that the following is a more direct way to get an unbiased estimate.

The following shows that this estimator is unbiased as long as the propensities are bounded away from zero.

In the following experiments, we will use this estimator whenever a direct estimate of ${R}(d)$ is needed for the fairness disparities or as a global ranking criterion.

Dynamically Controlling Fairness

Given the formalization of the dynamic LTR problem, our definition of fairness, and our derivation of estimators for all relevant parameters, we are now in the position to tackle the problem of ranking while enforcing the fairness conditions. We view this as a control problem since we need to be robust to the uncertainty in the estimates $\hat{R}(d|\bm{x})$ and $\hat{R}(d)$ at the beginning of the learning process. Specifically, we propose a controller that is able to make up for the initial uncertainty as these estimates converge during the learning process.

Following our pairwise definitions of amortized fairness from Section 5, we quantify by how much fairness between all classes is violated using the following overall disparity metric.

This metric can be instantiated with the disparity $D^{E}_{\tau}(G_{i},G_{j})$ from Equation (10) for exposure-based fairness, or $D^{I}_{\tau}(G_{i},G_{j})$ from Equation (12) for impact-based fairness. Since optimal fairness is achieved for $\overline{D}_{\tau}=0$, we seek to minimize $\overline{D}_{\tau}$.

To this end, we now derive a method we call FairCo, which takes the form of a Proportional Controller (a.k.a. P-Controller) (Bequette, 2003). A P-controller is a widely used control-loop mechanism that applies feedback through a correction term that is proportional to the error. In our application, the error corresponds to the violation of our amortized fairness disparity from Equations (10) and (12). Specifically, for any set of disjoint groups $\mathcal{G}=\{G_{1},\dots,G_{m}\}$, the error term of the controller for any item $d$ is defined as

The error term $\mathbf{err}_{\tau}(G)$ is zero for the group that already has the maximum exposure/impact w.r.t. its merit. For items in the other groups, the error term grows with increasing disparity.

Note that the disparity $\hat{D}_{\tau-1}(G_{i},G)$ in the error term uses the estimated ${\hat{Merit}}(G)$ from Equation (15), which converges to ${Merit}(G)$ as the sample size $\tau$ increases. To avoid division by zero, ${\hat{Merit}}(G)$ can be set to some minimum constant.

We are now in a position to state the FairCo ranking policy as

When the exposure-based disparity $\hat{D}^{E}_{\tau-1}(G_{i},G)$ is used in the error term, we refer to this policy as FairCo(Exp). If the impact-based disparity $\hat{D}^{I}_{\tau-1}(G_{i},G)$ is used, we refer to it as FairCo(Imp).

Like the policies in Section 4.3, FairCo is a sort-based policy. However, the sorting criterion is a combination of relevance $\hat{R}(d|\bm{x})$ and an error term representing the fairness violation. The idea behind FairCo is that the error term pushes the items from the underexposed groups upwards in the ranking. The parameter $\lambda$ can be chosen to be any positive constant. While any choice of $\lambda$ leads to asymptotic convergence as shown by the theorem below for exposure fairness, a suitable choice of $\lambda$ can have influence on the finite-sample behavior of FairCo: a higher $\lambda$ can lead to an oscillating behavior, while a smaller $\lambda$ makes the convergence smoother but slower. We explore the role of $\lambda$ in the experiments, but find that keeping it fixed at $\lambda=0.01$ works well across all of our experiments. Another key quality of FairCo is that it is agnostic to the choice of error metric, and we conjecture that it can easily be adapted to other types of fairness disparities. Furthermore, it is easy to implement and it is very efficient, making it well suited for practical applications.

To illustrate the theoretical properties of FairCo, we now analyze its convergence for the case of exposure-based fairness. To disentangle the convergence of the estimator for ${\hat{Merit}}(G)$ from the convergence of FairCo, consider a time point $\tau_{0}$ where ${\hat{Merit}}(G)$ is already close to ${Merit}(G)$ for all $G\in\mathcal{G}$. We can thus focus on the question whether FairCo can drive $\overline{D}^{E}_{\tau}$ to zero starting from any unfairness that may have persisted at time $\tau_{0}$. To make this problem well-posed, we need to assume that exposure is not available in overabundance, otherwise it may be unavoidable to give some groups more exposure than they deserve even if they are put at the bottom of the ranking. A sufficient condition for excluding this case is to only consider problems for which the following is true: for all pairs of groups $G_{i},G_{j}$, if $G_{i}$ is ranked entirely above $G_{j}$ at any time point $t$, then

Intuitively, the condition states that ranking $G_{i}$ ahead of $G_{j}$ reduces the disparity if $G_{i}$ has been underexposed in the past. We can now state the following theorem.

For any set of disjoint groups $\mathcal{G}=\{G_{1},\dots,G_{m}\}$ with any fixed target merits ${\hat{Merit}}(G_{i})>0$ that fulfill (18), any relevance model $\hat{R}(d|\bm{x})\in$, any exposure model $\operatorname{\mathbf{p}}_{t}(d)$ with $0\leq\operatorname{\mathbf{p}}_{t}(d)\leq\operatorname{\mathbf{p}}_{\max}$, and any value $\lambda>0$, running FairCo(Exp) from time $\tau_{0}$ will always ensure that the overall disparity $\overline{D}^{E}_{\tau}$ with respect to the target merits converges to zero at a rate of $\mathcal{O}\left(\frac{1}{\tau}\right)$, no matter how unfair the exposures $\frac{1}{\tau_{0}}\sum_{t=1}^{\tau_{0}}{Exp}_{t}(G_{j})$ up to $\tau_{0}$ have been.

The proof of the theorem is included in Appendix B. Note that this theorem holds for any time point $\tau_{0}$, even if the estimated merits change substantially up to $\tau_{0}$. So, once the estimated merits have converged to the true merits, FairCo(Exp) will ensure that the amortized disparity $\overline{D}^{E}_{\tau}$ converges to zero as well.

Empirical Evaluation

In addition to the theoretical justification of our approach, we also conducted an empirical evaluationThe implementation is available at https://github.com/MarcoMorik/Dynamic-Fairness.. We first present experiments on a semi-synthetic news dataset to investigate different aspects of the proposed methods under controlled conditions. After that we evaluate the methods on real-world movie preference data for external validity.

To be able to evaluate the methods in a variety of specifically designed test settings, we created the following simulation environment from articles in the Ad Fontes Media Bias datasethttps://www.adfontesmedia.com/interactive-media-bias-chart/. It simulates a dynamic ranking problem on a set of news articles belonging to two groups $G_{\text{left}}$ and $G_{\text{right}}$ (e.g. left-leaning and right-leaning news articles).

In each trial, we sample a set of 30 news articles ${\mathcal{D}}$. For each article, the dataset contains a polarity value $\rho^{d}$ that we rescale to the interval between -1 and 1, while the user polarities are simulated. Each user has a polarity that is drawn from a mixture of two normal distributions clipped to $$

where $p_{neg}$ is the probability of the user to be left-leaning (mean=$-0.5$). We use $p_{neg}=0.5$ unless specified. In addition, each user has an openness parameter $o^{u_{t}}\sim\mathcal{U}(0.05,0.55)$, indicating on the breadth of interest outside their polarity. Based on the polarities of the user $u_{t}$ and the item $d$, the true relevance is drawn from the Bernoulli distribution

As the model of user behavior, we use the Position-based click model (PBM (Chuklin et al., 2015)), where the marginal probability that user $u_{t}$ examines an article only depends only on its position. We choose an exposure drop-off analogous to the gain function in DCG as

The remainder of the simulation follows the dynamic ranking setup. At each time step $t$ a user $u_{t}$ arrives to the system, the algorithm presents an unpersonalized ranking $\bm{\sigma}_{t}$, and the user provides feedback $\operatorname{\mathbf{c}}_{t}$ according to $\operatorname{\mathbf{p}}_{t}$ and $\operatorname{\mathbf{r}}_{t}$. The algorithm only observes $\operatorname{\mathbf{c}}_{t}$ and not $\operatorname{\mathbf{r}}_{t}$.

To investigate group-fairness, we group the items according to their polarity, where items with a polarity $\rho^{d}\in[-1,0)$ belong to the left-leaning group $G_{\text{left}}$ and items with a polarity $\rho^{d}\in$ belong to the right-leaning group $G_{\text{right}}$.

We measure ranking quality by the average cumulative NDCG $\frac{1}{\tau}\sum_{t=1}^{\tau}U^{DCG}(\bm{\sigma}_{t}|\operatorname{\mathbf{r}}_{t})$ over all the users up to time $\tau$. We measure Exposure Unfairness via $\overline{D}^{E}_{\tau}$ and Impact Unfairness via $\overline{D}^{I}_{\tau}$ as defined in Equation (16).

In all news experiments, we learn a global ranking and compare the following methods.

Rank by the sum of the observed feedback $\operatorname{\mathbf{c}}_{t}$.

Dynamic LTR by sorting via the unbiased estimates ${\hat{R}^{\scalebox{0.6}{IPS}}}(d)$ from Eq. (15).

Fairness controller from Eq. (17) for impact fairness.

This is the key question in evaluating FairCo, and Figure 1 shows how NDCG and Unfairness converge for Naive, D-ULTR(Glob), and FairCo(Imp). The plots show that Naive achieves the lowest NDCG and that its unfairness remains high as the number of user interactions increases. D-ULTR(Glob) achieve the best NDCG, as predicted by the theory, but its unfairness is only marginally better than that of Naive. Only FairCo manages to substantially reduce unfairness, and this comes only at a small decrease in NDCG compared to D-ULTR(Glob).

The following questions will provide further insight into these results, evaluating the components of the FairCo and exploring its robustness.

1.2. Do the unbiased estimates converge to the true relevances?

The first component of FairCo we evaluate is the unbiased IPS estimator ${\hat{R}^{\scalebox{0.6}{IPS}}}(d)$ from Equation (15). Figure 1 shows the absolute difference between the estimated global relevance and true global relevance for ${\hat{R}^{\scalebox{0.6}{IPS}}}(d)$ and the estimator used in the Naive. While the error for Naive stagnates at around 0.25, the estimation error of ${\hat{R}^{\scalebox{0.6}{IPS}}}(d)$ approaches zero as the number of users increases. This verifies that IPS eliminates the effect of position bias and learns accurate estimates of the true expected relevance for each news article so that we can use them for the fairness and ranking criteria.

1.3. Does FairCo overcome the rich-get-richer dynamic?

The illustrating example in Section 2 argues that naively ranking items is highly sensitive to the initial conditions (e.g. which items get the first clicks), leading to a rich-get-richer dynamic. We now test whether FairCo overcomes this problem. In particular, we adversarially modify the user distribution so that the first $x$ users are right-leaning ($p_{neg}=0$), followed by $x$ left-leaning users ($p_{neg}=1$), before we continue with a balanced user distribution ($p_{neg}=0.5$). Figure 3 shows the unfairness after 3000 user interactions. As expected, Naive is the most sensitive to the head-start that the right-leaning articles are getting. D-ULTR(Glob) fares better and its unfairness remains constant (but high) independent of the initial user distribution since the unbiased estimator ${\hat{R}^{\scalebox{0.6}{IPS}}}(d)$ corrects for the presentation bias so that the estimates still converge to the true relevance. FairCo inherits this robustness to initial conditions since it uses the same ${\hat{R}^{\scalebox{0.6}{IPS}}}(d)$ estimator, and its active control for unfairness makes it the only method that achieves low unfairness across the whole range.

1.4. How effective is the FairCo compared to a more expensive Linear-Programming Baseline?

As a baseline, we adapt the linear programming method from (Singh and Joachims, 2018) to the dynamic LTR setting to minimize the amortized fairness disparities that we consider in this work. The method uses the current relevance and disparity estimates to solve a linear programming problem whose solution is a stochastic ranking policy that satisfies the fairness constraints in expectation at each $\tau$. The details of this method are described in Appendix A. Figure 4 shows NDCG and Impact Unfairness after 3000 users averaged over 15 trials for both LinProg and FairCo for different values of their hyperparameter $\lambda$. For $\lambda=0$, both methods reduce to D-ULTR(Glob) and we can see that their solutions are unfair. As $\lambda$ increases, both methods start enforcing fairness at the expense of NDCG. In these and other experiments, we found no evidence that the LinProg baseline is superior to FairCo. However, LinProg is substantially more expensive to compute, which makes FairCo preferable in practice.

1.5. Is FairCo effective for different group sizes?

In this experiment, we vary asymmetry of the polarity within the set of 30 news articles, ranging from $G_{\text{left}}=1$ to $G_{\text{left}}=15$ news articles. For each group size, we run 20 trials for 3000 users each. Figure 5 shows that regardless of the group ratio, FairCo reduces unfairness for the whole range while maintaining NDCG. This is in contrast to Naive and D-ULTR(Glob), which suffer from high unfairness.

1.6. Is FairCo effective for different user distributions?

Finally, to examine the robustness to varying user distributions, we control the polarity distribution of the users by varying $p_{neg}$ in Equation (19). We run 20 trials each on 3000 users. In Figure 6, observe that Naive and D-ULTR(Glob) suffer from high unfairness when there is a large imbalance between the minority and the majority group, while FairCo is able to control the unfairness in all settings.

2. Evaluation on Real-World Preference Data

To evaluate our method on a real-world preference data, we adopt the ML-20M dataset (Harper and Konstan, 2015). We select the five production companies with the most movies in the dataset — MGM, Warner Bros, Paramount, 20th Century Fox, Columbia. These production companies form the groups for which we aim to ensure fairness of exposure. To exclude movies with only a few ratings and have a diverse user population, from the set of $300$ most rated movies by these production companies, we select $100$ movies with the highest standard deviation in the rating across users. For the users, we select $10^{4}$ users who have rated the most number of the chosen movies. This leaves us with a partially filled ratings matrix with $10^{4}$ users and $100$ movies. To avoid missing data for the ease of evaluation, we use an off-the-shelf matrix factorization algorithmSurprise library (http://surpriselib.com/) for SVD with biased=False and D=50 to fill in the missing entries. We then normalize the ratings to $$by apply a Sigmoid function centered at rating$b=3$with slope$a=10$. These serve as relevance probabilities where higher star ratings correspond to a higher likelihood of positive feedback. Finally, for each trial we obtain a binary relevance matrix by drawing a Bernoulli sample for each user and movie pair with these probabilities. We use the user embeddings from the matrix factorization model as the user features$\bm{x}_{t}$.

In the following experiments we use FairCo to learn a sequence of ranking policies ${\pi}_{t}(\bm{x})$ that are personalized based on $\bm{x}$. The goal is to maximize NDCG while providing fairness of exposure to the production companies. User interactions are simulated analogously to the previous experiments. At each time step $t$, we sample a user $\bm{x}_{t}$ and the ranking algorithm presents a ranking of the 100 movies. The user follows the position-based model from Equation (20) and reveal $\operatorname{\mathbf{c}}_{t}$ accordingly.

For the conditional relevance model ${\hat{R}^{\scalebox{0.6}{Reg}}}(d|\bm{x})$ used by FairCo and D-ULTR, we use a one hidden-layer neural network that consists of $D=50$ input nodes fully connected to 64 nodes in the hidden layer with ReLU activation, which is connected to 100 output nodes with Sigmoid to output the predicted probability of relevance of each movie. Since training this network with less than 100 observations is unreliable, we use the global ranker D-ULTR(Glob) for the first 100 users. We then train the network at $\tau=100$ users, and then update the network after every 10 users on all previously collected feedback i.e. $\operatorname{\mathbf{c}}_{1},...,\operatorname{\mathbf{c}}_{\tau}$ using the unbiased regression objective, $\mathcal{L}^{\operatorname{\mathbf{c}}}(w)$, from Eq. (14) with the Adam optimizer (Kingma and Ba, 2014).

We first evaluate whether training a personalized model using the de-biased ${\hat{R}^{\scalebox{0.6}{Reg}}}(d|\bm{x})$ regression estimator improves ranking performance over a non-personalized model. Figure 7 shows that ranking by ${\hat{R}^{\scalebox{0.6}{Reg}}}(d|\bm{x})$ (i.e. D-ULTR) provides substantially higher NDCG than the unbiased global ranking D-ULTR(Glob) and the Naive ranking. To get an upper bound on the performance of the personalization models, we also train a Skyline model using the (in practice unobserved) true relevances $\operatorname{\mathbf{r}}_{t}$ with the least-squares objective from Eq. (13). Even though the unbiased regression estimator ${\hat{R}^{\scalebox{0.6}{Reg}}}(d|\bm{x})$ only has access to the partial feedback $\operatorname{\mathbf{c}}_{t}$, it tracks the performance of Skyline. As predicted by the theory, they appear to converge asymptotically.

2.2. Can FairCo reduce unfairness?

Figure 8 shows that FairCo(Exp) can effectively control Exposure Unfairness, unlike the other methods that do not actively consider fairness. Similarly, Figure 9 shows that FairCo(Imp) is effective at controlling Impact Unfairness. As expected, the improvement in fairness comes at a reduction in NDCG, but this reduction is small.

2.3. How different are exposure and impact fairness?

Figure 10 evaluates how an algorithm that optimizes Exposure Fairness performs in terms of Impact Fairness and vice versa. The plots show that the two criteria achieve different goals and that they are substantially different. In fact, optimizing for fairness in impact can even increase the unfairness in exposure, illustrating that the choice of criterion needs to be grounded in the requirements of the application.

Conclusions

We identify how biased feedback and uncontrolled exposure allocation can lead to unfairness and undesirable behavior in dynamic LTR. To address this problem, we propose FairCo, which is able to adaptively enforce amortized merit-based fairness constraints even though their underlying relevances are still being learned. The algorithm is robust to presentation bias and thus does not exhibit rich-get-richer dynamics. Finally, FairCo is easy to implement and computationally efficient, which makes it well suited for practical applications.

References

Appendix A Linear Programming Baseline

Here, we present a version of the fairness constraint defined in Singh and Joachims (2018) that explicitly computes an optimal ranking to present in each time step $\tau$ by solving a linear program (LP). In particular, we formulate an LP that explicitly maximizes the estimated DCG of the ranking $\bm{\sigma}_{\tau}$ while minimizing the estimated cumulative fairness disparity $D^{I}_{\tau}$ formulated in Equation (11). This is used as a baseline to compare the P-Controller with.

The parameter $\lambda$ controls trade-off between DCG of $\bm{\sigma}_{t}$ and fairness. We explore this parameter empirically in Section 8.1.

Note that the number of variables in the LP is $O(n^{2}+|\mathcal{G}|^{2})$, and even a polynomial-time LP solver incurs substantial computation cost when working with a large number of items in a practical dynamic ranking application.

Appendix B Convergence of FairCo-Controller

In this section we will prove the convergence theorem of FairCo for exposure fairness. We conjecture that analogous proofs apply to other fairness criteria as well. To prove the main theorem, we will first set up the following lemmas.

Under the conditions of the main theorem, for any value of $\lambda$ and any $\tau>\tau_{0}$: if $D^{E}_{\tau-1}(G_{i},G_{j})>\frac{1}{(\tau-1)\lambda}$, then

From the definition of $D^{E}_{\tau}$ in Eq. (10) we know that for $\tau>\tau_{0}$,

Since $D^{E}_{\tau-1}(G_{i},G_{j})>\frac{1}{(\tau-1)\lambda}$, we know that for all items in $G_{j}$ it holds that $\mathbf{err}_{\tau}(d)>\frac{1}{\lambda}$. Hence, FairCo adds a correction term $\lambda\mathbf{err}_{\tau}(d)$ to the $\hat{R}(d)$ of all $d\in G_{j}$ that is greater than $\lambda\frac{1}{\lambda}=1$. Since $0\leq\hat{R}(d)\leq 1$, the ranking is dominated by the correction term $\lambda\mathbf{err}_{\tau}(d)$. This means that all $d\in G_{j}$ are ranked above all $d\in G_{i}$. Under the feasibility condition from Eq.(18), this implies that $\left(\frac{{Exp}_{\tau}(G_{i})}{{\hat{Merit}}(G_{i})}\leq\frac{{Exp}_{\tau}(G_{j})}{{\hat{Merit}}(G_{j})}\right)$ and thus $\tau D^{E}_{\tau}(G_{i},G_{j})\leq(\tau-1)D^{E}_{\tau-1}(G_{i},G_{j})$.∎

Under the conditions of the main theorem, for any value of $\lambda>0$ there exists $\Delta\geq 0$ such that for any $G_{i},G_{j}$ and $\tau>\tau_{0}$: if $D^{E}_{\tau-1}(G_{i},G_{j})\leq\frac{1}{(\tau-1)\lambda}$, then $\tau D^{E}_{\tau}(G_{i},G_{j})\leq\frac{1}{\lambda}+\Delta$.

Using the definition the definition of $D^{E}_{\tau}$ in Eq. (10), we know that

where $\Delta=\max_{\sigma}\max_{\begin{subarray}{c}G,G^{\prime}\\ G\neq G^{\prime}\end{subarray}}\left(\frac{{Exp}_{\sigma}(G)}{{\hat{Merit}}(G)}-\frac{{Exp}_{\sigma}(G^{\prime})}{{\hat{Merit}}(G^{\prime})}\right)$. Note that $\Delta$ is a constant independent of $\tau$ and refers to the ranking $\sigma$ for which two groups $G,G^{\prime}$ have the maximum exposure difference (e.g. one is placed at the top of the ranking, and the other is placed at the bottom). ∎

Using these two lemmas, we conclude the following theorem:

For any set of disjoint groups $\mathcal{G}=\{G_{1},\dots,G_{m}\}$ with any fixed target merits ${\hat{Merit}}(G_{i})>0$ that fulfill (18), any relevance model $\hat{R}(d|\bm{x})\in$, any exposure model $\operatorname{\mathbf{p}}_{t}(d)$ with $0\leq\operatorname{\mathbf{p}}_{t}(d)\leq\operatorname{\mathbf{p}}_{\max}$, and any value $\lambda>0$, running FairCo(Exp) from time $\tau_{0}$ will always ensure that the overall disparity $\overline{D}^{E}_{\tau}$ with respect to the target merits converges to zero at a rate of $\mathcal{O}\left(\frac{1}{\tau}\right)$, no matter how unfair the exposures $\frac{1}{\tau_{0}}\sum_{t=1}^{\tau_{0}}{Exp}_{t}(G_{j})$ up to $\tau_{0}$ have been.

To prove that $\overline{D}^{E}_{\tau}$ converges to zero at a rate of $\mathcal{O}\left(\frac{1}{\tau}\right)$, we will show that for all $\tau\geq\tau_{0}$, the following holds:

The two terms in the max provide an upper bound on the disparity at time $\tau$ for any $G_{i}$ and $G_{j}$. To show this, we prove by induction that $\tau D^{E}_{\tau}(G_{i},G_{j})\leq\max\left(\tau_{0}\left|D^{E}_{\tau_{0}}(G_{i},G_{j})\right|,\frac{1}{\lambda}+\Delta\right)$ for all $\tau\geq\tau_{0}$. At the start of the induction at $\tau=\tau_{0}$, the max directly upper bounds $\tau_{0}D^{E}_{\tau_{0}}(G_{i},G_{j})$. In the induction step from $\tau-1$ to $\tau$, if $(\tau-1)D^{E}_{\tau-1}(G_{i},G_{j})>\frac{1}{\lambda}$, then Lemma B.1 implies that $\tau D^{E}_{\tau}(G_{i},G_{j})\leq(\tau-1)D^{E}_{\tau-1}(G_{i},G_{j})\leq\max\left(\tau_{0}\left|D^{E}_{\tau_{0}}(G_{i},G_{j})\right|,\frac{1}{\lambda}+\Delta\right)$. If $(\tau-1)D^{E}_{\tau-1}(G_{i},G_{j})\leq\frac{1}{\lambda}$, then Lemma B.2 implies that $\tau D^{E}_{\tau}(G_{i},G_{j})\leq\frac{1}{\lambda}+\Delta\leq\max\left(\tau_{0}\left|D^{E}_{\tau_{0}}(G_{i},G_{j})\right|,\frac{1}{\lambda}+\Delta\right)$ as well. This completes the induction, and we conclude that