User-item fairness tradeoffs in recommendations

Authors: sophie  greenwood
sudalakshmee  chiniah
nikhil  garg
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:34:08

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.

Main paper: 
 introduction: 
 Recommendation systems are employed throughout modern online platforms to 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 in disparately poor outcomes for some items, which may not be most preferred by any user [42] . 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, 33, 46, 48] . However, by not solely optimizing for user engagement, these techniques impose a 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, 45] . 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 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 fairness constraints.However, an open question is, what are the implications of such algorithms on the recommendations, i.e., what do multi-sided constraints do, and what is the price of (multi-sided) 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 "fairness" 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 [38] , 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 in 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 a 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 fairness is formalized as an objective on the minimum normalized utility provided to each user -and item fairness constraints determine the problem's feasible region, through the solutions of another concave optimization. This formulation qualitatively captures standard multi-objective approaches for user-item fairness [5, 12] . We show that when item fairness constraints are maximal, the solutions to this optimization problem (recommendation probabilities for each user) have a 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 to characterize user-item fairness tradeoffs. We identify two phenomena: (a) "free fairness" as a function of user preference diversity: if users have sufficiently diverse preferences, imposing item fairness 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 on whom the platform has no data) typically receive more inaccurate recommendations; we show that this effect may be worsened with item fairness constraints, in a 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 to 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 on 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 fairness" 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 is available at this repository. 
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 n items. Let w ij > 0 be the utility of recommending item j to user i; this could represent a click-through rate or purchase probability. We suppose that user-item utilities are symmetric: each of the user i and item j receives utility w ij from being recommended item j.Let ∆ n-1 denote the simplex in R n . The platform's task is to choose a recommendation policy ρ ∈ ∆ m n-1 . For each user i, the platform will recommend one item to user i selected randomly according to the distribution ρ i . Given a recommendation policy ρ, user i's expected utility from using the platform is j ρ ij w ij ; item j's expected utility is i ρ ij w ij , where j ρ ij = 1 for each user i.Fairness desiderata. We suppose that the platform uses as a benchmark, for each user or item, the best thing that it could do for that agent if it ignored the utilities of others. Thus, given a recommendation policy ρ, let U i (ρ, w) be user i's utility from ρ, normalized by the utility max j w ij they would receive from being recommended their best match. Let I j (ρ, w) be item j's utility from ρ, normalized by the utility j receives if it is recommended to every user, i w ij . The normalized utilities are:U i (ρ, w) = j ρ ij w ij max j w ij , I j (ρ, w) = i ρ ij w ij i w ij .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 or an item that is generally undesirable to users.Given a recommendation policy ρ, user fairness is quantified as the minimum normalized user utility U min (ρ, w) = min i U i (ρ, w), and item fairness analogously as I min (ρ, w) = min j I j (ρ, w).Multi-objective recommendation optimization. We suppose that the platform seeks to satisfy its fairness desiderata as follows. At the extremes, the platform could choose a maximally fair solution for one side, ignoring the other. Denote the optimal user fair utility as U * min (w) := max ρ U min (ρ, w) (achieved by giving each user their favorite item deterministically), and the optimal item fair utility as I * min (w) := max ρ I min (ρ, w). Finally, we cast the two-sided fair optimization -for the optimal γ-constrained user fair solution -asEQUATIONsubject to I min (ρ, w) ≥ γI * min (w), i.e., we maximize the minimum normalized user utility, subject to the minimum normalized item utility being at least a fraction γ of the optimal item fair solution.Research questions: price of fairness and misestimation. We can now define the price of item fairness on user fairness π F U |I ("price of fairness") as the decrease in user fairness with maximal item fairness constraints: .We ask how π F U |I changes with the utility matrix w. We note that while this question (in terms of solutions to Problem (1) ) can be simply stated, as we detail in Section 3, finding a closed form expression for U * min (1, w) -the optimal minimum normalized user utility given item fairness constraints -in terms of w is theoretically challenging.Similarly, we investigate the price of misestimation. Let ŵij denote the platform's estimate of the utility of recommending i to j; let ρ(γ) be a policy that solves the optimization problem above with misestimated utilities, that is, ρ(γ) attains U * min (γ, ŵ). 1 Then we define the price of misestimation on user utility ("price of misestimation") π M U asπ M U (γ, w, ŵ) := U * min (γ, w) -U min (ρ(γ), w) U * min (γ, w), that is, the decrease in true user fairness due to optimizing with estimated utilities. In particular, in Section 5 we will examine whether item fairness exacerbates the price of misestimation by comparing π M U (0, w, ŵ) and π M U (1, w, ŵ), particularly in the case of cold start users.Discussion. We note several modeling choices. First, we assume that utility w ij is shared -both the item j and user i benefit equally from a 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 [45] , and prevents solutions in which an item that provides utility ϵ to every user needs to be recommended to every user to equalize utilities. We use individual egalitarian fairness (minimum utility over individuals) instead of group fairness to capture settings in which group identity is not available, and systems in which individual-level disparities may be widespread; egalitarian fairness is widespread in algorithmic fairness [2, 17, 41, 43] . In Appendix A we show that our 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 an item fairness term to the objective; these two approaches can be thought of conceptually as dual to one another, and so we expect similar properties to hold in either formulation. 
theoretical framework: 
 To determine how the price of fairness π F U |I depends on utility matrix w, we need to compute U * min (1, w) and U * min (w). It turns out that U * min (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 U * min (w) = 1. However, with an item fairness constraint, we can no longer select each user's recommendation policies independently. Thus characterizing U * min (1, w) is much more complicated. Recall that U * min (1, w) is the minimum normalized user utility of the optimal user-fair recommendation subject to maximal item fairness constraints. Plugging into Problem (1) and expanding the definitions, we haveEQUATIONsubject to ρ ∈ arg maxϕ∈∆ m n-1 min j i w ij ϕ ij i w ij .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 a framework to solve this problem, which we later apply to show our main results Theorems 3 and 4. Proposition 1. Suppose that for a set of recommendation policies S ⊆ ∆ m n-1 , (i) S can be described by a finite set of linear constraints (ii) There exists an optimal solution ρ * to Problem (2) such that ρ * ∈ S (iii) ρ * is the unique feasible solution to Problem (2) in S1 Multiple policies ρ may optimize U * min (γ, ŵ), and different policies ρ may have different values of Umin (ρ, w). In our experimental results, we use the policy ρ found by the convex optimization solver.Then, finding an optimal solution ρ * 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 S and w, finding a closed-form expression for ρ * ; (c) given a closed form for ρ * in terms of w, reasoning about the properties of item fair solution U * min (1, w). To do this, for our main results, we construct S as a set of recommendations with a particular symmetric structure. Suppose users come in K types, where a user of type k shares a utility vector. Then, consider S symm = {ρ :ρ i = ρ i ′ if w i = w i ′ } ⊆ ∆ m n-1, the set of policies where users of the same type are given the same recommendation probabilities. Note that, in the extreme case, each user is their own type. Furthermore, let ρ k denote the recommendation policy for type k, for ρ ∈ S symm . Proposition 2. S symm satisfies conditions (i) and (ii) in Proposition 1. Furthermore, solutions ρ ∈ S symm to Problem (2) have a sparse structure:• If ρ is a basic feasible solution to the linear program L in Proposition 1, then there are at most n + K -1 type-item pairs (k, j) such that ρ kj > 0 (out of nK possible pairs).• If ρ is also optimal, then there are at most K -1 items that are ever recommended to more than one type of user, i.e., whereρ kj , ρ k ′ j > 0 for k ̸ = k ′ .For our main results, we will leverage the sparsity structure in Proposition 2 to show, with further restrictions on utility matrix w, that S symm also satisfies (iii). We will then derive closed-form expressions for that solution, and show how it changes as a function of w.The sparsity structure in Proposition 2 is also interesting in its own right. Without item fairness 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 fairness constraints in settings with symmetric solutions. 
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. In particular, we identify "free fairness," i.e., the price of fairness is low, when preferences are sufficiently diverse.Example 1. For intuition as to why user diversity affects the price of fairness, consider the following example. Suppose we have n = 2 items and m users, and that half the users have utility ϵ for the first item and 1 -ϵ for the second item. Then, the recommender can simply give each user their favorite item (the user optimal solution), and this solution simultaneously maximizes user and item fairness as well as total user and item utility.On the other hand, suppose all users have the same preferences: each user has utility 1 -ϵ 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 is on average less preferred by users.Since all users have the same preferences for items, using Proposition 2 it is sufficient to consider them receiving the same recommendation probabilities ρ 1 for the first item and ρ 2 = 1 -ρ 1 for the second. Bounding minimum item utility I min by the utility of the second item, we haveI min ≤ I 2 (ρ) = i ρ 2 ϵ mϵ = ρ 2 ≜ 1 -ρ 1 .For a given recommendation probability ρ 1 , the minimum normalized user utility isU min = (1 -ϵ)ρ 1 + ϵρ 2 = ϵ + (1 -2ϵ)ρ 1 ≤ ρ 1 + ϵ. Rearranging, we get that U min -ϵ ≤ ρ 1 ≤ 1 -I min =⇒ U min + I min ≤ 1 + ϵ.Thus the minimum normalized user utility and the minimum normalized item utility essentially follow a negative linear relationship -guaranteeing the second item even ϵ as much utility as the first item results in a linear cost to users. □ 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 v 1 > v 2 > ... > v n > 0. Suppose that there are two user types: a user i either has utility w ij = v j or w ij = v n-j+1 , and say that user i is of type 1 or 2 respectively. In words, the two types have opposite 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 fairness constraints.Let α be the proportion of type 1 users in the population, out of a fixed population of m users. Parameter α thus controls the population heterogeneity; if α is near 0 or 1, the population is highly homogeneous, dominated by users of the same type. If α = 1 2 , the population is split evenly between the two types and is highly heterogeneous. Since we parametrize w by α, we may write the price of fairness as,π F U |I (α) := U * min (α) -U * min (γ = 1, α) U * min (α).Given this structure, Theorem 3 states that the price of fairness π F U |I (α) increases in the homogeneity of the users -heterogeneous user populations are less affected by incorporating item fairness constraints. Theorem 3. π F U |I (α) is decreasing in α for 0 < α ≤ 1/2, and increasing in α for 1/2 ≤ α < 1.Proof sketch for Theorem 3. We show that when in a population with two opposing types as described above, the sparsity condition in Proposition 2 yields a unique solution, for which we can find a closed form and express in terms of α. We then evaluate U min (ρ, α) at this solution to find U * min (1, α), and show that this is indeed increasing. The full proof is in Appendix D. 
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 as the average of preferences of existing users (e.g., in a 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 [29] for example develop an algorithm for item fairness where users with weaker preferences are explicitly leveraged in this way.For a given item fairness level γ, true utility matrix w, and estimated utility matrix ŵ, let ρ(γ) be a recommendation policy that solves the recommendation problem (Problem 1) with respect to the misestimated utilities, that is, ρ solves U * min (γ, ŵ). Recall that we define the price of misestimationπ M U (γ, w, ŵ) = U * min (γ, w) -U min (ρ(γ), w) U * min (γ, w), which represents the relative decrease in minimum normalized user utility as a result of misestimation. Item fairness worsens the price of misestimation if π M U (γ = 1, w, ŵ) > π M U (γ = 0, w, ŵ). We now formalize the above argument, building on the analysis in the previous section. As in Section 4, suppose that there are 2 types of users, with opposing preferences (i.e., with values v 1 , v 2 ..., v n and v n , v n-1 , ..., v 1 , respectively) -and the platform has correctly estimated these preferences. However, now, these two types only make up a proportion β of the population each. Now, we suppose that there is a fraction 1 -β 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 a prior by averaging over the known users' preferences -(mis)estimating the users' utility for each item j as vj +vn-j+1 2.Theorem 4. If β > 1 n and w and ŵ are as described above, then fairness constraints can arbitrarily worsen the price of misestimation.• The price of misestimation without fairness constraints is low: for all {v j }, there is a recommendation policy ρ that solves the misestimated problem U * min (0, ŵ) so thatπ M U (0, w, ŵ) ≤ 1 2 .• The price of misestimation with fairness constraints can be arbitrarily large: ∀ϵ, there exists {v j } and a recommendation policy ρ that solves the problemU * min (1, ŵ) such that π M U (1, w, ŵ) > 1 -ϵ.Proof sketch. The main task is to find the price of misestimation with fairness constraints, which requires computing U * min (1, w) when users' values are correctly estimated, and computing U * min (1, ŵ) when users' values are incorrectly estimated. To find U * min (1, w), note that w is a population with two opposing types of users, so we may leverage the insights of Theorem 3. To find U * min (1, ŵ) we again use the framework in Section 3, showing that in the setting of this theorem, we can find an optimal policy ρ * for U * min (1, ŵ) in a set S ′ ⊆ S symm of policies with an additional column-symmetry property. We use an analogue of the sparsity result in Proposition 2 to show that there is a unique feasible solution ρ ∈ S ′ and obtain a closed form expression for ρ * , and find an upper bound for U min (ρ, ŵ) = U * min (1, ŵ). In fact, we show that as long as β > 1 n , under ρ the mis-estimated users will never be recommended their most preferred items. The full proof is in Appendix E.The idea follows the above intuition: without fairness constraints and assuming cold start users follow the same distribution as existing users, the platform's price of misestimation is low because the platform treats cold start users as the average of the existing population. Fairness 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 a more careful treatment of uncertainty and fairness together is necessary for recommendation algorithms. 
empirical findings: arxiv 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 so 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 to estimate their preferences.Empirical setup. We use data from arXiv and Semantic Scholar [1, 23] . 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-based models -TF-IDF [26] and the sentence transformer model SPECTER [13] -to textual features such as the paper'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 a 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 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 [18, 39] . 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 [23] 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 a citation. We find that our recommendations effectively predict whether a user cites a paper with a high score after 2020. In Table 1 we show the results of a logistic regression between each similarity score and the presence of a citation, and observe that the coefficient on the score is significantly positive for each model. 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. (a) Illustrating Theorem 3 empirically -homogeneous populations have a higher price of fairness. Empirically, however, the price of fairness is small except with strict item fairness constraints γ → 1. (b) For a set of users, holding other users fixed, the cost to the worst-off user of misestimating their preferences at varying levels of fairness. Empirically, the cost of misestimation is high, but is not worsened with item fairness constraints, as in the worst case analysis of Theorem 4.We examine the tradeoffs between item and user fairness and the effect of misestimation on this tradeoff empirically. We work with a dataset of all 14,307 papers from 2020 and 1,000 randomly selected authors who published papers prior to 2020. The recommendation engine described above produces similarity scores between each author and paper in this dataset; we take w to be these similarity scores. For a given value of γ, to compute U * min (γ) we use the cvxpy implementation of the convex optimization algorithm SCS [36] .User-item tradeoffs as function of user diversity. Figure 3a shows the tradeoff between user fairness and item fairness in a random population and in a population of homogeneous users. To generate a tradeoff curve for the heterogeneous population, we sampled 20 random papers and 40 random authors to form w, and computed U * min (γ, w) for 50 values of γ between 0 and 1. To generate tradeoff curves from homogeneous user populations, we clustered all 1,000 users into 25 clusters using the k-means algorithm. For a single curve, to form w we sampled 20 random papers and all authors in one random cluster, which has 40 users in expectation. We run 10 experiments and plot the mean of U * min (γ, w) at each value of γ across the 10 curves as well as two std. error bars for the mean.Figure 3a demonstrates that in real data, for moderate item fairness guarantees (0 ≤ γ ≤ 0.9), on average there is a fairly low cost to user fairness, but as we approach optimal item fairness (γ → 1), the tradeoff becomes very steep. Furthermore, Figure 3a shows that item fairness tends to impose a higher cost to user fairness in more homogeneous populations, as in Theorem 3.Price of misestimation. Figure 3b shows how user fairness is affected by item fairness guarantees in the presence of misestimation. For sets of 20 random papers and 40 random authors, we select a set 10% of these users at random and treat them as 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 ( ŵ in the notation of Theorem 4). For 50 values of γ between 0 and 1, we compute U * min (1, ŵ) for the misestimated utility matrix. We also compute, counterfactually, this quantity if the utility matrix had been correctly estimated, U * min (1, w). We plot the true minimum normalized user utility for the misestimated group under the recommendation policies that attain U * min (1, w) and U * min (1, ŵ). We run 10 experiments and plot the mean value of the minimum normalized user utility and two std. error bars.In Figure 3b , near γ = 0, the price of misestimation -the gap between the two curves -is higher than the cost of misestimation near γ = 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 a large literature on (item) fair recommendation and ranking [3, 33, 46, 48, 49] and, more recently, on multi-sided user-item fair recommendation [5, 10-12, 16, 37, 45] . This literature is primarily algorithmic: for a 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 [45] develop an optimization algorithm to be fair to users (in terms of group fairness 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 fairness 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 [24] 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 a function of properties of the recommendation setting such as user diversity and recommender mis-estimation. Rahmani et al. [40] demonstrate a similar tension between item and user fairness in empirical data. Liu and Burke [29] 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 [29] 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 as 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, as a 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 fairness in an array of optimization scenarios. This concept has been subsequently applied in a variety of domains, including auction theory [22] , fair division and resource allocation [6, 30, 44] , and computer networking [47] . Barre et al. [3] apply a similar concept in assortment optimization, examining the cost of item visibility constraints on the revenue of a 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 utility required by the constraints, and the item/user utility in a revenueoptimal solution. We study how the price of item fairness on user fairness 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 fairness constraints when preferences are 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 and ranking: engagement versus value, diversity, strategic behavior, and over-time dynamics [9, 14, 15, 18-21, 25, 27, 28, 31, 32, 34, 39] . In the context of set recommendations when users consume their favorite item out of the multiple recommended, e.g., Peng et al. [39] show that there is a minimal utility-diversity tradeoff, and Besbes et al. [9] show that there is a minimal exploration-exploitation tradeoff. 
discussion: 
 In this project, we investigate the relationship between user fairness and item fairness in recommendation settings. We first develop a theoretical framework to enable us to solve for the price of fairness for many population settings, and develop a recommendation engine using real data to allow us to investigate user-item fairness tradeoffs in practice. Our work informs the design of fair recommendation systems as follows: (1) first, it emphasizes the benefits of a 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 in the presence of a user fairness objective. Our empirical analysis supports our theoretical analysis-the user base diversity affects the severity of user-side effects of imposing item fairness; however, the price of misestimating user utility is already high without item fairness constraints, and so imposing such constraints does not have additional effects. Such results speak to the importance of instance-specific analyses, cf. [38] : one cannot make general statements about the specific effects of item-fairness constraints on users (or vice versa) outside of a specific context, though we identify two relevant phenomena (user diversity and misestimation) that modulate these effects.Limitations. Our theoretical analysis explores these fairness tradeoffs in a fairly restricted setting. First, we assume that users are only recommended a single item; future work should investigate how the price of fairness 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 item or user fairness at the expense of the entire platform's utility; the problem is really one of balancing user and item fairness with overall platform performance. Algorithms to optimize these multisided problems are explored in other work [12] , but it would be interesting to develop qualitative observations about user-item fairness tradeoffs in the presence of a total utility constraint. Finally, we show our Theorems 3 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.A.1 Alternative definitions of fairness Nash Welfare The first alternative definition of fairness we consider is Nash welfare [35] ,U NW (ρ) = i log U i (ρ), I NW (ρ) = j log I j (ρ).This measure of fairness is more holistic than egalitarian fairness as it accounts for the utilities of all users (items). In Figure 2 , we show the results of repeating the experiment in Figure 1 with Nash Welfare fairness. We see 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 γ with 1/γ in the item fairness constraint of 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. When this γ is nearly 1, we do see an increase in the price of mis-estimation. min . Thus as before, when γ = 0 there is effectively no item fairness constraint, and γ = 1 constrains item fairness to be maximal.The second alternative definition of fairness we consider is the sum of the kminimum user or item utilities, which is a generalization of egalitarian fairness (k = 1) that measures the utility of a size-k set of worst-off entities,U k-min (ρ) = min i1̸ =...̸ =i k k ℓ=1 U i ℓ (ρ), I k-min (ρ) = min j1̸ =...̸ =j k k ℓ=1 I j ℓ (ρ).In Figure 3 , we show the results of repeating the experiment in Figure 1 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. At already very high levels of item fairness -between γ ≈ 0.9 and γ = 1 -there appears to be an increase in the price of misestimation.In our theoretical and empirical results, we use a symmetric utility model, where an item's utility for being recommended to a user is the same as the user's utility for the recommendation. Formally, in general item j has utility w I ij for being recommended to user i, while user i may have a different utility w U ij for that recommendation. In our theoretical and empirical results above, we took w ij = w I ij = w U ij . 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 a successful recommendation. This is reasonable in settings in which not only does a user want to be recommended relevant items, but an item's producer wants it to be recommended to users 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 to be shown the item; in a 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: an 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 to 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 ρ ij , these are both j i w ij ρ ij . 2One generalization of the symmetric utility model is where each user and item receives utility proportional to some shared recommendation quality w ij . Formally, each user i receives a utility of a i w ij and each item j receives a utility of b j w ij from recommending j to i, for a i , b j > 0. For example, different values of a i could capture different levels of 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, 37] , where items receive utility only from being recommended, and are ambivalent to which user it is shown to. Formally, this corresponds to taking w I ij = 1 for all i, j. 3 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 a 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 4 and 5 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 preference diversity indeed still improves the user-item fairness 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. Figure 4 : Robustness of empirical findings without symmetry assumption: user-item fairness tradeoffs and diversity as item utilities become less correlated with user utilities. Here, we take the user utilities w U 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 I ij = ∆ • 1 + (1 -∆) • w U ij .When ∆ = 0, item and user utilities agree; when ∆ = 1 items derive utility solely from 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 w U 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 I ij = ∆ • 1 + (1 -∆) • w U ij .When ∆ = 0, item and user utilities agree; when ∆ = 1 items derive utility solely from exposure.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 so only have metadata but no associated interaction or 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-based methods on the abstract text (for both items and the user's historical papers) to generate similarity scores (utility matrices) for users and items. We use the similarity scores to 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.The original dataset was sourced from the public ArXiv Dataset available on Kaggle,4 containing 1,796,911 articles. This dataset covers a wide range of scientific categories. Each entry in the dataset is characterized by features which include:• ID: A unique identifier for each entry.• Authors: Names and affiliations of the authors.• 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 [23] . 5 For each paper, we have both the papers that it cites and the papers that cite it.We focus exclusively on 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 filtering results in 177,323 entries. This entire empirical workflow was run on a machine with 64 CPUs, 1 TB RAM, and 14 TB (non-SSD) disk. The estimated time was about 20 hours per week for 3 months, and the longest individual run was approximately 12 hours.Train and test data As training (to construct embeddings for users), we consider papers that those users published up to the end of 2019. Papers in 2020 are in the test set (the set available to be recommended). Papers after 2020 are used to evaluate recommendations (did the user cite a 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 approximately 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 the distribution of the number of papers per user in the training set on a 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 in fact cited in their subsequent works. For further details, see below Section B.3 on the model evaluation.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 to 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 on the abstracts of each paper to generate paper embeddings. The first approach is TF-IDF, while the second employs Sentence Transformers.TF-IDF. The first preprocessing step involved removing stopwords-common words with little informational value, such as "and" and "the"-to reduce noise and emphasize meaningful content. Next, a 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-based 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 a pre-trained Sentence Transformer model, specifically the AllenAI SPECTER model [13] , 6available on Hugging Face.(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' Mean score. We take the mean of the cosine similarities between the recommendation set paper and each of the papers by the user in the training set. This approach is equivalent to constructing a 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 a user may have [18, 39] -for example, for a user who has published papers in two different subject areas, a 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-paper 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.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-paper pair, we use the following as outcome data:User cites paper in the future: Is the paper cited by the user in the future?Paper cites user: Does the paper cite the user already? We note 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 not 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 as 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 of the similarity score, where percentile is 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 a strong relationship between text-based similarity scores and future citation outcomes.We evaluate each of the 4 approaches. As summarized below, we find that the best performing approach is using the TF-IDF vectorizer to construct abstract embeddings, and then using the max similarity scores between any of their papers in the training set and each paper in the recommended set. We find that this approach is effective at predicting future citations by the user, especially for a cold start recommender that uses only abstract textual information, and for such a sparse outcome as citations.No 3 : Logistic regression results for predicting whether user i cites paper j from the similarity score w ij , 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 a citation occurred between the user and paper (whether the user cites the paper, or vice versa). Figure 8 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 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 text-based recommendation scores are effective for predicting whether the user will cite the given paper. For example, Figure 8b shows that Pr(Highest score bin|Author cites paper) is more than five times Pr(Highest score bin|Author does not cite paper).No Mean score, TF-IDF Table 4 shows the similarity measures described above averaged over all users and test papers, conditioned on whether or not a 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 5 : Logistic regression results for predicting whether user i cites paper j from the similarity score w ij " for the Mean score, TF-IDF model the future. The density for cited papers is higher at higher levels of similarity scores compared to non-cited papers. Table 5 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.No 6 shows the similarity measures described above averaged over all users and test papers, conditioned on whether or not a 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-paper score and whether the user cites the paper with a bias term ('User cites paper ∼ 1 + score'), for each score measure.No 8 shows the similarity measures described above averaged over all users and test papers, conditioned on whether or not a 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-paper score and whether the user cites the paper with a 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.In this section, we provide complete proofs for Proposition 1 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 w ij > 0 for all j, I * min > 0.Proof. Let ρ ij = 1 n . Then I j (ρ) > 0 for all j so I min (ρ) > 0 and I * min = max ρ I min (ρ) > 0.First, recall the statement of Proposition 1. Proposition 1. Suppose that for a set of recommendation policies S ⊆ ∆ m n-1 , (i) S can be described by a finite set of linear constraints (ii) There exists an optimal solution ρ * to Problem (2) such that ρ * ∈ S (iii) ρ * is the unique feasible solution to Problem (2) in S Then, finding an optimal solution ρ * 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 1 can be expressed as a linear program. We will prove this result below. (EQUATIONThen F is the solution set of the linear programEQUATIONNow, condition (iii) on S implies that there is a unique ρ * in S ∩ F. Thus ρ * = F ∩ S = arg maxEQUATIONWe can add S as a constraint in Problem 4 because we know that there is at least one solution to Problem 4 in S -namely, ρ * -so this additional constraint will not change the optimal objective value, but will constrain the set of optimal solutions to be in S, as desired.By condition (ii), ρ * is an optimal solution for Problem 1; by condition (i), S can be described by a finite set of linear constraints, and thus Problem 5 is a linear program; call this L.We now show Lemma 2. Lemma 2. Let F denote the feasible set of Problem 1,EQUATION)Then F is the solution set of the linear program F = arg maxEQUATIONProof. To show this, we prove by contradiction that every optimal policy gives each item j the same normalized utility; that is, we show that if the policy ρ is an optimal solution of Problem 3, then there is some λ such that for all j, I j (ρ) = λ, and in this case λ = min j I j (ρ). This implies that any solution ρ to Problem 3 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 at the optimum, we suppose the contrary and produce a contradiction. Suppose that the policy ρ maximizes min j I j (ρ), but there is some j such that I j (ρ) > I * min . We will show that this means we can construct ρ ′ such that I min (ρ ′ ) > I * min . First, note that it is impossible that ρ ij = 0 for all i, otherwise I * min = I j (ρ) = 0. However, by Lemma 1, I * min > 0. Thus for some i, ρ ij > 0. Define J = {j ′ : I j ′ (ρ) = I * min }, and let j ′ ∈ J . Sinceρ ij > 0 and k ρ ik = 1, ρ ij ′ < 1. Pick ϵ > 0 such that ρ ′ ij := ρ ij -ϵ > 0, ρ ′ ij ′ := ρ ij ′ + ϵ < 1, and I j (ρ ′ ) > I * min . Since I j is linear in the recommendation policy, this is always possible. Now, repeat this process for all j ′ ∈ J , to obtain a final recommendation policy ρ ′ in whichI ℓ (ρ ′ ) > I *min for all ℓ and thus I min (ρ ′ ) > I * min . This contradicts the optimality of I * min .Now, we prove Proposition 2. Proposition 2. S symm satisfies conditions (i) and (ii) in Proposition 1. Furthermore, solutions ρ ∈ S symm to Problem (2) have a sparse structure:• If ρ is a basic feasible solution to the linear program L in Proposition 1, then there are at most n + K -1 type-item pairs (k, j) such that ρ kj > 0 (out of nK possible pairs).• If ρ is also optimal, then there are at most K -1 items that are ever recommended to more than one type of user, i.e., whereρ kj , ρ k ′ j > 0 for k ̸ = k ′ .Proof. We will first prove that S symm satisfies conditions (i) and (ii), and then show sparsity.Part 1. Recall that for fixed w,S symm = {ρ : ρ i = ρ i ′ if w i = w i ′ } = i,i ′ :wi=w i ′ {ρ : ρ i = ρ i ′ }which is a finite set of linear constraints, so condition (i) holds. Now, we show condition (ii), that always there is some ϕ * ∈ S symm that is an optimal solution to Problem 1. Let ρ be an arbitrary optimal solution to Problem 1. Then ρ is also feasible:I min (ρ) = I * min .We first define a piece of convenient notation: if two users i, i ′ share the same utility vector w i = w i ′ , we say that they have the same typeτ (i) = τ (i ′ ). If τ (i) = τ (i ′ ) := τ , we write w ij = w i ′ j := w τ j Let ϕ ij = 1 |{i ′ : τ (i ′ ) = τ (i)}| i ′ :τ (i ′ )=τ (i) ρ i ′ jfor all i, j. We must show that:• ϕ ij = ϕ i ′ j for all i, i ′ where τ (i) = τ (i ′ ),• ϕ is a valid set of recommendation probabilities,• ϕ is feasible: I min (ϕ) = I * min , and • ϕ is optimal: U min (ϕ) ≥ U min (ρ) = U * min .Clearly ϕ ij = ϕ i ′ j for all i, i ′ where τ (i) = τ (i ′ ), since ϕ ij depends only on i through τ (i).For each i,j ϕ ij = 1 |{i ′ : τ (i ′ ) = τ (i)}| i ′ :τ (i ′ )=τ (i) j ρ i ′ j = 1 |{i ′ : τ (i ′ ) = τ (i)}| i ′ :τ (i ′ )=τ (i) 1 = 1.Moreover, for all i, j, 0 ≤ min r,s ρ rs ≤ ϕ ij ≤ max r,s ρ rs ≤ 1. Thus ϕ ∈ ∆ m n-1 . To show that I min (ϕ) = I * min , notice that intuitively, when we move from ρ to ϕ, we redistribute the probability mass assigned to an item j among users of the same type. Since all of these users generate the same value for item j, there should be no change in item j's expected utility. Formally,I min (ϕ) = min j τ w τ j i:τ (i)=τ ϕ ij τ w τ j i:τ (i)=τ 1 = min j τ w τ j i:τ (i)=τ ρ ij τ w τ j i:τ (i)=τ 1 = I min (ρ) = I * min .(ρ is optimal) Finally, to show that U min (ϕ) ≥ U min (ρ), we 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 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(τ ) ∈ arg min i:τ (i)=τ U i (ρ). ThenU i(τ ) (ρ) ≤ U i ′ (ρ) for all i ′ : τ (i ′ ) = τ =⇒ n j=1 w τ j ρ i(τ )j max j v j ≤ n j=1 w τ j ρ i ′ j max j v j for all i ′ : τ (i ′ ) = τ =⇒ |{i ′ : τ (i ′ ) = τ }| n j=1 w τ j ρ i(τ )j max j v j ≤ i ′ :τ (i ′ )=τ n j=1 w τ j ρ i ′ j max j v j =⇒ n j=1 w τ j ρ i(τ )j max j v j ≤ n j=1 w τ j ϕ i ′ j max j v j for all i ′ : τ (i ′ ) = τ (definition of ϕ) =⇒ min i:τ (i)=τ U i (ρ) ≤ min i:τ (i)=τ U i (ϕ) Then U min (ρ) = min τ min i:τ (i)=τ U i (ρ) ≤ min τ min i:τ (i)=τ U i (ϕ) = U min (ϕ)and we have shown that U min (ϕ) ≥ U min (ρ).Part 2. Now we show the sparsity of solutions to the linear program L in Proposition 1, that is, Problem 5 defined above in the proof of Proposition 1. Given that ρ ∈ S symm , we can rewrite the linear program as ϕ = arg maxρ∈∆ K n-1 ,λ λ subject to I j (ρ) = λ ∀j, which is the same as ϕ = arg max ρ,λ λ subject to I j (ρ) = λ ∀j, j ρ kj = 1 ∀k, ρ kj ≥ 0 ∀k, j,where I j (ρ) is shorthand forI j (ρ ′ ) where ρ ′ ∈ ∆ m n-1 is ρ ∈ ∆ K n-1expressed in terms of users rather than types. This is a linear program with nK + 1 variables, and n + K equality constraints. Then for any basic feasible solution ρ of Problem 5, there must be nK + 1 linearly independent active constraints (see Definition 2.9 in Bertsimas and Tsitsiklis [7] ). This means that of the nK constraints {ρ kj ≥ 0} k,j , at least nK + 1 -(n + K) must be binding. Equivalently, there can be at most nK -(nK + 1 -(n + K)) = n + K -1 values of k, j such that ρ kj > 0.If ρ is also an optimal solution, then by Lemma 1 there must be some k such that ρ kj > 0 for each j, which takes up n non-zero values. Only K -1 non-zero values remain to be assigned, so at most K -1 items j have ρ kj , ρ k ′ j > 0 for two types k, k ′ .Recall Theorem 3 and its setting. We let v 1 > v 2 > ... > v n and suppose that there are two user types. A user i either has value w ij = v j for all j or w ij = v n-j+1 for all j, corresponding to types 1 and 2 respectively. That is, the two types have opposite preferences. We let α be the proportion of type 1 users in the population, out of a fixed population of m users. Theorem 3. π F U |I (α) is decreasing in α for 0 < α ≤ 1/2, and increasing in α for 1/2 ≤ α < 1.Proof. The proof will proceed in two parts. First, we will reduce the problem to finding a solution for a linear program using the framework from Proposition 1. Then, we will find a solution to the linear program. In this proof, we will use a series of intermediate results, which we prove in the following section. The first such result is Lemma 3.Lemma 3. For all 0 < α < 1, U * min (α) = 1. By Lemma 3, U * min (α) := U * min is constant in α, so π F U |I (α) = (U * min -U * min (1,α)) /U * min and it is enough to show U * min (1, α) increases in α.{ρ :ρ i = ρ i ′ if w i = w i ′ }.By Proposition 2, we know that S symm is a satisfies conditions (i) and (ii) on S for Proposition 1.Thus by Proposition 1, it is sufficient to find ϕ such that ϕ ∈ arg maxρ∈S∩∆ m n-1 ,λ λ subject to I j (ρ) = λ ∀j,and show that this ϕ is unique, where the linear program is derived from the proof of Proposition 1.Since each user in our population only has one of two possible value vectors, w i = (v 1 , ..., v n ) or w i = (v n , ...., v 1 ), we can identify S symm with ∆ 2 n-1 , and identify ρ ∈ S symm with a pair x, y. Expanding the expression for I j (ρ) and making explicit the dependence on α, we see thatI j (ρ, α) = i ρ ij w ij (α) i w ij (α) = i:τ (i)=1 ρ ij v j + i:τ (i)=2 ρ ij v n-j+1 i:τ (i)=1 v j + i:τ (i)=2 v n-j+1 = mαx j v j + m(1 -α)y j v n-j+1 mαv j + m(1 -α)v n-j+1 = q j (α)x j + (1 -q j (α))y j where q j (α) := αv j αv j + (1 -α)v n-j+1.Note that for all j and 0 < α < 1, we have 0 < q j , 1 -q j < 1. We can thus simplifyEQUATIONFirst, we will show uniqueness and find a closed form to Problem 6 in Lemmas 4 and 5. Then, we will use this closed forms to show that U * min (1, α) is increasing for α < 1/2. By symmetry, this implies that U * min (1, α) must be decreasing for α > 1/2 and we will be done. Lemma 4. Problem 6 has a unique solution (x, y, λ). Moreover, the solution is sparse: there is some 1 ≤ t ≤ n such that for j > t, x j = 0, and for j < t, y j = 0. Thus, to solve our original problem (Problem 1) we merely need to evaluate the user fairness U min of x, y solving Problem 6 and show that this is increasing. We will do this in the remainder of the proof.For each α, let x, y be the solution to the corresponding Problem 6, and define7 t(α) := max{j : x j (α) > 0}.Lemma 5. Let 0 < α < 1, t := t(α). DefineL t = j<t 1 q j , R t = j>t 1 1 -q j .ThenI * min = 1 1 + q t L t + (1 -q t )R t ,andx j =      I * min qj , j < t 1 - Lt 1+qtLt+(1-qt)Rt , j = t 0, j > t , y j =      0, j < t 1 - Rt 1+qtLt+(1-qt)Rt , j = t I * min 1-qj , j > t .Note that for t ̸ = t(α), x, y above may not be valid probability vectors.Lemma 6. For 0 < α < 1/2, if ρ * is the optimal recommendation policy, thenU i (ρ * , α) ≥ U i ′ (ρ * , α) for τ (i) = 1, τ (i ′ ) = 2. By Lemma 6, U * min (α) = U i (α) for i with τ (i) = 2. Then U * min (1, α) = U i (α) = 1 max j v j n j=1 y j v n-j+1 = 1 max j v j   y t(α) v n-t(α)+1 + j>t(α) y j v n-j+1   = 1 max j v j     1 - j>t(α) I * min (α) 1 -q j (α)   v n-t(α)+1 + j>t(α) I * min (α) 1 -q j (α) v n-j+1   = 1 max j v j   v n-t(α)+1 + j>t(α) I * min (α) 1 -q j (α) (v n-j+1 -v n-t(α)+1 )  The following results will enable us to conclude thatU * min (1, α) is increasing for α < 1/2. Lemma 7. t(α) is weakly increasing. Lemma 8. I * min (α) is increasing for α ≤ 1/2.Lemma 9. q j (α) strictly increases as α increases and strictly decreases as j increases.Since t(α) is increasing and v j decreases in j, v n-t(α)+1 is increasing in α. Also, I * min (α) is increasing for α < 1/2, and q j (α) is increasing, soI * min (α) 1-qj (α) is increasing. For j > t(α), v n-j+1 - v n-t(α)+1 > 0. Thus, U * min (1, α) is increasing.We will first prove Lemma 9, as it is a simple result that we will use extensively. Lemma 9. q j (α) strictly increases as α increases and strictly decreases as j increases.Proof. Recall the definition of q j (α):q j (α) = αv j αv j + (1 -α)v n-j+1.We can rewrite this asq j (α) = 1 1 + (1-α)vn-j+1 αvj = 1 1 + ( 1 α -1) vn-j+1 vj , which is strictly increasing in α since v n-j+1 /v j > 0. Since v j is decreasing in j, v n-j+1 /v j is increasing in j. Then since 1/α > 1, 1 α -1 vn-j+1 vj is increasing, so q j (α) is decreasing. Lemma 3. For all 0 < α < 1, U * min (α) = 1.Proof. Simply put, the argument below says that since there are no total utility or item fairness constraints, we can simply maximize utility for each user individually. When we do this, each user gets a utility ratio of 1. Formally, recall thatU * min (α) = max ρ∈∆ m n-1 min i j=1 ρ ij w ij (α) max j w ij (α)We can pick x i for each user i independently, so this problem becomesU * min (α) = min i 1 max j w ij max ρi∈∆n-1 j=1x ij w ij (α).We know that j=1 ρ ij w ij is maximized by putting all probability mass of ρ i on the coordinate of w i with the highest value, yielding expected value max j w ij . ThenU * min (α) = min i max j w ij max j w ij = 1.Lemma 4. Problem 6 has a unique solution (x, y, λ). Moreover, the solution is sparse: there is some 1 ≤ t ≤ n such that for j > t, x j = 0, and for j < t, y j = 0.Proof. Let α be fixed; we will suppress the dependence on α for the remainded of the proof. Recall that Problem 6 is a linear program, and we can therefore rely on known facts about the structure of solutions to linear programs to prove this result.Part 1 First, we show that at least n -1 of {x j , y j } j must be zero in every basic feasible solution.By Proposition 2, since K = 2, at most n + 2 -1 = n + 1 of {x j , y j } j can be non-zero and thus at least n -1 of these are zero.Part 2 Now, we show that every optimal basic feasible solution has the form above.If x, y, λ define an optimal basic feasible solution and x j = 0, then if i > j, x i = 0. To see this, suppose this is not the case, that is, there is some j < i such that x i := c > 0 but x j = 0. We will show that we can form x ′ , y ′ with min j I j (x ′ , y ′ ) > λ, which means that the policy ρ ′ formed by giving recommendation policy x ′ to all users of type 1 and recommendation policy y ′ to all users of type 2, is a better solution to Problem 1 than the policy ρ defined by x, y, which means ρ is not optimal and we have a contradiction.Since x, y are feasible, we must have I i (x, y) = I j (x ′ , y ′ ) = λ, so q i c + (1 -q i )y i = (1 -q j )y j . (7) Define x ′ , y ′ as follows:EQUATIONIntuitively, to define x ′ we move all probability mass away from i to j. To define y ′ , we move sufficient mass from j to i to offset the decrease in value to item i from changing x to x ′ . In order to strictly increase I ℓ for all items ℓ, in x ′ we also move ϵ 1 mass to the other items.These will be valid probability vectors for ϵ 1 , ϵ 2 > 0 small enough; for x ′ this is clear. For y ′ , we must show that y j > qic 1-qi , and y i + qic 1-qi < 1. Rearranging Equation 7and noticing that q j > q i by Lemma 9,y i + q i c 1 -q i = (1 -q j )y j 1 -q i < y j ≤ 1.Moreover, 7)y j - q i c 1 -q i = q i c + (1 -q i )y i 1 -q j - q i c 1 -q i (Equation> q i c + (1 -q i )y i 1 -q i - q i c 1 -q i (q j > q i ) = y i .≥ 0 Now, we can show that I min (x ′ , y ′ ) > I min (x, y) = I * min , which is a contradiction. To do this, it is sufficient to show that I ℓ (x ′ , y ′ ) > I ℓ (x, y) for each ℓ.• ℓ / ∈ {i, j}: Since x ′ ℓ > x ℓ , y ′ ℓ = y ℓ , I ℓ (x ′ , y ′ ) > I ℓ (x, y). • ℓ = i: I i (x ′ , y ′ ) = (1 -q i ) y i + q i c 1 -q i + ϵ 2 = (1 -q i )y i + q i λ + ϵ 2 = I i (x, y) + ϵ 2 • ℓ = j: I j (x ′ , y ′ ) = q j (λ -ϵ 1 ) + (1 -q j ) y j - q i λ 1 -q i -ϵ 2 = (1 -q j )y j + λ q j -q i 1 -q j 1 -q i -ϵ 1 q j -ϵ 2 (1 -q j ) = I j (x, y) + λ q j -q i 1 -q j 1 -q i -ϵ 1 q j -ϵ 2 (1 -q j )Since q j > q i , q j -q i 1-qj 1-qi > 0, and thus I j (x ′ , y ′ ) > I j (x, y) if ϵ 1 , ϵ 2 are small enough.Since we did not use the fact that α < 1/2 here, a symmetric argument shows that we cannot have y j = 0, y i > 0, and i < j,Let k be the number of indices j such that x j > 0. The above arguments together imply that x j = 0, j > k. There are then at least n -1 -(n -k) = k -1 indices j such that y j = 0; the argument above implies that these zeroes are on the lowest possible indices, that is, y j = 0, j < k. Thus if we take t = k, we have that for j > t, x j = 0, and for j < t, y j = 0.Part 3 Finally, we show that there is only a single optimal solution, which is a basic feasible solution of this form.Suppose that x ′ , y ′ is another optimal basic feasible solution; we will show that x ′ = x, y ′ = y. Denote t(x, y) = max{j : x j > 0}.• If t(x, y) = t(x ′ , y ′ ), then:-For j < t, y j = y ′ j = 0, and q j x j = I j (x, y)EQUATIONsox j = x ′ j .-Similarly for j > t, x j = x ′ j = 0, and(1 -q j )y j = I j (x, y) = I min (x, y) = I min (x ′ , y ′ ) = I j (x ′ , y ′ ) = (1 -q j )y ′ j , so y ′ j = y j . -Finally, this means y t = 1 -j>t y j = 1 -j>t y ′ j = y ′ t , and x t = 1 -j<t x j = 1 -j<t x ′ j = x ′ t .• Otherwise, without loss of generality let t(x ′ , y ′ ) > t(x, y) := t. For j < t, q j x j = I j (x, y) = I j (x ′ , y ′ ) = q j x ′ j , so x ′ j = x j . For j > t, x j = 0. Furthermore,q t x t + (1 -q t )y t = I t (x, y) = I t (x ′ , y ′ ) = q t x ′ t ⇐⇒ q t   1 - j<t x j   + (1 -q t )y t = q t x ′ t ⇐⇒ q t   1 - j<t x ′ j   + (1 -q t )y t = q t x ′ t ⇐⇒ (1 -q t )y t = q t   j≤t x ′ t -1  Since q t , 1 -q t > 0, and y t ≥ 0, j≤t x ′ t ≤ 1, it must be the case that y t = 0 and j≤t x ′ t = 1. However, y t > 0 by definition of t, and we have a 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 0 < α < 1, t := t(α). DefineL t = j<t 1 q j , R t = j>t 1 1 -q j . Then I * min = 1 1 + q t L t + (1 -q t )R t ,andx j =      I * min qj , j < t 1 - Lt 1+qtLt+(1-qt)Rt , j = t 0, j > t , y j =      0, j < t 1 - Rt 1+qtLt+(1-qt)Rt , j = t I * min 1-qj , j > t .Proof. Fix 0 < α < 1. This result mainly follows from the fact that j x j = j y j = 1, and I j (x * , y * ) = I j ′ (x * , y * ) for all j, j ′ , as well as the sparse solution structure shown in Lemma 4.We know that the optimal solution satisfies I * min = I j = I j ′ for all j, j ′ . We also already know that for j > t, x j = 0, and for j < t, y j = 0.For j < t, I * min = I j = x j q j + 0 =⇒ x j = I * min qj .For j > t, I * min = I j = 0 + y j (1 -q j ) =⇒ y j = I * min 1-qj .For j = t, we know I * min = I t = q t x t + (1 -q t )y t . Then for j < t, x j = 1 qj (q t x t + (1 -q t )y t ), soEQUATIONSimilarly, y j = 1 1-qj (q t x t + (1 -q t )y t ) soEQUATIONCombining equations 8 and 9, we obtainEQUATIONSubstituting equation 10 into equation 9, we get1 -y t = q t 1 - L t R t (1 -y t ) + (1 -q t )y t R t ⇐⇒ 1 + q t L t -q t R t = y t (1 + q t L t + (1 -q t )R t ) =⇒ y t = 1 + q t L t -q t R t 1 + q t L t + (1 -q t )R t = 1 - R t 1 + q t L t + (1 -q t )R t Then x t = 1 - L t R t (1 -y t ) = 1 - L t 1 + q t L t + (1 -q t )R t .Finally, we see thatI * min = q t x t + (1 -q t )y t = q t 1 - L t 1 + q t L t + (1 -q t )R t + (1 -q t ) 1 - R t 1 + q t L t + (1 -q t )R t = 1 - q t L t + (1 -q t )R t 1 + q t L t + (1 -q t )R t = 1 1 + q t L t + (1 -q t )R t . Lemma 6. For 0 < α < 1/2, if ρ * is the optimal recommendation policy, then U i (ρ * , α) ≥ U i ′ (ρ * , α) for τ (i) = 1, τ (i ′ ) = 2.Proof. Intuitively, the type with a 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 recommendation probability on the items they really like compared to the smaller group.Formally, let i, i ′ be users such that τ(i) = 1, τ (i ′ ) = 2. For α ≤ 1/2, j < t(α), x j -y n-j+1 = 1 q j (α) - 1 1 -q j (α) = αv j + (1 -α)v n-j+1 αv j - αv n-j+1 -(1 -α)v j (1 -α)v j = 1 v j v j + 1 -α α v n-j+1 -v j - α 1 -α v n-j+1 = v n-j+1 v j 1 -α α - α 1 -α = v n-j+1 v j 1 -2α α(1 -α) ≥ 0 (0 < α ≤ 1/2) So max j v j • (U i -U i ′ ) = j≤t v j x j - j≥t v n-j+1 y j = j≤t v j (x j -y n-j+1 ) - j<t v j y n-j+1 (collecting coefficients of v j ) ≥ j≤t v t (x j -y n-j+1 ) - j>t v j y n-j+1 (v t ≤ v j for j ≤ t, x j > y n-j+1 ) ≥ v t j≤t (x j -y n-j+1 ) -v t j>t y n-j+1 (v t > v j for j > t) ≥ v t -v t j≤t y n-j+1 -v t j>t y n-j+1 ( j≤t x j = 1) = v t -v t ( j≤t y j = 1) = 0Since max j v j > 0, we have that U i ≥ U i ′ .Lemma 7. t(α) is weakly increasing.Proof. Suppose not, that is, there are some α < α ′ such that t := t(α) > t(α ′ ) := t ′ . We will split this problem into several cases based on which of α, α ′ gives a solution with higher item fairness, and show the implications of decreasing t on the closed-form solutions from Lemma 5, eventually reaching a contradiction in each case.Recall from Lemma 9 that q j (α) = αvj αvj +(1-α)vn-j+1 is increasing in α, so q j (α) < q j (α ′ ) for all j. First, let I * min (α) < I * min (α ′ ). If t = n then for j < n, y j = 0, and thus y n = 1. SoI * min (α) = (1 -q n (α)) > (1 -q n (α ′ )) ≥ (1 -q n (α ′ ))y ′ n = I * min (α ′ ) since y ′n ≤ 1, and we have a contradiction. Otherwise if t < n, let j > t. Then(1 -q j (α))y j = I * min (α) < I * min (α ′ ) = (1 -q j (α ′ ))y ′ j ⇐⇒ y j y ′ j < 1 -q j (α ′ ) 1 -q j (α) < 1 =⇒ y j < y ′ j Then y t = 1 -j>t y j > 1 -j>t y ′ j ≥ y ′ t . So q t (α)x t + (1 -q t (α))y t < (1 -q t (α ′ ))y ′ t < (1 -q t (α ′ ))y t =⇒ q t (α)x t < (1 -q t (α ′ ))y t -(1 -q t (α))y t=⇒ 0 ≤ q t (α)x t < y t (q t (α) -q t (α ′ )) < 0 and we have a contradiction. Now, let I * min (α) ≥ I * min (α ′ ) instead. If t ′ = 1 then x ′ 1 = 1 andI * min (α ′ ) = q 1 (α ′ ) > q 1 (α) ≥ q 1 (α)x 1 = I * min (α),and we have a contradiction. Otherwise if t ′ > 1, then for j < t ′ ,q j (α)x j = I * min (α) ≥ I * min (α ′ ) = q j (α ′ )x ′ j =⇒ x j x ′ j ≥ q j (α ′ ) q j (α) > 1 =⇒ x j > x ′ j .Thenx ′ t ′ = 1 -j<t ′ x ′ j > 1 -j<t ′ x j ≥ x t ′ . So q t ′ (α ′ )x ′ t ′ + (1 -q t ′ (α ′ ))y ′ t ′ = I * min (α ′ ) ≤ I * min (α) = q t ′ (α)x t =⇒ (1 -q t ′ (α ′ ))y ′ t ′ ≤ q t ′ (α)x t ′ -q t ′ (α ′ )x ′ t ′ < q t ′ (α)x t ′ -q t ′ (α ′ )x t ′ =⇒ 0 ≤ (1 -q t ′ (α ′ ))y ′ t ′ < x t ′ (q t ′ (α) -q t ′ (α ′ )) ≤ 0and we have a contradiction. Thus all cases result in a contradiction.Lemma 8. I * min (α) is increasing for α ≤ 1/2.Proof. We first need the following Lemma, which shows that α ≤ 1/2 implies that t(α) must be an index at most halfway through the list of items.Lemma 10. If α ≤ 1/2, then t(α) ≤ (n + 1)/2. Now, for 1 ≤ t ≤ n, define A(t) = {α : t(α) = t}. Since t(α) is weakly increasing in α by Lemma 7, A(t) is an interval in (0, 1), and [A(1), A(2), ..., A(n)] forms a consecutive partition of (0, 1). We will now show that I * min (α) is increasing on each of the first ⌊(n + 1)/2⌋ intervals, which by Lemma 10 contain all α ∈ (0, 1/2]. Lemma 11. I * min (α) is increasing on A(t) for t ≤ (n + 1)/2.Finally, we show that this implies I * min (α) is increasing on 0 < α ≤ 1/2. Notice that I j (x, y, α) is continuous in α for each fixed x, y, so I min (x, y, α) = min j I j (x, y, α) is continuous in α for each fixed x, y. Recall that I * min (α) = max x,y∈∆n-1 I min (x, y, α). As the supremum of a set of continuous functions on a compact set must itself be continuous , this means that I * min (α) must be continuous in α, since Proof. By Lemma 7, it is enough to show that for α = 1/2, t(α) ≤ (n + 1)/2.∆ n-1 × ∆ n-1 is compact. Since I * min (α)Suppose that α = 1/2 and we have x, y of the form in Lemma 5 such that t := t(α) > (n + 1)/2.If n is even, take t ′ = n/2 in the definitions of x j , y j in Lemma 5; if n is odd, take t ′ = (n + 1)/2. We now verify that this results in x ′ , y ′ that are a feasible solution to Problem 6 and that satisfy x ′ j = y ′ n-j+1 . This is simple to see after observing that when α = 1/2, q j = 1 -q n-j+1 , so for even n, L t ′ = R t ′ + 1 1-q t ′ , and for odd n, L t ′ = R t ′ , and simplifying. Since by assumption t(α) yields the optimal solution, I min (x, y) > I min (x ′ , y ′ ). By the construction of solutions in Lemma 5, for all j we have I j (x ′ , y ′ ) = I min (x ′ , y ′ ) and I j (x, y) = I min (x, y). Then for j < t, q j x j = I j (x, y) > I j (x ′ , y ′ ) = q j x ′ j , so x j > x ′ j . Then since I t ′ (x, y) > I t ′ (x ′ , y ′ ),q t ′ x t ′ > q t ′ x ′ t ′ + (1 -q t ′ )y ′ t ′ = q t ′   1 - j<t ′ x ′ j   + (1 -q t ′ )y ′ t ′ > q t ′   1 - j<t ′ x j   + (1 -q t ′ )y ′ t ′ > q t ′   1 - j<t ′ x j   ≥ q t ′ x t ′which is a contradiction.Lemma 11. I * min (α) is increasing on A(t) for t ≤ (n + 1)/2.Proof. Recall that for fixed t,I * min (α) = 1 1 + q t (α)L t (α) + (1 -q t (α))R t (α).It is sufficient to show that q t L t + (1 -q t )R t is decreasing.We first expand the expression:q t (α)L t (α) + (1 -q t (α))R t (α) = j<t q t (α) q j (α) + j>t 1 -q t (α) 1 -q j (α) = j<t q t (α) q j (α) + j≥n-t 1 -q t (α) 1 -q j (α) + t<j<n-t 1 -q t (α) 1 -q j (α) Let t < j ≤ n -t + 1. Then g(α) := 1 -q t (α) 1 -q j (α) = (1 -α)v n-t+1 αv t + (1 -α)v n-t+1 αv j + (1 -α)v n-j+1 (1 -α)v n-j+1 = v n-t+1 v n-j+1 αv j + (1 -α)v n-j+1 αv t + (1 -α)v n-t+1 = v n-t+1 v n-j+1 v n-j+1 + α(v j -v n-j+1 ) v n-t+1 + α(v t -v n-t+1 ) So g ′ (α) = v n-t+1 v n-j+1 (v j -v n-j+1 )(v n-t+1 + α(v t -α)v n-t+1 )) -(v t -v n-t+1 )(v n-j+1 + α(v j -v n-j+1 )) (v n-t+1 + α(v t -v n-t+1 )) 2 ∝ (v j -v n-j+1 )(v n-t+1 + α(v t -v n-t+1 )) -(v t -v n-t+1 )(v n-j+1 + α(v j -v n-j+1 )) = (v j -v n-j+1 )v n-t+1 -(v t -v n-t+1 )v n-j+1 = v j v n-t+1 -v t v n-j+1 ≤ v t v n-j+1 -v t v n-j+1 (j > t, n -j + 1 < n -t + 1) = 0So g is a decreasing function of α. Now, consider j<t q t (α) q j (α) + j>n-t1 -q t (α) 1 -q j (α) = t-1 j=1 q t (α) q j (α) + n j=n-t+2 1 -q t (α) 1 -q j (α) = t-1 j=1 q t (α) q j (α) + t-1 i=1 1 -q t (α) 1 -q n-i+1 (α) (i = n -j + 1) = t-1 j=1 q t (α) q j (α) + 1 -q t (α) 1 -q n-j+1 (α) Then for 1 ≤ j ≤ t -1, h t (α) := q t (α) q j (α) + 1 -q t (α) 1 -q n-j+1 (α) = αv t αv t + (1 -α)v n-t+1 • αv j + (1 -α)v n-j+1 αv j + (1 -α)v n-t+1 αv t + (1 -α)v n-t+1 • αv n-j+1 + (1 -α)v j (1 -α)v j = v t (αv j + (1 -α)v n-j+1 ) + v n-t+1 (αv n-j+1 + (1 -α)v j ) v j (αv t + (1 -α)v n-t+1 ) = 1 + (1 -α)v t v n-j+1 + αv n-t+1 v n-j+1 v j (αv t + (1 -α)v n-t+1 ) = 1 + v n-j+1 v j • (1 -α)v t + αv n-t+1 αv t + (1 -α)v n-t+1 = 1 + v n-j+1 v j • v t + α(v n-t+1 -v t ) v n-t+1 + α(v t -v n-t+1 ) . So h ′ t (α) = v n-j+1 v j • (v n-t+1 -v t )(v n-t+1 + α(v t -v n-t+1 )) -(v t -v n-t+1 )(v t + α(v n-t+1 -v t )) (v n-t+1 + α(v t -v n-t+1 )) 2 ∝ -(v t -v n-t+1 )(v n-t+1 + α(v t -v n-t+1 )) -(v t -v n-t+1 )(v t + α(v n-t+1 -v t )) = -(v t -v n-t+1 )(v n-t+1 + α(v t -v n-t+1 ) + v t + α(v n-t+1 -v t )) = -(v t -v n-t+1 )(v t + v n-t+1 ) ≤ -(v t -v n-t+1 ) (t ≤ (n + 1)/2 ≤ n -t + 1) ≤ 0 and h t is decreasing in α for 1 ≤ j ≤ t-1. Then t-1 j=1 h t (α) is decreasing, and q t L t +(1-q t )R t = t-1 j=1 h t (α) + n-t+1j=t+1 g t (α) is decreasing, and I * min (α) is increasing.Recall Theorem 4. Theorem 4. If β > 1 n and w and ŵ are as described above, then fairness constraints can arbitrarily worsen the price of misestimation.• The price of misestimation without fairness constraints is low: for all {v j }, there is a recommendation policy ρ that solves the misestimated problem U * min (0, ŵ) so thatπ M U (0, w, ŵ) ≤ 1 2 .• The price of misestimation with fairness constraints can be arbitrarily large: ∀ϵ, there exists {v j } and a recommendation policy ρ that solves the problem U * min (1, ŵ) such that π M U (1, w, ŵ) > 1 -ϵ.Proof. We first find a 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 ŵ there are three distinct user value types, and thus we can identify S symm with ∆ 3 n-1 and a policy ρ ∈ S symm with vectors x, y, z, where x is the recommendation policy for users with value ŵij = v j , y is the recommendation policy for users with value ŵij = v n-j+1 , and z is the recommendation policy for the mis-estimated users.S ′ = {x, y, z ∈ S symm : x j = y n-j+1 , z j = z n-j+1 for all j}.Since y is completely determined by x, we can identify S ′ with ∆ 2 n-1 and can identify x, y, z ∈ S ′ simply by x, z.Lemma 12. If a policy ρ = (x, y, z) ∈ S symm solves U min (ρ) = U * min (1), then there is some policyρ ′ = x ′ , z ′ ∈ S ′ that solves U min (ρ ′ ) = U * min (1).Applying the framework in Proposition 1 to this proof with S = S ′ and using ŵ as the user and item values, we reduce the problem to findingEQUATIONand showing that this ϕ is unique.First, we use an analogue of the sparsity result Proposition 2 to show that the optimal x, z has the following sparse structure.Lemma 13. Let x, z be an optimal basic feasible solution to the linear program Problem 11. There is some j ≤ n+1 2 such that for all j ′ > j, x j ′ = 0 and for all j ′ < j, z j ′ = z n-j ′ +1 = 0. Let the pivot index t denote the minimum such j.This sparse structure implies uniqueness. Lemma 14. Problem 11 has a unique optimal solution.We can now describe what this solution (x, z) looks like.Lemma 15. Let (x, z) be the optimal solution to Problem 12, and let t be the pivot element of (x, z);suppose that t ̸ = n+1 2 . Define L t := j<t 1 q j . Then λ = 2βq t + 1 /2(1 -2β) 1 + q t L t + 1 /2(n -2t) , z j =      0, j < t 1 2 1 -(n -2t) λ 1-2β , j ∈ {t, n -t + 1} λ 1-2β , t < j < n -t + 1 .Finally,x j =      λ 2βqj , j < t 1 -λ 2β L t , j = t 0, j > t .If t = n+1 2 , then x remains the same, but z t = 1 andλ = 2βq t + (1 -2β) 1 + q t L t .If we try t = 1 and obtain z 1 < 0 above, we can conclude that t > 1. Suppose t = 1. Then L t = 0, soλ = 2βq 1 + 1 /2(1 -2β) 1 + 1 /2(n -2) and z 1 = 1 2 1 -(n -2) λ 1 -2β = 1 2 1 -(n -2) 1 1 -2β 2βq 1 + 1 /2(1 -2β) n /2 = 1 n - n -2 n 2βq 1 1 -2β Then t = 1 and z 1 < 0 if and only if 1 n - n -2 n 2βq 1 1 -2β < 0 ⇐⇒ v n v 1 < n -2 1 /2β -1 -1. since q 1 = v1 v1+vn . If β > 1 n , then n -2 1 /2β -1 -1 > n -2 n /2 -1 -1 = 2 n -2 n -2 -1 = 1.So if β > 1 n , t > 1 and z 1 = z n = 0. In this case, regardless of whether a mis-estimated user has w i1 = v 1 or w in = v 1 , that user will never be recommended their most preferred item.Moreover, no matter the true type of the mis-estimated user,U i (x, z) = 1 v 1   1≤j≤n v j z j   = 1 v 1   1<j<n v j z j   < v 2 v 1   1<j<n z j   = v 2 v 1 Thus if v 2 < v1 n ϵ, then U i (x, z) < ϵ n .Taking ρ to be the recommendation probabilities induced by this pair x, z, this implies that U min (ρ) < ϵ/n.Item fairness constraints without mis-estimation. 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 α = 1/2.If α = 1/2, then by Lemma 17 with β = 1, t = ⌊ n+1 2 ⌋, and we can show thatL t = R t -1 qt , n even R t , nodd .By Lemma 5 we know thatI * min = 1 1 + q t L t + (1 -q t )R t ,so if n is even, we haveI * min = 1 1 + q t (R t -1 qt ) + (1 -q t )R t = 1 R t = 1 j>t 1 1-qj > 1 2(n -(n/2)) = 1 nwhere we use the fact from Lemma 16 that if j > n+1 2 , then q j < 1 2 . Likewise if n is odd,I * min = 1 1 + q t R t + (1 -q t )R t = 1 1 + R t = 1 1 + j>t 1 1-qj > 1 1 + 2(n -(n + 1)/2) = 1 n .Then a user i of type 1 will have normalized utility will beU i (x, y) ≥ x 1 v 1 v 1 = I * min q 1 = I * min v 1 + v n v n ≥ I * min > 1 n .Similarly a user of type 2 will have utilityU i (x, y) ≥ y n v 1 v 1 = I * min 1 -q n = I * min v 1 + v n v n ≥ I * min > 1 n .This means that U * min (1) > 1/n.Moreover, the estimated normalized utility of a mis-estimated user i, will beU i (ρ ′ ) = n j=1 z ′ j v j + v n-j+1 2 = 1 2 n j=1 z j v j + v n-j+1 2 + 1 2 n j=1 z n-j+1 v j + v n-j+1 2 = 1 2 (U i (ρ ′ ) + U i (ρ ′ )) = U i (ρ ′ ). So min i U i (ρ ′ ) ≥ min i U i (ρ).Finally, for any j, we can expand the definition of I j to see thatI j (ρ ′ ) = 1 2 (I j (ρ) + I n-j+1 (ρ)) = I * min .Thus ρ ′ is also an optimal solution to Problem 1.Lemma 13. Let x, z be an optimal basic feasible solution to the linear program Problem 11. There is some j ≤ n+1 2 such that for all j ′ > j, x j ′ = 0 and for all j ′ < j, z j ′ = z n-j ′ +1 = 0. Let the pivot index t denote the minimum such j.Proof. Part 1. While it is tempting attempt to directly apply the sparsity result in Proposition 2 here, we will need a slightly stronger result to ensure that there are no j such that x j = z j = 0. First, we must show that x j > 0 and y j > 0 are almost mutually exclusive. Lemma 17. Let (x, z) be an optimal solution to Problem 11. For j > n+1 2 , x j = 0.In particular, if we let h = ⌊ n+1 2 ⌋ indicate the index halfway through the set of items, this means that we can simplify the problem above to arg max x1,...,x h , z1,...,z h , λ λ subject toEQUATIONNow this is a linear program with 2h + 1 variables and h + 2 constraints, so by an argument analogous to Problem 12, we find that every basic feasible solution x 1:h , z 1:h must share h -1 zeros. This means that there is a single index t such that x t > 0, z t > 0; if there were more than one, by the pigeonhole principle there must be some t ′ ≤ h such that x t ′ = z t ′ = x n-t ′ +1 = 0, and I t ′ (x, z) = 0. Then I min (x, z) = 0; however, by Lemma 1, I min (x, z) = I * min > 0, so we have a contradiction. In terms of x, z,I j (x, z) = βv j x j + βv n-j+1 x n-j+1 + (1 -2β) vj +vn-j+1 2 z j βv j + βv n-j+1 + (1 -2β) vj +vn-j+1 2 = βv j x j + βv n-j+1 x n-j+1 + (1 -2β) vj +vn-j+1 2 z j vj +vn-j+1 2 = 2β v j v j + v n-j+1 x j + v n-j+1 v j + v n-j+1x n-j+1 + (1 -2β)z j Let q j = vj vj +vn-j+1 . Note that q j does not depend on β, and q j is decreasing in j. Then I j (x, y, z) = 2β (q j x j + (1 -q j )y j ) + (1 -2β)z j .Part 2. Moreover, the set of j such that x j = 0 is contiguous; similarly for z j .We prove this by contradiction, showing that if this set is not contiguous, we can move around probability mass until we achieve greater than optimal item fairness. Let i < j ≤ h, and let x, z be an optimal solution to Problem 12. We need to show that if x i = 0 then x j = 0, and if z i > 0, then z j > 0.Suppose first that x i = 0 and x j > 0. Notice that since x, z are optimal,(1 -2β)z i = I i (x, z) = I j (x, z) = 2βq j x j + (1 -2β)z j Define x ′ ℓ =      x j -ϵ, ℓ = i x i + ϵ h-1 , ℓ = j x ℓ + ϵ h-1 , otherwise , z ′ ℓ =    z j , ℓ = i z i , ℓ = j z ℓ , otherwisefor ϵ small enough that x ′ ∈ ∆ h-1 . Now for all ℓ / ∈ {i, j}, I ℓ (x ′ , z ′ ) > I ℓ (x, z), since we have increased the probability mass on x ℓ while leaving z ℓ unchanged. Furthermore,I i (x ′ , z ′ ) = 2βq i (x j -ϵ) + (1 -2β)z j = 2β(q i -q j )x j + 2βq j x j + (1 -2β)z j -2βq i ϵ = 2β(q i -q j )x j + (1 -2β)z i -2βq i ϵ = I i (x, z) + 2β(q i -q j )x j -2βq i ϵ > I i (x, z)as long as q i ϵ < (q i -q j )x j , which we can ensure by taking ϵ small enough, since q i > q j . Moreover,I j (x ′ , z ′ ) = 2βq j x i + ϵ h -1 + (1 -2β)z i = 2βq j x i + ϵ h -1 + 2βq j x j + (1 -2β)z j > 2βq j x j + (1 -2β)z j = I j (x, z). Thus I min (x ′ , z ′ ) = min ℓ I ℓ (x ′ , z ′ ) > min ℓ I ℓ (x, z) = I min (x, z) = I * minand we have a contradiction.Similarly, suppose that z i > 0 and z j = 0. Then since x, z is optimal, we haveEQUATIONDefineEQUATION= q j q i x j < x j (q j < q i ) ≤ 1 andx j -δ > x j - (1 -2β)(z i -ϵ) 2βq j = 1 2βq j (2βq j x j -(1 -2β)(z i -ϵ)) > 1 2βq j (2βq j x j -(1 -2β)z i ) = 1 2βq j (2βq j x j -(2βq j x j -2βq i x i )) (13) = 1 2βq j 2βq i x i > 0 and x i + δ > x i ≥ 0, x j -δ < x j ≤ 1, so x ′ ∈ ∆ h-1 .Now as above I ℓ (x ′ , z ′ ) > I min (x, z) for all ℓ / ∈ {i, j}, since there is strictly more probability mass on z ℓ while x ℓ remains the same. Furthermore,I i (x ′ , z ′ ) -I i (x, z) = 2βq i (x i + δ) + (1 -2β)(z j + ϵ h -1 ) -(2βq i x i + (1 -2β)z i ) > 2βq i (x i + δ) -(2βq i x i + (1 -2β)z i ) = 2βq i δ -(1 -2β)z i = 2βq i (1 -2δ) 2βq i z i -(1 -2β)z i = 0 and I j (x ′ , z ′ ) -I j (x, z) = 2βq j (x j -δ) + (1 -2β)(z i -ϵ) -2βq j x j = (1 -2β)(z i -ϵ) -2βq j δ > (1 -2β)(z i -ϵ) -2βq j (1 -2β)(z i -ϵ) 2βq j = 0 Then I min (x ′ , z ′ ) = min ℓ I ℓ (x ′ , z ′ ) > min ℓ I ℓ (x, z) = I min (x, z) = I * minand we have found x ′ , z ′ achieving a higher-than-optimal I min , which is a contradiction.Lemma 17. Let (x, z) be an optimal solution to Problem 11. For j > n+1 2 , x j = 0.Proof. We prove this by contradiction. Suppose that for j > n+1 2 , x j > 0. Then define x ′ such thatx ′ ℓ =    0, ℓ = j x n-j+1 + (x j -ϵ) ℓ = n -j + 1 x ℓ + ϵ n-2where 0 < ϵ < (2q n-j+1 -1)x j . Since j > n+1 2 , q n-j+1 > 1/2 by Lemma 16, so such ϵ exists. Then for all ℓ / ∈ {j, n -j + 1},I ℓ (x ′ , z) = 2β q ℓ x ′ ℓ + (1 -q ℓ )x ′ n-ℓ+1 + (1 -2β)z ℓ > 2β (q ℓ x ℓ + (1 -q ℓ )x n-ℓ+1 ) + (1 -2β)z ℓ = I ℓ (x, z).Since ϵ < (2q n-j+1 -1)x j , we can rearrange to see that (1 -q n-j+1 )x j < q n-j+1 (x j -ϵ). This implies thatI n-j+1 (x ′ , z) = 2β (q n-j+1 (x n-j+1 + (x j -ϵ)) + q j • 0) + (1 -2β)z n-j+1 = 2β (q n-j+1 x n-j+1 + q n-j+1 (x j -ϵ)) + (1 -2β)z n-j+1 > 2β (q n-j+1 x n-j+1 + 2β(1 -q n-j+1 )x j ) + (1 -2β)z n-j+1 = I n-j+1 (x, z)andEQUATION2β)z j (q n-j+1 = 1 -q j ) > 2β (q n-j+1 x n-j+1 + (1 -q n-j+1 )x j ) + (1 -2β)z j = 2β ((1 -q j )x n-j+1 + q j x j ) + (1 -2β)z j (q n-j+1 = 1 -q j ) = I j (x, z) Thus we have found a solution x ′ , z that satisfies Proof. Suppose (x, z) and (x ′ , z ′ ) are both optimal basic feasible solutions to Problem 12. Let t be the pivot index of (x, z) and t ′ be the pivot index of (x ′ , z ′ ), and suppose without loss of generality that t ≤ t ′ . First, if t < t ′ , then for all j < t, z j = z ′ j = 0, and 2βq j x j = I j (x, z) = I min (x, z) = I min (x ′ , z ′ ) = I j (x ′ , z ′ ) = 2βq j x ′ j so x j = x ′ j . If j > t, x j = 0. For j = t, z ′ t = 0 and2βq t x t + (1 -2β)z t = 2βq t x ′ t =⇒ 2βq t   1 - j<t x j   + (1 -2β)z t = 2βq t x ′ t =⇒ 2βq t   1 - j<t x ′ j   + (1 -2β)z t = 2βq t x ′ t =⇒ (1 -2β)z t = 2βq t   j≤t x ′ j -1   .But (1 -2β)z t ≥ 0, so j≤t x ′ j = 1 and for j > t, x ′ j = 0. This implies that t ′ ≤ t, which is a contradiction, so it is not possible for t ′ > t. Now, if t = t ′ , then again for all j < t, z j = z ′ j = 0, and x j = x ′ j . For t < j ≤ h, x j = x ′ j = 0 and if t < h, (1 -2β)z j = I j (x, z) = I min (x, z) = I min (x ′ , z ′ ) = I j (x ′ , z ′ ) = (1 -2β)z ′ j so z j = z ′ j . Finally,x t = 1 - j<t x j = 1 - j<t x ′ j = x ′ t and z t = 1 2 (1 -2 t<j≤h z j ) = 1 2 (1 -2 t<j≤h z ′ j ) = z ′ t , n even 1 2 (1 -2 t<j<h z j -z h ) = 1 2 (1 -2 t<j<h z ′ j -z h ) = z ′ t , n odd .If t = h, then z t = 1 = z ′ t . Thus (x, z) = (x ′ , z ′ ). Thus there is 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 (x, z) be the optimal solution to Problem 12, and let t be the pivot element of (x, z); suppose that t ̸ = n+1 2 . Define L t := j<t 1 q j .Thenλ = 2βq t + 1 /2(1 -2β) 1 + q t L t + 1 /2(n -2t) , z j =      0, j < t 1 2 1 -(n -2t) λ 1-2β , j ∈ {t, n -t + 1} λ 1-2β , t < j < n -t + 1 .Finally,x j =      λ 2βqj , j < t 1 -λ 2β L t , j = t 0, j > t .If t = n+1 2 , then x remains the same, but z t = 1 and λ = 2βq t + (1 -2β) 1 + q t L t .Proof. For all j < t, λ = 2βq j x j , so x j = λ 2βqj . Moreover,x t = 1 - j<t x j = 1 - j<t λ 2βq j = 1 - λ 2β L t .Suppose that n is odd and that t = h = n+1 2 . Then z t = z h must be 1 since for all j < h z j = 0. Moreover,λ = 2βq t x t + (1 -2β)z t = 2βq t 1 - λ 2β L t + (1 -2β)so, rearranging,λ = 2βq t + (1 -2β) 1 + q t L t .Otherwise, t < j ≤ h, λ = (1 -2β)z j , so z j = λ 1-2β . Then since j≤h z j + h<j≤n z n-j+1 = 1, Rearranging, λ(1 + q t L t + 1 /2(n -2t)) = 2βq t + 1 /2(1 -2β), so λ = 2βq t + 1 /2(1 -2β) 1 + q t L t + 1 /2(n -2t) .z t = 1 2   1 -• 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 or 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 in 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: We release a code to train and analyze the recommendation system that we develop, and provide documentation with the code. Guidelines:• The answer NA means that the paper does not release new 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.Of course, this need not be the platform's utility: in general the platform might receive utility rij if user i selects recommended item j.Again we could take w I ij = bj for some bj > 0, but this would have equivalent normalized item utilities.Used under license CC0 Public DomainUsed under the Semantic Scholar API License AgreementLicensed under the Apache License, Version 2.0While there is a single optimal solution x, y to Problem 6 for each α, there may be two t that satisfy Lemma 4. In particular, this occurs when for each j, xj = 0 or yj = 0. By contrast, t(α) is unique. 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: .
limitations: limitations: .
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. Limitations of the definition of fairness: the paper focuses mainly on minimized fairness indicators. Have other indicators of fairness been considered?
2 No specific methodology is given for actually achieving the three balances
3. The thesis assumes that the utility of users and items is symmetric, which may not always hold in reality.
questions: 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?
2. 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.
3. 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: 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.
2. Limitations of the fairness definition: it focuses mainly on minimized fairness metrics and does not consider other possible fairness measures (e.g. group fairness).
paper_summary: paper_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.

---

I have read the rebuttal and other reviews. My rating is unchanged.
strength_weakness: strength_weakness: 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.
questions: 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.

The 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: limitations: n/a
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The model and framework used in this paper would require significantly more justification. More specifically, 
- 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?
- 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.) 
- 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?

2. The theoretical results of this paper do not have sufficient technical contributions. For example,
- Proposition 2 basically uses the properties of BFS in LPs. 
- 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.

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

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

Overall, I think this work would require significantly more work in both its model and results and would recommend rejection.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.

Comments: title: Thanks
comment: Thanks to the authors for the response. I keep my positive score.
I have read the rebuttal and other reviews. Still, I think this is a solid work and will leave my rating (7-accept) unchanged
I have read the rebuttal
Dear reviewer:

I am another reviewer and an engineer who work in industrial RS. I would like to answer your question.
"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?"

In recommendation system, the key goal is to serve most user the item she want. The "platform's recommendation quality" could be evaluated in two perspectives: 1) is the users as a whole group satisfied? namely  the "user utilities" defined in line 135. 2) is every individual satisfied? In other world, maximize the user utilities of the least satisfied user, ie, "minimum user utilities" defined in this paper. 

In industrial system, we care about both the overall recommendation quality (point 1) and the recommendation quality for each user (point 2). Actually, if the least satisfied user is satisfied, the overall recommendation quality should be ok, although not optimal.

While whether an item get enough chance to be seen, is not the key concern of commercial RS. Bad item should naturally be less shown to users. Thus, "treating user/item fairness in the same fashion" does not make sense. A reasonable formulation is to treat recommendation quality as objective, while item fairness as constrain.