An open-source and greedy approach to individually fair re-ranking is presented, evaluated and tested. Previous literature on individually fair search suggested greedy-style heuristics, but no such designs or implementations were introduced before this writing. We release our re-ranker as a zero-dependency utility compatible with all major operating systems. We publish our re-ranker under a permissive software license (GPLv3). By explicitly considering individual fairness a post-processing (re-ranking) task, we implement the notion of individual fairness as a microservice, de-coupled from specific IR systems. Our software package works on commodity hardware, and finds application in small-to-medium-sized businesses, federated social networks, and under the broader open web search initiative.
impact on fairness outcomes. We demonstrate this through the lens of individual fairness, leaving group fairness for future work or additional re-ranking steps placed beforehand or afterwards within a ranking pipeline.
A major issue facing fairness-aware search adoption on the open web relates to compatibility and required expertise. With the exception of FairSearch [6], most fairness solutions are published in the form of Python experiments, without implementations that work across varied computer systems. Additionally, researching greedy fairness methods has been proposed as future work [2, p. 409], but as of this writing, the greedy strand of fair ranking research has received little explicit attention, despite eficient (greedy) solutions being vital for widespread feasibility of fair search.
Dublin + restaurant
Though some computationally eficient fairness techniques have been provided [ 7, 8], most others rely on intense optimisation strategies, necessitating a GPU at the minimum. This creates a high barrier to entry, thus excluding the open web as a consideration. There are also ecological downsides to this approach. In the case of Biega et al.’s technique [2, p. 411], integer linear programming (ILP) was used via a proprietary cloud-based system1. Singh and Joachims [9] concurrently suggested an approach equivalent to amortized fairness; their method uses Birkhofvon-Neumann decomposition (BvN decomp.), and they applied it to groups as opposed to individuals, noting their method could apply to individuals by reducing groups to size one. Again, BvN is a computationally expensive procedure. To our knowledge, Morik et al. [7] were the first to publish work addressing bias in what is known as a greedy solution. Definition 1. Greedy algorithm. “An algorithm that always takes the best immediate, or local, solution while finding an answer.” [ 10] Greedy algorithms can eficiently produce approximate solutions to NP-complete problems, including NP-complete fair ranking problems (Section 3). Though Morik et al. don’t directly mention greedy algorithms, their proposed method is undoubtedly greedy (Definition 1), particularly given that it is observed to produce oscillating behaviour when a certain parameter is not tuned correctly [7, p. 434]. Though this oscillation decreases with -tuning, results remain approximate, not optimal. The authors apply their P-controller method [7, 11] to group fairness, and don’t include quality threshold in their scope (e.g. Biega et al.’s threshold [2,
Comparing some existing fairness techniques in IR: computational costs, quality thresholds, and implementa
DELTR [12] ILP [2] LP (BvN decomp.) [9] Low Low
7 7 7 3 7 p. 409]). We later present a similarly greedy method that accounts for quality threshold, , while retaining low computational cost. Like the method of Morik et al., ours is not optimal. We define optimality in terms of the ILP solution [ 2], which is optimal by definition, given that the ILP solver finds the permutation of valid rankings that minimises the diference between attention [ ] and relevance [ ] (scaled by
per ranking count) (
Some previous fairness work has reached production-ready implementation, notably the work of Zehlike and her colleagues [8, 12, 13], who provide Python/Java libraries, and Elasticsearch plugins for both an in-processing technique (DELTR [12]) and a post-processing technique (FA*IR[8]). We categorise the DELTR approach as low-medium cost, given its reliance on an LTR method (in-processing fairness). Organisations may already have complex LTR pipelines, and integrating this approach might be similarly complex, involving specialised expertise. For companies without an LTR pipeline, relying on traditional no-data IR metrics alone (e.g. BM25), this approach would not apply.
The FA*IR approach [8], a post-processing technique, assures ranking prefixes carry predefined proportions across protected groups. The implementation [ 6] is eficient and requires little additional expertise for deployment. However, it has seen limited adoption in industry (7 ‘GitHub stars’ from industry practitioners, 13 in total as of January 2024). This could be due to a lack of group labels available to businesses (FA*IR is designed as a group-fair method), or perhaps the absence of a quality threshold on rankings produced by FA*IR. We summarise our analysis of these prior works in Table 1.
We now propose an individual fairness method that is low-cost and incorporates a quality threshold; we later introduce a reference C++ implementation (Section 3.2). Our approach is inspired by the combination of characteristics reviewed in Table 1, with an aim to introduce a fair re-ranking approach that can be immediately deployed in many varied computing environments, focusing mainly on open web search and scenarios of group membership ambiguity.
Central to the field of information retrieval is quality. Al-Maskari et al. [ 14] state, “User satisfaction is a subjective variable and is influenced by several factors (e.g. system efectiveness, user efectiveness, user efort, and user characteristics).” Two popular metrics for ensuring quality or system efectiveness
are expected reciprocal rank [ERR] (
= ∑ log2( + 1) =1 2
rel()− 1 = ∑
−1
=1 =1
∏[1 −rel()]
(
denotes the relevance of the document at position in a ranking [or re-ranking ]̃. NDCG is most often used as a quality metric during the development of relevance estimation strategies (including LTR). However, within fair re-ranking the formula is instead used in order to retain a certain level of quality; i.e. we define NDCG based on relevance probabilities as revealed to the fair re-ranker from an earlier point in the ranking pipeline. In fair re-ranking, these relevance scores do not arise directly from annotated data, and are generally the output from a ranking function itself. This new usage of the formula prompted Biega et al. to use difering notation for NDCG: NDCG-quality @(, )̃ = is a ranking without any amortized fairness applied, and ̃ is a ranking with amortized fairness applied. For simplicity, we instead refer to this as NDCG in the remainder of this paper.
Our method begins with quality control.
Therein we bypass the more dificult question: “Subject to
≥ , what is the best re-ranking ( )̃ to distribute attention ?” . Instead, we ask a series of easier questions: “What is the fairest result to return first, subject to ?” Then, “What is fairest to return next?” etc. This is a greedy approach (Definition 1). ≥
Before we go further, we must introduce what is meant by exposure, alternately referred to as attention by some authors. These are intuitive terms, especially to those familiar with search engine optimisation. The terms have numeric definitions in fair ranking research. The simplest practical model defines attention as the
marginal probability of examination [7] in reference to earlier position-based models [17] which found that rank alone can predict exposure with high enough levels of accuracy for practical purposes [7, 18, 19]. In this sense attention would be defined similarly to one of the summand denominators in DCG: = ( + 1) −1 [9]. Another model for attention is geometric [2], i.e. a special case of the cascade model using equal click probability for each item: = (1 − )−1 . We suggest a possible amendment to this model: removing the final multiplicand, given that attention maps to examination of items (not clicks), whereas the
multiplicand in the cascade model specifically models a click. In addition to the geometric model, the more general cascade model can be used to predict attention per-item in a ranking. This would difer from geometric in that each item receives varying click probability. The choice of attention model is important, though not the central scope of this work. We assume a geometric model with = 0.4 in our experiments (Section 4). Returning to the greedy approach, our task is as follows: a) choose an item at each rank which adds the most individual fairness, b) Ensure chosen items are good enough to prevent the overall ranking from dipping below the quality threshold ( ). For the purposes of their ILP-based approach, Biega et al. use unfairness(1, … , ) = =1 | − ⋅ ∑
| = ∑
=1 ∣∑=1 − ⋅
∣
.
the following definition:
is the attention obtained by document in ranking , and
is the relevance of the document
to the outer information need. We use an equivalent minimisation target (
unfairness(1, … , ) = max ∈ [1,]
[rel()
Proof of equivalence. When Biega et al.’s unfairness is minimised: − ⋅ = 0, ∀ . Put
diferently: rel ()= , ∀ . Therefore, unfairness(1, … , )would be minimised too (
It is useful to label r el(∗ ∗)itself as the relative compensation received by document (relative to
merit or utility). In this sense, we define unfairness as a large gap between the highest relative
compensation and the lowest.
3.1. Deriving minimal relevance (a-posteriori) at each rank via an optimistic strategy.
We use an optimistically greedy strategy, meaning we select the next result which minimises
unfairness (
A. z a d t o h p k b v u q i x s j c f g e ? z a d t o h p k b B. z a d t o h p k b v u q i x s j c f g e e p i d ? z a t o h
C. z a d t o h p k b v u q i x s j c f g e e p i d s z x g ? a DEM selection is illustrated in three stages during the preparation of a single re-ranking (Figure 2). The left side of the diagram depicts canonical relevancies of items, as passed into the reranking system from an earlier ranking process. The red line represents the first page cutof point ( = 10 ). The right side is the ongoing re-ranking of these items, with the sole coloured bar representing the current rank whose item is being decided. While choosing the first item (part A), the missing part of the ranking (dashed blocks) is assumed to be a prefix of the canonically ordered results, ⟨z, a, d, t, o, h, p, b⟩. Part B occurs after the prior selection of four items using DEM strategy. Notably, one of the items previously selected (d) was in the canonical prefix. We illustrate this by coloring its bar grey, meaning it can no longer be used during optimistic predictions about the remaining results. This is further illustrated in the dashed blocks (far right of part B), where the optimistic prefix excludes d: ⟨z, a, t, o, h⟩. This selection process continues (part C), and ultimately a re-ranking is produced within a given quality threshold. It might not end up that a re-ranking sufix (right) resembles a canonical prefix (left), but our overall strategy ensures we always remain within the quality threshold at each item choice. We now validate this strategy by considering the quality threshold as introduced earlier (NDCG ≥ ). This can be rewritten as follows.
DCG ()̃ ≥ ⋅ DCG ()
(
rel(i)− 1 item under the present rank ( ) is picked accordingly.
We represent this mathematically by
substituting an ideal sufix into the above (
2rel(i)− 1 (∑ log ⏟ ⏟=⏟1⏟⏟⏟2(⏟ ⏟+⏟1) past ) + (log
2rel(j)− 1 ⏟⏟⏟⏟2(⏟ ⏟+⏟1) present )+ ( ∑
log ⏟⏟=+⏟1⏟⏟ ⏟2(⏟⏟+⏟1) future (ideal) 2R:el()− 1 ) ≥ ∑ log ⏟=1⏟⏟⏟⏟2(⏟ ⏟+ 1) ultimate ideal The above can be re-organised to find a minimum relevance required at the present rank . Below this relevance [() ], meeting the quality threshold would be impossible. rel() ≥log2 (1 + [ ≥ min_relDCG =1 ∑ log R:el()excludes these bars while counting .
In the above equations, a distinction is made between canonical relevance [Rel(),]and canonical relevance with the previously chosen − 1 items removed [R:el().]This relates to the grey bars in Figure 2; Rel()counts from the beginning, including these grey bars. On the other hand, computer operations during the scan.
Our proposed method for greedy individual fairness involves sorting results by relative compensation.
We then scan over this list (lowest relative compensation to
highest), stopping at the first result with high enough relevance
[rel ≥ min_relDCG](
Though was first used with DCG [ 2],
it can also be used with any ranking quality metric, including ERR [introduced earlier (
∏ [1 −Rel()] =1
−1 =1 ≥ ⋅ IERR
…we use IERR (ideal ERR) as shorthand.
Expressing rel()in terms of everything else (in the case of ERR), assuming a DEM strategy (Figure 2), is more complicated than with DCG, the latter being a much more stateless metric. For ERR, we have: (∑ −1 rel()−1 ∏ [1 −rel()])+ (
∏ [1 −rel()])+ F⏟uture ≥ ⋅ ⏟ ⏟=1⏟⏟⏟⏟=⏟1 ⏟⏟⏟⏟⏟⏟ ⏟⏟⏟⏟⏟=1⏟⏟⏟⏟⏟⏟
" (ideal) past
present rel()
−1
I⏟ERR ultimate ideal with…
Future =
( ∏ [1 −rel()]) [1 −rel()]∏ [1 −R:el( − )]] The above can be rewritten in the following intermediate form:
∑ (13) (15) denote this cutof relevance as for DCG and then for ERR.
min_rel_prioriDCG returned to the user.
Though the above formula involves a lot of summed products, previous work has provided optimised O()techniques for calculating these parts [15]. Furthermore, in our web search use-case will generally be quite low (≪ 75), and min_rel∗ need only be calculated once per item
Above, we presented means of reducing computer operations
during the linear scan of items ordered by relative compensation [r el(∗ ∗)]. Another optimisation
for reducing the cost of this linear scan is to pre-calculate a-priori minimum relevance (given
quality threshold ) at each rank . Consider a scenario where almost all items in the re-ranking
̃ are ideal (relative to ), just not the item at rank . The minimum relevance necessary at
in order to make (14) or (15) hold true is thus defined by substituting Rel(⋅ )for all instances of
R:el(⋅)and rel(⋅ ≠ )in (
∑ log min_rel_prioriERR ⋅ IERR −∑=−11 Rel() =1 [1−Rel()] −1 ∏ ∏ =−11 [1−Rel()] ∑ log The completed rewrite, focusing on expressing rel()in terms of everything else, follows. rel() ≥ ≥ min_relERR
⋅ IERR −∑=1 −1 rel() =1 [1−rel()] −1 ∏ ∏ =−11 [1−rel()]
1 − ∑ streams into the re-ranking system ordered by relevance to the information need. (A) Serve top items as the first ranking, 1̃ = , updating ∗ accordingly. (B) Copy ( − 1)top items from into (left of red line, Figure 2).
(C) Calculate min_rel_priori∗ using and (14 & 15), ∀ ∈ [1, ] (D) Remove items from where rel() <min_rel_priori∗ (14 & 15).
(E) Create candidate lists per-rank, ∈ [1, ], st. list item relevances ≥
_
_
∗.
(F) Sort candidate lists by by relative compensation [rel(∗)
∗ ], low → high.
(G) Initiate a new re-ranking, ∗̃.
(H) For between 1 and :
(H)(
One caveat excluded from the overview (for brevity) is that sometimes the item selected at a given rank (coloured bars, right hand side, Figure 2) will be part of the optimistic tail (dashed blocks, Figure 2). In many cases, this will not be an issue, given that the a-posteriori past + present + future quality score (9 & 13) is likely to remain within threshold. However, this does constitute double-counting, and there will be some edge-cases where this becomes an issue. See Figure 3.
z o b v u q ? z o b b z o b
DCG( b z o b ) double count in a ranking that meets the quality threshold of ⋅ tail (dashed blocks) causes it to be double counted. 4 . The presence of b in the optimistic
Rather than addressing this issue before it arises, we instead prioritise linear scan speed, and initially let the error happen, only checking after a candidate item is found whether or not it is part of the optimistic tail (dashed boxes in Figure 2), and furthermore, whether the corrected quality of the ranking falls below the threshold.
To address this edge-case, we insert the below steps in the algorithm outline, displacing the
original Steps (H)(
Choose and subsequently mask ′′ instead of .
(H)(
Continue backwards (to very beginning of ), finding ′′ with lowest r el(∗ ∗).
(H)(
We further illustrate the edge-case double count problem via Figure 4, where a document x is chosen, but this document happens to be the optimistic tail (dashed blocks). Given the left scenario in Figure 4 meets quality standards, but the middle (accounting for the double count correctly) does not, we wish to know if this indicates that the right side scenario will also not meet quality standards. In the right hand side, rather than selecting x, another document beyond the end of the optimistic tail is chosen. the re-occurrence of x in the optimistic tail occurs at ofset into that tail.
All items after x in the canonical ordering are assumed to have equal relevance, < rel( ), and (with double x; θ respected) (without double x; θ broken)
(choosing from RHS of x: is θ broken?) A x H x
T
A x H
T →
A T H x T The diagram illustrates the formulae below. (16) corresponds to the middle portion of Figure 4, and (17) corresponds to the right portion. We use a symbol in (17) representing the unknown operator, ⟦⊕⟧ ∈ {⟦<⟧, ⟦≥⟧}. We seek to prove that ⟦⊕⟧ = ⟦<⟧.
A
A … with = ⋅ x (middle)
−1 2()
− 1 ⏟=1⏟⏟⏟⏟2(⏟ ⏟+ 1)+ log ∑ log 2( )− 1 ⏟⏟2⏟(⏟ ⏟+1) + −1 ∑
log ⏟=⏟1⏟⏟⏟2(⏟ ⏟+⏟+⏟1)
H (middle)
log ⏟=+⏟1 ⏟⏟⏟2⏟( + )
⏟
T (middle) 2 :()− 1 + − ∑ 2 − 1 < −1 2()
− 1 ⏟=1⏟⏟⏟⏟2(⏟ ⏟+ 1)+ log ∑ log
2 − 1 ⏟⏟2⏟(⏟ ⏟+1) T (right; first) + −1 ∑ 2
:()− 1 log ⏟=⏟1⏟⏟⏟2(⏟ ⏟+⏟+⏟1)
H (right) + log 2( )− 1 ⏟⏟2⏟(⏟+⏟) x (right) + − ∑
2 − 1 log ⏟=+⏟2 ⏟⏟⏟2⏟( + )
⏟ T (right; second) ⊕ Shifting some common parts from ( 16 & 17) [i.e. A, H] to the RHS, ‘ − ShiftedParts’ can be replaced with another constant, , and we now have a simpler problem. If we can prove that ⟦⊕⟧ = ⟦<⟧ in (19), then we will have proven the same in (17).
2 − 1 2( )− 1 ⏟⏟2⏟(⏟ ⏟+1)+ log log x (middle) 2 − 1 ⏟⏟2⏟(⏟ ⏟+1)+ log log T (right; first) ⏟⏟2⏟(⏟+⏟ ⏟+⏟1)
x (right) 2( )− 1 + + − ∑ − ∑
log ⏟=+⏟2 ⏟⏟⏟2⏟( + )
⏟ T (right; second) 2 − 1 2 − 1 < ⊕ ⏟⏟2(⏟ ⏟+⏟+⏟1)⏟⏟ ⏟=+⏟2⏟⏟⏟2⏟(⏟+ )
log
T (middle)
Given that the LHS of (19) is clearly smaller than the LHS of (18), by transitivity ⟦⊕⟧ = ⟦<⟧.
Ultimately, this is why we only need to scan upwards in Step (H)(
e z i Rank #2 → 7 candidates
e p z w i r t Rank #3 → 7 candidates e p z w i r t doc e chosen doc p chosen doc i chosen
Relative compensation changes for … → ∀ ranks, doc moves down candidate list. z e i z e w p i r t z e w p i r t Rank #4 → 10 candidates d e p s z w i o r t
Rank #4 → 10 candidates d z e s w p i o r t Rank #5 → 12 candidates u d e p s z w i y o g r t
Rank #5 → 12 candidates u d z e s w p i y o g r t greedy/shallow graph-search approaches. The methods and optimisations described above can be implemented in any programming language, but we provide a sample GPLv3-licensed implementation written in standard C++†. This choice focuses on the open web, given the ubiquity of C++ compilers for all modern operating systems, and the performance benefits associated with the low-level programming paradigm. The implementation ofers a built-in CLI interface with further integrations to follow. The underlying re-ranker runs as a daemon, reachable by diferent processes. With the optimisations described in Section 3, particularly the DEM selection strategy, individually fair re-rankings are placed within reach for any organisation limited to commodity hardware. Usage instructions can be found within the project website.
RQ1 Can we address quality-constrained individual fairness via greedy item-by-item selection? RQ1a Is the greedy method comparable to best-case scenarios (ILP, Graph search, BvN decomp.) in terms of optimal fairness per-ranking? RQ1b Is the greedy method fast enough for general-purpose usage?
RQ1c Is the installation process easy enough to support a non-centralised ecosystem? The first research question ( RQ1) is more-so a mathematical one, with an answer etched out in Section 3, as well as in the subsequent implementation (Section 3.2). However, without analysing how closely the fairness results of this approach align with the best case (RQ1a), it would be unclear under what scenarios each method is better.
RQ1a Optimality We were unable to obtain funding for Gurobi’s cloud-based solution. However, we were able to ascertain some optimally fair re-rankings using exhaustive graph search in SWI-Prolog. We then used these optimal solutions as a reference point to estimate fairness loss when using our greedy method. The Prolog solution space search relies on an observation from Figure 5: given a high enough quality threshold, low ranks will have small numbers of feasible candidates, and higher ranks will have higher numbers of feasible candidates. This a-priori observation considerably reduces the search space of feasible rankings. With a small enough corpus size (≈ 30), and proper re-calculation of feasible items (DEM strategy, Section 3.1), the search space becomes small enough to iterate over each valid ranking. It is thereby possible to determine how many excess rankings our method requires, as compared to a re-ranker that finds the optimally fair re-ranking at each query instance. We investigate this for various values, with the initial and trivial observation that when = 0 , the greedy method produces optimal rankings. Likewise, when = 1 , greedy re-rankings are optimal. †https://librecoir.com/
Using an aggregated metric for unfairness (20), we conducted experiments with the three query types from Figure 6.
This metric counts instances of negative discrimination (underrepresentation as opposed to over-representation). The attention aforded to each document is made relative by division with the sum of all attention. This value is then compared to the item’s relative utility, rel()/ ∑rel().
unfairness =
max [0, ∑ ∈[1,] () ∑ rel() −
∑ ] (20)
The results from this experiment indicated that fairness is much more attainable with some query types versus others.
Query 2 in particular (the green peak in Figure 6) was able to approach fairness relatively quickly, even when excessively high , results are inevitably unfair. was set high ( ≈ 0.88 ).
However, with For example, when a quality threshold of = 0.98 is used, barely any change in ordering is allowed near the top of the result page, and this results in a slowly rising unfairness metric. On the other hand, when quality threshold is low enough ( ≈ 0.78 ), fairness is achieved in Query 2 very early on.
Even with more dificult queries (Queries 1 and 2), a low enough threshold ( < 0.5 ) while using the greedy method leads to reasonable individual fairness. Though the comparison with optimal rankings was restricted to small levels of duplication, and thereby not statistically significant, there is inevitably a trade-of between algorithm eficiency and optimality. This is future research.
Evaluating a system’s ease-of-use is a qualitative and highly subjective task, especially in the case of WWW software; a software suite or package built for the web could be easy to install one month, later rendered entirely unusable the next month due to dependency versioning or backwards compatibility issues. In the case of ML systems, the problem is made worse by widespread practices of publishing pre-trained models without background training sets. At times this is done for copyright reasons, other times because the dataset is too large. We aimed to bypass most compatibility issues by writing the CO*IR program in C++, purposely avoiding external dependencies. Additionally, we bypass issues around datasets by producing a fairness method that doesn’t rely on data. Future work will amend CO*IR to allow for gradually acquired training data for tuning automatically per-query. Evaluation of the system’s ease-ofuse is ongoing, and we welcome feedback from all stakeholders, especially those in positions to implement fairness in product settings (software engineers, system admins, etc.) Query
Query 1 Query 2
Query 3 100000
Repetition 0 50000 150000 200000
Computing time taken for bulk re-ranking jobs on a large corpus (10,000 items). RQ1b Eficiency One of the primary purposes of this work was the attempted introduction of individual fairness to web-scale search on commodity hardware. To evaluate this goal, the CO*IR system was applied to the task of re-ranking a query with 10,000 competing documents, and a gradually declining relevancy slope among documents (like Query 1 in Figure 6). CO*IR was able to produce 8,000 re-rankings in under 3 seconds on an i5 processor (2.30GHz). Results from this experiment are presented in Table 2.
In this work we considered the problem of barriers to entry in fair re-ranking, particularly individually fair re-ranking. We designed and analysed a fair re-ranker for commodity hardware. Optimisations included: tackling the re-ranking problem in a greedy fashion, pre-eliminating infeasible (irrelevant) items, and exploiting edge-cases to allow for early exit from a linear scan. With these optimisations, applying individual fairness on a much higher quantity of results (as compared to prior work; ≫ 100) is now within reach for smaller (as well as larger) organisations.
Future work might aim to make the package more usable in web search scenarios (the preliminary version targets standalone rankings). Distributing the program’s execution across a network of collaborating servers would also be advantageous for the open web. Integrating group fairness as an additional feature, alongside individual fairness, would also be necessary for a more holistically ethical ranking tool, as individual fairness would be inappropriate for the purposes of positive action intervention in rankings [20]. For group fairness, however, there already exists FairSearch [6], which we recommend. Optional multi-threading or GPU support would also increase our tool’s eficiency in many scenarios. We didn’t target this initially; version one was intended first-and-foremost to bring individually fair ranking into the range of possibility for small organisations partaking in an open, non-centralised, web.
Finally, we aim to introduce a modified version of the CO*IR algorithm, which uses the same heuristics as above (8 and 13), applying them in A* graph search [21]. With a pessimistic heuristic, A* search produces admissible solutions [22]; and would therefore be equivalent to the ILP method used by Biega et al. [2]. Varying between pessimistic and optimistic heuristics, we hypothesise it is possible to have a fairness solution that uses system resources dynamically, i.e. optimality when the resources are there, sub-optimality otherwise, and many diferent grades of optimality in-between the two extremes.
This paper was in part funded by the Science Foundation Ireland. I must thank Maaike Visser for her ongoing support, sharing of ideas and guidance. Her Masters thesis [23] provided me an introduction to fairness evaluation metrics, which will help inform future work. Computing Machinery, New York, NY, USA, 2020, p. 2849–2855. URL: https://doi.org/10.1145/3366424.3380048. doi:10.1145/3366424.3380048. [13] M. Zehlike, Fairness in Rankings (Dissertation), Ph.D. thesis, 2022. [14] A. Al-Maskari, M. Sanderson, A review of factors influencing user satisfaction in information retrieval, Journal of the American Society for Information Science and Technology 61 (2010) 859–868. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/asi.21300. doi:https://doi.org/10.1002/asi.21300.
arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/asi.21300. [15] O. Chapelle, D. Metlzer, Y. Zhang, P. Grinspan, Expected reciprocal rank for graded relevance, in: Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM ’09, Association for Computing Machinery, New York, NY, USA, 2009, p. 621–630. URL: https://doi.org/10.1145/1645953.1646033.
doi:10.1145/1645953.1646033. [16] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, G. Hullender, Learning to rank using gradient descent, in: Proceedings of the 22nd International Conference on Machine Learning, ICML ’05, Association for Computing Machinery, New York, NY, USA, 2005, p. 89–96. URL: https://doi.org/10.1145/1102351.1102363. doi:10.1145/1102351.1102363. [17] N. Craswell, O. Zoeter, M. Taylor, B. Ramsey, An experimental comparison of click position-bias models, in: Proceedings of the 2008 International Conference on Web Search and Data Mining, WSDM ’08, Association for Computing Machinery, New York, NY, USA, 2008, p. 87–94. URL: https://doi.org/10.1145/1341531.1341545.
doi:10.1145/1341531.1341545. [18] A. Agarwal, I. Zaitsev, X. Wang, C. Li, M. Najork, T. Joachims, Estimating position bias without intrusive interventions, in: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM ’19, Association for Computing Machinery, New York, NY, USA, 2019, p. 474–482. URL: https://doi.org/10.1145/3289600.3291017. doi:10.1145/3289600.3291017. [19] X. Wang, N. Golbandi, M. Bendersky, D. Metzler, M. Najork, Position bias estimation for unbiased learning to rank in personal search, in: Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM ’18, Association for Computing Machinery, New York, NY, USA, 2018, p. 610–618. URL: https://doi.org/10.1145/3159652.3159732. doi:10.1145/3159652.3159732. [20] M. Zehlike, A. Loosley, H. Jonsson, E. Wiedemann, P. Hacker, Beyond incompatibility: Trade-ofs between mutually exclusive fairness criteria in machine learning and law, 2022. arXiv:2212.00469. [21] P. E. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics 4 (1968) 100–107. doi:10.1109/TSSC.1968.300136. [22] S. J. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed., Pearson,
Boston, 2018. [23] M. Visser, Investigating Fair Rankers Under the Expected Exposure Framework, Master’s thesis, 2022.