Fairness of Exposure in Ranking

Two job candidates are scored 0.51 and 0.49 by a ranker. Under the standard position discount, the one at rank 1 receives exposure 1.000 and the one at rank 2 receives \(1/\log_2 3 = 0.631\). A two-point difference in estimated relevance has become a 37 percent difference in attention, and if the same query runs a thousand times the gap compounds a thousand times. Nothing in the model caused this. Winner-take-all is a property of how results are presented, and classification fairness criteria have nothing to say about it because there is no per-item decision to equalise.

Exposure is the resource being allocated

Under a position-based examination model, the exposure of rank \(j\) is a constant \(v_j\) independent of what sits there, conventionally the DCG discount:

Total exposure in the top 5 is 2.949, and rank 1 takes a third of it. Once exposure is written as a quantity, fairness can be stated as a constraint on its allocation: equal exposure per group, exposure in proportion to relevance, or clicks in proportion to relevance. These are different constraints with different consequences, and the vocabulary matters because "fair ranking" with no constraint named is not a specification.

Constrained optimisation over distributions of rankings

A single deterministic ranking cannot usually satisfy an exposure constraint, because exposure comes in the quantised lumps \(v_j\). The standard construction therefore optimises over a doubly stochastic marginal rank probability matrix \(P\), where \(P_{ij}\) is the probability that item \(i\) is shown at rank \(j\). Expected user utility is linear in \(P\), and so are group exposure constraints, so the whole thing is a linear program. A Birkhoff–von Neumann decomposition then writes the optimal \(P\) as a convex combination of permutation matrices, and sampling one permutation per impression with the matching probabilities realises the constrained exposure in expectation (Singh and Joachims, 2018, Fairness of Exposure in Rankings, KDD, arXiv:1802.07281).

That construction buys something subtle: the system is now allowed to be stochastic, which is the only way to give two near-tied items near-equal attention without lying about their relevance.

Amortising across queries, and measuring it

Individual-level exposure fairness is unachievable within one ranking whenever relevance genuinely differs. The alternative is to let it hold over a sequence: accumulated attention proportional to accumulated relevance, enforced as an online optimisation with a per-ranking quality constraint, which becomes an integer program solved impression by impression (Biega, Gummadi and Weikum, 2018, Equity of Attention: Amortizing Individual Fairness in Rankings, SIGIR, arXiv:1805.01788).

Evaluation needs the matching change. If the system produces a distribution over rankings, a metric computed on one ranking is measuring a sample. The expected-exposure framework scores the distribution instead, against the principle that items of equal relevance grade should receive equal expected exposure, and decomposes the resulting error into a part attributable to under-exposing relevant items and a part attributable to over-exposing non-relevant ones (Diaz et al., 2020, Evaluating Stochastic Rankings with Expected Exposure, CIKM, arXiv:2004.13157).

In a marketplace the constraint has a second beneficiary. Suppliers care about exposure, users care about relevance, and the platform trades them off whether or not it admits to doing so; counterfactual evaluation on music streaming logs shows the trade-off curve is measurable rather than a matter of taste (Mehrotra et al., 2018, Towards a Fair Marketplace, CIKM).

When it breaks

The exposure model is an assumption, and a wrong one is a wrong allocation. \(1/\log_2(1+j)\) is a convention, not a measurement. Real examination curves depend on surface, device, result-block layout and query intent, and if your estimated \(v_j\) is flatter than reality the constraint under-corrects (see position bias and the examination hypothesis).

Relevance estimates are downstream of past exposure. Making exposure proportional to estimated relevance reproduces whatever the logs already believed, because items that were never shown have no clicks and therefore low estimated relevance. Exposure fairness and unbiased evaluation have to be solved together (see counterfactual learning to rank).

Stochastic ranking has engineering costs that rarely appear in the papers. Caching gets harder, A/B results get noisier for a fixed sample, two users with the same query see different pages and support cannot reproduce a complaint, and the variance lands on exactly the near-tied items whose ordering users notice.

Amortisation needs identity and patience. It assumes items persist across queries and that nobody minds being under-exposed now in exchange for later. Both fail for perishable inventory, and both fail for a candidate who was rejected in March.

Group constraints need group labels for items. Protected attributes of the ranked entities are often unavailable or inferred, and inferring them to enforce fairness carries the same error-direction problems as inferring them to measure it (see measuring fairness without the attribute).