Ranking is the problem of retrieving the most rele vaitnetms for a query in a pool ofitems. Since ranking algorithms are extensively used in socially sensitive applications (e.g., candidate selections and search engines), it becomes critical to take into account an adequate notion of fairness. In this paper, we consider a flexible optimization-based fair ranking framework and we analyze optimal state-of-the-art algorithms on real-world data. We identify the merits as well as bottlenecks of existing methods and point out directions for future research.
CEUR ceur-ws.org
methods for concrete applications. As a byproduct of our evaluation, we also point toward future research directions. In particular, we provide the following contributions: • An explicit description of two state-of-the-art methods appeared in past literature only implicitly and in the proofs of runtime bounds. • A discussion on the benefits of these methods as well as their drawbacks. • A numerical evaluation of real-world datasets aimed at assessing the maturity of these solutions for concrete deployment into real-world applications. To the best of our knowledge, this is the first numerical evaluation of these methods.
Related work. Ranking with fairness constraints has recently received much attention from
the research community, and a complete account is given in a recent su2r, v3e].yO[ ne can
distinguish at least two diferent approaches to enforce fairness constraints in a proasnt-king:
hoc adjustments (e.g., [
In [
introduces the problem setting. Sect3iodnetails the considered methods and Sect4ioprnesent the numerical evaluation. Finally, Sect5idonraws some conclusions and sketches future directions for research.
Notation. ℕ, ℤ, ℝ denote the set of natural, integer, and real numbers. Weℕd0efin“eℕ∪t0u, ℝ` ≔ ℝ ∩ r0, ∞q andℤ` ≔ ℤ ∩ ℕ0. For every ∈ ℕ , r s will denote the ste1t, 2, … , u. Given a set we denote its cardinality|by|. Given , ∈ ℕ and a se t , × denotes the set of by matrices with entries in. We will denote vectors with lowercase bold letters and matrices with uppercase bold letters. Given a vecatwore denote its-th entry with . The zero norm of a vectora is defined as }a}0 ≔ |t ∶ ‰ 0u|. Given a matrixA we denote itps, q-th entry with when is true and0 otherwise. . Given a logical predicat,ewe denote its indicator function pbyq, notice thatp q “ 1
Given , ∈ ℕ
, the ranking problem consists informally of retrieving (and sorting) the items in a pool of upon receiving a query. Thuetility of an item depends on the specific query and maybe the level of the required skill in a job ofer, or the h-index in a Google Scholar search. In this work, we assume that the query is given and fixed, so that we collect the utility of placing a ite m∈ r s in position ∈ r s in autility matrix U ∈ × . We stress the importance ` of accounting for the position of a item in a given ranking: in a real-world setting, the perceived utility is inversely proportional to the item’s position in the ranking, a phenomenon known as position bias. A ranking is a vectorr ∈ r s s.t. “ if item is placed in positio n, assigned to positionin the ranking, ii∑) and ‰ for each ‰ . For ∈ r s the -prefix We introduce thaessignment matrix of a rankingA ∈ t0, 1u× ≤ 1 for each ∈ r s and∑ where i) “ 1 if item is “1
“ 1 for each of a rankingr is the vector “ p 1, … , q. ∈ r s. We denote the set of all such matrices b. yNotice that there is a bijection between the set of the rankings and the set of the assignment matrices, thus we can speak about a ranking or its assignment matrix interchangeably.oTpthiemal ranking problem is defined as max ∑ A∈ “1 “1
∑ . max A∈ ∑
∑ “1 “1 “1 ∈ ℓ s.t. ℓp q ≤ ∑
∑ ≤ ℓp q, ∀ ∈ r s, ∀ ∈ r s . optimal value of the above problem will be denoted wOPitTh.
We notice that this problem has bina⋅ ry decision variables an ⋅d p ` q constraints. The ranking, that is
fairness and denote withℓ ⊆ r s the set of items having the properℓt∈y r s: examples of properties are the gender, the ethnicity or the age. Fairness may be expressed via lower and upper bounds on the number of items featuring a given properties in each prefix of the ranking.
number of men and women. Formally, the matricFepsq, Fp q ∈ ℤ specifies the minimum F p q and the maximum numberFpℓ q of items having the propertℓyin the -prefix of a feasible ℓ × ` (1) (2) (3) “1 ∈ ℓ ℓp q ≤ ∑
∑ ≤ ℓp q, ∀ ∈ r s, ∀ ∈ r s .
These matrices are callelodwer fairness constraint matrix andupper fairness constraint matrix respectively. TheOptimal Fair Ranking (OFR) problem is thus defined as
positions bias. We denote wi ththeabsolute utility of the item . We consider the following models for the utility of placing ∈ r s in position ∈ r s loolooogoo2´om1po1ooo`ooonq, lo oopo1oo´moooqoo´on1, looopom“ooo1onq ℎ (4)
model presented above does not need to be. Further, notice that the geometric model is parametrized by adiscount factor ∈ r0, 1s controlling how quickly the utility of an item decays w.r.t. its position in the ranking.
1 1 ≥ 2 1, 1 1 ≥ 1 2, 1 1 ` 2 2 ≥ 1 2 ` 2 1 (5) where the two leftmost inequality are called monotonicity and the rightmost is knMowonngaes condition. We notice that is the users are sorted in descending order of absolute utilities, then any of the above models for the position bias satisfies the Equat5i)o.n (
belonging to a certain category that can appear in a given prefix. This can be done by setting Fp q to the zero matrix and only specifyiFnpgq. We name this problemOptimal Fair Ranking with Upper constraints (OFRU).
optimality and runtime guarantees that depend on certain parameters, making them better suited under diferent circumstances. We notice that these methods first appear1e]d, binut[ only implicitly with the proofs of the main theorems. We notice that this is the first explicit description of such algorithms.
Dynamic programming. We define the type of an item as a binary vectotrp q ∈ t0, 1u such tha tℓp q “ 1 if and only if has the propertyℓ ∈ r s. Let ≔ ttp q ∶ ∈ r su the set of diferent types in the data, and l≔et | |. We let the elements ofbe p1q, … , p q and define ℓ ≔ t ∈ r s ∶ tp q “ pℓqu - the set of the firs t items of typeℓ - for eachℓ ∈ r s. We denote with ℓ the cardinality oℓf and its elements wi tp1hℓq, … , pℓq. ℓ
(i.e., the items with the smallest indices) for each type. In light of Equ3a),taiomnon(g these (at while 1 ` ⋯ ` ă do
u Ð p0, … , 0q ∈ ℕ0 for ℓ “ 1, … , do Initializer0, … , 0s Ð 0, 1, … , Ð 0, “ empty list if Feasiblep 1, … , ℓ ` 1, … , q then ℓ Ð r 1, … , s ` pℓℓq ℓ Ð ´∞ Get the indexℓ˚ and the value˚ of maxℓ∈r s ℓ
Increment ℓ˚ Ð ℓ˚ ` 1, r 1, … , s Ð ˚, . appendp pℓℓ˚qq
Input: the set s 1, … , , the utility matrUix, the constraintFsp q, Fp q, and the set of properties t1, … , u.
else end if end for end while Output: the optimal rankin g,the optimal utilitry 1, … , ℓs. most) ⋅ items there will be the optimal ranking. Notice step can be done in or⋅ dertoimfe and produces the se ts1, … , . simple: it is enough to check that
The idea of the dynamic programming approach is the following. We can partition the set of all possible rankings of a certain le n≤g th according to the number of items of each type they have. That is, fo r1, … , ∈ ℕ0 s.t. “ 1 ` ⋯ ` we denote withp 1, … , q the set of all rankings of lengt hmade of items of typevp q for each ∈ r s. Furthermore, withr 1, … , s we denote the value of the feasible rankings of the highest vapl1u,e…in, q. Thus, finding the optimal solution to an OFR problem corresponds to identifying a feasible ranking of utility r 1, … , s “ OPT, when 1 ` ⋯ ` “ . Checking feasibility of the rankingsp i1n, … , q is ℓp q ≤ ∑ ℎ ℓpℎq ≤ ℓp q, ∀ℓ ∈ r s, which takes order o f⋅ time.
We start initializ inrg0, … , 0s “ 0 and notice that by Equatio5n), (it either holds that r 1, … , s “ max r 1, … , ℓ ´ 1, … , s ` pℓq , ℓ´1 ℎ“1 ℓ∈r s or thatp 1, … , q is infeasible in which case we setr 1, … , s “ ´∞. As a result, we can build the optimal solution with a bottom-up approach: we startp0fr,…om, 0q and we build the ranking by adding an item of maximal utility that keeps the constraints satisfied at each step.
rankings that needed to be considered (all the ways to cnhaotsueral numbers so that they sum to ). The overall algorithm is described in Algori1t.hBmelow we report the theorem establishing its theoretical performances.
Theorem 1 (Theorem 3.1 in [
Remark 1 (On the complexity of Algorith1m). We make the following comments: • We notice that an exhaustive search among all possible rankings of leinngathpool of ⋅ takes the order o f time. On the other hand, the proposed method takes the order of time, which is better: in real-world applicat ioshnosu,ld be thought of as a constant determined by the fairness constraints, w hiilsea parameter that can be as larg e. as • The practicality of Algorith1mdepends on the value o.f We notice tha t≥ , implies that when fairness is defined using more than 2-3 properties, the algorithm becomes unpractical.
alternative greedy approach.
The algorithm is simple. Similarly to Algorit1,himt keeps the items grouped into the set 1, … , . At each ste p, the algorithm greedily takes the item with the highest utilvitpyq- let its type - and adds it to the ranking if this addition does not violate the constraints. Otherwise, it seeks the next item among the typtevsp1q, … , vp qu{tv p qu. If no feasible item can be found, the problem is declared to be infeasible. Since ther e aproesitions to fill and each item can be checked for feasibility in order otfime, the runtime of this algorithm is the orde⋅ r of. The algorithm is also described in Algorit2h.m
Δ ≔ max } }0 (6)
∈ that isΔ, is the maximum number of properties each type of item can exhibit. Then the following holds.
Theorem 2 (Theorem 3.2 in [
Input: the set s 1, … , , the utility matrUix, the constraintFsp q, Fp q, and the set of properties t1, … , u.
Initialize Ð 0, 1, … , Ð 0, “ empty list for “ 1, … , do
Sort by decreasing utilipt11yq, … , p q # We denote wit h the sorted indices for ℓ “ 1, … , do if Feasiblep 1, … , ℓ ` 1, … , q then
Ð ` pℓℓq , . appendp pℓℓqq, ℓ Ð ℓ{t pℓℓqu, Flag Ð true end if end for if flag ““ false then return Infeasible end if end for
• The runtime of this greedy method is exponentially) (simnaller than that of Theor1e.m
• When Δ ≥ 3, Theorem 10.2 in [
item pool to retain only the t⋅ op items. This step is justified by the Equation5)(. In practice, even when the utilities are obtained from an application of the position-bias model to the absolute utilities, it is often not the case that the items are already sorted in a wsaatyitsfiehsat
on their absolute utilities, a step that requires o rldoegr otfime. Overall the pre-processing runs in order o ⋅f log ` ⋅ time. In the case of Algorith2mthis pre-processing time dominates over the ranking time.
⋅ space. In addition, Algorith1malso requires to store the array withrt1h,e… , s values, which can require up to order of space. This results in a strong limitation - even disposing of time, when is moderately large it is not possible to run this method.
work within this framework, it is necessary to translate this constraint into thFep mqatrices andFp q. This is not straightforward in general, but we will show an example in 4S.ection Chess Ranking
• Exemplify some typical values thaatndΔ may take in real-world applications. • What is the actual runtime of Algori1t?hmDoes it follow the theoretical complexity? • How does Algorithm2 compare with Algorithm1even when the hypothesis of Theorem2 are violated?
For all datasets, we consider the logarithmic position-bias model discussed in2S.eFcotrion the sake of comparison, when setting the fairness constraints we alwaFypsq p“ut0, thus restricting the problems to be instances of the OFRU problemF.p Fqowre consider the notion of fairness known apsroportional representation, where the entrpy, ℓ q of the upper fairness constraint matrix i|s |{ , where is the subset of items that have prope r.tNyotice that this constraint imposes that each property, in the firpsotsitions, cannot be represented with more items than the overall population, fractionally. For each algorithm, we measure the runtime excluding the pre-processing that is common to both methods. For Algor2iwthemreport also thecompetitive ratio of the computed rankinrĝ, this is defined as the ratio between the utility of r̂ and the optimal valuOePT. This ratio takes valueri0n, 1s and follows the semantic ththaet higher the better. Notice that, due to its optimality, for Algor1ithmis ratio always evaluates 1.
3251 entries, one per player. For each player, we have the absolute utility as given by the FIDE
rating, the gender (male or female), and the race (Asian, Hispanic-Latin, white). Notice that
in this dataset there are no women of Hispanic-Latin ethnicity, so“t5haatndΔ “ 2. We
derive two more datasets from Chess Ranking. We consider a simplified version, that we name
Chess Ranking S(implified), where each player has a gender and is either white or non-white,
leading to“ 4 andΔ “ 2. Instead, we drop the gender attributCehienss Ranking R(ace)
and keep the ethnicity, leading t“o3 andΔ “ 1. Occupation [
actual runtime scales with a diferent law depending on the dataset. This is in line with the theory as the leading term in the bound takes on the expres5s,ion4, 3, 2 respectively on the considered datasets. Second, we notice that on at least 3 out of 4 datasets, the behavior of
Optimization. We now fix “ 100 and compareDP toGreedy. Results are shown in Tab2l.e
Chess Ranking Chess Ranking S
Chess Ranking, it is 6 orders of magnitude faster. Second, even wΔhąen1, Greedy features a competitive ratio very close1t,omeaning that it essentially finds an optimal solution. Third, in the case of Occupation WGreedy finds an optimal solution in abou0t.2 seconds, while it is not even possible to runDP due to the tremendous space required to store the tablre1f,o…r, s: 10094 elements for this dataset.
ness constraints must be accounted for. In this paper, we present and discuss an important optimization-based framework for ranking with fairness constraints. We provide, for the first time, an explicit description of state-of-the-art algorithms and evaluate them critically on realworld datasets. By considering the critical parameters controlling the complexity of the fair ranking problem, we shed light on the limitations of the exact dynamic programming method.
than 3 properties are used to define fairness. On the other hand, the greedy approach seems to ofer a viable alternative even when the hypothesis that ensures its optimality is violated.
real-world applications such as candidate selection in job matching.
case Δ “ 2; re-parameterize the problem and design novel algorithms with better dependencies on the parameters than Algorit1h; midentify additional assumptions to place to escape NPhardness results.
program under grant number 101070363 - AEQUITAS. Funded by the European Union. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union. Neither the European Union nor the granting authority can be held responsible for them.