# Two-sided fairness in rankings via Lorenz dominance

Virginie Do1,2, Sam Corbett-Davies1, Jamal Atif2, Nicolas Usunier1
1Facebook AI
2LAMSADE, Université PSL, Université Paris Dauphine, CNRS, France
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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.

##  1 Introduction

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 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.

##  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 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. $|\cal X|$ denotes the cardinal of the set
$\cal X$. Given $n\in\mathbb{N}$, we denote by $[\\![n]\\!]=\\{1,\ldots,n\\}$.
The set of users ${\cal N}$ is identified with $\\{1,...,|{\cal N}|\\}$ and
the set of items ${\cal I}$ is identified with $\\{|{\cal N}|+1,...,n\\}$
where $n=|{\cal N}|+|{\cal I}|$. For $(i,j)\in{\cal N}\times{\cal I}$, we
denote by $\mu_{ij}$ the value of item $j$ to user $i$.

A (deterministic) ranking $\sigma:{\cal I}\to[\\![{|{\cal I}|}]\\!]$ is a one-
to-one mapping from items $j$ to their rank $\sigma(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
$P_{ijk}$ is the probability that $j$ is recommended to $i$ at rank $k$. We
denote by $\mathcal{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\in\mathbb{R}^{{|{\cal I}|}}$, where $v_{k}$
is the exposure weight at rank $k$. We assume that lower ranks receive more
exposure, so that $\forall k\in[\\![{|{\cal I}|}-1]\\!],v_{k}\geq v_{k+1}\geq
0$.111We use a user-independent $v$ for simplicity. Considering user-dependent
weights is straightforward. Given a user $i$ and a ranking $\sigma_{i}$, the
_user-side utility_ of $i$ is the sum of the $\mu_{ij}$s weighted by the
exposure weight of their rank $\sigma_{i}(j)$:
$u_{i}(\sigma_{i})=\sum_{j\in{\cal I}}v_{\sigma_{i}(j)}\mu_{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:222We consider
$P_{ij}$ as a row vector in the formula, so that $P_{ij}v=\sum_{k=1}^{|{\cal
I}|}P_{ijk}v_{k}$.

user-side utility: $\displaystyle\quad u_{i}(P)=\sum_{j\in{\cal
I}}\mu_{ij}P_{ij}v\quad$ item-side utility (exposure): $\displaystyle\quad
u_{j}(P)=\sum_{i\in{\cal N}}P_{ij}v$ (1)

We denote by ${\boldsymbol{u}}(P)=(u_{i}(P))_{i=1}^{n}$ the utility profile
for $P$, and by ${\cal U}=\\{{\boldsymbol{u}}(P):P\in\mathcal{P}\\}$ the set
of feasible profiles. For ${\boldsymbol{u}}\in{\cal U}$,
${{\boldsymbol{u}}}_{{\cal N}}=(u_{i})_{i\in{\cal N}}$ and
${{\boldsymbol{u}}}_{{\cal I}}=(u_{i})_{i\in{\cal I}}$ denote the utility
profiles of users and items respectively.

#### Two-sided fairness in rankings.

In practice, values of $\mu_{ij}$ are not known to the recommender system.
Ranking algorithms use an estimate $\hat{\mu}$ of $\mu$ based on historical
data. We address here the problem of _inference_ : the task is to compute the
ranking tensor given $\hat{\mu}$, 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 $\mu_{ji}$ the value of user $i$ to item $j$,
the item side-utility is then $u_{j}(P)=\smash{\sum\limits_{i\in{\cal
N}}}\mu_{ji}P_{ij}v$.

Figure 1: Generalized Lorenz curves for usual (left) and reciprocal (right)
recommendation.

###  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 ${\boldsymbol{u}}$, let $(u_{(i)})_{i=1}^{n}$ be the
sorted values in ${\boldsymbol{u}}$ from smallest to largest, i.e.,
$u_{(1)}\leq\ldots\leq u_{(n)}$, then the generalized Lorenz curve plots
$(U_{i})_{i=1}^{n}$ where $U_{i}=u_{(1)}+\ldots+u_{(i)}$. To assess the
fairness of trade-offs, we rely on the following dominance relations on
utility profiles:

Pareto-dominance $\succ_{\rm P}$. ${\boldsymbol{u}}\succ_{\rm
P}{\boldsymbol{u^{\prime}}}\iff(\forall i\in[\\![n]\\!],u_{i}\geq
u^{\prime}_{i}$ and $\exists i\in[\\![n]\\!],u_{i}>u^{\prime}_{i})$.

Lorenz-dominance $\succ_{\rm L}$. Then ${\boldsymbol{u}}\succ_{\rm
L}{\boldsymbol{u^{\prime}}}\iff{\boldsymbol{U}}\succ_{\rm
P}{\boldsymbol{U^{\prime}}}$.

We write $\succeq_{\rm L}$ for non-strict Lorenz dominance (i.e., $\forall
i,U_{i}\geq U^{\prime}_{i}$). 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:

######  Definition 1 (Lorenz efficiency).

A utility profile ${\boldsymbol{u}}\in{\cal U}$ is _Lorenz-efficient_ if there
is no ${\boldsymbol{u^{\prime}}}\in{\cal U}$ such that either
($\boldsymbol{u}^{\prime}_{{\cal I}}\succeq_{\rm L}{{\boldsymbol{u}}}_{{\cal
I}}$ and $\boldsymbol{u}^{\prime}_{{\cal N}}\succ_{\rm
L}{{\boldsymbol{u}}}_{{\cal N}}$) or ($\boldsymbol{u}^{\prime}_{{\cal
N}}\succeq_{\rm L}{{\boldsymbol{u}}}_{{\cal N}}$ and
$\boldsymbol{u}^{\prime}_{{\cal I}}\succ_{\rm L}{{\boldsymbol{u}}}_{{\cal
I}}$).

We consider that Lorenz-dominated 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. 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
$\theta=(\lambda,\alpha_{1},\alpha_{2})$:333$W_{\theta}({\boldsymbol{u}})=-\infty$
if $\alpha\leq 0$ and $\exists i,u_{i}=0$. In practice, we use
$\psi(x+\eta,\alpha)$ for $\eta>0$ to avoid this case.

(2)

Inference is carried out by maximizing $W_{\theta}$ (an efficient algorithm is
proposed in Section 4):

(ranking procedure) $\displaystyle
P^{*}\in\smash{\operatorname*{argmax}\limits_{P\in\mathcal{P}}}~{}W_{\theta}({\boldsymbol{u}}(P))\vphantom{\sum}$
(3)

In $W_{\theta}$, $\lambda\in[0,1]$ controls the relative weight of users and
items. The motivation for the specific choice of $\psi$ 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_{\theta}$ are Pareto-efficient. For $\alpha_{1}<1$ and
$\alpha_{2}<1$, $W_{\theta}$ is strictly concave. Then, $W_{\theta}$ 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
$\alpha_{1}<1$ (here, $\alpha_{1}=0.5$) and incrasing $\lambda$ (see blue
solid vs orange dashed curve). The parameter $\alpha_{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
$\Theta=\\{(\lambda,\alpha_{1},\alpha_{2})\in\\!(0,1)\times(\\!{-}\infty,\\!1)^{2}\\}$.
For every $\theta\in\Theta,W_{\theta}$ 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.

$\forall\theta\in\Theta,\forall
P^{*}\in\smash{\operatorname*{argmax}\limits_{P\in\mathcal{P}}}W_{\theta}({\boldsymbol{u}}(P))$,
$P^{*}$ is Lorenz-efficient.

#### Relationship to inequality measures

A well-known measure of inequality is the Gini index, defined as
$1-2\times{\rm AULC}$, where ${\rm 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 $\alpha_{1},\alpha_{2}\rightarrow-\infty,$
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.

###  2.3 Extension to reciprocal recommendation

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 ${\cal N}={\cal
I}$ and $n=|{\cal 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 $\mu_{ij}$ the mutual
preference value between $i$ and $j$, and our examples follow the common
assumption that $\mu_{ij}=\mu_{ji}$ (see e.g., [45]). For instance, when
recommending CVs to recruiters, $\mu_{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:

$\displaystyle\overbrace{\vphantom{\sum}\overline{u}_{i}(P)=\sum_{j\in{\cal
I}}\mu_{ij}P_{ij}v}^{\begin{subarray}{c}\text{user-side utility}\\\
\text{\emph{($j$ recommended to $i$)}}\end{subarray}}$
$\displaystyle\overbrace{\vphantom{\sum}\overline{v}_{i}(P)=\sum_{j\in{\cal
N}}\mu_{ij}P_{ji}v}^{\begin{subarray}{c}\text{item-side utility}\\\
\text{\emph{($i$ recommended to $j$)}}\end{subarray}}$
$\displaystyle\overbrace{u_{i}(P)=\overline{u}_{i}(P)+\overline{v}_{i}(P)}^{\text{(two-
sided) utility}}$ (4)

With this definition of two-sided utility, our previous framework can be
readily applied using ${\cal N}={\cal I}$. A (two-sided) utility profile
${\boldsymbol{u}}\in{\cal U}$ is _Lorenz-efficient_ if there is no
${\boldsymbol{u^{\prime}}}\in{\cal U}$ such that
${\boldsymbol{u^{\prime}}}\succ_{\rm L}{\boldsymbol{u}}$. The welfare function
simplifies to $W_{\theta}({\boldsymbol{u}})=\sum_{i=1}^{n}\psi(u_{i},\alpha)$,
and Proposition 1 also holds true in this setting: maximizing the welfare
function always yields Lorenz-efficient rankings.

Fig. 1 (right) illustrates how decreasing $\alpha$ 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/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.

###  3.1 Objective functions

#### 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 exposure_ 444We use here the terminology of [63]. This
criterion has also been called “disparate treatment” [54], “merit-based
fairness” [55] and “equity of attention” [7]., which is advocated by many
authors, defines the _quality_ of an item as the sum of user values
$q_{j}=\sum_{i\in{\cal N}}\mu_{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={|{\cal N}|}\left\lVert v\right\rVert_{1}$ the total exposure
and by $Q=\sum_{j\in{\cal I}}q_{j}$ the total quality:

$\displaystyle\displaystyle\begin{subarray}{c}\text{\emph{\normalsize quality-
weighted }}\\\ \text{\normalsize\emph{exposure}}\end{subarray}~{}~{}F^{\rm
qua}_{\beta}({\boldsymbol{u}})=\sum_{i\in{\cal
N}}u_{i}-\beta\sqrt{D^{qua}({\boldsymbol{u}})}\text{~{}~{}with~{}~{}}D^{qua}({\boldsymbol{u}})=\frac{1}{n}\sum\limits_{j\in{\cal
I}}\Big{(}u_{j}-\frac{q_{j}E}{Q}\Big{)}^{2}.$
$\displaystyle\begin{subarray}{c}\text{\emph{\normalsize equality of }}\\\
\text{\normalsize\emph{exposure}}\end{subarray}$ $\displaystyle
F_{\beta}({\boldsymbol{u}})$ $\displaystyle=\sum_{i\in{\cal
N}}u_{i}-\beta\sqrt{D({\boldsymbol{u}})}$
$\displaystyle\text{with~{}~{}}D({\boldsymbol{u}})=\sum_{j\in{\cal
I}}\frac{1}{n}\Big{(}u_{j}-\frac{1}{{|{\cal I}|}}\sum_{j^{\prime}\in{\cal
I}}u_{j^{\prime}}\Big{)}^{2}.$ (5)

Some authors use $D^{\prime}({\boldsymbol{u}})=\sum_{(j,j^{\prime})\in{\cal
I}^{2}}|\frac{u_{j}}{q_{j}}-\frac{u_{j^{\prime}}}{q_{j^{\prime}}}|$ instead of
$\sqrt{D^{qua}}$ [55, 42, 6]. $D^{qua}$ and $D^{\prime}$ have qualitatively
the same behavior. We propose $D^{qua}({\boldsymbol{u}})$ as a computationally
efficient alternative to $D^{\prime}$, since it involves only a linear number
of terms and $\sqrt{D^{qua}}$ is convex and differentiable except on $0$.

#### 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:

$\displaystyle\begin{subarray}{c}\text{\emph{\normalsize equality of }}\\\
\text{\normalsize\emph{utility}}\end{subarray}$ $\displaystyle
F_{\beta}({\boldsymbol{u}})$ $\displaystyle=\sum_{i\in{\cal
N}}u_{i}-\beta\sqrt{D({\boldsymbol{u}})}$
$\displaystyle\text{with~{}~{}}D({\boldsymbol{u}})=\sum_{j\in{\cal
I}}\frac{1}{n}\Big{(}u_{j}-\frac{1}{{|{\cal I}|}}\sum_{j^{\prime}\in{\cal
I}}u_{j^{\prime}}\Big{)}^{2}.$ (6)

###  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 $\theta\in\Theta$,
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
$\theta\in\Theta$, let
${\boldsymbol{u}}^{\theta}=\smash{\operatorname*{argmax}\limits_{{\boldsymbol{u}}\in{\cal
U}}}W_{\theta}({\boldsymbol{u}})$, and for $\beta>0$, let ${\cal U}^{\rm
qua}_{\beta}=\smash{\operatorname*{argmax}\limits_{{\boldsymbol{u}}\in{\cal
U}}}~{}F^{\rm qua}_{\beta}({\boldsymbol{u}})$.

######  Proposition 2.

The following claims hold irrespective of the choice of
${\boldsymbol{u}}^{{\rm qua},\beta}\in{\cal U}^{\rm qua}_{\beta}$.

For every $d\in\mathbb{N}_{*}$ and every $N\in\mathbb{N}_{*}$, there is a one-
sided recommendation problem, with $d+1$ items and $N(d+1)$ users, such that
$\forall\theta\in\Theta$, we have:

$\displaystyle\big{(}\exists\beta>0,{\boldsymbol{u}}^{\theta}_{\cal
N}\succ_{\rm L}{\boldsymbol{u}}^{{\rm qua},\beta}_{\cal
N}\text{~{}and~{}}{\boldsymbol{u}}^{\theta}_{\cal I}\succ_{\rm
L}{\boldsymbol{u}}^{{\rm qua},\beta}_{\cal I}\big{)}$ and
$\displaystyle\lim_{\beta\rightarrow\infty}\frac{\sum_{i\in{\cal
N}}u_{i}^{{\rm qua},\beta}}{\sum_{i\in{\cal
N}}u_{i}^{\theta}}\xrightarrow[d\to\infty]{}\frac{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 $\theta\in\Theta$, there exists $\beta>0$ such that
equality of utility has lower utility for every user, eventually leading to 0
utility for everyone in the limit $\beta\rightarrow\infty$.

######  Proposition 3.

For $\beta>0$, let ${\cal U}^{\rm
eq}_{\beta}=\operatorname*{argmax}_{{\boldsymbol{u}}\in{\cal
U}}F_{\beta}({\boldsymbol{u}})$. The claim below holds irrespective of the
choice of ${\boldsymbol{u}}^{{\rm eq},\beta}\in{\cal U}^{\rm eq}_{\beta}$. Let
$n\geq 5$. There is a reciprocal recommendation task with $n$ users such that:

$\displaystyle\forall\theta\in\Theta,{\boldsymbol{u}}^{\theta},\exists\beta>0:~{}~{}\forall
i\in[\\![n]\\!],u_{i}^{\theta}>u_{i}^{{\rm eq},\beta}$ and
$\displaystyle\smash{\lim_{\beta\rightarrow\infty}}\smash{\sum\limits_{i\in{\cal
N}}}u_{i}^{{\rm eq},\beta}=0.$ (7)

#### 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.

##  4 Efficient inference of fair rankings with the Frank-Wolfe algorithm

We now present our inference algorithm for (3). 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^{*}\in\operatorname*{argmax}_{P\in\mathcal{P}}W(P)\text{~{}~{}~{}with~{}~{}~{}}W(P)=\sum_{i=1}^{n}\Phi_{i}\\!\bigg{(}\sum_{j=1}^{n}\mu_{ij}(P_{ij}+P_{ji})v\bigg{)}$
(8)

where for every $i$, $\Phi_{i}:\mathbb{R}_{+}\rightarrow\mathbb{R}$ is concave
increasing, $\mu_{ij}\geq 0$ and $v$ is a vector of non-negative non-
increasing values. Since $W$ is concave and $\mathcal{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 ${|{\cal N}|}{|{\cal I}|}^{2}$ parameters
and $2{|{\cal N}|}{|{\cal 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 $\langle X\,|\,\mathopen{}Y\rangle=\sum_{ijk}X_{ijk}Y_{ijk}$ the dot
product between tensors, the algorithm creates iterates $P^{(t)}$ by first
computing $\tilde{P}=\operatorname*{argmax}_{P\in\mathcal{P}}\langle
P\,|\,\mathopen{}\nabla W(P^{(t)})\rangle$ and then updating
$P^{(t)}=(1-\gamma^{(t)})P^{(t-1)}+\gamma^{(t)}\tilde{P}$ with
$\gamma^{(t)}=\frac{2}{t+2}$ [13]. Starting from an initial solution555In our
experiments, we initialize with the utilitarian ranking (Proposition 6)., the
algorithm always stays in the feasible region without any additional
projection step. Our main contribution of this section is to show that
$\operatorname*{argmax}_{P\in\mathcal{P}}\langle P\,|\,\mathopen{}\nabla
W(P^{(t)})\rangle$ 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 $\mathfrak{S}(P_{i})$ the
support of $P_{i}$ in ranking space.666Formally,
$\mathfrak{S}(P_{i})=\big{\\{}\sigma:{\cal I}\rightarrow[\\![{|{\cal
I}|}]\\!]\big{|}\,\sigma\text{~{}is one-to-one, and~{}}\forall j\in{\cal
I},P_{ij\sigma(j)}>0\big{\\}}$.

######  Theorem 1.

Let
$\tilde{\mu}_{ij}=\Phi_{i}^{\prime}\big{(}u_{i}(P^{(t)})\big{)}\mu_{ij}+\Phi_{j}^{\prime}\big{(}u_{j}(P^{(t)})\big{)}\mu_{ji}$.
Let $\tilde{P}$ such that:

$\displaystyle\forall i\in{\cal
N},\forall\tilde{\sigma}_{i}\in\mathfrak{S}(\tilde{P_{i}})$:
$\tilde{\sigma}_{i}(j)<\tilde{\sigma}_{i}(j^{\prime})\implies\tilde{\mu}_{ij}\geq\tilde{\mu}_{ij^{\prime}}$

. Then
$\displaystyle\tilde{P}\in\smash{\operatorname*{argmax}\limits_{P\in\mathcal{P}}}\langle
P\,|\,\mathopen{}\nabla W(P^{(t)})\rangle$ .

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 $\Phi_{i}^{\prime\prime}$ is bounded, we
have:

######  Proposition 4.

Let
$B=\max\limits_{i\in[\\![n]\\!]}\left\lVert\Phi_{i}^{\prime\prime}\right\rVert_{\infty}$
and $U=\max\limits_{{\boldsymbol{u}}\in{\cal
U}}\left\lVert{\boldsymbol{u}}\right\rVert_{2}^{2}$. Let $K$ be the maximum
index of a nonzero value in $v$ (or ${|{\cal I}|}$). Then $\forall t\geq
1,W(P^{(t)})\geq\max\limits_{P\in\mathcal{P}}W(P)-O(\frac{BU}{t})$. Moreover,
for each user, an iteration costs $O({|{\cal I}|}\ln K)$ operations and
requires $O(K)$ additional bytes of storage.

##  5 Experiments

(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.

###  5.1 One-sided recommendation

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 $\beta\frac{E}{{|{\cal
I}|}}$ where $\beta$ 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.

#### 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 $\alpha_{1}=\alpha_{2}=0$ and varying the relative weight
of items $\lambda$. Fig. 2(a) 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 $\beta$ of the inequality measure.

  * •

qua.-weighted yields unfair trade-offs Fig. 2(c) 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. 2(b): 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 $\leq 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 $\alpha_{1}\in\\{-2,0,1\\}$,
keeping $\alpha_{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 $\alpha_{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 $\alpha_{1}\in\\{-2,0,1\\}$ in Fig. 3(a) and Fig. 3(b).

  * •

_welf $\alpha_{1}=0$ is better than Patro et al._, which can be seen by
jointly looking at Fig. 3(c), 3(d) and Fig. 3(b) which give the cumulative
utility at different points of the Lorenz curve ($10\%$, $25\%$ and $100\%$ of
the users respectively). We observe that welf $\alpha_{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. 3(e) and 3(f) which plot welf $\alpha_{1}=0$
and Patro et al. at two levels of item inequality. welf $\alpha_{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 $\alpha_{1}=1$ and eq.
exposure.

  * •

_More user inequalities is not necessarily unfair_ as seen in Fig. 3(a)
comparing welf $\alpha_{1}=0$ and Patro et al.. We observe that welf
$\alpha_{1}=0$ has slightly higher Gini index, but this is not unfair: as seen
in Fig. 3(e) and 3(f), 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..

(a) User inequality.

(b) Total user utility.

(c) Cumulative utility at 10% worse-off users.

(d) Cumulative utility at 25% worse-off users.

(e) Item inequality $\approx 0.4$.

(f) Item inequality $\approx 0.6$.

Figure 3: Summary of results on Lastfm-2k for two-sided fairness: effect of
varying $\alpha_{1}$.

###  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 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 $13$k 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 quality-weighted 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 $\alpha$_ are plotted in Fig. 4a.
As $\alpha$ 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 $\alpha=-5$ has more than doubled the cumulative utility of
the 10% worse off users compared to $\alpha=1$ (120 vs 280), but at the cost
of more than 60% of the total utility ($17$k vs $6.4$k). 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 $\alpha=0.5$
already dominates some of their models, even though in this region of $\alpha$
there is little focus on worse-off users. More generally, all values of
$\beta\geq 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 $\beta$, 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.

(a) Example trade-offs achieved by welf.

(b) welf dominates exposure-based methods.

(c) welf dominates eq. utility near strict equality.

(d) Total utility vs inequality.

(e) Total utility vs utility of 10% worse-off users.

(f) Total utility vs utility of 25% worse-off users.

(g) Total utility vs utility of 50% worse-off users.

Figure 4: Results on the twitter dataset.

##  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 [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.

##  7 Conclusion

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.

## References

  * Abdollahpouri et al. [2019] H. Abdollahpouri, M. Mansoury, R. Burke, and B. Mobasher.  The unfairness of popularity bias in recommendation.  _arXiv preprint arXiv:1907.13286_ , 2019.
  * Agarwal [2014] S. Agarwal.  Surrogate regret bounds for bipartite ranking via strongly proper losses.  _The Journal of Machine Learning Research_ , 15(1):1653–1674, 2014.
  * Atkinson [1970] A. B. Atkinson.  On the measurement of inequality.  _Journal of economic theory_ , 2(3):244–263, 1970\.
  * Balcan et al. [2018] M.-F. Balcan, T. Dick, R. Noothigattu, and A. D. Procaccia.  Envy-free classificatoion.  _arXiv preprint arXiv:1809.08700_ , 2018.
  * Bartlett et al. [2006] P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe.  Convexity, classification, and risk bounds.  _Journal of the American Statistical Association_ , 101(473):138–156, 2006.
  * Basu et al. [2020] K. Basu, C. DiCiccio, H. Logan, and N. E. Karoui.  A framework for fairness in two-sided marketplaces.  _arXiv preprint arXiv:2006.12756_ , 2020.
  * Biega et al. [2018] A. J. Biega, K. P. Gummadi, and G. Weikum.  Equity of attention: Amortizing individual fairness in rankings.  In _The 41st international acm sigir conference on research & development in information retrieval_, pages 405–414, 2018.
  * Burke [2017] R. Burke.  Multisided fairness for recommendation.  _arXiv preprint arXiv:1707.00093_ , 2017.
  * Cantador et al. [2011] I. Cantador, P. Brusilovsky, and T. 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.
  * Celis et al. [2017] L. E. Celis, D. Straszak, and N. K. Vishnoi.  Ranking with fairness constraints.  _arXiv preprint arXiv:1704.06840_ , 2017.
  * Celma [2010] O. Celma.  _Music Recommendation and Discovery in the Long Tail_.  Springer, 2010.
  * Chakraborty et al. [2019] 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.
  * Clarkson [2010] K. L. Clarkson.  Coresets, sparse greedy approximation, and the frank-wolfe algorithm.  _ACM Transactions on Algorithms (TALG)_ , 6(4):1–30, 2010.
  * Cossock and Zhang [2008] D. Cossock and T. Zhang.  Statistical analysis of bayes optimal subset ranking.  _IEEE Transactions on Information Theory_ , 54(11):5140–5154, 2008.
  * De Domenico et al. [2013] M. De Domenico, A. Lima, P. Mougel, and M. Musolesi.  The anatomy of a scientific rumor.  _Scientific reports_ , 3(1):1–9, 2013.
  * Do et al. [2021] V. Do, S. Corbett-Davies, J. Atif, and N. Usunier.  Online certification of preference-based fairness for personalized recommender systems.  _arXiv preprint arXiv:2104.14527_ , 2021.
  * Finocchiaro et al. [2021] 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 fairness.  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , pages 489–503, 2021.
  * Frank and Wolfe [1956] M. Frank and P. Wolfe.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ , 3(1-2):95–110, 1956.
  * Gini [1921] C. Gini.  Measurement of inequality of incomes.  _The economic journal_ , 31(121):124–126, 1921\.
  * Gölz et al. [2019] P. Gölz, A. Kahng, and A. D. Procaccia.  Paradoxes in fair machine learning.  _Advances in Neural Information Processing Systems (NeurIPS). Forthcoming_ , 2019.
  * Hannak et al. [2014] 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.
  * Hardt et al. [2016] M. Hardt, E. Price, N. Srebro, et al.  Equality of opportunity in supervised learning.  In _Advances in Neural Information Processing Systems_ , pages 3315–3323, 2016.
  * Hardy et al. [1952] G. H. Hardy, J. E. Littlewood, and G. Pólya.  Inequalities. 2nd ed.  Cambridge, Engl.: At the University Press. XII, 324 p. (1952)., 1952\.
  * Harper and Konstan [2015] 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.
  * Heidari et al. [2018] 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 1265–1276, 2018.
  * Heidari et al. [2019] H. Heidari, M. Loi, K. P. Gummadi, and A. Krause.  A moral framework for understanding fair ml through economic models of equality of opportunity.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , pages 181–190, 2019.
  * Hossain et al. [2020] 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\.
  * Hu and Chen [2020] 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.
  * Hu et al. [2008] Y. Hu, Y. Koren, and C. Volinsky.  Collaborative filtering for implicit feedback datasets.  In _2008 Eighth IEEE International Conference on Data Mining_ , pages 263–272. Ieee, 2008.
  * Jaggi [2013] M. Jaggi.  Revisiting frank-wolfe: Projection-free sparse convex optimization.  In _International Conference on Machine Learning_ , pages 427–435. PMLR, 2013.
  * Jia et al. [2018] 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.
  * Johnson [2014] C. C. Johnson.  Logistic matrix factorization for implicit feedback data.  _Advances in Neural Information Processing Systems_ , 27(78):1–9, 2014.
  * Kay et al. [2015] 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.
  * Kleinberg et al. [2018] J. Kleinberg, J. Ludwig, S. Mullainathan, and A. Rambachan.  Algorithmic fairness.  In _Aea papers and proceedings_ , volume 108, pages 22–27, 2018.
  * Lambrecht and Tucker [2019] 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\.
  * Lee et al. [2021] M. S. A. Lee, L. Floridi, and J. Singh.  Formalising trade-offs beyond algorithmic fairness: lessons from ethical philosophy and welfare economics.  _AI and Ethics_ , pages 1–16, 2021.
  * Lesmana et al. [2019] 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'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Lim et al. [2015] 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.
  * Liu et al. [2019] 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.
  * Mehrotra et al. [2017] R. Mehrotra, A. Anderson, F. Diaz, A. Sharma, H. Wallach, and E. Yilmaz.  Auditing search engines for differential satisfaction across demographics.  In _Proceedings of the 26th international conference on World Wide Web companion_ , pages 626–633, 2017.
  * Mehrotra et al. [2018] R. Mehrotra, J. McInerney, H. Bouchard, M. Lalmas, and F. Diaz.  Towards a fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recommendation systems.  In _Proceedings of the 27th acm international conference on information and knowledge management_ , pages 2243–2251, 2018.
  * Morik et al. [2020] M. Morik, A. Singh, J. Hong, and T. Joachims.  Controlling fairness and bias in dynamic learning-to-rank.  _arXiv preprint arXiv:2005.14713_ , 2020.
  * Moulin [2003] H. Moulin.  _Fair division and collective welfare_.  MIT press, 2003.
  * Nanda et al. [2020] V. Nanda, P. Xu, K. A. Sankararaman, J. Dickerson, and A. Srinivasan.  Balancing the tradeoff between profit and fairness in rideshare platforms during high-demand hours.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 2210–2217, 2020.
  * Palomares et al. [2021] I. Palomares, C. Porcel, L. Pizzato, I. Guy, and E. Herrera-Viedma.  Reciprocal recommender systems: Analysis of state-of-art literature, challenges and opportunities towards social recommendation.  _Information Fusion_ , 69:103–127, 2021.
  * Paraschakis and Nilsson [2020] D. Paraschakis and B. J. Nilsson.  Matchmaking under fairness constraints: a speed dating case study.  In _International Workshop on Algorithmic Bias in Search and Recommendation_ , pages 43–57. Springer, 2020.
  * Patro et al. [2020] G. K. Patro, A. Biswas, N. Ganguly, K. P. Gummadi, and A. Chakraborty.  Fairrec: Two-sided fairness for personalized recommendations in two-sided platforms.  _arXiv preprint arXiv:2002.10764_ , 2020.
  * Ravikumar et al. [2011] P. Ravikumar, A. Tewari, and E. Yang.  On ndcg 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.
  * Richardson et al. [2003] M. Richardson, R. Agrawal, and P. Domingos.  Trust management for the semantic web.  In _International semantic Web conference_ , pages 351–368. Springer, 2003.
  * Roemer and Trannoy [2016] J. E. Roemer and A. Trannoy.  Equality of opportunity: Theory and measurement.  _Journal of Economic Literature_ , 54(4):1288–1332, 2016.
  * Sen [1979] A. Sen.  Equality of what?  _The Tanner lecture on human values_ , 1, 1979.
  * Shorrocks [1980] A. F. Shorrocks.  The class of additively decomposable inequality measures.  _Econometrica: Journal of the Econometric Society_ , pages 613–625, 1980.
  * Shorrocks [1983] A. F. Shorrocks.  Ranking income distributions.  _Economica_ , 50(197):3–17, 1983.
  * Singh and Joachims [2018] 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–2228. ACM, 2018.
  * Singh and Joachims [2019] A. Singh and T. Joachims.  Policy learning for fairness in ranking.  In _Advances in Neural Information Processing Systems_ , pages 5427–5437, 2019.
  * Speicher et al. [2018] T. Speicher, H. Heidari, N. Grgic-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.
  * Sweeney [2013] L. Sweeney.  Discrimination in online ad delivery.  _Queue_ , 11(3):10, 2013.
  * Thistle [1989] P. D. Thistle.  Ranking distributions with generalized lorenz curves.  _Southern Economic Journal_ , pages 1–12, 1989.
  * Ustun et al. [2019] B. Ustun, Y. Liu, and D. Parkes.  Fairness without harm: Decoupled classifiers with preference guarantees.  In _International Conference on Machine Learning_ , pages 6373–6382, 2019.
  * Wang and Joachims [2020] L. Wang and T. Joachims.  Fairness and diversity for rankings in two-sided markets.  _arXiv preprint arXiv:2010.01470_ , 2020.
  * Wang et al. [2018] 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.
  * Wolfson and Lin [2017] O. Wolfson and J. Lin.  Fairness versus optimality in ridesharing.  In _2017 18th IEEE International Conference on Mobile Data Management (MDM)_ , pages 118–123. IEEE, 2017.
  * Wu et al. [2021] 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.09024_ , 2021.
  * Xia et al. [2019] B. Xia, J. Yin, J. Xu, and Y. Li.  We-rec: A fairness-aware reciprocal recommendation based on walrasian equilibrium.  _Knowledge-Based Systems_ , 182:104857, 2019.
  * Zehlike and Castillo [2020] M. Zehlike and C. Castillo.  Reducing disparate exposure in ranking: A learning to rank approach.  In _Proceedings of The Web Conference 2020_ , pages 2849–2855, 2020\.
  * Zhang et al. [2004] T. Zhang et al.  Statistical behavior and consistency of classification methods based on convex risk minimization.  _The Annals of Statistics_ , 32(1):56–85, 2004\.
  * Zimmer et al. [2021] 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.

##  Appendix A Outline of the appendices

These appendices are structured as follows:

  * •

In Appendix B, we present how our fairness framework can be applied to
sensitive groups of users or categories of items.

  * •

In Appendix C, we present a deeper analysis of the trade-offs achieved by the
welfare approach. We also provide a theoretical guarantee relating the true
welfare obtained by maximizing the welfare using estimated preferences,
depending on the quality of the estimates.

  * •

In Appendix D, we present the proofs for the theoretical results comparing our
results and previous criteria of fairness in rankings. In addition, in
Appendix D.3, we describe how to extend the criteria of equality of exposure
and quality-weighted exposure in a reciprocal recommendation setting. This is
the extension used in our experiments on reciprocal recommendation. In
Proposition 8, we present an additional result regarding the inefficiency of
these criteria in reciprocal recommendation.

  * •

In Appendix E, we present the more general version of the Frank-Wolfe
algorithm, which we use both to optimize the welfare function over stochastic
rankings, as well as the penalty-based baselines. This appendix also contains
the proofs of the results in Section 4. In addition, this appendix contains
fundamental lemmas that are used in other appendices.

  * •

Appendix F gives the details of the experiments presented in Section 5, as
well we many additional experiments (two additional, larger scale datasets on
one-sided recommendation, and an additional dataset for reciprocal
recommendation)

  * •

Appendix G briefly discusses the difference between the penalty we use in our
implementation of the baseline approaches and an alternative penalty used by
some authors.

  * •

Finally, Appendix H discusses the difference between applying item-side
fairness criteria for every ranking, compared to what we do in the paper,
which defines item-side utility as an aggregate over the rankings of all
users.

##  Appendix B Fairness towards sensitive groups rather than individuals

In all the paper we focus on fairness towards individual users and items
rather than groups of users or items. Prior work [54, 42, 55] considered the
utlity of a group as the sum or the average utility of its members. Using this
definition of group utility, our framework dirrectly extends to groups rather
than individuals. In this section we describe the case of one-sided
recommendation with groups of users and item categories. The case of
reciprocal recommendation (with user groups only) is similar but simpler.

Let ${\cal S}=(s_{p})_{p=1}^{|{\cal S}|}$ be (possibly overlapping) user
groups, i.e., $\forall p\in[\\![{|{\cal S}|}]\\!],s_{p}\subseteq{\cal N}$ and
$\cup_{p\in[\\![{|{\cal S}|}]\\!]}s_{p}={\cal N}$. Similarly, let ${\cal
C}=(c_{q})_{q=1}^{|{\cal C}|}$ be (possibly overlapping) item categories,
i.e., $\forall q\in[\\![{|{\cal C}|}]\\!],c_{q}\subseteq{\cal I}$ and
$\cup_{q\in[\\![{|{\cal C}|}]\\!]}c_{q}={\cal I}$. On the user side, such
groups would typically correspond to demographic groups considered sensitive
for the application at hand [57]. On the item side, groups can represent a
single producer for the case where we want to be fair to producers based on
the aggregate utility they obtain from their products [41], or demographic
groups as well [33].

In all cases, we redefine the user-side utility for groups and the item-side
utility for categories:

$\displaystyle u_{s_{p}}^{\rm gr}(P)=\sum_{i\in s_{p}}u_{i}(P)$ $\displaystyle
u_{c_{q}}^{\rm cat}(P)=\sum_{j\in c_{q}}u_{j}(P)$ (9)

Let $\boldsymbol{{\boldsymbol{u}}missing}^{\rm gr}(P)=(u_{s_{p}}^{\rm
gr}(P))_{p=1}^{|{\cal S}|}$ and $\boldsymbol{{\boldsymbol{u}}missing}^{\rm
cat}(P)=(u_{c_{q}}^{\rm cat}(P))_{q=1}^{|{\cal C}|}$ be the utility profiles
of user groups and item categories associated to $P$ respectively. The two-
sided Lorenz efficiency for groups and categories is defined as:

######  Definition 2.

Let ${\cal S}$ be a set of user groups and ${\cal C}$ a set of item
categories. Let $P\in\mathcal{P}$. $P$ is $({\cal S},{\cal C})$-Lorenz
efficient if there is no $P^{\prime}\in\mathcal{P}$ such that either condition
holds:

  1. 1.

$\boldsymbol{{\boldsymbol{u}}missing}^{\rm gr}(P^{\prime})\succeq_{\rm
L}\boldsymbol{{\boldsymbol{u}}missing}^{\rm gr}(P)$ and
$\boldsymbol{{\boldsymbol{u}}missing}^{\rm cat}(P^{\prime})\succ_{\rm
L}\boldsymbol{{\boldsymbol{u}}missing}^{\rm cat}(P)$, or

  2. 2.

$\boldsymbol{{\boldsymbol{u}}missing}^{\rm cat}(P^{\prime})\succeq_{\rm
L}\boldsymbol{{\boldsymbol{u}}missing}^{\rm cat}(P)$ and
$\boldsymbol{{\boldsymbol{u}}missing}^{\rm gr}(P^{\prime})\succ_{\rm
L}\boldsymbol{{\boldsymbol{u}}missing}^{\rm gr}(P)$.

The welfare function associated to $({\cal S},{\cal C})$, still parametrized
by $\theta=(\lambda,\alpha_{1},\alpha_{2})\in\Theta$, is defined as

$W_{\theta}^{\rm gr}(P)=(1-\lambda)\sum_{s\in{\cal S}}\psi(u_{s}^{\rm
gr}(P),\alpha_{1})+\lambda\sum_{c\in{\cal C}}\psi(u_{c}^{\rm
cat}(P),\alpha_{2})$ (10)

The welfare function follows the general form of objective function used for
the algorithm in Appendix E, so the optimization of $W_{\theta}^{\rm gr}$
requires similar computational complexity as $W_{\theta}$.

Finally, the extension of Proposition 1 is straightforward. Its proof is
similar to the proof presented in Appendix C.

######  Proposition 5.

$\forall\theta\in\Theta,\forall
P^{*}\in\operatorname*{argmax}\limits_{P\in\mathcal{P}}W_{\theta}^{\rm
gr}(P)$, $P^{*}$ is $({\cal S},{\cal C})$-Lorenz efficient.

Note that this way of treating groups is not necessarily optimal. In
particular, in does not account for within-group fairness. The separate
consideration of within-group and between-group fairness has been studied
extensively in the literature on equality of opportunity [50], which has
inspired several works on algorithmic fairness [22, 26]. Yet, how to apply
these principles to two-sided fairness in recommendation is still open, and is
left as future work.

##  Appendix C More on welfare functions

This appendix provides an in-depth analysis of the trade-offs that are
achievable by the welfare approach. We first pove the proposition of Section
2.2, and analyze the utilitarian rankings (obtained with
$\alpha_{1}=\alpha_{2}=1$). We then analyze how to obtain leximin optimal
solutions on the side of the items in Appendix C.2, as mentioned in Section
2.2. Finally, we prove Theorem 2 in Appendix C.3, which provides a regret
bound relating the true welfare achieved when maximizing welfare on estimated
preferences. Some results in this section use Lemma 3 of Appendix 4, which is
proved in Appendix 4.

Throughout the appendices, we use the more general version of item utilities
(two-sided preferences), described at the end of Section 2.1. Moreover, to
clarify the notation, we remind that a _ranking tensor_ is a three-way tensor
$P$ where $P_{ijk}$ is the probability that item $j$ is recommended to user
$i$ at rank $k$. We consider $P$ as an $n\times n\times{|{\cal I}|}$ tensor,
where irrelevant entries are set to $0$. With this notation, the utility for
both users and items can be written with the same formula:

$\forall i\in[\\![n]\\!],u_{i}(P)=\sum_{j=1}^{n}\mu_{ij}(P_{ij}+P_{ji})v.$
(11)

Note that this formula also corresponds to the two-sided utility in reciprocal
recommendation. In general, the results in this appendix can be extended to
reciprocal recommendation with minimal changes to their proofs, using ${\cal
N}={\cal I}=[\\![n]\\!]$ and the formula above for the utility.

###  C.1 Lorenz efficiency and utilitarian ranking

We first prove Proposition 1: See 1

###### Proof.

It is well known that if $\Phi$ is increasing and strictly concave, then
$F({\boldsymbol{u}})=\sum_{i=1}^{n}\Phi(u_{i})$ is monotonic with respect to
Lorenz dominance [53, 58]: ${\boldsymbol{u}}\succ_{\rm
L}{\boldsymbol{u^{\prime}}}\implies
F({\boldsymbol{u}})>F({\boldsymbol{u^{\prime}}})$.

In the case of $W_{\theta}$, for every
$\theta=(\lambda,\alpha_{1},\alpha_{2})\in\Theta$, both $\psi(.,\alpha_{1})$
and $\psi(.,\alpha_{2})$ are strictly concave by the definition of $\Theta$
(recall that in $\Theta$, we have $\alpha_{1},\alpha_{2}<1$).

The partial function777We denote by $({{\boldsymbol{u}}}_{{\cal
I}},{{\boldsymbol{u}}}^{\prime}_{{\cal N}})$ the vector $\mathbb{R}^{d}$ such
that $({{\boldsymbol{u}}}_{{\cal I}},{{\boldsymbol{u}}}^{\prime}_{{\cal
N}})_{i}=u_{i}$ if $i\in{\cal I}$ and $({{\boldsymbol{u}}}_{{\cal
I}},{{\boldsymbol{u}}}^{\prime}_{{\cal N}})_{i}=u^{\prime}_{i}$ if $i\in{\cal
N}$. ${{\boldsymbol{u}}}^{\prime}_{{\cal N}}\mapsto
W_{\theta}(({{\boldsymbol{u}}}_{{\cal I}},{{\boldsymbol{u}}}^{\prime}_{{\cal
N}}))$ is, up to a constant, of the form of $F$ and likewise for the partial
function ${{\boldsymbol{u}}}^{\prime}_{{\cal I}}\mapsto
W_{\theta}(({{\boldsymbol{u}}}^{\prime}_{{\cal I}},{{\boldsymbol{u}}}_{{\cal
N}}))$. We now prove the result by contradiction. Assume that
${\boldsymbol{u}}\in\operatorname*{argmax}_{{\boldsymbol{u}}\in{\cal
U}}W_{\theta}({\boldsymbol{u}})$ is not Lorenz efficient. Then there is
${\boldsymbol{u^{\prime}}}\in{\cal U}$ such that
$(\boldsymbol{u}^{\prime}_{{\cal N}}\succeq_{\rm L}{{\boldsymbol{u}}}_{{\cal
N}}$ and $\boldsymbol{u}^{\prime}_{{\cal I}}\succ_{\rm
L}{{\boldsymbol{u}}}_{{\cal I}})$ or $(\boldsymbol{u}^{\prime}_{{\cal
N}}\succ_{\rm L}{{\boldsymbol{u}}}_{{\cal N}}$ and
$\boldsymbol{u}^{\prime}_{{\cal I}}\succeq_{\rm L}{{\boldsymbol{u}}}_{{\cal
I}})$. Let us assume $(\boldsymbol{u}^{\prime}_{{\cal N}}\succeq_{\rm
L}{{\boldsymbol{u}}}_{{\cal N}}$ and $\boldsymbol{u}^{\prime}_{{\cal
I}}\succ_{\rm L}{{\boldsymbol{u}}}_{{\cal I}})$, the other case is dealt with
similarly. We then have:

$\displaystyle W_{\theta}({\boldsymbol{u^{\prime}}})$ $\displaystyle\geq
W_{\theta}((\boldsymbol{u}^{\prime}_{{\cal I}},{{\boldsymbol{u}}}_{{\cal
N}}))$ (because $\boldsymbol{u}^{\prime}_{{\cal N}}\succeq_{\rm
L}{{\boldsymbol{u}}}_{{\cal N}}$)
$\displaystyle>W_{\theta}(({{\boldsymbol{u}}}_{{\cal
I}},{{\boldsymbol{u}}}_{{\cal N}}))$ (because $\boldsymbol{u}^{\prime}_{{\cal
I}}\succ_{\rm L}{{\boldsymbol{u}}}_{{\cal I}}$)

which contradicts the maximality of ${\boldsymbol{u}}$. ∎

The analogous for Proposition 1 for reciprocal recommendation is a direct
consequence of standard results that concave welfare functions are monotonic
with respect to Lorenz dominance [53, 58].

#### Utilitarian ranking

Proposition 6 below generalizes to two-sided utilities the well-known result
that maximizing user-side utility is achieved by sorting $j\in{\cal I}$ by
decreasing $\mu_{ij}$ (see e.g., [14]). For a ranking tensor $P$ and a user
$i$, we denote by $\mathfrak{S}(P_{i})$ the support of $P_{i}$ in ranking
space.888Formally, $\mathfrak{S}(P_{i})=\big{\\{}\sigma:{\cal
I}\rightarrow[\\![{|{\cal I}|}]\\!]\big{|}\,\sigma\text{~{}is one-to-one,
and~{}}\forall j\in{\cal I},P_{ij\sigma(j)}>0\big{\\}}$. We remind that
$\sigma(j)$ is the rank of item $j$, and that lower ranks are better. For a
user $i$ and item $j$, we use $\mu_{ji}=1$.

######  Proposition 6 (Utilitarian ranking).

Assume $\forall k\in[\\![n-1]\\!],v_{k}>v_{k+1}\geq 0$ and let

$P^{*}\in\smash{\operatorname*{argmax}\limits_{P\in\mathcal{P}}}W_{\frac{1}{2},1,1}(P)=\smash{\operatorname*{argmax}\limits_{P\in\mathcal{P}}}\sum\limits_{i\in[\\![n]\\!]}u_{i}(P).$
(12)

  1. 1.

$\displaystyle\forall i\in{\cal
N},\forall\sigma\in\mathfrak{S}(P^{*}_{i}):\sigma(j)<\sigma(j^{\prime})\implies\tilde{\mu}_{ij}\geq\tilde{\mu}_{ij^{\prime}}\text{~{}~{}with~{}~{}}\tilde{\mu}_{ij}=\mu_{ij}+\mu_{ji}.$

  2. 2.

If $\forall(i,j)\in[\\![n]\\!]^{2},\mu_{ij}=\mu_{ji}$, then
$\tilde{\mu}_{ij}\geq\tilde{\mu}_{ij^{\prime}}\iff\mu_{ij}\geq\mu_{ij^{\prime}}$.

When mutual preferences are symmetric (i.e., $\mu_{ij}=\mu_{ji}$), the
utilitarian ranking is the same as the usual sort by decreasing $\mu_{ij}$.
This also obviously holds when we consider exposue as item utility
($\mu_{ji}=1$). This means that without considerations of two-sided fairness
($\alpha_{1},\alpha_{2}<1$), the optimal ranking for two-sided utilities is
the same as the usual ranking. This might explain why the two-sided utility
has never been studied before, even in reciprocal recommendation [45].

For the proof of Proposition 6, the main part is the following lemma:

######  Lemma 1.

Let $F({\boldsymbol{u}}(P))=\sum\limits_{i=1}^{n}u_{i}(P)$ and
$\tilde{\mu}_{ij}=\mu_{ij}+\mu_{ji}$. Assume $\forall
k\in[\\![n-1]\\!],v_{k}\geq v_{k+1}\geq 0$.

If $P^{*}\in\mathcal{P}$ is such that
$\forall\sigma\in\mathfrak{S}(P_{i}^{*}),\forall j,j^{\prime}$,
$\sigma(j)<\sigma(j^{\prime})\implies\tilde{\mu}_{ij}\geq\tilde{\mu}_{ij^{\prime}}$
then
$P^{*}\in\operatorname*{argmax}\limits_{P\in\mathcal{P}}{\boldsymbol{u}}(P)$.

Moreover, if $\forall k\in[\\![n-1]\\!],v_{k}>v_{k+1}\geq 0$, then the
reciprocal is true.

###### Proof.

Notice that, thanks to the completion of $P$ with zeros on irrelevant entries
and formula 11, $F({\boldsymbol{u}}(P))$ can be rewritten as:

$\displaystyle F({\boldsymbol{u}}(P))$
$\displaystyle=\sum\limits_{i=1}^{n}u_{i}(P)=\sum_{i=1}^{n}\sum_{j=1}^{n}\mu_{ij}(P_{ij}+P_{ji})v=\sum_{i=1}^{n}\sum_{j=1}^{n}(\mu_{ij}+\mu_{ji})P_{ij}v$
(13)

where the last equality is obtained by swapping $i$ and $j$ in the second sum,
which is possible since $i$ and $j$ span the same range.

The result is then a direct consequence of Lemma 3 in Appendix E, using
$A_{ij}=\mu_{ij}+\mu_{ji}$. ∎

The first of statement of Proposition 6 assumes that the exposure weights $v$
are non-negative and strictly decreasing as per the second point of Lemma 1.
Lemma 1 above gives the statement for the more general case of non-increasing
$v$.

###### Proof of Proposition 6.

The first statement is the consequence of Lemma 1 above, noticing that
$F({\boldsymbol{u}}(P))$ in Lemma 1 always has the same argmax. The second
statement is obvious from the assumptions.

∎

###  C.2 Item-side leximin optimality

The most egalitarian trade-off achievable by our method is described by the
leximin order [51]. Given two utility profiles ${\boldsymbol{u}}$ and
${\boldsymbol{u^{\prime}}}$, ${\boldsymbol{u}}\mathop{\geq}_{\rm
lex}{\boldsymbol{u^{\prime}}}$ if ${\boldsymbol{U}}$ is greater than
${\boldsymbol{U^{\prime}}}$ according to the lexicographic order.999Formally,
${\boldsymbol{u}}\mathop{>}_{\rm lex}{\boldsymbol{u^{\prime}}}$ if $(\exists
k\in[\\![d]\\!]$ s.t. $\forall i<k$, $U_{i}=U^{\prime}_{i}$ and
$U_{k}>U^{\prime}_{k})$. ${\boldsymbol{u}}\mathop{\geq}_{\rm
lex}{\boldsymbol{u^{\prime}}}\iff\lnot({\boldsymbol{u^{\prime}}}\mathop{\geq}_{\rm
lex}{\boldsymbol{u}})$. The leximin optimal profile is egalitarian in the
sense that it maximizes the utility of individuals in sequence, from the
worse-off to the better-off. Depending on the set of feasible profiles, this
may not lead to equal utility for everyone, but any further reduction of
inequality can only be achieved by making people worse off for the benefit of
no other, in violation of Pareto-dominance.

The proposition below formalizes how leximin optimal solutions on the side of
items are found. It shows that item-side leximin solutions are obtained by
having $\alpha_{2}\to-\infty$ and $\lambda\to 1$ at the same time. The
proposition gives a formal statement of the rate at which $\lambda$ should
converge to $1$ relative to $\alpha$.

In the statement of the proposition, given two functions $F$ and $G$, we use
$F(\alpha)\mathop{\geq}\limits_{\alpha\to-\infty}G(\alpha)$ as a shorthand for
$F(\alpha)\geq G(\alpha)$ for $\alpha$ sufficiently small.101010Formally,
$F(\alpha)\mathop{\geq}\limits_{\alpha\to-\infty}G(\alpha)\iff\exists\alpha_{0}\in\mathbb{R},\forall\alpha\leq\alpha_{0},F(\alpha)\geq
G(\alpha)$..

######  Proposition 7.

Let ${\cal U}^{\rm item}_{\rm lex}=\\{{\boldsymbol{u}}\in{\cal
U}:\forall{\boldsymbol{u^{\prime}}}\in{\cal U},{{\boldsymbol{u}}}_{{\cal
I}}\mathop{\geq}_{\rm lex}\boldsymbol{u}^{\prime}_{{\cal I}}\\}$ and let
${\boldsymbol{u}}^{*}=\smash{\operatorname*{argmax}\limits_{{\boldsymbol{u}}\in{\cal
U}^{\rm item}_{\rm lex}}}\sum\limits_{i\in{\cal N}}\psi(u_{i},\alpha_{1})$.

$\displaystyle\forall\eta>\max(1,\left\lVert{{\boldsymbol{u}}^{*}}_{{\cal
I}}\right\rVert_{\infty}),\forall{\boldsymbol{u}}\in{\cal
U}:W_{1-\eta^{\alpha},\alpha_{1},\alpha}({\boldsymbol{u}}^{*})\mathop{\geq}\limits_{\alpha\to-\infty}W_{1-\eta^{\alpha},\alpha_{1},\alpha}({\boldsymbol{u}}).$
(14)

This means that among the leximin-optimal item-side utility profiles,
$\alpha_{1}$ still controls the redistribution profile on the user side, since
it is possible that $|{\cal U}^{\rm item}_{\rm lex}|>1$ in one-sided
recommendation. A similar result holds for user-side item leximin.

###### Proof.

Let
${\boldsymbol{u}}^{*}=\smash{\operatorname*{argmax}\limits_{{\boldsymbol{u}}\in{\cal
U}^{\rm item}_{\rm lex}}}\sum\limits_{i\in{\cal N}}\psi(u_{i},\alpha_{1})$ and
${\boldsymbol{u}}\in{\cal U}$. Let $\theta=(\lambda,\alpha_{1},\alpha)$ and
take $\alpha<\min(0,\alpha_{1})$.

Let $(j_{1},j_{2},\ldots,j_{{|{\cal I}|}})$ be the ranking of
${\boldsymbol{u}}^{*}_{{\cal I}}$ in increasing order:
$u^{*}_{j_{1}}\leq\ldots u^{*}_{j_{{|{\cal I}|}}}$. Likewise, let
$(j^{\prime}_{1},j^{\prime}_{2},\ldots,j^{\prime}_{{|{\cal I}|}})$ be the
ranking of ${{\boldsymbol{u}}}_{{\cal I}}$ in increasing order:
$u_{j^{\prime}_{1}}\leq\ldots\leq u_{j^{\prime}_{{|{\cal I}|}}}$.

Let $m=\max\\{k\in[\\![{|{\cal I}|}]\\!]\cup\\{0\\}:\forall\ell\leq
k,u^{*}_{j_{\ell}}=u_{j^{\prime}_{\ell}}\\}+1$, be the last index (+1) such
that the smallest values of ${\boldsymbol{u}}^{*}$ and ${\boldsymbol{u}}$ are
equal ($m=1$ if the smallest values are different).

Let
$C(\alpha)=W_{1-\eta^{\alpha},\alpha_{1},\alpha}({\boldsymbol{u}}^{*})-W_{1-\eta^{\alpha},\alpha_{1},\alpha}({\boldsymbol{u}})$.

Let $K=\sum_{i\in{\cal
N}}\big{(}\psi(u_{i}^{*},\alpha_{1})-\psi(u^{\prime}_{i},\alpha_{1})\big{)}$.

case 1: $m={|{\cal I}|}+1$. Then $C(\alpha)=(1-\eta^{\alpha})K\geq 0$ since
${\boldsymbol{u}}^{*}_{{\cal I}}={{\boldsymbol{u}}}_{{\cal I}}$ and
${\boldsymbol{u}}^{*}$ maximizes the user-side welfare.

case 2: $m<{|{\cal I}|}$. Then, we have $u_{j^{\prime}_{m}}<u^{*}_{j_{m}}$ by
the leximin optimality of ${\boldsymbol{u}}^{*}_{{\cal I}}$. We then have:

$\displaystyle C(\alpha)$
$\displaystyle=(1-\eta^{\alpha})K+\eta^{\alpha}\sum_{j\in{\cal
I}}-(u^{*}_{j})^{\alpha}+(u_{j})^{\alpha}$ (15)
$\displaystyle=-(1-\eta^{\alpha})\big{(}u^{*}_{j_{m}}\big{)}^{\alpha}\Big{(}\frac{K}{1-\eta^{\alpha}}\underbrace{\big{(}\frac{\eta}{u^{*}_{j_{m}}}\big{)}^{\alpha}}_{\xrightarrow[\alpha\to-\infty]{}0}+1+\sum_{k>m}\underbrace{\big{(}\frac{u^{*}_{j_{k}}}{u^{*}_{j_{m}}}\big{)}^{\alpha}}_{\xrightarrow[\alpha\to-\infty]{}0}-\underbrace{\big{(}\frac{u_{j^{\prime}_{m}}}{u^{*}_{j_{m}}}\big{)}^{\alpha}}_{\xrightarrow[\alpha\to-\infty]{}+\infty}-\sum_{k>m}\underbrace{\big{(}\frac{u_{j^{\prime}_{m}}}{u^{*}_{j_{m}}}\big{)}^{\alpha}}_{\geq
0}\Big{)}$ (16)

which implies $\lim\limits_{\alpha\to-\infty}C(\alpha)=+\infty$ and thus the
desired result. ∎

###  C.3 Guarantees when performing inference with estimated preferences

In practice, inference is carried out on an estimate $\hat{\mu}$ of $\mu$,
meaning that, denoting $\hat{{\boldsymbol{u}}}$ the resulting estimated
utility111111We have $\hat{{\boldsymbol{u}}}_{i}(P)=\sum_{j\in{\cal
I}}\hat{\mu}_{ij}P_{ij}v$ for $i\in{\cal N}.$ the system output
$\hat{P}=\operatorname*{argmax}_{P\in\mathcal{P}}W_{\theta}(\hat{{\boldsymbol{u}}}(P))$.
The following result extends surrogate regret bounds that exist in
classification [5, 66] and learning to rank [14, 48, 2]to the case of welfare
functions and global stochastic rankings. It makes the link between the
quality of the estimate $\hat{\mu}$ and an optimality guarantee for
${\boldsymbol{u}}(\hat{P})$ (i.e., the true welfare of the ranking inferred on
the estimated values). We prove the result for
$\theta=(\frac{1}{2},\alpha,\alpha)$ for $\alpha\leq 1$ to simplify
notation.121212The dependency on $\hat{\mu}$ in $B(\hat{\mu})$ is because
$\psi^{\prime}(.,\alpha)$ is not bounded in general. In practice, we use
$\psi(x+\eta,\alpha)$ for a small $\eta>0$ to avoid the singular point at $0$,
in which case $B<\psi^{\prime}(\eta,\alpha)$.

######  Theorem 2.

Let $\alpha\leq 1$ and $\theta=(\frac{1}{2},\alpha,\alpha)\in\Theta$. Let
$\hat{\mu}\in\mathbb{R}_{+}^{|{\cal N}|\times|{\cal I}|}$,
$\hat{P}=\operatorname*{argmax}_{P\in\mathcal{P}}W_{\theta}(\hat{{\boldsymbol{u}}}(P))$,
and
$P^{*}=\operatorname*{argmax}_{P\in\mathcal{P}}W_{\theta}({\boldsymbol{u}}(P))$.

Let furthermore
$B(\hat{\mu})=\max\big{(}\max_{i\in[\\![n]\\!]}\psi^{\prime}(u_{i}(\hat{P}),\alpha),\max_{i\in[\\![n]\\!]}\psi^{\prime}(\hat{u}_{i}(P^{*}),\alpha)\big{)}$.
We have:

$\displaystyle
W_{\theta}({\boldsymbol{u}}(P^{*}))-W_{\theta}({\boldsymbol{u}}(\hat{P}))\leq
4B(\hat{\mu})\sqrt{n\left\lVert
v\right\rVert_{2}^{2}}\sqrt{\sum_{(i,j)\in{\cal N}\times{\cal
I}}(\hat{\mu}_{ij}-\mu_{ij})^{2}}.$ (17)

The existing results closest to our Theorem 2 are Theorem 2 of [14]. Here the
result is substantially more difficult to prove because of the concave
function and the fact that utilities are two-sided, calling for considering
the rankings of multiple users at once.

###### Proof.

We have:

$\displaystyle
W_{\theta}({\boldsymbol{u}}(P^{*}))-W_{\theta}({\boldsymbol{u}}(\hat{P}))$
$\displaystyle=W_{\theta}({\boldsymbol{u}}(P^{*}))-\underbrace{W_{\theta}(\hat{{\boldsymbol{u}}}(\hat{P}))}_{\geq
W_{\theta}(\hat{{\boldsymbol{u}}}(P^{*})}+W_{\theta}(\hat{{\boldsymbol{u}}}(\hat{P}))-W_{\theta}({\boldsymbol{u}}(\hat{P}))$
$\displaystyle\leq\underbrace{W_{\theta}({\boldsymbol{u}}(P^{*}))-W_{\theta}(\hat{{\boldsymbol{u}}}(P^{*}))}_{=C_{1}}+\underbrace{W_{\theta}(\hat{{\boldsymbol{u}}}(\hat{P}))-W_{\theta}({\boldsymbol{u}}(\hat{P}))}_{=C_{2}}$

Let
$B_{1}(\hat{\mu})=\max_{i\in[\\![n]\\!]}\psi^{\prime}(\hat{{\boldsymbol{u}}}_{i}(P^{*}),\alpha)$.

We first prove:

$C_{1}\leq 2B_{1}(\hat{\mu})\sqrt{n\left\lVert
v\right\rVert_{2}^{2}}\sqrt{\sum_{(i,j)\in[\\![n]\\!]^{2}}(\hat{\mu}_{ij}-\mu_{ij})^{2}}.$
(18)

To prove (18), we start by using the concavity of $\psi(.,\alpha)$ for
$\alpha\leq 1$. Let $\Phi(.)=\frac{1}{2}\psi(.,\alpha)$. We have:

$\displaystyle C_{1}$
$\displaystyle=\sum_{i=1}^{n}\big{(}\Phi({\boldsymbol{u}}(P^{*}))-\Phi(\hat{{\boldsymbol{u}}}(P^{*}))\Big{)}\leq\sum_{i=1}^{n}\Phi^{\prime}(\hat{{\boldsymbol{u}}}_{i}(P^{*}))\big{(}{\boldsymbol{u}}(P^{*}))-\hat{{\boldsymbol{u}}}(P^{*})\big{)}$
(19) $\displaystyle\text{thus~{}~{}}C_{1}$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{j=1}^{n}\Phi^{\prime}(\hat{{\boldsymbol{u}}}_{i}(P^{*}))(\mu_{ij}-\hat{\mu}_{ij})(P^{*}_{ij}+P^{*}_{ji})v$
(20)
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}\big{(}\underbrace{\Phi^{\prime}(\hat{{\boldsymbol{u}}}_{i}(P^{*}))(\mu_{ij}-\hat{\mu}_{ij})+\Phi^{\prime}(\hat{{\boldsymbol{u}}}_{j}(P^{*}))(\mu_{ji}-\hat{\mu}_{ji})}_{=A_{ij}}\big{)}P^{*}_{ij}v$
(21)

where, similarly to the proof of Lemma 1, we swapped the indexed $(i,j)$ in
the $\Phi^{\prime}(\hat{{\boldsymbol{u}}}_{i}(P^{*}))\mu_{ij}P^{*}_{ji})v$,
which is possible because $i$ and $j$ span the same range in the sum.

Notice that the terms $A_{ij}P^{*}_{ij}v$ are all zero except if $i\in{\cal
N}$ and $j\in{\cal I}$ (because $P^{*}_{ijk}=0$ otherwise). For $i\in{\cal
N}$, let $\sigma_{i}$ be a ranking which ranks $(A_{ij})_{j\in{\cal I}}$ in
decreasing order, i.e., $\sigma_{i}(j)<\sigma_{i}(j^{\prime})\implies
A_{ij}\geq A_{ij^{\prime}}$. Using Lemma 3 in Appendix E, we have:

$\displaystyle C_{1}$ $\displaystyle\leq\max_{P\in\mathcal{P}}\sum_{i\in{\cal
N}}^{n}\sum_{j\in{\cal I}}A_{ij}P_{ij}v=\sum_{i\in{\cal N}}^{n}\sum_{j\in{\cal
I}}A_{ij}v_{\sigma_{i}(j)}$ (22)

Now let $V=[v_{\sigma_{i}(j)}]_{\begin{subarray}{c}i\in{\cal N}\\\ j\in{\cal
I}\end{subarray}}$. By Cauchy-Shwarz inequality and denoting $\left\lVert
X\right\rVert_{F}=\sqrt{\sum_{ij}X_{ij}^{2}}$ the Frobenius norm of matrix
$X$, we have $\left\lVert V\right\rVert_{F}=\sqrt{n\left\lVert
v\right\rVert_{2}^{2}}$ and $\left\lVert A\right\rVert_{F}\leq
B_{1}(\hat{\mu})(\left\lVert\mu-\hat{\mu}\right\rVert_{F}+\left\lVert\mu^{\top}-\hat{\mu}^{\top}\right\rVert_{F})$,
leading to:

$\displaystyle C_{1}\leq\sqrt{n\left\lVert v\right\rVert_{2}^{2}}\left\lVert
A\right\rVert_{F}\leq 2B_{1}(\hat{\mu})\sqrt{n\left\lVert
v\right\rVert_{2}^{2}}\left\lVert\mu-\hat{\mu}\right\rVert_{F}$ (23)

which proves (18).

Similarly, using
$B_{2}(\hat{\mu})=\max_{i\in[\\![n]\\!]}\psi^{\prime}(u_{i}(\hat{P}),\alpha)$
and the same arguments as above, we obtain:

$C_{2}\leq\sqrt{n\left\lVert v\right\rVert_{2}^{2}}\left\lVert
A\right\rVert_{F}\leq 2B_{2}(\hat{\mu})\sqrt{n\left\lVert
v\right\rVert_{2}^{2}}\left\lVert\mu-\hat{\mu}\right\rVert_{F}$ (24)

which yields the desired result. ∎

##  Appendix D Comparison to utility/inequality trade-offs

In this appendix, we provide the proofs of Section 3, and describe more
precisely how we applied quality-weighted exposure and equality of exposure in
reciprocal recommendation.

###  D.1 One-sided recommendation: quality-weighted exposure

We prove here Proposition 2 of Section 3. The result shows that in some cases,
compared to any choice of the parameter $\theta\in\Theta$ of the welfare
approach, quality-weighted exposure leads to the undesirable behavior of
_decreasing user utility_ while _increasing inequalities of exposure_ between
items. Figure 5 gives an example. See 2

###### Proof.

We prove it for $N=1$, the more general case is just obtained by repeating the
pattern with $d+1$ items and $d+1$ users.

Let $i_{1},...,i_{d+1}$ be the indexes of the users and $j_{1},...,j_{d+1}$
the indexes of the items. The preferences have the following pattern:

$\displaystyle\forall k\in[\\![d+1]\\!],\mu_{i_{k}j_{k}}=1$
$\displaystyle\forall k\in[\\![d]\\!],\mu_{i_{k}j_{d+1}}=\frac{1}{2}$ (25)

all other $\mu_{ij}$ (for user $i$ and item $j$) are set to $0$ (note that we
are in a problem with one-sided preferences, which means $\mu_{ji}=1$ for
every item $j$ and user $i$.

We consider a task with a single recommendation slot
($v_{1}=1,v_{2}=\ldots=v_{{|{\cal I}|}}=0$). On that problem, the optimal
ranking for every $\theta\in\Theta$ is to show item $j_{k}$ to user $i_{k}$,
which leads to perfect equality in terms of item exposure, and maximizes every
user utility. It is thus leximin optimal for both users and items for every
$\theta\in\Theta$.

Then, the qualities are equal to:

$\displaystyle\forall k\in[\\![d]\\!],q_{j_{k}}=1$ $\displaystyle
q_{j_{d+1}}=\frac{1}{2}d+1$ (26)

the target exposure is thus $t_{j_{k}}=\frac{d+1}{\frac{3}{2}d+1}$ for
$k\in[\\![d]\\!]$ and
$t_{j_{d+1}}=(d+1)\frac{\frac{1}{2}d+1}{\frac{3}{2}d+1}$.

Since the problem is symmetric in the users $i_{1},...,i_{d}$, by the
concavity of $F^{\rm qua}_{\beta}({\boldsymbol{u}}(P))$ with respect to $P$,
there is an optimal ranking described by a single probability $p$ as:

$\displaystyle\forall k\in[\\![d]\\!],P_{i_{k}j_{k}}$ $\displaystyle=1-p$
$\displaystyle P_{i_{k}j_{d+1}}=p$ $\displaystyle P_{i_{d+1}j_{d+1}}=1$ (27)

Note that for such a $P$, $\forall k\in[\\![d]\\!]$,
$u^{\text{qua},\beta}_{i_{k}}(P)=1-\frac{1}{2}p$, and it is clearr that there
is $\beta>0$ such that $p>0$, which then implies
${\boldsymbol{u}}^{\theta}\succ_{\rm L}{\boldsymbol{u}}^{{\rm
qua},\beta}_{\cal N}\text{~{}and~{}}{\boldsymbol{u}}^{\theta}\succ_{\rm
L}{\boldsymbol{u}}^{{\rm qua},\beta}_{\cal I}$.

Now, as $\beta\to\infty$, $p$ is such that exposure equals its target, which
leads to the following equation:

$\displaystyle dp+1=(d+1)\frac{\frac{1}{2}d+1}{\frac{3}{2}d+1}.$ (28)

We thus get
$p=\frac{d+1}{d}\frac{d+2}{3d+2}-\frac{1}{d}\xrightarrow[d\to\infty]{}\frac{1}{3}$,
which gives the result
$u^{\text{qua},\beta}_{i_{k}}(P)=1-\frac{1}{2}p\xrightarrow[p\to\frac{1}{3}]{}\frac{5}{6}$.

Notice that similarly to Proposition 3, the result does not depend on the
choice of ${\boldsymbol{u}}^{{\rm qua},\beta}$ because the sum of user
utilities converges. ∎

###  D.2 Reciprocal recommendation: equality of exposure

We now prove Proposition 3. See 3

###### Proof.

The example is given in Figure 5. We still consider a recommendation task with
a single recommendation slot.

Let us rename the users by $i_{1},i_{2},...,i_{5}$. The preference patterns
are $\mu_{i_{1}i_{2}}=\mu_{i_{1}i_{3}}=1$ and $\mu_{i_{4}i_{5}}=1$. Apart from
$\mu_{ij}=\mu_{ji}$, other $\mu_{ij}$s are $0$. In this proof, we show that
$u_{i_{1}}^{{\rm eq},\beta}=2u_{i_{2}}^{{\rm eq},\beta}$ for every $\beta$,
which implies that $u_{i_{1}}^{{\rm eq},\beta}\xrightarrow[\beta\to\infty]{}0$
because $0$ utility for every user is feasible. On this task, the leximin
ranking also maximizes the sum of users utilities (as shown in Figure 5), so
the optimal ranking is the same for every $\theta\in\Theta$, and every user
has a two-sided utility of at least $1.5$.

Since $F_{\beta}({\boldsymbol{u}})$ is stricly Schur-concave for $\beta>0$,
$i_{2}$ and $i_{3}$ always have the same utility in an optimal utility profile
(because they play a symmetric role). $i_{4}$ and $i_{5}$ also have the same
utility. Note that the interest of $i_{4}$ and $i_{5}$ in that problem is to
make it possible to recommend them to $i_{1}$, which has $0$ value.

Similarly to the problem in one-sided recommendation, the only way to decrease
the penalty is to reduce the utility of $i_{1},i_{4},i_{5}$. However, reducing
the utility of $i_{1}$ can only be done by either recommending $i_{4}$ or
$i_{5}$ to $i_{1}$, or recommending $i_{4}/i_{5}$ to $i_{2}/i_{3}$. In all
cases, decreasing $i_{1}$’s utility decreases $i_{2}/i_{3}$’s utilities.

More precisely, because of the symmetries and the concavity of
$F_{\beta}({\boldsymbol{u}}(P))$ with respect to $P$, for every $\beta>0$,
there is an optimal ranking tensor described by three probabilities
$p,q,q^{\prime}$ such that:131313Since there is a single recommendation slot,
we identify $P_{ij1}$ with $P_{ij}$

$\displaystyle P_{i_{1}i_{2}}$
$\displaystyle\\!=\\!P_{i_{1}i_{3}}\\!=\\!\frac{1}{2}p$ $\displaystyle
P_{i_{2}i_{1}}$ $\displaystyle\\!=\\!P_{i_{3}i_{1}}\\!=\\!q$ $\displaystyle
P_{i_{4}i_{5}}$ $\displaystyle\\!=\\!P_{i_{5}i_{4}}\\!=\\!q^{\prime}$ (29)
$\displaystyle P_{i_{1}i_{4}}$
$\displaystyle\\!=\\!P_{i_{1}i_{5}}\\!=\\!\frac{1}{2}(1-p)$ $\displaystyle
P_{i_{2}i_{3}}$
$\displaystyle\\!=\\!P_{i_{2}i_{4}}\\!=\\!P_{i_{2}i_{5}}\\!=\\!\frac{1}{3}(1-q)$
$\displaystyle P_{i_{4}i_{1}}$
$\displaystyle\\!=\\!P_{i_{4}i_{2}}\\!=\\!P_{i_{4}i_{3}}\\!=\\!\frac{1}{3}(1-q^{\prime})$
(30) $\displaystyle P_{i_{3}i_{2}}$
$\displaystyle\\!=\\!P_{i_{3}i_{4}}\\!=\\!P_{i_{3}i_{5}}\\!=\\!\frac{1}{3}(1-q)$
$\displaystyle P_{i_{5}i_{1}}$
$\displaystyle\\!=\\!P_{i_{5}i_{2}}\\!=\\!P_{i_{5}i_{3}}\\!=\\!\frac{1}{3}(1-q^{\prime})$
(31)

In all cases, the two-sided utility are

$\displaystyle u_{i_{1}}(P)$
$\displaystyle=\underbrace{p}_{\begin{subarray}{c}P_{i_{1}i_{2}}\mu_{i_{1}i_{2}}+P_{i_{1}i_{3}}\mu_{i_{1}i_{3}}\\\
\text{user-side
utility}\end{subarray}}+\underbrace{2q}_{\begin{subarray}{c}P_{i_{2}i_{1}}\mu_{i_{2}i_{1}}+P_{i_{3}i_{1}}\mu_{i_{3}i_{1}}\\\
\text{item-side utility}\end{subarray}}$ and $\displaystyle u_{i_{2}}(P)$
$\displaystyle=q+\frac{1}{2}p$ (33)

Thus, in an optimal ranking for $F_{\beta}({\boldsymbol{u}})$, we must have
$u_{i_{1}}(P)=2u_{i_{2}}(P)$. Equality, which is achieved at $\beta\to\infty$
can then only be at $0$ utility for every user (since $0$ is feasible).

The task used in the proof contains only $5$ users. Any number of users can be
added to the group $\\{i_{4},i_{5}\\}$, with a “complete” preference profile
($\mu_{ij}=1$ for all pair $i,j$ in that group). ∎

The Lorenz efficiency of our welfare approach guarantees that it cannot
exhibit the undesirable behaviors of equality or quality-weighted exposure
penalties described in Propositions 2 and 8.

###  D.3 Equality of exposure and quality-weighted exposure in reciprocal
recommendation

In one-sided recommendation with one-sided preferences, equality of exposure
is the same as equality of utility. More generally, let
$e_{j}(P)=\sum_{i\in{\cal N}}P_{ij}v$ the total exposure of item $j$. Equality
of exposure is defined by:

$\displaystyle F^{{\rm expo}}_{\beta}(P)$ $\displaystyle=\sum_{i\in{\cal
N}}\overline{u}_{i}(P)-\beta\sqrt{\sum\limits_{j\in{\cal
I}}\Big{(}e_{j}(P)-\frac{{|{\cal N}|}}{{|{\cal I}|}}\left\lVert
v\right\rVert_{1}\Big{)}^{2}}$ (34)

In one-sided recommendation, parity of exposure is relatively well behaved
because the exposure target $\frac{{|{\cal N}|}}{{|{\cal I}|}}\left\lVert
v\right\rVert_{1}$ is constant. Driving towards equality can thus not lead to
a decrease of the total exposure budget, which was the problem with equality
of utility in settings with two-sided preferences (driving towards equality of
utility leads to a decrease of total utility), as we described in Section 3.

The formula allows us to extend parity of exposure in the next section and in
our experiments, since it is also valid in reciprocal recommendation.
Likewise, the formula of quality-weighted exposure that is also valid in
reciprocal recommendation is given by:

$\displaystyle F^{\rm qua}_{\beta}(P)=\sum_{i\in{\cal
N}}\overline{u}_{i}(P)-\beta\sqrt{\sum\limits_{j\in{\cal
I}}\Big{(}e_{j}(P)-\frac{q_{j}E}{Q}\Big{)}^{2}}.$

The result below shows that equality of exposure and quality-weighted exposure
lead to inefficiencies in reciprocal recommendation settings:

######  Proposition 8.

For every $n\in\mathbb{N}_{*}$, there is a reciprocal recommendation task with
$n$ users such that:

$\displaystyle\forall\theta\in\Theta,\exists\beta>0:$
$\displaystyle{\boldsymbol{u}}^{\theta}\succ_{\rm L}{\boldsymbol{u}}^{{\rm
expo},\beta}$ and $\displaystyle{\boldsymbol{u}}^{\theta}\succ_{\rm
L}{\boldsymbol{u}}^{{\rm qua},\beta}.$ (35)

Moreover, $\displaystyle\lim_{\beta\rightarrow\infty}\sum_{i\in{\cal
N}}u_{i}^{{\rm expo},\beta}=\frac{2}{n}\sum_{i\in{\cal N}}u_{i}^{\theta}$ and
$\displaystyle\lim_{\beta\rightarrow\infty}\sum_{i\in{\cal N}}u_{i}^{{\rm
qua},\beta}=\frac{2+n}{2n}\sum_{i\in{\cal N}}u_{i}^{\rm sum}$.

###### Proof.

An example of extreme case is with $n$ users when there is a “leader” who is
the only possible match with other users. We consider a single recommendation
slot. The preferences are:

$\displaystyle\forall j\in\\{2,\ldots,n\\},\mu_{1j}=\mu_{j1}=1$
$\displaystyle\forall(i,j)\in\\{2,\ldots,n\\}^{2},\mu_{ij}=0.$ (36)

On this task, the for every $\theta\in\Theta$, the optimal ranking is given
by:

$\displaystyle\forall j\in\\{2,\ldots,n\\},P_{1j}=\frac{1}{n-1}$
$\displaystyle\forall i\in\\{2,\ldots,n\\}P_{i1}=1.$ (37)

The reason it is the only possible optimal ranking is because it is leximin
optimal and has the maximum achievable sum of utilities. The utilities are
then $u_{1}(P)=n$ and $u_{i}(P)=1+\frac{1}{n-1}$, which leads to
$\sum_{i=1}^{n}u_{i}=2n$.

Equality of exposure Driving towards equality of exposure requires to reduce
the exposure of user $1$, which in turn reduces the utility of user $1$ and
the utilities of those who user 1 is less exposed to. Thus, there is $\beta>0$
such that ${\boldsymbol{u}}^{\theta}\succ_{\rm L}{\boldsymbol{u}}^{{\rm
expo},\beta}$ because of the loss of efficiency. Finally, by the concavity of
the objective with respect to $P$, and by the symmetry of the problem with
respect to $i_{2},\ldots,i_{n}$, we can conclude that an optimal way to
achieve perfect equality of exposure is to recommend, to every user $i$, every
user $j\neq i$ with probability $\frac{1}{n-1}$. The utility is then
$u_{1}(P)=1+(n-1)\frac{1}{n-1}$ and $u_{i}(P)=\frac{2}{n-1}$ for $i\geq 2$,
leading to $\sum_{i=1}^{n}u_{i}=4$, which gives the result.

Quality-weighted exposure On the same example, the qualities are $q_{1}=n-1$
and $q_{i}=1$ for $1\geq 2$. The total exposure targets are then
$t_{1}=\frac{1}{2}n$ and $t_{i}=\frac{n}{2(n-1)}$. These exposure targets mean
less exposure for $1$ than in the leximin ranking. Thus $\beta$ sufficiently
large has the effect of reducing $1$’s exposure141414Direct calculations of
the derivatives show that when $\beta>0$ is too small the penalty has no
effect., which reduces the utility of $1$ and the users to whom $1$ is less
recommended. Thus ${\boldsymbol{u}}^{\theta}\succ_{\rm
L}{\boldsymbol{u}}^{{\rm qua},\beta}$. By the symmetry of the problem, as
$\beta\to\infty$, quality weighted exposure is achieved by setting:

$\displaystyle\forall j\in\\{2,\ldots,n\\}:P_{1j}$
$\displaystyle=\frac{1}{n-1}$ $\displaystyle P_{j1}=\frac{n}{2(n-1)}$ (38)
$\displaystyle\forall j^{\prime}\in\\{2,\ldots,n\\},j^{\prime}\neq
j,P_{jj^{\prime}}$
$\displaystyle=\frac{1-\frac{n}{2(n-1)}}{n-2}=\frac{1}{2(n-1)}$ (39)

The utilities are then $u_{1}(P)=1+(n-1)\frac{n}{2(n-1)}=1+\frac{n}{2}$ and
$u_{i}(P)=\frac{n}{2(n-1)}+\frac{1}{n-1}=\frac{n+2}{2(n-1)}$. The total
utility is thus $2+n$, which gives the result. ∎

The Lorenz efficiency of our welfare approach guarantees that it cannot
exhibit the undesirable behaviors of parity or quality-weighted exposure
penalties described in Propositions 2 and 8.

Figure 5: Left: Example of a reciprocal recommendation task where equality of
utility leads to $0$ utility (see the proof of Prop. 3 in App. D). There is
one recommendation slot per user. We give the recommendation probabilities and
utilities for the utilitarian ranking and three users, the other ones are
obtained by the symmetry of the problem. The utilitarian ranking is also
leximin optimal, so our approach yields the same recommendations for all
$\theta$. Right: Example where quality-weighted exposure reduces user utility
while increasing inequalities between items.

##  Appendix E A generic Frank-Wolfe algorithm for ranking

In this section, we present a general form of our algorithm presented in
Section 4, as well as the proofs of the claims.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$, concave, and we want to find

$P^{*}\in\operatorname*{argmax}_{P\in\mathcal{P}}F({\boldsymbol{u}}(P)).$ (40)

Let $\langle X\,|\,\mathopen{}Y\rangle=\sum_{ijk}X_{ijk}Y_{ijk}$ be the dot
product between three-way tensors, and let $\nabla(F\circ{\boldsymbol{u}})(P)$
be the gradient of $P\mapsto F({\boldsymbol{u}}(P))$ taken at $P$, i.e.,
$(\nabla(F\circ{\boldsymbol{u}}))_{ijk}=\frac{\partial
F\circ{\boldsymbol{u}}missing}{\partial P_{ijk}}$

Starting from $P^{(0)}\in\mathcal{P}$ (in our experiments we always use a
utilitarian ranking
$P^{(0)}\in\operatorname*{argmax}_{P\in\mathcal{P}}\sum_{i=1}^{n}u_{i}(P)$),
the Frank-Wolfe algorithm alternates two steps for $t\geq 1$:

  1. 1.

let $\tilde{P}\in\operatorname*{argmax}_{P\in\mathcal{P}}\langle
P\,|\,\mathopen{}\nabla(F\circ{\boldsymbol{u}})(P^{t-1})\rangle$

  2. 2.

$P^{(t)}=(1-\gamma^{(t)})P^{(t-1)}+\gamma^{(t)}\tilde{P}$ with
$\gamma^{(t)}=\frac{2}{t+2}$

The stepsize $\frac{2}{t+2}$ is from Clarkson [13, Section 3], which avoids a
line search and in our experiments seemed to yield acceptable results.
Irrespective of the step size, the fundamental results which allows to use
Frank-Wolfe in the setting of (40) are the two following lemmas:

######  Lemma 2.

Recall that $u_{i}(P)=\sum_{i=1}^{n}\mu_{ij}(P_{ij}+P_{ji})v$. Let
$\frac{\partial F}{\partial u_{i}}$ denote the derivative of $F$ with respect
to its $i$-th argument and $\frac{\partial F}{\partial
u_{i}}({\boldsymbol{u}}(P))$ the value of this derivative at
${\boldsymbol{u}}(P)$.

Then, $\forall i\in{\cal N},\forall j\in{\cal I},\forall k\in[\\![{|{\cal
I}|}]\\!]$, we have:

$\displaystyle\frac{\partial F\circ{\boldsymbol{u}}missing}{\partial
P_{ijk}}(P)=\Big{(}\mu_{ij}\frac{\partial F}{\partial
u_{i}}\big{(}{\boldsymbol{u}}(P)\big{)}+\mu_{ji}\frac{\partial F}{\partial
u_{j}}\big{(}{\boldsymbol{u}}(P)\big{)}\Big{)}v_{k}.$ (41)

###### Proof.

The result is a consequence of the chain rule:

$\displaystyle\frac{\partial F\circ{\boldsymbol{u}}missing}{\partial
P_{ijk}}(P)=\sum_{p=1}^{n}\frac{\partial F}{\partial
u_{p}}({\boldsymbol{u}}(P))\frac{\partial u_{p}(P)}{\partial P_{ijk}}$ (42)

With

$u_{p}(P)=\sum_{q=1}^{n}\mu_{pq}\sum_{r=1}^{{|{\cal
I}|}}(P_{pqr}+P_{qpr})v_{k}.$ (43)

Thus $\frac{\partial u_{p}(P)}{\partial
P_{ijk}}=(\mu_{ij}\mathbbm{1}_{\\{p=i\\}}+\mu_{ji}\mathbbm{1}_{\\{p=j\\}})v_{k}$,
which gives the desired result. ∎

######  Lemma 3.

Let $A$ be an $n\times n$ matrix with $A_{ij}\in\mathbb{R}$ (not necessarily
non-negative). Let $v\in\mathbb{R}^{{|{\cal I}|}}$ with non-negative and non-
increasing entries, i.e., $\forall k\in[\\![{|{\cal I}|}-1]\\!]$, $v_{k}\geq
v_{k-1}\geq 0$. Let $K$ be the last index such that $v_{K}>0$ (or $K={|{\cal
I}|}$ if there is no such index).

Let $P\in\mathcal{P}$ such that:

$\forall
i,\forall\sigma_{i}\in\mathfrak{S}(P_{i}),\forall(j,j^{\prime})\in{\cal
I}^{2}:~{}~{}\Big{(}\sigma_{i}(j)\leq
K\text{~{}and~{}}\sigma_{i}(j)<\sigma_{i}(j^{\prime})\implies A_{ij}\geq
A_{ij^{\prime}}\Big{)}.$ (44)

And let $X$ be the $n\times n\times{|{\cal I}|}$ tensor defined as
$X_{ijk}=A_{ij}v_{k}$.

Then $P\in\operatorname*{argmax}_{P\in\mathcal{P}}\langle
P\,|\,\mathopen{}X\rangle$.

Moreover, if $\forall k\in[\\![{|{\cal I}|}-1]\\!]$, $v_{k}>v_{k-1}\geq 0$,
then for every $P\in\operatorname*{argmax}_{P\in\mathcal{P}}\langle
P\,|\,\mathopen{}X\rangle$, we have:

$\forall
i,\forall\sigma_{i}\in\mathfrak{S}(P_{i}),\forall(j,j^{\prime})\in{\cal
I}^{2}:~{}~{}\Big{(}\sigma_{i}(j)<\sigma_{i}(j^{\prime})\implies A_{ij}\geq
A_{ij^{\prime}}\Big{)}.$ (45)

###### Proof.

The result stems from the rearrangement inequality (also known as the Hardy-
Littlewood inequality [23]), which states that for two vectors
$a\in\mathbb{R}_{+}^{n}$, and $b\in\mathbb{R}^{n}$,
$\operatorname*{argmax}_{\nu}\sum_{j=1}^{n}a_{\nu(j)}b_{j}$, where $\nu$ spans
the permutations of $[\\![n]\\!]$, is the set of permutations such that $b$ is
ordered similarly to $(a_{\nu(i)})_{i=1}^{n}$. If the $a_{k}$s are non-
increasing, then every permutation that sorts $b$ in decreasing order is in
the argmax. We need the reciprocal statement for the second part of our Lemma:
if the $a_{i}$s are strictly decreasing, then only the permutations that sort
$b$ in decreasing order are in
$\operatorname*{argmax}_{\nu}\sum_{j=1}^{n}a_{\nu(j)}b_{j}$. Note that these
arguments are well-known in learning to rank [see, e.g., 14].

In our case, notice that

$\langle P\,|\,\mathopen{}X\rangle=\sum_{i\in{\cal N}}\Big{(}\sum_{j\in{\cal
I}}A_{ij}P_{ijk}v_{k}\Big{)}$ (46)

The maximization over $P$ can then be performed over each user $i$ (and thus
each bistochastic matrix $P_{i}$ separately). Now, if $P_{i}$ is such that
every $\sigma_{i}\in\mathfrak{S}(P_{i})$ orders $A_{ij}$ in decreasing order,
then by the rearrangement inequality
$\sigma_{i}\in\operatorname*{argmax}_{\nu}\sum_{j\in{\cal
I}}A_{ij}v_{\nu(j)}$. Notice that if only the $K$ first elements of $v$ are
non-zero, we only need a top-$K$ ranking. This gives us the first part of the
thoerem.

The second part of the theorem follows from the reciprocal of the
rearrangement inequality, since for $P_{i}$ to be an optimal stochastic
ranking for $\sum_{j\in{\cal I}}A_{ij}P_{ijk}v_{k}$, every permutation
$\sigma_{i}$ in its support must be in
$\operatorname*{argmax}_{\nu}\sum_{j\in{\cal I}}A_{ij}v_{\nu(j)}$. ∎

###  E.1 Proof of Theorem 1

Lemma 2 and 3 together are sufficient to give algorithms for the inference of
stochastic rankings using our welfare function (3) and using the penalties of
Section 3, by computing the partial derivatives $\frac{\partial F}{\partial
u_{i}}$. The main result of Section 4, which we prove now, instantiates this
principle for the welfare function approach: See 1

###### Proof.

Notice that with
$W(P)=F({\boldsymbol{u}}(P))=\sum_{i=1}^{n}\Phi_{i}(u_{i}(P))$, then
$\frac{\partial F}{\partial
u_{i}}({\boldsymbol{u}}(P))=\Phi_{i}^{\prime}(u_{i}(P))$. By Lemma 2, we have
that $\langle P\,|\,\mathopen{}\nabla F(P^{(t}\rangle)$ is of the form
$\langle P\,|\,\mathopen{}X\rangle$ with $X_{ijk}=A_{ij}v_{k}$ with
$A_{ij}=\tilde{\mu}_{ij}$, so the result is implied by Lemma 3. ∎

###  E.2 Proof of Proposition 4

See 4

###### Proof.

Note that $\mathcal{P}$ is a simplex over ranking tensors containing one
deterministic ranking for each user. Using [13, Section 3], the Frank-Wolfe
algorithm with our step-size converges in $O\big{(}\frac{C_{W}}{t}\big{)}$,
where, using [13, Equation 11] and denoting by $\nabla^{2}W$ the Hessian of
$W$, we have

$\displaystyle C_{W}$
$\displaystyle\leq\sup\limits_{\begin{subarray}{c}{\boldsymbol{u}},{\boldsymbol{u^{\prime}}}\in{\cal
U}\\\ \tilde{\bf u}\in{\cal
U}\end{subarray}}-\frac{1}{2}({\boldsymbol{u}}-{\boldsymbol{u^{\prime}}})^{\top}\nabla^{2}W(\tilde{\bf
u})({\boldsymbol{u}}-{\boldsymbol{u^{\prime}}})\leq\frac{B}{2}\sup\limits_{{\boldsymbol{u}},{\boldsymbol{u^{\prime}}}\in{\cal
U}}\left\lVert{\boldsymbol{u}}-{\boldsymbol{u^{\prime}}}\right\rVert^{2}_{2}\leq
2BU.$ (47)

where we used
$\left\lVert{\boldsymbol{u}}-{\boldsymbol{u^{\prime}}}\right\rVert_{2}^{2}\leq
2\left\lVert{\boldsymbol{u}}\right\rVert_{2}^{2}+2\left\lVert{\boldsymbol{u^{\prime}}}\right\rVert_{2}^{2}$.

For the computation cost, we use Lemma 3, which is more precise than Theorem
1, to see that finding the argmax only requires a top-$K$ ranking. While
technically any $P\in\mathcal{P}$ should contain a whole bistochastic matrix,
it is not necessary to store a completion of the top-$K$ rankings because they
have no impact on the utility. As such, storing each $\tilde{P}$ only costs
$O(K)$ bytes per user, which contain the indices of the top-K items in the
ranking found by Theorem 2.

Computing the two-sided utilities costs $O({|{\cal N}|}{|{\cal I}|})$, and
thus $O({|{\cal I}|})$ per user. Moreover, computing the top-K ranking costs
$O({|{\cal I}|}\ln K)$ in the worst case, with a streaming method that
maintains a min-heap of the top-K elements seen so far, and finish with
sorting the top-$K$ elements. ∎

Notice that for faster average performance, the top-K sort can be performed
using a fast selection algorithm (such as quickselect), to obtain the top-$K$
elements with $O({|{\cal I}|})$ expected time complexity, and then sorting,
yielding $O({|{\cal I}|}+K\ln K)$ expected time complexity per user at each
iteration.

##  Appendix F Additional experimental results

Our experiments are fully implemented in Python 3.9 using
PyTorch151515http://pytorch.org. We provide the code as supplementary
material. We compare our welfare maximization approach with the fairness
penalties presented in Section 3.

We also compare ourselves to the algorithm FairRec from Patro et al. [47]
(referred to as Patro et al. in the figures and description), who consider
envy-freeness as user-side fairness criterion, and max-min share of exposure
as item-side fairness criterion. Envy-freeness states that every user should
prefer their recommendation list to that of any other user. The max-min
exposure criterion on the item side means that each user should receive an
exposure of at least $\beta\frac{E}{{|{\cal I}|}},$ where $\beta$ is a
parameter allowing to control how much exposure is guaranteed to items. We
vary this parameter in our experiments to show the trade-offs achieved by
Patro et al.. Since Patro et al. does not produce rankings, we took the
recommendation list with the given order as a ranked list.

###  F.1 One-sided recommendation: Lastfm-2k dataset

We describe in this section the details of the experiments presented in
Section 5.1. We use a dataset from the online music service
Last.fm161616https://www.last.fm/. In the main paper, we presented results on
Lastfm-2k from Cantador et al. [9] which contains real play counts of $2k$
users for $19k$ artists, and was used by Patro et al. [47] who also study two-
sided fairness in recommendation. We filter the top $2,500$ items most
listened to. Following [32], we pre-process the raw counts with
$\log$-transformation. We split the dataset into train/validation/test sets,
each including $70\%/10\%/20\%$ of the user-item play counts. We create three
different splits using three random seeds. One-sided preferences are estimated
using the standard matrix factorization algorithm171717Using the Python
library Implicit: https://github.com/benfred/implicit (MIT License). of Hu et
al. [29] trained on the train set, with hyperparameters selected on the
validation set by grid search. The number of latent factors is chosen in
$[16,32,64,128]$, the regularization in $[0.1,1.,10.,20.,50.]$, and the
confidence weighting parameter in $[0.1,1.,10.,100.]$. The estimated
preferences we use are the positive part of the resulting estimates.

Rankings are inferred from these estimated preferences. The exposure weights
we use in the computation of utilities are the standard weights of the
_discounted cumulative gain_ (DCG) (also used in e.g., [54, 7, 42]): $\forall
k\in[\\![{|{\cal I}|}]\\!],v_{k}=\frac{1}{\log_{2}(1+k)}$. For each ranking
approach, the Frank-Wolfe algorithm is run with $5000$ iterations to make sure
we are close to convergence, and the number of recommendation slots is set to
$40$.

We evaluate rankings on estimated preferences, considered as ground truth,
following many works on fair recommendation [54, 47, 60, 63]. This is because
the goal is to evaluate the fairness of ranking algorithms themselves, rather
than biases in preference estimates. All results are averaged over three
random seeds. To obtain various trade-offs, for welf we vary $\lambda$ in
$[0.001,0.01,0.05,0.075,0.1,0.125,0.15,0.2,0.3,0.325,0.35]$ and
$[0.4,0.45,0.5,0.55,0.6,0.65,0.7,0.75,0.8,0.9,0.95,0.99,0.999]$. For Patro et
al. we vary $\beta$ in $[0.01,0.05,0.1,0.15,0.2,0.25,0.3,0.35,0.4]$ and
$[0.45,0.5,0.55,0.6,0.65,0.7,0.75,0.8,0.85,0.9,0.95,1]$, and for other methods
we vary $\beta$ in
$[0.001,0.005,0.01,0.015,0.0175,0.02,0.025,0.03,0.035,0.04,0.045,0.05,0.055,0.06]$
and
$[0.065,0.07,0.075,0.08,0.085,0.09,0.095,0.1,0.105,0.11,0.2,0.5,1,2,5,10,20,30,40,50,70,100]$.

#### Item-side fairness

Figure 6 presents the various trade-offs achieved by each method in one-sided
recommendation, as discussed in Section 5.1. We observe that only
qua.-weighted is unable to reach equal exposure because of its quality-
weighted exposure target: perfectly equal exposure is only permitted when all
items have the same quality.

#### Two-sided fairness

Figure 7 shows the effect of varying $\alpha_{1}$ and $\lambda$ on user
fairness as in Figure 3 of the main paper, but with results repeated over
three random seeds. We observe the same trade-offs and conclude again that
welf is better than Patro et al. and eq. exposure, in terms of its impact on
worse-off users.

#### The importance of considering the whole Lorenz curve

In Fig. 8 we show the results of the same models as before, but changing the
way we measure the item inequality: using the standard deviation of exposure
rather than the Gini index. Now, eq. exposure dominates the total utility/item
inequality plot, since the plot corresponds exactly to the objective function
of the algorithm. Comparing eq. exposure with welf $\alpha_{1}=1$, we now see
that the trade-offs are different, with eq. exposure performing better on the
worse-off users. Comparing welf $\alpha_{1}=0$ and Patro et al., we see that
they still exhibit similar behaviors, with welf $\alpha_{1}=0$ being better
for better off users. Finally, welf $\alpha_{1}=-2$ still dominates the othe
methods in terms of performance on the worse-off users.

(a) Welfare (ours)

(b) Patro et al.

(c) eq. exposure

(d) qua.-weighted

Figure 6: representative trade-offs achieved by the various compared methods
on Lastfm-2k. The trade-offs achieved by the different methods look alike,
except that qua.-weighted does not aim at reaching equality of exposure for
exteme values of $\beta$. See Section 5.1 for the discussions on the
differences between the trade-offs achieved by the different approaches.

(a) Total user utility.

(b) User inequality.

(c) Cumulative utility for 10% worse-off users

(d) Cumulative utility for 25% worse-off users

Figure 7: Focus on user fairness on Lastfm-2k: effect of varying $\alpha_{1}$
(user-side curvature of the welfare function) keeping $\alpha_{2}=0$. The
figure shows all the results obtained with a repetition of three seeds.
Overlapping points correspond to the same model parameter across different
seeds. We can see that the variance is negligible compared to the observed
differences.

(a) Total user utility.

(b) User inequality.

(c) Cumulative utility for 10% worse-off users

(d) Cumulative utility for 25% worse-off users

Figure 8: Focus on user fairness on Lastfm-2k, measuring item inequality with
standard deviation rather than Gini index. We observe a similar relative
behavior between welf and Patro et al., but now equality of exposure is
optimal on the total utility/item inequality trade-off since it corresponds
exactly to the objective of the algorithm. Nonetheless, welf $\alpha_{1}=-2$
still obtains higher performance on 10%-25% worse-off users, showing that welf
offers a larger range of trade-offs than eq. exposure.

###  F.2 One-sided recommendation: Lastfm-15k dataset

We replicate the experiments on a larger dataset to verify our conclusions at
a larger scale. We consider another Lastfm dataset from Celma [11], which
includes $360k$ users and $180k$ items (artists). We select the top $15,000$
users and items having the most interactions, so we refer to this dataset as
Lastfm-15k. We apply exactly the same experimental protocol as for Lastfm-2k,
with the same range of hyperparameters for the different methods.

#### Results

Fig. 11 and 10 show the results obtained by welf, Patro et al. and eq.
exposure. The conclusions are similar to those on Lastfm-2k, with the results
of welf $\alpha=0$ being more uniformly better than those of Patro et al.,
even though overall similar. welf $\alpha_{1}=-2$ dominates in terms of user
utility on worse-off users. welf and eq. exposure still find different trade-
offs, with welf dominating eq. exposure when inequality between items is
measured by the Gini index, and eq. exposure dominating welf when inequality
is measured by the standard deviation.

(a) Total user utility.

(b) User inequality.

(c) Cumulative utility for 10% worse-off users

(d) Cumulative utility for 25% worse-off users

Figure 9: Results on Lastfm-15k when measuring the inequality between items
with the Gini coefficient.

(a) Total user utility.

(b) User inequality.

(c) Cumulative utility for 10% worse-off users

(d) Cumulative utility for 25% worse-off users

Figure 10: Results on Lastfm-15k when measuring inequalities between items
with the standard deviation.

###  F.3 One-sided recommendation: Movielens dataset

We provide additional results on the MovieLens-20m dataset [24], which
contains ratings on a 5-star scale of movies by real users. To simulate a
collaborative filtering task with implicit feedback similar to Last.fm, we
consider missing ratings as negative feedback and the task is to predict
positive values. Since ratings $<3$ are usually considered as negative [38,
61], we set ratings $<3$ to zero, resulting in a dataset with preference
values among $\\{0,3,3.5,4,4.5,5\\}$. As for Lastfm-15k, we select the top
$15,000$ users and items with the most interactions. For the inference and
evaluation of rankings, we follow the same protocols as for Last.fm.

The experimental protocol is the same as for Lastfm-2k and Lastfm-15k except
that we do not run the algorithm by [47] because its runtime was prohibitive.

#### results

The results are qualitatviely similar to those on Lastfm-2k and Lastfm-15k
except that the trends are magnified. welf $\alpha=1$ and eq. exposure seem
more similar, with welf $\alpha=0$ dominating the trade-off total utility/item
iniequality when item inequality is measured with the Gini index, and eq.
exposure dominating this trade-off when item inequality is measured with
standard deviation. welf $\alpha=-2$ has great performance on worse-off users
compared to eq. exposure or welf with larger $\alpha$, but also comes at a
significant cost in terms of total user utility, which is very rapidly driven
down.

(a) Total user utility.

(b) User inequality.

(c) Cumulative utility for 10% worse-off users

(d) Cumulative utility for 25% worse-off users

Figure 11: Results on Movielens when measuring the inequality between items
with the Gini coefficient.

(a) Total user utility.

(b) User inequality.

(c) Cumulative utility for 10% worse-off users

(d) Cumulative utility for 25% worse-off users

Figure 12: Results on Movielens when measuring inequalities between items with
the standard deviation.

###  F.4 Reciprocal recommendation: Twitter-13k dataset

We now provide the full details of the experiments on Twitter presented in
Section 5.2 of the main body. Given the lack of common benchmark for
reciprocal recommendation [45], we generate a reciprocal recommendation task
for people-to-people recommendation problems based on the social network
Twitter. We use the Higgs Twitter-13k dataset which includes (directed)
follower relationships between users.181818It was collected following the
discovery of the Higgs boson in July, 2012. We keep users having at least $20$
mutual follows, resulting in a subset of $13$k users. We use the directed
links to estimate the probability $\phi_{ij}$ that $i$ follows $j$, and the
(symmetric) probability of a mutual follow, which is
$\mu_{ij}=\phi_{ij}\times\phi_{ji}$. As in the experiments for one-sided
recommendation, we split the dataset into train/validation/test sets, each
including $70\%/10\%/20\%$ of the _directed_ follower links. We create three
random uniform splits, corresponding to three different seeds.

Estimates $\hat{\phi}_{ij}$ are built with logistic matrix
factorization191919Using the Python library Implicit (MIT License). [32]
trained on the train set with hyperparameter selection on the validation set.
The number of latent factors is chosen in $[16,32,64,128]$, the regularization
in $[0.1,1.,10.,20.,50.]$, and the confidence weighting parameter in
$[0.1,1.,10.,100.]$. Rankings are inferred from all estimated mutual
preferences $\hat{\mu}_{ij}=\max(\hat{\phi}_{ij}\hat{\phi}_{ji},0)$. For each
ranking method, the Frank-Wolfe algorithm is run with $5000$ iterations, and
the number of recommendation slots is set to $40$. As for one-sided
recommendation, rankings are estimated on estimated mutual preferences taken
as ground truth.

We generate different trade-offs with welf by varying $\alpha$ in
$[0.99,0.9,0.75,0.5,0.25,0,-0.25,-0.5,-0.6,-0.7,-0.8,-0.9,-1.0]$,
$[-1.1,-1.25,-1.5,-1.75,-2.0,-2.5,-3,-5,-10,-15,-16,-17,-18]$. For all other
methods, we vary $\beta$ in
$[0.01,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1,1.1,1.25,1.5,2,5,10,50,100]$.

All presented results are obtained by averaging performance over the three
seeds.

#### Results

Figure 13 presents the trade-offs achieved by the different methods on
Twitter-13k. As expected, qua.-weighted and eq. exposure do not exhibit a good
behavior: stronger penalties lead to more dominated curves where the utility
of every user is decreased. This is because constraining item exposure is not
meaningful in reciprocal recommendation, where the relevant utility is the
two-sided utility. The trade-offs achieved by the welf and eq. utility are
different. Equal utility rapidly generates near-flat curves without really
focusing on the very first users, while welf increases the utility of the
worst-off users while keeping the total utility relatively high.

(a) Welfare (ours)

(b) eq. utility

(c) eq. exposure

(d) qua.-weighted

Figure 13: representative trade-offs achieved by the various compared methods
on Twitter-13k. Exposure-based approaches (qua.-weighted and eq. exposure) do
not yield interesting trade-offs as they are unable to increase the utility of
worse-off users. The trade-offs achieved by the welf and eq. utility are
different. Equal utility rapidly generates near-flat curves without really
focusing on the very first users, while welf increases the utility of the
worst-off users while keeping the total utility relatively high.

###  F.5 Reciprocal recommendation: Epinions dataset

We present additional experiments on reciprocal recommendation with the
Epinions dataset [49]. Epinions.com is a consumer review site with a who-
trust-whom network, and the dataset gathers (directed) trust relationships
between members of the platform. Here, we consider the task of finding mutual
trust links. We keep users having at least $20$ mutual trust links, resulting
in a subset of $800$ entities. For the inference and evaluation of rankings,
we use the same protocols as for the Twitter experiments described in the
previous subsection. The experimental parameters are the same as for the
Twitter-13k dataset.

(a) Welfare (ours)

(b) eq. utility

(c) eq. exposure

(d) qua.-weighted

Figure 14: representative trade-offs achieved by the various compared methods
on Epinions. The results are qualitatively similar to those on Twitter-13k.

(a) Example trade-offs achieved by welf.

(b) welf dominates exposure-based methods.

(c) welf dominates eq. utility near strict equality.

(d) Total utility vs inequality.

(e) Total utility vs utility of 10% worse-off users.

(f) Total utility vs utility of 25% worse-off users.

(g) Total utility vs utility of 50% worse-off users.

Figure 15: Results on the epinions dataset.

#### Results

Figure 14 presents the trade-offs achieved by the different methods on
Epinions. As expected, qua.-weighted and eq. exposure do not exhibit a good
behavior: stronger penalties lead to more dominated curves where the utility
of every user is decreased. In Figure 15 plots the equivalent of Fig. 4. The
results are similar: all of qua.-weighted, eq. exposure and eq. utility have
dominated curves. We also observe that in the more interesting region where we
are closer to the maximum achievable utility, welf optimizes better the
utility of worse-off users. Yet, in that region, there is no strict dominance
of welf over eq. utility.

##  Appendix G Pairwise vs pointwise penalties

Our penalty-based approach uses the penalty $\sqrt{D({\boldsymbol{u}})}$ with:

$D({\boldsymbol{u}})=\sum_{j\in{\cal I}}\Big{(}u_{j}-\frac{1}{{|{\cal
I}|}}\sum_{j^{\prime}\in{\cal I}}u_{j^{\prime}}\Big{)}^{2}.$ (48)

Some authors use $D^{\prime}({\boldsymbol{u}})=\sum_{(j,j^{\prime})\in{\cal
I}^{2}}|u_{j}-u_{j}^{\prime}|$ instead of $\sqrt{D({\boldsymbol{u}})}$ [55,
42, 6], but it is less computationally efficient than our penalty because it
involves a quadratic number of terms.

The penalties are similar in that they are related to well-known measures of
inequalities:

  * •

$\frac{D^{\prime}({\boldsymbol{u}})}{2{|{\cal I}|}\sum_{j\in{\cal I}}u_{j}}$
is the Gini index of ${{\boldsymbol{u}}}_{{\cal I}}$ [19], which, up to an
affine transform is the area under the Lorenz curve.

  * •

$D({\boldsymbol{u}})$, which is (up to a constant) the variance of
${{\boldsymbol{u}}}_{{\cal I}}$ is part of the family of additively
decomposable inequality measures [52]. We use $\sqrt{D({\boldsymbol{u}})}$ to
scale the penalty with the sum of users’ utilities.

Note that $\sqrt{D({\boldsymbol{u}})}$ and $D^{\prime}({\boldsymbol{u}})$ have
the same dependency to the overall scale of the utilities (i.e., multiplying
all utilities by a constant factor has the effect of multiplying both
penalties by the same factor). Since both penalties drive towards equality, it
is straightforward to show that the results of Section 3 as $\beta\to\infty$
also apply to $D^{\prime}({\boldsymbol{u}})$.

##  Appendix H Exposure constraints at the level of every ranking

The notions of fairness of exposure are sometimes defined with item-side
constraints defined at the level of _every ranking_ [54, 6]. We give here the
examples of constraints for equality of exposure and quality-weighted
exposure:

$\displaystyle\begin{subarray}{c}\text{equality of}\\\
\text{exposure}\end{subarray}$ $\displaystyle P^{\rm
expo}\in\operatorname*{argmax}_{P\in\mathcal{P}}\sum_{i\in{\cal N}}u_{i}(P)$
$\displaystyle\text{u.c.~{}~{}}\forall(i,j)\in{\cal N}\times{\cal
I},P_{ij}v=\frac{\left\lVert v\right\rVert_{1}}{{|{\cal I}|}}$ (49)
$\displaystyle\begin{subarray}{c}\text{quality-weighted}\\\
\text{exposure}\end{subarray}$ $\displaystyle P^{\rm
qua}\in\operatorname*{argmax}_{P\in\mathcal{P}}\sum_{i\in{\cal N}}u_{i}(P)$
$\displaystyle\text{u.c.~{}~{}}\forall(i,j)\in{\cal N}\times{\cal
I},P_{ij}v=\frac{\mu_{ij}\left\lVert
v\right\rVert_{1}}{\sum_{j^{\prime}\in{\cal I}}\mu_{ij^{\prime}}}$ (50)

The advantage of this formulation is that it leads to optimization problems
that can be solved locally for every user, since there is no dependency
between user rankings through item utility anymore.

However, applying the exposure criterion at the level of every ranking
effectively applies a different notion of fairness. In our setting, this
corresponds to defining a separate recommendation task for every user, i.e.,
taking ${|{\cal N}|}=1$. The welfare function then mediates, within a single
ranking, between the user utility and the utility of the different items.

When evaluated on exposures aggregated over all users, as we do in the paper,
applying the fairness constraints at the level of individual rankings can lead
to drastic reductions of user utility for no benefit in terms of total item
exposure. This is summarized in the following result, which shows that there
exists problems for which the optimal rankings for every $\theta\in\Theta$
satisfy the constraints of equality of exposure and quality-weighted exposure
as we define them in Section 3, but when applying the constraints at the level
of every ranking, it has the effect of reducing user utility. In the
proposition, we use the notation of the objective function for parity of
exposure $F_{\beta}$ and $F^{\rm qua}_{\beta}$ of Section 3.

######  Proposition 9.

For every $d\in\mathbb{N}_{*}$ and every $N\in\mathbb{N}_{*}$, there is a one-
sided recommendation task with $d+1$ items and $N(d+1)$ users such that,
$\forall\theta\in\Theta$:

$\forall{\boldsymbol{u}}^{\theta}\in\operatorname*{argmax}_{{\boldsymbol{u}}\in{\cal
U}}W_{\theta}({\boldsymbol{u}})$, $\forall\beta>0$ we have:
${\boldsymbol{u}}^{\theta}\in\operatorname*{argmax}\limits_{{\boldsymbol{u}}\in{\cal
U}}F_{\beta}({\boldsymbol{u}})$ and
${\boldsymbol{u}}^{\theta}\in\operatorname*{argmax}\limits_{{\boldsymbol{u}}\in{\cal
U}}F^{\rm qua}_{\beta}({\boldsymbol{u}})$, and

$\displaystyle\sum\limits_{i\in{\cal N}}u_{i}(P^{\rm
expo})=\frac{2}{d+1}\sum\limits_{i\in{\cal N}}u_{i}^{\theta}$ and
$\displaystyle\sum\limits_{i\in{\cal N}}u_{i}(P^{\rm
qua})=(\frac{1}{2}+\frac{1}{d})\sum\limits_{i\in{\cal N}}u_{i}^{\theta}.$ (52)

In other words, applying the constraints at the level of every ranking might
lead to a drastic decrease of user utilities, even in tasks where satisfying
the constraints on average over users (as we do in this paper) does not
conflict with the optimal ranking.

###### Proof.

We describe the problem with $N=1$, the general case is obtained by repeating
the preference pattern. Let us consider a task with $d+1$ users, $d+1$ items
and a single recommendation slot. Let $i_{1},\ldots,i_{d+1}$ be the user
indexes, and $j_{1},\ldots,j_{d+1}$ the item indexes. The preferences are
defined as:

$\displaystyle\forall k\in[\\![d+1]\\!],\mu_{i_{k}j_{k}}=1$
$\displaystyle\forall j\neq j_{k},\mu_{i_{k}j}=\frac{1}{d}.$ (53)

All items have the same quality. For every $\theta\in\Theta$,
${\boldsymbol{u}}^{\theta}$ is given by the utilitarian ranking, which gives
probability $1$ to item $j_{k}$ for user $i_{k}$, which leads to optimal user
utility $u_{i}^{\theta}=1$ and equal exposure to every item
$u_{j}^{\theta}=1$. Since the quality is the same for all items (equal to
$1+d\frac{1}{d}$), the ranking for ${\boldsymbol{u}}^{\theta}$ satisfies both
equality of exposure and quality-weighted exposure constraints. Thus, for
every $\beta>0$,
${\boldsymbol{u}}^{\theta}\in\operatorname*{argmax}_{{\boldsymbol{u}}\in{\cal
U}}F_{\beta}({\boldsymbol{u}})$ and
${\boldsymbol{u}}^{\theta}\in\operatorname*{argmax}_{{\boldsymbol{u}}\in{\cal
U}}F^{\rm qua}_{\beta}({\boldsymbol{u}})$.

On the other hand, satisfying equality of exposure at the level of every
ranking requires $P^{\rm expo}_{ij}=\frac{1}{d+1}$ for every user $i$ and item
$j$, which leads to $u_{i}(P^{\rm
expo})=\frac{1}{d+1}+d\times\frac{1}{d}\times\frac{1}{d+1}=\frac{2}{d+1}$ for
every user.

For quality-weighted exposure for every ranking, it leads to:

$\displaystyle\forall k\in[\\![d+1]\\!],P^{\rm qua}_{i_{k}j_{k}}=\frac{1}{2}$
$\displaystyle\forall j\neq j_{k},P^{\rm qua}_{i_{k}j}=\frac{1}{d}$ (54)

and thus a user utility $u_{i}(P^{\rm
qua})=\frac{1}{2}+d\times\frac{1}{d}\times\frac{1}{d}=\frac{1}{2}+\frac{1}{d}$.
∎

Notice that in the examples of the proof, the global exposure of items is
constant in $P^{\rm expo}$ and $P^{\rm qua}$, as well as in the ranking given
by optimal welfare. So from the point of view of our definitions of utility,
applying the constraints at the level of every ranking only decreased user
utility for the benefit of no items. Yet, we re-iterate that applying item-
side fairness at the level of every ranking might be meaningful in some
contexts. The goal of this section is to highlight the difference between
using global and local definitions of item utilities.