Introduction of the paper

Today, I’m going to share points and conceptions I got from a fantastic paper “Fairness of Exposure in Rankings¹” written by Ashudeep Singh and Thorsten Joachims.

In this paper, the authors mainly introduce the fairness constraints based on exposure in rankings. They proposed three forms of fairness constraints, namely demographic parity, disparate treatment and disparate impact constraints to balance fairness to the items being ranked with the utility.

Demographic parity²

Demographic parity states that protected groups (based on sensitive attributes, e.g. sex, gender, etc.) should have equal opportunities to be shown or recommended. For example, male and female job seekers should have equal opportunities to expose in a job seeker website. It’s reasonable to distribute exposure more evenly, even if sacrificing the utility in rankings.

Disparate treatment²

Disparate treatment is a term refers to a kind of intentional discrimination. For example, only testing the particular skills of female applicants in a job seeker website.

Disparate impact

Unlike disparate treatment, disparate impact is referred to unintentional discrimination, for example, female job seekers with a lower proportion of all job seekers would be exposed less unintentionally.

The framework for fair ranking

As the authors of this paper proposed, the definition of fairness depends on context and application, which means that different fairness constraints should be applied on different scenarios. They developed a general framework for computing utility-maximizing ranking under different fairness constraints. Generally, the problem of optimal ranking under fairness constraints can be formulated as the following optimization problem:

, where $U(r|q)$ denotes the utility of a ranking $r$ for query $q$, the ranking $r$ presents the order of a set of documents $\mathcal{D} = \{d_1, d_2, d_3\dots, d_N\}$.

Untility

The utility measures of a ranking system evaluates the utility of the ranking from the relevance of the individual items being ranked. $rel(d|u, q)$ denotes the relevance score of the document $d$ when a user $u$ search a query $q$, the relevance could be binary relevance, movie ratings or a real-valued score. In information retrieval systems, the generic way to express utility measures is:

where $\mathcal{U}$ is the set of all users that lead to identical $q$, $v$ reflects the importance of ranking position and $\lambda$ is a function mapping the relevance to its utility. Take Discounted Cumulative Gain (DCG) as an example:

where $2^{rel(d|u,q)} - 1 = \lambda(rel(d|u,q))$ and $\frac{1}{log(1 + rank(d|r))} = v(rank(d|r))$.

Due to the linear relationship between utility and both $v$ and $\lambda$, the above equation can be reformulated as:

, where

is the expected utility of a document $d$ for query $q$. $u(d|q)$ can be understood as the probability of relevance if $rel(d|u,q)$ are binary relevances. Therefore, sorting the documents by $u(d|q)$ is the effective way to maximize the utility for ranking:

Based on this equation, we can take an example to explain it:

We can easily get the best-ranking order by sorting the $v(rank(d\vert r))u(d\vert q)$, the ranking order with maximum utility should be $\{d_1, d_3, d_4, d_0, d_2, d_5\}$.

Probabilistic Rankings

In this paper, the authors applied probabilistic rankings $R$ instead of a single deterministic ranking $r$ to avoid combinatorial optimization:

, to avoid the exponential computation, the authors compute the utility by the marginal rank distributions³ of the documents.

Specifically, let $P_{i, j}$ be the probability that $R$ places document $d_i$ at rank $j$, then creating a doubly stochastic matrix⁴ of size $N \times N$ using $P$. The matrix meets:

. Therefore, the expected utility for a probabilistic ranking can be computed as:

where $u(d_i|q)$ for each user should be a column vector with size of $N$, and $v$ is also a column vector of size $N$. Thus, the expected utility can be rewritten as:

Optimizing Fair Rankings via Linear Programming

To efficiently compute $R$ for every doubly stochastic matrix $P$, they formulated the problem of finding the utility-maximizing probabilistic ranking under fairness constraints in terms of doubly stochastic matrices instead of distributions over rankings:

The optimization objective is linear in $N^2$ variables $P_{i,j}$ ($1 <= i,j <= N$). And the fairness constraints are linear as well. The solution without fairness constrains and for any $v_j$ that decreases with $j$ is the permutation matrix⁵ that ranks the set of documents in decreasing order of utility. Therefore, the problem of finding the utility-maximizing probabilistic ranking and the fairness constraints can be linearly formulated as:

Sampling Rankings

The authors employed the Birkhoff-von Neumann(BvN) decomposition⁶ to compute $R$ from $P$. Specifically, if $A$ is a doubly stochastic matrix, the decomposition of the form is:

where $0 <= \theta_i <= 1$, and $A_i$ are permutation matrices. $A_i$ corresponses to deterministic rankings of the document set and $\theta_i$ corresponds to the probability of sampling each ranking.

The decomposition can be computed efficiently in polynomial time, according to Marcus-Ree theorem⁶, there are no more than $(N-1)^2 + 1$ permutation matrices.

Summary of Algorithm

1. Set up the utility vector $u$ and position discount vector $v$, as well as the vectors $f$ and $g$, and $h$.

2. Solve the linear program for $P$.

3. Compute the Birkhoff-von Neumann decomposition $P = \theta_1P_1 + \theta_2P_2 + ... + \theta_nP_n$.

4. Sample permutation matrix $P_i$ with probability proportional to $\theta_i$ and get the corresponding ranking $r_i$.

While setting up the vectors in the first step, $u(d|q)$ is assumed as true relevances and $\hat{u}(d|q)$ is from some predictive models.

Fairness Constraints

First, to clearly express the fairness, the authors define the exposure for a document $d_i$ under a probabilistic ranking $P$ as:

The goal is to ensure different groups $G_k$ have the same opportunities of exposure.

Data sets

They employed two data sets, one is the fake synthetic data set which contains 6 job seekers with probabilities of relevance to an employer of $u = (0.81, 0.80, 0.79, 0.78, 0.77, 0.76)^T$ and the other is News recommendation dataset with ratings divided by 5 and added a Gaussian noise of 0.05 (finally clipped to 0 ~ 1).

Demographic Parity Constraints

This constraint enforces the average exposure of the documents in both groups is equal, the average exposure in a group is denoted as:

this constraint can be easily expressed as:

Experiments

For the data set of Job-seeker, after solving the linear program without fairness constrains, the below figure shows the optimal rankings in terms of $P$.

The optimal rankings in terms of $P$ with Demographic Parity constraint is shown as the below figure:

This fair ranking can be decomposed into a mixture of two deterministic permutation matrices with the associated weights:

The results are shown by the below figure for the data set News recommendation dataset:

Disparate Treatment Constraints

This constraint ensure the exposure be proportional to relevance, to end this, the average utility of a group can be denoted as:

the exposure of two groups to be proportional to their average utility:

To compute how differently the two groups are treated, they defined a measure called Disparate Treatment Ratio (DTR):

The results are not going to show here, please find details from the paper¹.

Disparate Impact Constraints

For this constraint, they first define the probability of a document getting clicked:

Then, compute the average clickthrough rate of documents in a group G_k as:

The Disparate Impact Constraint enforces the expected clickthrough rate of each group is proportional to its average utility:

Similarly, to measure the extent to which the disparate impact constraint is violated, DIR (Disparate Impact Ratio) is defined as:

Conclusion

In this paper, the authors developed a generic probabilistic ranking framework for applying different fairness constraints. The defined three constraints are very clear and clever, which reflects the authors’ solid mathematical skills.

In this blog article, all main points and logics are summarised, I recommended to read the original paper for the specific details. You are also welcome to discuss here. : D

References