Two-sided fairness in rankings via Lorenz dominance
Authors: Virginie Do
Sam Corbett-Davies
Jamal Atif
Nicolas Usunier
Venue: NeurIPS 2021 Poster (2021)
Keywords: fairness
ranking
recommendation
welfare

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.

Two-sided fairness in rankings via Lorenz dominance
Virginie D Sam Corbett-Davies' Jamal Atif", Nicolas Usunier'
Facebook AI
LLAMSAD,, Université PSL., Université Paris Dauphine, CNRS, France virginiedo@fb.. com, scd@fb. com, jamal. at attishhuppine, psl. usunierdfb.cmm com
Abstract
We consider the problem generating rankings that are fair towards both users and item producers in recommender systems. We address both usual recommendation (e.g., music or movies) and reciprocal recommendation (e.g., dating). Following concepts of distributive justice in welfare economics, 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 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 fairness constraints, our approach always produces fair rankings. Our experiments also show that it increases the utility of the worse-off lower costs in terms of overall utility.
Introduction
Recommender systems have growing impact on the information we see and on our life opportunities, as they help us browse news articles, find 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 's perspective, the recommendations also have an impact on the recommended "items". News outlets rely exposure to generate revenue, finding a job depends on which recruiter gets to see our resume, and the effectiveness 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 fairness in rankings is the problem of generating personalized recommendations by fairly mediating between the interests of users and items. It involves complex multidimensional trade-off. Fairness towards item producers requires boosting the exposure of small producers (c.g., to avoid winner-take-all effects and popularity biases [I] 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), again at the expense of average user utility. The goal of this paper is to provide 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 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 "tradc-off's between utility and faireess" 65. 4l obtained by relaxing the faireess 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 uilitt/inequality trade-off not necessarily 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 (NcurIPS 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 new framework for two-sided faimness 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 economies [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 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 given 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 specific trade-off depends on the application.
From 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 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. 77 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-offss 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 B and present ranking algorithm in Section 4 Our experiments are
described in Section 5 and the related work is discussed in Section 6
2 Two-sided fairness via Lorenz dominance
2.1 Formal framework
Terminology and notation. We identify an item with its producer, so that "item utility" means "item producer's 's utility". The main paper focuses on fairness towards individual users and items. We describe in Appendix the extension of our approach to sensitive groups of users or items. [X| denotes the cardinal of the set X. Given n E N. we denote by [m]] = {l..... n). The set of users A is identified with {1,.., .... [ and the set of items I is identified with { + I....n where n = W + [Z] For (1.5) E N x I, we denote by pij the value of item j to user i.
A (deterministic) ranking o I + [[ is one-to-one mapping from items j to their rank a()). Following 544, 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 ý is recommended to at rank k. We denote by P the set of ranking tensors.

---

12:00
17303
ubiitariann
#1/02)0-1000000
17500
1503)
welf au-2
LElitarian (welf s=1)
welf 21002/0m2200
Cum. exposure
weighted R-0.5
12500
qua wwightedd fw0.5
1000
30000
1350
cum:
7300
2200
5000
1009
2500
75
1800
1250
1500
1750
0
1000
1500
2000
2500
0
25.00
3000
1900
10000 22000
users
ttems
users
Figure 1: Generalized Lorenz curves for usual (left) and reciprocal (right) recommendation.
Utilities of users and items are defined through a position-basede model, as in previous work 54
Let E R7lz where 2k is the exposure weight at rank k. We assume that lower ranks receive more exposure, that vk E [|z] II, u Z U of Given user and ranking d, the user-side utility of is the sum of the MayS weighted by the exposure weight of their rank (j): u,(o,) = Σjer Va, (P)le- Given an item j. the teem-side utility of j the sum over users of the exposure of rankings, written in matrix form
These definitions extend stochastic rankings by taking the expectation
user-side utility: Us (P) = Σ
PigPigo JET
item-side utility (exposure): uj(P) EEPp EN
We denote by u P) (w: ()) the utility profile for P, and by U (P) P P) the set of feasible profiles. For u E U. uN = (u))eN and uy = (u)kez denote the utility profiles users and items respectively.
Two-sided fairness in rankings. practice, values of Pay 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 to compute the ranking tensor given já, 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 users. Thus, accounting for both users' and items' utilities in the recommendations is global inference problem.
More general item utilities We consider exposure as the item-side utility follow prior work and for simplicity. Our framework and algorithm readily applies in more general case of (wo-sided preferences, where items also have preferences over users (for instance, hiring, job seekers have preferences over which recruiters they are recommended to). Denoting Pij the value of user i to item j. the item side-utility then uy Ey
iEN
2.2 Lorenz efficiency and the welfare function approach
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()))= be the sorted values in from smallest to largest, i.c., U(1) .... S U(n), then the generalized Lorenz curve plots (U:),= where U; U(1) +... + U(y). To assess the fairness of trade-offs, rely on the following dominance relations on utility profiles:
Pareto-dominance >p. u > > (Vi E [n], u, 2 ul and E [n]] u > v())
Lorenz-dominance Then u > u' = U>p U' U'.
We write 11. for non-strict Lorenz dominance (i.c., Vi,U, U/). Notice that Pareto-dominance implies Looren--ommnance.. Our notion of fairness, which we call Lorenz efficiency, states that a ranking is fair if the utility profiles for users and for items not jointly Lorenz-dominated:
We use user-independent for simplicity. Considering user-dependent weights is straightforward.
We consider P3 vector in the formula, that P.y E1 PELUE.

---

Definition 1 (Lorenz efficiency), A utility profile u E U is Lorenz-efficient if there is no u' E u such that either (uz Σt. uI and u'y >1. uN) or (u'y Σt. uN and uzz >1. Ur).
We consider that breen-ddmmnated profiles are undesirable (and unfair) because the utility of worse- off 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. ! 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.
fundamental result from cardinal welfare economics is that concave welfare functions of utility profiles order profiles according to Lorenz dominance [ [ The choice of the welfare function specifies which (fair) trade-off desirable 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,
x log(z)
if a > 0 a = 0 -x
Vu E IR= Wo(u) = (1 () 2)
Σ
bu, + +>> 02) with (x)
ENN
JEI
if a < 0
Inference is carried out by maximizing Wo (an efficient algorithm is proposed in Section
(ranking procedure)
pa E argmax (e()(P))
(1)
PEP
The motivation for the specific choice of &i is that it appears in scale invariant welfare functions 44 but other families can be used as long as the functions are increasing and concave. Monotonicity implies that maxima of Wa are Pareto- efficient. For α₁ < 1 and a2 < 1, We is strictly concave. Then, We 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. (left): For item fairness we obtain more item equality by using 0n incrasing À (see blue solid vs orange dashed curve). The parameter 0r 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 θ {(), an, a2) E 1) x (=),,1)²). For every O Wo 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
In Wo, [0, 1] controls the relative weight of users and items.
(here, 0n 0.5) and
(1,
Proposition 1. v0 0, E argmaxWo(u(()), P* is Lorenz-efficient
PEP
Relationship to inequality measures A well-known measure of inequality is the Gini index, defined as 1 2 x 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:
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. 2 we show that as 01, 02 -00, utility profiles tend to leximin-optimal solutions [3) Leximin optimality corresponds to increasing the utility of the worst-off users/items one a time, similarly to lexical order. In App. O present 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.
P Wo(u) -o if 0 and 3i, u, 0. In practice, we (e n, a) for n > O avoid this case.

---

2.3 Extension to reciprocal recommendation
In reciprocal recommendation problems such as dating. the users are also items. The notion of faireess simplifies to increasing the utilityy 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 V = I and [-]- 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 Mij the mutual preference value between and j. and our examples follow the common assumption that Paj = Mgj (see e.g., (5).. For instance, when recommending CVs to recruiters, Mij 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 recommended to
item siem-side utility recommendde j)
(two-sided) utility
(P)
Σ Pig jEI
Us (P(P)
Σ Mag Pag Pacu JEN
uy (P) (P( (P)
With this definition of two-sided utility, our previous framework can be readily applied using W I. A (two-sided) utility profile u E 24 is Loreng-efficient if there is no u' E Ul such that u' >1, u. The welfare function simplifies to (w( = Σ (lu; (x), and Proposition I also holds true in this setting: maximizing the welfare function always yields Lorenz-efficient rankings.
Fig. M (right) illustrates how decreasing a 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.
3 Comparison to utility/inequality trade-off approaches
As stated in the introduction, leading approaches to fairness in ranking are based on utility/inequaiity trade-off's. 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.
3.1 Objective functions
One-sided recommendation In one-sided recommendation, the leading approach is to define exposure-based criteria for item fairness (54 Z7. The first criterion, equality of exposure, aims at equalizing exposure across items. The second one, quality-weighted exposure which is advocated by many authors, defines the quality of an item as the sum of user values q Eien jaj 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 [|el] the total exposure and by Q = ΣSEz Zjez Oj the total quality:
exposure
Fqua
Σ u,- BV Dqua (u) with Dewa iEN
71
1
Σ
Ug
gj
Q
F
jeI
equality of exposure
Fø(u)= = =I u - 3VD(U)
with D(u) =
1
Ug
Σ
uy
2
iEN
JEI
JEi
Some authors use D'(u)= Eu.her Mi instead of Deua
55
Dqua and D' have
qualitatively the same behavior. We propose D (u) as computationally efficient alternative to D', since it involves only a linear number of terms and / Dque is convex and differentiable except on 0.
'We use here the terminology of 68 This criterion has also been called "disparate treatment" 54
"merit-base based fairness" [55 and "equity of attention"
5

---

Reciprocal recommendation For reciprocal recommendation, we consider as competing approach trade-off between total (two-sided) utility and inequality of utilities, as measured by the standard deviation:
equality of utility
Ps(u) = Σ u -v-B/D((u
with D(u)
Σ JEZz
uyy
T
VEN
JEZ
3.2 Inequity and inefficiency of some of the previous approaches
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 O quality-weighted exposure leads the undesirable behavior of decreasing user utility while increasing inequalities of exposure hetween items. This is formalized by the proposition below, which uses the following notation: for 0 θ, let u argmax e ((u). and for 3 > O, let Ug argmax 13
uell
uel
Proposition The following claims hold irrespective of the choice of qua E L
For every d N., and every N E N., there is one-sided recommendation problem, with d items and (d + 1) users, such that 40 E O, we have:
Σier Eue uuu.s EieN up
5
(33 > 0, uy L uus and ut L us 2
and
lim 8-+00
6
Second, in reciprocal recommendation, striving for pure equality can even lead to 0 utility for every user, that of the worst-off user. More precisely, show that in welfare approach with any choice of parameter E O there exists 3 > 0 such that equality of utility has lower utility for every user, eventually leading to O utility for everyone in the limit 3 oo.
cases, compared the
Proposition 3. For 8 >> O, let Us argmax wel (T)) The claim below holds irrespective of the choice of u . E EUg. Let
There is a reciprocal recommendation task with n users such that:
vO O u" 38 0: Wi [m].
u .q.8
and
lim
eq.3 =0 0.
Proofs and additional results All proofs deferred to App. D where we provide several addi- tional results regarding the use of quality-weighted exposure and equality of exposure in reciprocal recommendation: We show in Prop. that there cases where both approaches lead profiles with Lorenz-dominate curves, and significantly lower total user utility than the welfare approach for any choice of the parameters.
utility
4 Efficient inference of fair rankings with the Frank- Wolfe algorithm
We now present our inference algorithm for ( Appendix B contains the proofs of this section and describes similar approach for the objective functions of the previous section. From an abstract perspective, the goal is to find maximum P such that:
P E argmaxx (P) with W(P) = Σ PEP
Mig (Pa + P3)0)
where for every i, D; R., + R is concave increasing, Mig and is vector of non- non-negative non-increasing values. Since W is concave and P defined by equality constraints, the problem above is a convex optimization problem. However, this is global optimization problem over the rankings of all users, so naive approach would require 2 parameters and ||A|[[ linear constraints. The same problem arises with the penalties of previous work. In the literature, authors either considered applying the nem-fairness constraints each ranking individually [54 Kl. which leads to inefficiencies with our definition utility (see Appendix H). or resort to heuristics to compute the rankings by one without guarantees on the trade-offs that are achieved 42 7
Our approach based on the Frank- Wolfe algorithm [8], which was previously used in machine
learning in e.g., structured output prediction or low-rank matrix completion 30 but to the best of

---

6013
6003
sum usee Whitt
011
09.02
130000
129
905
On 0rrdir ft
2000
espesurs
vel si-12-0
que wongghtdd
322
066
700
1396 1766
1996
706 00' 700 1996
17ee 1906
03 61
05
36
10905
(tem inequality (Gimi indea)
(a) Examples of generalized Lorenz curves achieved by welf. (b) Summary of trade-offs (c) Dominated curve
Figure 2: Summary of results on Lastfm-2k, focusing on the user utility/item inequality trade-off.
knowledge not for ranking. Denoting (X EGi XijoYiyk the dot product between tensors, the algorithm creates iterates p(() by first computing argmaxpep (P (VW(P()) and then updating p(t) (1 (0) + xt) with 7(() 242
| Starting from initial solution the algorithm always stays in the feasible region without any additional projection step. Our main contribution of this section is to show that argmaXpep (PI VW (P(()))) can be computed efficiently, requiring only one sort operation per user after computing the utilities. In the result below, for ranking tensor P and user i, we denote by G(P.) the support of P. in ranking space 5
Theorem 1.
Let Pi5 = 8 (u:((()))) (u,((((())) pge-- Let P such that:
WEW, Vo, G(P.): 6.0) <.,'") = jug Pay. Then P argmax(( VW VP(O))).. PEP
Moreover, it produces compact representation of the stochastic ranking 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 Trank-Wolfe algorithm [K]. assuming each &" is bounded, we have:
Proposition Let B = max %l and U = max | 1|g- Let K be the maximum index of a uell
iEIn|
nonzero value in v (or (I). Then Vt 2 1, (P(())
max W(P) O ((B)). Moreover, for each PEP
user, an iteration costs O( In K) operations and requires ((K) additional bytes of storage.
5
Experiments
5.1 One-sided recommendation
We first present experiments on movie recommendation task. We report here our experiments with the Lastfm-2k dataset 99, 47), which contains the music listening histories of 1.9k users. We present in App. F2 experiments on a larger portion of the Last.fm dataset, and App. results using the
MovieLens-200 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 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.T Since the goal is to analyze the behavior of the ranking algorithms rather than the quality of the preference estimates, consider the estimated preferences as ground truth when computing user utilities and comparing methods, following previous work. We compare our welfare approach (weif) to three baselines. The Patro al. the figures), who consider envy-freenes for user-side fairesss and, for item-side fairness, constraint that the minimum exposure of an item is 3 [ where is the trade-off parameter. The other baselines are quality-weighted exposure (qua.-weight weiihee)gh and equality of exposure (eq. exposure) as described in Sec.
first one the algorithm of 47 (referred
'In our experiments, we initialize with utilitarian ranking (Proposition Formally, 6(P)) (o I [[]]]| is one-to-one, and Vjj I, P.jo 0).
7

---

man momeee anneno (SS% exeret
User incquall (Gm
612
samuoe utllyy
340
Kito at rq repecur
030-
103-1)
or
87
03
02
nequainty index
inequaiity iiniidedd
inquaattttyy (Gin
inequaity
(a) User incquality.
(b) Total user utility.
(c) Cumulative utility at
(d) Cumulative utility at
10% worsc-off uscrs.
25% worse-off users.
540
Tatro 9-1.4
300
Netroitill 99-3:25
000
0202
00015
(c) Item incquality = 0.4.
(f) Item incquality z 0.6.
Figure 3: Summary of results on Lastfm-2k for two-sided faimess:: effect of varying an.
Item-side fairness We first study in isolation item-side faimess, defined improving the exposure of the worse-off item (producers). To summarize the trade-off', we show the trade-off's 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 a1 02 0 and varying the relative weight of items A. Fig. plopts 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. ii the appendix provides analogous curves for all methods, obtained by varying the weight 3 of the inequality measure.
qua--weighted yields unfair trade-offss Fig. [2 shows a welf ranking that dominates a qua.-weighted ranking on both user and item curves. This line with the discussion of Section B qua qui-hhighttdd can lead to unfair rankings on utility/item inequality trade-offs.
welf dominates the user utility/item inequality (Gini) trade-off's as seen on Fig. 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 incqualities with the standard deviation, eq. exposure becomes optimal since our implementation optimizes a trade-off with this measure (see Fig. 8 in App. Overall, welf and eq. exposure yield different fair trade-offs.
while all
Two-sided fairness Fig. 3 shows the effect of the user curvature on E (-2, 0, 1), keeping 0:2 = 0. Fig. R in App. F.T shows similar plots when the item inequality is measured by the standard deviation rather than the Gini index.
Smaller 0n reduce user inequalities the expense of total user utility, at various levels of item inequality. This is observed by comparing the results for 0n E (-2, 0, }} in Fig. Bal and Fig. 3b welf ag 0 is better than Patro et al., which be seen by jointly looking 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 a1 = 0 is similar to Patro al. at the 10% and 25% levels, but has higher total utility. Example curves are given in Fig. 3e and 3f which plot welf 01 0 and Patro al. at two levels of item inequality. welf on 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 welfa; a 1 and eq. exposure.
More user inequalities is not necessarily unfair as seen in Fig. 3a comparing welf a1 = 0 and Patro et al.. We observe that welf a = 0 has slightly higher Gini index, but this is not unfair: as seen in Fig. 3ejand 31 this is due to the higher utility at the end of the generalized Lorenz curve of welf, but the wofse-off users have similar utilities with welf and Patro al..
8

---

5.2 Reciprocal recommendation
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 the Higgs Twitter dataset [13], 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 subset of 13k users. We build estimated match probabilities using matrix factorization. The experimental protocol is detailed in App. I:4 We also present in App. F.5 additional experiments
using the Epinions dataset 49 The results are qualitatively similar.
We also compare to quality- weighted exposure, and equality of exposure as baselines that ignore the reciprocal nature of the task.
Our main baseline is equal utility (eq. utility) defined in Section
The results are summarized in Fig. !
Example of trade-off's obtained by varying are plotted in Fig. Fa. As a 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 massive cost on total user utility: looking at the exact numbers we observe that a = -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. c in Appendix F.4 contains plots of the trade-offs achieved by the other methods. qua.-weighted and eq. exposure
dominated by welf large range of hyperparameters. An example is given in Fig. Ap, where welf a = 0.5 already dominates some of their models, even though in this region of there is little foeus worse-off users. More generally, all values of 3 2 0.1 for -wiihhe 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. 4e: for large values of B, it not possible increase the utility of the worse off users, and eq. utility only drags utility of better-off users down.
welf'n is more effective at increasing utility of the worse-off users as can be seen in Fig. Frg which plots the total utility as 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. Eh) in the interesting region where the total utility is within 20% of the maximum.
More inequality is not necessarily unfair As shown in Fig. I.. 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.
6 Related work
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 Our work follows the subsequent work ranking algorithms that promote
57
33
21
40 351
fairness of exposure for individual or sensitive groups of items [TC g 54
42 65). The goal is often
to prevent winner-take-all effects, combat popularity bias I 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 faimess 6 53 These three approaches rely on the definitions of itde-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 the reciprocal setting. Xia al. 64 aim at equalizing user utility between groups, which suffers from the problems discussed in

---

400
wegthed
.502
s--27
euponure (Pnd
LtB 9-33
CUr
2090
100
200
1509
Example trade-offs achieved by welf.
welf dominates (c) welf dominates eq. utility near strict equality.
exposure-basee methods.
zum ubity
12:4
300
1230
300
C1 (88)
Ad
Enequality
utliity
(d) Total utility vs inequal- (e) Total utility vs utility of 10% worse-off users.
(I) Total utility vs utility of 25% worse-off users.
(g) Total utility vs utility of 50% worse-off users.
ity.
Figure Results on the twitter dataset.
Section Jia et al. 31 generate rankings using a welfare function approach, but optimizing only the utility users being recommended. Paraschakis and Nilsson 4d postprocess rankings to correct for inconsistencies between estimated and declared preferences of users. In contrast, trade-offss 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
aim at fair
62
37
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
20
27
16 17. and welfare economics particular [56 28
kel 36
In line with Hu and Chen 2S
who focused on classification and parity penalties, 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 faimess in recommendation.
7 Conclusion
We view fairness in rankings as optimizing the distribution of user and item utilities, giving priority 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 critical for the deployment of our approach. In particular, true preferences 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. is thus necessary make sure that the proxies we choose lead to meaningful comparisons of utilities between users. Third, estimating preferences 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.
10

---

References
[1] H. Abdollahpouri, M. Mansoury, R. Burke, and B. Mobasher. The unfairness of popularity bias in recommendation. arXiv preprint arXiv: 13286, 2019.
[2] S. Agarwal. Surrogate regret bounds for bipartite ranking via strongly proper losses. The Journal of Machine Learning Research, 15(1) 2014.
[3] A. B. Atkinson. On the measurement of inequality. Journal of economic theory, 2(3):244-263, 1970.
[4] M.-F. Balcan, T. Dick, R. Noothigattu, and A. D. Procaccia. Envy-firee classificatoion, arXiv preprint 1rXiv:/809.087000 2018.
[5] L. Bartlett, M. Jordan, and J. D. McAuliffe, Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):188-55, 2006.
[6] K. Basu, C. DiCiccio, H. Logan, and N. E. Karoui. A framework for faimess in two-sided marketplaces. arXiv preprini arXiv:2006. 12756, 2020.
[7] A. J. Biega, K. P. Gummadi, and G. Weikum. Equity of attention: Amortizing individual fairness in rankings. In The s international acm sigir conference research & development in information retrieval, pages 405-414, 2018.
[8] R. Burke. Multisided faimesss for recommendation. arXiv preprint arXiv: 170..0077000093, 2017.
[9] Cantador, P. Brusilovsky, and Kuflik. 2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011). In Proceedings of the 5th ACM conference on Recommender systems, RecSys 2011, New York, NY, USA, 2011. ACM.
[10] L. Celis, D. Straszak, and N. K. Vishnoi. Ranking with fairness constraints. arXiv preprint arXiv: 1704.06800 2017.
[11] O. Celma. Music Recommendation and Discovery in the Long Tail. Springer, 2010.
[12] A. Chakraborty, G. K. Patro, N. Ganguly, K. P. Gummadi, and P. Loiseau. Equality of voice: Towards fair representation in crowdsourced top-k recommendations. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 129-138. ACM, 2019,
[13] K. L. Clarkson. Coresets, sparse greedy approximation, and the frank-wolfe algorithm. ACM Transactions on Algorithms (TALG), 6-4):1-30, 2010.
[14] D. Cossock and T. Zhang. Statistical analysis of bayes optimal subset ranking. IEEE Transac- tions on Information Theory, 54(1 54(11):5140-5154: 2008.
[15] M. De Domenico, A. Lima, P. Mougel, and M. Musolesi. The anatomy of a scientific rumor. Scientific reports, 3(1):1-9, 2013.
[16] V. Do. S. Corbett-Davies, Atif, and N. Usunier. Online certification of reference-based fairness for personalized recommender systems. arXiv preprint arXiv:2 /4527, 2021.
[17] J. Finocchiaro, R. Maio, F. Monachou, G. K. Patro, M. Raghavan, A.-A. Stoica, and S. Tsirtsis. Bridging machine learning and mechanism design towards algorithmic faimess. In Proceedings of the 202/ ACM Conference on Fairness, Accountability, and Transparency, pages 489-503, 2021.
[18] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-1 10, 1956.
[19] C. Gini. Measurement of inequality of incomes. The economic journal, 31(1211) 1921.
[20] Gölz, A. Kahng, and A. D. Procaccia. Paradoxes in fair machine learning. Advances in Neural Information Processing Systems (NeurIPS). Forthcoming. 2019.
[21] A. Hannak, G. Soeller, D. Lazer, A. Mislove, and C. Wilson. Measuring price discrimination and steering on e-commerce web sites. In Proceedings of the 2014 conference on internet measurement conference, pages 305-318, 2014.
[22] M. Hardt, F. Price, N. Srebro, et al. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, pages 3315-3323. 2016.
[23] G. H. Hardy, J. E. Littlewood, and G. Pólya. Inequalities. 2nd ed. Cambridge, Engl.: At the University Press. XII, 324 p. (1952)., 1952.

---

[24] F. M. Harper and J. A. Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis). 5(4):1-19, 2015.
[25] H. Heidari, C. Ferrari, K. Gummadi, and A. Krause. Fairness behind a veil of ignorance: A welfare analysis for automated decision making. In Advances in Neural Information Processing Systems, pages 1263- 2263-126, 1276, 2018.
[26] H. Heidari, M. Loi, P. Gummadi, and A. Krause. A moral framework for understanding fair ml through economic models of equality of opportunity, In Proceedings of the Conference Fairness, Accountabilityy and Transparency, pages 181-190, 2019.
[27] S. Hossain, A. Mladenovic, and N. Shah. Designing fairly fair classifiers via economic fairness notions. In Proceedings of The Web Conference 2020, pages 1559-1569, 2020.
[28] L. Hu and Y. Chen. Fair classification and social welfare. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 535-545, 2020.
[29] Y. Hu, Y. Koren, and C. Volinsky. Collaborative filtering for implicit feedback datasets. In 2008 Eighth IEEE International Conference Data Mining, pages 263 272. Ieee, 2008
[30] M. Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning, pages 427-435. PMLR, 2013.
[31] Y. Jia, X. Liu, and W. Xu. When online dating meets nash social welfare: Achieving efficiency and fairness. In Proceedings of the 2018 World Wide Web Conference, pages 429-438, 2018.
[32] C. C. Johnson. Logistic matrix factorization for implicit feedback data. Advances in Neural Information Processing Systems, 27(78):1-9, 2014.
[33] M. Kay, C. Matuszek, and S. A. Munson. Unequal representation and gender stereotypes in image search results for occupations. In Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, pages 3819-3828. ACM, 2015.
[34] J. Kleinberg. J. Ludwig. S. Mullainathan, and A. Rambachan. Algorithmic fairness. In Aea papers and proceedings, volume 108, pages 22-27, 2018.
[35] A. Lambrecht and C. Tucker. Algorithmic bias? an empirical study of apparent gender-based discrimination in the display of stem career ads. Management Science, 65(7):2966-2981, 2019.
[36] M. S. A. Lee, L. Floridi, and J. Singh. Formalising trade-off's beyond algorithmic faimess: lessons from ethical philosophy and welfare economics. Al and Ethics, pages 1-16, 2021.
[37] N. S. Lesmana, X. Zhang, and X. Bei. Balancing efficiency and fairness in on-demand ridesourcing. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[38] D. Lim, J. McAuley, and G. Lanckriet. Top-n recommendation with missing implicit feedback. In Proceedings of the 9th ACM Conference on Recommender Systems, pages 309-312, 2015.
[39] W. Liu, J. Guo, N. Sonboli, R. Burke, and S. Zhang. Personalized fairness-aware re-ranking for microlending. In Proceedings of the 13th ACM Conference on Recommender Systems, pages 467-471, 2019.
[40] R. Mehrotra, A. Anderson, F. Diaz, A. Sharma, H. Wallach, and F. Yilmaz. Auditing search en- gines for differential satisfaction across demographics. In Proceedings of the 26th international conference on World Wide Web companion, pages 626-633, 2017.
[41] R. Mehrotra, J. McInerney, H. Bouchard, M. Lalmas, and F. Diaz. Towards fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recom- mendation systems. In Proceedings of the 27th acm international conference on information and knowledge management. pages 2243-2251, 2018
[42] M. Morik, A. Singh, Hong, and T. Joachims. Controlling fairness and bias in dynamic learning-to-rank. arXiv preprint arXiv:2005. 14713, 2020.
[43] H. Moulin. Fair division and collective welfare. MIT press, 2003.
[44] V. Nanda, P. Xu, K. A. Sankararaman, J. Dickerson, and A. Srinivasan. Balancing the tradeoff between profit and fairness rideshare platforms during high-demand hours. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2210-2217, 2020.
12

---

[45] I. Palomares, C. Porcel, L. Pizzato, I. Guy, and E. Herrera- Viedma. Reciprocal recommender systems: Analysis of state-of-an art literature, challenges and opportunities towards social recom- mendation. Information Fusion, 69: 69:103-127, 2021.
[46] D. Paraschakis and B. J. Nilsson. Matchmaking under faimess constraints: a speed dating case study. In International Workshop on Algorithmic Bias in Search and Recommendation, pages 43-57. Springer, 2020.
[47] G. K. Patro, A. Biswas, N. Ganguly, K. Gummadi, and A. Chakraborty. Fairrec: Two- sided faimesss for personalized recommendations in two-sided platforms. arXiv preprint arXiv:2002. 10764, 2020.
[48] P. Ravikumar, A. Tewari, and E. Yang. On ndeg consistency of listwise ranking methods. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 618-626, JMLR Workshop and Conference Proceedings, 2011.
[49] M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In International semantic Web conference, pages 351-368. Springer, 2003.
[50] E. Roemer and A. Trannoy. Equality of opportunity: Theory and measurement. Journal of Economic Literature, 54(4):1288-1333) 2016.
[51] A. Sen. Equality of what? The Tanner lecture on human values, 1, 1979.
[52] A. F. Shorrocks. The class of additively decomposable inequality measures. Econometrica: Journal of the Econometric Society, pages 613-625, 1980.
[53] A. Shorrocks. Ranking income distributions. Economica, 50(197):3-17, 1983.
[54] A. Singh and T. Joachims. Fairness of exposure in rankings. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2219-2211 2228.
ACM, 2018
[55] A. Singh and T. Joachims. Policy learning for faimess in ranking. In Advances in Neural Information Processing Systems, pages 5427-5437, 2019.
[56] T. Speicher, H. Heidari, N. Grgie-Hlaca, K. P. Gummadi, A. Singla, A. Weller, and M. B. Zafar. A unified approach to quantifying algorithmic unfairness: Measuring individual &group unfairness via inequality indices. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2239-2248. ACM, 2018.
[57] L. Sweeney. Discrimination online ad delivery. Queue, 11(3):0, 2013.
[58] P. D. Thistle. Ranking distributions with generalized lorenz curves. Southern Economic Journal, pages 1-12, 1989.
[59] B. Ustun, Y. Liu, and D. Parkes. Fairness without harm: Decoupled classifiers with preference guarantees. In International Conference Machine Learning, pages 6373-6382, 2019.
[60] L. Wang and T. Joachims. Fairness and diversity for rankings in two-sided markets. arXiv preprint arXiv:2010.014700 2020.
[61] M. Wang, M. Gong, X. Zheng, and K. Zhang. Modeling dynamic missingness of implicit feedback for recommendation. Advances in neural information processing systems, 31:6669, 2018.
[62] O. Wolfson and J. Lin. Fairness versus optimality in ridesharing. In 2017 18th IEEE Interna- tional Conference on Mobile Data Management (MDM), pages 118-123 IEEE, 2017.
[63] Y. Wu, J. Cao, G. Xu, and Y. Tan. Tfrom: A two-sided fairness-aware recommendation model for both customers and providers. arXiv preprint arXiv:2104.090024, 2021.
[64] B. Xia, J. Yin, J. Xu, and Y. Li. We-rec: A fairness- reciprocal recommendation based on walrasian equilibrium. Knowledge-Bil
Systems, 182: 104:17, 2019.
[65] M. Zehlike and C. Castillo. Reducing disparate exposure in ranking: learning to rank approach. In Proceedings of The Web Conference 2020, pages 2849-2855, 2020.
[66] T. Zhang et al. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56-88) 2004
[67] M. Zimmer, C. Glanois, U. Siddique, and P. Weng- Learning fair policies in decentralized cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pages 12967-12978. PMLR, 2021.
13


Reviews:
[{"review_id": "mFDagfdnZLQ", "reviewer": "Reviewer_wTCs", "summary": "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors study a natural consideration in matching problems where you must balance fairness on the part of both the users and advertisers simultaneously.\n\nThe definition of fairness introduced by the authors makes sense in a two-sided market, and they bring up a good parallel to Pareto efficiency. However, Pareto efficiency (and Lorenz domination) can be a relatively weak property in the sense that a Pareto or Lorenz curve with one small \"good part\" may not ever be dominated by any other curve even though those curves are better \"overall\". \n\nI found the paper to be quite dense and notationally heavy, and some results were hard to interpret without the appendix. \n\nAround line 103, the analogies explaining why \\mu_{ij} = \\mu_{ji} in two-sided preferences don't exactly fit (at least not to me). Prospective employers and prospective employees derive different utilities from an interview; in general, people in relationships can derive different utilities as well. \n\nAround line 160, could you please explain the alphas a bit better? It seems like each alpha should be between 0 and 1 in order to get a strictly concave function, and the experiments show a range of alphas -- how did you choose them in asymmetric settings? \n\nI also found the figures in the experimental section a bit hard to interpret. Would it be helpful / informative to plot \"perfectly equitable\" Lorenz curves where applicable to more clearly illustrate domination? \n\n\nMinor comments:\n\n44 and 46: either \"can lead to a decrease in the utility\" or \"can decrease the utility\"\n47: worst-off\n89: users\n91: cardinality\n92: the (i,j)-th\n97: either? stress that this \"either\" is based on previous lines of work; it'll be clear in this paper depending on context\n103: don't understand the analogies. different utilities to each side...suggest something like \n201: of the most satisfied users\n224: qualitatively ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "IgwUyZ79r9", "reviewer": "Reviewer_oh3N", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: To the best of my knowledge, the results & contributions of the study are novel.\n\nQuality: The work has a notable amount of contribution and all of them are supported by theoretical results (with a lot of detailed proofs in Supp. Mat.). Also, the authors provide experimental evaluation.\n\nClarity: On the one hand, the paper is well structured, with a good story line and introduction of all required theoretical definitions, theorems and experimental setup. On the other hand, the authors permanently consider several variants of their setup \"one-sided recommendation\", \"reciprocal recommendation”, \"one-sided preferences”, and \"two-sided preferences\"\n\nFor instance, Line 159 & Line 161: “In our case where there are users and items …” and “In reciprocal recommendation”. This is one among a lot of other lines of examples. Sometimes, it leads to misunderstanding of what is the considered case in this work.\n\nIs it possible to make the work more focused on one single particular setup, while other ones localize in a dedicated place of the paper (e.g., move to discussion)?\n\n[CLARIFIED DURING REBUTTAL PERIOD] Line 283: It is not clear about “O(K) additional bytes for each iteration” (the proof in Appendix did not help). Even \\tilda P is new for each iteration t, but all previous \\tilda P (from steps t-1, t-2, t-3, etc) are not required to keep in memory (Am I right?). So, we can use the same memory for each iteration. \n\n\n[CLARIFIED DURING REBUTTAL PERIOD] Significance: Overall, I appreciate the contribution of the work. However, I believe that it may significantly benefit for practice if it (at least) discusses how the results can be used in paid scenarios. Many ranking (recomm) systems are paid. So, how are these results related to such systems that are quite popular? Usually, every large system needs a monetization implying sponsored ranking / recommendations / suggestions / etc.: e.g., sponsored search, social networks, ecom, crowdsourcing platforms,…\n\nMinor comments:\n-\tLine 130: I did not get “true” applied to “user”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "EKQDIEIH3oG", "reviewer": "Reviewer_WERu", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nS1: The main idea (of employing Lorenz dominance to implement fair utility) is insightful.\nS2: The proposed formulation is elegant: it covers both one-sided and reciprocal recommendation systems.\nS3: Theoretical guarantees of the considered algorithm are provided in Theorems 1 and 2.\n\nWeaknesses:\nW1: Improvement over the considered baselines (particularly for equal_expo and equal_util) seems marginal. This blurs the superiority gained in Section 4 and hence weaken the motivation of using the proposed framework instead of a more simple item-side fairness scheme.\nW2: Comparison with prior two-sided fairness algorithms (such as [41]) are missing. \nW3: \"Tradeoffs\" are unclear in Figure 2 and Figure 3. As described in Section 6, now the left column in Fig. 2 exhibits tradeoff between user and item utilities depending on alpha, but I am not sure this tension still remains when \"alpha_1\" and \"alpha_2\" take different values. It seems that if we take \"alpha_1 = 0.95\" and \"alpha_2 = 0\", then both user and item utilities yield the best curves with no trade-off. Figure 3 only shows aggregated two-sided utilities so tension between two utilities is impossible to see.\n\nThe technical content of this paper appears to be correct.\nThe paper was overall well-written yet would benefit from more proofreading. More precisely:\n- Please remove \"is” from \"is is the value” in line 96 of page 3.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discussed limitations and societal impacts adequetly in conclusion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers were very appreciative of the melding of traditional economic concepts such as Lorenz dominance with the topical problem of two-sided fairness in ranking/matching platforms.  Parallels to Pareto efficiency and other realistic desiderata and concerns were also appreciated.  Some comparisons to baselines/related work seemed marginal or weak.  In a subsequent or final version, I would ask that the authors do indeed make the changes promised during the post-rebuttal discussion (e.g., addition of discussion of sponsored search / other paid settings, all typos/method clarifications, newer results, and so on).  This is a case where the rebuttal and discussion directly and positively influenced the reviewers' (and this AC's) opinion.
Decision: Accept (Poster)