User-item fairness tradeoffs in recommendations
Authors: Sophie Greenwood
Sudalakshmee Chiniah
Nikhil Garg
Venue: NeurIPS 2024 poster (2024)
Keywords: recommendation systems
algorithmic fairness
Primary area: fairness
TL;DR: We explore the effect of population heterogeneity and preference mis-estimation on the tradeoff between user fairness and item fairness in recommendation systems in a theoretical model and in real data.

Abstract: In the basic recommendation paradigm, the most (predicted) relevant item is recommended to each user. This may result in some items receiving lower exposure than they "should"; to counter this, several algorithmic approaches have been developed to ensure *item fairness*. These approaches necessarily degrade recommendations for some users to improve outcomes for items, leading to *user fairness* concerns. In turn, a recent line of work has focused on developing algorithms for multi-sided fairness, to jointly optimize user fairness, item fairness, and overall recommendation quality. This induces the question: *what is the tradeoff between these objectives, and what are the characteristics of (multi-objective) optimal solutions?* Theoretically, we develop a model of recommendations with user and item fairness objectives and characterize the solutions of fairness-constrained optimization. We identify two phenomena: (a) when user preferences are diverse, there is "free" item and user fairness; and (b) users whose preferences are misestimated can be *especially* disadvantaged by item fairness constraints. Empirically, we prototype a recommendation system for preprints on arXiv and implement our framework, measuring the phenomena in practice and showing how these phenomena inform the *design* of markets with recommendation systems-intermediated matching.

User-item fairness tradeoffs in recommendations
Sophie Greenwood Computer Science Cornell Tech
Sudalakshmee Chiniah
Operations Research and Information Engineering Cornell Tech
Nikhil Garg
Operations Research and Information Engineering
Cornell Tech
Abstract
In the basic recommendation paradigm, the most (predicted) relevant item is recom- mended to each user. This may result some items receiving lower exposure than they "should"; to counter this, several algorithmic approaches have been developed to ensure item fairness. These approaches necessarily degrade recommendations for some users to improve outcomes for items, leading to user fairness concerns. turn, a recent line of work has focused on developing algorithms for multi-sided fairness, to jointly optimize user fairness, item fairness, and overall recommen- dation quality. This induces the question: what is the tradeoff between these objectives, and what are the characteristics
objlti-objective optimal solutions? Theoretically, we develop a model recommendations with user and item fairness objectives and characterize the solutions of cooeeesssoonsraineed optimization. We identify two phenomena: (a) when user preferences are diverse, there is "free" item and user fairness; and (b) users whose preferences misestimated can be especially disadvantaged by item fairness constraints. Empirically, we prototype recommendation system for preprints arXiv and implement our framework, measuring the phenomena in practice and showing how these phenomena inform the design of markets with recommendation systems- inteen--ittrmmditted matching.
Introduction
Recommendation systems are employed throughout modern online platforms suggest items (media, songs, books, products, or jobs) to users (viewers, listeners, readers, consumers, or job seekers). The platform learns user preferences and shows each user personalized recommendations, One recommendation paradigm is to simply show the user the items they most prefer. However, this approach may result disparately poor outcomes for some items, which may not be most preferred by any user [44]. For example, in our empirical application in prototyping a recommender system for arXiv prepints, we find that on average more than 47% of papers have less than a 0.0001 % probability of being recommended to any user, even when the number of users and items are the same. Thus, many algorithmic techniques have been proposed to improve item fairness in recommendation [3, 35, 48, 50]. However, by not solely optimizing for engagement, these techniques impose cost both to overall recommendation quality [3] and especially for some individual users more than others.
Accordingly, algorithms have recently been introduced to address the problem of two-sided fairness (or multi-sided fairness), in which the platform aims to balance user fairness, item fairness, and overall recommendation quality [11, 12, 47]. These algorithms formalize the desired balance in terms of an optimization problem for example, maximizing the difference between overall recommendation quality and unfairness penalties [11], or the overall recommendation quality subject to fairness
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

constraints [12]. The relative importance of user and item fairness is described by the relative strength of the respective unfairness penalties or slack in the faimess constraints.
However, an open question is, what are the implications of such algorithms on the recommendations, Le., what do multi-sided constraints do, and what is the price of (malti--ided) fairness? More specifically, are there settings in which we can simultaneously maximize all objectives, "for free?," as opposed to there being large tradeoffs as commonly emphasized? Are some users or items -for example, those new to the platform more affected than others? How do the answers to the above questions depend on the context and. in real-world settings, do "fairess" " constraints substantially affect recommendation characteristics? Such real-world considerations are essential for platform designers to understand. In fact, a recent survey and critique of the fair ranking literature advocated for such grounded analyses to understand algorithmic implications and tradeoffs [40], as opposed to black-box deployment of fairness algorithms.
Answering such questions is challenging. Theoretically, multi-sided fairness is cast as an optimization problem, and conceptually characterizing optimization solutions is often intractable. For example, given an arbitrary utility matrix and a constraint on the exposure provided to each item, it is not tractable to calculate recommendations closed form: the solution depends on global structure, users may not receive their most preferred items, and items may not be recommended to the users who most prefer them. Then, once phenomena are theoretically identified, empirically verifying phenomena requires specifying recommendation setting and measuring user-item utilities as a function of their characteristics. Given these challenges, our contributions are as follows.
Theoretical framework to characterize solutions of multi-sided fair recommendations. We formulate a concave optimization problem in which user faimesss is formalized as an objective on the minimum normalized utility provided to each user and item fairness constraints determine the problem's 's feasible region, through the solutions of another concave optimization. This formulation qualitatively captures standard multi-objective approaches for user-item fairness [S, 12]. We show that when item fairness constraints are maximal, the solutions to this optimization problem (recom- mendation probabilities for each user) have sparse structure that can be characterized as a function of the problem inputs (e.g., estimated utilities for each user-item pair, or slack given in the item fairness constraint).
Conceptual insights on the price of fairness. We use our theoretical framework characterize user-item fairness tradeoffs. We identify two phenomena: (a) "free fairness" as a function of user preference diversity: users have sufficiently diverse preferences, imposing item fairnsss constraints can have large benefits to individual items with little cost to users, i.e., there is a small price of fairness. (b) "Reinforced disparate effects" due to preference uncertainty. Of course, users for whom the platform has poor preference estimation (e.g.. "cold start" users whom the platform has no data) typically receive more inaccurate recommendations: we show that this effect may be worsened with item fairness constraints, in worst case sense: when a user's preferences are uncertain, item-fair recommendation algorithms will recommend them the globally least preferred items even when attempting maximize the minimum user utility.
Empirical measurement. Finally, we use real data to prototype a recommendation engine for new arXiv preprints and use this system to measure the above phenomena in practice. For example, we find that more homogeneous groups of users have steeper user-item fairness tradeoffs - as theoretically predicted, diverse user preferences decrease the price of item fairness. Furthermore, we find that the "price of misestimation" is high (users for whom less training data is available receive poor recommendations), but average item fairness constraints do not increase this cost.
Putting things together, we show that the real-world effects of user-item recommendation fairness constraints heavily depend on the empirical context. In some cases, "item faimess"" comes for free, with little cost to users. In others, deploying such an algorithm may lead to especially poor recommendations for some users, in ways that cannot be mechanically addressed by adding user fairness terms. We urge designers of fair recommendation systems in practice to develop such evaluations to measure such individual-level effects, and for researchers to further characterize the potential implications of such algorithms. Our code available at the following repository: https:/ // /gg github. cww www.wwchwniaa////oocccoococccaat AArviv att.r//aaaaaraiiaeeeeeeeettttttt Recommendation.Resse..

---

2
Formal Model
Our setup is characterized by user and item (estimated) utilities, recommendation optimization with user and item fairness desiderata, and evaluation of the effects of such desiderata. (As discussed below, some of these modeling choices are made for concreteness, and our results extend beyond these specific choices).
Users, items, and utilities. There is a finite population of m users and items. Let wa > 0 be the utility recommending item user i; this could represent click-through rate purchase probability. We suppose that user-item utilities are symmetric: each of the user and item receives utility Wiy from being recommended item
Let An-1 denote the simplex in R". The platform's 's task is to choose a recommendation policy P - For each user i, the platform will recommend one item user i selected randomly according to the distribution P:- Given a recommendation policy p. user i's expected utility from using the platform is En Pij item j's expected utility is E; PijWij. where Σ, Pij for each user
Fairness desiderata. We suppose that the platform uses as benchmark, for each user or item, ignored the utilities of others. Thus, given
the best thing that it could do for that agent recommendation policy let Up(p, w) be user i's utility from normalized by the utility max, wy they would receive from being recommended their best match. Let (p, w) be item j utility from normalized by the utility receives if it is recommended to every user, E, Wij. The normalized utilities are:
Ejpisus max, Wij"
w) Eipis Σ, Wiy
U.(p, w)
The normalizations capture that recommendations should not be affected by scaling utilities, or be distorted by a user who is not satisfied with any item an item that is generally undesirable to users.
Given recommendation policy p. user fairness is quantified as the minimum normalized user utility Unin (p. w) = min, Up, w), and item faireess analogously as minn (p. w) min, I5 (p, w).
Multi-objective recommendation optimization. We suppose that the platform seeks to satisfy its fairness desiderata follows. At the extremes, the platform could choose maximally fair solution for one side, ignoring the other. Denote the optimal user fair utility as U (w) == maxp Umin (p. w) (achieved by giving each user their favorite item deterninistically), and the optimal item fair utility as Iiin (w) := max, min (p, w).
Finally, we cast the two-sided fair optimization - for the optimal 7-constrained user fair solution as
U (7, w) = max Unia (p, w)
subject to Imin (p. w) 2 7 Tmmn (w).
i... we maximize the minimum normalized user utility, subject to the minimum normalized item utility being at least fraction of the optimal item fair solution.
Research questions: price of fairness and misestimation. We can now define the price item P faimess user faimess TZ ("price of fairness") as the decrease in user faimess with maximal item fairness constraints:
T (w) = Uniu (w) Unnn (y L, w)
U (w)
We ask how Th changes with the utility matrix We note that while this question (in terms of solutions to Problem (1)) can be simply stated, detail in Section 3, finding a closed form expression for U (1, w) the optimal minimum normalized user utility given item fairness constraints in terms of is theoretically challenging.
Similarly, we investigate the price of misestimation. Let viy denote the platform's 's estimate of the utility of recommending i to j; let p(ry) be policy that solves the optimization problem above with
3

---

misestimated utilities, that is, P(7) attains U min (7,20) i)). on user utility ("price of misestimation") m8 as
Then we define the price of misestimation
Tff (7/ w. w) min (7, w) U min (p(7), w))
Uni (7, w)
that is, the decrease in true user fairness due to optimizing with estimated utilities. In particular, in Section we will examine whether item fairness exacerbates the price of misestimation by comparing TU M (0, w, u)) and T (1, w. i)), particularly in the case of cold start users.
Discussion. We note several modeling choices. First, we assume that utility wij is shared both the item j and user benefit equally from successful recommendation. This choice captures, e.g., purchase or click-through rates. It also helps us isolate effects due to fairness constraints and effects across items and users, as opposed to misaligned utilities. We expect the price of fairness to increase and potentially be arbitrarily high with such misaligned utilities. We further justify and relax the shared utility assumption in Appendix A. Second, we quantify fairness through the minimum normalized utility. Normalization is standard in related algorithmic work, such as [47], and avoids solutions in which an item that provides utility to every user needs to be recommended every user to equalize utilities. We use individual egalitarian fairness (minimum utility over individuals) instead of group fairmess capture settings in which group identity is not available, and systems in which individual-leved disparities may be widespread: egalitarian fairness widespread in algorithmic fairness [2. 17, 43, 45]. In Appendix A show that empirical findings extend to other measures of individual fairness. Finally, in the user-item fairness tradeoff problem (Problem 1) we used an item fairness constraint rather than adding item fairness term to the objective; these approaches can be thought of conceptually as dual to one another, and so we expect similar properties to hold in either formulation.
3 Theoretical framework
To determine how the price of fairness Tei depends on utility matrix w, we need to compute Unin (1,w) w) and Uiin (w). It turns out that U (w) is easy to describe: without item fairness constraints, the optimal recommendation policy deterministically recommends each user their most preferred item. Each user attains the maximum possible normalized utility of 1, and Unin (w) 1.
However, with an item fairness constraint, we can no longer select each user's recommendation policies independently. Thus characterizing Unin (1, w) is much more complicated. Recall that Unin (1, w) is the minimum normalized user utility of the optimal user-fair recommendation subject to maximal item fairness constraints. Plugging into Problem (I) and expanding the definitions, we have
Eg WipPi max, Wij
Unin (1, = max OE Am R-1
min
Σ, U E, wij
subject to P arg max min DEAT
Thus we need to find closed-form solutions in terms of the utilities w to a non-linear concave program, in which both the objective and the constraint depend on w, and indeed even determining the constraint requires solving another non-linear concave program.
In Proposition 1, we develop framework solve this problem, which we later apply show our main results Theorems and 4.
Proposition Suppose that for a set of recommendation policies S A
(i) S can be described by finite set of linear constraints
(i) There exists optimal solution p² to Problem (2) such that p² E S
(iii) p² is the unique feasible solution to Problem (2) in S
Multiple policies P may optimize U (r,, w). and different policies may have different values of Unia (p, w). In our experimental results, the policy e found the convex optimization solver.

---

Then, finding an optimal solution p" to Problem (2) can be reduced to solving a linear program L.
With Proposition 1, the key technical challenges become: (a) given utility matrix w, finding S satisfying the above conditions; (b) given and w, finding a closed-form expression for p²; (c) given a closed form for p* in terms of w, reasoning about the properties of item fair solution U (1, w).
To do this, for our main results, we construct S as a set of recommendations with a particular symmetricc structure. Suppose users come in K types, where a user of type l shares a utility vector. Then, consider Symm {p: P. = Py if w wy } C A the set of policies where users of the same type are given the same recommendation probabilities. Note that, in the extreme case, each user their own type. Furthermore, let Pk: denote the recommendation policy for type k for p E Ssymm- Proposition 2. Skymm satisfies conditions (i) and (ū) in Proposition 1. Furthermore, solutions p E Soymn Problem (2) have sparse structure:
If p is a basic feasible solution to the linear program in Proposition 1, then there are at most n + K - 1 type- item pairs (k, such that pkj >> O (out of nK possible pairs).
If is also optimal, then there are at most K - items that are ever recommended to more than one type of user, ie., where Pkjs parj for ks + K.
For our main results, will leverage the sparsity structure in Proposition restrictions on utility matrix w, that Symm also satisfies (jii). We will then derive closed-form expressions for that solution, and show how changes as function of w.
show, with further
The sparsity structure in Proposition constraints, solutions will be highly sparse: each user will be recommended their most preferred item deterministically; each other item will have a recommendation probability of zero. Once we add item fairness constraints, solutions do not necessarily remain sparse. However, Proposition 2 shows that sparse solutions still arise under item fairess constraints in settings with symmetric solutions.
also interesting in its own right. Without item fairness
User preference diversity and fairness tradeoffs
We now use the theoretical framework developed in the above section to understand the effect of the structure of user utilities on the price of fairness. particular, we identify "free fairness," i..., the price of fairness is low, when preferences are sufficiently diverse.
Example 1. For intuition as why user diversity affects the price of fairness, consider the following example. Suppose we have n = 2 items and m users; half the users have utility e for the first item and - e for the second item, and the other half has utility Then, the recommender can simply give each user their favorite item (the user optimal solution), and this solution simultaneously maximizes user and item fairness well as total user and item utility.
for the first item and e for the second.
On the other hand, suppose all users have the same preferences: each user has utility 1 1-6 c for the first item and utility for the second item, for > 0 that is small. Then, any recommendation probability given to the second item comes at a cost to users who receive that item instead of the first item; however, (normalized) item fairness would require that the second item receives as much utility as the first item. Below, we show that this results in a tradeoff even between linear normalized user and item utilities, where we account for the fact that the second item on average less preferred by users.
Since all users have the same preferences for items, using Proposition it is sufficient to consider them receiving the same recommendation probabilities #I for the first item and p2 1 P1 for the second. Bounding minimum item utility min by the utility of the second item, we have
Imin < (2(p) P.
P2 A 1-10 PI.
me For given recommendation probability Pl, the minimum normalized user utility is
Umin = (1 - e)pp + Epp = 22 S p te.
Rearranging, we get that
Unin - < S p: 1 Jmin =
Unin + min S1+6.
Thus the minimum normalized user utility and the minimum normalized item utility essentially follow a negative linear relationship- -garantteiigggggg the second item even 6 as much utility as the first item results in linear cost to users.
5

---

We now formalize and generalize this example, when the level of heterogeneity in the population can be captured by a single parameter. Consider the following utility matrix structure. Let v1 > 12 Un > 0. Suppose that there are two user types: a user either has utility wij 0; or Wkj = Un- and say that user i is of type or 2 respectively. preferences, but the preferences can otherwise be generic and be for any number of items. Now, the direct solution by symmetry for the example no longer directly holds the items in the middle, not necessarily preferred by either user type, may be binding in terms of item fairesss constraints.
words, the two types have opposite
Let a be the proportion of type users in the population, out of a fixed population of m users. Parameter thus controls the population heterogeneity; if a is near 0 or 1, the population is highly homogeneous, dominated by users of the same type. If = }. the population split evenly between the two types and is highly heterogeneous. Since we parametrize w by a, we may write the price of fairness as.
(a)r(a)= == Uni (a) Uii (7 = 1, a)
-
U (a)
Given this structure, Theorem 3 states that the price of fairness F (a) increases in the homogeneity of the users heterogeneous user populations are less affected by incorporating item faimess constraints.
Theorem 3. TEir(a) (a) is decreasing in foror 0 < S 1/2, and increasing in a oor 1/2 S a < 1.
Proof sketch for Theorem 3. We show that when in population with two opposing types as described above, the sparsity condition in Proposition 2 yields unique solution, for which we can find a closed form and express in terms of a. We then evaluate Umin (p. a) at this solution to find U (1, a). and show that this is indeed increasing. The full proof is Appendix D.
5 Uncertainty and fairness tradeoffs
A basic fact often ignored in fair recommendation - is that recommendations are made with (mis)estimated utilities. Platforms do not have full knowledge of user preferences, especially those new to the platform. Of course, recommendations under misestimated utilities may be poor; here, we show that adding item fairness constraints may worsen the cost of this misestimation even further.
Intuitively - for a new user for whom the platform has no data the platform would estimate the user's preferences the average of preferences of existing users (c.g.. in Bayesian fashion). Thus, without item fairness considerations, it would show the user generally popular items. However, the new user's preferences are generally estimated as "weaker" than the preferences of others for any given item (since it averages preferences of users who may either like or dislike any given item). Thus, with fairness constraints, the optimization is incentivized to show the user otherwise unpopular items, since all the user's estimated preferences are weaker. Liu and Burke [31] for example develop an algorithm for item fairness where users with weaker preferences are explicitly leveraged in this way.
For given item fairness level y. true utility matrix w, and estimated utility matrix ú. let p():) be a recommendation policy that solves the recommendation problem (Problem 1) with respect to the misestimated utilities, that is, f solves min (7, t)). Recall that we define the price of misestimation
U min (7, w) Unin (p(7), w)
M To (7, w. ④
U (7,w)
which represents the relative decrease in minimum normalized user utility as a result of misestimation. Item fairness worsens the price of misestimation if T (7 = w, () > T (7 = 0, w, t))
We now formalize the above argument, building the analysis in the previous section. As in Section 4, suppose that there are 2 types of users, with opposing preferences (i.c., with values v1, u2..., Un and Un, Ux-1. ... U1. respectively) and the platform has correctly estimated these preferences. However, now, these two types only make up a proportion 3 of the population each.
Now, we suppose that there is a fraction 1 8 3 of the user population who are "new" users. We assume that these users are drawn from the same distribution as the remaining users, but the platform does not know their preferences. It thus constructs prior by averaging over the known users' preferences (mis (sttmmatgg the users' utility for each item 2n-141

---

Theorem 4. If > and w and i are as described above, then faimess constraints can arbitrarity worsen the price of misestimation.
The price of misestimation without faimess constraints is low: for all {uz}. there is recommendation policy p that solves the misestimated problem Unin (0, ú) so that
Tt (0, w, i)
The price of misestimation with fairness constraints can be arbitrarily large: Ye, there exists AzyJ and recommendation policy P that solves the problem Unin (1, ()) such that
TU (1, w. ú 1.
Proof sketch. The main task is to find the price of misestimation with fairness constraints, which re- quires computing Unin (1,w) when users' values are correctly estimated, and computing U (1, w) when users' values are incorrectly estimated. To find Min (1,w), note that w a population with two opposing types of users, so may leverage the insights of Theorem 3. To find Unin (1, i) we again use the framework in Section 3, showing that the setting of this theorem, we can find an optimal policy p² for U (1, ()) in a set S' S Symm of policies with an additional colunn-symmelry property. We use an analogue of the sparsity result in Proposition 2 to show that there is a unique feasible solution á E S' and obtain closed form expression for p", and find upper bound for Unin (p, à) = min (1, ú)). In fact, we show that as long as > 1 will never be recommended their most preferred items. The full proof is in Appendix E.
u. under ý the mis- estimattdd users
The idea follows the above intuition: without item fairesss constraints and assuming cold start users follow the same distribution as existing users, the platform's 's price of misestimation low because the platform treats cold start users the average of the existing population. Faimess constraints, however, can make this cost arbitrarily high, as in expectation cold start users relatively enjoy items other users do not. Such effects suggest that more careful treatment of uncertainty and fairness together is necessary for recommendation algorithms.
6 Empirical findings: Xiv recommendation engine
We prototype a recommender for preprints on arXiv, to illustrate our conceptual findings. We consider the cold start setting for items (papers), when they are newly uploaded to arXiv and only have metadata and paper text but no associated interaction or citation data. For users (readers), we use as data the papers that they have shared on arXiv estimate their preferences.
Empirical setup. We use data from arXiv and Semantic Scholar [1, 25]. As training for user preferences, we consider 139,308 CS papers by 178,260 distinct authors before 2020; as the items to be recommended, we consider the 14,307 papers uploaded to arXiv in 2020. We apply two natural language processing-
models TF-IDF [28] and the sentence transformer model SPECTER [13]-to to textual features such as the paper's 's abstract (for both items and the user's ' historical papers) to generate embeddings for all papers in the training set. We use these embeddings to compute similarity scores (utility matrices) for users and items. To compute the similarity score (utility) between user (an author of at least one paper before 2020) and an item (a paper uploaded in 2020), we compute the cosine similarity between the embedding of each of the user's pre-2020 papers and the item's s embedding. We then use either the mean or the max similarity amongst the pre-2020 papers and the item; the max similarity score may more effectively capture a user's diverse interests [20, 41]. We then generate recommendations for each user, at various levels of user and item fairness constraints.
To validate our recommendation approach, we use citation data from Semantic Scholar [25] to determine for each user and each paper published in 2020 whether the user cites that paper in their post-2020 work. We then examine how well the user-item similarity score generated by our recommendation engine predicts the presence of citation. The recommendations effectively predict whether a user cites a paper with high score after 2020. In Table I we show the results of logistic regression between each similarity score and the presence of a citation, where the coefficient on the score is large and statistically significant for each model; the predictive power of our models is
7

---

Model Max score, TF-IDF
Coefficient
Std. Err
z-value
Adjusted R²²
12.4100
0.058
212.178
0.08915
Mean score, TF-IDF
20.2122
0.131
154.835
0.04616
Max score, Sentence transformer
18.4557
0.250
73.695
0.1347
Mean score, Sentence transformer
16.2482
0.246
66.144 148
0.09085
Table I:
Logistic regression results for predicting whether user i cites paper j from the similarity score Wij for each model.
1.0
Mis essemattiion
1.0
True estimation
0.9
0.8
User fairness
0.8
User fairness
0.6
0.7
0.4
0.6
0.5
Random users
0.2
Homogeneous users
0.0
0.2
0.4
0.6
2.0
0.0
0.0
0.2
0.4
0.6
1.0
Item fairness constraint strength, y
Item faimess constraint strength, y
(a) Homogeneous versus diverse users
(b) With and without misestimation
Figure I: Empirical (using our arXiv recommender) tradeoff between the minimum user (Y axis) and item (X axis) utility. Recall y is the fraction of the best possible minimum normalized item utility Iijn guaranteed. (a) Illustrating Theorem 3 empirically homogeneous populations have higher price of fairness. Empirically, however, the price of fairness is small except with strict item fairness constraints y 1. (b) For set of users, holding other users fixed, the cost to the worst-off user of misestimating preferences, at varying yy Empirically, the cost of misestimation is already so high that it is not worsened with item fairees constraints, in the worst case analysis of Theorem 4.
reasonable for sparse, high variance event such as citations. We generally find that the max score models are more predictive of future citations. Appendix B includes details and evaluations; our computational experiments in the main text use the max score, TF-IDF model.
6.1 Empirical results.
We examine the tradeoffs between item and user fairness and the effect of misestimation on this tradeoff empirically. We use the similarity scores generated by the recommendation engine described above - in particular, the max score, TF-IDF model as the utility values Wiy- We consider a pool of 14,307 papers in the computer science category posted to arXiv in 2020, and pool of 20,512 authors who posted papers in the computer science category to arXiv both in 2020 and prior to 2020 (we use the papers prior 2020 compute the similarity scores as described above). We then subsample recommendation settings from this pool; we give further details about the sampling process below. For a given value of y, to compute U (7) we use the cvxpy implementation of the convex optimization algorithm SCS [38].
User-item tradeoff's as function of user diversity. Figure 3a shows the tradeoff between user faimees and item fairness in random population and in population of homogeneous users. To generate tradeoff curve for the heterogeneous population, we sampled 200 random papers and 500 random authors to form w, and computed U (7. w) for 50 values of y between 0 and 1. To generate tradeoff curves from homogeneous user populations, we clustered all 20,5 users into 10 clusters using the k-means algorithm. For single curve, to form we sampled 200 random papers and 500 random authors from one random cluster. We run 10 experiments and plot the mean of U min (7, w) at each value of across the 10 curves well as two std. error bars for the mean.
8

---

Figure 3a demonstrates that in real data, for moderate item faimess guarantees (0 < Y S 0.9), on average there a fairly low cost to user fairness, but as we approach optimal item fairness (? + 1), the tradeoff becomes steep. Furthermore, Figure 3a shows that item fairness tends to impose a higher cost to user fairness in more homogeneous populations, as Theorem 3.
Price of misestimation. Figure 3b shows how user fairess is affected by item faimess guarantees in the presence of misestimation. For sets of 200 random papers and 500 random authors, we select a set 10% of these users at random and treat them if we did not have any data for them, estimating these users' utility for item j as the average utility for item j for the other 90% of the users (w in the notation of Theorem 4). For 50 values of 7 between O and 1, we compute misestimated utility matrix. We also compute, counterfactually. this quantity if the utility matrix had been correctly estimated, Uninn w.). We plot the true minimum normalized user utility under the recommendation policies that attain Umin (1, w) and Uni (1, w). We run 10 experiments and plot the mean value of the minimum normalized user utility and two std. error bars.
U min (1, t0) for the
In Figure 3b, near 7 = O, the price of misestimation - the gap between the two curves - is higher than the cost of misestimation near y 1. This results because the item fairness constraint barely changes the (already low) utility of these users when their preferences are misestimated, but substantially changes their utility when their preferences are correctly estimated. While theoretically, item fairness constraints can arbitrarily increase the cost of misestimation, in practice, on average they do not affect this cost the cost of misestimation without item fairness is already high.
Related work
There is large literature (item) fair recommendation and ranking [3, 35, 48, 50, 51] and, more recently, on multi-sided user-item fair recommendation [5, 10-12, 16, 39, 47]. This literature is primarily algorithmic: for given formulation of user and item utility (and other desiderata), how do we devise an efficient algorithm for multiple objectives or constraints? In contrast, our goal is primarily conceptual, to aid algorithm designers in choosing when to use such algorithms: for example, by explaining when we might expect the tradeoff to be especially sharp. and to understand the cost to cold start users in particular, For example, we theoretically analyze recommendations from a constrained optimization- based approach akin to that in Basu et al. [5], in terms of the implications of such an approach on recommendations.
Several papers observe related phenomena to the ones we study, especially empirically. Wang and Joachims [47] develop optimization algorithm to be fair to users (in terms of group faimess to demographic groups) and items (similar to our normalized utility metric). Theoretically. they show that there is a tradeoff between user and item utility metrics, and further empirically show how faimess interacts with the diversity of items shown to each user. While their focus is also primarily algorithmic, they do show that there is a fundamental tension between item and user fairness. In concurrent work, Kleinberg and Meister [26] also theoretically demonstrate and characterize this tension. They focus on the cost to individual users caused by imposing maximal item fairness constraints similar to how we define price of fairness and determine the relationship between a cost level and the proportion of users in the worst-case recommendation setting who experience that cost. In constrast, we examine the cost to the single worst-off user as function of properties of the recommendation setting such as user diversity and recommender mis- miiimattittiin. Rahmani et al. [42] demonstrate a similar tension between item and user fairness in empirical data. Liu and Burke [31] do not examine user fairness, but observe that one can mitigate the cost of item fairness in multi-sided recommendations by recommending to users with weaker preferences for items that may otherwise be less preferred. Subsequently, Farastu et al. [16] examine which users bear the cost of item fairness, pointing to Liu and Burke [31] to argue that the cost to users of item fairness constraints disproportionately falls on users with flexible preferences, creating an incentive for users to misrepresent their preferences more rigid than reality. We build on these arguments by theoretically analyzing the cost of item fairness on (individual) users, especially the users most affected, function of the estimated user preference matrix.
In focusing on conceptual phenomena, our work is related to work analyzing the price of fairness and efficiency-equity tradeoffs in various settings beyond recommendations. Bertsimas et al. [8] first defined the price of fairness as the normalized decrease in the utility of an algorithmic outcome after adding fairness considerations, and develop general bounds on the price of faimess in array of

---

optimization scenarios. This concept has been subsequently applied in a variety of domains, including auction theory [24]. fair division and resource allocation [6. 32. 46], and computer networking [49]. Barre et al. [3] apply a similar concept in assortment optimization, examining the cost of item visibility constraints on the revenue of platform. Most similarly, Chen et al. [12] define the price of fairness in the setting of multi-sided fairness as the cost on platform revenue of including both fairness constraints; in contrast we define the price of fairness as the cost to user fairness of imposing item fairness constraints in order to capture the interplay between user and item fairness. The authors then show that this price of fairness on the revenue depends on objective misalignment - the difference in fairness between the item/user utilityy required by the constraints, and the item/user utility in revenue- optimal solution. We study how the price of item fairnsss on user faimess depends on user preference diversity- the agreement between users' utilities. These concepts are related: user preference diversity may cause objective alignment. Moreover, they also consider the problem of unknown preferences: they examine how to algorithmically impose fairmess constraints when preferences unknown, while we address the question of whether fairness constraints disproportionately harm users with unknown preferences. Finally, our result that diverse population preferences can mitigate the price of fairness resembles the result of Bastani et al. [4] that greedy contextual bandits can perform well without exploration if there is sufficient contextual diversity.
Finally, there is a large literature on other tradeoffs in recommendations, rankings, and ratings: engagement versus value, diversity, strategic behavior, uncertainty, and over-time dynamics [9, 14, 15, 18-23, 27, 29, 30, 33, 34, 36, 41]. In the context of set recommendations when users consume their favorite item out of the multiple recommended. e.g., Peng et al. [41] show that there is minimal uiility-diversity tradeoff, and Besbes et al. [9] show that there is a minimal exploration-exploiaatoon tradeoff.
Discussion
We investigate the relationship between user fairness and item faimesss in recommendation settings. We develop (a) a theoretical framework to enable us to solve for the price of fairness for many population settings, and (b) recommendation engine using real data to allow to investigate user-item fairness tradeoff's in practice. Our work informs the design of fair recommendation systems: (1) it emphasizes the benefits of diverse user population, and suggests that item fairness constraints should not be imposed on sub-markets (sub-groups), but instead on the entire population together. (2) It cautions designers to be especially mindful of effects on individual users (especially cold start users), who may receive disproportionately poor recommendations with item fairness constraints, even with a user fairness objective. Our empirical analysis supports our theoretical analysis- the userbase diversity affects the severity of user-side effects of imposing item faimess; however, the price of misestimating user utility already high without item fairness constraints, and so imposing such constraints does not have additional effects. Such results speak to the importance of instance analyses, ef. [40]: one cannot make general statements about the specific effects of constraints on users (or vice versa) outside of specific context, though we identify two relevant phenomena (user diversity and misestimation) that modulate these effects.
Limitations. Our theoretical analysis explores these fairness tradeoffss in fairly restricted setting. First, we assume that users are only recommended a single item; future work should investigate how the price of faimess changes as the number of recommended items increases. We do not expect our theoretical framework to easily extend to other definitions of fairness; however, we extend our computational arXiv experiments to other definitions of fairness in Appendix A. These extended experiments also show that diverse user preferences reduce fairness tradeoffs; an interesting direction for future work is to theoretically characterize user-item fairness tradeoffs under other definitions of fairness. Furthermore, in practice platforms are unwilling to maximize the worst-off user's 's item or user fairness at the expense of the entire platform's 's utility; the problem is really one of balancing user and item fairness with overall platform performance. Algorithms to optimize these multi- sided problems are explored in other work [12], but would be interesting to develop qualitative observations about user-item faimess tradeoff's in the presence of a total utility constraint. Finally, we show our Theorems and 4 in a limited context with only two or three types of users. However, the theoretical framework developed in Section 3 is significantly more general. It is would be interesting to apply this framework to other population structures such as when users do not have perfectly opposite preferences and where there are more than three groups of users.
10

---

Acknowledgments and Disclosure of Funding
SG supported by a fellowship from the Cornell University Department of Computer Science and an NSERC PGS-D fellowship [587665]. NG is supported by NSF CAREER IIS-2339427, and Cornell Tech Urban Tech Hub, Meta, and Amazon research awards. The authors would like to thank Sidhika Balachandar, Erica Chiang, Evan Dong, Omar El Housni, Meena Jagadeesan, Jon Kleinberg, Kevin Leyton-Browe Michela Meister, Chidozie Onyeze, Kenny Peng, Emma Pierson, and Manish Raghavan for valuable conversations and insights, as well as the NeurlPS 2024 reviewers for helpful feedback.
References
[1] arXiv.org submitters. arXiv dataset, 2024. URL https://www.kagee
[2] Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, page I 12-1211 New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781 595936631 18. doi: 10. 145/1250799. 2500088 URL wtt.h:ttt////oot org/
10. 1 101111111157000 1250808.
[3] Theo Barre, Omar El Housni, Marouane Ibn Brahim, Andrea Lodi, and Danny Segev. Assort- ment optimization with visibility constraints, 2024. URL https: //axxiv wwtp//vvoorr/oooooooooooo httg//bs/220000 13656.
[4] Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-fiee algorithms for contextual bandits. Management Science, 67, 07 2020. doi: 10.12877mmss.2220.550
[5] Kinjal Basu, Cyrus DiCiccio, Heloise Logan, and Noureddine El Karoui. A framework for fairness in two-sided marketplaces, 2020. URL https: www.oogg/////ooooooooo/....... hatg/ab/20006 12756.
[6] Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong. The price of fairness for indivisible goods. Theory of Computing Systems, 65:1069 1093, 2019. URL https:
/ //api. semanticscholar Trrg/CorpuIID::: 1522282239:12 152282391.
[7] Dimitris Bertsimas and John Tsitsiklis. Introduction Linear Optimization. 1998.
[8] Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. The price of fairness. Operational Research, 59:17-31,
[9] Omar Besbes, Yash Kanoria, and Akshit Kumar. The fault in our recommendations: the perils of optimizing the measurable, 2024. URL httttt//s///rii http://////aaooooo//aaaab/ess//s org/abs/24055 03948.
[10] Robin Burke. Multisided fairness for recommendation, 2017. URL https::ts:///ariv.oom abs/1707.00083 00093.
[11] Robin Burke, Nasim Sonboli, and Aldo Ordonez-Gauger. Balanced neighborhoods for multi-sided fairness recommendation. Sorelle A. Friedler and Christo Wilson, editors, Proceedings of the 1st Conference Fairness, Accountability and Transparency, volume 81 of Proceedings of Machine Learning Research, pages 202-214. PMLR, 23-24 Feb 2018. URL httpss:/prroeeedingg mlr ppess/v81/burkes
html.
[12] Qinyi Chen, Jason Liang, Negin Golrezaei, and Djallel Bouneffouf, Interpolating item and user fairness in multi-sided recommendations. In The Thirty-Eightl Annual Conference on Neural Information Processing Systems, NeurlPS 24, 2024. URL 10050.
[13] Arman Cohan, Sergey Feldman, Iz Beltagy, Doug Downey, and Daniel S. Weld. SPECTER: Document-level representation learning using citation-informed transformers. In ACL, 2020.
[14] Jessica Dai, Bailey Flanigan, Meena Jagadeesan, Nika Haghtalab, and Chara Podimata. Can probabilistic feedback drive user impacts online platforms? In International Conference on Artificial Intelligence and Statistics, pages 2512-2555 12-2220. PMLR, 2024.

---

[15] Sarah Dean, Evan Dong, Meena Jagadeesan, and Liu Leqi. Accounting for Al and users shaping one another: The role of mathematical models, 2024. URL https://arxii.... org www./bs///////o/ooo/gooo/.eeeee/ abs/2404. 12366.
[16] Paresha Farastu, Nicholas Mattei, and Robin Burke. Who pays? Personalization, bossiness and the cost of fairness, 2022. URL.
arg/ 04043.
[17] Naveen Garg, Telikepalli Kavitha, Amit Kumar, Kurt Mchlhorn. and Julián Mestre. Assigning papers to referees. Algorithmica, 58(1):119-136 September 2010. ISSN 0178-4617.
[18] Nikhil Garg and Ramesh Johari. Designing optimal binary rating systems. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1930-1939. PMLR, 2019.
[19] Nikhil Garg and Ramesh Johari. Designing informative rating systems: Evidence from an online labor market. Manufacturing Service Operations Management, 23(3):589-605, 2021.
[20] Wenshuo Guo, Karl Krauth, Michael Jordan, and Nikhil Garg. The stereotyping problem in collaboratively filtered recommender systems. In Proceedings of the 1st ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pages 1-10, 2021.
[21] Andreas Haupt, Dylan Hadfield- and Chara Podimata. Recommending to strategic users. 2023. URL https / /awxiv.vvvv/////i///a/////aaal org/ httg/bb/23000 06559.
[22] Daniel Huttenlocher, Hannah Li, Liang Lyu, Asuman Ozdaglar, and James Siderius. Matching of users and creators in two-sided markets with departures, 2023, URL https://arxiv org/ abs/2401. 00313.
[23] Meena Jagadeesan, Nikhil Garg, and Jacob Steinhardt. Supply-side equilibria in recommender systems, Advances in Neural Information Processing Systems. 36, 2024.
[24] Mariusz Kaleta. Price of faimeess on networked auctions. J. Appl. Math,, 2014:860747:1- org/ Chrp/oCrpusIDDDD : 38538799.
860747:7, 2014. URL
[25] Rodney Michael Kinney, Chloe Anastasiades, Russell Authur, Iz Beltagy, Jonathan Bragg, Alexandra Buraczynski, Isabel Cachola, Stefan Candra, Yoganand Chandrasekhar, Arman Cohan, Miles Crawford, Doug Downey, Jason Dunkelberger, Oren Etzioni, Rob Evans, Sergey Feldman, Joseph Gorney, David W. Graham, F.Q. Hu, Regan Huff, Daniel King, Sebastian Kohlmeier, Bailey Kuehl, Michael Langan, Daniel Lin, Haokun Liu, Kyle Lo, Jaron Lochner, Kelsey MacMillan, Tyler Murray, Christopher Newell, Smita R Rao, Shaurya Rohatgi, Paul Sayre, Zejiang Shen, Amanpreet Singh, Luca Soldaini, Shivashankar Subramanian, A. Tanaka, Alex Wade, Linda M. Wagner, Lucy Lu Wang, Christopher Wilhelm, Caroline Wu, Jiangjiang Yang, Angele Zamarron, Madeleine van Zuylen, and Daniel S. Weld. The Semantic Scholar Open Data platform. ArXiv, abs/2301.10140. 2023. URL https://pppp http//pp..smmaicscchh.l.aaa Tng/Corpus 256194545.
[26] Jon Kleinberg and Michela Meister. Modeling amplification in a network of speakers and listeners. Private correspondence, 2024.
[27] Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. The challenge of understanding what users want: Inconsistent preferences and engagement optimization. Management Science, 2023.
[28] Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. Mining of Massive Datasets. Cambridge University Press, 2011.
[29] David Liu, Jackie Baek, and Tina Eliassi-Rad. When collaborative filtering is not collabora- tive: Unfairness of PCA for recommendations, 2023. URL htt..tttss//rrr..orggaaasae 09687.
[30] Lydia T Liu, Nikhil Garg, and Christian Borgs. Strategic ranking. In International Conference on Artificial Intelligence and Statisties, pages 2489-2518, PMLR, 2022.
12

---

[31] Weiwen Liu and Robin Burke. Personalizing faimess aware re-ranking. In FATRec Workshop on Responsible Recommendation, page appear, 2018.
[32] Zhi Liu and Nikhil Garg. Redesigning service level agreements: Equity and efficiency in city government operations. In ACM Conference on Economics and Computation, 2024.
[33] Thomas Ma, Michael S Bernstein, Ramesh Johari, and Nikhil Garg. Balancing producer faimess and efficiency via Bayesian rating system design. In International AAAI Conference on Web and Social Media, ICWSM '25, 2025.
[34] Vahideh Manshadi, Scott Rodilitz, Daniela Saban, and Akshaya Suresh. Redesigning Volunteer- Match's 's ranking algorithm: Toward more equitable access to volunteers. Available at SSRN 4497747, 2023.
[35] Rishabh Mehrotra, James MeInerney, Hugues Bouchard, Mounia Lalmas, and Fernando Diaz. Towards fair marketplace: Counterfactual evaluation of the trade-off between relevance, fair- ness & satisfaction in recommendation systems. In Proceedings of the 27th ACM International New
Conference Information and Knowledge Management, CIKM '18, page York, NY. USA, 2018. Association for Computing Machinery. ISBN 9781450360142. doi: 011144/326920632770000 URL https: //to:/ org/10gg///o 10. 1145 32622066222222 3272027..
[36] Smitha Milli, Emma Pierson, and Nikhil Garg. Choosing the right weights: Balancing value, strategy, and noise in recommender systems, 2023. URL https: //tp://///xivi//// www.aaiww.......a...oo.ooooooott wrg.abs/2303 17428.
[37] Hervé Moulin. Fair Division and Collective Welfare. MIT Press, 2003.
[38] Brendan O'Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 16963)11022-1068 June 2016. URL http: //tanfo/// cadu/bbodd/papeee papers/ 8C8 html.
[39] Gourab K Patro, Arpita Biswas, Niloy Ganguly, Krishna P. Gummadi, and Abhijnan Chakraborty. FairRec: Two-sided fairness for personalized recommendations in two-sided platforms. In Proceedings of The Web Conference 2020, WWW '20, page 1194-1204, New York, NY. USA, 2020. Association for Computing Machinery. ISBN 9781450370233, doi: 10. 10.1145/3366423, 3380196. URL httpp:///dot http///do.oooo/o//////////////// / 3380196.
[40] Gourab K Patro, Lorenzo Porcaro, Laura Mitchell, Qiuyue Zhang, Meike Zehlike, and Nikhil Garg. Fair ranking: A critical review, challenges, and future directions. In Proceedings of the 2022 ACM conference on Fairness, Accountability, and Transparency, pages 1929-1942, 2022. doi: 10.1 10.1154/3331 146.3333333
URL httph:tt///oot orgg 10. 00.11////31111 146553114114111111 353323.
[41] Kenny Peng, Manish Raghavan, Emma Pierson, Jon Kleinberg, and Nikhil Garg. Reconciling the accuracy-diversity trade-off in recommendations. In Proceedings of the ACM on Web Conference 2024, WWW '24, page 3318-1329, New York, NY, USA, 2024. Association doi: 10. 14114//59993343555525,. URL
for Computing Machinery. ISBN 9798400701719. http:/...111/////1 1145 00W.8893333.66665.... 3645625.
[42] Hossein A. Rahmani, Yashar Deldjoo, Ali Tourani, and Mohammadmehdi Naghiaei. The unfairness of active users and popularity bias in point-of-interes recommendation. In International Workshop Algorithmic Bias in Search and Recommendation, 2022. doi: 10. (007/978-3-031-099316 6. URL https: //doi. org / /00 1007/078-7733 000-000---0000 031-09316-6.2 6_6.
[43] John Rawls. A Theory of Justice: Original Edition. Harvard University Press, 1971. ISBN 9780674880108. URL http: / www.jstorrr
htt.ssooor//ttalleeeeoooo wwwp///ttl///.oo/oo ctvjf926v.
[44] Ashudeep Singh and Thorsten Joachims. Faimess of exposure in rankings. In Proceedings of 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, page 2219-2228, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978 9781450355520 doi: 10. 00.1145//21181192220000 URL. httpps://aat wrg/o0rg./.. 1145/ 3219819 3220088.
13

---

[45] Ivan Stelmakh, Nihar B. Shah, and Aarti Singh. Peerreview4all: Fair and accurate reviewer assignment peer review. In Aurélien Garivier and Satyen Kale, editors, Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pages 828 856. PMLR, 22-24 Mar 2019. URL. https:// proceedings. mmr. press/v98/steee stelmakh199..hme
[46] Zhongzheng Tang, Chenhao Wang, and Mengqi Zhang. Price of fairness in budget division for egalitarian social welfare. In International Conference on Combinatorial Optimization and Applications, volume 12577 of Lecture Notes Computer Science, pages 594-607. Springer, 2020. doi: 1210077/97--3-00--6668808 978-3-030 64000064443-5400
40. URL https: :/do:i:///di.. org/10.
[47] Lequn Wang and Thorsten Joachims. User fairness, item fairesss, and diversity for rankings in two-sided markets. In Proceedings of the 2021 ACM SIGIR International Conference on Theory of Information Retrieval, ICTIR '21, page 23-41, New York, NY, USA, 2021. Associa- tion for Computing Machinery, ISBN 378145038611 11. doi: 10. 10.1145/2471158.347722 URL https://doi. /ttp://///oo.o//1..... 1145/3471155 3472260.
[48] Lequn Wang. Yiwei Bai, Wen Sun, and Thorsten Joachims. Fairness of exposure stochastic bandits. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pages 10686-10696. PMLR, 18-24 Jul 2021. URL https: https://prroeeedings mlr..mmr.... www.mmrrrp.... / v139/wang21b. html.
[49] Yong Xiao, Jianwei Huang, Chau Yuen, and Luiz A. Dasilva. Fairness and efficiency tradeoffs for user cooperation in distributed wireless networks. 2013 Proceedings IEEE INFOCOM, pages 285-289, 2013. doi: 10.1 110/NNCC...200..6666677 URL htt.httss///eeeeplrrr lee..org/ea..................... httg/doccumen//55667555
[50] Chen Xu, Sirui Chen, Jun Xu, Weiran Shen, Xiao Zhang, Gang Wang, and Zhenhua Dong. P-MMF: Provider max-min fairness re-ranking in recommender system. In Proceedings of the ACM Web Conference 2023, WWW '23, page 3701-3711, 1, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450394161. doi: 10. 10.1145/35430073553290
URL https://doi. orgoorg//// 10. 1145/3543507. 3583296.
[51] Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza- Yates. FA*IR: A fair top-k ranking algorithm. In Proceedings of the 2017 ACM
Conference on Information and Knowledge Management, CIKM '17 page 1569-1578, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450349185. doi: 10.1145/3132847.313222 URL https: //doi. org/10...00o 114533138711 3132938.
14

---

A
Extensions
In the experiments below, we subsample recommendation settings the same way as described in Section 6 but with 50 papers and 100 authors.
A.1
Alternative definitions of fairness
Nash Welfare
The first alternative definition of fairness we consider is Nash welfare [37].
UNw(p) = Σ log U.(p), INw(p) = Σ log (p(p).
This measure of fairness more holistic than egalitarian fairness accounts for the utilities of all users (items). In Figure 2, we show the results of repeating the experiment in Figure with Nash Welfare fairness. We that the trade-off between user and item fairness is steeper for homogeneous populations of users than for uniformly random populations. While the curves appear more concave than before, it is important to notice that we replaced y with 1/y in the item fairness constraint the optimization problem due to the Nash welfare being negative (as detailed in Figure 2), so that while still capturing constraint strength has a slightly different interpretation than previously.
-10
-30
-30 Ranzam
Na-otimation
Pamoggnesss
1.0
0.5
Ber
(a) Homogeneous versus diverse users
(b) With and without misestimation
Figure 2: We repeat the experiment of Figure from the original paper but replace max- max-min fairness with Nash welfare fairness. That is, in the objective we replace Unin with the user Nash welfare U UNw- We must be more careful with the item fairness constraint: we know that the normalized utilities satisfy 0 S U,, 1 I 1, so UNw, JNw < O. This means that in Problem we must replace the item fairness constraint mii (p) 2 yT with the constraint kw(p) 2 (1/7) When 7 O, this corresponds to INw(p) when 7 = 0 there is effectively no item fairness constraint, and y = constrains item fairness to be maximal.
Do; when 7 1, this corresponds to mmin (p) 2 Iinn Thus before,
Sum of k-min The second alternative definition of fairesss consider is the sum of the k- minimum user or item utilities, which is generalization of egalitarian fairness (k 1) that measures the utility of size-k set of worst-off entities,
Up-min()) min
(p), In min ff..
(p).
31 f....
In Figure 3, we show the results repeating the experiment Figure with max-sum-k-min fairness. We again observe that the trade-off between user and item fairness is steeper for homogeneous populations of users than for uniformly random populations. We also do not see an increase the price of mis-estimation when item constraints are added again, the price of mis-estimation is very high.
A.2 Alternative item utility models
In our theoretical and empirical results, we use a symmetric utility model, where an item's utility for being recommended to a user the same as the user's utility for the recommendation. Formally, in general item has utility w for being recommended to user i, while user may have different
15

---

2.75
2.50
Ploeximmtion
2.00
1.5
1.73
1.0
1.50
Rendom user
tomegenecus LS427
0.0
0.2
0.4
C/6
2.0
Trem falmmess constraint dtregght
farmess constraie strength
(a) Homogeneous versus diverse users
(b) With and without misestimation
Figure 3: We repeat the experiment of Figure from the original paper but replace max-min fairness with max-sum---min fairness for k 3. In the optimization in Problem 1, we replace Umin and Imin with Uk-min and I--in respectively.
utility w for that recommendation, In our theoretical and empirical results above, we took waj = wy, way. Below, we discuss the rationale for this model, and show that this assumption may be relaxed in our theoretical and empirical results.
The symmetric utility model we use which corresponds to the "market share" item utility model in Chen et al. [12] is motivated by platforms in which both users and items derive utility from successful recommendation. This is reasonable in settings in which not only does user want to be recommended relevant items, but an item's producer wants it be recommended to for which the item is especially relevant. Concretely, in the case of readers receiving recommendations for academic pre-prints, the readers prefer papers that they will engage with, and authors prefer readers that will engage with their work. in an online marketplace producers want customers who will purchase their product be shown the item; social media setting, content creators prefer their content to appear to users who will appreciate it and thus engage with future content. Our symmetric utility model captures this basic structure behind producer preferences in many cases.
Note that since users can only receive a limited number of recommendations, our assumption does not eliminate the tension between user and item utility: individual user wants recommendations that maximize her total utility across all items, while an individual item wants the platform to produce recommendations that maximize its total utility across all users. A concrete example of this is that under this model a low-quality item will want to be recommended to the user most likely to click on it, but that user won't want be recommended the low-quality item. This assumption does, however, imply that the platform-wide item utility and platform-wide user utility are equivalent for recommendations Pij. these are both E; E; WayPi..
One generalization of the symmetric utility model is where each user and item receives utility proportional to some shared recommendation quality wij- Formally, each user receives a utility of a:Wi; and each item j receives a utility of by from recommending to i, for a,, by >> 0. For example, different values of a; could capture different levels baseline interest in items among users. Our theoretical results still hold in this more general setting, since these coefficients will cancel out when we normalize the utilities.
Another common item utility model is exposure [11, 39], where items receive utility only from being recommended, and are ambivalent which user it is shown to. Formally, this corresponds taking w/J = 1 for all j. Intuitively, with exposure- based item utility. the item fairness constraint will cause the users' recommendation policies move from being concentrated on the most popular items, to more uniform distribution over items. If the users in the population have diverse preferences, each item will already have an approximately uniform probability of being recommended, so that imposing item fairness constraints has a low cost.
In Figures& and we examine the robustness of our empirical results in 3a and 3b respectively as we interpolate the item utility model between symmetry and exposure. In Figure 5 we see that user
"f course, this need not platform's utility: general platform might receive utility ri user i selects recommended item j. Aggain we could take wly for some b; > O. but this would have equivalent normalized item utilities.
16

---

preference diversity indeed still improves the user-item fairess tradeoff when we change the item utility model. We also again see that the price of mis-estimation does not appear to increase with item fairness.
1
36
3.77
47
61.
wesggran 1011
s0rgees 20 1949
14
C4
94
10
(a) A 0 (symmetric)
(b) A 0.33
(c) A 0.67
(d) A (pure exposure)
Figure 4: Robustness of empirical findings without symmetry assumption: user-item fairness trade- offs and diversity as item utilities become less correlated with user utilities. Here, we take the user utilities w" to be derived from the arXiv recommendation engine similarity scores as in Figure 3a. For each plot the item utilities are a linear interpolation between the users' utilities and exposure. Formally, w/j A 1 + (1 A) w.. When A = 0, item and user utilities agree; when A = 1 items derive utility solely from exposure.
344-
Rec.
42-
23
CP
33
13
03
34
(a) A = 0 (symmetric)
(b) A = 0.33
(c) A = 0.67 (d) A = (pure exposure)
Figure 5: Robustness of empirical findings without symmetry assumption: item fairness constraints still do not increase the price of mis-estimation empirically. Here, we take the user utilities wo to be derived from the arXiv recommendation engine similarity scores as in Figure 3b. For each plot the item utilities are a linear interpolation between the users' utilities and exposure. Formally, w/, = A 1 + (1 A) wy. When A 0, item and user utilities agree; when 1 items derive utility solely from exposure.
B arXiv recommender empirical details
We prototype recommender for preprints on arXiv, to illustrate our conceptual findings. We consider the cold start setting for items (papers), when they are newly uploaded to arXiv and so only have metadata but associated interaction citation data. For users (readers), we use as data the papers that they have published on arXiv in the past; we assume authors with identical names are the same author. We implement various natural language processing- both items and the user's ' historical papers) to generate similarity scores (utility matrices) for users and items. We use the similarity scores generate recommendations for each user, at various levels of user and item fairness constraints. We validate our approach by analyzing how citations correlate with the similarity score.
methods on the abstract text (for
B.1 Dataset and computation details
The original dataset was sourced from the public ArXiv Dataset available on Kaggle, containing 1, 1,796,911 articles. This dataset covers wide range of scientific categories. Each entry in the dataset is characterized by features which include:
IDD: A unique identifier for each entry.
Authors: Names and affiliations of the authors.
*Used under license CCO Public Domain
17

---

Title:
The title of the paper.
Categories: The scientific categories for the paper.
Abstract: A brief summary of the paper.
Update Date: The date of the latest update.
We further join this data with citation data from the Semantic Scholar API [25].² For each paper, have both the papers that it cites and the papers that cite it.
We focus exclusively entries classified under the "Computer Science (CS)' category. We extract entries where the primary category designation was 'CS', and remove null and duplicate paper ID values. This filterigg results in 177,323 entries.
This entire empirical workflow was run on machine with 64 CPUs, TB RAM, and TB (non- SSD) disk. The estimated time was about 20 hours per week for 3 months, and the longest individual run was approximately hours.
Train and test data As training (to construct embeddings for users), consider papers that those users published up to the end of 2019. Papers 2020 are in the test set (the set available to be recommended). Papers after 2020 used evaluate recommendations (did the user cite paper published in 2020).
The training dataset has 139,308 papers, and the test dataset has 14,307 papers, with the remaining being post-2020 papers. The training dataset has 178,260 distinct users with an average of approxi- mately 2 papers per user. Figures 6a and 6b show the distribution of research paper subcategories between the train and test datasets. Figure 7 below shows distribution the number of papers per user in the training set logarithmic scale for the y-axis. The x-axis represents the number of papers per user, ranging from 0 to over 250.
Splitting the training and test data temporally both reflects practice and allows us to evaluate the recommendation model's effectiveness in predicting future citations. As detailed below, the model's success was measured by whether papers our model would have recommended to users in 2020 were fact cited in their subsequent works. For further details, see below Section B.3 on the model evaluation.
B.2 Recommendation models
Each recommendation approach has two design dimensions: (a) how we generate embeddings for each paper (papers to be recommended, and papers uploaded by users that will be used construct user embeddings), and (b) how similarity scores are constructed once we have an embedding for each paper. Below, we evaluate each approach by their effectiveness in recommending papers that users are likely to cite in their future works.
(a) Generating embeddings for each paper We use text-based analyses the abstracts of each paper to generate paper embeddings. The first approach is TF-IDF, while the second employs Sentence Transformers.
TF-IDE.
The first preprocessing step involved removing stopwords-comme words with little informational value, such as "and" and "the"-to reduce noise and emphasize meaningful content. Next, TF-IDF (Term Frequency-Inverse Document Frequency) vectorizer is applied to count term frequencies and scale them according to their rarity across the dataset, highlighting unique and informative words. The resulting frequency vector for each abstract is used as its embedding.
Sentence Transformers. The author- recommendation model using Sentence Transformers leverages contextual embeddings from sentence-level representations. The preprocessing involves tokenizing the text (title, abstract, and categories) and generating embeddings using pre-trained Sentence Transformer model, specifically the AllenAl SPECTER model [13], available on Hugging Face.
5 Useed under Semantic Scholar API License Agreement
'I Licensed under the Apache License, Version 2.0
18

---

Compate casa.
unaergg deeteeed me compungg
Scacaa resee sas feserly
Casm Daary
cap-canggpee
(a) Distribution of rescarch paper publications in the train dataset over time
sangee and aaaa Towery
Cood Deaade Speans
Eeciam penpiaiion Unganate
and Paace Purgetoon
Scone
boteer and toeas
CAmpUE SaMera sugrrggee
(b) Distribution research paper publications in the test dataset over time
Figure 6: Distribution of research paper publications time
(b) Constructing similarity scores for each user-paper pair. After constructing embeddings. we have an embedding for each paper in the potential recommendation set, and for each paper authored by a user in the training set. We construct user-paper similarity scores as follows. First, we compute the cosine similarity between each recommendation set embedding and each user's papers' embeddings. Then, the similarity score between each user and the recommendations set paper is constructed using one of the following approaches:
Mean score. We take the mean of the cosine similarities between the recommendation paper and each of the papers by the user in the training set. This approach is equivalent to constructing user embedding as the mean embedding of their uploaded papers.
Max score. The mean similarity score has been recognized as not capturing diverse interests that may have [20, 41] for example, for user who has published papers in two
19

---

101
104
102
Lng
30
100
150
200
250
Number of Papers
Figure 7: Distribution of the number of papers per user in the training set on logarithmic scale
different subject areas, paper should be recommended to them if it matches either of their interests, as opposed to the average of those interests. Thus, we also construct user-papel similarity scores via the max similarity between any of the user's training set papers, and the recommended set paper.
Note that we also experimented with using dot products instead of cosine similarity; results are similar and omitted.
B.3 Model evaluation method
We evaluate each of the four approaches (TF-IDF and sentence transformers, each with the max or the mean scores) using citation data for 1,128 users (authors) and 14,307 papers. For each user pape- pair, we use the following as outcome data:
User cites paper in the future:
the paper eited by the user in the future?
Paper cites user: Does the paper cite the user already? We that this data is technically available at the time of a hypothetical recommendation for a new paper, and so in theory could be used by a recommender. Thus, although metric does directly measure the future behavior of the user, it helps in understanding the contextual alignment (determined just by natural language processing of the abstracts) of the recommended papers with the user's previous research or interests. Importantly, these references are not part of the data used to generate the similarity score.
In both cases, we consider the presence of citations signifying a good recommendation.
For each recommendation approach, we calculate the relationship between this citation data and the following similarity score measures.
Similarity score: The raw cosine similarity score.
Score percentile: The percentile rank the similarity score, where percentile calculated for each user.
Normalized score: The similarity score is normalized by subtracting the mean and dividing by the standard deviation of scores for each user.
A successful recommendation approach would have strong relationship between text-based similarity scores and future citation outcomes.
B.4 Evaluation results
We evaluate each of the 4 approaches. As summarized below, we find that the best performing approach using the TF-IDF vectorizer to construct abstract embeddings, and then using the max similarity scores between any of their papers in the training and each paper in the recommended
20

---

set. We find that this approach is effective at predicting future citations by the user, especially for cold start recommender that uses only abstract textual information, and for such a sparse outcome as citations.
Citation Type
No/Yes
Similarity Score
Score Percentile
Normalized Score
No
0.041454
0.499737
-0.001701
User cites paper
Yes
D.133650
0.765008
1.514331
No
0.041147
0.498860
-0.006536
Paper cites user
Yes
0.138199
0.784410
1.582545
Table 2: Average similarity measures in the Max score, TF-IDF model, conditioned on citation presence for different types of citations.
DADOY
Autior cibos paper
12-
Dondty
Denafty
0.0
Similorty
Similanty Score Percentile
(a) Density plot of similarity scores grouped citation presence.
(b) Density plot of similarity score percentiles grouped by citation presence.
Figure 8: Pr(score| User cites paper), the distribution of the score for user-paper pair, conditional on whether the user cites the paper in the future, for the Max score, TF-IDF model.
Variable
Coefficient
Std. Err
z-value
P-value
Adjusted R²
Similarity score
12.4100
0.058
212.178
0.000
0.08915
Score percentile Normalized Score 0.3905
3.9218
0.035
111.194
0.000
0.05973
0.002
158.421
0.000
0.05159
Table 3: Logistic regression results for predicting whether user i cites paper j from the similarity score Way, for the Max score, TF-IDF model
Max score, TF-IDF Table 2 shows the similarity measures described above averaged over all users and test papers. conditioned on whether or not citation occurred between the user and paper (whether the user cites the paper, or vice versa). Figure illustrates the distribution of similarity scores for papers that were cited (orange) versus those that were cited (blue) by the user in the future. The density for cited papers is higher at higher levels of similarity scores compared to non-cited papers. Table 3 performing logistic regression between the user-paper score and whether the user cites the paper with a bias term ("User cites paper ~ 1 + score'), ) for each score measure. All measures suggest that our next-based recommendation scores are effective for predicting whether the user will cite the given paper. For example, Figure 8b shows that Pr(Highest score Author cites paper) is more than five times Pr(Highest score bin Author does not cite paper).
Mean score, TF-IDF Table shows the similarity measures described above averaged over all users and test papers, conditioned whether not citation occurred between the user and paper (whether the author cites the paper, or vice versa). Figure 9 illustrates the distribution of similarity scores for papers that were cited (orange) versus those that were not cited (blue) by the user in the future. The density for cited papers is higher at higher levels of similarity scores compared to non-cited papers. Table performing logistic regression between the user-paper score and whether the user cites the paper with a bias term (" ('User cites paper ~ 1 + score') ) for each score measure.
Max score, Sentence transformer
21

---

Citation Type
No/Yes
Similarity Score
Score Percentile Normalized Score
No
0.019405
0,499717
-0,001799
Author cites paper
Yes
0.044938
0.783110
1.600929
No
0.019323
0,498790
-0.006737
Paper cites author
Yes
0.046283
0,801
1.631049
Table 4: Average similarity measures in the Mean score, TF-IDF model, conditioned on citation presence for different types of citations.
15.0
32.-
Denskty
10.0
0.0
Similnity Score
Similarity Scote Parcentie
(a) Density plot of similarity scores grouped by citation presence.
(b) Density plot of similarity score percentiles grouped by citation presence.
Figure 9: Trsscore/Auhhr cites paper), the distribution of the score for a user-paper pair, conditional on whether the user cites the paper in the future, for the Mean score, TF-IDF model.
Variable
Coefficient
Std. Err
z-value
P-value
Adjusted R²
Similarity score
20.2122
0.131
154.835
0.000
0.04616
Score percentile
4.3535
0.037
116.516
0.000
0.06934
Normalized Score
0.4184
0.003
164.894
0.000
0.05815
Table 5: Logistic regression results for predicting whether user i cites paper j from the similarity
score Wij. for the Mean score, TF-IDF model
Citation Type
No/Yes
Similarity Score
Score Percentile
Normalized Score
No
0.666801
0.499821
-0.00183
Author cites paper
Yes
0.784402
0.807 105
1.30730
No
0.666379
0.498851
-0.005735
Paper cites author
Yes
0.794945
0,805592
1.251814
Table 6: Average similarity measures in the Max score, Sentence transformer model, conditioned
on citation presence for different types of citations.
Variable
Coefficient
Std. Err
z-value
P-value
Adjusted R²
Similarity score
18.4557
0.250
73.695
0.000
0.1347
Score percentile
5.0122
0,098
51.161
0.000
0.08604
Normalized Score
1.2332
0.017
71.426
0.000
0.1076
Table Logistic regression results for predicting whether user i cites paper j from the similarity score Waj,, for the Max score, Sentence transformer model
Table 6 shows the similarity measures described above averaged over all users and test papers, conditioned on whether not citation occurred between the user and paper (whether the user cites the paper, or vice versa). Figure 10 illustrates the distribution of similarity scores for papers that were cited (orange) versus those that were not cited (blue) by the user in the future. The density for cited papers is higher at higher levels of similarity scores compared to non-cited papers. Table 7 shows the results of performing logistic regression between the user-pape user-paper score and whether the user eites the paper with bias term ("User cites paper ~ 1 score'), )), for each score measure.
22

---

Damiltyy
Similarity
Similarity Score Perconticc
(a) Density plot of similarity scores grouped citation presence.
(b) Density plot of similarity score percentiles grouped by citation presence.
Figure 10: Pr(score| Author cites paper), the distribution of the score for user-paper pair, conditional on whether the user cites the paper in the future, for the Max score, Sentence transformer model.
Mean score, Sentence transformer
23

---

Citation Type
No/Yes
Similarity Score
Score Percentile
Normalized Score
No
0.612678
0.499825
-0.001767
User cites paper
Yes
0.696291
0.803641
1.262704
No
0.612397
0.498891
-0.005418
Paper cites user
Yes
0.699609
0.796941
1.182465
Table 8: Average similarity measures in the Mean score, Sentence transformer model, conditioned
on citation presence for different types of citations.
Denitty
Similarity
Similarity Parcentie
(a) Density plot of similarity scores grouped citation presence.
Density plot of similarity percentiles grouped by citation presence.
Figure 11: Pr(score| User cites paper), the distribution of the score for user-paper pair, conditional on whether the user cites the paper in the future, for the Mean score, Sentence transformer model.
Variable
Coefficient
Std. Err
z-value
P-value
Adjusted R²
Similarity score 16.2482
0.246
66.148 148
0.000
0.09085
Score percentile
4.9088
0.097
50.820
0.000
0.08377
Normalized Score
1.2297
0.018
69.188
0.000
0.1026
Table 9: Logistic regression results for predicting whether user i cites paper j from the similarity score Wij. for the Mean score, Sentence transformer model
Table 8 shows the similarity measures described above averaged over all users and test papers, conditioned on whether not citation occurred between the user and paper (whether the user cites the paper, or vice versa). Figure 11 illustrates the distribution of similarity scores for papers that were cited (orange) versus those that were not cited (blue) by the user in the future. The density for cited papers is higher at higher levels of similarity scores compared to non-cited papers. Table 9 shows the results of performing logistic regression between the user-pay paper score and whether the user cites the paper with bias term ("User cites paper ~ 1 + score'), ) for each score measure.
Altogether, each model performs fairly well; the model using sentence transformer embeddings and the max similarity score among each author's papers appears to perform the best overall.
C Proof of Section 3 results
In this section, we provide complete proofs for Proposition and Proposition 2. In this and all other proofs in the appendix, we ignore the dependence on the utility matrix w in the user and item utility and fairness functions when clear.
The following result will be broadly useful throughout the rest of the proofs.
Lemma 1. Since Wii > 0 for all j. Ii >
Proof. Let Pij 1. Then (p) > 0 for all j so Imin (p) and Iin max, Imin (p) > 0.
First, recall the statement of Proposition 1.

---

Proposition 1. Suppose that for set of recommendation policies S _ A n-11
(i) S can be described by a finite set of linear constraints
(i) There exists optimal solution p" to Problem (2) such that p² S
(iii) p² is the unique feasible solution to Problem (2) in S
Then, finding optimal solution p" to Problem (2) can be reduced to solving a linear program L.
Proof. We first need the following result, which states that the feasible set of can be expressed as a linear program. We will prove this result below.
Lemma 2. Let F denote the feasible set of Problem 1,
F arg
max PEA. n-1
Imin (p) - arg max min (p).. PEA. n-1
(3)
Then F is the solution set of the linear program
F arg
(4)
subject to 1g(p) = Vj.
Now, condition (iii) on S implies that there is unique p² in S n F. Thus
p F FNS arg PEAR_,nS,A
max
(5)
subject to ()(p = Vj,
We add S as constraint in Problem 4 because know that there is least one solution Problem in S - namely, - this additional constraint will not change the optimal objective value, but will constrain the set of optimal solutions to be in S, desired.
By condition (ii), p" an optimal solution for Problem I; by condition (i), can be described by finite set of linear constraints, and thus Problem 5 is linear program; call this L.
We now show Lemma 2.
Lemma 2. Let F denote the feasible set of Problem 1,
F arg
max
Iuin (p) - arg max min (p)...
(3)
DEA --
PEAT
Then F is the solution set of the linear program
F arg PEA 1nr
max
(4)
subject to 1p(p) = Vj.
Proof. To show this, prove by contradiction that every optimal policy gives each item the same normalized utility; that is, we show that if the policy p is an optimal solution of Problem 3, then there is some À such that for all (p) X, and in this case À min; (p)) This implies that any solution P to Problem is a feasible solution of 4. Since these two problems have the same objective, and the additional constraint in Problem 4 does not eliminate any solutions. the two problems have the same solution set.
To show that all items have the same normalized utility the optimum, we suppose the contrary and produce contradiction. Suppose that the policy p maximizes min, (p), but there some j such that (p) > - We will show that this means
construct such that min (p') I
First, note that impossible that Ptj Lemma 1, - > 0. Thus for some i, Pij 0.
for all i, otherwise Lini 1,(p) 0. However, by
Define J { (p) I }, and let j' J. Since Pij 0 and Σx Psk = Pay 1. Pick <> 0 such that PL, := Pij c > 0, Pbg = Pij' + c < 1, and I,(p') ) > I Since I, is linear the recommendation policy, this is always possible.
Now, repeat this process for j' E J, obtain a final recommendation policy pl in which Ie(p') > I for all f and thus Iuin (p') I This contradicts the optimality of I D
25

---

Now, we prove Proposition 2.
Proposition 2. Syymn satisfies conditions (i) and (ü) in Proposition 1. Furthermore, solutions P E Ssymn Problem (2) have sparse structure:
If is a basic feasible solution to the linear progrum L in Proposition 1, then there are at most n. + K type-item pairs (k,j) such that pkj >> 0 (out of nK possible pairs).
If p is also optimal, then there most K 1 items that than one type of user, i.e., where Pkijs Pw > for ls + k'.
recommended to
Proof. We will first prove that Syym satisfies conditions (i) and (ii), and then show sparsity.
Part Recall that for fixed w.
Ssymm pp:p: if W/ =wy n
{p: p
which is finite of linear constraints, condition (i) holds.
Now, we show condition (ii), that always there is some o² E Symm that is an optimal solution to
Problem 1. Let p be arbitrary optimal solution to Problem Then p is also feasible: Imiu (p) min
We first define a piece of convenient notation: if two users i, share the same utility vector W/p
we say that they have the same type r(i) T('). (i) = T(²) = T, we write way Wej == Wrj
Let
6U Ki : T(i)) = xi))}
Σ
Pej
())())=-())
for all j.j. We must show that:
dij dey for all i, where - T(i',
é is valid set of recommendation probabilities,
d is feasible: Iii (Ø) Iinn and
à is optimal: Umin (Ø) 2 U (p) U miin
Clearly dig = Φry for all i, where (()) T(²), since dij depends only on i through T()).
For each i,
Σ Dis = 1 :(t') T() (iT(())=(())
Σ ΣNO5 PPj = : T {())
Σ
1=1.
(1)(()==(()
Moreover, for all i.j. min,, Pro S 0i S max,, Pre S Thus & E A
To show that min (Ø) = I notice that intuitively, when we move from p to Φ. we redistribute item j among users of the same type. Since all of these users
the probability mass assigned generate the same value for item j, there should be no change in item j's expected utility. Formally,
Σx Wrj Eir(i) Dig
I Mmin (Ø) = min
Σ, Wti Eis(())r
Σ. Wrj Ei:(()) Pij
min
Σr Wrj Σi:(()
Jmin (p)
I
(p is optimal)
Finally, to show that Umin (Φ) > Umin (p), observe that if users with the same values are given different recommendation probabilities, some user will be worst off and have expected value lower than the average expected value over all users in that type. By averaging, we bring all users' expected
26

---

values to the average expected value across the type, increasing the expected value for the previously worst off user. Formally, for each type т. let i(T) arg min (p). Then
Up(r)(p) & (p) for all :T((') =T
Σラ=1 W for all i' T((')
max, Vi
max, V/
Ki r(1) = =T} Eー WriPi(Tis max, Uj
2j-1Wripe max, Uj
E
(TT(()==
E WrSPi(r)
Σj=1 Wry0rj
for all i' :(: =
(definition of ()
max, Ui
max, Vi
min Ui(p) S :-(()==
min (:((
(i)
Then
Unin (p) min min Uz(p) S min min U,(Ø) Unin (Ø)
(r(()=
(r(1)T
and we have shown that Umi (6) 2 Umin (p).
Part 2. Now we show the sparsity of solutions the linear program L in Proposition 1, that is, Problem 5 defined above the proof of Proposition 1. Given that E Syymms we can rewrite the linear program
Φ = arg
max A
A
PEA a-1nd
subject to In(p) > Vj.
which is the same as
Φ = arg max X
P.
subject
Ix(p) = Vj.
Σ Pkj = 1 Vk,
Pkj 2 Vh
where (p) shorthand for 1z(p") where p' E A is p E A expressed in terms of users rather than types. This is a linear program with nkK + 1 variables, and K equality constraints. Then for any basic feasible solution P of Problem 5, there must be nk + linearly independent active constraints (see Definition 2.9 in Bertsimas and Tsitsiklis [7]). This means that of the n.K constraints {pks 2 O...j. at least n + 1 - (n + K) must be binding. Equivalently, there can be at most nk (nk
(n + K))
K values of j such that Pkj 0.
p is also an optimal solution, then by Lemma there must some such that Pkj > for each j. which takes up non-zero values. Only K- non-zero values remain to be assigned, at most K items j have Pkjs PM'j > 0 for two types k, k'.
D Proof of Theorem 3
Recall Theorem and its setting. We let 01 > 02 ...>> U, and suppose that there are two user types. A user i either has value Wiy = vy for all j or Way = Un- for all j. corresponding types I and 2 respectively. That is, the two types have opposite preferences. We let a be the proportion of type users in the population, out of fixed population of users.
Theorem 3. FF (a) is decreasing in fofor 0 < S 1/2, and increasing in ar for 1/2 < a < 1.
D.1 Main proof
Proof. The proof will proceed in two parts. First, we will reduce the problem to finding solution for a linear program using the framework from Proposition 1. Then, we will find solution to the linear program. this proof, we will use a series of intermediate results, which we prove in the following section. The first such result is Lemma 3.
27

---

Lemma 3. For all 0 < a < 1. U (a) 1.
By Lemma 3, U
"min (a) : U min is constant in so
F [()((a) (um -m (1.o))/uma. and it is
enough to show U min (1,0) increases in
Recall the definition of Ssymm
(p: - Py if w; wy
By Proposition we know that Syymm is a satisfies conditions (i) and (ii) for Proposition 1.
Thus by Proposition 1, it is sufficient to find ø such that
E arg PESnA m-11d ind
max
A
subject to
I5(p) = Vj.
and show that this is unique, where the linear program is derived from the proof of Proposition 1.
Since each user in population only has of two possible value vectors, wN (V1: -0.9 vn)) or w.; = (V.....,, ) we can identify Ssymm with A?_1- and identify P E Ssymm with a pair æ; Expanding the expression for l,(p) and making explicit the dependence on a, see that
(ipisusy(a) Σ, (a)
a)
Exr(1== Pijul Σ Eiz((i)= P PiyUn-jt1
Exr()=11 1/ + Σ Ei Un-jt1
mazzy, + m a Un-
mar; + m(1 (1 Un1+++
=
qg(() + (1 - (3(
where
(5(0): =
av,
ae; + (1 0n
Note that for all j and 0 < < 1, we have 0 < <; 1 - 4j < 1. We can thus simplify
Φ = arg
max .VEA
(6)
subject to g,(a)æ, + (1)0)))) Vj.
First, we will show uniqueness and find closed form to Problem 6 in Lemmas 4 and 5. Then, will use this closed forms to show that U (1, a) is increasing for a < 1/2. By symmetry, this implies that Unii (1, a) must be decreasing for > 1/2 and we will be done.
Lemma 4. Problem 6 has unique solution (z. y, A). Moreover, the solution is sparse: there is some 1 1 t n such that for j >> t, Iz = O, for t, yソ O.
Thus, solve our original problem (Problem
merely need evaluate the user fairness Umin of x, solving Problem and show that this is increasing. We will do this in the remainder of the proof.
For each let 2. y be the solution to the corresponding Problem 6, and define?
t(a) max(j (z(aa 0}.
Lemma S. Ler == t(a)). Define
L
R₁ = Σ j>t
1
1
jat
'While there is single optimal solution x, to Problem 6 for each there be two that satisfy Lemma 4. In particular, this occurs when for each j. zi or yi 0. By contrast, t(x:) is unique.
28

---

Then
min
1 qeL + (1 - qt Rs
and
jet
0,
t Re)
Ij
1+4 +(1
Le
= b,
Vj
1+ J.t
+1
0,
t
1-9g"
> t
Note that for + (((x), I, above may not be valid probability vectors.
Lemma For < a < 1/2, if p² is the optimal recommendation policy, then Uz(p", ,a) 2 (p" for rii) 1, 7(i') 2.
By Lemma 6, Unin (a) = Ui(() for with r(1) = 2. Then
Unin (1, U.(a)
1
Uj Untn-
max, Dj j=l
Ut(a) +
Σ
By Ujun-
max, Dj
5>t(a)
1- Σ
1 min (a)
Σ
min (a)
Un Un-((a)+1++
1 (j(()) Un Un-j+1
maxj By
(a)
s>((a))
j>(((a)
min (at)
Un Un-1(a)+1
Σ
(Vn-j+1 Un Un-o(a)+1)
max, by
j>((a)
The following results will enable us conclude that Unin (1, a) is increasing for < 1/2. Lemma 7. ((a:) is weakly increasing.
Lemma 8. min (o) is increasing for S 1/2.
Lemma 9, g,(a) strictly increases as increases and strictly decreases as j increases.
Since ((a) is increasing and "y decreases in j. Un-t(a)+1 increasing a. Also, T (a) r (o)
increasing. For j > t(a). Un- increasing for 1/2, and qı (a) is increasing, so (-))(a)
Un (n=t(a)+1 > 0. Thus, U (1, a:) is increasing.
D.2 Supporting lemma proofs
We will first prove Lemma 9, as it is simple result that we will use extensively. Lemma 9. qj(0) (a) strictly increases increases and strictly decreases as j increases.
Proof. Recall the definition of q, (a):
()(
av' + (1 a Un-j41
We can rewrite this as
1
(a)
1
000 i11
13
29

---

which is strictly increasing in a since Un-s+1/2y > 0.
Since 0j is decreasing in j. on-5+1/15 is increasing in j. Then since 1/a> > 1, (a - tn Ji1 is increasing, so 9; (a) is decreasing.
Lemma 3. For all 0 < a < 1. Uni (a)=1. = 1.
Proof. Simply put, the argument below says that since there are no total utility or item fairesss constraints, we can simply maximize utility for each user individually. When we do this, each user gets utility ratio of 1. Formally, recall that
Ej=1 Piy
min (a) = max min PEA
max, way (a)
We can pick zy for each user independently, so this problem becomes
Umin (a) = min
max
Σ Zx)Wiy(a).
max, Wij P.EA,
We know that Ej=1 Myy is maximized by putting all probability mass of pt on the coordinate of wA with the highest value, yielding expected value max, Wej. Then
Umiu (a) = min max; Wij 1.
max; Wij
Lemma 4. Problem 6 has unique solution (ar, y, A). Moreover, the solution is sparse: there is some 1 S t S n such that for j >> t, Iz = 0, and for < t, Dj = 0.
Proof. Let a be fixed; we will suppress the dependence on for the remainded of the proof. Recall that Problem a linear program, and we can therefore rely on known facts about the structure of solutions to linear programs prove this result.
Part 1 First, we show that at least n - of {z. Vi must be zero in every basic feasible solution.
By Proposition 2, since K = 2, at most + 2 - 1 + of {2yz U,}s can be non-zero and thus at least n 1 of these are zero.
Part 2 Now, show that every optimal basic feasible solution has the form above.
æ, y, A define an optimal basic feasible solution and 2, = O, then if > j. I; = 0. To see this, suppose this is not the case, that is, there is some j < i such that z, show that we can form x', ,''' with miny I5 (x', 3/) > X, which means that the policy p' formed by giving recommendation policy x' all users of type and recommendation policy 1 all users of type 2, is better solution to Problem 1 than the policy p defined by x. y. which means is not optimal and have contradiction.
but z, 0. We will
Since v, are feasible, we must have [, v) = 15(x', (x',,//' v/) X, so
q.c + (1 q:)yy = (1 93 B5)
Define x',// y/ as follows:
c
61
{=j
x/6
0,
t=i
otherwise
n-21
yj
I I-9i
9.c
+ E2
f=j
%/
3/1 +
gic_
+ E2
-
T-qi
y/::
otherwise
30

---

Intuitively, to define x' we move all probability mass away from i to j. To define y', we move sufficient mass from j to to offset the decrease value item from changing strictly increase T for all items f, in x' we also move 61 mass to the other items.
x'. In order to
These will be valid probability vectors for 61,62 O small enough; for x' this is clear. For y', must show that Yj I- Lemma 9,
q.c. and y) + q.c 1-q.
< L. Rearranging Equation 7 and noticing that qi > qi by
(1 13)10
+
< Uj S1.
1 qi
1 qi
Moreover,
V3
q.c
q.c + (1 9:)8/
9:c
(Equation 7)
96
9j
1 9i
qic + (1 )3/
9:C
(gj n
qi
1 qi
yi-
0
Now, we can show that miin (I', ..) min (x, 1/ = Linm which a contradiction. To do this, is sufficient to show that le 3/) > Le(x, y) for each L.
E E {t,j): Since x/2 > xe. V/c ye. Ie(x', ./) > Ie(2, v)-
l = i:
1,''' = =(1 1---) 4i:) y1 + - 9i
qic + 62
=1 qi 9:)1 9id + E2
= 11 3) +
=(=j:
4i
15(x'v))= 95(A (1) + -9;)
Vj
qi
(1 - 9;)yı + > ( 91
1 1 qj
E19j 62(1 95)
qi
- 4i
(,( x qj 4b
E19j <2 93)
qi
Since q3 > qt. 9j
9: 1-9s > 0, and thus 1,(x', w/) > [z(2, 3) 61. 62 are small enough. 1-4
Since we did not use the fact that a < 1/2 here, symmetric argument shows that we cannot have V; 0, y 0, and j.
Let & be the number of indices j such that 2j > The above arguments together imply that
I; = 0, > k. There are then at least n 1 - (n k) k 1 indices such that yj 0: the argument above implies that these zeroes are on the lowest possible indices, that is, yj = 0, j < Thus if we take t k we have that for j > t, Iy 0, and for リ! 0.
Finally, show that there is only a single optimal solution, which is basic feasible solution of this form.
Part 3
Suppose that x', x',y' is another optimal basic feasible solution; we will show that x' = x. =
Denote ((x, y) = max j xy > 0}.
If ((, v) t(,', then:
31

---

For j < <t, M, 0/ = 0, and
95 [x y)
(Lemma 5)
min (x. y)
(feasibility)
min (x', .3
(optimality)
(feasbility)
(Lemma 5)
so 2j = z
Similarly for j t, 23 2/- and
(1 -1-9) (- = 1ز 3) = miin (z, 3)) = mmin (2',2/) = 11(2', 1/) = (1 1 -;)l//
so 1/} = Vjj-
Finally, this means y = Ejst Uj =1 Ejzs 3/3 3/s and It = 1 -Ejet
1- E-Eeeo'j = z4.
Otherwise, without loss of generality let t(z', > t(z, y) == t. For j < t.
= = 1, = 1, v/) y3
x = I.. For j > t, Iz 0.
Furthermore.
4: + (1 - 4:vu = [1 = TT(2' = q
F q1
1 Σ
Fj
+ (1 20); q.r4
jet
- qt
1 Σ Jyj
+ (1 2) = 90
jJL
(1
9096 = 91
Σ o ját
Since q;, 1 q: > 0, and yt 2 0, Ej of S 1, it must be the case that y/ and
Ejst o4 = However, y/ > 0 by definition of i, and we have contradiction.
This means that there is only one optimal basic feasible solution, and thus there is only one solution to the linear program.
Lemma 5. Let < a < 1 t(a). Define
R₂ = Σ 1
L
jaL qi
9j
Then
1
1
min
1 1 + (1 gt R,
and
F
jct t,
0,
j <ct t
Ij
1 1 L. +1
L
a H
Dj
1
t+
L,
+
R.
9.)
j=t.
0,
t
1-95"
j>t t
Proof. Fix 0 < a < 1. This result mainly follows from the fact that =
= = 1, and
1,(x",y") 1,= y²) for all j.J' well the sparse solution structure shown in Lemma 4.
32

---

We know that the optimal solution satisfies min = 1 = lyr for all j.j'. We also already know that for 2- 0, and for j < t. Vjj
O.
For j < I, min 1 - zj + - zjj 93
fim.
For j > 1, T min
1 = 0 (j
{3) = Uj
finn.
1-
For j = t, we know min = 1 = ut + (1 - 91 Then for j < t, x, = 1/ (q:27 + (1 1: (1)) so
1- Z4
Σ 2j Σ 91
(9:0g (1-9))81) (q + (1 9c)
Σ
1
(q:24 (1- 90)
j2t
(8)
Similarly, Uj
1 l-q; (q + (1 - ()) so
1 - 11 = Σ
(1:34 + (1 - (:)ut) = (g:02 + (1 (())))) Re.
(9)
1 Dj
jst
Combining equations 8 and 9, we obtain
L (1 v6) =1 1-11-00 = D2 = 1
Lt R2
(1 - yt)
(10)
R2
Substituting equation into equation we get
I,
1 - y/ = 4t
(1 ye) + gt)81 Rr.
- + I
9t R₁ (1 + ge + (1 -et)
1 + q: Ia q1 Rr
Rr
ye
=1 - 1 91L1 + (1 (1) R
+ a1 + (1 q1) R
Then
L, (1 - y1)
Lr
It =
Rs
+ ge I + (1 - R4
Finally, we see that
-ii = 912's (1- Vt
L,
+ (1 9:) (1-
R
= =q: 1
+ q: Lu + (1 ạ1 Rr
grhr (1
Re
9:hr (1 - Re
+ a: I. + (1 Re
1
1+ 9:L, + (1 - Ri
Lemma 6. For 0 < < 1/2, if p² is the optimal recommendation policy, then Uz(p",ca > U. (p" (0, for T(i) 1, T(1)) =
Proof. Intuitively, the type with larger proportion in the population must shoulder the burden of ensuring item fairness to mediocre items, and thus users from this type will have a lower recommen- dation probability on the items they really like compared to the smaller group.
33

---

Formally, let i, i' be users such that r(1) = 1, 7(2") = 2. For 2 1/2,, < t(a),
Ij 8n-
(3(a) 1 1 (a)
any + (1 an
atn- (1 a)vy
(1 - o))
1
1
13
+
Un-j+1
2
1 a nn-j+1
Dj
a
Un-s+1 1
a
- a
Un-j+1 1 1 20
U/ a(1 a)
2 0
(0 (0<a$1/22)
So
max U3) . (U, - -Up)
Σ Vj Σ
vn-
151
121
Σ U2 - 2n 14n-)+1)
Σ
0jUn--+1
(collecting coefficients of vj)
igt
2
Σ
Velzy- - Yn (+1) - Σ
U/0n-j+1
(vr S by for j S t, > yn-i++)
jSt
j>1
1/
(1z Un 2/
Σ
Un-j+1
(vz > U for j > 1)
i5t
j>t
2 1/- 01
yn-f+1 11 Σ
Bn-
Ejst 1)
15t
jzt
1/- Ft
Ej Uj 1)
0
Since max, Uy > O, we have that U, 2 Up.
Lemma 7. t(a) is weakly increasing.
Proof. Suppose not, that is, there are some a < a' such that := t(a) > t(a') == We will split this problem into several cases based which of a, a' gives a solution with higher item faimess, and show the implications of decreasing i on the closed-form solutions from Lemma 5, eventually reaching a contradiction in each case.
Recall from Lemma 9 that dj (a) any a)o is increasing in a, so (a) < (a())) for all j.
First, let In (a) < Iii (a'). If = n then for j < n, yj = 0, and thus yn = 1. So
Imin (a) (1 qn (a)) (1 (a')) 2 (1 (a
Linin (a')
since s/n S 1, and we have a contradiction. Otherwise if t < n, let j > t. Then
(1 - {)(())) = Iini (a) < Imm (a') = (1 - ()() = yi J
< 1 (a)
< = y/ < v/j
(((a)
Then y = =1 Ui > 1 E, 1 v/j 2 V/. So
q((a)=1 + (1 (a))m (1 q( (1))))) (1- ((a))(a)))))
(:(a). < (l))()))) (1 - (a))))
0 (a)) < (l(a(a)- <o) ( <0
34

---

and we have a contradiction.
Now, let min (a)) 2 min (a') instead. If then x/ and
Min (a') = ςn (a') > @ (a) 2 2) (1) = mia (a);
and we have a contradiction. Otherwise if then for jonj< <1',
3j 2 4(aa)
q1(a)zz = Tini (a) 2 miin (a') 2=(''z² =
> = Ij x3> >
zj 21(a)
Then z/p = 1 --jEE 13y 13,=1= >1 Ejer Fjj 2 Tz. So
(e(a') + +(1 (1- - qr 1)1k" min (a') S min (ar qr (a)
= (1 - (a S qe (a)zz qu (a' )r' < q qu (a )z (1 (r ))22 ze (ge (a) q (a')) <
and we have a contradiction. Thus all cases result in a contradiction.
Lemma 8. min (a) is increasing for 1/2.
Proof. We first need the following Lemma, which shows that a S 1/2 implies that t(a.) must be an index at most halfway through the list of items.
Lemma 10. Ifa S 1/2, then t(a) s (n 1)/2.
Now, for 1 < n, define A(t) = fa t(a) t}. Since t(a) is weakly increasing in a by Lemma A() an interval in (0, 1), and ..) A(n) forms consecutive partition (0, 1). We will now show that T (a:) is increasing on each of the first [(z + 1)/2] intervals, which by Lemma 10 contain all 1/2].
Lemma 11. min (a:) is increasing on for) S 11/2.
Finally, we show that this implies Iin (a) is increasing on 0 < a I 1/2. Notice that [z y, a.) continuous in for each fixed y, so Imin (I, (r,y, miny I5 y, a)) is continuous in for each fixed v. y. Recall that - (a) = maxa.yEA, miin (z,y, a)) As the supremum of a set of must itself be continuous, this means that min (ar) must be continuous functions on compact
continuous in a, since An x An is compact. Since Liin (a) is continuous and is increasing on each interval (A(t))gg(++1/2 by Lemma 11, Jiin (a) must be increasing Urs A(t). By Lemma 10, Urs(n41)/2 A(t) 5 (0, 1/2]. So ! (a) is increasing on (0, 1/2).
Now, we show Lemmas 10 and 11. Lemma 10. Ifa a S 1/2, then t(a) S (n 1)/2.
Proof. By Lemma is enough show that for 1/2, f(a) S (n + 1)/2.
Suppose that a = 1/2 and we have æ, y of the form in Lemma such that f: t(a) > (n + 1)/2. If n is even, take t' = n//2 in the definitions of æj Vj in Lemma 5; if n is odd, take t' = (n + 1)/2.
We now verify that this results in z', y that are feasible solution to Problem and that satisfy
at = V/--+11- This is simple to see after observing that when 1/2, lj even n, L Ry T-9.
On (n-j+1. so for
I and for odd n. Le Rr, and simplifying.
Since by assumption ((a) yields the optimal solution, Imin (x, y) > mmin (x', (²).)) By the construction of solutions in Lemma 5, for all j we have (₁(x', y') Imin (2',2/) and 1 (z, = Imin (z, y). Then
35

---

for j oz = 1) > 15 .5) = gy 5o I. > Izy. Then since (F > (2 v)
u qt + (1 - qu Va
Σ 2
+ (1 ge W//
qr
qu
1 Σ zy
+11 q W/
jer
1 Σ Zj
qu
j<v
2 Fv
which is a contradiction.
Lemma 11. Tmin (a) is increasing on for S (n 11/2
Proof. Recall that for fixed
mii (a) = + (((a))((a) (1- (a)a(
It is sufficient to show that ge + (1 - 4: R4 is decreasing.
We first expand the expression:
(e(a))o(a) + (1
(()a)
- (()
jet (j(()
i>t (a)
Σ (((a)
jrn-t 1 - (a) + Σ - (((a)
Σ 1 q((a)
+
jat (((a)
K<jnn- 1 - (a(a)
Then
s(a) - (:(a))
(a)
- a))n--tt 0u, + (1 a)en-st1
at, (1 a)Un1++1
(1 (1-a) (n+
Un-t41 aU, + (1 - a a)Unnnitttt
Un-j+1 02hi + 01)
Un-141 Un-j+1 + a(u, - 1n-
Un-j+1 Un-141 + ax(i' Un-141)
So
Un-t+1 (Uj (oa-++))(ee ((n=)+)((nn-+1 + a(v - -))nn - (vx (n + Falt; (En-1+1 + aal 0n-141))
Un on-)+)))
o'(a)
Un-jt1
(vj - (h-j+1)(Unee (
+ - on- - (er (n + talu; vn-j+1))
= (v, - (h-j+1)Un-4411 (vr 1n-c-1)en-a41
UyUn-141 V1Un-j+1
< 0;Un-j+1 - U1Un-j+1
(j G>4m-j+1<n-i4
0
36

---

So is a decreasing function of a. Now, consider
Σ g:(a)
Σ (:(a)
- (1(a)
jet
jun-t
2((a)
1 1- (a)
Σ
9j(a)
(a)
++
ga(a)
1-1
(()
(i (i=n-j+1)
(:(a)
(n-i+((a)
1=1
(()))
1 1 (())
8j(a)
(
Then for ssist- 1,
h+(a) = 9: (1(())
1 - (((a)
9j (a)
1 - 4n (n)
au2 + (1 - a)un-j+1
034 + (1 0)
(1 - 01 0))
0U j+1 + (1 a1
at; (1 Un
(1 a)u
er(ary + (1 a) a)en--+)) +
+ (1 a)²))
0/ 03(00, + (1 an)n+++1)
=1 + (1 - a)vxvn- + 14
U/ (0u (1 11+)
Un リn-s+1 (1 - a)2 + 01p-1+1
=1 +
Bjy
at' + a)
Un Un-j+1
Ut + a a(nn vt)
=1 +
fj
Un-t+1 + a( Un-141)
So
(1(a)= Un-i+1
(Un-241 (Un + a(v (n-)+1)) (v. Un- a(Un-141 - v2))
(In-et1 + a(v 1=)
< (v. [n-++1)(Un-tH+ + -
(w un- +a 11:11-1-)) 0z))
= (t. (n-144)(Un-c++ + a(t - Un-141 + or + a(vn-e41 v())
(v. 1n=141)(1; kn-)+1)
< (v, (2-1+))
(1 S (n & n - 11
+
and he is decreasing in a for Sj Then Ej=1 ha(a) is decreasing, and g,Le + (1- Rz
E h,(a) ΣØ (a) decreasing, and Iin (a) is increasing.
E Proof of Theorem 4
Recall Theorem 4.
Theorem 4. If > and w and à are as described above, fairnes constraints can arbitrarily worsen the price of misestimation.
The price of misestimation without fairness construints is low: for all {vz}, there recommendation policy P that solves the misestimated problem U (0, w) so that
TH (0, w. w) S 2
37

---

The price of misestimation with fairness constraints can be arbitrarily large: Ve. there exists {fj} and recommendation policy ý that solves the problem U min (1, ()) such that
M U (1, 1 1 -c.
E.1
Main proof
Proof. We first find worst-case price of misestimation with fairness constraints, and then find the price of misestimation without fairness constraints.
Item fairness constraints with misestimation. First, notice that in the misestimated value matrix w there are three distinct user value types, and thus we can identify Symm with A and a policy P E Ssymm with vectors 2, y. where x is the recommendation policy for users with value di; U/j y is the recommendation policy for users with value Wij = -+- and & the recommendation policy for the mis-estimated users.
Let
= (r, E Ssymm: :. = Un-j+1, Rj An 2n-j+1 for all j}.
Since y is completely determined by x, we can identify S' with A and can identify E S' simply by x. z.
Lemma 12. I policy p= (I, y, 2) Symm solves Umin (p) = Umio (1), then there is some policy p' ='= 2' E S' that solves Uniu (p') U (1).
Applying the framework in Proposition 1 to this proof with S S' and using i as the user and item values, we reduce the problem to finding
arg
max 2. -
X
(11)
subject (x( = Vj,
and showing that this @ unique.
First, we use an analogue of the sparsity result Proposition 2 to show that the optimal x, has the following sparse structure.
Lemma 13. Let x. be an optimal basic feasible solution to the linear program Problem 11. There
some j S = such that for all j' j. 3zz' and for all j' j. Zz' Zn-j'+1 0. Let the pivol index I denote the minimum such j-
This sparse structure implies uniqueness.
Lemma 14. Problem Il has a unique optimal solution.
We can now describe what this solution (z. looks like.
Lemma 15. Let (I, 2) be the optimal solution to Problem 12, and let be the pivot element of (x, 2): suppose that t # n+1. Define 2
L Σ
jet 4i
Then
2,g + 1/2(1 - 2,3)
A
1 L1L1 1/2(11 2t)
0
jzt
2ÿ
(n 2t)
1
jE (t,n-t+1]
1-20
Finally,
jct
23 =
Lu
j =t.
23
0,
j j>t
38

---

Ift = n+1 then a remains the same, but 2, and
25q. + (1 (1-23) 23)
1+ gcLe
If we try / = 1 and obtain 21 < 0 above, can conclude that >> 1. Suppose / = 1. Then L, 0, 80
X 23q + 1/22(11 23)
1+ 1/2(n=12
and
1
2.q1 1/2(1 23)
2,3q1
21 2
1 1- (n 2)
1 (n 2)
23
1 2/3
4/2
n
7
1 2
Then t= = 1 and
< 0 if and only if
2
2,8g1
Un
2
< 0
1.
n then "²
2,3
01
1/288
since
01
Fi t
If 8
2
2
11 - 2
1
4/2 1
2 n1
11
1/28
So if B > 1, 1 and 2 2n 0. In this case, regardless of whether mis-estimated user has
Wi1 = or Win = v1, that user will never be recommended their most preferred item.
Moreover, no matter the true type of the mis-estimated user.
U2(2, 2) =
Σ U22 1SjSh
=
1
Σ
2z2g
0/2
Σ
2j
0/
U1
|Kjs<n
1<jen
Thus if 02 ee, then
<)
Taking ğ to be the recommendation probabilities induced by this pair x; 2, this implics that Uniu (p) < e/n.
Item fairness constraints without mis ettimastintaion This becomes precisely the problem we solve in Theorem 3; if the two types occur in equal proportion in the mis-estimated group as well as the correctly estimated group, then a 1/2.
If a = 1/2, then by Lemma 17 with 8 = 1, 1 = | J. and we can show that
L R₂ ge even
Pr,
nodd
By Lemma we know that
I min 1 qeLe + (1 Rs
so if n is even, we have
1
1
I + (R, - 1) +1 - R.
R₂
Es>t 1-4;
1
2(n - (nn22) 7
where we use the fact from Lemma that if j at1 then Oj }. Likewise if n odd,
1
1
Iiin 1 Re + (1 R. 1+ R.
I+E T-
(n + 1)/2) + 2(n
Then user of type will have normalized utility will be
U,(2,)) (z
21
I
I I
+
minn
1
U1
91
Un
n
Similarly a user of type will have utility
Un
-
U1 + Un
U, y) >
Jinn
>
21
1
Gn
Un
min
71
This means that U (1) 1/n.
39

---

Price of estimation with item fairness constraints. The two arguments above imply that
Uni (p, w)
Tf (1, w. 20 =
Unn (1, w)
e/n
1
1/n
1
Price of estimation without item fairness constraints. In this optimal recommendation policy may choose each user's policy individually without regard to item utilities. Given the mis- estimated values, it is optimal give mis-estimated users the item j -j that maximizes "itin_ith deterministically. is thus also optimal recommend the item j and n j + each with probability 1/2. This yields expected value
+ Un-j+1
21
+ Un
11
max
2
2
and thus mis-estimated user i will receive normalized value of U:(p') 1/2.
The optimal utility each user their preferences were correctly estimated is 1, so the price of misestimation is 1/2.
E.2 Supporting lemma proofs
First, we show fact that will be helpful later on.
Lemma 16. ifj < 2+1 then qj 1/2: if
m+1 2
then Oj 1/2 Ifj
n+1
2 .9
1/2
Proof. j < n+1 then Dj > Un-j+1 and
Uz
1
91
Uj Un-j+1
86-1+1
1+1
2
j < #+1
2 then tj < Un- and symmetric argument holds.
If = a+1 then U = Un- and thus q, = 1/2.
2
In the remainder of this section, we will use rev denote the reverse of vector x, that is, rev(r), = In-jt1 for all j.
Lemma 12. If a policy p (I, 2) Saymm solves Umiu (p) = U (1), then there is some policy x', x' E S' that solves Umin (p') min (1).
Proof. Suppose (z, 2) = is an optimal solution to U (1)-
First, if min (1) (p) for some in the first second type of user
Let p' = xx' v z' where 2'j = Vn j+1 = (xx + yn vn-)+1), and 2/J = [ + 2n-j+1.
1,0 s 2/, 2/1 $ for all j. Then clearly p' E S', and E, r ビソ ス 1,
Furthermore, for users i, of the first and second types respectively with correctly estimated types.
U,(p')= = Eo (r, + Bn----1ee +(pp)UU((0 min(U.(p), (p)p) 2
and by an analogous argument,
Uy 2 min(Ui(p)),u(())
40

---

Moreover, the estimated normalized utility of mis-estimated user i, will be
U:(p') = Σ
Di
+
Dn-s+1
2
==1
1
Vj + On-j-11
+
Un -+-
2 jml
Rj
+
2n
j+1
2
2 (Vi(() + U.((D')
U.(D')
So min; U:(p') 2 min; U((p).
Finally, for any j. we can expand the definition of 15 to see that
1,(0') = 1 (4,(0) - (n- = Imiu
Thus pf is also optimal solution to Problem 1.
Lemma 13. Let x, an optimal basic feasible solution to the linear program Problem 11. There some j S 2 such that for all j' j. Tiz' and for all j' j. Zz' Zn-j'+1 0. Let the pivol index & denote the minimum such j-
Proof. Part 1. While is tempting attempt to directly apply the sparsity result in Proposition 2 here, we will need slightly stronger result to ensure that there are no j such that Iz 2ÿ O. First, we must show that 2z > 0 and yj > 0 are almost mutually exclusive.
Lemma 17. Let (xx, 2) be optimal solution Problem 11. For >
n+1 Tj 0.
In particular, if we let [ indicate the index halfway through the set of items, this means that we can simplify the problem above to
arg max F1....fh.
subject
1,(2,2) -,, h
(12)
Σ マイーー
-
Σ
2j + Σ
An-j+1 1
iSh
ihh
hejšn
2j 2.
Now this a linear program with 2/ + variables and h+2 constraints, so by an argument analogous to Problem 12, find that every basic feasible solution Tich 21:h must share h zeros. This means that there is a single index t such that Ø; > 0, 24 > 0; if there were more than one, by the pigeonhole principle there must be some t' < h such that Ze 24 In-F+1 0, and I (z. 2) 0. Then Imin (x, 2) O; however, by Lemma 1, Imin (x, 2) = I >> 0, so we have contradiction.
In terms of z.
[z(x,2) 2) = BegKz + BUn j+ + 2,3) S1t 2j
2
Beg + BUn-5++1 + (1 - 2,3) 2 tun-
Beszy + Bun
1 BUn-j+122
j+1 + (1 2,3) vn- 2j
Y bn-
Un-jt1 In-jtt| + (1-1101) 223)2
= 23
Tz +
0ú + Un Un-
Uj Un-jt1
41

---

Vi Let q3 25+
Note that jj does not depend on B, and q, is decreasing in j. Then
1,( 2/3 (g + (1 43 ());;) + (1 2.3)2.
Part 2. Moreover, the set of such that zj = 0 is contiguous; similarly for 2j.
We prove this by contradiction, showing that if this set is not contiguous, probability mass until we achieve greater than optimal item fairness. Let i < j Σ h, and let æ; & be an optimal solution Problem 12. We need to show that if x; 0 then Iy 0, and if 2 0, then
move around
2j > O.
Suppose first that 2ū 0 and 3z > 0. Notice that since are optimal,
(1 = [x 2) (2, 2) = 23 + (1 -2
Define
Tj
t=i
2j. f f=
x/.
+ h-1
e=j
2/
Zis t=j
It + I-II
otherwise
Zgg otherwise
for small enough that x' Ah-1. Now for all l (i,j), Te(x',=') [r 2). since have increased the probability mass on zy while leaving žς unchanged. Furthermore,
4(2',2')
23q (z, - (1-28)2;
2 9z)2z + 25 + (1- 1 23))2 - 2.qrc
2,((g: - q3)æ + (0)); 223qE
-4(I,2) + 23(4: 9;)22 - -,8q.
(1,,2)
as long as < (9i-9) - kg, which we can ensure by taking small enough, since > qj. Moreover,
1,(x', = 23gj
I4 + h-1
+ (1 - -28)24
= =23gg
83 + h-
+ +2,8q.I, + +(1 (1- 28))
> 28 + (1 - 28)22
())
Thus
miin (x',²) min Tx(x,,²/) > min Te(x,, 2) Jmin (x,, 2) Iin
and we have a contradiction.
Similarly, suppose that 2, and 2j 0. Then since x, = optimal, we have
28qar; + - (1-2)))z 1(x, =) = 1, (x, 2) = 23gz
(13)
Define
C
{=j
Ij 8, f=j
2/
Zj + h-1
f=i
x =
I + 8,
f f=i
+
T
otherwise
It.
otherwise
for 8
1-29 and taking small enough that o' An-1 and e < 2/(1 9//4:). This implies
23g.
24
that
2-
(1
2,3 c)
24
2,9q;
2,3g;
42

---

Now
1-29
22 + 8 = T; +
28g
(2,9g3;
23)
2,q
1
2
(13)
2,q
4i 3ij
qi
< Ijj
(g < q))
S
and
(1 11-220 (2) c)
2j - 8> Dj
28g.
(2,3g00 - (1 - -2,)) - c))
259
(25qg (1 22)))ss)
23gg
(23gz (28ggæz, 23gg2;))
(13)
2,gg
2.3g.1
2,gg
00
and x; + v4 0, Fj 8 < xz so x' Ah-1.
Now as above Ie(z', z/) > Imin (z,2) for all & {i,j}. since there is strictly more probability mass on 22 while remains the same. Furthermore,
[,(,' x²) [e 2) = 2, + 5) + (1 (2) + h h-1
6 -288g + +(1 2.9) 2;)
2zq + 8) (2,q,zz + 235)z))
25qq0 - (1- 23)
28g: (1 25)
25 - 233)
2,gg
0
and
I,(,'22) (5, = (2) - -) (1 +1 -28) -)) -23g,
= (1 - 28) - - -239,8
> (1 - 23) - -c) - 239g (13)) -e)
2,3g
=0
Then
mmin (2',²') = min (x',,2)) > min =) mmi (x, 2) = Iinn {
8
and we have found x', x' achieving a higher-than-optime Imin which a contradiction.
Lemma 17. Let (xr 2) be an optimal solution Problem 11. For
3j 0.
Proof. We prove this by contradiction. Suppose that for j > n+1
2 Tij 0. Then define x' such that
0,
{=
x/6
In In-jt1 + (Iz e) {= +1
Ft + n-2
43

---

where 0 <e << (2qn-5+1 - 1) Since j> nt1 a > 1/2 by Lemma 16, so such exists.
Then for all l & (i.n - 1}.
[e(x',2) 23 (qet' + (1 qe n0)====++1))11110 -1--13)) 111-230
> 23 (qiIt + (1 - qt In) e+ 1) + - -23)2z
= Tt(2,2). 2).
Since e < (2qn -41 1) we can rearrange to see that (1 - -n- < 9n- c). This
implies that
1n-j+1 (x', 2) 23 (() (1-33))
23 (in-jt1nnnttt (o- (1-2,)) 2n-j-1
2 2n
23 (gn-st1Un-st1 220-))))22010-11-100 (1 23) ž
In -n-
and
1,(a,, 2) 2/ (4g 0+ (1 91) (c; ()) -1-25)
23 (In-jt1In-jt1 + (
28)=
(qn-j+1 = -gp)
> 2 (1 +1 23)
23 ((1 +
-1 93)
[,( =)
Thus have found a solution x', z that satisfies
minn (x' =) min T (x',, > min T, 2) mmin (x,, 2) Iin
and we have a contradiction.
Lemma 14. Problem 11 has a unique optimal solution.
Proof. Suppose (ar, 2) and (x', z²) are both optimal basic feasible solutions to Problem 12. Let / be the pivot index of 2) and 1 be the pivot index of (a', 2²), and suppose without loss of generality that < t'.
First, i <t, then for all < 2j z/} 0, and
28qzzz = 1z(x, = Amin (z, z) = mmio (a', (z',z') = 15(x²,²²) = 2,9q,a
80 2. = If 1, æ. 0. For j = t, 2 0 and
2. + (1 - 23))z 2.qg.a
= 2,99
1 Σ 3j
+ + +11 2.3q
jet
2,94
1 1 Σ o
+ + 23) 2,3
jCt
- 118)22 2,89t
Σ 001 -
jst
But - 21-28) 2 0, so Ejsea' 1 and for j > x/j
This implies that L < i, which is
contradiction, is not possible for t' >
Now, ift =t, then again for all j < t, 2j = o/ =0, and xjj = xzy. For t < Ki if t h,
$ h 2ÿ = 2/j = 0 and
(1 1--230 28)2, 1x(222) mmnn (z, 2) Imin (x', x') ( ,²) 2
44

---

so 2j = zj. Finally,
= -1- Σ
2j = =1 Σ 2nj x/
JCL
and
(1-221s -11-Essssh
ssjsh 2/) = (2 - - zj) = =//
11 even
24
(1 1 -'tejeh 2j 2n) 21 2 2l<jch 2/2 2hh 2/2
odd
If h, then 21
z/.. Thus (z, (
Thus there only one optimal basic feasible solution to Problem 12, and thus only one optimal solution by the fundamental theorem of linear programming.
Lemma 15. Let (a, 2) be the optimal solution to Problem 12, and let be the pivot element of (r, 2);
suppose that t + a+1 Define
L Σ
1
jEL 9j
Then
23g + 1/2(1 - 2()
A
1 q1l1 + 1122(n - 2t)
0
jel
2g
(n 21) 21) T-23
jE 11+1-1+1)+
t t<j<n-tti
1-28
Finally,
jet
2391
Lts j=t.
23
0,
j>t
Ift n+1 then x remains the same, but 21 and
23q. + (1 - 2,)
A
1 1 gche
Proof. For all j < x, 28qjaz, 20
A_ Moreover,
28g,
A
3t = Σ
1j =
La-
2
23
j<l
j<t
Suppose that n is odd and that t = h = Moreover,
n+1
Then 24 = 24 must be 1 since for all j < h 2j = 0.
2
= 2, + (B-2 = 239 (1
23 L1 + + - 2.3)
rearranging,
23q. + (1-28)
1 geLo
Otherwise, <j h, -1-223)2 20
Then since Ejsh
Enejsn 2n-jt1=
1-23-
2,
1
Σ
2j
2j
Zn Zn-j+1
Σ Zn-jt1
jct
Kojh
hejen-t11
jon-tt1
1
Σ
2j
Žn-j-1
(2j 0 for j < I)
KjSh
hejen-141
A
1 1
(n- 2f)
2
2,3
45

---

Moreover,
= 23 + (1 (1-23)) -2))2 = 23q (1- x
23 23L4) + +11 1 (n - 21) 1 23
Rearranging,
X(1 + qe + 1/2(n - 21)) 2,9q + 1/2(1 2/3),
so
2,3g, + 1/2(1-22 - -33)
+ gcL + 1/2(n 2t)
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We believe the abstract and the introduction provide an accurate overview of the contents of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations in Section 8.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
47

---

For each of our main theorems, we provide detailed description of the modeling assumptions prior the theorem. We provide complete proofs of each theorem in Appendices C, D, and E.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide our code and thoroughly detail our experimental setting.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
48

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: In the introduction, we provide link GitHub repository containing the code we used to train our recommendation engine and run our experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/gue Coaeee//ooSSuubisii.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: htpplli/gguideie gww.guudee//eee wttpeeeSuumssssoooooooooooo
/ wwwpcc/cpppccceeeeeeeeeeeeeeeele
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide detailed description the training and evaluation of our recom- mendation engine in Appendix B. We describe the training procedure in Appendix B.2, and the evaluation in Appendix B.3.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In Appendix B provide thorough evaluation of our recommendation engine including; quantities are reported with P-values and standard deviations where appropriate. We also show error bars on the experimental plots and discuss how they were obtained.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
49

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide this information in Appendix B.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: ttttpp:///eeurre /wwrrpuu....///
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss this Section 8; since our paper is investigating potential negative social impacts of technology, we anticipate a positive social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
50

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the models and datasets use and provide license information in Appendix B.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
51

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. conddatasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release code train and analyze the recommendation system that develop, and provide documentation with the code.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
52

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "k63nJ59PdH", "reviewer": "Reviewer_yH5N", "summary": "This paper develop a theoretical framework to analysis the trade-off between user fairness and item fairness. From the theoretically analysis, we understand that diverse user population benefits the recommendation, and users whose preferences are misestimated can be disadvantaged by the constraints on item fairness. The conclusion makes sense and is useful.", "questions": ".", "limitations": ".", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "Clear definition on user fairness, item fairness, item utility constrained user utility, price etc. Good analysis on the two conclusion.", "weaknesses": "Relatively easy setting, e.g., only one item is recommended to a user. While the author honestly pointed out these weaknesses in the last paragraph, these weaknesses are acceptable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our work! We agree that only recommending one item is an aspect of our current theoretical model. We note that recommendations being probabilistic (e.g., one can think of an item being sampled each time period) somewhat mitigates this aspect, though agree that more explicitly modeling recommending multiple items (and how users select between them) is an important consideration for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H7IuEvE5Wf", "reviewer": "Reviewer_3QdJ", "summary": "This paper investigates the trade-off between user fairness and item fairness in recommender systems. The authors develop a theoretical framework to characterize the user-item fairness trade-off by analyzing the recommendation strategy optimization problem. The following phenomena are found: 1. The more diversified the user preferences are, the smaller the user-item fairness trade-off is. 2. Inaccurate estimation of user preferences exacerbates the fairness trade-off, especially for new users. 3. In real data, moderate item fairness constraints have a small effect on user fairness but very strong constraints can significantly reduce user fairness.  Overall, the theoretical derivation part of this study is brilliant and provides theoretical assurance for the framework. It is a worthy study to explore the fairness problem of recommender systems in depth.", "questions": "1. The paper assumes that the utility of users and items is symmetric, which may not always hold in reality. How does this assumption affect the generalisability of the results?\n2. In this paper, fairness is quantified as the minimum normalized utility. This definition is supposed to follow Rawlsian fairness. it is not based on group fairness? fairness in this paper is measured using individuals. I am concerned about this because there are a large number of users in a recommender system and individual users may not be representative. I would like the authors to explain my concerns.\n3. The selection of scenarios in the experimental section is limited, and the experiment on arXiv recommender systems, while meaningful, may not be sufficiently representative of all types of recommender systems. The generalisability of the results of this experiment could be discussed, or additional experiments in other domains could be considered.", "limitations": "1. Simplification of model assumptions: It assumes symmetric user and item utilities, which may not always hold in reality. It only considers the case of a single-item recommendation, whereas real systems usually recommend multiple items.\n2. Limitations of the fairness definition: it focuses mainly on minimized fairness metrics and does not consider other possible fairness measures (e.g. group fairness).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The trade-off relationship between user fairness and item fairness is systematically analyzed for the first time.\n2. A new theoretical framework is proposed to simplify complex optimization problems.\n3. the theoretical analysis is rigorous and provides in-depth mathematical proofs.", "weaknesses": "1. Limitations of the definition of fairness: the paper focuses mainly on minimized fairness indicators. Have other indicators of fairness been considered?\n2 No specific methodology is given for actually achieving the three balances\n3. The thesis assumes that the utility of users and items is symmetric, which may not always hold in reality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback; we believe addressing them makes for a stronger paper.\n\n### Fairness definitions\n\nWe agree that it is important to study how our results extend to other definitions of fairness. In the main response, we give further justification for our choice, and show experiments demonstrating that our diversity result generalizes to Nash welfare fairness, $\\sum_i \\log(U_i(\\rho))$. \n\nWhile still being an individual fairness measure (in considering fairness to users as individuals rather than as members of a certain group, which is outside the scope of our paper), Nash welfare incorporates a term from each user in the sum, resulting in a more holistic measure of user fairness. We hope this new experiment addresses your concern about representation and generalizability. We think that extending our results theoretically for additional definitions of fairness is an interesting question for future work.\n\n### Achieving the three balances\n\nIt is true that our paper does not provide a novel efficient algorithm for achieving multi-sided fairness (besides our reduced optimization problem); this is an interesting technical problem that has been explored in related work [4,10,11]. Our work complements these papers: we provide conceptual insights into the tradeoffs between user and item fairness. This is especially important for work like [11], whose algorithm needs to set hyper-parameters for the strength of user and item fairness constraints; setting these values appropriately requires understanding how and whether the two objectives trade off in the deployment setting.\n\n### Symmetric utility\n\nIn the main response, we provide experiments showing that the diversity phenomenon extends to settings where user and item utility are not symmetric, and further explain our reasoning for choosing this simplification.\n\n### Single-item recommendation\n\nWe agree that this is a limitation of our framework, and discuss this in the limitations section. Our intuition is that since in our framework the platform selects probabilistic policies, increasing the number of items will not affect the solutions qualitatively as much as a discrete policy would. We believe this is an important but difficult question for future work; one challenge with considering multiple items is modeling a tractable choice model that allows users to choose multiple items from the set of recommended items.\n\n### ArXiv experiment generalizability\n\nThank you for this suggestion; we will add a discussion of the generalizability of the experiment to other domains.\n\nThank you for your consideration of this response!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IwYJKK82Lg", "reviewer": "Reviewer_rEVK", "summary": "The paper works on the relationship between user fairness and item fairness in recommender system settings. A theoretical framework is proposed and some theoretical results and intuitions are provided based on the framework. The main results are the tradeoffs between fairness and 1) uncertainty and 2) diversity where theorems are proved together with some discussions.\n\n---\n\nI have read the rebuttal and other reviews. My rating is unchanged.", "questions": "I think the platform-level utility is missing from the discussion? In practice the platform controls the recommendation algorithm and therefore they may favor their utility as the primary objective.\n\nThe default for cold start user may not be the average of existing users, but selecting top-performing items. Suggest to consider this aspect in the revision process.", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like this paper. The theoretical framework is clear and useful. I expect more results can be derived out of this framework in the future e.g. assuming the utility w_{ij} is an estimator with certain bias and variance, or in practice one may not achieve the global optimal \\rho^* but with a gap. The main results lie in theorem 3 and 4. Both results seem valid and intuitive. They illustrate how the price of fairness is changed when other factors like diversity/uncertainty are part of the consideration.", "weaknesses": "The empirical part on arxiv is quite light. I see more details in the appendix but the main body part needs more information to make it self-contained. In the theoretical framework part, I would make the setting more comprehensive but put additional assumptions in later sections in order to support those theorems e.g. I think the current setting is for a single-item recommendation problem and all users are independent. There will be correlation terms for different items when multiple items are shown to users together. In addition, the paper focuses on individual utility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and suggestions; we are glad you like our theoretical framework! We agree that there are likely to be other applications of the framework, and we are currently looking at ways to further draw out and interpret the sparsity result in the writing.\n\n\n### Empirical details\n\nWe will move more details from the appendix into the main body as you suggest for a more self-contained description.\n\n\n### Theoretical framework generality\n\nThank you for your comments regarding the theory writing. We agree that one possible writing approach is to introduce a general model and then later introduce the necessary assumptions. We will consider such a rewrite, though also would like to make our assumptions clear early. \n\n\n###  Platform-level utility\n\nOur main goal was to understand the interplay between user and item fairness. We agree that platform utility  is a key follow-up question and include this in our list of suggested future work; this question is partially explored in [11], where they look at how the platform’s revenue trades off with fairness. We expect our diversity and mis-estimation results to extend to this setting. For example, with diverse users, giving every user their favorite item is optimal for users, items, and likely platform revenue as well. \n\n\n### Cold start user default\n\nThis is an interesting suggestion. We will try to model this and see what insights our framework gives for this case. We note that this choice partially occurs with our current framework without fairness constraints, since items that are generally popular will have high expected utility. \n\nThank you for your consideration of our response!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YaFSOcszMq", "reviewer": "Reviewer_t7QC", "summary": "In this paper, the authors studied the tradeoff between user and item fairness in a recommendation setting. They proposed a constrained optimization problem that imposes user fairness as its objective and incorporates item fairness as its constraints. The authors also identified that (1) when user preferences are diverse, item fairness can be easily achieved; (2) when there is mis-estimation of user preference, imposing item constraint can lead to further cost for the users. Finally, the authors illustrated their findings using arXiv data.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "- The problem of multi-sided fairness is an important problem, but most existing literature focus on studying single-sided fairness. Understanding the price of fairness is a meaningful problem for decision-makers in practice.", "weaknesses": "1. The model and framework used in this paper would require significantly more justification. More specifically, \n- It is unclear why the authors choose to consider an optimization problem which maximizes normalized user preference as the objective subject to item fairness constraints. To me this is a rather counterintuitive choice and requires more motivation. Why not solving a dual-objective problem and treating user/item fairness in the same fashion? Alternatively, why not maximizing online platform's recommendation quality?\n- The assumption that user and item share the same utility $w_{i,j}$ is too strong and can hardly hold in practice. In recommendation systems, a number of factors such as pricing, rankings, utility models, etc., could impact the item/user utilities in different ways. (See prior works such as [10, 11, 32], all of which use different definitions of user/item utilities.) \n- The fairness notion that the authors adopt for users/items resemble a min-max type of fairness notion. This is again quite restrictive and requires more justification. Does your framework and results hold under alternative notions?\n\n2. The theoretical results of this paper do not have sufficient technical contributions. For example,\n- Proposition 2 basically uses the properties of BFS in LPs. \n- Theorems 3 and 4 are only shown on a restrictive example (where there are only 2-3 types of users with opposing preferences in a pre-defined form). This raises the question of whether the theoretical results/insights can be extended to more general setups. Due to the restrictive setup and assumptions, the insights might also not have much practical relevance.\n\n3. The price of fairness of multi-sided recommendations is a topic already studied in prior works. The insights provided in this work are not particularly surprising, nor distinguishable from prior works. \n- For example, in [11] the authors also studied price of fairness and show that the price relates to the misalignment of platform/item/user objectives and designed an algorithm that resolves the issue of having unknown user/item data. \n- The phenomena described in this work, such as more diverse user preferences naturally inducing item fairness, is also rather natural especially when min-max fairness is imposed, which encourages uniform item exposure. I'd expect such statement would fail to work if a different type of item fairness is considered. \n\n4. No algorithm has been studied or introduced in this work. The empirical study of arXiv data merely serves to evaluate Problem (1) on arXiv data, but the model and framework itself already raises questions and requires extensive justification. \n\nOverall, I think this work would require significantly more work in both its model and results and would recommend rejection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We hope that the additional experiments we describe in the main rebuttal as well as the justification provided below address your concerns.\n\n### Constrained optimization justification\n\nWe agree that we could have modeled this as a dual objective problem – constraints at varying strength versus objectives with different weights are often interchangeable. We believe that our choice is reasonable, and using fairness constraints rather than objectives is consistent with related work [11]. We agree with reviewer yH5N that user and item fairness are not necessarily equally important in practice, and note that this could be captured by the dual-objective framework suggested by reviewer t7QC by using different weights on each objective.\n\nWe will update our text to clarify this justification.\n\n### Symmetric utility assumption\nThank you for this feedback! \n- In the main response we provide experiments showing the robustness of our diversity result to alternative item utility models. \n- We also provide additional justification for why it is reasonable to restrict our analysis to this model: it is necessary and common in related work [10,32] to assume a specific utility model, and we believe a symmetric utility model captures a fundamental characteristic of producer preferences in many recommendation settings better than alternative models. \nWe give more detail for these positions in the main response. We hope this addresses your concerns!\n\n### Alternative notions of fairness\nWe agree that other notions of fairness are also interesting, and re-ran our experiment in Figure 1(a) with Nash welfare as our definition of fairness for users and items, and see qualitatively the same results. We include an additional discussion of these points in the main response. We believe extending our theoretical results to additional definitions of fairness is an interesting question for future work. \n\n### Insufficient technical contributions\n- We agree that Proposition 2 is mainly a result of using BFS properties: we included it as a separate result because it has an interesting qualitative interpretation.\n- However, we respectfully disagree that our work is not sufficiently technical – one challenge is to transform our problem into a setting where Proposition 2 can be applied, and then using the result for our conceptual findings. Proposition 1 provides a framework to transform the complicated program into a much simpler program. The proof involved manipulating the problem in a sequence of non-obvious ways. We then found closed form solutions to the transformed problem in Proposition 1, which was also non-trivial.\nWe agree that the question of whether our results extend to populations with arbitrary preferences is crucial, and this was the intention of the experiments with arXiv data in Section 6. We hope that these experiments address your concerns, and agree that finding more general theoretical results is an interesting question for future work.\n\n### Prior work\nThank you for pointing this out! \n- [11] indeed defines the price of fairness, but in a different way from us: they examine the price of imposing fairness constraints on the revenue, thus capturing the impact of item/user fairness on revenue, while we examine the price of imposing item fairness constraints on user fairness, thus capturing the interplay between user and item fairness. \n- Moreover, their concept of objective misalignment (the difference in fairness between the {item, user} utility required by the constraints, and the {item, user} utility in a revenue-optimal solution) is not the same as our concept of user preference diversity (agreement between users' utilities). User preference diversity may *cause* objective alignment, but it is a different concept.\n- Their algorithm focuses on the algorithmic question of how to impose fairness constraints when preferences are unknown, but their analysis does not answer our question of whether fairness constraints disproportionately harm users with unknown preferences.\nWe will update our related work section to make these points clearer.\n\n### The diversity phenomenon is natural, and will fail with a different fairness definition.\nWe agree that this phenomenon is natural, but disagree that it only would hold in a max-min fairness definition. Moreover, as mentioned above, we re-ran our arXiv experiment that demonstrated this result in the setting of Nash welfare fairness and saw the same effect (see Figure 3 in the PDF)\n\n### No algorithm has been introduced\nSeveral algorithms have been developed to ensure multi-sided fairness in the existing literature [4,10,11]. The aim of this project is to understand factors affecting the trade-off between user fairness and item fairness. For example, in the algorithm in [11] the platform must choose the strength of the user- and item- fairness constraints. What constitutes a reasonable choice for the relative strength of the constraints depends heavily on how user and item fairness trade off, and is an important question independent from the development of the algorithm.\n\nThank you for your consideration of our response!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their helpful feedback, and are glad that you found the paper “clear and useful” and the results to be both “rigorous” and “intuitive”. Multiple reviewers sought more justification for our **symmetry assumption** and **fairness definition**, so we discuss these issues here.

Overall, we appreciate the reviewer’s questions – there are always many ways to model this question, and the “correct” model often depends on the exact application. However, we believe that our primary insights are robust to the exact modeling choices, and that our choices are reasonable. 

First, in response to the reviews, we include **additional arXiv experiments** in the response PDF. 
- Figures 1 and 2 relax the **symmetric utility assumption** in the same setting as Figure 2 from the original paper, using exposure (and different levels of correlation) for item utility. The figures show that the diversity phenomenon is robust to this assumption, and that under different item utility models item fairness constraints still do not empirically increase the price of mis-estimation.
- Figure 3 shows that the diversity phenomenon is robust to **different definitions of fairness** by modifying the experiments of Figure 2 in the original paper to use **Nash welfare** [43] to define fairness. We also see the same phenomenon when we use the sum of the $k$ minimum participant utilities (which is a smoother extension of max-min fairness), with $k = 3$.

We will update our manuscript to include these experiments, showing that our results do not exactly depend on our theoretical choices.

Moreover, we believe that our restriction to symmetric utilities and minimized fairness for our theoretical analysis are reasonable choices for the theoretical analysis.

**Symmetric utility.** Our model assumes that users and items share a common utility $w_{ij}$ for recommending paper $j$ to user $i$. 
1. **Extended model:** We would like to draw attention to line 1092 in Appendix E, where we provide an extension of our model in which user and item utilities are only assumed to be *proportional* to some shared value (that is, when item $j$ is recommended to user $i$, $i$ and $j$'s utilities are $\alpha_i w_{ij}$ and $\beta_j w_{ij}$ respectively for some $\alpha_i, \beta_j > 0$). Our theoretical results hold in this extended setting.
2. **Prior work:** Fixing a particular model of item utility is consistent with related work, as this is typically necessary for theoretical analysis. We use $w_{ij}^I = w_{ij}^U$, which resembles the "market share" utility model in [11]. *Exposure* ($w_{ij}^I = 1$ for all $i,j$) is also a popular choice [10,32] for this model, as we do in the new empirical analyses.
3. **Simple models:** As pointed out by the reviewers, neither model can fully capture the nuances of producer preferences. However, we believe that the symmetric utility model reflects a basic structure behind producer preferences in many cases ("items prefer to be recommended to users who like them, as that predicts consumption/purchase"), and that our theoretical findings should extend to settings with more or less this structure.
4. **Symmetry vs exposure:** We argue in Appendix E that having user and item preferences depend on a common value such as a purchase probability or click-through rate to be a more realistic representation of producer preferences than exposure in many cases. For example in an online marketplace a producer prefers their item to be recommended to users who are likely to buy their product, and in the paper recommendation setting an author prefers their paper to be recommended to a reader who is likely to engage with their work. This type of preference is not captured by exposure but is captured by the symmetric model.

We will update the writing to discuss these points, as well as alternative approaches.

**Minimized fairness.** Our model defines fairness as the normalized utility of the minimum user.
1. Min utility is a common notion of individual fairness in algorithmic fairness (called Rawlsian or egalitarian fairness); other reasonable choices include Nash welfare, which we now include in our empirical analysis ($\sum_i \log U_i(\rho)$, $\sum_j \log I_j(\rho)$ for users and items respectively; see pdf). We agree with reviewers that generalizing to other definitions is interesting and leave a theoretical extension for future work.

2. We expect the results to extend beyond this choice. One intuition for our diversity result is to consider the most user-diverse population: a population where every ranking of items is equally represented (and there is a consistent mapping from rankings to utilities). The user-optimal solution of giving every user their favorite item is also optimally item-fair for any reasonable* definition of individual item fairness, so there is no tradeoff. This intuition (and others) is independent of the definition of fairness, so we expect our results to generalize (and indeed they appear to do so in the new experiments in Figure 3).

*since it assigns all items the same utility and maximizes the total item utility.

Note: In this and the individual responses, we use the numbered references in our paper to refer to related work. For our experiments using different definitions of fairness, we add the following citation.
[43] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The Unreasonable Fairness of Maximum Nash Welfare. ACM Trans. Econ. Comput. 7, 3, Article 12 (August 2019), 32 pages.

Meta-review: This paper investigates the trade-offs between user and item fairness in recommender systems, a crucial yet under-explored area. The authors present a novel theoretical framework and validate their findings empirically on the arXiv dataset, leading to valuable insights into fairness dynamics in recommendation.
Reviewers overall appreciate the paper's clarity, the importance of the problem tackled, and the rigor of the theoretical analysis. The identified phenomena, particularly the role of user diversity and the disproportionate impact of preference mis-estimation on fairness, are novel and hold significant practical implications for building fairer recommender systems. However, Reviewer t7QC raises several valid concerns regarding the paper's theoretical setup, specifically questioning the choice of fairness definition and the strong symmetry assumption in the utility model. While the authors have partially addressed these concerns by incorporating Nash Welfare in their empirical analysis and providing some justification for their modeling choices, a more thorough discussion and potential relaxation of these assumptions would significantly strengthen the paper.
Despite the limitations pointed out by Reviewer t7QC, the paper makes a valuable contribution to the field through the theoretical analysis and insights, and some practical relevance of the experiments. Therefore, the paper is recommended for acceptance. However, the authors are strongly encouraged to consider and address Reviewer t7QC's concerns in their final version of the paper -- specifically, discussing the limitations and exploring potential impact of alternative definitions on their findings, and providing a more thorough justification for the symmetry assumption in their utility model while discussing consequences of relaxing this assumption.
Decision: Accept (poster)