Two-sided fairness in rankings via Lorenz dominance
Year: 2021

Abstract:
We consider the problem of generating rankings that are fair towards both users and item producers in recommender systems. We address both usual recommendation (e.g., of music or movies) and reciprocal recommendation (e.g., dating). Following concepts of distributive justice in welfare economics, our notion of fairness aims at increasing the utility of the worse-off individuals, which we formalize using the criterion of Lorenz efficiency. It guarantees that rankings are Pareto efficient, and that they maximally redistribute utility from better-off to worse-off, at a given level of overall utility. We propose to generate rankings by maximizing concave welfare functions, and develop an efficient inference procedure based on the Frank-Wolfe algorithm. We prove that unlike existing approaches based on fairness constraints, our approach always produces fair rankings. Our experiments also show that it increases the utility of the worse-off at lower costs in terms of overall utility.

heading: 1 Introduction
text: Recommender systems have a growing impact on the information we see and on our life opportunities, as they help us browse news articles, find a new job, house, or people to connect with. While the objective of recommender systems is usually defined as maximizing the quality of recommendations from the user’s perspective, the recommendations also have an impact on the recommended “items”. News outlets rely on exposure to generate revenue, finding a job depends on which recruiter gets to see our resume, and the effectiveness of a dating application also depends on who we are recommended to—and if we are being recommended, then someone else is not. Two-sided fairness in rankings is the problem of generating personalized recommendations by fairly mediating between the interests of users and items. It involves a complex multidimensional trade-off. Fairness towards item producers requires boosting the exposure of small producers (e.g., to avoid winner-take-all effects and popularity biases [1]) at the expense of average user utility. Fairness towards users aims at increasing the utility of the least served users (e.g., so that least served users do not support the cost of item-side fairness), once again at the expense of average user utility. The goal of this paper is to provide an algorithmic framework to generate rankings that achieve a variety of these trade-offs, leaving the choice of a specific trade-off to the practitioner.
The leading approach to fairness in rankings is to maximize user utility under constraints of equal item exposure (or equal quality-weighted exposure) [54, 7] or equal user satisfaction [6]. When these constraints imply an unacceptable decrease in average user utility, so-called “trade-offs between utility and fairness” [65, 41] are obtained by relaxing the fairness constraints, leading to the optimization of a trade-off between average user utility and a measure of users’ or items’ inequality.
Thinking about fairness in terms of optimal utility/inequality trade-offs has, however, two fundamental limitations. First, the optimization of a utility/inequality trade-off is not necessarily Pareto-efficient from the point of view of users and items: it sometimes chooses solutions that decrease the utility of some individuals without making anybody else better off. We argue that reducing inequalities by decreasing the utility of the better-off is not desirable if it does not benefit anyone. The second
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
limitation is that focusing on a single measure of inequality does not address the question of how inequality is reduced, and in particular, which fraction of the population benefits or bears the cost of reducing inequalities.
In this paper, we propose a new framework for two-sided fairness in rankings grounded in the analysis of generalized Lorenz curves of user and item utilities. Widely used to study efficiency and equity in cardinal welfare economics [53], these curves plot the cumulative utility obtained by fractions of the population ordered from the worst-off to the best-off. A curve that is always above another means that all fractions of the populations are better off. We define fair rankings as those with non-dominated generalized Lorenz curves for users and items. First, this definition guarantees that fair rankings are Pareto efficient. Second, examining the entirety of the generalized Lorenz curves provides a better understanding of which fractions of the population benefit from an intervention, and which ones have to pay for it. We present our general framework based on Lorenz dominance in usual recommendation settings (e.g., music or movie recommendation), and also show how extend it to reciprocal recommendation tasks such as dating applications or friends recommendation, where users are recommended to other users.
We present a new method for generating rankings based on the maximization of concave welfare functions of users’ and items’ utilities. The parameters of the welfare function control the relative weight of users and items, and how much focus is given to the worse-off fractions of users and items. We show that rankings generated by maximizing our welfare functions are fair for every value of the parameters. Our framework does not aim at defining what parameters are suitable in general — rather, the choice of a specific trade-off depends on the application.
From an algorithmic perspective, two-sided fairness is challenging because items’ utilities depend on the rankings of all users, requiring global inference. Previous work on item-side fairness addressed this issue with heuristic methods without guarantees or control on the achievable trade-offs. We show how the Frank-Wolfe algorithm can be leveraged to make inference tractable, addressing both our welfare maximization approach and existing item-side fairness penalties.
We demonstrate that our welfare function approach enjoys stronger theoretical guarantees than existing methods. While it always generates rankings with non-dominated generalized Lorenz curves, many other approaches do not. We show that one of the main criteria of the literature, called equity of attention by Biega et al. [7], can lead to decrease user utility, while increasing inequalities of exposure between items. Moreover, equal user satisfaction criteria in reciprocal recommendation can lead to decrease the utility of every user, even the worse-off. Our notion of fairness prevents these undesirable behaviors. We report experimental results on music and friend recommendation tasks, where we analyze the trade-offs obtained by different methods by looking at different points of their Lorenz curves. Our welfare approach generates a wide variety of trade-offs, and is, in particular, more effective at improving the utility of worse-off users than the baselines.
We present our formal framework in Section 2. We discuss the theoretical properties of previous approaches in Section 3, and present our ranking algorithm in Section 4. Our experiments are described in Section 5, and the related work is discussed in Section 6.

heading: 2 Two-sided fairness via Lorenz dominance

heading: 2.1 Formal framework
text: Terminology and notation. We identify an item with its producer, so that “item utility” means “item producer’s utility”. The main paper focuses on fairness towards individual users and items. We describe in Appendix B the extension of our approach to sensitive groups of users or items. |X | denotes the cardinal of the set X . Given n 2 N, we denote by [[n]] = {1, . . . , n}. The set of users N is identified with {1, ..., |N |} and the set of items I is identified with {|N | + 1, ..., n} where n = |N |+ |I|. For (i, j) 2 N ⇥ I, we denote by µij the value of item j to user i. A (deterministic) ranking : I ! [[|I|]] is a one-to-one mapping from items j to their rank (j). Following [54], we use stochastic rankings because they allow us to perform inference using convex optimization (see Section 4). The recommender system produces one stochastic ranking per user, represented by a 3-way ranking tensor P where Pijk is the probability that j is recommended to i at rank k. We denote by P the set of ranking tensors.
Utilities of users and items are defined through a position-based model, as in previous work [54, 7, 63]. Let v 2 R|I|, where vk is the exposure weight at rank k. We assume that lower ranks receive more exposure, so that 8k 2 [[|I| 1]], vk vk+1 0.1 Given a user i and a ranking i, the user-side utility of i is the sum of the µijs weighted by the exposure weight of their rank i(j): ui( i) = P j2I v i(j)µij . Given an item j, the item-side utility of j is the sum over users i of the exposure of j to i. These definitions extend to stochastic rankings by taking the expectation over rankings, written in matrix form:2
user-side utility: ui(P ) = X
j2I µijPijv item-side utility (exposure): uj(P ) =
X
i2N Pijv
We denote by u(P ) = (ui(P ))ni=1 the utility profile for P , and by U = {u(P ) : P 2 P} the set of feasible profiles. For u 2 U , uN = (ui)i2N and uI = (ui)i2I denote the utility profiles of users and items respectively.
Two-sided fairness in rankings. In practice, values of µij are not known to the recommender system. Ranking algorithms use an estimate µ̂ of µ based on historical data. We address here the problem of inference: the task is to compute the ranking tensor given µ̂, with the goal of making fair trade-offs between (true) user and item utilities. Notice that the user-side utility depends only on the ranking of the user, but for every item, the exposure depends on the rankings of all users. Thus, accounting for both users’ and items’ utilities in the recommendations is a global inference problem.
More general item utilities We consider exposure as the item-side utility to follow prior work and for simplicity. Our framework and algorithm readily applies in a more general case of two-sided preferences, where items also have preferences over users (for instance, in hiring, job seekers have preferences over which recruiters they are recommended to). Denoting µji the value of user i to item j, the item side-utility is then uj(P ) =
P i2N µjiPijv.

heading: 2.2 Lorenz efficiency and the welfare function approach
text: Our notion of fairness aims at improving the utility of the worse-off users and items. Since this does not prescribe exactly which fraction of the worse-off users/items should be prioritized, the assessment of trade-offs requires looking at all fractions of the population. This is captured by the generalized Lorenz curve used in cardinal welfare economics [53]. Formally, given a utility profile u, let (u(i))ni=1 be the sorted values in u from smallest to largest, i.e., u(1)  . . .  u(n), then the generalized Lorenz curve plots (Ui)ni=1 where Ui = u(1) + . . . + u(i). To assess the fairness of trade-offs, we rely on the following dominance relations on utility profiles:
Pareto-dominance P. u P u0 () (8i 2 [[n]], ui u0i and 9i 2 [[n]], ui > u0i). Lorenz-dominance L. Then u L u0 () U P U 0. We write ⌫L for non-strict Lorenz dominance (i.e., 8i, Ui U 0i ). Notice that Pareto-dominance implies Lorenz-dominance. Our notion of fairness, which we call Lorenz efficiency, states that a ranking is fair if the utility profiles for users and for items are not jointly Lorenz-dominated:
1We use a user-independent v for simplicity. Considering user-dependent weights is straightforward. 2We consider Pij as a row vector in the formula, so that Pijv = P|I| k=1 Pijkvk.
Definition 1 (Lorenz efficiency). A utility profile u 2 U is Lorenz-efficient if there is no u0 2 U such that either (u0I ⌫L uI and u0N L uN ) or (u0N ⌫L uN and u0I L uI).
We consider that Lorenz-dominated profiles are undesirable (and unfair) because the utility of worseoff fractions of the population could have been increased at no cost for total utility. Examples of Lorenz-curves of users and items are given in Fig. 1. The blue solid, green dotted and orange dashed curves are all non-dominated (the blue solid ranking has higher user utility but high item inequality, the green dotted and orange dashed curves have similar item exposure profiles, but user curves that intersect). On the other hand, the red dot/dashed curve is an unfair ranking: compared to the green dotted and orange dashed curve, all fractions of the worse off users have lower utility, together with less exposure for worse-off items.
A fundamental result from cardinal welfare economics is that concave welfare functions of utility profiles order profiles according to Lorenz dominance [3, 53]. The choice of the welfare function specifies which (fair) trade-off is desirable in a specific context. This result holds when all utilities are comparable. In our case where there are users and items, we propose the following welfare function parameterized by ✓ = ( ,↵1,↵2):3
8u 2 Rn+ : W✓(u) = (1 ) X
i2N (ui,↵1) +
X j2I (uj ,↵2) with (x,↵) =
8 <
:
x ↵ if ↵ > 0
log(x) if ↵ = 0 x↵ if ↵ < 0 .
Inference is carried out by maximizing W✓ (an efficient algorithm is proposed in Section 4):
(ranking procedure) P ⇤ 2 argmax
P2P W✓(u(P )) (1)
In W✓, 2 [0, 1] controls the relative weight of users and items. The motivation for the specific choice of is that it appears in scale invariant welfare functions [43], but other families can be used as long as the functions are increasing and concave. Monotonicity implies that maxima of W✓ are Paretoefficient. For ↵1 < 1 and ↵2 < 1, W✓ is strictly concave. Then, W✓ exhibits diminishing returns, which is the key to Lorenz efficiency: an increment in utility for a worse-off user/item increases welfare more than the same increment for a better-off user/item. The effect of the parameters is shown in Fig. 1 (left): For item fairness we obtain more item equality by using ↵1 < 1 (here, ↵1 = 0.5) and incrasing (see blue solid vs orange dashed curve). The parameter ↵2 controls user fairness: smaller values yield more user utility for the worse-off users at the expense of total utility, with similar item exposure curve (green dotted vs orange dahsed curves). Let ⇥ = {( ,↵1,↵2) 2(0, 1)⇥ ( 1,1)2}. For every ✓ 2 ⇥,W✓ is strictly concave, and users and items have non-zero weight. We then have (the result is a straightforward consequence of diminishing returns, see Appendix C):
Proposition 1. 8✓ 2 ⇥, 8P ⇤ 2 argmax P2P W✓(u(P )), P ⇤ is Lorenz-efficient.
Relationship to inequality measures A well-known measure of inequality is the Gini index, defined as 1 2⇥AULC, where AULC is the area under the Lorenz curve. The difference between Lorenz and generalized Lorenz curves is that the former is normalized by the cumulative utility. This difference is fundamental: we can decrease inequalities while dragging everyone’s utility to 0. However, this would lead to dominated generalized Lorenz curves. Interestingly, for item-side fairness, the cumulative exposure is a constant and thus trade-offs between user utility and item exposure inequality are not really problematic. However, for user-side fairness, the total utility is not constant and reducing inequalities might require dragging the utility of some users down for the benefit of no one.
Additional theoretical results In App. C.2, we show that as ↵1,↵2 ! 1, utility profiles tend to leximin-optimal solutions [43]. Leximin optimality corresponds to increasing the utility of the worst-off users/items one a a time, similarly to a lexical order. In App. C.3, we present an excess risk bound, which provides theoretical guarantees on the true welfare when computing rankings based on estimated preferences, depending on the quality of the estimates.
3W✓(u) = 1 if ↵  0 and 9i, ui = 0. In practice, we use (x+ ⌘,↵) for ⌘ > 0 to avoid this case.

heading: 2.3 Extension to reciprocal recommendation
text: In reciprocal recommendation problems such as dating, the users are also items. The notion of fairness simplifies to increasing the utility of the worse-off users, which can in practice be done by boosting the exposure of worse-off users. Our framework above applies readily by taking N = I and n = |N |. The critical step however is to redefine the utility of a user to account for the fact that (1) the user utility comes from both the recommendation they receive and who they are recommended to, and (2) users have preferences over who they are recommended to.
To define this two-sided utility, let us denote by µij the mutual preference value between i and j, and our examples follow the common assumption that µij = µji (see e.g., [45]). For instance, when recommending CVs to recruiters, µij can be the probability of interview, while in dating, it can be that of a “match”. The two-sided utility is then the sum of the user-side utility and item-sided utility of the user:
user-side utility (j recommended to i)z }| { ui(P ) = X
j2I µijPijv
item-side utility (i recommended to j)z }| { vi(P ) = X
j2N µijPjiv
(two-sided) utilityz }| { ui(P ) = ui(P ) + vi(P )
With this definition of two-sided utility, our previous framework can be readily applied using N = I . A (two-sided) utility profile u 2 U is Lorenz-efficient if there is no u0 2 U such that u0 L u. The welfare function simplifies to W✓(u) = Pn i=1 (ui,↵), and Proposition 1 also holds true in this setting: maximizing the welfare function always yields Lorenz-efficient rankings.
Fig. 1 (right) illustrates how decreasing ↵ increases utilities for the worse-off users at the expense of total utility. It also shows a Lorenz-dominated (unfair) profile, in which all fractions from the worst-off to the better-off users have lower utility.
From now on, we refer to one-sided recommendation for non-reciprocal recommendation.

heading: 3 Comparison to utility/inequality trade-off approaches
text: As stated in the introduction, leading approaches to fairness in ranking are based on utility/inequality trade-offs. We describe here the representative approaches we consider as baselines in our experiments. We then present theoretical results illustrating the undesirable behavior of some of them.

heading: 3.1 Objective functions
text: One-sided recommendation In one-sided recommendation, the leading approach is to define exposure-based criteria for item fairness [54, 7]. The first criterion, equality of exposure, aims at equalizing exposure across items. The second one, quality-weighted exposure4, which is advocated by many authors, defines the quality of an item as the sum of user values qj = P i2N µij and aims for item exposure proportional to quality. The motivation of quality-weighted exposure is to take user utilities into account in the extreme case where the constraint is strictly enforced. Interestingly, as we show later, this approach has bad properties in terms of trading off user and item utilities.
In our experiments, we use the standard deviation as a measure of inequality. Denoting by E = |N | kvk1 the total exposure and by Q = P j2I qj the total quality:
quality-weighted exposure F qua (u) =
X
i2N ui
p Dqua(u) with Dqua(u) = 1
n
X
j2I
⇣ uj qjE
Q
⌘2 .
equality of exposure
F (u) = X
i2N ui
p D(u) with D(u) = X
j2I
1
n
⇣ uj
1 |I| X
j02I uj0
⌘2 .
Some authors use D0(u) = P
(j,j0)2I2 | uj qj
uj0qj0 | instead of p Dqua [55, 42, 6]. Dqua and D0 have
qualitatively the same behavior. We propose Dqua(u) as a computationally efficient alternative to D0, since it involves only a linear number of terms and p Dqua is convex and differentiable except on 0.
4We use here the terminology of [63]. This criterion has also been called “disparate treatment” [54], “merit-based fairness” [55] and “equity of attention” [7].
Reciprocal recommendation For reciprocal recommendation, we consider as competing approach a trade-off between total (two-sided) utility and inequality of utilities, as measured by the standard deviation:
equality of
utility F (u) =
X
i2N ui
p D(u) with D(u) = X
j2I
1
n
⇣ uj
1 |I| X
j02I uj0
⌘2 .

heading: 3.2 Inequity and inefficiency of some of the previous approaches
text: We point out here to two deficiencies of previous approaches.
First, for one-sided recommendation, we show that in some cases, compared to the welfare approach with any choice of the parameter ✓ 2 ⇥, quality-weighted exposure leads to the undesirable behavior of decreasing user utility while increasing inequalities of exposure between items. This is formalized by the proposition below, which uses the following notation: for ✓ 2 ⇥, let u✓ = argmax
u2U W✓(u),
and for > 0, let Uqua = argmax u2U F qua (u). Proposition 2. The following claims hold irrespective of the choice of uqua, 2 Uqua .
For every d 2 N⇤ and every N 2 N⇤, there is a one-sided recommendation problem, with d+ 1 items and N(d+ 1) users, such that 8✓ 2 ⇥, we have:
9 > 0,u✓N L u qua, N and u ✓ I L u qua, I
and lim
!1
P i2N u
qua, iP
i2N u ✓ i
! d!1
5 6 .
Second, in reciprocal recommendation, striving for pure equality can even lead to 0 utility for every user, even that of the worst-off user. More precisely, we show that in some cases, compared to the welfare approach with any choice of parameter ✓ 2 ⇥, there exists > 0 such that equality of utility has lower utility for every user, eventually leading to 0 utility for everyone in the limit ! 1. Proposition 3. For > 0, let Ueq = argmaxu2U F (u). The claim below holds irrespective of the choice of ueq, 2 Ueq . Let n 5. There is a reciprocal recommendation task with n users such that:
8✓ 2 ⇥,u✓, 9 > 0 : 8i 2 [[n]], u✓i > u eq, i and lim
!1
X i2N u eq, i = 0.
Proofs and additional results All proofs are deferred to App. D, where we provide several additional results regarding the use of quality-weighted exposure and equality of exposure in reciprocal recommendation: We show in Prop. 8 that there are cases where both approaches lead to user utility profiles with Lorenz-dominated curves, and significantly lower total user utility than the welfare approach for any choice of the parameters.

heading: 4 Efficient inference of fair rankings with the Frank-Wolfe algorithm
text: We now present our inference algorithm for (1). Appendix E contains the proofs of this section and describes a similar approach for the objective functions of the previous section. From an abstract perspective, the goal is to find a maximum P ⇤ such that:
P ⇤ 2 argmax
P2P W (P ) with W (P ) =
nX
i=1
i
✓ nX
j=1
µij(Pij + Pji)v
◆
where for every i, i : R+ ! R is concave increasing, µij 0 and v is a vector of non-negative non-increasing values. Since W is concave and P is defined by equality constraints, the problem above is a convex optimization problem. However, this is a global optimization problem over the rankings of all users, so a naive approach would require |N ||I|2 parameters and 2|N ||I| linear constraints. The same problem arises with the penalties of previous work. In the literature, authors either considered applying the item-fairness constraints to each ranking individually [54, 6], which leads to inefficiencies with our definition of utility (see Appendix H), or resort to heuristics to compute the rankings one by one without guarantees on the trade-offs that are achieved [42, 7].
Our approach is based on the Frank-Wolfe algorithm [18], which was previously used in machine learning in e.g., structured output prediction or low-rank matrix completion [30], but to the best of
our knowledge not for ranking. Denoting hX |Y i = P
ijk XijkYijk the dot product between tensors, the algorithm creates iterates P (t) by first computing P̃ = argmaxP2PhP |rW (P (t))i and then updating P (t) = (1 (t))P (t 1) + (t)P̃ with (t) = 2t+2 [13]. Starting from an initial solution
5, the algorithm always stays in the feasible region without any additional projection step. Our main contribution of this section is to show that argmaxP2PhP |rW (P (t))i can be computed efficiently, requiring only one sort operation per user after computing the utilities. In the result below, for a ranking tensor P and a user i, we denote by S(Pi) the support of Pi in ranking space.6
Theorem 1. Let µ̃ij = 0i ui(P (t)) µij + 0j uj(P (t)) µji. Let P̃ such that:
8i 2 N , 8̃i 2 S(P̃i): ̃i(j) < ̃i(j0) =) µ̃ij µ̃ij0 . Then P̃ 2 argmax P2P hP |rW (P (t))i.
Moreover, it produces a compact representation of the stochastic ranking as a weighted sum of permutation matrices. The number of iterations of the algorithm allows to control the trade-off between memory requirements and accuracy of the solution. Using previous convergence results for the Frank-Wolfe algorithm [13], assuming each 00i is bounded, we have:
Proposition 4. Let B = max i2[[n]] k 00i k1 and U = maxu2U kuk 2 2. Let K be the maximum index of a
nonzero value in v (or |I|). Then 8t 1,W (P (t)) max P2P W (P ) O(BUt ). Moreover, for each user, an iteration costs O(|I| lnK) operations and requires O(K) additional bytes of storage.

heading: 5 Experiments

heading: 5.1 One-sided recommendation
text: We first present experiments on movie recommendation task. We report here our experiments with the Lastfm-2k dataset [9, 47], which contains the music listening histories of 1.9k users. We present in App. F.2 experiments on a larger portion of the Last.fm dataset, and in App. F.3 results using the MovieLens-20m dataset [24]. Our results are qualitatively similar across the three datasets.
We select the top 2500 items most listened to, and estimate preferences with a matrix factorization algorithm using a random sample of 80% of the data. All experiments are carried out with three repetitions for this subsample. The details of the experimental protocol are in App. F.1. Since the goal is to analyze the behavior of the ranking algorithms rather than the quality of the preference estimates, we consider the estimated preferences as ground truth when computing user utilities and comparing methods, following previous work. We compare our welfare approach (welf) to three baselines. The first one is the algorithm of [47] (referred to as Patro et al. in the figures), who consider envy-freeness for user-side fairness and, for item-side fairness, a constraint that the minimum exposure of an item is E|I| where is the trade-off parameter. The other baselines are quality-weighted exposure (qua.-weighted) and equality of exposure (eq. exposure) as described in Sec. 3.
5In our experiments, we initialize with the utilitarian ranking (Proposition 6). 6Formally, S(Pi) = : I ! [[|I|]] is one-to-one, and 8j 2 I, Pij (j) > 0 .
Item-side fairness We first study in isolation item-side fairness, defined as improving the exposure of the worse-off item (producers). To summarize the trade-offs, we show the trade-offs by looking at exposure inequalities as measured by the Gini index (see Sec. 2.2). The results are given in Fig. 2:
• Generating user utility/item inequality trade-offs is performed with our approach by keeping ↵1 = ↵2 = 0 and varying the relative weight of items . Fig. 2a plots some trade-offs achieved by our approach. As expected, the user utility curve degrades as we increase the weight of items, while at the same time the curve of item exposure moves towards the straight line, which corresponds to strict equality of exposure. Fig. 6 in the appendix provides analogous curves for all methods, obtained by varying the weight of the inequality measure. • qua.-weighted yields unfair trade-offs Fig. 2c shows a welf ranking that dominates a qua.-weighted ranking on both user and item curves. This is in line with the discussion of Section 3, qua.-weighted can lead to unfair rankings on utility/item inequality trade-offs. • welf dominates the user utility/item inequality (Gini) trade-offs as seen on Fig. 2b: while all methods have the same total user utility when accepting high item inequality, welf dominates Patro et al., eq. exposure and qua.-weighted as soon as Gini  0.5. Note, however, that the Gini index is only one measure of inequality. When measuring item inequalities with the standard deviation, eq. exposure becomes optimal since our implementation optimizes a trade-off with this measure (see
Fig. 8 in App. F.1). Overall, welf and eq. exposure yield different fair trade-offs.
Two-sided fairness Fig. 3 shows the effect of the user curvature ↵1 2 { 2, 0, 1}, keeping ↵2 = 0.
Fig. 8 in App. F.1 shows similar plots when the item inequality is measured by the standard deviation rather than the Gini index.
• Smaller ↵1 reduce user inequalities at the expense of total user utility, at various levels of item inequality. This is observed by comparing the results for ↵1 2 { 2, 0, 1} in Fig. 3a and Fig. 3b. • welf ↵1 = 0 is better than Patro et al., which can be seen by jointly looking at Fig. 3c, 3d and Fig. 3b which give the cumulative utility at different points of the Lorenz curve (10%, 25% and 100% of the users respectively). We observe that welf ↵1 = 0 is similar to Patro et al. at the 10% and 25% levels, but has higher total utility. Example curves are given in Fig. 3e and 3f which plot welf ↵1 = 0 and Patro et al. at two levels of item inequality. welf ↵1 = 0 obtains similar curves to Patro et al., except that it performs better at the end of the curve. A similar comparison can be made with welf ↵1 = 1 and eq. exposure. • More user inequalities is not necessarily unfair as seen in Fig. 3a comparing welf ↵1 = 0 and Patro et al.. We observe that welf ↵1 = 0 has slightly higher Gini index, but this is not unfair: as seen in Fig. 3e and 3f, this is due to the higher utility at the end of the generalized Lorenz curve of welf, but the worse-off users have similar utilities with welf and Patro et al..

heading: 5.2 Reciprocal recommendation
text: We now present results on a reciprocal recommendation task, where fairness refers to increasing the utility of the worse-off users (this can be done by boosting their exposure at the expense of total utility). Since there is no standard benchmark for reciprocal recommendation, we generate an artificial task based on the Higgs Twitter dataset [15], which contains follower links, and address the task of finding mutual followers (i.e., “matches”). We keep users having at least 20 mutual links, resulting in a subset of 13k users. We build estimated match probabilities using matrix factorization. The experimental protocol is detailed in App. F.4. We also present in App. F.5 additional experiments using the Epinions dataset [49]. The results are qualitatively similar.
Our main baseline is equal utility (eq. utility) defined in Section 3. We also compare to qualityweighted exposure, and equality of exposure as baselines that ignore the reciprocal nature of the task. The results are summarized in Fig. 4:
• Example of trade-offs obtained by varying ↵ are plotted in Fig. 4a. As ↵ decreases, the utility increases for the worse-off users at the expense of better-off users. We note that increasing the utility of worse-off users has a massive cost on total user utility: looking at the exact numbers we observe that ↵ = 5 has more than doubled the cumulative utility of the 10% worse off users compared to ↵ = 1 (120 vs 280), but at the cost of more than 60% of the total utility (17k vs 6.4k).
Fig. 6 in Appendix F.4 contains plots of the trade-offs achieved by the other methods. • qua.-weighted and eq. exposure are dominated by welf on a large range of hyperparameters. An example is given in Fig. 4b, where welf ↵ = 0.5 already dominates some of their models, even though in this region of ↵ there is little focus on worse-off users. More generally, all values of 0.1 for qua.-weighted and eq. exposure lead to rankings with dominated curves. This is expected since they ignore the reciprocal nature of the task. • eq. utility is dominated by welf near strict equality as illustrated in Fig. 4c: for large values of , it is not possible to increase the utility of the worse off users, and eq. utility only drags utility of better-off users down. • welf is more effective at increasing utility of the worse-off users as can be seen in Fig. 4e-g, which plots the total utility as a function of the cumulative utility at different points of the Lorenz curve (10%, 20%, 50% worse-off users respectively). For total utilities larger than 50% of the maximum achievable, welf significantly dominates eq. utility in terms of utility of worse-off users (10% and 25%) at a given level of total utility. welf also dominates eq. utility on the 50% worse-off users (Fig. 4h) in the interesting region where the total utility is within 20% of the maximum. • More inequality is not necessarily unfair As shown in Fig. 4d, we see that for the same utility for the 10% worse-off users, welf models have higher inequalities than eq. utility. As seen before, this higher inequality is due to a higher total utility (and higher total utilities for the 25% worse-off users. The analysis of these Lorenz curves allow us to conclude that these larger inequalities are not due to unfairness. They arise because welf optimizes the utility of the worse-off users at lower cost in terms of average utility than eq. utility.

heading: 6 Related work
text: The question of fairness in rankings originated from independent audits on recommender systems or search engines, which showed that results could exhibit bias against relevant social groups [57, 33, 21, 40, 35] Our work follows the subsequent work on ranking algorithms that promote fairness of exposure for individual or sensitive groups of items [10, 8, 7, 54, 42, 65]. The goal is often to prevent winner-take-all effects, combat popularity bias [1] or promote smaller producers [39, 41]. Section 3 is devoted to the comparison with this type of approaches. Most of these works use a notion of fairness oriented towards items only. Towards two-sided fairness, Wang and Joachims [60] promote user-side fairness using concave functions of user utilities, similarly to us. Other works use equality constraints to define user-side fairness [6, 63]. These three approaches rely on the definitions of item-side fairness discussed in Section 3. Patro et al. [47] generate rankings that are envy-free on the user side, and guarantees the fair min-share for items. This approach is not amenable to controllable trade-offs between user and item utilities.
We are the first to address one-sided and reciprocal recommendation within the same framework. There is less existing work studying the fairness of rankings in the reciprocal setting. Xia et al. [64] aim at equalizing user utility between groups, which suffers from the problems discussed in
Section 3. Jia et al. [31] generate rankings using a welfare function approach, but optimizing only the utility of users being recommended. Paraschakis and Nilsson [46] postprocess rankings to correct for inconsistencies between estimated and declared preferences of users. In contrast, we aim at fair trade-offs between user and item utilities, under the assumption that biases in the preference estimates have been addressed earlier in the recommendation pipeline. Fairness is also studied in the context of ridesharing applications [62, 37, 44], but they address matching rather than ranking problems.
There is growing interest in making the relationship between fairness in machine learning and social choice theory [25, 59, 4, 20, 27, 12, 16, 17], and welfare economics in particular [56, 28, 34, 36, 67]. In line with Hu and Chen [28], who focused on classification and parity penalties, we argue that Pareto-efficiency should be part of fairness assessments. We are the first to propose concave welfare functions and Lorenz dominance to address two-sided fairness in recommendation.

heading: 7 Conclusion
text: We view fairness in rankings as optimizing the distribution of user and item utilities, giving priority to the worse-off. Following this view, we defined fair rankings as having non-dominated generalized Lorenz curves of user and item utilities, and develop a new conceptual and algorithmic framework for fair ranking. The generality of the approach is showcased on several recommendation tasks, including reciprocal recommendation.
The expected positive societal impact of this work is to provide more principled approaches to mediating between several parties on a recommendation platform. Yet, we did not address several questions that are critical for the deployment of our approach. In particular, true user preferences are often not directly available, and we only observe proxies to them, such as clicks or likes. Second, interpersonal comparisons of utilities are critical in this work. It is thus necessary to make sure that the proxies we choose lead to meaningful comparisons of utilities between users. Third, estimating preferences or their proxies is itself not trivial in recommendation because of partial observability. The true fairness of our approach is bound to a careful analysis of (at least) these additional steps.
Acknowledgments and Disclosure of Funding
We thank David Lopez-Paz, Jérôme Lang, as well as the anonymous NeurIPS reviewers for their constructive feedback on early versions of the paper.

Review summaries:
The authors study fairness in recommendation lists, where fairness is considered on both the part of consumers / users, as well as producers / items. They define fairness as a combination of Pareto efficiency and equity given that total level of utility, and note that non-dominated Lorenz curves satisfy their definition of fairness. They demonstrate that their method can be efficiently computed and show that it does well on real-world datasets. 

The authors of this work study fairness in two-sided platforms that utilize ranking as a mechanism for improve experience and utility of users and “items” (that can also be users). They introduce a new framework using the notion of Lorenz dominance through equity and efficiency. The work also contributes a novel algorithm (based on Frank-Wolfe) and show experimental evidence for its performance.

This paper proposes a new ranking framework that concerns the fairness of all parties (i.e., users and items) participating in recommender systems. Inspired by techniques used in welfare economics, the authors formulate a convex optimization that yields Pareto-efficient and equitable (within each parties) utilities. To demonstrate the superiority over existing methods, they consider some special cases where the proposed approach is shown to achieve better utilities than the baseline methods. They provide an efficient implementation based on the Frank-Wolfe algorithm, together with theoretical results on tractability and convergence.