Virginie Do
email: virginiedo@fb.com

Optimizing generalized Gini indices for fairness in rankings

Keywords: Information systems → Retrieval models and ranking fairness, ranking, recommender systems, welfare economics

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 15k users and items, which show that our approach obtains better trade-offs than the baselines on a variety of recommendation tasks and fairness criteria.

the side of item producers, the growing literature on fairness of exposure aims to avoid popularity biases [START_REF] Abdollahpouri | The unfairness of popularity bias in recommendation[END_REF] by reducing inequalities in the exposure of different items [START_REF] Singh | Fairness of exposure in rankings[END_REF], or aiming for equal exposure weighted by relevance [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF][START_REF] Diaz | Evaluating stochastic rankings with expected exposure[END_REF][START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF]. 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, [START_REF] Weymark | Generalized Gini inequality indices[END_REF]) from the economic literature on inequality measurement [START_REF] Frank | Measurement of inequality[END_REF]. 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 [START_REF] Gini | Measurement of inequality of incomes[END_REF], they can be used to optimize trade-offs between exposure inequality among items and user utility, a goal seeked by many authors [START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF][START_REF] Zehlike | Reducing disparate exposure in ranking: A learning to rank approach[END_REF]. GGFs also conveniently specify normative criteria based on utility quantiles [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF]: 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 [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF].

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 [START_REF] Frank | An algorithm for quadratic programming[END_REF] was shown to be a computationally efficient method for maximizing globally fair ranking objectives, requiring only one top-𝐾 sort operation per user at each iteration [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF]. 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 [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF][START_REF] Kiran K Thekumparampil | Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method[END_REF][START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF]. These methods usually optimize smoothed surrogate objective functions, while gradually decreasing a smoothing parameter, and a common smoothing technique uses the Moreau envelope [START_REF] Jacques | Fonctions convexes duales et points proximaux dans un espace hilbertien[END_REF][START_REF] Yosida | Functional analysis[END_REF]. Our main insight is that the gradient of the Moreau envelope of GGFs can be computed in 𝑂 (𝑛 log 𝑛) operations, where 𝑛 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 15𝑘 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. [START_REF] Prescott | Ranking via sinkhorn propagation[END_REF] we provide the details of our algorithm and the convergence guarantees. Our experimental results are reported in Sec. [START_REF] Anthony B Atkinson | On the measurement of inequality[END_REF], 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.

FAIR RANKING WITH GENERALIZED GINI 2.1 Recommendation framework

We consider a recommendation scenario with 𝑛 users, and 𝑚 items, and 𝐾 recommendation slots. 𝜇 𝑖 𝑗 ∈ [0, 1] denotes the value of item 𝑗 for user 𝑖 (e.g, a "liking" probability), and we assume the values 𝜇 are given as input to the system. The goal of the system is to produce a ranked list of items for each of the 𝑛 users. Following previous work on fair rankings [e.g. 66], 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 𝑖 is represented by a bistochastic matrix 𝑃 𝑖 ∈ R 𝑚×𝑚 , where 𝑃 𝑖 𝑗𝑘 is the probability that item 𝑗 is recommended to user 𝑖 at position 𝑘. The recommender system is characterized by a ranking policy 𝑃 = (𝑃 𝑖 ) 𝑛 𝑖=1 . We denote the convex set of ranking policies by 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" [START_REF] Moulin | Fair division and collective welfare[END_REF]. Similarly to [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF][START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF][START_REF] Wang | User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets[END_REF], 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 [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF][START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF][START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF] with weights 𝒃 ∈ R 𝑚 + . The weight 𝑏 𝑘 is the probability that a user examines the item at position 𝑘, and we assume that the weights are non-increasing. Since there are 𝐾 recommendation slots, we have 𝑏 1 ≥ . . . ≥ 𝑏 𝐾 and 𝑏 𝑘 = 0 for any 𝑘 > 𝐾. The user and item utilities are then:

User utility: 𝑢 𝑖 (𝑃) = 𝑚 ∑ 𝑗=1 𝜇 𝑖 𝑗 𝑃 ⊤ 𝑖 𝑗 𝒃 Item exposure: 𝑣 𝑗 (𝑃) = 𝑛 ∑ 𝑖=1 𝑃 ⊤ 𝑖 𝑗 𝒃. (1)
We follow a general framework where the ranking policy 𝑃 is found by maximizing a global welfare function 𝐹 (𝑃), and the welfare function is a weighted sum of welfare functions for users and items:

𝐹 (𝑃) = (1 -𝜆)𝑔 user (𝒖 (𝑃)) + 𝜆𝑔 item (𝒗 (𝑃)), (2)
where 𝑔 user : R 𝑛 → R and 𝑔 item : R 𝑚 → R respectively aggregate the utilities of users and item exposures and 𝜆 ∈ [0, 1] specifies the relative weight of users and items.

Generalized Gini welfare functions

In this work, we focus on the case where 𝑔 item and 𝑔 user are based on Generalized Gini welfare Functions (GGFs) [START_REF] Weymark | Generalized Gini inequality indices[END_REF]). A GGF 𝑔 𝒘 : R 𝑛 → R is a function parameterized by a vector 𝒘 ∈ R 𝑛 of nonincreasing positive weights such that 𝑤 1 = 1 ≥ . . . ≥ 𝑤 𝑛 ≥ 0, and defined by a weighted sum of its sorted inputs, which is also called an ordered weighted averaging operator (OWA) [START_REF] Ronald R Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF]. Formally, let 𝒙 ∈ R 𝑛 be a utility vector and denote by 𝒙 ↑ the values of 𝒙 sorted in increasing order, i.e., 𝑥

↑ 1 ≤ ... ≤ 𝑥 ↑ 𝑛 . Then: 𝑔 𝒘 (𝒙) = 𝑛 ∑ 𝑖=1 𝑤 𝑖 𝑥 ↑ 𝑖 . Let V 𝑛 = {𝒘 ∈ R 𝑛 : 𝑤 1 = 1 ≥ . . . ≥ 𝑤 𝑛 ≥ 0}
be the set of admissible weights of GGFs. Given 𝒘1 ∈ V 𝑛 , 𝒘 2 ∈ V 𝑚 and 𝜆 ∈ (0, 1), we define the two-sided GGF as the welfare function [START_REF] Abdollahpouri | The unfairness of popularity bias in recommendation[END_REF] with 𝑔 user = 𝑔 𝒘 1 and 𝑔 item = 𝑔 𝒘 2 :

𝐹 𝜆,𝒘 1 ,𝒘 2 (𝑃) = (1 -𝜆)𝑔 𝒘 1 𝒖 (𝑃) + 𝜆𝑔 𝒘 2 (𝒗 (𝑃) . (3)
With non-increasing, non-negative weights 𝒘, OWA operators are concave [START_REF] Ronald R Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF]. The maximization of 𝐹 𝜆,𝒘 1 ,𝒘 2 (𝑃) (3) 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 [START_REF] Moulin | Fair division and collective welfare[END_REF], 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 𝑤 𝑖 > 0 for all 𝑖, 𝑔 𝒘 is increasing with respect to every individual utilities, which ensures that maximizers of GGFs are Pareto-optimal [START_REF] Moulin | Fair division and collective welfare[END_REF]. The Gini index of 𝒙, denoted Gini(𝒙) is associated to the GGF 𝑔 𝒘 (𝒙) with 𝑤 𝑖 = (𝑛-𝑖+1) /𝑛 [for formulas of Gini index, see 81]:

Gini(𝒙) = 1 - 2 ∥𝒙 ∥ 1 𝑛 ∑ 𝑖=1 𝑛 -𝑖 + 1 𝑛 𝑥 ↑ 𝑖 (4) = 1 𝑛 2 𝒙 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 |𝑥 𝑖 -𝑥 𝑗 | with 𝒙 = 1 𝑛 𝑛 ∑ 𝑖=1 𝑥 𝑖 .
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 ∥𝒙 ∥ 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 [START_REF] Anthony B Atkinson | On the measurement of inequality[END_REF], and by [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] in the context of fairness in rankings. Yet, when 𝒙 is a vector of item exposures 𝒙 = 𝒗 (𝑃), 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 𝑔 𝒘 (𝒙) is based on the generalized Lorenz curve 1 [START_REF] Anthony | Ranking income distributions[END_REF] of 𝒙, which is denoted 𝑿 and is defined as the vector of cumulative sums of sorted utilities:

𝑔 𝒘 (𝒙) = 𝑛 ∑ 𝑖=1 𝑤 ′ 𝑖 𝑋 𝑖 where 𝑤 ′ 𝑖 = 𝑤 𝑖 -𝑤 𝑖+1 and 𝑋 𝑖 = 𝑥 ↑ 1 + . . . + 𝑥 ↑ 𝑖 .(5)
We used the convention 𝑤 𝑛+1 = 0. Notice that since the weights 𝒘 are non-increasing, we have that 𝑤 ′ 𝑖 ≥ 0. Thus, family of admissible OWA weights 𝒘 yield weights 𝒘 ′ 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 [START_REF] Arthur M Geoffrion | Proper efficiency and the theory of vector maximization[END_REF][START_REF] Miettinen | Nonlinear multiobjective optimization[END_REF]. We get back to this interpretation in the next subsections.

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. [START_REF] Prescott | Ranking via sinkhorn propagation[END_REF].

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 [START_REF] Singh | Fairness of exposure in rankings[END_REF][START_REF] Wu | TFROM: A Two-sided Fairness-Aware Recommendation Model for Both Customers and Providers[END_REF][START_REF] Zehlike | Reducing disparate exposure in ranking: A learning to rank approach[END_REF]. 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 [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF][START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF]). Removing the dependency on 𝑃 to lighten the notation, a natural formulation of this trade-off uses the two-sided GGF (3) by setting 𝒘 1 = (1, . . . , 1) and

𝒘 2 = 𝑚-𝑗+1 𝑚 𝑚 𝑗=1
, which yields:

𝑔 user (𝒖) = 1 𝑛 𝑛 ∑ 𝑖=1 𝑢 𝑖 𝑔 item (𝒗) = 𝑚 ∑ 𝑗=1 𝑚 -𝑗 + 1 𝑚 𝑣 ↑ 𝑗 . (6)
As stated in the previous section, for item exposure, maximizing 𝑔 item is equivalent to minimizing the Gini index. The Gini index for 𝑔 item has been routinely used for evaluating inequality in item exposure [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF][START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF] but there is no algorithm to optimize general tradeoffs between user utility and the Gini index of exposure. Morik et al. [START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF] use the Gini index of exposures in the context of dynamic ranking (with the absolute pairwise differences formula (4)), where their algorithm is shown to asymptotically drive 𝑔 item (𝒗) to 0, equivalent to 𝜆 → 1 in (2). However, their algorithm cannot be used to converge to the optimal rankings for other values of 𝜆. Do et al. [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] 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 [START_REF] Abdollahpouri | The unfairness of popularity bias in recommendation[END_REF] with this instantiation of 𝑔 item given by eq. ( 6).

Several authors [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF][START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF] used merit-weighted exposure 2 𝒗 ′ 𝑗 (𝑃) = 𝒗 (𝑃)/𝜇 𝑗 where 𝜇 𝑗 = 1 𝑛 𝑛 𝑖=1 𝜇 𝑖 𝑗 is the average value of item 𝑗 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 (6) with meritweighted exposures is not strictly equivalent to minimizing the Gini index.

2 also called "equity of attention" [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF], "disparate treatment" [START_REF] Singh | Fairness of exposure in rankings[END_REF] Two-sided fairness. Do et al. [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] 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 (5) of GGFs, trade-offs between maximizing the cumulative utility at a specific quantile 𝑞 of users and total utility can be formulated using a parameter 𝜔 ∈ [0, 1] as follows:

𝑔 user (𝒖) = 𝑛 ∑ 𝑖=1 𝑤 ′ 𝑖 𝑈 𝑖 with 𝑤 ′ ⌊𝑞𝑛⌋ = 𝜔 and 𝑤 ′ 𝑛 = 1 -𝜔, (7)
where all other values of 𝑤 ′ 𝑖 = 0. In our experiments, we combine this 𝑔 user with the Gini index for 𝑔 item for two-sided fairness.

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 [START_REF] Anthony B Atkinson | On the measurement of inequality[END_REF][START_REF] Moulin | Fair division and collective welfare[END_REF][START_REF] Anthony | Ranking income distributions[END_REF], 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. [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] 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 𝐹 𝜆,𝒘 1 ,𝒘 2 (𝑃) (3) 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 [START_REF] Arthur M Geoffrion | Proper efficiency and the theory of vector maximization[END_REF][START_REF] Miettinen | Nonlinear multiobjective optimization[END_REF]. We give here the formal statements for exhaustivity.

Let 𝒙 and 𝒙 ′ two vectors in R 𝑛 + . We say that 𝒙 weakly-Lorenzdominates 𝒙 ′ , denoted 𝒙 ⪰ L 𝒙 ′ , when the generalized Lorenz curve of 𝒙 is always at least equal to that of 𝒙 ′ , i.e., 𝒙 ⪰ L 𝒙 ′ ⇐⇒ ∀𝑖, 𝑋 𝑖 ≥ 𝑋 ′ 𝑖 . We say that 𝒙 Lorenz-dominates 𝒙 ′ , denoted 𝒙 ≻ L 𝒙 ′ if 𝒙 ⪰ L 𝒙 ′ and 𝒙 ≠ 𝒙 ′ , i.e., if the generalized Lorenz curve of 𝒙 is strictly larger than that of 𝒙 ′ on at least one point. The criterion that generalized Lorenz curves of users and items are not jointlydominated is captured by the notion of Lorenz-efficiency: Definition 1 (Do et al. [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF]). A ranking policy 𝑃 ∈ P is Lorenzefficient if there is no 𝑃 ′ ∈ P such that either [𝒖 (𝑃 ′ ) ⪰ L 𝒖 (𝑃) and

𝒗 (𝑃 ′ ) ≻ L 𝒗 (𝑃)] or [𝒗 (𝑃 ′ ) ⪰ L 𝒗 (𝑃) and 𝒖 (𝑃 ′ ) ≻ L 𝒖 (𝑃)].
We now present the main result of this section:

Proposition 2. Let Θ = (0, 1) × V 𝑛 × V 𝑚 .
(1) Let (𝜆, 𝒘 1 , 𝒘 2 ) ∈ Θ, where 𝒘 1 and 𝒘 2 have strictly decreasing weights, and

𝑃 * ∈ argmax 𝑃 ∈ P 𝐹 𝜆,𝒘 1 ,𝒘 2 (𝑃). Then 𝑃 * is Lorenz-efficient. (2) If 𝑃 is Lorenz efficient, then there exists (𝜆, 𝒘 1 , 𝒘 2 ) ∈ Θ such that 𝑃 ∈ argmax 𝑃 ∈ P 𝐹 𝜆,𝒘 1 ,𝒘 2 (𝑃).
Proof. The proof uses standard results on convex multi-objective optimization from [START_REF] Arthur M Geoffrion | Proper efficiency and the theory of vector maximization[END_REF][START_REF] Miettinen | Nonlinear multiobjective optimization[END_REF]. Written in the form (5), 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 𝑛 + 𝑚 objectives. Indeed, each objective function is a point of the generalized Lorenz curve (𝑼 (𝑃), 𝑽 (𝑃)). Each objective 𝑈 𝑖 (𝑃) is concave because it corresponds to an OWA operator with non-increasing weights 𝝆 with 𝜌 𝑖 ′ = 1 {𝑖 ′ ≤𝑖 } , applied to utilities, which are linear functions of the ranking policy. Each objective 𝑉 𝑖 (𝑃) is similarly concave. Moreover, we are optimizing over the convex set of stochastic ranking policies P. The multi-objective problem is then concave, which means that the maximizers of all weighted sums of the objectives (𝑼 (𝑃), 𝑽 (𝑃)) with strictly positive weights are Pareto-efficient. Reciprocally every Pareto-efficient solution is a solution of a non-negative weighted sum of the objectives (𝑼 (𝑃), 𝑽 (𝑃)), where the weights sum to 1 [START_REF] Miettinen | Nonlinear multiobjective optimization[END_REF].

The result follows from the observation that the Lorenz-efficiency of 𝑃, defined as the Lorenz-efficiency of (𝒖 (𝑃), 𝒗 (𝑃)), is equivalent to the Pareto-efficiency of its joint user-item Lorenz curves (𝑼 (𝑃), 𝑽 (𝑃)). This is because the Lorenz dominance relation between vectors 𝒙, 𝒙 ′ is defined as Pareto dominance in the space of their generalized Lorenz curves 𝑿, 𝑿 ′ . □

Additive welfare functions vs GGFs. Do et al. [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] use additive concave welfare functions to generate Lorenz-efficient rankings. Let [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] use concave welfare functions of the form:

𝜙 (𝑥, 𝛼) = 𝑥 𝛼 if 𝛼 > 0, 𝜙 (𝑥, 𝛼) = log(𝑥) if 𝛼 = 0 and 𝜙 (𝑥, 𝛼) = -𝑥 𝛼 if 𝛼 < 0. Do et al.
𝑔 user (𝒖) = 𝑛 ∑ 𝑖=1 𝜙 (𝑢 𝑖 , 𝛼 1 ) 𝑔 item (𝒗) = 𝑚 ∑ 𝑗=1 𝜙 (𝑣 𝑗 , 𝛼 2 ) (8)
Where 𝛼 1 (resp. 𝛼 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 [START_REF] Anthony B Atkinson | On the measurement of inequality[END_REF][START_REF] Frank | Inequality decomposition: three bad measures[END_REF][START_REF] Dalton | The measurement of the inequality of incomes[END_REF], as well as in the study of welfare functions because additive separability follows from a standard axiomatization [START_REF] Moulin | Fair division and collective welfare[END_REF]. However, this leads to a restricted class of functions, so that varying 𝛼 1 , 𝛼 2 and 𝜆 in (8) 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.

OPTIMIZING GENERALIZED GINI WELFARE

In this section, we provide a scalable method for optimizing twosided GGFs welfare functions (3) 𝐹 𝜆,𝒘 1 ,𝒘 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.

Challenges

In multi-objective optimization, a standard approach to optimizing OWAs is to solve the equivalent linear program derived by Ogryczak and Śliwiński [START_REF] Ogryczak | On solving linear programs with the ordered weighted averaging objective[END_REF]. Because the utilities depend on 3dtensors 𝑃 ∈ P in our case, the linear program has 𝑂 (𝑛•𝑚 2 ) variables and constraints, which is prohibitively large in practice. Another approach consists in using online subgradient descent to optimize GGFs, like [START_REF] Busa-Fekete | Multiobjective bandits: Optimizing the generalized Gini index[END_REF][START_REF] Mehrotra | Bandit based Optimization of Multiple Objectives on a Music Streaming Platform[END_REF]. 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 P. On the other hand, the Frank-Wolfe algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF] was shown to provide a computationally efficient and provably convergent method to optimize over P [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF]. However, it only applies to smooth functions, and Frank-Wolfe with subgradients may not converge to an optimal solution [START_REF] Nesterov | Complexity bounds for primal-dual methods minimizing the model of objective function[END_REF].

We turn to Frank-Wolfe variants for nonsmooth objectives, since Frank-Wolfe methods are well-suited to our structured ranking problem [START_REF] Kenneth L Clarkson | Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm[END_REF][START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF][START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-free sparse convex optimization[END_REF]. More precisely, following [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF][START_REF] Kiran K Thekumparampil | Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method[END_REF][START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF], 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 [START_REF] Chen | Smoothing proximal gradient method for general structured sparse learning[END_REF]. Our main technical contribution is to show that the gradient of the Moreau envelope of GGFs can be computed in 𝑂 (𝑛 log 𝑛) operations.

The Moreau envelope of GGFs

In the sequel, ∥𝒛∥ denotes the ℓ 2 norm. Moreover, a function 𝐿 :

X ⊆ R 𝑛 → R is 𝐶-smooth if it is differentiable with 𝐶-Lipschitz continu- ous gradients, i.e., if ∀𝒙, 𝒙 ′ ∈ X , ∥∇𝐿(𝒙) -∇𝐿(𝒙 ′ )∥ ≤ 𝐶 ∥𝒙 -𝒙 ′ ∥ .

Definition and properties.

Let us fix weights 𝒘 ∈ V and focus on maximizing the GGF 𝑔 𝒘 . Let ℎ(𝒛) := -𝑔 𝒘 (𝒛) to obtain a convex function (this simplifies the overall discussion). The function ℎ is ∥𝒘 ∥-Lipschitz continuous, but non-smooth. We consider the smooth approximation of ℎ given by its Moreau envelope [START_REF] Parikh | Proximal algorithms[END_REF] defined as:

ℎ 𝛽 (𝒛) = min 𝒛 ′ ∈R 𝑛 ℎ(𝒛 ′ ) + 1 2𝛽 𝒛 -𝒛 ′ 2 . It is known that ℎ 𝛽 (𝒛) ≤ ℎ(𝒛) ≤ ℎ 𝛽 (𝒛) + 𝛽 2 ∥𝒘 ∥ 2 and that ℎ 𝛽 is 1 𝛽 -smooth [see e.
Proof. Let prox 𝛽ℎ (𝒛) = argmin 𝒛 ′ ∈R 𝑛 𝛽ℎ(𝒛) + 1 2 ∥𝒛 ′ -𝒛∥ 2 denote the proximal operator of 𝛽ℎ. Denoting by 𝒖 * the adjoint of 𝒖, it is known that ∇𝑓 𝛽 (𝑃) = 1 𝛽 𝒖 * (𝒖 (𝑃)prox 𝛽ℎ (𝒖 (𝑃)) [START_REF] Parikh | Proximal algorithms[END_REF]. We first notice that since 𝒘 are non-increasing, the rearrangement inequalities [START_REF] Hardy | [END_REF] gives: ℎ(𝒛) =min

𝜎 ∈𝔖 𝑛 𝒘 ⊺ 𝝈 𝒛 = max 𝜎 ∈𝔖 𝑛 -𝒘 ⊺ 𝝈 𝒛.
Thus, ℎ is the support function of the convex set C( w), since:

ℎ(𝒛) = max 𝜎 ∈𝔖 𝑛 -𝒘 ⊺ 𝝈 𝒛 = sup 𝒚 ∈ C ( w) 𝒚 ⊺ 𝒛.
Then the Fenchel conjugate of ℎ is the indicator function of C( w), and its proximal is the projection Π C ( w) [START_REF] Parikh | Proximal algorithms[END_REF]. By Moreau decomposition, we get prox(𝒛) = 𝒛 -𝛽 Π C ( w) ( 𝒛 /𝛽) , and thus:

∇𝑓 𝛽 (𝑃) = 𝒖 * Π C ( w) ( 𝒖 (𝑃 ) /𝛽) .
The result follows from the definition of 𝒖 (𝑃) = 𝑗,𝑘 𝜇 𝑖 𝑗 𝑃 𝑖 𝑗𝑘 𝑏 𝑘 𝑛 𝑖=1

. □ Overall, computing the gradient of the Moreau envelope boils down to a projection onto the permutahedron C( w). This projection was shown by several authors to be reducible to isotonic regression: Proposition 4 (Reduction to isotonic regression [START_REF] Blondel | Fast differentiable sorting and ranking[END_REF][START_REF] Cong | Efficient bregman projections onto the permutahedron and related polytopes[END_REF][START_REF] Negrinho | Orbit regularization[END_REF]). Let 𝜎 ∈ 𝔖 𝑛 that sorts 𝒛 decreasingly, i.e. 𝑧 𝜎 (1) ≥ . . . ≥ 𝑧 𝜎 (𝑛) . Let 𝒙 be a solution to isotonic regression on 𝒛 𝝈w, i.e.

𝒙 = argmin

𝑥 ′ 1 ≤... ≤𝑥 ′ 𝑛 1 2 ∥𝒙 ′ -(𝒛 𝝈 -w)∥ 2
Then we have:

Π C ( w) (𝒛) = 𝒛 + 𝒙 𝝈 -1 .
Following these works, we use the Pool Adjacent Violators (PAV) algorithm for isotonic regression, which gives a solution in 𝑂 (𝑛) iterations given a sorted input [START_REF] Michael | Minimizing separable convex functions subject to simple chain constraints[END_REF]. The algorithm for computing the projection is summarized in Alg. 1 where we use the notation argsort(𝒛) = {𝜎 ∈ 𝔖 𝑛 : 𝑧 𝜎 (1) ≥ . . . ≥ 𝑧 𝜎 (𝑛) } for permutations that sort 𝒛 ∈ R 𝑛 in decreasing order. Including the sorting of 𝒖 (𝑃 ) 𝛽 , it costs 𝑂 (𝑛 log 𝑛) time and 𝑂 (𝑛) space. Remark 1. Our method is related to the differentiable sorting operator of Blondel et al. [START_REF] Blondel | Fast differentiable sorting and ranking[END_REF], 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 𝑓 𝛽 (𝑃) = ℎ 𝛽 (𝒖 (𝑃)) with user utilities. The gradient of 𝑓 𝛽 (𝑃) = ℎ 𝛽 (𝒗 (𝑃)) using item exposures is computed similarly:

𝜕𝑓 𝛽 𝜕𝑃 𝑖 𝑗𝑘 (𝑃) = 𝑦 𝑗 𝑏 𝑘 with 𝒚 = Π C ( w) 𝒗 (𝑃 ) 𝛽 .

Frank-Wolfe with smoothing

We return to the optimization of the two-sided GGF objective (3).

In this section, we fix the parameters (𝜆, 𝒘 1 , 𝒘 2 ) and consider the minimization of 𝑓 := -𝐹 𝜆,𝒘 1 ,𝒘 2 over P. For 𝛽 > 0 we denote by ℎ 𝛽 1 and ℎ 𝛽 2 the Moreau envelopes of -𝑔 𝒘 1 and -𝑔 𝒘 2 respectively. The smooth approximation of 𝑓 is then:

𝑓 𝛽 (𝑃) := (1 -𝜆)ℎ 𝛽 1 (𝒖 (𝑃)) + 𝜆ℎ 𝛽 2 (𝒗 (𝑃)).
Our algorithm FW-smoothing (Alg. 2) for minimizing 𝑓 uses the Frank-Wolfe method for nonsmooth optimization from Lan [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF] 3 . Given a sequence (𝛽 𝑡 ) 𝑡 ≥1 of positive values decreasing to 0, the algorithm constructs iterates 𝑃 (𝑡 ) by applying Frank-Wolfe updates to 𝑓 𝛽 𝑡 at each iteration 𝑡. More precisely, FW-smoothing finds an update direction with respect to ∇𝑓 𝛽 𝑡 by computing:

𝑄 (𝑡 ) = argmin 𝑃 ∈ P ⟨𝑃 | ∇𝑓 𝛽 𝑡 (𝑃 (𝑡 -1) )⟩. ( 10
)
The update rule is 𝑃 (𝑡 ) = 𝑃 (𝑡 -1) + 2 𝑡 +2 𝑄 (𝑡 ) -𝑃 (𝑡 -1) . Before giving the details of the computation of (10), we note that applying the convergence result of Lan [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF], and denoting 𝐷 P = max 𝑃,𝑃 ′ ∈ P ∥𝑃 -𝑃 ′ ∥ the diameter of P, we obtain 4 : Proposition 5 (Th. 4, [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF]). With 𝛽 0 = 2𝐷 P 𝑏 (𝑇 ) .

Efficient computation of the update direction. For smooth welfare functions of user utilities and item exposures, the update direction (10) can be computed with only one top-𝐾 sorting operation per user [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF]. In our case, the update is given by the following result, where top-𝐾 (𝒛) = {𝜎 ∈ 𝔖 𝑛 : 𝑧 𝜎 (1) ≥ . . . ≥ 𝑧 𝜎 (𝐾) and ∀𝑘 ≥ 𝐾, 𝑧 𝜎 (𝐾) ≥ 𝑧 𝜎 (𝑘) } is the set of permutations that sort the 𝑘 largest elements in 𝒛. Proposition 6. Let μ defined by μ𝑖 𝑗 = (1 -𝜆) 𝑦 1 𝑖 𝜇 𝑖 𝑗 + 𝜆𝑦 2 𝑗 where 𝒚 1 = Π C ( w1 ) 𝒖 (𝑃 (𝑡 -1) ) /𝛽 𝑡 and 𝒚 2 = Π C ( w2 ) 𝒗 (𝑃 (𝑡 -1) ) /𝛽 𝑡 . For all 𝑖 ∈ [[𝑛]], let σ𝑖 ∈ top-𝐾 (-μ𝑖 ) and 𝑄 (𝑡 ) 𝑖 a permutation matrix representing σ𝑖 . Then 𝑄 (𝑡 ) ∈ argmin 𝑃 ∈ P ⟨𝑃 | ∇𝑓 𝛽 𝑡 (𝑃 (𝑡 -1) )⟩. 3 Lan [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF] uses the smoothing scheme of Nesterov [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF] which is in fact equal to the Moreau envelope (see [START_REF] Beck | Smoothing and first order methods: A unified framework[END_REF]Sec. 4.3]). 4 In more details, the convergence guarantee of Lan [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF] uses the operator norm of 𝒖 and 𝒗, which we bound as follows: ∥𝑢 (𝑃 ) ∥ 2 ≤ 𝑖 𝑗,𝑘 (𝜇

𝑖 𝑗 𝑃 𝑖 𝑗𝑘 𝑏 𝑘 ) 2 ≤ 𝑏 2 1 ∥𝑃 ∥ 2 , because 𝜇 𝑖 𝑗 ∈ [0, 1] 𝑏 𝑘 ∈ [0, 𝑏 1 ], and similarly ∥𝒗 (𝑃 ) ∥ 2 ≤ 𝑏 2 1 ∥𝑃 ∥ 2 .
Proof. Using the expression of the gradient of the Moreau envelope derived in Proposition 3, eq. ( 9), we have:

𝜕𝑓 𝛽 𝑡 𝜕𝑃 𝑖 𝑗𝑘 (𝑃 (𝑡 -1) ) = (1 -𝜆) 𝜕 𝜕𝑃 𝑖 𝑗𝑘 (ℎ 𝛽 𝑡 1 (𝒖 (𝑃 (𝑡 -1) )) + 𝜆 𝜕 𝜕𝑃 𝑖 𝑗𝑘 (ℎ 𝛽 𝑡 2 (𝒗 (𝑃 (𝑡 -1) ))

And thus

𝜕𝑓 𝛽 𝑡 𝜕𝑃 𝑖 𝑗𝑘 (𝑃 (𝑡 -1) ) = μ𝑖 𝑗 ×𝑏 𝑘 . The result then follows from [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF]Lem. 3] and is a consequence of the rearrangement inequality [START_REF] Hardy | [END_REF]: 𝑄 (𝑡 ) is obtained by sorting μ𝑖 𝑗 in increasing order, or equivalently, by sorting -μ𝑖 𝑗 in decreasing order. □

Since the computation of the gradient of Moreau envelopes costs 𝑂 (𝑛 ln 𝑛 + 𝑛 ln 𝑚) operations using Alg. 1, then by Prop. 6 at each iteration, the cost of the algorithm is dominated by the top-K sort per user, each of which has amortized complexity of 𝑂 (𝑚 + 𝐾 ln 𝐾): Proposition 7. Each iteration costs 𝑂 (𝑛𝑚 + 𝑛𝐾 ln 𝐾) operations. The total amount of storage required is 𝑂 (𝑛𝐾𝑇 ).

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/ √ 𝑇 , while the Frank-Wolfe algorithm converges in 𝑂 (1/𝑇 ) when the objective is smooth [START_REF] Kenneth L Clarkson | Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm[END_REF].

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 [START_REF] Birkhoff | Lattice theory[END_REF] of the bistochastic matrices for free, avoiding the overhead of an additional decomposition algorithm as in existing works on fair ranking [START_REF] Singh | Fairness of exposure in rankings[END_REF][START_REF] Su | Optimizing Rankings for Recommendation in Matching Markets[END_REF][START_REF] Wang | User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets[END_REF].

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 𝐹 𝜆,𝒘 1 ,𝒘 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.

Experimental setup

Our experiments are implemented in Python 3.9 using PyTorch 5 . For the PAV algorithm, we use the implementation of Scikit-Learn. 64.1.1 Data and evaluation protocol. We present experiments on two recommendation tasks, following the protocols of [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF][START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF]. First, we address music recommendation with Lastfm-2k from Cantador et al. [START_REF] Cantador | 2nd Workshop on Information Heterogeneity and Fusion in Recommender Systems (HetRec 2011)[END_REF] which contains real listening counts of 2𝑘 users for 19𝑘 artists on the online music service Last.fm7 . 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 [START_REF] Harper | The movielens datasets: History and context[END_REF], 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 [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF][START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF][START_REF] Wang | User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets[END_REF]. For each dataset, a full user-item preference matrix (𝜇 𝑖,𝑗 ) 𝑖,𝑗 is obtained by standard matrix factorization algorithms8 from the incomplete interaction matrix, following the protocol of [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF]. Rankings are inferred from these estimated preferences. The exposure weights 𝒃 are the standard weights of the discounted cumulative gain (DCG) (also used in e.g., [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF][START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF][START_REF] Singh | Fairness of exposure in rankings[END_REF]

): ∀𝑘 ∈ [[𝐾]], 𝑏 𝑘 = 1 log 2 (1+𝑘) .
The generated 𝜇 𝑖 𝑗 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 𝜇 𝑖 𝑗 .

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 (3) 𝐹 𝜆,𝒘 1 ,𝒘 2 .

Task 1: Trade-offs between user utility and inequality between items. We use the two-sided GGF 𝐹 𝜆,𝒘 1 ,𝒘 2 instantiated as in Eq. ( 6), i.e., with 𝒘 1 = (1, . . . , 1) and

𝑤 2 𝑗 = 𝑚-𝑗+1
𝑚 . 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 𝜆 ∈ (0, 1). We remind though that unlike the standard Gini index, the GGF is un-normalized (see eq. ( 4), Sec 2.2).

We use three baselines for this task. First, since the Gini index is non-differentiable, [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] proposed a differentiable surrogate using the standard deviation (std) instead, which we refer to as eq. exposure:

𝐹 eq (𝑃) = 𝑛 ∑ 𝑖=1 𝑢 𝑖 (𝑃) - 𝜆 𝑚 𝑚 ∑ 𝑗=1 𝑣 𝑗 (𝑃) - 1 𝑚 𝑚 ∑ 𝑗 ′ =1 𝑣 𝑗 ′ (𝑃) 2
Second, Patro et al. [START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF] 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 [START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF]Fig. 1]), recalling that the standard Gini index is often defined as 1 -2𝐴 where 𝐴 is the area under the Lorenz curve [START_REF] Yitzhaki | More than a dozen alternative ways of spelling Gini[END_REF]. Their fairness constraints are slightly different though, as their algorithm FairRec9 guarantees envy-freeness for users, and a minimum exposure of 𝜆𝑛 ∥𝒃 ∥ 𝑚 for every item, where 𝜆 is the user-item tradeoff parameter.

Finally, we use the additive welfare function (8) (refered to as welf) with the recommended values 𝛼 1 ∈ {-2, 0, 1} and 𝛼 2 = 0 [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF], and varying 𝜆 ∈ (0, 1) as third baseline. We only report the result of 𝛼 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 𝑞 fraction of worst-off users, where 𝑞 ∈ {0.25, 0.5}, and inequality between items measured by the Gini index, as in [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF]. For this task, we instantiate the two-sided GGF 𝐹 𝜆,𝒘 1 ,𝒘 2 as follows: the GGF for users is given by Eq. ( 7) with parameters (𝑞, 𝜔) in {0.25, 0.5} × {0.25, 0.5, 1}, and the GGF for items uses the Gini index weights 𝑤 𝑗 = 𝑚-𝑗+1 𝑚 . We generate tradeoffs between user fairness and item fairness by varying 𝜆 ∈ (0, 1).

The baseline approach for this task is welf, the additive welfare function [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF], still with the recommended values 𝛼 1 ∈ {-2, 0, 1} and 𝛼 2 = 0 and varying 𝜆 ∈ (0, 1). We only report the results of 𝛼 1 = -2 as they obtained the best performances on this task.

Results

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 𝜆. Since Patro et al. [START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF]'s algorithm FairRec does not scale, we compare to FairRec only on Lastfm-2k.

We optimize 𝐹 𝜆,𝒘 1 ,𝒘 2 using FW-smoothing with 𝛽 0 = 100 and 𝑇 = 5𝑘 for Lastfm-2k, and 𝛽 0 = 1000 and 𝑇 = 50𝑘 for MovieLens. 𝐹 welf and 𝐹 eq are optimized with the Frank-Wolfe method of [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] for 𝑇 = 1𝑘 and 𝑇 = 5𝑘 iterations respectively for Lastfm-2k and MovieLens. This is the number of iterations recommended by [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF], while we need more interactions for FW-smoothing because its convergence is 𝑂 ( 1 √ 𝑇

) rather than 𝑂 ( 1 𝑇 ) 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 ×) on this task because eq. exposure reduces inequality between items by minimizing the std of exposures, while GGF with weights 𝑤 2 𝑗 = 𝑚-𝑗+1 𝑚 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 𝜔 is put on the 𝑞-% worst-off in GGF, the higher the curve, which is why we observe the ordering green □ ≺ red + ≺ purple ⋄ for GGF, on both 25% and 50% trade-offs plots. Second, as expected, welf is outperformed by our two-sided GGF with instantiation [START_REF] Michael | Minimizing separable convex functions subject to simple chain constraints[END_REF] and (𝑞, 𝜔) = (𝑞, 1) (purple ⋄), since it corresponds to the optimal settings for this task.

Figures 1(e),1(f),1(g) illustrates the same trade-offs on Movie-Lens. 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).

Convergence diagnostics

We now demonstrate the usefulness of FW-smoothing for optimizing GGF objectives, compared to simply using the Frank-Wolfe method of [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] with a subgradient of the GGF (FW-subgradient). We note that a subgradient of 𝑔 𝒘 (𝒙) is given by 𝒘 𝝈 -1 , where 𝜎 ∈ argsort(-𝒙). More precisely, FW-subgradient is also equivalent to using subgradients of -𝑔 𝒘 1 and -𝑔 𝒘 2 in Line 3 of Alg. 2, instead of ∇𝑓 𝛽 𝑡 (𝑃 (𝑡 ) ), ignoring the smoothing parameters 𝛽 𝑡 . FWsubgradient is simpler than FW-smoothing, but it is not guaranteed to converge [START_REF] Nesterov | Complexity bounds for primal-dual methods minimizing the model of objective function[END_REF]. The goal of this section is to assess whether the smoothing is necessary in practice.

We focus on the two-sided GGF (6) of Task 1 on Lastfm-2k and MovieLens, using FW-subgradient and FW-smoothing with different values of 𝛽 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 𝛽 0 . On MovieLens (Fig 1(h)), FW-subgradient converges to the optimal solution, but it is still slower than FW-smoothing with 𝛽 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 FWsubgradient since the computation cost is dominated by the sort operations in Alg. 2.

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 [START_REF] Palomares | Reciprocal Recommender Systems: Analysis of state-of-art literature, challenges and opportunities towards social recommendation[END_REF], 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, 𝑛 = 𝑚 and 𝜇 𝑖 𝑗 denotes the mutual preference value between 𝑖 and 𝑗 (e.g., the probability of a "match" between 𝑖 and 𝑗). Following [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF], we extend our previous framework to reciprocal recommendation by introducing the two-sided utility of a user 𝑖, which sums the utility 𝑢 𝑖 (𝑃) derived by 𝑖 from the recommendations it gets, and the utility 𝑣 𝑖 (𝑃) from being recommended to other users:

𝑢 𝑖 (𝑃) = 𝑢 𝑖 (𝑃) + 𝑣 𝑖 (𝑃) = ∑ 𝑖,𝑗 (
The choice of 𝒘 controls the degree of priority to the worse-off in the user population. We show in our experiments in Section 5.2 (a) Total user utility vs. inequality between items. GGF is instantiated as [START_REF] Beck | Smoothing and first order methods: A unified framework[END_REF].

(b) Utility of the 25% worse-off users vs. inequality between items. GGF is instantiated as [START_REF] Michael | Minimizing separable convex functions subject to simple chain constraints[END_REF] with parameters (𝑞, 𝜔).

(c) Utility of the 50% worse-off users vs. inequality between items. GGF is instantiated as [START_REF] Michael | Minimizing separable convex functions subject to simple chain constraints[END_REF] with parameters (𝑞, 𝜔).

(d) Optimization of GGF [START_REF] Beck | Smoothing and first order methods: A unified framework[END_REF] with 𝜆 = 0.5 (e) Total user utility vs. inequality between items. GGF is instantiated as [START_REF] Beck | Smoothing and first order methods: A unified framework[END_REF].

(f) Utility of the 25% worse-off users vs. inequality between items. GGF is instantiated as [START_REF] Michael | Minimizing separable convex functions subject to simple chain constraints[END_REF] with parameters (𝑞, 𝜔).

(g) Utility of the 50% worse-off users vs. inequality between items. GGF is instantiated as [START_REF] Michael | Minimizing separable convex functions subject to simple chain constraints[END_REF] with parameters (𝑞, 𝜔).

(h) Optimization of GGF ( 6) with 𝜆 = 0.5 that in reciprocal recommendation too, the GGF objective can be adequately parameterized to address existing fairness criteria.

𝐹 𝒘 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 C( w), and obtain 𝒚 = Π C ( w) 𝒖 (𝑃 (𝑡 -1) )

𝛽 𝑡 in Line 3 of Algorithm 2. Line 5 becomes μ𝑖 𝑗 = (1 -𝜆)𝑦 𝑖 𝜇 𝑖 𝑗 + 𝜆𝑦 𝑗 𝜇 𝑗𝑖 .

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. [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF].

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.

Data. We reproduce the experimental setting of [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] who also study fairness in reciprocal recommendation. We simulate a friend recommendation task from the Higgs Twitter dataset [START_REF] De | The anatomy of a scientific rumor[END_REF], 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 13𝑘 users. We estimate mutual scores 𝜇 𝑖 𝑗 (i.e., match probabilities) by matrix factorization.

(a) Total utility vs. inequality. GGF is instantiated as [START_REF] Burke | Multisided fairness for recommendation[END_REF] and we vary 𝜆.

(b) Total utility vs. utility of the 25% worseoff. GGF is instantiated as [START_REF] Michael | Minimizing separable convex functions subject to simple chain constraints[END_REF] with 𝑞 = 0.25 and varying 𝜔.

Fairness criteria.

Similarly to Section 4.1.2, we state two fairness tasks that previously appeared in the literature, we instantiate the GGF objective 𝐹 𝒘 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 [START_REF] Basu | A Framework for Fairness in Two-Sided Marketplaces[END_REF][START_REF] Jia | When Online Dating Meets Nash Social Welfare: Achieving Efficiency and Fairness[END_REF], 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 [START_REF] Bottou | Counterfactual reasoning and learning systems: The example of computational advertising[END_REF] with

𝑤 𝑖 = (1 -𝜆) + 𝜆 • 𝑛-𝑖+1
𝑛 , which yields a trade-off function between the sum of utilities and inequality of utilities, and we vary 𝜆 in (0, 1) to generate such trade-offs:

𝐹 𝒘 (𝑃) = (1 -𝜆) 𝑛 ∑ 𝑖=1 𝑢 𝑖 (𝑃) + 𝜆 𝑛 ∑ 𝑖=1 𝑛 -𝑖 + 1 𝑛 𝑢 ↑ 𝑖 (𝑃). (12)
We use two baselines for this task. First, similarly to eq. exposure, to bypass the nonsmoothness of the Gini index, [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] optimize a surrogate with std, named eq. utility:

𝐹 eq (𝑃) = 𝑛 ∑ 𝑖=1 𝑢 𝑖 (𝑃) - 𝜆 𝑛 𝑛 ∑ 𝑖=1 𝑢 𝑖 (𝑃) - 1 𝑛 𝑛 ∑ 𝑖 ′ =1 𝑢 𝑖 ′ (𝑃) 2 .
Second, the welfare function welf (8) of [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] is used in reciprocal recommendation as a single sum: 𝐹 welf (𝑃) = 𝑛 𝑖=1 𝜙 (𝑢 𝑖 (𝑃), 𝛼) where 𝜙 is defined in Sec. 2.3. We study welf as baseline by varying 𝛼, 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 [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] with welf is to trade-off between the total utility and the cumulative utility of the 𝑞 fraction of worse-off users. For this task, we instantiate the GGF with [START_REF] Michael | Minimizing separable convex functions subject to simple chain constraints[END_REF], with fixed quantile 𝑞 = 0.25 and we vary 𝜔 to generate trade-offs between total utility and cumulative utility of the 25% worst-off.

We compare it to the welf baseline where 𝛼 is varied as in [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF].

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 𝐹 𝒘 (𝑃) using FW-smoothing with 𝛽 0 = 10 for 𝑇 = 50𝑘 iterations, and optimize 𝐹 welf and 𝐹 eq using Frank-Wolfe for 𝑇 = 5𝑘 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 □) on Task 1, despite good performance of the baselines eq. utility (orange ×) and welf (blue •). 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 (7) (green □) is the most effective. This is because unlike the welf approach (blue •) of [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF] who address this fairness task, this form of GGF is exactly designed to optimize for utility quantiles.

RELATED WORK

Algorithmic fairness. Fairness in ranking and recommendation systems is an active area of research. Since recommender systems involve multiple stakeholders [START_REF] Abdollahpouri | Multistakeholder recommendation: Survey and research directions[END_REF][START_REF] Burke | Multisided fairness for recommendation[END_REF], 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 [START_REF] Michael D Ekstrand | All the cool kids, how do they fit in?: Popularity and demographic biases in recommender evaluation and effectiveness[END_REF][START_REF] Mehrotra | Auditing search engines for differential satisfaction across demographics[END_REF]. On the item side, authors aim to prevent winner-take-all effects [START_REF] Abdollahpouri | The unfairness of popularity bias in recommendation[END_REF] by redistributing exposure across groups of producers, either towards equal exposure, or equal ratios of exposure to relevance [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF][START_REF] Diaz | Evaluating stochastic rankings with expected exposure[END_REF][START_REF] Kletti | Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings[END_REF][START_REF] Singh | Fairness of exposure in rankings[END_REF], sometimes measured by the classical Gini index [START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF][START_REF] Wilkie | Best and fairest: An empirical analysis of retrieval system bias[END_REF]. Some authors consider fairness for both users and items, often by applying existing user or item criteria simultaneously to both sides, such as [START_REF] Basu | A Framework for Fairness in Two-Sided Marketplaces[END_REF][START_REF] Wang | User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets[END_REF][START_REF] Wu | TFROM: A Two-sided Fairness-Aware Recommendation Model for Both Customers and Providers[END_REF]. [START_REF] Do | Online certification of preference-based fairness for personalized recommender systems[END_REF][START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF] instead discuss two-sided fairness with envy-freeness as user-side criterion, while [START_REF] Deldjoo | A flexible framework for evaluating user and item fairness in recommender systems[END_REF] propose to use generalized cross entropy to measure unfairness among sensitive groups of users and items. [START_REF] Wu | Multi-FR: A Multi-Objective Optimization Method for Achieving Two-sided Fairness in E-commerce Recommendation[END_REF] 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. [START_REF] Mehrotra | Bandit based Optimization of Multiple Objectives on a Music Streaming Platform[END_REF] 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 [START_REF] Mehrotra | Bandit based Optimization of Multiple Objectives on a Music Streaming Platform[END_REF][START_REF] Wu | Multi-FR: A Multi-Objective Optimization Method for Achieving Two-sided Fairness in E-commerce Recommendation[END_REF], 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 [START_REF] Jia | When Online Dating Meets Nash Social Welfare: Achieving Efficiency and Fairness[END_REF][START_REF] Paraschakis | Matchmaking under fairness constraints: a speed dating case study[END_REF][START_REF] Xia | Reciprocal recommendation system for online dating[END_REF]. The closest to our work is the additive welfare approach of [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF], 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 [START_REF] Finocchiaro | Bridging Machine Learning and Mechanism Design towards Algorithmic Fairness[END_REF], using inequality indices to quantify and mitigate unfairness [START_REF] Heidari | Fairness behind a veil of ignorance: A welfare analysis for automated decision making[END_REF][START_REF] Lazovich | Measuring Disparate Outcomes of Content Recommendation Algorithms with Distributional Inequality Metrics[END_REF][START_REF] Speicher | A Unified Approach to Quantifying Algorithmic Unfairness: Measuring Individual &Group Unfairness via Inequality Indices[END_REF][START_REF] Wilkie | Retrievability and retrieval bias: A comparison of inequality measures[END_REF], taking an axiomatic perspective [START_REF] Cousins | An axiomatic theory of provably-fair welfare-centric machine learning[END_REF][START_REF] Gölz | Paradoxes in Fair Machine Learning[END_REF][START_REF] Williamson | Fairness risk measures[END_REF] or applying welfare economics principles [START_REF] Hu | Fair classification and social welfare[END_REF][START_REF] Rambachan | An economic approach to regulating algorithms[END_REF]. GGFs, in particular, were recently applied to fair multiagent reinforcement learning, with multiple reward functions [START_REF] Busa-Fekete | Multiobjective bandits: Optimizing the generalized Gini index[END_REF][START_REF] Siddique | Learning Fair Policies in Multi-Objective (Deep) Reinforcement Learning with Average and Discounted Rewards[END_REF][START_REF] Zimmer | Learning fair policies in decentralized cooperative multi-agent reinforcement learning[END_REF]. These works consider sequential decision-making problems without ranking, and their GGFs aggregate the objectives of a few agents (typically 𝑛 < 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 [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF][START_REF] Shamir | Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes[END_REF], and in particular variants of the Frank-Wolfe algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF][START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-free sparse convex optimization[END_REF] for nonsmooth problems [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF][START_REF] Sathya | A deterministic nonsmooth frank wolfe algorithm with coreset guarantees[END_REF][START_REF] Kiran K Thekumparampil | Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method[END_REF][START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF]. The recent algorithm of [START_REF] Kiran K Thekumparampil | Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method[END_REF] 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 [START_REF] Lan | The complexity of large-scale convex programming under a linear optimization oracle[END_REF], 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 [START_REF] Prescott | Ranking via sinkhorn propagation[END_REF][START_REF] Chapelle | Gradient descent optimization of smoothed information retrieval metrics[END_REF][START_REF] Taylor | Softrank: optimizing non-smooth rank metrics[END_REF], and recent growing interest in designing smooth ranking modules [START_REF] Blondel | Fast differentiable sorting and ranking[END_REF][START_REF] Cuturi | Differentiable Ranking and Sorting using Optimal Transport[END_REF][START_REF] Grover | Stochastic optimization of sorting networks via continuous relaxations[END_REF] for endto-end differentiation pipelines. The closest method to ours is the differentiable sorting operator of Blondel et al. [START_REF] Blondel | Fast differentiable sorting and ranking[END_REF], which also relies on isotonic regression. The differences between our approaches are explained in Remark 1.

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 [START_REF] Basu | A Framework for Fairness in Two-Sided Marketplaces[END_REF][START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF][START_REF] Singh | Fairness of exposure in rankings[END_REF][START_REF] Wu | TFROM: A Two-sided Fairness-Aware Recommendation Model for Both Customers and Providers[END_REF]. 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 [START_REF] Do | Twosided fairness in rankings via Lorenz dominance[END_REF].

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 [START_REF] Su | Optimizing Rankings for Recommendation in Matching Markets[END_REF], feedback loops in the learning process [START_REF] Bottou | Counterfactual reasoning and learning systems: The example of computational advertising[END_REF], and the changing nature of the users' and items' populations [START_REF] Morik | Controlling Fairness and Bias in Dynamic Learning-to-Rank[END_REF] and preferences [START_REF] Kalimeris | Preference Amplification in Recommender Systems[END_REF]. Addressing these limitations, in combination with our method, are interesting directions for future research.

Algorithm 1 :

 1 g., 71]. The parameter 𝛽 thus controls the trade-off between the smoothness and the quality of the approximation of ℎ. Computation of Π C ( w) input : GGF weights 𝒘 ∈ R 𝑛 , 𝒛 ∈ R 𝑛 output : Projection of 𝒛 onto the permutahedron C( w). 1 w ← -(𝑤 𝑛 , ..., 𝑤 1 ) and 𝜎 ← argsort(𝒛) 2 𝒙 ← PAV(𝑧 𝜎w) 3 𝒚 ← 𝒛 + 𝒙 𝝈 -1 4 Return 𝒚.

3. 2 . 2

 22 Efficient computation of the gradient. We now present an efficient procedure to compute the gradient of 𝑓 𝛽 (𝑃) := ℎ 𝛽 (𝒖 (𝑃)).Given an integer 𝑛 ∈ N, let [[𝑛]] := {1, . . . , 𝑛} and let 𝔖 𝑛 denotes the set of permutations of [[𝑛]]. For 𝒙 ∈ R 𝑛 , and 𝜎 ∈ 𝔖 𝑛 , let us denote by 𝒙 𝝈 = (𝑥 𝜎 (1) , ..., 𝑥 𝜎 (𝑛) ). Furthermore, let C(𝒙) denote the permutahedron induced by 𝒙, defined as the convex hull of all permutations of the vector 𝒙: C(𝒙) = conv{𝒙 𝝈 : 𝜎 ∈ 𝔖 𝑛 }. Finally, let Π X (𝒛) := argmin 𝒛 ′ ∈X ∥𝒛 -𝒛 ′ ∥ 2 . denote the projection onto a compact convex X. The following proposition formulates ∇𝑓 𝛽 as a projection onto a permutahedron: Proposition 3. Let w = -(𝑤 𝑛 , ..., 𝑤 1 ). Let 𝑃 ∈ P. Then for all (𝑖, 𝑗, 𝑘) ∈ [[𝑛]] × [[𝑚]] 2 , we have: 𝜕𝑓 𝛽 𝜕𝑃 𝑖 𝑗𝑘 (𝑃) = 𝑦 𝑖 𝜇 𝑖 𝑗 𝑏 𝑘 where 𝒚 = Π C ( w) 𝒖 (𝑃) 𝛽 .

  𝜇 𝑖 𝑗 + 𝜇 𝑗𝑖 )𝑃 ⊺ 𝑖 𝑗 𝒃 where 𝑢 𝑖 (𝑃) = 𝑛 ∑ 𝑖=1 𝜇 𝑖 𝑗 𝑃 ⊺ 𝑖 𝑗 𝒃 and 𝑣 𝑖 (𝑃) = 𝑛 ∑ 𝑗=1 𝜇 𝑖 𝑗 𝑃 ⊺ 𝑖 𝑗 𝒃 . Objective and optimization. The two-sided GGF objective (3) in reciprocal recommendation simply becomes one GGF of two-sided utilities, and it is specified by a single weighting vector 𝒘: max 𝑃 ∈ P {𝐹 𝒘 (𝑃) := 𝑔 𝒘 (𝒖 (𝑃))}.

Figure 1 :

 1 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 𝜆 ∈ [0, 1]. (Right column): Convergence of FW-subgradient compared to FW-smoothing, for various values of 𝛽 0 . FW-subgradient is not guaranteed to converge to an optimum.

Figure 2 :

 2 Figure 2: Fairness trade-offs achieved by competing methods on reciprocal recommendation on Twitter. They are generated by varying 𝜆 for eq. utility and GGF, and 𝛼 for welf.

  1 ∥𝒘 ∥ and 𝛽 𝑡 = FW-smoothing. Alg. 1 is used for 𝒚 1 and 𝒚 2 .

				𝛽 0 √ 𝑡	,
	FW-smoothing obtains the following convergence rate:
		𝑓 (𝑃 (𝑇 ) ) -𝑓 (𝑃 * ) ≤	2𝐷 P 𝑏 1 ∥𝒘 ∥ √	.
				𝑇
	Algorithm 2: (0) 𝑖	sorts 𝜇 𝑖 in decreasing order
	2 for t=1, . . . , T do
				𝛽 𝑡
	4	for i=1, . . . , n do
			(𝑡 ) 𝑖 represents σ𝑖
	9	𝑃 (𝑡 ) ← (1 -2 𝑡 +2 )𝑃 (𝑡 -1) + 2 𝑡 +2 𝑄 (𝑡 ) .
	10 end
	11 Return 𝑃

input : values (𝜇 𝑖 𝑗 ), # of iterations 𝑇 , smoothing seq. (𝛽 𝑡 ) 𝑡 output : ranking policy 𝑃 (𝑇 )

1 Initialize 𝑃 (0) such that 𝑃 3 Let 𝒚 1 = Π C ( w1 ) 𝒖 (𝑃 (𝑡 -1) ) 𝛽 𝑡 and 𝒚 2 = Π C ( w2 ) 𝒗 (𝑃 (𝑡 -1) ) 5 μ𝑖 𝑗 = (1 -𝜆) 𝑦

1 𝑖 𝜇 𝑖 𝑗 + 𝜆𝑦 2 𝑗 6 σ𝑖 ← top-𝐾 (-μ𝑖 ) // Update direction (10) 7 end 8

Let 𝑄 (𝑡 ) ∈ P such that 𝑄

Lorenz curves are normalized so that the last value is 1, while generalized Lorenz curves are not normalized.

http://pytorch.org

https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/isotonic.py

https://www.last.fm/

Using the Python library Implicit: https://github.com/benfred/implicit (MIT License).

[START_REF] Gourab K Patro | FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms[END_REF] 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.

ACKNOWLEDGMENTS

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