# Optimizing generalized Gini indices for fairness in rankings

Virginie Do<EMAIL_ADDRESS>Meta AI Research LAMSADE, Université Paris
Dauphine-PSL and  Nicolas Usunier<EMAIL_ADDRESS>Meta AI Research

(2022)

###### Abstract.

There is growing interest in designing recommender systems that aim at being
fair towards item producers or their least satisfied users. Inspired by the
domain of inequality measurement in economics, this paper explores the use of
generalized Gini welfare functions (GGFs) as a means to specify the normative
criterion that recommender systems should optimize for. GGFs weight
individuals depending on their ranks in the population, giving more weight to
worse-off individuals to promote equality. Depending on these weights, GGFs
minimize the Gini index of item exposure to promote equality between items, or
focus on the performance on specific quantiles of least satisfied users. GGFs
for ranking are challenging to optimize because they are non-differentiable.
We resolve this challenge by leveraging tools from non-smooth optimization and
projection operators used in differentiable sorting. We present experiments
using real datasets with up to $15$k users and items, which show that our
approach obtains better trade-offs than the baselines on a variety of
recommendation tasks and fairness criteria.

fairness, ranking, recommender systems, welfare economics

††copyright: acmcopyright††journalyear: 2022††copyright:
acmlicensed††conference: Proceedings of the 45th International ACM SIGIR
Conference on Research and Development in Information Retrieval; July 11–15,
2022; Madrid, Spain††booktitle: Proceedings of the 45th International ACM
SIGIR Conference on Research and Development in Information Retrieval (SIGIR
’22), July 11–15, 2022, Madrid, Spain††price: 15.00††doi:
10.1145/3477495.3532035††isbn: 978-1-4503-8732-3/22/07††ccs: Information
systems Retrieval models and ranking

##  1\. Introduction

Recommender systems play an important role in organizing the information
available to us, by deciding which content should be exposed to users and how
it should be prioritized. These decisions impact both the users and the item
producers of the platform. While recommender systems are usually designed to
maximize performance metrics of user satisfaction, several audits recently
revealed potential performance disparities across users (Sweeney, 2013; Datta
et al., 2015; Ekstrand et al., 2018; Mehrotra et al., 2017). On the side of
item producers, the growing literature on fairness of exposure aims to avoid
popularity biases (Abdollahpouri et al., 2019) by reducing inequalities in the
exposure of different items (Singh and Joachims, 2018), or aiming for equal
exposure weighted by relevance (Diaz et al., 2020; Biega et al., 2018; Morik
et al., 2020). In most cases, the approaches proposed for user- and item-side
fairness aim to reduce inequalities.

In this paper, we propose a new approach to fair ranking based on Generalized
Gini welfare Functions (GGFs, (Weymark, 1981)) from the economic literature on
inequality measurement (Cowell, 2000). GGFs are used to make decisions by
maximizing a weighted sum of the utilities of individuals which gives more
weight to those with lower utilities. By prioritizing the worse-off, GGFs
promote more equality.

The normative appeal of GGFs lies in their ability to address a multiplicity
of fairness criteria studied in the fair recommendation literature. Since GGFs
include the well-known Gini inequality index as a special case (Gini, 1921),
they can be used to optimize trade-offs between exposure inequality among
items and user utility, a goal seeked by many authors (Morik et al., 2020;
Zehlike and Castillo, 2020). GGFs also conveniently specify normative criteria
based on utility quantiles (Do et al., 2021): for instance, it is possible to
improve the utility of the $10\%$ worse-off users and/or items with GGFs,
simply by assigning them more weight in the objective. Moreover, using
techniques from convex multi-objective optimization, we show that GGFs cover
_all_ ranking policies that satisfy _Lorenz efficiency_ , a distributive
justice criterion which was recently introduced for two-sided fairness in
rankings (Do et al., 2021).

The difficulty of using GGFs as objective functions for fairness in ranking
stems from their non-differentiability, which leads to computational
challenges. Indeed, ranking with fairness of exposure requires the solution of
a global optimization problem in the space of (randomized) rankings of all
users, because the exposure of an item is the sum of its exposure to every
users. The Frank-Wolfe algorithm (Frank and Wolfe, 1956) was shown to be a
computationally efficient method for maximizing globally fair ranking
objectives, requiring only one top-$K$ sort operation per user at each
iteration (Do et al., 2021). However, vanilla Frank-Wolfe algorithms only
apply to objective functions that are differentiable, which is not the case of
GGFs.

We propose a new algorithm for the optimization of GGFs based on extensions of
Frank-Wolfe algorithms for non-smooth optimization (Lan, 2013; Yurtsever et
al., 2018; Thekumparampil et al., 2020). These methods usually optimize
smoothed surrogate objective functions, while gradually decreasing a smoothing
parameter, and a common smoothing technique uses the Moreau envelope (Moreau,
1962; Yosida et al., 1965). Our main insight is that the gradient of the
Moreau envelope of GGFs can be computed in $O(n\log n)$ operations, where $n$
is the number of users or items. This result unlocks the use of Frank-Wolfe
algorithms with GGFs, allowing us to efficiently find optimal ranking policies
while optimizing GGFs.

We showcase the performances of the algorithm on two recommendations tasks of
movies and music, and on a reciprocal recommendation problem (akin to dating
platforms, where users are recommended to other users), with datasets
involving up to $15k$ users and items. Compared to relevant baselines, we show
that our algorithm successfully yields better trade-offs in terms of user
utility and inequality in item exposure measured by the Gini index. Our
approach also successfully finds better trade-offs in terms of two-sided
fairness when maximizing the lower quantiles of user utility while minimizing
the Gini index of item exposure.

In the remainder of the paper, we first describe our recommendation framework.
We then present the family of generalized Gini welfare functions and its
relationship to previously proposed fairness criteria in ranking. In Sec. 3 we
provide the details of our algorithm and the convergence guarantees. Our
experimental results are reported in Sec. 4, and an extension to reciprocal
recommendation problems is discussed in Sec. 5. We position our approach with
respect to the related work in Sec. 6, and Sec. 7 concludes the paper and
discusses the limitations of our work.

##  2\. Fair ranking with Generalized Gini

###  2.1. Recommendation framework

We consider a recommendation scenario with $n$ users, and $m$ items, and $K$
recommendation slots. $\mu_{ij}\in[0,1]$ denotes the value of item $j$ for
user $i$ (e.g, a “liking” probability), and we assume the values $\mu$ are
given as input to the system. The goal of the system is to produce a ranked
list of items for each of the $n$ users. Following previous work on fair
rankings (e.g. Singh and Joachims, 2018), we consider randomized rankings
because they enable the use of convex optimization techniques to generate the
recommendations, which would otherwise involve an intractable combinatorial
optimization problem in the space of all users’ rankings. A _randomized
ranking_ for user $i$ is represented by a bistochastic matrix
$P_{i}\in\mathbb{R}^{m\times m},$ where $P_{ijk}$ is the probability that item
$j$ is recommended to user $i$ at position $k.$ The recommender system is
characterized by a _ranking policy_ $P=(P_{i})_{i=1}^{n}$. We denote the
convex set of ranking policies by $\mathcal{P}$.

We use the term _utility_ in its broad sense in cardinal welfare economics as
a “ _measurement of the higher-order characteristic that is relevant to the
particular distributive justice problem at hand_ ” (Moulin, 2003). Similarly
to (Patro et al., 2020; Wang and Joachims, 2021; Do et al., 2021), we define
the utility of a user as the ranking performance, and the utility of an item
as its average exposure to users, which are formalized in (1) below. Utilities
are defined according to the position-based model (Biega et al., 2018; Morik
et al., 2020; Do et al., 2021) with weights
${\boldsymbol{b}}\in\mathbb{R}_{+}^{m}$. The weight $b_{k}$ is the probability
that a user examines the item at position $k$, and we assume that the weights
are non-increasing. Since there are $K$ recommendation slots, we have
$b_{1}\geq\ldots\geq b_{K}$ and $b_{k}=0$ for any $k>K$. The user and item
utilities are then:

(1)

We follow a general framework where the ranking policy $P$ is found by
maximizing a global _welfare function_ $F(P)$, and the welfare function is a
weighted sum of welfare functions for users and items:

(2) $\displaystyle F(P)=(1-\lambda)g^{\rm user}({\boldsymbol{u}}(P))+\lambda
g^{\rm item}({\boldsymbol{v}}(P)),$

where $g^{\rm user}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and $g^{\rm
item}:\mathbb{R}^{m}\rightarrow\mathbb{R}$ respectively aggregate the
utilities of users and item exposures and $\lambda\in[0,1]$ specifies the
relative weight of users and items.

###  2.2. Generalized Gini welfare functions

In this work, we focus on the case where $g^{\rm item}$ and $g^{\rm user}$ are
based on Generalized Gini welfare Functions (GGFs) (Weymark, 1981)). A GGF
$g_{{\boldsymbol{w}}}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a function
parameterized by a vector ${\boldsymbol{w}}\in\mathbb{R}^{n}$ of non-
increasing positive weights such that $w_{1}=1\geq\ldots\geq w_{n}\geq 0$, and
defined by a weighted sum of its sorted inputs, which is also called an
ordered weighted averaging operator (OWA) (Yager, 1988). Formally, let
${\boldsymbol{x}}\in\mathbb{R}^{n}$ be a utility vector and denote by
${\boldsymbol{x}}^{\uparrow}$ the values of ${\boldsymbol{x}}$ sorted in
increasing order, i.e., $x_{1}^{\uparrow}\leq...\leq x_{n}^{\uparrow}$. Then:

(3) $\displaystyle
g_{{\boldsymbol{w}}}({\boldsymbol{x}})=\sum_{i=1}^{n}w_{i}x_{i}^{\uparrow}.$

Let
${\mathcal{V}}_{n}=\\{{\boldsymbol{w}}\in\mathbb{R}^{n}:w_{1}=1\geq\ldots\geq
w_{n}\geq 0\\}$ be the set of admissible weights of GGFs. Given
${\boldsymbol{w^{1}}}\in{\mathcal{V}}_{n}$,
${\boldsymbol{w^{2}}}\in{\mathcal{V}}_{m}$ and $\lambda\in(0,1)$, we define
the _two-sided GGF_ as the welfare function (2) with $g^{\rm
user}=g_{{\boldsymbol{w^{1}}}}$ and $g^{\rm item}=g_{{\boldsymbol{w^{2}}}}$:

(4) $\displaystyle
F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}(P)=(1-\lambda)g_{{\boldsymbol{w^{1}}}}\big{(}{\boldsymbol{u}}(P)\big{)}+\lambda
g_{{\boldsymbol{w^{2}}}}\big{(}({\boldsymbol{v}}(P)\big{)}.$

With non-increasing, non-negative weights ${\boldsymbol{w}}$, OWA operators
are concave (Yager, 1988). The maximization of
$F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}(P)$ (4) is thus a
convex optimization problem (maximization of a concave function over the
convex set of ranking policies). GGFs address fairness from the point of view
of distributive justice in welfare economics (Moulin, 2003), because they
assign more weight to the portions of the population that have the least
utility. Compared to a standard average, a GGF thus promotes more equality
between individuals.

##### Relationship to the Gini index

GGFs are welfare functions so they follow the convention that they should be
maximized. Moreover, if $w_{i}>0$ for all $i$, $g_{{\boldsymbol{w}}}$ is
increasing with respect to every individual utilities, which ensures that
maximizers of GGFs are Pareto-optimal (Moulin, 2003). The Gini index of
${\boldsymbol{x}}$, denoted $\mathrm{Gini}({\boldsymbol{x}})$ is associated to
the GGF $g_{{\boldsymbol{w}}}({\boldsymbol{x}})$ with
$w_{i}=\nicefrac{{(n-i+1)}}{{n}}$ (for formulas of Gini index, see Yitzhaki
and Schechtman, 2013):

(5) $\displaystyle\mathrm{Gini}({\boldsymbol{x}})$
$\displaystyle=1-\frac{2}{\left\lVert{\boldsymbol{x}}\right\rVert_{1}}\sum_{i=1}^{n}\frac{n-i+1}{n}x_{i}^{\uparrow}$
(6)
$\displaystyle=\frac{1}{n^{2}\overline{{\boldsymbol{x}}}}\sum_{i=1}^{n}\sum_{j=1}^{n}|x_{i}-x_{j}|$
$\displaystyle\text{with~{}}\overline{{\boldsymbol{x}}}=\frac{1}{n}\sum_{i=1}^{n}x_{i}.$

The second equality gives a more intuitive formula as a normalized average of
absolute pairwise differences. The Gini index is an inequality measure, and
therefore should be minimized, but, more importantly, it is normalized by the
sum of utilities $\left\lVert{\boldsymbol{x}}\right\rVert_{1}$, which means
that in general minimizing the Gini index does not yield Pareto-optimal
solutions. The importance of this normalization is discussed by e.g., Atkinson
(1970), and by (Do et al., 2021) in the context of fairness in rankings. Yet,
when ${\boldsymbol{x}}$ is a vector of item exposures
${\boldsymbol{x}}={\boldsymbol{v}}(P)$, the normalization is not important
because the total exposure is constant. It is then equivalent to minimize the
Gini index of item exposures or to maximize its associated GGF.

##### Multi-objective optimization of Lorenz curves

An alternative formula for $g_{{\boldsymbol{w}}}({\boldsymbol{x}})$ is based
on the generalized Lorenz curve111Lorenz curves are normalized so that the
last value is $1$, while generalized Lorenz curves are not normalized.
(Shorrocks, 1983) of ${\boldsymbol{x}}$, which is denoted ${\boldsymbol{X}}$
and is defined as the vector of cumulative sums of sorted utilities:

(7)

We used the convention $w_{n+1}=0$. Notice that since the weights
${\boldsymbol{w}}$ are non-increasing, we have that $w_{i}^{\prime}\geq 0$.
Thus, family of admissible OWA weights ${\boldsymbol{w}}$ yield weights
${\boldsymbol{w}}^{\prime}$ that are non-negative and sum to $1$. This formula
offers the interpretation of GGFs as positively weighted averages of points of
the generalized Lorenz curves. Every GGF thus corresponds to a scalarization
of the multi-objective problem of maximizing every point of the generalized
Lorenz curve (Geoffrion, 1968; Miettinen, 2012). We get back to this
interpretation in the next subsections.

###  2.3. GGFs for fairness in rankings

To give concrete examples of the relevance of GGFs for fairness in rankings,
we provide here two fairness evaluation protocols that have been previously
proposed and fall under the scope of maximizing of GGFs as in Eq. (4).

##### Trade-offs between user utility and inequality in item exposure

The first task consists in mitigating inequalities of exposure between (groups
of) items, and appears in many studies (Singh and Joachims, 2018; Zehlike and
Castillo, 2020; Wu et al., 2021a). This leads to a trade-off between the total
utility of users and inequality among items, and such inequalities are usually
measured by the Gini index (as in (Morik et al., 2020; Biega et al., 2018)).
Removing the dependency on $P$ to lighten the notation, a natural formulation
of this trade-off uses the two-sided GGF (4) by setting
${\boldsymbol{w^{1}}}=(1,\ldots,1)$ and
${\boldsymbol{w^{2}}}=\left(\frac{m-j+1}{m}\right)_{j=1}^{m}$, which yields:

(8) $\displaystyle\displaystyle g^{\rm
user}({\boldsymbol{u}})=\frac{1}{n}\sum_{i=1}^{n}u_{i}\quad\quad g^{\rm
item}({\boldsymbol{v}})=\sum_{j=1}^{m}\frac{m-j+1}{m}v_{j}^{\uparrow}.$

As stated in the previous section, for item exposure, maximizing $g^{\rm
item}$ is equivalent to minimizing the Gini index. The Gini index for $g^{\rm
item}$ has been routinely used for _evaluating_ inequality in item exposure
(Morik et al., 2020; Biega et al., 2018) but there is no algorithm to optimize
general trade-offs between user utility and the Gini index of exposure. Morik
et al. (2020) use the Gini index of exposures in the context of dynamic
ranking (with the absolute pairwise differences formula (5)), where their
algorithm is shown to asymptotically drive $g^{\rm item}({\boldsymbol{v}})$ to
$0$, equivalent to $\lambda\to 1$ in (2). However, their algorithm cannot be
used to converge to the optimal rankings for other values of $\lambda$. Do et
al. (2021) use as baseline a variant using the standard deviation of exposures
instead of absolute pairwise difference because it is easier to optimize (it
is smooth except on $0$). In contrast, our approach allows for the direct
optimization of the welfare function (2) with this instantiation of $g^{\rm
item}$ given by eq. (8).

Several authors (Morik et al., 2020; Biega et al., 2018) used _merit-weighted_
exposure222also called _“equity of attention”_ (Biega et al., 2018),
_“disparate treatment”_ (Singh and Joachims, 2018)
${\boldsymbol{v}}^{\prime}_{j}(P)={\boldsymbol{v}}(P)/\overline{\mu}_{j}$
where $\overline{\mu}_{j}=\frac{1}{n}\sum_{i=1}^{n}\mu_{ij}$ is the average
value of item $j$ across users, rather than the exposure itself. We keep the
non-weighted exposure to simplify the exposition, but our method
straightforwardly applies to merit-weighted exposure. Note however that the
sum of weighted exposures is not constant, so using (8) with merit-weighted
exposures is not strictly equivalent to minimizing the Gini index.

##### Two-sided fairness

Do et al. (2021) propose to add a user-side fairness criterion to the trade-
off above, to ensure that worse-off users do not bear the cost of reducing
exposure inequalities among items. Their evaluation involves multi-dimensional
trade-offs between specific points of the generalized Lorenz curve. Using the
formulation (7) of GGFs, trade-offs between maximizing the cumulative utility
at a specific quantile $q$ of users and total utility can be formulated using
a parameter $\omega\in[0,1]$ as follows:

(9) $\displaystyle g^{\rm
user}({\boldsymbol{u}})=\sum_{i=1}^{n}w_{i}^{\prime}U_{i}\quad\text{with~{}}w_{\lfloor
qn\rfloor}^{\prime}=\omega\text{~{}and~{}}w_{n}^{\prime}=1-\omega,$

where all other values of $w_{i}^{\prime}=0$. In our experiments, we combine
this $g^{\rm user}$ with the Gini index for $g^{\rm item}$ for two-sided
fairness.

###  2.4. Generating all Lorenz efficient solutions

In welfare economics, the fundamental property of concave welfare functions is
that they are monotonic with respect to the dominance of generalized Lorenz
curves (Atkinson, 1970; Shorrocks, 1983; Moulin, 2003), because this garantees
that maximizing a welfare function performs an optimal redistribution from the
better-off to the worse-off at every level of average utility. In the context
of two-sided fairness in rankings, Do et al. (2021) formalize their fairness
criterion by stating that a ranking policy is fair as long as the generalized
Lorenz curves of users and items are not jointly dominated. In this section,
we show that the family of GGFs
$F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}(P)$ (4) allows to
generate _every_ ranking policy that are fair under this definition, and
_only_ those. The result follows from standard results of convex multi-
objective optimization (Geoffrion, 1968; Miettinen, 2012). We give here the
formal statements for exhaustivity.

Let ${\boldsymbol{x}}$ and ${\boldsymbol{x}}^{\prime}$ two vectors in
$\mathbb{R}_{+}^{n}$. We say that ${\boldsymbol{x}}$ weakly-Lorenz-dominates
${\boldsymbol{x}}^{\prime}$, denoted ${\boldsymbol{x}}\succeq_{\rm
L}{\boldsymbol{x}}^{\prime}$, when the generalized Lorenz curve of
${\boldsymbol{x}}$ is always at least equal to that of
${\boldsymbol{x}}^{\prime}$, i.e., ${\boldsymbol{x}}\succeq_{\rm
L}{\boldsymbol{x}}^{\prime}\iff\forall i,X_{i}\geq X_{i}^{\prime}$. We say
that ${\boldsymbol{x}}$ Lorenz-dominates ${\boldsymbol{x}}^{\prime}$, denoted
${\boldsymbol{x}}\succ_{\rm L}{\boldsymbol{x}}^{\prime}$ if
${\boldsymbol{x}}\succeq_{\rm L}{\boldsymbol{x}}^{\prime}$ and
${\boldsymbol{x}}\neq{\boldsymbol{x}}^{\prime}$, i.e., if the generalized
Lorenz curve of ${\boldsymbol{x}}$ is strictly larger than that of
${\boldsymbol{x}}^{\prime}$ on at least one point. The criterion that
generalized Lorenz curves of users and items are not jointly-dominated is
captured by the notion of _Lorenz-efficiency_ :

###### Definition 1 (Do et al. (2021)).

A ranking policy $P\in\mathcal{P}$ is _Lorenz-efficient_ if there is no
$P^{\prime}\in\mathcal{P}$ such that either
[${\boldsymbol{u}}(P^{\prime})\succeq_{\rm L}{\boldsymbol{u}}(P)$ and
${\boldsymbol{v}}(P^{\prime})\succ_{\rm L}{\boldsymbol{v}}(P)$] or
[${\boldsymbol{v}}(P^{\prime})\succeq_{\rm L}{\boldsymbol{v}}(P)$ and
${\boldsymbol{u}}(P^{\prime})\succ_{\rm L}{\boldsymbol{u}}(P)$].

We now present the main result of this section:

###### Proposition 2.

Let $\Theta=(0,1)\times{\mathcal{V}}_{n}\times{\mathcal{V}}_{m}$.

  1. (1)

Let $(\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}})\in\Theta$, where
${\boldsymbol{w^{1}}}$ and ${\boldsymbol{w^{2}}}$ have strictly decreasing
weights, and
$P^{*}\in\operatorname*{argmax}_{P\in\mathcal{P}}F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}(P)$.

Then $P^{*}$ is Lorenz-efficient.

  2. (2)

If $P$ is Lorenz efficient, then there exists
$(\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}})\in\Theta$ such that
$P\in\operatorname*{argmax}_{P\in\mathcal{P}}F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}(P)$.

###### Proof.

The proof uses standard results on convex multi-objective optimization from
(Geoffrion, 1968; Miettinen, 2012). Written in the form (7), the GGFs
corresponds to the scalarization of the multi-objective problem of jointly
maximizing the generalized Lorenz curves of users and items, which is a
problem with $n+m$ objectives. Indeed, each objective function is a point of
the generalized Lorenz curve $({\boldsymbol{U}}(P),{\boldsymbol{V}}(P)).$ Each
objective $U_{i}(P)$ is concave because it corresponds to an OWA operator with
non-increasing weights ${\boldsymbol{\rho}}$ with
$\rho_{i^{\prime}}=\mathbbm{1}_{\\{i^{\prime}\leq i\\}},$ applied to
utilities, which are linear functions of the ranking policy. Each objective
$V_{i}(P)$ is similarly concave. Moreover, we are optimizing over the convex
set of stochastic ranking policies $\mathcal{P}$. The multi-objective problem
is then concave, which means that the maximizers of all weighted sums of the
objectives $({\boldsymbol{U}}(P),{\boldsymbol{V}}(P))$ with strictly positive
weights are Pareto-efficient. Reciprocally every Pareto-efficient solution is
a solution of a non-negative weighted sum of the objectives
$({\boldsymbol{U}}(P),{\boldsymbol{V}}(P)),$ where the weights sum to $1$
(Miettinen, 2012).

The result follows from the observation that the Lorenz-efficiency of $P$,
defined as the Lorenz-efficiency of
$({\boldsymbol{u}}(P),{\boldsymbol{v}}(P)),$ is equivalent to the Pareto-
efficiency of its joint user-item Lorenz curves
$({\boldsymbol{U}}(P),{\boldsymbol{V}}(P)).$ This is because the Lorenz
dominance relation between vectors
${\boldsymbol{x}},{\boldsymbol{x}}^{\prime}$ is defined as Pareto dominance in
the space of their generalized Lorenz curves
${\boldsymbol{X}},{\boldsymbol{X}}^{\prime}.$

∎

##### Additive welfare functions vs GGFs

Do et al. (2021) use additive concave welfare functions to generate Lorenz-
efficient rankings. Let $\phi(x,\alpha)=x^{\alpha}$ if $\alpha>0$,
$\phi(x,\alpha)=\log(x)$ if $\alpha=0$ and $\phi(x,\alpha)=-x^{\alpha}$ if
$\alpha<0$. Do et al. (2021) use concave welfare functions of the form:

(10) $\displaystyle g^{\rm
user}({\boldsymbol{u}})=\sum_{i=1}^{n}\phi(u_{i},\alpha_{1})$ $\displaystyle
g^{\rm item}({\boldsymbol{v}})=\sum_{j=1}^{m}\phi(v_{j},\alpha_{2})$

Where $\alpha_{1}$ (resp. $\alpha_{2}$) specifies how much the rankings should
redistribute utility to worse-off users (resp. least exposed items).

Additive separability plays an important role in the literature on inequality
measures (Dalton, 1920; Atkinson, 1970; Cowell, 1988), as well as in the study
of welfare functions because additive separability follows from a standard
axiomatization (Moulin, 2003). However, this leads to a restricted class of
functions, so that varying $\alpha_{1},\alpha_{2}$ and $\lambda$ in (10)
cannot generate all Lorenz-efficient solutions in general. The GGF approach
provides a more general device to navigate the set of Lorenz-efficient
solutions, with interpretable parameters since they are weights assigned to
points of the generalized Lorenz curve.

##  3\. Optimizing Generalized Gini Welfare

In this section, we provide a scalable method for optimizing two-sided GGFs
welfare functions (4) $F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}$.
The challenge of optimizing GGFs is that they are nondifferentiable since they
require sorting utilities. We first describe why existing approaches to
optimize GGFs are not suited to ranking in Sec. 3.1. We then show how to
efficiently compute the gradient of the Moreau envelope of GGFs in Sec. 3.2
and present the full algorithm in Sec. 3.3.

###  3.1. Challenges

In multi-objective optimization, a standard approach to optimizing OWAs is to
solve the equivalent linear program derived by Ogryczak and Śliwiński (2003).
Because the utilities depend on 3d-tensors $P\in\mathcal{P}$ in our case, the
linear program has $O(n\cdot m^{2})$ variables and constraints, which is
prohibitively large in practice. Another approach consists in using online
subgradient descent to optimize GGFs, like (Busa-Fekete et al., 2017; Mehrotra
et al., 2020). This is not tractable in our case because it requires to
project iterates onto the parameter space, which in our case involves costly
projections onto the space of ranking policies $\mathcal{P}.$ On the other
hand, the Frank-Wolfe algorithm (Frank and Wolfe, 1956) was shown to provide a
computationally efficient and provably convergent method to optimize over
$\mathcal{P}$ (Do et al., 2021). However, it only applies to smooth functions,
and Frank-Wolfe with subgradients may not converge to an optimal solution
(Nesterov, 2018).

We turn to Frank-Wolfe variants for nonsmooth objectives, since Frank-Wolfe
methods are well-suited to our structured ranking problem (Do et al., 2021;
Jaggi, 2013; Clarkson, 2010). More precisely, following (Lan, 2013; Yurtsever
et al., 2018; Thekumparampil et al., 2020), our algorithm uses the Moreau
envelope of GGFs for smoothing. The usefulness of this smooth approximation
depends on its gradient, which computation is in some cases intractable (Chen
et al., 2012). Our main technical contribution is to show that the gradient of
the Moreau envelope of GGFs can be computed in $O(n\log n)$ operations.

###  3.2. The Moreau envelope of GGFs

In the sequel, $\left\lVert{\boldsymbol{z}}\right\rVert$ denotes the
$\ell_{2}$ norm. Moreover, a function
$L:\mathcal{X}\subseteq\mathbb{R}^{n}\rightarrow\mathbb{R}$ is $C$-smooth if
it is differentiable with $C$-Lipschitz continuous gradients, i.e., if
$\forall{\boldsymbol{x}},{\boldsymbol{x}}^{\prime}\in\mathcal{X}\,,\left\lVert\nabla
L({\boldsymbol{x}})-\nabla L({\boldsymbol{x}}^{\prime})\right\rVert\leq
C\left\lVert{\boldsymbol{x}}-{\boldsymbol{x}}^{\prime}\right\rVert.$

####  3.2.1. Definition and properties

Let us fix weights ${\boldsymbol{w}}\in{\mathcal{V}}$ and focus on maximizing
the GGF $g_{{\boldsymbol{w}}}.$ Let
$h({\boldsymbol{z}}):=-g_{{\boldsymbol{w}}}({\boldsymbol{z}})$ to obtain a
convex function (this simplifies the overall discussion). The function $h$ is
$\|{\boldsymbol{w}}\|$-Lipschitz continuous, but non-smooth. We consider the
smooth approximation of $h$ given by its Moreau envelope (Parikh and Boyd,
2014) defined as:

(11) $\displaystyle
h^{\beta}({\boldsymbol{z}})=\min_{{\boldsymbol{z}}^{\prime}\in\mathbb{R}^{n}}h({\boldsymbol{z}}^{\prime})+\frac{1}{2\beta}\left\lVert{\boldsymbol{z}}-{\boldsymbol{z}}^{\prime}\right\rVert^{2}.$

It is known that $h^{\beta}({\boldsymbol{z}})\leq h({\boldsymbol{z}})\leq
h^{\beta}({\boldsymbol{z}})+\frac{\beta}{2}\left\lVert{\boldsymbol{w}}\right\rVert^{2}$
and that $h^{\beta}$ is $\frac{1}{\beta}$-smooth (see e.g., Thekumparampil et
al., 2020). The parameter $\beta$ thus controls the trade-off between the
smoothness and the quality of the approximation of $h$.

####  3.2.2. Efficient computation of the gradient

1

input : GGF weights ${\boldsymbol{w}}\in\mathbb{R}^{n}$,
${\boldsymbol{z}}\in\mathbb{R}^{n}$

output : Projection of ${\boldsymbol{z}}$ onto the permutahedron
$\mathcal{C}({\boldsymbol{\tilde{w}}})$.

2 ${\boldsymbol{\tilde{w}}}\leftarrow-(w_{n},...,w_{1})$ and
$\sigma\leftarrow\operatorname{argsort}({\boldsymbol{z}})~{}$

3
${\boldsymbol{x}}\leftarrow\texttt{PAV}(z_{\sigma}-{\boldsymbol{\tilde{w}}})~{}$

4 ${\boldsymbol{y}}\leftarrow{\boldsymbol{z}}+{\boldsymbol{x_{\sigma^{-1}}}}$

Return ${\boldsymbol{y}}$.

Algorithm 1 Computation of
$\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}}})}$

We now present an efficient procedure to compute the gradient of
$f^{\beta}(P):=h^{\beta}({\boldsymbol{u}}(P))$.

Given an integer $n\in\mathbb{N},$ let $[\\![n]\\!]:=\\{1,\ldots,n\\}\,$ and
let $\mathfrak{S}_{n}$ denotes the set of permutations of $[\\![n]\\!]$. For
${\boldsymbol{x}}\in\mathbb{R}^{n}$, and $\sigma\in\mathfrak{S}_{n}$, let us
denote by ${\boldsymbol{x_{\sigma}}}=(x_{\sigma(1)},...,x_{\sigma(n)})$.
Furthermore, let $\mathcal{C}({\boldsymbol{x}})$ denote the _permutahedron_
induced by ${\boldsymbol{x}}$, defined as the convex hull of all permutations
of the vector ${\boldsymbol{x}}$: $\,\mathcal{C}({\boldsymbol{x}})={\rm
conv}\\{{\boldsymbol{x_{\sigma}}}:\sigma\in\mathfrak{S}_{n}\\}.$ Finally, let
$\operatorname{\Pi}_{\mathcal{X}}({\boldsymbol{z}}):=\operatorname*{argmin}\limits_{{\boldsymbol{z}}^{\prime}\in\mathcal{X}}\left\lVert{\boldsymbol{z}}-{\boldsymbol{z}}^{\prime}\right\rVert^{2}.$
denote the projection onto a compact convex $\mathcal{X}$. The following
proposition formulates $\nabla f^{\beta}$ as a projection onto a
permutahedron:

###### Proposition 1.

Let ${\boldsymbol{\tilde{w}}}=-(w_{n},...,w_{1})$. Let $P\in\mathcal{P}$. Then
for all $(i,j,k)\in[\\![n]\\!]\times[\\![m]\\!]^{2}$, we have:

(12) $\displaystyle\frac{\partial f^{\beta}}{\partial
P_{ijk}}(P)=y_{i}\mu_{ij}b_{k}$
$\displaystyle\text{where}\quad{\boldsymbol{y}}=\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}}})}\left(\frac{{\boldsymbol{u}}(P)}{\beta}\right).$

###### Proof.

Let $\operatorname{prox}_{\beta
h}({\boldsymbol{z}})=\operatorname*{argmin}\limits_{{\boldsymbol{z}}^{\prime}\in\mathbb{R}^{n}}\beta
h({\boldsymbol{z}})+\frac{1}{2}\|{\boldsymbol{z}}^{\prime}-{\boldsymbol{z}}\|^{2}$
denote the proximal operator of $\beta h$. Denoting by ${\boldsymbol{u}}*$ the
adjoint of ${\boldsymbol{u}}$, it is known that $\nabla
f^{\beta}(P)=\frac{1}{\beta}{\boldsymbol{u}}^{*}({\boldsymbol{u}}(P)-\operatorname{prox}_{\beta
h}({\boldsymbol{u}}(P))$ (Parikh and Boyd, 2014).

We first notice that since ${\boldsymbol{w}}$ are non-increasing, the
rearrangement inequalities (Hardy et al., 1952) gives:
$h({\boldsymbol{z}})=-\min\limits_{\sigma\in\mathfrak{S}_{n}}{\boldsymbol{w_{\sigma}^{\intercal}}}{\boldsymbol{z}}=\max\limits_{\sigma\in\mathfrak{S}_{n}}-{\boldsymbol{w_{\sigma}^{\intercal}}}{\boldsymbol{z}}.$
Thus, $h$ is the support function of the convex set
$\mathcal{C}({\boldsymbol{\tilde{w}}})$, since:

$\displaystyle
h({\boldsymbol{z}})=\max_{\sigma\in\mathfrak{S}_{n}}-{\boldsymbol{w_{\sigma}^{\intercal}}}{\boldsymbol{z}}=\sup_{{\boldsymbol{y}}\in\mathcal{C}({\boldsymbol{\tilde{w}}})}{\boldsymbol{y}}^{\intercal}{\boldsymbol{z}}.$

Then the Fenchel conjugate of $h$ is the indicator function of
$\mathcal{C}({\boldsymbol{\tilde{w}}})$, and its proximal is the projection
$\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}}})}$ (Parikh and Boyd,
2014). By Moreau decomposition, we get
$~{}\operatorname{prox}({\boldsymbol{z}})={\boldsymbol{z}}-\beta\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}}})}\left(\nicefrac{{{\boldsymbol{z}}}}{{\beta}}\right),$
and thus:

(13) $\displaystyle\nabla
f^{\beta}(P)={\boldsymbol{u}}^{*}\left(\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}}})}\left(\nicefrac{{{\boldsymbol{u}}(P)}}{{\beta}}\right)\right).$

The result follows from the definition of
${\boldsymbol{u}}(P)=\left(\sum_{j,k}\mu_{ij}P_{ijk}b_{k}\right)_{i=1}^{n}.$ ∎

Overall, computing the gradient of the Moreau envelope boils down to a
projection onto the permutahedron $\mathcal{C}({\boldsymbol{\tilde{w}}})$.
This projection was shown by several authors to be reducible to isotonic
regression:

###### Proposition 2 (Reduction to isotonic regression (Negrinho and Martins,
2014; Lim and Wright, 2016; Blondel et al., 2020)).

Let $\sigma\in\mathfrak{S}_{n}$ that sorts ${\boldsymbol{z}}$ decreasingly,
i.e. $z_{\sigma(1)}\geq\ldots\geq z_{\sigma(n)}.$ Let ${\boldsymbol{x}}$ be a
solution to isotonic regression on
${\boldsymbol{z_{\sigma}}}-{\boldsymbol{\tilde{w}}}$, i.e.

(14)
$\displaystyle{\boldsymbol{x}}=\operatorname*{argmin}_{x^{\prime}_{1}\leq\ldots\leq
x^{\prime}_{n}}\frac{1}{2}\|{\boldsymbol{x}}^{\prime}-({\boldsymbol{z_{\sigma}}}-{\boldsymbol{\tilde{w}}})\|^{2}$

Then we have:
$\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}}})}({\boldsymbol{z}})={\boldsymbol{z}}+{\boldsymbol{x_{\sigma^{-1}}}}.$

Following these works, we use the Pool Adjacent Violators (PAV) algorithm for
isotonic regression, which gives a solution in $O(n)$ iterations given a
sorted input (Best et al., 2000). The algorithm for computing the projection
is summarized in Alg. 1 where we use the notation
$\operatorname{argsort}({\boldsymbol{z}})=\\{\sigma\in\mathfrak{S}_{n}:z_{\sigma(1)}\geq\ldots\geq
z_{\sigma(n)}\\}$ for permutations that sort
${\boldsymbol{z}}\in\mathbb{R}^{n}$ in decreasing order. Including the sorting
of $\frac{{\boldsymbol{u}}(P)}{\beta}$, it costs $O(n\log n)$ time and $O(n)$
space.

###### Remark 1.

Our method is related to the differentiable sorting operator of Blondel et al.
(2020), which uses a regularization term to smooth the linear formulation of
sorting. The regularized form can itself be written as a projection to a
permutahedron. The problem they address is different since they differentiate
the multi-dimensional sort operation, but eventually the techniques are
similar because the smoothing is done in a similar way.

###### Remark 2.

We computed the gradient of $f^{\beta}(P)=h^{\beta}({\boldsymbol{u}}(P))$ with
user utilities. The gradient of $f^{\beta}(P)=h^{\beta}({\boldsymbol{v}}(P))$
using item exposures is computed similarly: $\frac{\partial
f^{\beta}}{\partial P_{ijk}}(P)=y_{j}b_{k}$ with
${\boldsymbol{y}}=\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}}})}\left(\frac{{\boldsymbol{v}}(P)}{\beta}\right)$.

###  3.3. Frank-Wolfe with smoothing

We return to the optimization of the two-sided GGF objective (4). In this
section, we fix the parameters
$(\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}})$ and consider the
minimization of $f:=-F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}$
over $\mathcal{P}$. For $\beta>0$ we denote by $h_{1}^{\beta}$ and
$h_{2}^{\beta}$ the Moreau envelopes of $-g_{{\boldsymbol{w^{1}}}}$ and
$-g_{{\boldsymbol{w^{2}}}}$ respectively. The smooth approximation of $f$ is
then:

(15) $\displaystyle
f^{\beta}(P):=(1-\lambda)h_{1}^{\beta}({\boldsymbol{u}}(P))+\lambda
h_{2}^{\beta}({\boldsymbol{v}}(P)).$

Our algorithm FW-smoothing (Alg. 2) for minimizing $f$ uses the Frank-Wolfe
method for nonsmooth optimization from Lan (2013)333Lan (2013) uses the
smoothing scheme of Nesterov (2005) which is in fact equal to the Moreau
envelope (see (Beck and Teboulle, 2012, Sec. 4.3)).. Given a sequence
$(\beta_{t})_{t\geq 1}$ of positive values decreasing to $0$, the algorithm
constructs iterates $P^{(t)}$ by applying Frank-Wolfe updates to
$f^{\beta_{t}}$ at each iteration $t$. More precisely, FW-smoothing finds an
update direction with respect to $\nabla f^{\beta_{t}}$ by computing:

(16) $\displaystyle Q^{(t)}=\operatorname*{argmin}_{P\in\mathcal{P}}\langle
P\,|\,\mathopen{}\nabla f^{\beta_{t}}(P^{(t-1)})\rangle.$

The update rule is
$P^{(t)}=P^{(t-1)}+\frac{2}{t+2}\big{(}Q^{(t)}-P^{(t-1)}\big{)}$.

Before giving the details of the computation of (16), we note that applying
the convergence result of Lan (2013), and denoting
$D_{\mathcal{P}}=\max\limits_{P,P^{\prime}\in\mathcal{P}}\|P-P^{\prime}\|$ the
diameter of $\mathcal{P}$, we obtain444In more details, the convergence
guarantee of Lan (2013) uses the operator norm of ${\boldsymbol{u}}$ and
${\boldsymbol{v}}$, which we bound as follows: $\left\lVert
u(P)\right\rVert^{2}\leq\sum_{i}\sum_{j,k}(\mu_{ij}P_{ijk}b_{k})^{2}\leq
b_{1}^{2}\left\lVert P\right\rVert^{2}$, because $\mu_{ij}\in[0,1]$
$b_{k}\in[0,b_{1}],$ and similarly
$\left\lVert{\boldsymbol{v}}(P)\right\rVert^{2}\leq b_{1}^{2}\left\lVert
P\right\rVert^{2}$. :

###### Proposition 3 (Th. 4, (Lan, 2013)).

With $\beta_{0}=\frac{2D_{\mathcal{P}}b_{1}}{\|{\boldsymbol{w}}\|}$ and
$\beta_{t}=\frac{\beta_{0}}{\sqrt{t}}$, FW-smoothing obtains the following
convergence rate:

$f(P^{(T)})-f(P^{*})\leq\frac{2D_{\mathcal{P}}b_{1}\|{\boldsymbol{w}}\|}{\sqrt{T}}.$

1

input : values $(\mu_{ij})$, $\\#$ of iterations $T$, smoothing seq.
$(\beta_{t})_{t}$

output : ranking policy $P^{(T)}$

2

3Initialize $P^{(0)}$ such that $P_{i}^{(0)}$ sorts $\mu_{i}$ in decreasing
order

4 for  _t=1, …, T_ do

5 Let

$\displaystyle{\boldsymbol{y}}^{1}=\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}^{1}}})}\left(\frac{{\boldsymbol{u}}(P^{(t-1)})}{\beta_{t}}\right)$
and
$\displaystyle{\boldsymbol{y}}^{2}=\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}^{2}}})}\left(\frac{{\boldsymbol{v}}(P^{(t-1)})}{\beta_{t}}\right)$

6 for  _i=1, …, n_ do

7 $\tilde{\mu}_{ij}=(1-\lambda)\,y_{i}^{1}\mu_{ij}+\lambda y_{j}^{2}$

$~{}~{}\tilde{\sigma}_{i}\leftarrow\mathop{\text{top-}K}(-\tilde{\mu}_{i})$ //
Update direction (16)

8

9 end for

10 Let $Q^{(t)}\in\mathcal{P}$ such that $Q^{(t)}_{i}$ represents
$\tilde{\sigma}_{i}$

11 $P^{(t)}\leftarrow(1-\frac{2}{t+2})P^{(t-1)}+\frac{2}{t+2}Q^{(t)}\,$.

12 end for

Return $P^{(T)}$.

Algorithm 2 FW-smoothing. Alg. 1 is used for ${\boldsymbol{y}}^{1}$ and
${\boldsymbol{y}}^{2}$.

##### Efficient computation of the update direction

For smooth welfare functions of user utilities and item exposures, the update
direction (16) can be computed with only one top-$K$ sorting operation per
user (Do et al., 2021). In our case, the update is given by the following
result, where
$\mathop{\text{top-}K}({\boldsymbol{z}})=\\{\sigma\in\mathfrak{S}_{n}:z_{\sigma(1)}\geq\ldots\geq
z_{\sigma(K)}\text{ and }\forall k\geq K,z_{\sigma(K)}\geq z_{\sigma(k)}\\}$
is the set of permutations that sort the $k$ largest elements in
${\boldsymbol{z}}$.

###### Proposition 4.

Let $\tilde{\mu}$ defined by
$\tilde{\mu}_{ij}=(1-\lambda)\,y_{i}^{1}\mu_{ij}+\lambda y_{j}^{2}\,$ where
${\boldsymbol{y}}^{1}=\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}^{1}}})}\left(\nicefrac{{{\boldsymbol{u}}(P^{(t-1)})}}{{\beta_{t}}}\right)$
and
${\boldsymbol{y}}^{2}=\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}^{2}}})}\left(\nicefrac{{{\boldsymbol{v}}(P^{(t-1)})}}{{\beta_{t}}}\right)$.

For all $i\in[\\![n]\\!],$ let
$\tilde{\sigma}_{i}\in\mathop{\text{top-}K}(-\tilde{\mu}_{i})$ and
$Q^{(t)}_{i}$ a permutation matrix representing $\tilde{\sigma}_{i}$. Then
$Q^{(t)}\in\operatorname*{argmin}\limits_{P\in\mathcal{P}}\langle
P\,|\,\mathopen{}\nabla f^{\beta_{t}}(P^{(t-1)})\rangle.$

###### Proof.

Using the expression of the gradient of the Moreau envelope derived in
Proposition 1, eq. (12), we have:

And thus $\frac{\partial f^{\beta_{t}}}{\partial
P_{ijk}}(P^{(t-1)})=\tilde{\mu}_{ij}\times b_{k}$. The result then follows
from (Do et al., 2021, Lem. 3) and is a consequence of the rearrangement
inequality (Hardy et al., 1952): $Q^{(t)}$ is obtained by sorting
$\tilde{\mu}_{ij}$ in increasing order, or equivalently, by sorting
$-\tilde{\mu}_{ij}$ in decreasing order. ∎

Since the computation of the gradient of Moreau envelopes costs $O(n\ln n+n\ln
m)$ operations using Alg. 1, then by Prop. 4 at each iteration, the cost of
the algorithm is dominated by the top-K sort per user, each of which has
amortized complexity of $O(m+K\ln K)$:

###### Proposition 5.

Each iteration costs $O(nm+nK\ln K)$ operations. The total amount of storage
required is $O(nKT)$.

In conclusion, FW-smoothing has a cost per iteration similar to the standard
Frank-Wolfe algorithm for ranking with smooth objective functions. The cost of
the non-smoothness of the objective function is a convergence rate of
$1/\sqrt{T}$, while the Frank-Wolfe algorithm converges in $O(1/T)$ when the
objective is smooth (Clarkson, 2010).

Moreover, the algorithm produces a _sparse representation_ of the stochastic
ranking policy as a weighted sum of permutation matrices. In other words, this
gives us a Birkhoff-von-Neumann decomposition (Birkhoff, 1940) of the
bistochastic matrices _for free_ , avoiding the overhead of an additional
decomposition algorithm as in existing works on fair ranking (Singh and
Joachims, 2018; Wang and Joachims, 2021; Su et al., 2021).

##  4\. Experiments

We first present our experimental setting for recommendation of music and
movies, together with the fairness criteria we explore and the baselines we
consider. These fairness criteria have been chosen because they were used in
the evaluation of prior work, and they exactly correspond to the optimization
of a GGF. We thus expect our two-sided GGF
$F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}$ to fare better than
the baselines, because they allow for the optimization of the exact evaluation
criterion. We provide experimental results that demonstrate this claim in Sec.
4.2. Note that the GGFs are extremely flexible as we discussed in Sec. 2.1, so
our experiments can only show a few illustrative examples of fairness criteria
that can be defined with GGFs. In Sec. 4.3, we show the usefulness of FW-
smoothing compared to the simpler baseline of Frank-Wolfe with subgradients.

###  4.1. Experimental setup

Our experiments are implemented in Python 3.9 using
PyTorch555http://pytorch.org. For the PAV algorithm, we use the implementation
of Scikit-Learn.666https://github.com/scikit-learn/scikit-
learn/blob/main/sklearn/isotonic.py

####  4.1.1. Data and evaluation protocol

We present experiments on two recommendation tasks, following the protocols of
(Do et al., 2021; Patro et al., 2020). First, we address music recommendation
with Lastfm-2k from Cantador et al. (2011) which contains real listening
counts of $2k$ users for $19k$ artists on the online music service
Last.fm777https://www.last.fm/. We filter the $2,500$ items having the most
listeners. In order to show how the algorithm scales, we also consider the
MovieLens-20m dataset (Harper and Konstan, 2015), which contains ratings in
$[0.5,5]$ of movies by users, and we select the top $15,000$ users and items
with the most interactions.

We use an evaluation protocol similar to (Patro et al., 2020; Do et al., 2021;
Wang and Joachims, 2021). For each dataset, a full user-item preference matrix
$(\mu_{i,j})_{i,j}$ is obtained by standard matrix factorization
algorithms888Using the Python library Implicit:
https://github.com/benfred/implicit (MIT License). from the incomplete
interaction matrix, following the protocol of (Do et al., 2021). Rankings are
inferred from these estimated preferences. The exposure weights
${\boldsymbol{b}}$ are the standard weights of the _discounted cumulative
gain_ (DCG) (also used in e.g., (Singh and Joachims, 2018; Biega et al., 2018;
Morik et al., 2020)): $\forall k\in[\\![K]\\!],b_{k}=\frac{1}{\log_{2}(1+k)}.$

The generated $\mu_{ij}$ are used as ground truth to evaluate rankings, in
order to decouple the fairness evaluation of the ranking algorithms from the
evaluation of biases in preference estimates (which are not addressed in the
paper). The results are the average of three repetitions of the experiments
over different random train/valid/test splits used to generate the $\mu_{ij}$.

####  4.1.2. Fairness criteria

We remind two fairness tasks studied in the ranking literature and presented
in Section 2.3, and describe existing approaches proposed to address them,
which we consider as baselines for comparison with our two-sided GGF (4)
$F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}$.

##### Task 1: Trade-offs between user utility and inequality between items

We use the two-sided GGF
$F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}$ instantiated as in Eq.
(8), i.e., with ${\boldsymbol{w^{1}}}=(1,\ldots,1)$ and
$w^{2}_{j}=\frac{m-j+1}{m}$. This corresponds to a trade-off function between
the sum of user utilities and a GGF for items with the Gini index weights,
where the trade-off is controlled by varying $\lambda\in(0,1).$ We remind
though that unlike the standard Gini index, the GGF is un-normalized (see eq.
(5), Sec 2.2).

We use three baselines for this task.

First, since the Gini index is non-differentiable, (Do et al., 2021) proposed
a differentiable surrogate using the standard deviation (std) instead, which
we refer to as eq. exposure:

(17) $\displaystyle F^{\rm
eq}(P)=\sum_{i=1}^{n}u_{i}(P)-\frac{\lambda}{m}\sqrt{\sum_{j=1}^{m}\left(v_{j}(P)-\frac{1}{m}\sum_{j^{\prime}=1}^{m}v_{j^{\prime}}(P)\right)^{2}}$

Second, Patro et al. (2020) address the trade-off of Task 1, since they
compare various recommendation strategies based on the utility of users and
the Lorenz curves of items (see (Patro et al., 2020, Fig. 1)), recalling that
the standard Gini index is often defined as $1-2A$ where $A$ is the area under
the Lorenz curve (Yitzhaki and Schechtman, 2013). Their fairness constraints
are slightly different though, as their algorithm FairRec 999(Patro et al.,
2020) consider unordered recommendation lists with a uniform attention model.
We transform them into ordered lists using the order output by FairRec, and
adapt the item-side criterion of minimal exposure to the position-based model.
guarantees envy-freeness for users, and a minimum exposure of $\frac{\lambda
n\left\lVert{\boldsymbol{b}}\right\rVert}{m}$ for every item, where $\lambda$
is the user-item tradeoff parameter.

Finally, we use the additive welfare function (10) (refered to as welf) with
the recommended values $\alpha_{1}\in\\{-2,0,1\\}$ and $\alpha_{2}=0$ (Do et
al., 2021), and varying $\lambda\in(0,1)$ as third baseline. We only report
the result of $\alpha_{1}=1$ since it obtained overall better performances on
this task.

##### Task 2: Two-sided fairness

We consider trade-offs between the cumulative utility of the $q$ fraction of
worst-off users, where $q\in\\{0.25,0.5\\},$ and inequality between items
measured by the Gini index, as in (Do et al., 2021). For this task, we
instantiate the two-sided GGF
$F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}$ as follows: the GGF
for users is given by Eq. (9) with parameters $(q,\omega)$ in
$\\{0.25,0.5\\}\times\\{0.25,0.5,1\\}$, and the GGF for items uses the Gini
index weights $w_{j}=\frac{m-j+1}{m}.$ We generate trade-offs between user
fairness and item fairness by varying $\lambda\in(0,1).$

The baseline approach for this task is welf, the additive welfare function
(10), still with the recommended values $\alpha_{1}\in\\{-2,0,1\\}$ and
$\alpha_{2}=0$ and varying $\lambda\in(0,1)$. We only report the results of
$\alpha_{1}=-2$ as they obtained the best performances on this task.

###  4.2. Results

(a) Total user utility vs. inequality between items. GGF is instantiated as
(8).

(b) Utility of the 25% worse-off users vs. inequality between items. GGF is
instantiated as (9) with parameters $(q,\omega)$.

(c) Utility of the 50% worse-off users vs. inequality between items. GGF is
instantiated as (9) with parameters $(q,\omega)$.

(d) Optimization of GGF (8) with $\lambda=0.5$

(e) Total user utility vs. inequality between items. GGF is instantiated as
(8).

(f) Utility of the 25% worse-off users vs. inequality between items. GGF is
instantiated as (9) with parameters $(q,\omega)$.

(g) Utility of the 50% worse-off users vs. inequality between items. GGF is
instantiated as (9) with parameters $(q,\omega)$.

(h) Optimization of GGF (8) with $\lambda=0.5$

Figure 1. Summary of the results on Lastfm-2k (top row) and MovieLens (bottom
row). (Left 3 columns): Trade-offs achieved by competing methods on various
fairness criteria, when varying $\lambda\in[0,1].$ (Right column): Convergence
of FW-subgradient compared to FW-smoothing, for various values of $\beta_{0}.$
FW-subgradient is not guaranteed to converge to an optimum.

We now present experiments that illustrate the effectiveness of the two-sided
GGF approach on Task 1 and 2.

For each fairness method, Pareto frontiers are generated by varying $\lambda$.
Since Patro et al. (2020)’s algorithm FairRec does not scale, we compare to
FairRec only on Lastfm-2k.

We optimize $F_{\lambda,{\boldsymbol{w^{1}}},{\boldsymbol{w^{2}}}}$ using FW-
smoothing with $\beta_{0}=100$ and $T=5k$ for Lastfm-2k, and $\beta_{0}=1000$
and $T=50k$ for MovieLens. $F^{\it welf}$ and $F^{\rm eq}$ are optimized with
the Frank-Wolfe method of (Do et al., 2021) for $T=1k$ and $T=5k$ iterations
respectively for Lastfm-2k and MovieLens. This is the number of iterations
recommended by (Do et al., 2021), while we need more interactions for FW-
smoothing because its convergence is $O(\frac{1}{\sqrt{T}})$ rather than
$O(\frac{1}{T})$ because of non-smoothness.

We first focus on Lastfm-2k. On Task 1, _Fig. 1(a)_, the GGF (red $+$ curve)
obtains the best trade-off between total utility of users and Gini inequality
between items, compared to FairRec and eq. exposure. It fares better than eq.
exposure (orange $\times$) on this task because eq. exposure reduces
inequality between items by minimizing the std of exposures, while GGF with
weights $w^{2}_{j}=\frac{m-j+1}{m}$ minimizes the Gini index. This shows that
Task 1 can be addressed by directly optimizing the Gini index, thanks to GGFs
with FW-smoothing.

For Task 2, _Fig. 1(b) and 1(c)_ depicts the trade-offs achieved between the
utility of the $25\%$ / $50\%$ worst-off users and inequality among items.
First, we observe that the more weight $\omega$ is put on the $q$-% worst-off
in GGF, the higher the curve, which is why we observe the ordering green
$\square$ $\prec$ red $+$ $\prec$ purple $\diamond$ for GGF, on both $25\%$
and $50\%$ trade-offs plots. Second, as expected, welf is outperformed by our
two-sided GGF with instantiation (9) and $(q,\omega)=(q,1)$ (purple
$\diamond$), since it corresponds to the optimal settings for this task.

Figures 1(e),1(f),1(g) illustrates the same trade-offs on MovieLens. Results
are qualitatively similar: by adequately parameterizing GGFs, we obtain the
best guarantees on each fairness task.

Overall, these results show that even though the baseline approaches obtain
non-trivial performances on the two fairness tasks above, the direct
optimization of the trade-offs involving the Gini index or points of the
Lorenz curves, which is possible thanks to our algorithm, yields significant
performance gains. Moreover, we reiterate that these two tasks are only
examples of fairness criteria that GGFs can formalize, since by varying the
weights we can obtain all Lorenz-efficient rankings (Prop. 2).

###  4.3. Convergence diagnostics

We now demonstrate the usefulness of FW-smoothing for optimizing GGF
objectives, compared to simply using the Frank-Wolfe method of (Do et al.,
2021) with a subgradient of the GGF (FW-subgradient). We note that a
subgradient of $g_{{\boldsymbol{w}}}({\boldsymbol{x}})$ is given by
${\boldsymbol{w_{\sigma^{-1}}}},$ where
$\sigma\in\operatorname{argsort}(-{\boldsymbol{x}})$. More precisely, FW-
subgradient is also equivalent to using subgradients of
$-g_{{\boldsymbol{w^{1}}}}$ and $-g_{{\boldsymbol{w^{2}}}}$ in Line 3 of Alg.
2, instead of $\nabla f^{\beta_{t}}(P^{(t)}),$ ignoring the smoothing
parameters $\beta_{t}$. FW-subgradient is simpler than FW-smoothing, but it is
not guaranteed to converge (Nesterov, 2018). The goal of this section is to
assess whether the smoothing is necessary in practice.

We focus on the two-sided GGF (8) of Task 1 on Lastfm-2k and MovieLens, using
FW-subgradient and FW-smoothing with different values of $\beta_{0}$. Figure
1(d) depicts the objective value as a function of the number of iterations,
averaged over three seeds (the colored bands represent the std), on Lastfm-2k.
We observe that FW-subgradient (blue dotted curve) plateaus at a suboptimum.
In contrast, FW-smoothing converges (orange dotted and green dash-dot curves),
and the convergence is faster for larger $\beta_{0}$. On MovieLens (Fig 1(h)),
FW-subgradient converges to the optimal solution, but it is still slower than
FW-smoothing with $\beta_{0}=1000$.

In conclusion, even though FW-subgradient reaches the optimal performance on
Movielens for this set of parameters, it is still possible that FW-subgradient
plateaus at significantly suboptimal solutions. The use of smoothing is thus
not only necessary for theoretical convergence guarantees, but also in
practice. In addition, FW-smoothing has comparable computational complexity to
FW-subgradient since the computation cost is dominated by the sort operations
in Alg. 2.

##  5\. Reciprocal recommendation

###  5.1. Extension of the framework and algorithm

We show that our whole method for fair ranking readily applies to reciprocal
recommendation tasks, such as the recommendation of friends or dating
partners, or in job search platforms.

##### Reciprocal recommendation framework

The recommendation framework we discussed thus far depicted _“one-sided”
recommendation_ , in the sense that only items are being recommended. In
_reciprocal recommendation_ problems (Palomares et al., 2021), users are also
items who can be recommended to other users (the item _per se_ is the user’s
profile or CV), and they have preferences over other users.

In this setting, $n=m$ and $\mu_{ij}$ denotes the mutual preference value
between $i$ and $j$ (e.g., the probability of a “match” between $i$ and $j$).
Following (Do et al., 2021), we extend our previous framework to reciprocal
recommendation by introducing the _two-sided utility_ of a user $i$, which
sums the utility $\overline{u}_{i}(P)$ derived by $i$ from the recommendations
it gets, and the utility $\overline{v}_{i}(P)$ from being recommended to other
users:

$\displaystyle
u_{i}(P)=\overline{u}_{i}(P)+\overline{v}_{i}(P)\,=\sum_{i,j}(\mu_{ij}+\mu_{ji})P_{ij}^{\intercal}{\boldsymbol{b}}$
$\displaystyle\text{where
}~{}~{}\overline{u}_{i}(P)=\sum_{i=1}^{n}\mu_{ij}P_{ij}^{\intercal}{\boldsymbol{b}}\quad\text{
and
}\quad\overline{v}_{i}(P)=\sum_{j=1}^{n}\mu_{ij}P_{ij}^{\intercal}{\boldsymbol{b}}\,.$

##### Objective and optimization

The two-sided GGF objective (4) in reciprocal recommendation simply becomes
one GGF of two-sided utilities, and it is specified by a single weighting
vector ${\boldsymbol{w}}$:

(18)
$\displaystyle\max\limits_{P\in\mathcal{P}}\\{F_{{\boldsymbol{w}}}(P):=g_{{\boldsymbol{w}}}({\boldsymbol{u}}(P))\\}.$

The choice of ${\boldsymbol{w}}$ controls the degree of priority to the worse-
off in the user population. We show in our experiments in Section 5.2 that in
reciprocal recommendation too, the GGF objective can be adequately
parameterized to address existing fairness criteria.

$F_{{\boldsymbol{w}}}$ can be optimized using our algorithm FW-smoothing.
Since there is only one GGF, the subroutine Alg. 1 is simply used once per
iteration to project onto $\mathcal{C}({\boldsymbol{\tilde{w}}}),$ and obtain
${\boldsymbol{y}}=\operatorname{\Pi}_{\mathcal{C}({\boldsymbol{\tilde{w}}})}\left(\frac{{\boldsymbol{u}}(P^{(t-1)})}{\beta_{t}}\right)$
in Line 3 of Algorithm 2. Line 5 becomes
$\tilde{\mu}_{ij}=(1-\lambda)y_{i}\mu_{ij}+\lambda y_{j}\mu_{ji}.$

Our method for fair ranking is thus general enough to address both one-sided
and reciprocal recommendation, using the notion of two-sided utility from Do
et al. (2021).

###  5.2. Experiments

Similarly to our experiments in Sec. 4.2, the goal of these experiments is to
demonstrate that in reciprocal recommendation, GGF can be parameterized to
exactly optimize for existing fairness criteria, outperforming previous
approaches designed to address them.

(a) Total utility vs. inequality. GGF is instantiated as (19) and we vary
$\lambda.$

(b) Total utility vs. utility of the 25% worse-off. GGF is instantiated as (9)
with $q=0.25$ and varying $\omega.$

Figure 2. Fairness trade-offs achieved by competing methods on reciprocal
recommendation on Twitter. They are generated by varying $\lambda$ for eq.
utility and GGF, and $\alpha$ for welf.

##### Data

We reproduce the experimental setting of (Do et al., 2021) who also study
fairness in reciprocal recommendation. We simulate a friend recommendation
task from the Higgs Twitter dataset (De Domenico et al., 2013), which contains
directed follower links on the social network Twitter. We consider a mutual
follow as a “match”, and we keep users having at least 20 matches, resulting
in a subset of $13k$ users. We estimate mutual scores $\mu_{ij}$ (i.e., match
probabilities) by matrix factorization.

####  5.2.1. Fairness criteria

Similarly to Section 4.1.2, we state two fairness tasks that previously
appeared in the literature, we instantiate the GGF objective
$F_{{\boldsymbol{w}}}$ for each task and describe existing baselines.

##### Task 1: Trade-offs between total utility and inequality of utility among
users

Although reciprocal recommendation received less attention in the fairness
literature, an existing requirement is to mitigate inequalities in utility
between users (Jia et al., 2018; Basu et al., 2020), similarly to the eq.
exposure criterion in one-sided recommendation. This leads to a trade-off
between the sum of utilities and inequality typically measured by the Gini
index. For Task 1, we use the GGF (18) with
$w_{i}=(1-\lambda)+\lambda\cdot\frac{n-i+1}{n},$ which yields a trade-off
function between the sum of utilities and inequality of utilities, and we vary
$\lambda$ in $(0,1)$ to generate such trade-offs:

(19) $\displaystyle
F_{{\boldsymbol{w}}}(P)=(1-\lambda)\sum_{i=1}^{n}u_{i}(P)+\lambda\sum_{i=1}^{n}\frac{n-i+1}{n}u_{i}^{\uparrow}(P).$

We use two baselines for this task.

First, similarly to eq. exposure, to bypass the nonsmoothness of the Gini
index, (Do et al., 2021) optimize a surrogate with std, named eq. utility:

(20) $\displaystyle F^{\rm
eq}(P)=\sum_{i=1}^{n}u_{i}(P)-\frac{\lambda}{n}\sqrt{\sum_{i=1}^{n}\left(u_{i}(P)-\frac{1}{n}\sum_{i^{\prime}=1}^{n}u_{i^{\prime}}(P)\right)^{2}}.$

Second, the welfare function welf (10) of (Do et al., 2021) is used in
reciprocal recommendation as a single sum: $F^{\it
welf}(P)=\sum_{i=1}^{n}\phi(u_{i}(P),\alpha)$ where $\phi$ is defined in Sec.
2.3. We study welf as baseline by varying $\alpha,$ which controls the
redistribution of utility in the user population.

##### Task 2: Trade-offs between total utility and utility of the worse-off

The main task studied by (Do et al., 2021) with welf is to trade-off between
the total utility and the cumulative utility of the $q$ fraction of worse-off
users. For this task, we instantiate the GGF with (9), with fixed quantile
$q=0.25$ and we vary $\omega$ to generate trade-offs between total utility and
cumulative utility of the $25\%$ worst-off.

We compare it to the welf baseline where $\alpha$ is varied as in (Do et al.,
2021).

####  5.2.2. Fairness trade-offs results

##### Results

We now demonstrate that in reciprocal recommendation too, GGF is the most
effective approach in addressing existing fairness criteria. We optimize the
GGF $F_{{\boldsymbol{w}}}(P)$ using FW-smoothing with $\beta_{0}=10$ for
$T=50k$ iterations, and optimize $F^{\it welf}$ and $F^{\rm eq}$ using Frank-
Wolfe for $T=5k$ iterations.

Figure 2 depicts the trade-offs obtained by the competing approaches on the
fairness tasks 1 and 2, on the Twitter dataset. Fig. 2(a) illustrates the
superiority of GGF (green $\square$) on Task 1, despite good performance of
the baselines eq. utility (orange $\times$) and welf (blue $\circ$). As in
one-sided recommendation with eq. exposure, the reason why eq. utility
achieves slightly worse trade-offs on this fairness task is because it
minimizes the std as a surrogate to the Gini index, instead of the Gini index
itself as GGF does. For Task 2, on Fig.2(b), we observe that GGF with
parameterization (9) (green $\square$) is the most effective. This is because
unlike the welf approach (blue $\circ$) of (Do et al., 2021) who address this
fairness task, this form of GGF is exactly designed to optimize for utility
quantiles.

##  6\. Related work

##### Algorithmic fairness

Fairness in ranking and recommendation systems is an active area of research.
Since recommender systems involve multiple stakeholders (Burke, 2017;
Abdollahpouri et al., 2020), fairness has been considered from the perspective
of both users and item producers. On the user side, a common goal is to
prevent disparities in recommendation performance across sensitive groups of
users (Mehrotra et al., 2017; Ekstrand et al., 2018). On the item side,
authors aim to prevent winner-take-all effects (Abdollahpouri et al., 2019) by
redistributing exposure across groups of producers, either towards equal
exposure, or equal ratios of exposure to relevance (Singh and Joachims, 2018;
Biega et al., 2018; Diaz et al., 2020; Kletti et al., 2022), sometimes
measured by the classical Gini index (Morik et al., 2020; Wilkie and
Azzopardi, 2014).

Some authors consider fairness for both users and items, often by applying
existing user or item criteria simultaneously to both sides, such as (Basu et
al., 2020; Wu et al., 2021a; Wang and Joachims, 2021). (Patro et al., 2020; Do
et al., 2022) instead discuss two-sided fairness with envy-freeness as user-
side criterion, while (Deldjoo et al., 2021) propose to use generalized cross
entropy to measure unfairness among sensitive groups of users and items. (Wu
et al., 2021b) recently considered two-sided fairness in recommendation as a
multi-objective problem, where each objective corresponds to a different
fairness notion, either for users or items. Similarly, Mehrotra et al. (2020)
aggregate multiple recommendation objectives using a GGF, in a contextual
bandit setting. In their case, the aggregated objectives represent various
metrics (e.g., clicks, dwell time) for various stakeholders. Unlike these two
works (Wu et al., 2021b; Mehrotra et al., 2020), in our case the multiple
objectives are the individual utilities of each user and item, and our goal is
to be fair towards each entity by redistributing utility. To our knowledge, we
are the first to use GGFs as _welfare functions_ of users’ and items’
utilities for two-sided fairness in rankings.

Reciprocal recommender systems received comparatively less attention in the
fairness literature, to the exception of (Jia et al., 2018; Xia et al., 2015;
Paraschakis and Nilsson, 2020). The closest to our work is the additive
welfare approach of (Do et al., 2021), which addresses fairness in both one-
sided and reciprocal recommendation, and is extensively discussed in the
paper, see Sec. 2.1.

In the broader fair machine learning community, several authors advocated for
economic concepts (Finocchiaro et al., 2020), using inequality indices to
quantify and mitigate unfairness (Wilkie and Azzopardi, 2015; Speicher et al.,
2018; Heidari et al., 2018; Lazovich et al., 2022), taking an axiomatic
perspective (Gölz et al., 2019; Cousins, 2021; Williamson and Menon, 2019) or
applying welfare economics principles (Hu and Chen, 2020; Rambachan et al.,
2020). GGFs, in particular, were recently applied to fair multi-agent
reinforcement learning, with multiple reward functions (Busa-Fekete et al.,
2017; Siddique et al., 2020; Zimmer et al., 2021). These works consider
sequential decision-making problems without ranking, and their GGFs aggregate
the objectives of a few agents (typically $n<20$), while in our ranking
problem, there are as many objectives as there are users and items.

##### Nonsmooth convex optimization and differentiable ranking

Our work builds on nonsmooth convex optimization methods (Nesterov, 2005;
Shamir and Zhang, 2013), and in particular variants of the Frank-Wolfe
algorithm (Frank and Wolfe, 1956; Jaggi, 2013) for nonsmooth problems (Lan,
2013; Yurtsever et al., 2018; Ravi et al., 2019; Thekumparampil et al., 2020).
The recent algorithm of (Thekumparampil et al., 2020) is a Frank-Wolfe variant
which uses the Moreau envelope like us. Its number of first-order calls is
optimal, but this is at the cost of a more complex algorithm with inner loops
that make it slow in practice. In our case, since the calculation of the
gradient is not a bottleneck, we use the simpler algorithm of Lan (2013),
which applies Frank-Wolfe to the Moreau envelope of the nonsmooth objective.

Our technical contribution is also related to the literature on differentiable
ranking, which includes a large body of work on approximating learning-to-rank
metrics (Chapelle and Wu, 2010; Taylor et al., 2008; Adams and Zemel, 2011),
and recent growing interest in designing smooth ranking modules (Grover et
al., 2019; Cuturi et al., 2019; Blondel et al., 2020) for end-to-end
differentiation pipelines. The closest method to ours is the differentiable
sorting operator of Blondel et al. (2020), which also relies on isotonic
regression. The differences between our approaches are explained in Remark 1.

##  7\. Conclusion

We proposed generalized Gini welfare functions as a flexible method to produce
fair rankings. We addressed the challenges of optimizing these welfare
functions by leveraging Frank-Wolfe methods for nonsmooth objectives, and
demonstrated their efficiency in ranking applications. Our framework and
algorithm applies to both usual recommendation of movies or music, and to
reciprocal recommendation scenarios, such as dating or hiring.

Generalized Gini welfare functions successfully address a large variety of
fairness requirements for ranking algorithms. On the one hand, GGFs are
effective in reducing inequalities, since they generalize the Gini index in
economics. Optimizing them allows to meet the requirements of equal utility
criteria, largely advocated by existing work on fair recommendation (Singh and
Joachims, 2018; Basu et al., 2020; Patro et al., 2020; Wu et al., 2021a). On
the other hand, GGFs effectively increase the utility of the worse-off, which
is usually measured by quantile ratios in economics, and has been recently
considered as a fairness criterion in ranking (Do et al., 2021).

Our approach is limited to fairness considerations at the stage of inference.
It does not address potential biases arising at other parts of the
recommendation pipeline, such as in the estimation of preferences. Moreover,
we considered a static model, which does not accounts for real-world dynamics,
such as responsiveness in two-sided markets (Su et al., 2021), feedback loops
in the learning process (Bottou et al., 2013), and the changing nature of the
users’ and items’ populations (Morik et al., 2020) and preferences (Kalimeris
et al., 2021). Addressing these limitations, in combination with our method,
are interesting directions for future research.

###### Acknowledgements.

We would like to thank Sam Corbett-Davies for his thoughtful feedback on this
work.

## References

  * (1)
  * Abdollahpouri et al. (2020) Himan Abdollahpouri, Gediminas Adomavicius, Robin Burke, Ido Guy, Dietmar Jannach, Toshihiro Kamishima, Jan Krasnodebski, and Luiz Pizzato. 2020.  Multistakeholder recommendation: Survey and research directions.  _User Modeling and User-Adapted Interaction_ 30, 1 (2020), 127–158.
  * Abdollahpouri et al. (2019) Himan Abdollahpouri, Masoud Mansoury, Robin Burke, and Bamshad Mobasher. 2019.  The unfairness of popularity bias in recommendation.  _arXiv preprint arXiv:1907.13286_ (2019).
  * Adams and Zemel (2011) Ryan Prescott Adams and Richard S Zemel. 2011.  Ranking via sinkhorn propagation.  _arXiv preprint arXiv:1106.1925_ (2011).
  * Atkinson (1970) Anthony B Atkinson. 1970\.  On the measurement of inequality.  _Journal of economic theory_ 2, 3 (1970), 244–263.
  * Basu et al. (2020) Kinjal Basu, Cyrus DiCiccio, Heloise Logan, and Noureddine El Karoui. 2020.  A Framework for Fairness in Two-Sided Marketplaces.  _arXiv preprint arXiv:2006.12756_ (2020).
  * Beck and Teboulle (2012) Amir Beck and Marc Teboulle. 2012.  Smoothing and first order methods: A unified framework.  _SIAM Journal on Optimization_ 22, 2 (2012), 557–580.
  * Best et al. (2000) Michael J Best, Nilotpal Chakravarti, and Vasant A Ubhaya. 2000\.  Minimizing separable convex functions subject to simple chain constraints.  _SIAM Journal on Optimization_ 10, 3 (2000), 658–672.
  * Biega et al. (2018) Asia J Biega, Krishna P Gummadi, and Gerhard Weikum. 2018\.  Equity of attention: Amortizing individual fairness in rankings. In _The 41st international acm sigir conference on research & development in information retrieval_. 405–414.
  * Birkhoff (1940) Garrett Birkhoff. 1940\.  _Lattice theory_. Vol. 25.  American Mathematical Soc.
  * Blondel et al. (2020) Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. 2020.  Fast differentiable sorting and ranking. In _International Conference on Machine Learning_. PMLR, 950–959.
  * Bottou et al. (2013) Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. 2013\.  Counterfactual reasoning and learning systems: The example of computational advertising.  _The Journal of Machine Learning Research_ 14, 1 (2013), 3207–3260.
  * Burke (2017) Robin Burke. 2017\.  Multisided fairness for recommendation.  _arXiv preprint arXiv:1707.00093_ (2017).
  * Busa-Fekete et al. (2017) Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. 2017.  Multi-objective bandits: Optimizing the generalized Gini index. In _International Conference on Machine Learning_. PMLR, 625–634.
  * Cantador et al. (2011) Iván Cantador, Peter Brusilovsky, and Tsvi Kuflik. 2011\.  2nd Workshop on Information Heterogeneity and Fusion in Recommender Systems (HetRec 2011). In _Proceedings of the 5th ACM conference on Recommender systems_ (Chicago, IL, USA) _(RecSys 2011)_. ACM, New York, NY, USA.
  * Chapelle and Wu (2010) Olivier Chapelle and Mingrui Wu. 2010.  Gradient descent optimization of smoothed information retrieval metrics.  _Information retrieval_ 13, 3 (2010), 216–235.
  * Chen et al. (2012) Xi Chen, Qihang Lin, Seyoung Kim, Jaime G Carbonell, and Eric P Xing. 2012.  Smoothing proximal gradient method for general structured sparse learning.  _arXiv preprint arXiv:1202.3708_ (2012).
  * Clarkson (2010) Kenneth L Clarkson. 2010\.  Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm.  _ACM Transactions on Algorithms (TALG)_ 6, 4 (2010), 1–30.
  * Cousins (2021) Cyrus Cousins. 2021\.  An axiomatic theory of provably-fair welfare-centric machine learning.  _Advances in Neural Information Processing Systems_ 34 (2021).
  * Cowell (1988) Frank A Cowell. 1988\.  Inequality decomposition: three bad measures.  _Bulletin of Economic Research_ 40, 4 (1988), 309–312.
  * Cowell (2000) Frank A Cowell. 2000\.  Measurement of inequality.  _Handbook of income distribution_ 1 (2000), 87–166.
  * Cuturi et al. (2019) Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. 2019\.  Differentiable Ranking and Sorting using Optimal Transport. In _Advances in Neural Information Processing Systems_. 6858–6868.
  * Dalton (1920) Hugh Dalton. 1920\.  The measurement of the inequality of incomes.  _The Economic Journal_ 30, 119 (1920), 348–361.
  * Datta et al. (2015) Amit Datta, Michael Carl Tschantz, and Anupam Datta. 2015\.  Automated experiments on ad privacy settings.  _Proceedings on Privacy Enhancing Technologies_ 2015, 1 (2015), 92–112.
  * De Domenico et al. (2013) Manlio De Domenico, Antonio Lima, Paul Mougel, and Mirco Musolesi. 2013.  The anatomy of a scientific rumor.  _Scientific reports_ 3, 1 (2013), 1–9.
  * Deldjoo et al. (2021) Yashar Deldjoo, Vito Walter Anelli, Hamed Zamani, Alejandro Bellogin, and Tommaso Di Noia. 2021.  A flexible framework for evaluating user and item fairness in recommender systems.  _User Modeling and User-Adapted Interaction_ (2021), 1–55.
  * Diaz et al. (2020) Fernando Diaz, Bhaskar Mitra, Michael D Ekstrand, Asia J Biega, and Ben Carterette. 2020.  Evaluating stochastic rankings with expected exposure. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. 275–284.
  * Do et al. (2021) Virginie Do, Sam Corbett-Davies, Jamal Atif, and Nicolas Usunier. 2021.  Two-sided fairness in rankings via Lorenz dominance.  _Advances in Neural Information Processing Systems_ 34 (2021).
  * Do et al. (2022) Virginie Do, Sam Corbett-Davies, Jamal Atif, and Nicolas Usunier. 2022.  Online certification of preference-based fairness for personalized recommender systems. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36.
  * Ekstrand et al. (2018) Michael D Ekstrand, Mucun Tian, Ion Madrazo Azpiazu, Jennifer D Ekstrand, Oghenemaro Anuyah, David McNeill, and Maria Soledad Pera. 2018\.  All the cool kids, how do they fit in?: Popularity and demographic biases in recommender evaluation and effectiveness. In _Conference on Fairness, Accountability and Transparency_. PMLR, 172–186.
  * Finocchiaro et al. (2020) Jessie Finocchiaro, Roland Maio, Faidra Monachou, Gourab K Patro, Manish Raghavan, Ana-Andreea Stoica, and Stratis Tsirtsis. 2020.  Bridging Machine Learning and Mechanism Design towards Algorithmic Fairness.  _arXiv preprint arXiv:2010.05434_ (2020).
  * Frank and Wolfe (1956) Marguerite Frank and Philip Wolfe. 1956.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ 3, 1-2 (1956), 95–110.
  * Geoffrion (1968) Arthur M Geoffrion. 1968\.  Proper efficiency and the theory of vector maximization.  _Journal of mathematical analysis and applications_ 22, 3 (1968), 618–630.
  * Gini (1921) Corrado Gini. 1921\.  Measurement of inequality of incomes.  _The economic journal_ 31, 121 (1921), 124–126.
  * Gölz et al. (2019) Paul Gölz, Anson Kahng, and Ariel D Procaccia. 2019\.  Paradoxes in Fair Machine Learning.  _Advances in Neural Information Processing Systems (NeurIPS). Forthcoming_ (2019).
  * Grover et al. (2019) Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. 2019\.  Stochastic optimization of sorting networks via continuous relaxations.  _arXiv preprint arXiv:1903.08850_ (2019).
  * Hardy et al. (1952) G. H. Hardy, J. E. Littlewood, and George Pólya. 1952\.  Inequalities. 2nd ed.  Cambridge, Engl.: At the University Press. XII, 324 p. (1952)..
  * Harper and Konstan (2015) F Maxwell Harper and Joseph A Konstan. 2015.  The movielens datasets: History and context.  _Acm transactions on interactive intelligent systems (tiis)_ 5, 4 (2015), 1–19.
  * Heidari et al. (2018) Hoda Heidari, Claudio Ferrari, Krishna Gummadi, and Andreas Krause. 2018.  Fairness behind a veil of ignorance: A welfare analysis for automated decision making. In _Advances in Neural Information Processing Systems_. 1265–1276.
  * Hu and Chen (2020) Lily Hu and Yiling Chen. 2020.  Fair classification and social welfare. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_. 535–545.
  * Jaggi (2013) Martin Jaggi. 2013\.  Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In _International Conference on Machine Learning_. PMLR, 427–435.
  * Jia et al. (2018) Yongzheng Jia, Xue Liu, and Wei Xu. 2018.  When Online Dating Meets Nash Social Welfare: Achieving Efficiency and Fairness. In _Proceedings of the 2018 World Wide Web Conference_. 429–438.
  * Kalimeris et al. (2021) Dimitris Kalimeris, Smriti Bhagat, Shankar Kalyanaraman, and Udi Weinsberg. 2021.  Preference Amplification in Recommender Systems. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 805–815.
  * Kletti et al. (2022) Till Kletti, Jean-Michel Renders, and Patrick Loiseau. 2022\.  Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings. In _Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining_. 498–507.
  * Lan (2013) Guanghui Lan. 2013\.  The complexity of large-scale convex programming under a linear optimization oracle.  _arXiv preprint arXiv:1309.5550_ (2013).
  * Lazovich et al. (2022) Tomo Lazovich, Luca Belli, Aaron Gonzales, Amanda Bower, Uthaipon Tantipongpipat, Kristian Lum, Ferenc Huszar, and Rumman Chowdhury. 2022\.  Measuring Disparate Outcomes of Content Recommendation Algorithms with Distributional Inequality Metrics.  _arXiv preprint arXiv:2202.01615_ (2022).
  * Lim and Wright (2016) Cong Han Lim and Stephen J Wright. 2016.  Efficient bregman projections onto the permutahedron and related polytopes. In _Artificial Intelligence and Statistics_. PMLR, 1205–1213.
  * Mehrotra et al. (2017) Rishabh Mehrotra, Ashton Anderson, Fernando Diaz, Amit Sharma, Hanna Wallach, and Emine Yilmaz. 2017\.  Auditing search engines for differential satisfaction across demographics. In _Proceedings of the 26th international conference on World Wide Web companion_. 626–633.
  * Mehrotra et al. (2020) Rishabh Mehrotra, Niannan Xue, and Mounia Lalmas. 2020\.  Bandit based Optimization of Multiple Objectives on a Music Streaming Platform. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 3224–3233.
  * Miettinen (2012) Kaisa Miettinen. 2012\.  _Nonlinear multiobjective optimization_. Vol. 12.  Springer Science & Business Media.
  * Moreau (1962) Jean Jacques Moreau. 1962\.  Fonctions convexes duales et points proximaux dans un espace hilbertien.  _Comptes rendus hebdomadaires des séances de l’Académie des sciences_ 255 (1962), 2897–2899.
  * Morik et al. (2020) Marco Morik, Ashudeep Singh, Jessica Hong, and Thorsten Joachims. 2020.  _Controlling Fairness and Bias in Dynamic Learning-to-Rank_.  Association for Computing Machinery, New York, NY, USA, 429–438.  https://doi.org/10.1145/3397271.3401100
  * Moulin (2003) Hervé Moulin. 2003\.  _Fair division and collective welfare_.  MIT press.
  * Negrinho and Martins (2014) Renato Negrinho and Andre Martins. 2014.  Orbit regularization.  _Advances in neural information processing systems_ 27 (2014), 3221–3229.
  * Nesterov (2005) Yu Nesterov. 2005\.  Smooth minimization of non-smooth functions.  _Mathematical programming_ 103, 1 (2005), 127–152.
  * Nesterov (2018) Yu Nesterov. 2018\.  Complexity bounds for primal-dual methods minimizing the model of objective function.  _Mathematical Programming_ 171, 1 (2018), 311–330.
  * Ogryczak and Śliwiński (2003) Włodzimierz Ogryczak and Tomasz Śliwiński. 2003.  On solving linear programs with the ordered weighted averaging objective.  _European Journal of Operational Research_ 148, 1 (2003), 80–91.
  * Palomares et al. (2021) Iván Palomares, Carlos Porcel, Luiz Pizzato, Ido Guy, and Enrique Herrera-Viedma. 2021.  Reciprocal Recommender Systems: Analysis of state-of-art literature, challenges and opportunities towards social recommendation.  _Information Fusion_ 69 (2021), 103–127.
  * Paraschakis and Nilsson (2020) Dimitris Paraschakis and Bengt J Nilsson. 2020.  Matchmaking under fairness constraints: a speed dating case study. In _International Workshop on Algorithmic Bias in Search and Recommendation_. Springer, 43–57.
  * Parikh and Boyd (2014) Neal Parikh and Stephen Boyd. 2014.  Proximal algorithms.  _Foundations and Trends in optimization_ 1, 3 (2014), 127–239.
  * Patro et al. (2020) Gourab K Patro, Arpita Biswas, Niloy Ganguly, Krishna P. Gummadi, and Abhijnan Chakraborty. 2020\.  _FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms_.  Association for Computing Machinery, New York, NY, USA, 1194–1204.  https://doi.org/10.1145/3366423.3380196
  * Rambachan et al. (2020) Ashesh Rambachan, Jon Kleinberg, Sendhil Mullainathan, and Jens Ludwig. 2020.  _An economic approach to regulating algorithms_.  Technical Report. National Bureau of Economic Research.
  * Ravi et al. (2019) Sathya N Ravi, Maxwell D Collins, and Vikas Singh. 2019\.  A deterministic nonsmooth frank wolfe algorithm with coreset guarantees.  _Informs Journal on Optimization_ 1, 2 (2019), 120–142.
  * Shamir and Zhang (2013) Ohad Shamir and Tong Zhang. 2013.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In _International conference on machine learning_. PMLR, 71–79.
  * Shorrocks (1983) Anthony F Shorrocks. 1983\.  Ranking income distributions.  _Economica_ 50, 197 (1983), 3–17.
  * Siddique et al. (2020) Umer Siddique, Paul Weng, and Matthieu Zimmer. 2020.  Learning Fair Policies in Multi-Objective (Deep) Reinforcement Learning with Average and Discounted Rewards. In _International Conference on Machine Learning_. PMLR, 8905–8915.
  * Singh and Joachims (2018) Ashudeep Singh and Thorsten Joachims. 2018.  Fairness of exposure in rankings. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. ACM, 2219–2228.
  * Speicher et al. (2018) Till Speicher, Hoda Heidari, Nina Grgic-Hlaca, Krishna P Gummadi, Adish Singla, Adrian Weller, and Muhammad Bilal Zafar. 2018\.  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_. ACM, 2239–2248.
  * Su et al. (2021) Yi Su, Magd Bayoumi, and Thorsten Joachims. 2021.  Optimizing Rankings for Recommendation in Matching Markets.  _arXiv preprint arXiv:2106.01941_ (2021).
  * Sweeney (2013) Latanya Sweeney. 2013\.  Discrimination in online ad delivery.  _Queue_ 11, 3 (2013), 10.
  * Taylor et al. (2008) Michael Taylor, John Guiver, Stephen Robertson, and Tom Minka. 2008.  Softrank: optimizing non-smooth rank metrics. In _Proceedings of the 2008 International Conference on Web Search and Data Mining_. 77–86.
  * Thekumparampil et al. (2020) Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. 2020.  Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method. In _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 12211–12224.  https://proceedings.neurips.cc/paper/2020/file/8f468c873a32bb0619eaeb2050ba45d1-Paper.pdf
  * Wang and Joachims (2021) Lequn Wang and Thorsten Joachims. 2021.  User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets. In _Proceedings of the 2021 ACM SIGIR International Conference on Theory of Information Retrieval_. 23–41.
  * Weymark (1981) John A Weymark. 1981\.  Generalized Gini inequality indices.  _Mathematical Social Sciences_ 1, 4 (1981), 409–430.
  * Wilkie and Azzopardi (2014) Colin Wilkie and Leif Azzopardi. 2014.  Best and fairest: An empirical analysis of retrieval system bias. In _European Conference on Information Retrieval_. Springer, 13–25.
  * Wilkie and Azzopardi (2015) Colin Wilkie and Leif Azzopardi. 2015.  Retrievability and retrieval bias: A comparison of inequality measures. In _European Conference on Information Retrieval_. Springer, 209–214.
  * Williamson and Menon (2019) Robert Williamson and Aditya Menon. 2019.  Fairness risk measures. In _International Conference on Machine Learning_. PMLR, 6786–6797.
  * Wu et al. (2021b) Haolun Wu, Chen Ma, Bhaskar Mitra, Fernando Diaz, and Xue Liu. 2021b.  Multi-FR: A Multi-Objective Optimization Method for Achieving Two-sided Fairness in E-commerce Recommendation.  _arXiv preprint arXiv:2105.02951_ (2021).
  * Wu et al. (2021a) Yao Wu, Jian Cao, Guandong Xu, and Yudong Tan. 2021a.  TFROM: A Two-sided Fairness-Aware Recommendation Model for Both Customers and Providers.  _arXiv preprint arXiv:2104.09024_ (2021).
  * Xia et al. (2015) Peng Xia, Benyuan Liu, Yizhou Sun, and Cindy Chen. 2015\.  Reciprocal recommendation system for online dating. In _2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)_. IEEE, 234–241.
  * Yager (1988) Ronald R Yager. 1988\.  On ordered weighted averaging aggregation operators in multicriteria decisionmaking.  _IEEE Transactions on systems, Man, and Cybernetics_ 18, 1 (1988), 183–190.
  * Yitzhaki and Schechtman (2013) Shlomo Yitzhaki and Edna Schechtman. 2013.  More than a dozen alternative ways of spelling Gini.  In _The Gini Methodology_. Springer, 11–31.
  * Yosida et al. (1965) Kôsaku Yosida et al. 1965\.  Functional analysis.  (1965).
  * Yurtsever et al. (2018) Alp Yurtsever, Olivier Fercoq, Francesco Locatello, and Volkan Cevher. 2018.  A conditional gradient framework for composite convex minimization with applications to semidefinite programming. In _International Conference on Machine Learning_. PMLR, 5727–5736.
  * Zehlike and Castillo (2020) Meike Zehlike and Carlos Castillo. 2020.  Reducing disparate exposure in ranking: A learning to rank approach. In _Proceedings of The Web Conference 2020_. 2849–2855.
  * Zimmer et al. (2021) Matthieu Zimmer, Claire Glanois, Umer Siddique, and Paul Weng. 2021.  Learning fair policies in decentralized cooperative multi-agent reinforcement learning. In _International Conference on Machine Learning_. PMLR, 12967–12978.