Interpolating Item and User Fairness in Multi-Sided Recommendations

Authors: qinyi  chen
jason  cheuk
nam  liang
negin  golrezaei
djallel  bouneffouf
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:26:00

Abstract: Today's online platforms heavily lean on algorithmic recommendations for bolstering user engagement and driving revenue. However, these recommendations can impact multiple stakeholders simultaneously---the platform, items (sellers), and users (customers)---each with their unique objectives, making it difficult to find the right middle ground that accommodates all stakeholders. To address this, we introduce a novel fair recommendation framework, Problem (FAIR), that flexibly balances multi-stakeholder interests via a constrained optimization formulation. We next explore Problem (FAIR) in a dynamic online setting where data uncertainty further adds complexity, and propose a low-regret algorithm FORM that concurrently performs real-time learning and fair recommendations, two tasks that are often at odds. Via both theoretical analysis and a numerical case study on real-world data, we demonstrate the efficacy of our framework and method in maintaining platform revenue while ensuring desired levels of fairness for both items and users.

Main paper: 
 introduction: 
 Online recommendation systems have become essential components of various digital platforms and marketplaces, playing a critical role in user experience and revenue generation. These platforms usually operate as multi-sided entities, recommending items (services, products, contents) to users (consumers). Examples include e-commerce (Amazon, eBay, Etsy), service platforms (Airbnb, Google Local Services), job portals (LinkedIn, Indeed), streaming services (Netflix, Spotify), and social media (Facebook, TikTok). On the platform, there are typically two main groups of stakeholders: items (products, services, contents) and users (those engaging with items), with the platform itself acting as an independent stakeholder due to its unique objectives. However, as these platforms play a more vital role in societal and economic realms, fairness concerns have prompted increasing regulatory action. Notably, the European Union proposed the Digital Markets Act [54] , which emphasizes the need for contestable and fair markets in the digital sector, designating recommendation systems as a key area of focus; the U.S. Algorithmic Accountability Act [47] requires companies to assess the impacts of their automated decision systems to ensure they are not biased or discriminatory. It has also become increasingly evident, to the platforms, that upholding fairness across their stakeholder groups not only strengthens relationships with these stakeholders, but also enhances long-term platform sustainability [67] .Fairness concerns within digital platforms significantly impact both users and items, manifesting in various forms of disparities. For users, issues like racial discrimination in Airbnb's host-guest matching [25] and gender disparity in career ads [43] highlight the critical need for enforcing user fairness. Similarly, items on the platforms also experience unfair allocation of opportunities induced by algorithmic decisions, such as e-commerce platforms favoring their own private-label products [19] and social media prioritizing influencers' contents over others [63] , indicating a disparity that affects items (sellers, content creators) alike. These underscore the necessity to address biases and create a more inclusive environment for all stakeholders involved. Despite the many efforts by companies to mitigate fairness issues, most of the existing measures solely focus on one stakeholder group, sometimes even at the expense of another. For example, Airbnb has implemented strategies to mitigate racial discrimination among its users [4] , yet their listings of comparable relevance might still not receive similar levels of visibility. Etsy implements measures to promote market diversity and supporting new entrants, which contributes to equality of opportunities for its items (sellers) [27, 13] ; however, such a strategy may inadvertently disadvantage users by potentially overwhelming them with choices and hindering their ability to quickly find their preferred products. Similar to industrial practices, the majority of ongoing research on fairness in recommender systems (e.g., [13, 55, 71] ) also focus solely on either users or items, but seldom both.Addressing multi-sided fairness is inherently complex due to the competing interests and objectives of different stakeholders [39, 12] . If algorithms solely prioritize the platform's profits, this can lead to inequitable exposure for those more niche items and users who prefer them. In addition, what users perceive as fair may be viewed as unfair by items, and vice versa [16] .In face of these challenges, our work aims to answer the following two questions: (1) What constitutes a fair recommendation within a multi-sided platform? and (2) How would a platform implement a fair recommendation in a practical online setting? Our contributions are summarized as follows:1. A novel fair recommendation framework, Problem (FAIR). Our fair recommendation problem, framed as a constrained optimization problem, adopts a novel multi-sided perspective that first achieves within-group fairness among items/users, and then enforces cross-group fairness that addresses the trade-offs across groups. Notably, Problem (FAIR) enables the platform to (i) flexibly define fair solutions for items/users rather than relying on a single predefined notion (see Section 2.2); (ii) adjust trade-offs between its own business goals and fairness for stakeholders (see, e.g., our case study in Section 4); (iii) flexibly accommodate additional operational considerations. 2. A Fair Online Recommendation algorithm for Multi-sided platforms (FORM). In Section 3,  we study an online setting where the platform must ensure fairness for a sequence of arriving users amidst data uncertainty. We present FORM, a low-regret algorithm tailored for fair online recommendation, whose efficacy is further validated via a real-world case study (Section 4). The design of FORM contributes both methodologically and technically. (i) Methodologically, contrary to prior works (e.g., [55, 71] ) that treats learning and enforcing fairness as two separate tasks, we recognize that these two tasks, when conducted simultaneously, are often at odds. FORM well balances learning and fairness via properly relaxing fairness constraints and introducing randomized exploration. (ii) Technically, FORM overcomes a non-trivial challenge of managing uncertain fairness constraints when solving a constrained optimization problem in an online setting with bandit feedback. While existing works on online constrained optimization all would require certain access to constraint feedback (see discussion in Section 1.1), our setup disallows even verifying the satisfaction of item/user fairness constraints, demanding novel design in FORM.Our work primarily contributes to the emerging area of algorithmic fairness in recommender systems. Additionally, from a technical aspect, our algorithm contributes to the field of constrained optimization with bandit feedback. We highlight the literature most relevant to our work in both areas.Algorithmic fairness in recommender systems. Algorithmic fairness is an emerging topic [8, 2, 42] explored in various contexts such as supervised learning [14, 24] , resource allocation [9, 37] , opportunity allocation [36] , scheduling [50] , online matching [46] , bandits [6] , facility location [34] , refugee assignment [29] , assortment planning [17] , online advertising [21] , search [5] , and online combinatorial optimization [32] . Our research is primarily aligned with works investigating fairness in recommender systems; see [67, 20] for comprehensive surveys.The prior works on fairness in recommender systems can be categorized into three streams based on their subjects: item fairness, user fairness and joint fairness. Item fairness focuses on whether the decision treats items fairly, including fair ranking and display of search results [73, 11, 48, 10, 60, 66, 17, 72] , similar prediction errors for items' ratings [57] , and long-term fair exposure [31] . User fairness examines whether the recommendation is fair to different users, encompassing aspects like similar recommendation quality [26, 45, 68] and comparable explainability [30] across users.The third stream, also the stream that our work fits in, focuses on joint fairness that concerns whether both items and users are treated fairly. However, the number of works in this stream remain scarce, as dependency on θ whenever the context allows. Later, we will transition to an online setting where the problem instance θ becomes unknown (see Section 3) reestablish the dependency in our discussion.Here, we focus on a single-item recommendation setting, where the platform highlights one item to each arriving user. This approach applies to various real-world scenarios, such as Spotify's "Song of the Day", Amazon's "Best Seller", Medium's daily "Must-Read" article, etc. Later in Section 3.6 and our case study on Amazon review data in Section 4, we will show that the core concepts of our model and approach can naturally extend to recommending an assortment of items.2.2 Single-Sided Fair Solutions: Within-Group Fairness for Items and UsersTo properly address multi-sided fairness, we begin by first considering within-group fairness. That is, we seek to answer: what constitutes a fair solution within our item/user group? To address this question, it is important to understand the different outcomes that items and users respectively care about, and the fairness notions they would like to consider.Single-Sided Item-Fair Solutions. Let O I i (x) be the expected outcome received by item i at a round with recommendation probabilities x. We let O I i (x) take the following general form:O I i (x) = L ⊤ i,: x i,: , where L = (L i,j ) i∈[N ] j∈[M ]and L i,j can be any proxy for the expected outcome received by item i from type-j user if it gets offered. One can consider any of the following metrics or their weighted combinations as the item's outcome: (1) visibility: L i,j = p j and O I i (x) = j p j x i,j ; (2) marketshare: L i,j = p j y i,j and O I i (x) = j p j y i,j x i,j ; (3) expected revenue: L i,j = r i p j y i,j and O I i (x) = j r i p j y i,j x i,j . For items, a common way to achieve fairness is via the optimization of a social welfare function (SWF), denoted as W , which merges fairness and efficiency metrics into a singular objective (see [18] ). The maximization of SWF can incorporate a broad spectrum of fairness notions commonly adopted in practice, including maxmin fairness [58] , Kalai-Smorodinsky (K-S) bargaining solution [41] , Hooker-Williams fairness [37] , Nash bargaining solution [53] , demographic parity, etc. (See Section A.2 for an expanded discussion of these fairness notions and their social welfare functions.)To preserve the generality of our framework, we let the platform freely determine the outcome function and fairness notion for items, by broadly defining the item-fair solution as follows.Definition 2.1 (Item-Fair Solution) Given items' outcome matrix L(θ), and a SWF W : ∆ M N → R, an item-fair solution is given by:f I ∈ arg max x∈∆ M N W (O I (x)).One popular fairness notion that can be captured by Definition 2.1 is maxmin fairness, which ensures that the most disadvantaged item is allocated a fair portion of the outcome. A few prior works [55, 72] on fair recommendation solely focus on achieving maxmin fairness for the visibilities (exposure) received by the items. Our model, however, can flexibly accommodate any outcome functions as listed above and any fairness notions supported via SWF maximization (see Section A.2).Single-Sided User-Fair Solutions. Let O U j (x) be the expected outcome received by a type-j user at a round with recommendation probabilities x. We again let O U j (x) take a general form:O U j (x) = U ⊤ :,j x :,j , where U = (U i,j ) i∈[N ] j∈[M ]and U i,j is the expected outcome received by a type-j user if offered item i. Here, the specific form of the user's outcome matrix U (θ) is determined by user's utility model, which can vary depending on contexts. See Section A.1 for some example forms of U (θ) based on discrete choice models (multinomial logit (MNL), probit) used in demand modeling [65] and valuation-based models used in online auction design [51] . For generality, we do not impose restrictions on the form of U (θ), but merely assume knowledge of it.For users, achieving fairness is more straightforward. Since the platform can personalize recommendations based on user types, given the users' outcome matrix U (θ), it is best for type-j users to consistently receive the item that offers the highest utility. We thus define the user-fair solution as: Definition 2.2 (User-Fair Solution) Given users' outcome matrix U (θ), the user-fair solutionf U ∈ ∆ M N is given by f U i,j = 1 if i = arg max i U i,j and f U i,j = 0 otherwise, for all i ∈ [N ], j ∈ [M ]. 
drawbacks of a single-sided solution: 
 While a single-sided (fair) solution for one stakeholder group can be straightforward to identify, a recommendation policy that solely benefits a single stakeholder group (platform, items, users) could result in extensive costs for the rest of the stakeholders, as suggested by the following proposition.Proposition 2.1 Let ϵ 1 = min y/ max y, ϵ 2 = min U / max U , and ϵ = max{ϵ 1 , ϵ 2 , 1/N }. There exists a problem instance such that: (1) The platform's revenue-maximizing solution results in zero outcomes for some items and all users attaining only ϵ of their maximum attainable outcome. (2) The item-fair solution leads to the platform receiving at most 2ϵ of its maximum attainable revenue and any user achieving at most 2ϵ of their maximum attainable outcome. (3) The user-fair solution results in zero outcomes for some items and the platform receiving ϵ of its maximum attainable revenue.Proposition 2.1 shows that single-sided solutions that can lead to extremely unfair outcomes for some stakeholders under certain scenarios. This motivates us to investigate the concept of cross-group fairness in the following section, where we aim to balance the needs of all stakeholders.2.4 Multi-Sided Solutions: From Within-Group Fairness to Cross-Group FairnessIn this section, we proceed to investigate the concept of cross-group fairness by proposing a fair recommendation framework, Problem (FAIR). Specifically, we seek to answer the following: what constitutes a fair recommendation policy across all stakeholder groups on a multi-sided platform?The platform, our main stakeholder, primarily wishes to optimize its expected revenue, denoted by REV(x) = i,j r i p j y i,j x i,j . Whenever a type-j user arrives, a revenue-maximizing platform with full knowledge of the instance would show the most profitable item, i.e., i ⋆ j = arg max i∈[N ] r i y i,j , with probability one. We let OPT-REV = max x REV(x) be platform's maximum attainable expected revenue in the absence of fairness. Such a deterministic revenue-maximizing approach, as shown in Section 2.3, is evidently undesirable for the less profitable items and any user who prefer them.To create a fair ecosystem, the platform wishes to impose certain levels of fairness for all items/users. In an offline setting with full knowledge of the instance θ, the platform can first compute item-fair and user-fair solutions f I , f U and solve the following fair recommendation problem, Problem (FAIR), to prioritize its revenue maximization goal, while achieving cross-group fairness via fairness constraints:EQUATIONwhere δ I , δ U ∈ [0, 1] are the fairness parameters for items and users respectively. Here, the item/user fairness constraints ensure that the outcome received by any item/user is at least of a certain proportion of the outcome that they would otherwise receive under their within-group fair solution. One can think of δ I and δ U as tunable handles that the platform can adjust to regulate the tradeoff between fairness and its own revenue (see how a platform can tune these parameters in practice in Sections 4 and C). If a platform wishes to incorporate other operational considerations such as diversity constraints (x min ≤ x i,j ≤ x max ) or fairness for more stakeholder groups beyond items/users (e.g., DoorDash drivers, Airbnb hosts), additional constraints can be incorporated in a similar fashion.We let x ⋆ denote the optimal solution to Problem (FAIR), which serves as the benchmark that we compare our algorithm against when we next work with the online setting (see Section 3).Remark 2.1 (Constrained optimization versus fairness regularizers) An alternative method of integrating fairness is to use fairness regularizers (i.e., Lagrangian multipliers) and optimize a weighted sum of platform's revenue and items'/users' outcomes. Nonetheless, our constrained optimization formulation offers several clear benefits: (i) while it is possible to translate our constrained optimization formulation into a weighted sum with fairness regularizers via dualization, the reverse process is not straightforward; (ii) our fairness parameters δ I , δ U are directly interpretable; (iii) our framework accommodates additional operational considerations, with results remaining valid.Remark 2.2 (Selecting fairness parameters via "price of fairness") To choose the right fairness parameters δ I , δ U , it is important to understand both (i) the extent of fairness needed for items/users, and (ii) the cost of implementing fairness constraints to balance its revenue and stakeholder interests, often known as the "price of fairness" (PoF). In Section C, we investigate the concept of PoF under our framework (Problem (FAIR)), and show a piecewise linear dependency of the PoF on both (i) the amount of misalignment in the platform's and its stakeholders' objectives, (ii) the fairness parameters δ I , δ U (see Thoerem C.1). We further provide guidelines on how a platform can effectively tune its fairness parameters based on its desired fairness level and acceptable PoF via online A/B experimentation (see Section C for an extended discussion).3 Fair Online Recommendation Algorithm for Multi-Sided PlatformsIn practice, user data are often missing or inaccurate, so solving Problem (FAIR) with flawed data could inadvertently result in unfair outcomes. Our online setting (Section 3.1) allows the platform to improve its estimates of user data via a data collection process over time. However, this simultaneous process of learning to be fair and understanding user preferences also introduces new challenges. In this section, we address the more intricate online setting and introduce an algorithm for this scenario.EQUATIONwhere τ j,k ∈ [T ] denote the round at which the kth type-j user arrives.Solve a relaxed version of Problem (FAIR) under the estimated instance. Recall, from our first challenge, that we cannot directly verify if the fairness constraints have been satisfied due to having data uncertainty and partial feedback. If the platform solves Problem (FAIR) using the estimated instance, the flaw in estimation could easily lead to failure of maintaining fairness for some stakeholders. In face of this, FORM solves a relaxed version of Problem (FAIR), defined as follows:max x∈∆ M N REV(x, θt) s.t. O I i (x, θt) ≥ δ I • O I i (f I ( θt), θt) -ηt ∀i ∈ [N ] O U j (x, θt) ≥ δ U • O U j (f U ( θt), θt) -ηt ∀j ∈ [M ] . (FAIR-RELAX( θt, ηt))where θt is the estimated instance at round t and η t > 0 is a parameter that regulates the magnitude of relaxation on our fairness constraints (Eq. ( 1)). Here, Problem (FAIR-RELAX( θt , η t )) differs from Problem (FAIR) in that (i) it uses the estimated instance θt rather than the ground-truth instance θ, and (ii) it relaxes all fairness constraints by the amount of η t . At a high level, the relaxation here ensures that the solution fair to all stakeholders (i.e., x ⋆ ) would be captured even under data uncertainty. The magnitude of relaxation η t depends on Γ y,t and Γ p,t , which are respectively confidence bounds associated with estimated purchase/arrival probabilities (see Definition D.1). As our estimates become more accurate, both confidence bounds shrink, hence decreasing the magnitude of fairness relaxation.Recommend with randomized exploration. In order to handle the second challenge of some items being inadequately explored, we incorporate randomized exploration by sampling from a distribution that perturbs the estimated solution to Problem (FAIR), xt , by a carefully tailored amount ϵ t . This allows ongoing exploration of all items, with the magnitude of exploration ϵ t also decreasing over time as our parameter estimates improve, shifting from exploration towards greater exploitation.Unbiased estimators for our problem instance. In Algorithm 1, for simplicity, we estimate purchase probabilities y using an inverse probability weighted estimator and estimate arrival probabilities p with the sample mean (See Eq. ( 2)). For sufficiently large t, our estimates ŷt and pt will be accurate with high probability (see Lemma D.2). In practice, the platform, potentially with access to historical data, can freely use any learning mechanism that yield unbiased estimators for user preferences and arrival rates. As long as the estimates get sufficiently accurate over time with high probability, FORM would ensure low revenue/fairness regrets, all while keeping the rest of its design unchanged.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We have clearly stated the assumptions needed for our theoretical results, the computational complexity of the proposed algorithm, and the setups adopted for our numerical experiments. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • 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. 
online setting and goals: 
 In an online setting, the platform no longer has prior knowledge of user preference y and arrival rates p. At each round t, some non-anticipating algorithm A generates the recommendation probabilities x t ∈ ∆ M N , only based on past recommendation {x t ′ } t ′ <t and purchase decisions {z t ′ } t ′ <t . After observing the type of the arriving user J t , the platform offers item i with probability x t,i,Jt . Following this recommendation, the platform only observes the user's binary purchase decision z t ∈ {0, 1} for the offered item. We will measure the performance of our algorithm using the following metrics: R(T ) = 1 T T t=1 REV(x ⋆ , θ) -REV(x t , θ) and R F (T ) = max{R I F (T ), R U F (T )} , where R I F (T ) = max i 1 T T t=1 (δ I •O I i (f I (θ), θ)-O I i (x t , θ)) + and R U F (T ) = max j 1 T T t=1 (δ U • O U j (f U (θ), θ) -O U j (x t , θ)) +are respectively the maximum time-averaged violation of item/user-fair constraints. Here, REV(x, θ) = i,j r i p j y i,j x i,j is platform's expected revenue under instance θ;O I i (x, θ) = L i,: (θ) ⊤ x i,:and O U j (x, θ) = U :,j (θ) ⊤ x :,j are the item/user outcomes under θ; f I (θ) and f U (θ) are the item/user-fair solutions w.r.t. L(θ), U (θ) and SWF W , per Definition 2.1 and 2.2.Observe that in Definition 3.1, we reintroduce the dependency of our variables on the instance θ. This is because in the online setting, we typically work with an estimated instance, which in turn impacts our estimates for the platform's revenue, item/user outcomes as well as item/user-fair solutions.Before proceeding, we highlight the two main challenges unique to the online setting.(1) Data uncertainty and partial feedback can interfere with evaluating fairness. Due to lack of knowledge of the instance θ and limited feedback (as we only observe the purchase decision for the offered items), it is difficult to assess the quality of our recommendations x t at each round. In particular, verifying whether our fairness constraints are satisfied and/or measuring the amount of constraint violations require evaluating the item/user-fair solutions f I (θ), f U (θ) and item/user outcomesO I i (f I (θ), θ), O I i (x t , θ) and O U j (f U (θ), θ), O U j (x t , θ), all of which heavily depend on θ. This sets our work apart from prior works on fairness in recommender systems, which assume full knowledge of the problem instance (e.g., [55, 71] ), and from works on constrained optimization with bandit feedback (e.g., [38, 15, 61] ), which rely on the availability of constraint feedback. As we discussed in Section 1.1, the latter works need to access the amount of constraint violation or verify constraint satisfaction after each decision to update their policies. For example, in online learning with knapsack, the constraint is a resource budget, so constraint violations can be directly evaluated. Our work contributes to the literature on constrained optimization with bandit feedback by directly handling uncertain constraints and providing a sublinear regret bound (see Theorem 3.1).(2) Fairness can interfere with the quality of learning. To ensure fairness for all stakeholder groups, some items (e.g., low-revenue or low-utility items) would necessarily receive lower recommendation probabilities than the others. Nonetheless, if we barely offer these items to the users, the lack of exploration could also lead to poor estimation for their purchase probability.We now present our algorithm, called FORM (Fair Online Recommendation algorithm for Multi-sided platforms), which handles the aforementioned challenges by adopting a relaxation-then-exploration technique, allowing it to achieve both low revenue regret and fairness regret. The design of FORM is outlined in Algorithm 1, consisting of the following.Algorithm 1 Fair Online Recommendation Algorithm for Multi-Sided Platforms (FORM)Input: (i) N items with revenues r ∈ R N , item outcome L(θ) : Θ → R N ×M , item SWF W : ∆ M N → R; (ii) M types of users with user outcome U (θ) : Θ → R N ×M ; (iii) fairness parameters δ I , δ U ∈ [0, 1]. 1. Initialization. Set ŷ1,i,j = 1/2 and pj = 1/M for i ∈ [N ], j ∈ [M ]. Let the magnitude of exploration be ϵt = min N -1 , N -2 3 t -1 3, and define the magnitude of relaxation asEQUATIONwhere Γy,t = 2 log(T )/ ϵt • max{1, t/log(T ) -t log(T )/2} and Γp,t = 5 log(3T )/t. We theoretically analyze the performance of FORM, under a mild local Lipschitzness assumption.Assumption 3.1 Given instance θ ∈ Θ, there exists constants B, ζ > 0 such that for any θ ∈ Θ where ∥ θ -θ∥ ∞ ≤ ζ, max{∥U (θ) -U ( θ)∥ ∞ , ∥f I (θ) -f I ( θ)∥ ∞ } ≤ B∥θ -θ∥ ∞ .Assumption 3.1 is well justified in practice. In terms of users' outcome matrix, the assumption readily holds for all prevalent users' choice models and valuation-based models (see examples in Section A.1) as long as θ is bounded away from the boundaries of Θ. For item-fair solutions f I (θ), a wide range of standard outcome functions (visibility, revenue, etc.) and fairness notions (maxmin, K-S, etc.) readily induce locally Lipschitz item-fair solutions; see Section A.3 for some examples.Theorem 3.1 is the main result of this section, which states that FORM achieves both sublinear revenue regret and fairness regret, as desired. The proof of Theorem 3.1 is deferred to Section D.Theorem 3.1 (Performance of FORM) Given any problem instance θ ∈ Θ and assume that Assumption 3.1 holds, for T sufficiently large, we have that• the revenue regret of FORM is at most E[R(T )] ≤ O(M N 1 3 T -1 3 ); • the fairness regret of FORM is at most E[R F (T )] ≤ O(M N 1 3 T -13 ).In terms of the computational complexity of FORM, the dominant runtime cost in each iteration of FORM arises from solving Problem (FAIR-RELAX( θt , η t )). Note that for a wide variety of commonly used item-fairness notions (e.g., maxmin, K-S, demographic parity; see ). In practice, however, much better performance can often be achieved by advanced LP solvers such as Gurobi and CPLEX.For real-world deployments, FORM can be further adapted with scalability in consideration. First, in practice, there is no need to solve Problem (FAIR-RELAX( θt , η t )) at every user arrival. Instead, platforms can resolve the problem after a given number of user arrivals or periodically at fixed time intervals, while updating user data in real-time. This allows majority of the iterations to run in O(M N ) time and removes the computational overhead. 4 Second, we do not always encounter a large-scale optimization problem when applying our framework. Real-world recommendation systems often narrow down items through lightweight pre-filtering stages based on criteria like keywords or price range (e.g., [49] ), allowing us to enforce fairness within smaller, context-specific subsets. Our fairness framework is also particularly impactful at this final stage, where items with similar attributes compete for visibility and a revenue-maximizing strategy could lead to extremely unfair outcomes.Our framework, Problem (FAIR), and the proposed algorithm can be extended to accommodate other variations of our setup. Below, we briefly introduce these extensions; see Section E for more details.Periodic arrivals. While our current model focuses on stochastic arrivals with fixed user arrival probabilities p, real-world recommendation systems often observe non-stationary user arrivals with hourly, daily or weekly periodicity. In Section E.1, we show that by additionally integrating a sliding window mechanism, FORM can seamlessly accommodate periodic arrivals, and attain the sameO(M N 1/3 T -1/3) guarantees for both revenue and fairness regrets.Recommending an assortment. As remarked in Section 2, while our model adopts a single-item recommendation setting, the high-level ideas behind our framework/method naturally extend to recommending an assortment of size at most K. To extend our framework, Problem (FAIR), we will let {q j (S) :S ∈ [N ], |S| ≤ K, j ∈ [M ]} be the decision variables, where q j (S) is the likelihood of proposing assortment S to a type-j user. We can then apply the same relaxation-then-exploration techniques to solve the fair recommendation problem in a dynamic online setting. See Section E.2 for details of our extension. In the case study that follows (Section 4), we also validate the efficacy of our framework/method in a real-world assortment recommendation problem. 
case studies on amazon review data: 
 In our case study on Amazon review data, we act as an e-commerce platform displaying featured products to incoming users, aiming to maximize revenue while ensuring fairness for items and users.Our experiments numerically validate the efficacy of our framework/method. All algorithms were implemented in Python 3.7 and run on a MacBook with a 1.4 GHz Quad-Core Intel Core i5 processor.Data and setup. We use an Amazon review dataset [71] from the "Clothing, Shoes and Jewelry" category. Product reviews provide relevance scores between each item and user, serving as a proxy for purchase likelihood. Users are classified into M = 5 types using matrix factorization and k-means clustering on user feature vectors. The arrival probability p j is set to the proportion of type-j users.We select N = 30 items with the highest variance in relevance scores across user types, indicating a discrepancy between item and user interests and making this a challenging instance. Item revenues r i are uniformly drawn from [0.5, 1.5]. The purchase probability and users' utilities are defined based on the multinomial logit (MNL) model [65] . For a type-j user presented with assortment S, the probability of purchasing item i ∈ S is y i,j = e v i,j 1+ i ′ ∈S e v i ′ ,j , where v i,j is the relevance score. The user's perceived utility is log(1 + i ′ ∈S e v i ′ ,j ). Each instance simulates T = 2000 user arrivals. Upon arrival, each type-j user is shown an assortment S of up to K = 3 items. The platform's primary goal is to maximize its revenue while ensuring maxmin fairness for items w.r.t. item revenue, and fairness for users w.r.t. utilities from the MNL model. We apply the extension of FORM for recommending assortments, using relaxation-then-exploration techniques to produce fair recommendations while learning user data (see Section E.2). To establish generality of our framework/method, we have also performed additional experiments under alternative outcomes and fairness notions (see Section F.2) and an alternative movie recommendation setting using MovieLens data (see Section F.3). In all cases, our experiments yielded consistent results.Baselines. We consider six baselines for comparisons. Since all baselines assume full knowledge of the instance and lack a learning phase, we let them use our unbiased estimator to update their estimated instance as they observe purchase decisions, and recommend based on these estimates. (i) greedy: offers K items with the highest expected revenue, prioritizing platform's goal; (ii) max-utility: offers K items with the highest user utilities, a user-centric approach; (iii) min-revenue: offers K items generating the least revenue so far, promoting maxmin fairness for items w.r.t. revenue; (iv) random: offers K items uniformly at random, promoting maxmin fairness for items w.r.t. visibility; (v) FairRec [55] : an algorithm that addresses two-sided fairness in a static setting. While it's not designed for online settings, we adapt it for online arrivals by duplicating users and using the singleshot recommendation solution. It ensures maxmin fairness for item visibility and envy-free fairness for users; (vi) TFROM [71] : addresses two-sided fairness in an online setting, focusing on uniform item visibility and similar user normalized discounted cumulative gain. However, neither FairRec nor TFROM considers platform's revenue; see Section F.1 for more details on these two baselines. Platform's revenue. We first assess FORM's efficacy in achieving a low-regret solution. Figure 1a shows that the time-averaged revenue of FORM, i.e., 1 T T t=1 REV(x t ), converges rapidly to the optimal revenue for Problem (FAIR), complementing Theorem 3.1. Figure 1b compares the timeaveraged revenue (normalized by OPT-REV) of FORM with other baselines. As expected, greedy achieves revenue close to OPT-REV, while all other baselines result in significant revenue loss. FairRec and TFROM, in particular, reduce platform revenue by about 38% as their sole focus is on ensuring two-sided fairness. In contrast, FORM offers tunable parameters to balance platform and stakeholder interests. As shown in Figure 1b , adjusting δ I and δ U allows platforms to control revenue loss (e.g., choosing δ I , δ U = 0.2 keeps loss within 10%). See, also, Section C for how a platform can tune fairness parameters to control its "price of fairness" in practice.Item and user fairness. Figure 1c shows average outcomes for each item i, normalized by the outcome under item-fair solution, max{ 1T O I i (x t )/O I i (f I ), 1}.As expected, since our item-fair solution f I adopts maxmin fairness w.r.t. item revenues, min-revenue achieves the highest level of item fairness, though at a high cost to the platform. Methods such as random, FairRec, TFROM also achieve high item fairness but with some discrepancies in maximum and minimum item outcomes. greedy and max-utility show extremely skewed allocations, with some items receiving minimal or no revenue. In comparison, our algorithm FORM strikes a good balance, ensuring all items nearly attain or surpass the specified fairness levels, whether the level is high (δ I = 0.8) or moderate (δ I = 0.2).Figure 1d shows the average outcomes for each user type, normalized by their outcome under the user-fair solution,max{ 1 T O U j (x T )/O U j (f U ), 1}.In the Amazon review data, user interests align well with the platform's objectives (as validated in Section C), leading to most baselines performing fairly well and achieving high levels of fairness for the users. FORM again ensures good user outcomes, all while maintaining high platform revenue and desired item fairness levels. 
conclusion and future directions: 
 Our work introduced a novel fair recommendation framework that maintains platform revenue while addressing multi-stakeholder fairness, as well as a low-regret algorithm that effectively produces fair recommendations amidst data uncertainty. It is worth noting that the high-level ideas behind our versatile framework has the potential to be applied in settings beyond recommender systems, such as dynamic pricing and online advertising, ensuring fairness across different stakeholders and promoting stable market conditions in these applications.There are several future directions worth investigating. (i) Our current framework calibrates recommendation policies within a shorter time period when user preferences and item attributes are relatively fixed. Future research can explore long-term effects of our method by developing adaptive fairness notions that account for evolving user and item attributes and quantifying the long-term multi-stakeholder fairness. (ii) It'd be interesting to pursue real-world deployments of our framework/algorithm and evaluate their impact using an expanded set of metrics, such as user satisfaction, retention rates, and recommendation diversity. 
experiments compute resources: 
 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: As stated in Section 4, all algorithms were implemented in Python 3.7 and run on a MacBook with a 1.4 GHz Quad-Core Intel Core i5 processor.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?Answer: [Yes] Justification: This paper conforms, in every respect, with the NeurIPS Code of Ethics.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]• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • 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. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.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. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects. 
 
 Appendix: A Example Choices of Outcomes, Fairness Notions and Fair Solutions A.1 Example Utility Functions Below are some common example utility functions U (θ) based on common discrete choice models (multinomial logit (MNL), probit) used in demand modeling [65] and valuation-based models used in online auction design [51] . For all of these examples, U i,j is strictly increasing w.r.t. the purchase probability y i,j .• Multinomial logit (MNL) model. Let the utility of item i for a type j user be v i,j + ϵ i,j , where v i,j ≥ 0 and ϵ i,j is the random part drawn i.i.d. from the standard Gumbel distribution. Let ϵ 0,j be the utility of no-purchase option, again drawn i.i.d. from the standard Gumbel distribution. The expected utility is U i,j = E [max{v i,j + ϵ i,j , ϵ 0,j }] = log(1 + exp(v i,j )) + γ , where γ is the Euler-Mascheroni constant. The purchase probability is given by yi,j = P [v i,j + ϵ i,j > ϵ 0,j ] = exp(vi,j )1+exp(vi,j ) . Hence, the expected utility can be viewed as U i,j = log( 1 1-yi,j ) + γ. • Probit model. Let the utility of item i for a type j user again take the form of v i,j + ϵ i,j , where the random part ϵ i,j and the utility of the no-purchase option ϵ 0,j are drawn i.i.d. from a normal distribution N (0, σ). Here, the expected utilityU i,j = E [max{v i,j + ϵ i,j , ϵ 0,j }] = v i,j Φ vi,j √ 2σ + √ 2σϕ vi,j √ 2σ, where Φ(.) and ϕ(.) are the CDF and PDF of a standard normal distribution. The purchase probability is y i,j = Φ( vi,j √ 2σ ). We thus have U i,j = √ 2σΦ -1 (y i,j )y i,j + √ 2σϕ(Φ -1 (y i,j )) .• Valuation-based model. Let v i,j ∼ F i,j be the value of item i for a type j user, where F i,j is the distribution of v i,j . Then, y i,j = P[(v i,j -r i ) ≥ 0] and U i,j = E[(v i,j -r i ) + ], where r i is the price (revenue) of item i. If the valuations follow exponential distribution v i,j ∼ Exp(λ) for some λ > 0, we have purchase probability y i,j = exp(-λr i ) and expected utility U i,j = 1 λ exp(-λr i ) = y i,j /λ.Given a group of S stakeholders, each indexed by s ∈ [S], and any function that maps the platform's decision x to the stakeholders' outcome O(x) ∈ R S + , we can solve the following optimization problem to ensure that each of the S stakeholders are offered a fair outcome:f = arg max x W (O(x)) .where the social welfare function W determines which fairness notion we adopt. In Table 1, we list some example fairness notions commonly adopted in practice, as well as their corresponding social welfare functions W . Among them, we have • Maxmin fairness [58] : It maximizes the minimum outcome across all stakeholders, ensuring that the stakeholder with the least favorable outcome is as well-off as possible. • Kalai-Smorodinsky (K-S) fairness [41] : It seeks an equitable outcome where each stakeholder receives a proportional share of their maximum possible outcome. This is represented by a proportional allocation up to a common factor β. • Hooker-Williams fairness [37] : It aims to balance the efficiency/equity tradeoff using parameter ∆, by prioritizing stakeholders whose outcomes are within ∆ of the minimum outcome. • Nash bargaining solution: It maximizes the product of stakeholders' outcomes, ensuring an equitable distribution that reflects their relative negotiating power and achieves proportional fairness. • Demographic parity: It ensures that outcomes are equally distributed across different demographic groups, by minimizing the disparity in outcomes between a subset of stakeholders S ′ and the rest.See [18] for a comprehensive overview for all of the above fairness notions.Table 1 : Fairness notions and their social welfare functions (SWF).Maxmin fairness [58] mins Os(x)Kalai-Smorodinsky (K-S) fairness [41] s Os(x) • 1 {Os(x) = β maxx Os(x) for some β for all s} Hooker-Williams fairness [37] s max {Os(x) -∆, mins Os(x)}, for some ∆ ≥ 0 Nash bargaining solution [53] s log Os(x) demographic parity 1-1|S ′ | s∈S ′ Os(x)-1 S-|S ′ | s∈[S]\S ′ Os(x) , for some S ′ ⊂ [S]Choosing the right fairness notion is non-trivial and very much depends on the context. Some important considerations include:• Stakeholder needs and outcomes. Understanding the desired outcomes for items and users is crucial. Our framework, Problem (FAIR), is designed to handle various outcome functions (e.g., revenue, marketshare, visibility), which can differ across platforms. For example, a video streaming platform might aim to ensure fair visibility for both independent content creators and popular studios, while an e-commerce platform might focus more on fair marketshare/revenue for small sellers versus large brands. • Implication of fairness notion. Each fairness notion has a different implication, and platforms need to evaluate which best suits their goals and stakeholder needs. For example, maxmin fairness maximizes the outcome received by the most disadvantaged stakeholder, which can be ideal for video streaming platforms like Netflix or YouTube that wish to ensure independent and lesserknown content creators receive fair visibility alongside popular creators. K-S fairness ensures that each individual receives a fair share of his/her maximum attainable outcome. This can be suitable for platforms like LinkedIn or Indeed that wish to ensure fair opportunities for their job seekers relative to their qualifications and experience. Platforms may also need to experiment with different fairness notions to understand how their choices impact their "price of fairness" (see discussion in Section C). • Regulatory requirements. As we discussed in Section 1, one important motivation for imposing fairness in online recommendations is the increasing regulatory action. Therefore, the choice of fairness notions can also depend on legislative or regulatory requirements. For example, since the Digital Markets Act [54] calls for a fair and open digital marketplace, maxmin fairness can be potentially suitable as it ensures even the most disadvantaged item receive a fair level of exposure.In this section, we discuss a number of item-fair solutions that adopt different outcome functions and fairness notions, and show that they satisfy Assumption 3.1 in Section 3.4. In the following, we will assume that the item-fair solution satisfies the following condition:Condition A.1 Under problem instance θ ∈ Θ, the item outcome L and the social welfare function W are chosen such that(i) L i,j is Lipschitz in θ for all i ∈ [N ], j ∈ [M ].(ii) The item-fair solution f I is unique.Note that statement (i) in Condition A.1 is satisfied by all of the common definitions of item outcome, such as (1) visibility: L i,j = p j ; (2) marketshare: L i,j = p j y i,j ; (3) expected revenue: L i,j = r i p j y i,j . On the other hand, the uniqueness condition can be achieved via adding regularization or lexicographic optimization to the social welfare function. In light of Condition A.1, we enumerate several item-fair solutions adopting prevalent fairness notions (see Section A.2 for definitions) such that local Lipschitzness is satisfied, as outlined in Assumption 3.1.Example 1: Item-Fair Solution with Maxmin Fairness. Suppose that an item-fair solution f I adopts maxmin fairness, f I would be the solution to the following linear program (LP):max x∈∆ M N ,z∈R z s.t. L ⊤ i,: x i,: ≥ z ∀i ∈ [N ] .Let θ = (p, y, r), θ = ( p, ỹ, r) ∈ Θ be two problem instances such that ∥θ -θ∥ ∞ ≤ ζ for some ζ > 0. We consider the two item-fair solutions enforcing maxmin fairness under the two problem instances. For simplicity of notation, we let f I = f I (θ) and f I = f I ( θ); L = L(θ) and L = L( θ).The item-fair solutions are obtained via the following:EQUATIONandEQUATIONWe note that ∥fEQUATIONConsider the region D = {(x, z) :L ⊤ i,: x i,: ≥ z for all i ∈ [N ], z ≥ z ⋆ }. Under Condition A.1, we know that (f I , z ⋆ ) is only feasible point in D.We can then invoke Lemma G.1 (with x = (f I , z ⋆ ) and x ′ = ( f I , z⋆ ) and the feasibility region D) to bound the distance between (f I , z ⋆ ) and ( f I , z⋆ ) using a Hoffman constant H > 0 and a constraint violation term:EQUATION)where the Hoffman constant can be characterized by invoking Lemma G.2 for the matrix defining region D.Now, let us bound the two terms (i.e. max i ∥(z ⋆ -L ⊤ i,:f I i,: ) + ∥ ∞ and (z ⋆ -z⋆ ) +), on the right-hand side of ( 6) respectively. Let us first denote E = ∥L -L∥ ∞ .To bound the first term, given that for all i ∈ [N ], f I satisfies L⊤ i,:EQUATIONTo bound the second term, let us additionally consider the following auxiliary problem:EQUATIONNote that if L ⊤ i,: x i,: ≥ z + M E, we must also have L⊤ i,: x i,: ≥ L ⊤ i,: x i,: -M E ≥ z. Hence, the feasibility region of Problem (8) is included in the feasibility region of Problem (4), which implies that ẑ⋆ ≤ z⋆ .On the other hand, note that Problem (8) is equivalent toEQUATIONif we perform change of variable z ′ = z + M E. This implies thatEQUATIONEquations ( 9) and ( 11) together imply thatEQUATIONFinally, combining Equations ( 5), ( 6), ( 7) and ( 12), we get∥f I -f I ∥ ∞ ≤ ∥(f I , z⋆ ) -( f I , z⋆ )∥ ∞ ≤ H • max{∥(z ⋆ -L ⊤ i,: f I i,: ) + ∥ ∞ , (z ⋆ -z⋆ ) + } ≤ H • M E = H • M ∥L -L∥ ∞ .By statement (i) in Condition A.1, we thus establish the local Lipschitzness of item-fair solution f I that enforces maxmin fairness.Example 2: Item-Fair Solution with Hooker-Williams Fairness. If the platform adopts an item-fair solution f I w.r.t. Hooker-Williams fairness with some given ∆ > 0 (see definition in Section A.2), f I would be the solution to a mixed linear integer program, with the following LP relaxation (it is shown that the LP relaxation describes the convex hull of the feasibility set; see [37] ):EQUATIONHere, ∆ > 0 is a constant that regulates the equity/efficiency tradeoff, and Γ can be any constant such that Γ ≥ L where L = ∥L∥ ∞ . We would fix Γ = 2M L + ∆ in the following.Let θ, θ ∈ Θ be two problem instances such that ∥θ -θ∥ ∞ ≤ ζ for some ζ > 0. For simplicity of notation, we let L = L(θ) and L = L( θ). Here, using the same techniques as in maxmin fairness, we let (f I , z ⋆ , v ⋆ , w ⋆ , δ ⋆ ) denote the solution to Problem (13) under the problem instance θ, and ( f I , z⋆ , ṽ, w, δ) denote the solution to Problem (13) under the problem instance θ. We can bound the difference in the two item-fair solutions similarly byEQUATIONwhere the second inequality follows from uniqueness of f I in Condition A.1 and applying Lemma G.1 to the feasibility region of Problem (13) with the additional constraint z ≥ z ⋆ . The argument here is similar to what we did for item-fair solution with maxmin fairness. Here, H is the Hoffman constant associated with Problem (13) under instance θ, which can be characterized using Lemma G.2.It suffices to bound the three terms on the right hand side of (14) . The first two terms can be bounded using similar techniques as done in the case of maxmin fairness. Using E = ∥L -L∥ ∞ and the fact that L⊤ EQUATIONLet ( f I , ẑ⋆ , v, ŵ, δ) denote the solution to Problem (13) . Consider the feasibility region of Problem (13) under the problem instance θ, which contains the feasibility region of Problem (15) . This then gives ẑ⋆ ≤ z⋆ .(16) We note that if we solve Problem (13) under problem instance, we claim that we must haveδ ⋆ i ≤ 1/2. This is because if δ ⋆ i > 1/2, we would have w + (Γ -∆)δ ⋆ i ≥ 2M Lδ ⋆ i > L ⊤ i,: f I i,: -∆δ i .That is, the upper bound in the third constraint is not tight, so the upper bound in the second constraint should be tight. However, setting δ ⋆ i = 1/2 would yield a better objective. Having this in mind, we choose ζ > 0 sufficiently small such that M E < 1 4 ∆ (this is doable since ℓ i (θ) is Lipschitz in θ. Then, Problem (15) is feasible. We note that (f I , ẑ, v, ŵ, δ ⋆ ) is a feasible solution to Problem (15) , where vi = v ⋆ i -M E and ŵ = w -M E, ẑ = z ⋆ -N M E. This is because under the optimal solution (f I , z ⋆ , v ⋆ , w ⋆ , δ ⋆ ) to Problem (13) , both upper bounds for v i should be tight (otherwise, there exists a δ that yields a better objective). We thus haveEQUATIONEquations ( 16) and ( 17) together give z ⋆ -z⋆ ≤ N M E , which bounds the third term in the right-hand side of (14) .Having established the bounds in the right-hand side of ( 14), we have shown that∥f I -f I ∥ ∞ ≤ H • N M E = H • N M ∥L -L∥ ∞By statement (i) in Condition A.1, we thus establish the local Lipschitzness of item-fair solution f I that enforces Hooker-Williams fairness.Example 3: Item-Fair Solution with Kalai-Smorodinsky (K-S) Fairness. To obtain item-fair solution f I under K-S fairness, we solve the following problem given problem instance θ:EQUATION)where L ⋆ i = j L i,j denotes the maximum outcome that item i can receive. Note that this is achievable if the platform always show item i regardless of the type of the arriving user.By similar arguments as in our discussion for maxmin fairness, we would get∥f U -f U ∥ ∞ ≤ H E min i L ⋆ i = H min i L ⋆ i • ∥L -L∥ ∞ .where H is the Hoffman constant that can be characterized by invoking Lemma G.2. By statement (i) in Condition A.1, we thus have the local Lipschitzness of item-fair solution f I that enforces K-S fairness.As we discussed in Section 2.3, if a platform adopts a recommendation that solely benefits a single stakeholder group, this could result in extensive costs for the rest of the stakeholders, including the platform itself. The following Example B.1 establishes Proposition 2.1, where we consider a problem instance with one highly popular item and another notably profitable item. Under such a problem instance, the perceptions of a "fair solution" can vary widely among different stakeholders.Example B.1 (A single-sided solution can be extremely unfair to the other sides.) Consider a problem instance with N items and M types of users. For i ∈ [M ], j ∈ [N ], let the probability of purchases y 1,j = 1 and y i,j = ϵ 1 where ϵ 1 ≪ 1 for all i ̸ = 1; probability of arrival p j = 1/M ; revenue r 2 = 1/ϵ 2 1 and r i = 1, for all i ̸ = 2. For simplicity, let the utility of the users U i,j = y i,j . Let ϵ = max{ϵ 1 , 1/N }. Under such a instance, we have the following.Platform's revenue-maximizing solution. A platform that seeks to maximize its revenue would always recommend item 2 to any arriving user, which yields expected revenue of 1/ϵ 1 ≫ 1. However, such a solution is extremely unfair for any items i ̸ = 2 that receive zero outcome. This is also unfair to all users, as they would receive utility 1 from item 1 but only receives utility ϵ 1 from item 2.An item-fair solution. Suppose items consider visibility as their outcome and adopts maxmin fairness, offering all items equal visibility x i,j = 1/N is an item-fair solution. However, this can be unfair for all users who prefers item 1, whose utility under the item-fair solution is 1/N + (N -1)/N ϵ 1 < 2ϵ. This is also unfair to the platform that prefers item 2, as its current revenue becomes1/N • 1/ϵ 1 + 1/N + (N -2)/N • ϵ 1 < 1/N • 1/ϵ 1 + 1 = 1/N • 1/ϵ 1 + ϵ 1 • 1/ϵ 1 ≤ 2ϵ • 1/ϵ 1 .A user-fair solution. A user-fair solution would always display item 1 to all types of users. Nonetheless, such a solution is extremely unfair to the rest of the items that receives zero outcome. It is also unfair to the platform, as always displaying item 1 results in expected revenue of 1, while if it displays item 2 it would gain 1/ϵ 1 .In this section, we formally characterize the conflicting interests among different stakeholders using a concept called the price of fairness, and show that our formulation of Problem (FAIR) provides the platform with flexible handles to find the right middleground.The concept of price of fairness was first introduced by [9] , which we formally define as follows.Definition C.1 (Price of Fairness) Given a problem instance θ ∈ Θ, an item-fair solution f I and a user-fair solution f U . We let OPT-REV = max x REV(x) be the maximum achievable expected revenue in the absence of fairness, and let FAIR-REV be the solution to Problem (FAIR). The price of fairness (PoF) is defined asPOF = OPT-REV -FAIR-REV OPT-REV.The price of fairness, which depends on the problem instance θ and (δ I , δ U ), quantifies the trade-off between item/user fairness and platform interests, where a lower value is favored by the platform. In Theorem C.1, we formally upper bound the price of fairness introduced by Problem (FAIR) when we interpolate item and user fairness with parameters δ I , δ U .Theorem C.1 Given a problem instance θ ∈ Θ, item-fair solution f I and user-fair solution f U . Letx OPT = arg max x REV(x) be the revenue-maximizing solution in the absence of fairness. If we solve Problem (FAIR) with parameters δ I and δ U and assuming that the problem is feasible, the price of fairness is at mostPOF ≤ H • max max i∈[N ] (δ I • O I i (f I ) -O I i (x OPT )) + , max j∈[M ] (δ U • O U j (f U ) -O U j (x OPT )) + ,where constant H is the Hoffman constant associated with Problem (FAIR) under instance θ (see definition in Lemma G.2).There are two important takeaways from Theorem C.1: (1) The price of fairness arises from the misalignment of objectives, captured by the difference in items'/users' outcomes under the singlesided item/user-fair solution and the platform's optimal revenue solution, x OPT (i.e., (δI • O I i (f I ) - O I i (x OPT )) + and (δ U • O U j (f U ) -O U j (x OPT )) + .A high price of fairness can result from high divergence of platform's goals from item/user interests (as illustrated by Proposition 2.1 and Example B.1). ( 2) Theorem C.1 also underscores the value of the parameters δ I and δ U in achieving a balance among stakeholder interests. Both takeaways are further supported empirically, as we next investigate the price of fairness associated with our case study on Amazon review data in Section C.1.Recall from Section 2.4 that i ⋆ j = arg max i∈[N ] r i y i,j is the item with the maximum expected revenue, if an arriving user is of type j. (Here, we assumed that i ⋆ j is unique without loss of generality.) The platform's revenue-maximizing solution is x OPT i,j = 1 if i = i ⋆ j and x OPT i,j = 0 otherwise. Now, suppose that the platform solves Problem (FAIR) with some fairness parameters δ I , δ U ∈ [0, 1] and assuming Problem (FAIR) is feasible. LetF = {x ∈ ∆ M N : O I i (x) ≥ δ I • O I i (f I ); O U j (x) ≥ δ U • O U j (f U ) ∀i ∈ [N ], j ∈ [M ]} denote the feasibility region of Problem (FAIR). We defineEQUATIONThat is, x ′ is a feasible solution to Problem (FAIR) that is closest to x OPT w.r.t. ∥•∥ ∞ . Then, by Lemma G.1, we have the following boundEQUATIONwhere the first term H is the Hoffman constant associated with the feasibility region F, and the second term encapsulates how much x OPT violates the item/user-fairness constraints. Now, note that we also haveEQUATIONwhere (a) follows from the form of x OPT , and (b) follows from 1 -x ′ i ⋆ j ,j = i̸ =i ⋆ j ,j x ′ i,j ≥ x ′ i,j for any i ̸ = i ⋆ . This then allows us to bound the PoF as followsPOF = OPT-REV -FAIR-REV OPT-REV ≤ 1- REV(x ′ ) OPT-REV ≤ 1- j∈[M ] R i ⋆ j x ′ i ⋆ j ,j j∈[M ] R i ⋆ j ≤ max j∈[M ] 1-x ′ i ⋆ j ,j = ∥x ′ -x OPT ∥ ∞ ,where the first inequality follows from x ′ being a feasible solution to Problem (FAIR), the second inequality follows from REV(x′ ) ≥ j∈[M ] R i ⋆ j x ′ i ⋆ j ,j, and OPT-REV = j∈[M ] R i ⋆ j , and the final equality follows from (21) .Finally, combining Eq. ( 20) and Eq. ( 22) finishes the proof. ■In this section, we investigate the price of fairness from our case study on the Amazon review data (Section 4) and shed light on how our fair recommendation framework, Problem (FAIR), can help the platform achieve the right middleground among multiple stakeholders.In our case study, we act as an e-commerce site (such as Amazon) recommending a collection of at most K = 3 products to incoming users. There are a total of N = 30 items to be shown to M = 5 types of users, where the relevance score between items and users as well as users' arrival rates are both obtained from an Amazon review dataset [71] ; see Section 4 for a complete description of the dataset. Assuming that the platform has full knowledge of the problem instance, we solve Problem (FAIR-ASSORT) (here, we consider the assortment extension of Problem (FAIR); see Section E.2 for details) under different values of fairness parameters δ I , δ U to investigate how much loss the platform needs to endure in order to achieve various levels of fairness for its items/users. The left-hand side of Figure 2 shows the price of fairness (POF) endured by the platform given different (δ I , δ U ). Note that in our recommendation problem based on Amazon review data, item fairness is much more difficult to achieve than user fairness, since (i) the number of items is much larger, making the fair outcome of many items differentiate a lot from the outcome attained under platform's revenue-maximizing solution; and (ii) the objective of users (MNL utility) aligns fairly well with the platform's objective (revenue). As a result, the item-fair constraints are the binding constraints in majority of the cases. This can be seen in the left-hand side plot, where we see that POF increases more significantly when we increase δ I . This concurs with the first takeaway from Theorem C.1, which suggests that the misalignment of objectives directly impacts the POF.In the right-hand side of Figure 2 , we plot the evolution of PoF when we fix δ U = 0 (upper-right plot) and δ I = 0 (lower-right plot) respectively. Given that the item fairness constraints are primarily the binding constraints, as discussed above, we observe a linear increase in PoF for the platform as the fairness parameter δ I for items increases. This observation again corroborates the findings presented in Theorem C.1. For the users, in the case of Amazon review data, the misalignment of objectives(δ U • O U j (f U ) -O U j (x OPT)) + only becomes noteworthy as δ U gets close to 1. This indicates that under the Amazon review data, the platform can potentially obtain a high level of user-fairness at very little cost, which also matches our findings in our case study in Section 4. Insights from the case study. Our empirical analysis provides practical guidelines for selecting appropriate fairness parameters δ I , δ U in real-world settings. Specifically, platforms should focus on (i) identifying which fairness constraints are binding and (ii) evaluating the degree of objective misalignment, typically captured by the slope between the PoF and the fairness parameters.One potential approach is to first identify the binding constraints by assessing which stakeholders experience the most unfair outcomes under the current recommendation policy. Then, using the piecewise linear relationship established in Theorem C.1, the platform can estimate the tradeoff between the binding constraints and PoF. Based on the desired fairness levels and acceptable PoF, the platform can now narrow down the range of fairness parameters to experiment with. Once a small subset of promising fairness parameters is identified, a platform can conduct online A/B tests by splitting its traffic to experiment with these parameters in parallel, thus selecting the optimal fairness parameters efficiently without extensive trial-and-error.We first state a few definitions and lemmas that are useful for the proof of Theorem 3.1.Good event and cutoff time. We define the good event at round t, denoted by E t , as the event under which our estimates for y and p are accurate w.r.t. t. Definition D.1 (Good event) At round t, a good event E t isEQUATIONwhere Γ y,t = 2 log(T )/ m(t)ϵ t and m(t) = max 1, t/log(T ) -t log(T )/2 Γ p,t = 5 log(3T )/t .Observe that Γ p,t strictly decreases to 0 as t → ∞. This is also the case for Γ y,t . To see that, note that m(t), used to define Γ y,t , strictly increases in t and goes to ∞ as t → ∞. Hence, we can additionally define the cutoff time T , which is time after which the good event becomes "sufficiently good":EQUATION)where ζ is defined in Assumption 3.1. Here we also used y i,j ∈ (0, 1)for all i ∈ [N ], j ∈ [M ],which is assumed in Section 2.1, so we must have ∥y∥ ∞ < 1. Here, note that Γ y,t = O(t-1 3 ), Γ p,t = O(t -1 2 ) so T = O(max{ζ , ∥y∥ ∞ } 3) and is O(1) w.r.t. T . The following lemma states that under the good event, for t > 0 that is sufficiently large, the optimal solution x ⋆ to Problem (FAIR) is feasible to the relaxed problem under the estimated instance, Problem (FAIR-RELAX( θt , η t )), while our solution xt is also feasible to the relaxed problem under the ground-truth instance, Problem (FAIR-RELAX(θ, η t )). The proof is presented in Section D.3.Given problem instance θ ∈ Θ. Suppose that Assumption 3.1 holds, where B is the Lipschitz constant. Let constant Ū be the maximum utility in the small neighborhood around θ; that is, ∥U ( θ)∥ ∞ ≤ Ū for all θ ∈ Θ such that ∥θ -θ∥ ≤ ζ. Under the good event E t , when t > T (defined in (24) ) and log(T ) > (2 + ∥r∥ ∞ )B, we have the following:(i) ∥ ŷt ∥ ∞ < 1, so x t,i,j = (1 -N ϵ t ) xt,i,j + ϵ t according to FORM. (ii) x * is feasible to Problem (FAIR-RELAX( θt , η t )). (iii) xt is feasible to Problem (FAIR-RELAX(θ, 2η t ))where θt and η t are defined in Eq. (1) and Eq. (2).The second Lemma (Lemma D.2) shows that the good event happens with high probability. Its proof is deferred to Section D.4. • the revenue regret of FORM is at most E[R(T )] ≤ O(M N 1 3 T -1 3 ) • the fairness regret of FORM is at most E[R F (T )] ≤ O(M N 1 3 T -1 3 ).Proof of Theorem D.3. We bound the revenue regret and the fairness regret respectively.(1) Bounding revenue regret.For a given t > T , assume that the good event E t defined in Definition D.1 holds. Let R = (R i,j ) i∈[N ] j∈[M ], where R i,j = r i p j y i,j denotes the expected revenue that the platform receives from offering item i to user of type-j. That is, REV(x, θ)= i∈[N ] j∈[M ] R i,j x i,j . Similarly, for simplicity of notation, let Rt = ( Rt,i,j ) i∈[N ] j∈[M ], where Rt,i,j = r i pt,j ŷt,i,j .Let us first rewrite the revenue regret at round t as the following:REV(x ⋆ , θ) -REV(x t , θ) = i∈[N ] j∈[M ] R i,j x ⋆ i,j - i∈[N ] j∈[M ] R i,j x t,i,j = i∈[N ] j∈[M ] Rt,i,j (x ⋆ i,j -x t,i,j ) + i∈[N ] j∈[M ] x ⋆ i,j (R i,j -Rt,i,j ) - i∈[N ] j∈[M ] x t,i,j (R i,j -Rt,i,j ) = i∈[N ] j∈[M ] Rt,i,j (x ⋆ i,j -x t,i,j ) + i∈[N ] j∈[M ] (x ⋆ i,j -x t,i,j )(R i,j -Rt,i,j )We then haveEQUATION) where (a) follows from statement (i) in Lemma D.1, i.e., x t,i,j = (1 -N ϵ t ) xt,i,j + ϵ t ; (b) follows from the fact that ϵ t ≤ 1 N so 1 -N ϵ t ≥ 0, and by statement (ii) Lemma D.1, we have that x ⋆ and xt are both feasible to Problem (FAIR-RELAX( θt , η t )), and hence REV(x ⋆ , θt ) ≤ REV( xt , θt ); (c) follows from the fact that ϵ t ≤ 1 N .Rt,i,j -R i,j = r i ŷt,i,j pt,j -r i y i,j p j = r i (ŷ t,i,j pt,j -y i,j pt,j + y i,j pt,j -y i,j p j ) = r i (ŷ t,i,j -y i,j )p j + y i,j (p t,j -p j )EQUATIONWe thus haveEQUATIONHence, for any t > T , let F t-1 be the sigma-algbra generated from all randomness up to round t -1, andEQUATIONwhere (a) follows from ( 27); (b) follows from the high probability bound for event E t in Lemma D.2, given that t > T holds.Finally, by ( 28), we have1 T t∈[T ] E REV(x ⋆ , θ) -REV(x t , θ) ≤ O T T + M T t>T (Γ p,t + Γ y,t ) + N M T t>T ϵ t = O(M N 1 3 T -1 3 ) (29)where in the final equality we recallϵ t = min N -1 , N -2 3 t -1 3 and Γ y,t = 2 log(T )/ m(t)ϵ t < 2 log(T ) (t/log(T )- √ t log(T )/2)ϵt = O(N 1 3 t -1 3) since m(t) > 1 for all t > T defined in Eq. ( 24).(2) Bounding constraint violation.Item-Fair Constraints. For any item i ∈ [N ], and any t > T , under the good event E t defined in Definition D.1, we haveEQUATIONEQUATION)where (a) follows from Lemma D.1 part (i), which states that under the good event E t for t > T , we have x t,i,: = (1-N ϵ t ) xt,i,: +ϵ t e M according to Algorithm 1; (b) follows from Lemma D.1 part (iii), which states xt is feasible to Problem (FAIR-RELAX(θ, η t )), where η t = log(T ) max{Γ p,t , Γ y,t } according to Eq. ( 1).Hence, we haveEQUATIONwhere (a) and (b) follows from δ I ≤ 1 and L i,: (θ) ⊤ f I i,: (θ) ≤ max{1, r} depending on the item's outcome; (c) follows from Eq. ( 30); (d) follows from Lemma D.2 for sufficiently large T . Therefore, the time-averaged item-fairness constraint violation for any item i is at most O(M N1 3 T -1 3) . We can perform the same analysis for user-fairness constraints and obtain the same upper bound. The proof is thus omitted.We prove the three statements in Lemma D.1 respectively as follows.Proof for (i). Consider the following under the good event E t , defined in Eq. (D.1):EQUATIONwhere (a) follows from t > T and the definition of T in (24) . This gives ∥ ŷt ∥ ∞ < 1, and hence given the design of FORM, x t,i,j = (1 -N ϵ t ) xt,i,j + ϵ t .Proof for (ii). Here, we would like to show that x * is feasible for Problem (FAIR-RELAX( θt , η t )), where θt and η t are defined in Eq. ( 1) and Eq. ( 2).Item-Fair Constraints. Let L = ∥L∥ ∞ . For any i ∈ [N ] and x ∈ ∆ M N , under Assumption 3.1, we haveEQUATION)On the other hand, for any i ∈ [N ], we also haveEQUATION≤ L i,: ( θt ) ⊤ f I i,: ( θt ) -f I i,: (θ) + L i,: ( θt ) -L i,: (θ) ⊤ f I i,: (θ) ≤ M L • ∥f I i,: ( θt ) -f I i,: (θ)∥ ∞ + M • ∥L i,: ( θt ) -L i,: (θ)∥ ∞ ≤ M LB • ∥ θt -θ∥ ∞ + M B • ∥ θt -θ∥ ∞ ≤ M B( L + 1) max{Γ p,t , Γ y,t } (34)where the last inequality from the fact that for all t > T (see definition in (24) ), under the good eventE t : ∥ θt -θ∥ ∞ = max{∥ ŷt -y∥ ∞ , ∥ pt -p∥ ∞ } ≤ max{∥ ŷt -y∥ ∞ , ∥ pt -p∥ 1 } ≤ max{Γ y,t , Γ p,t } . Since x ⋆ ∈ ∆ MN is the optimal solution to Problem (FAIR), we know that L i,:EQUATION) where the first inequality holds because of Eq. ( 33) and the third inequality holds because of Eq. ( 34). Hence we haveEQUATIONwhere (a) follows from log(T ) > (2 + r)B > B + δ I B( L + 1). Since the amount of relaxation is η t = M log(T ) max{Γ p,t , Γ y,t }, as defined in Eq. 1, we show that x ⋆ satisfies the item-fair constraints for Problem (FAIR-RELAX( θt , η t )).User-Fair Constraints. For any j ∈ [M ] and x ∈ ∆ M N , under Assumption 3.1, we haveEQUATION)Also note that for any problem instance θ ′ ∈ Θ, we have thatU :,j (θ ′ ) ⊤ f U :,j (θ ′ ) = max i∈[N ] U i,j (θ ′ )Hence, we have the following:EQUATION)where the second inequality follows from local Lipschitzness of U (θ).Now, since x ⋆ ∈ ∆ MN is the optimal solution to Problem (FAIR), we know that U :,j (θ) ⊤ x ⋆ :,j ≥ δ U • U :,j (θ) ⊤ f U :,j (θ). Combining this with the Eq. ( 37) and Eq. ( 38), we haveEQUATION)Hence we haveEQUATION)Proof of (iii). We can show xt is feasible to Problem (FAIR-RELAX(θ, η t )) via a similar argument as our proof for (ii)Item-Fair Constraints. First note thatL i,: (θ) ⊤ xt,i,: + M B max{Γ p,t , Γ y,t } (a)≥ L i,: ( θt ) ⊤ xt,i,:EQUATIONHere, (a) follows from an identical argument as shown in (33) , while replacing x with xt ; (b) follows from feasibility of xt to Problem (FAIR-RELAX(θ, η t )); (c) follows from (34) . Hence, since log(T ) > (2 + r)B > B + δ I B( L + 1), we concludeEQUATION)User-Fair Constraints. We again follow the same arguments as in our proof for (ii) and establish the following:EQUATIONwhich then givesEQUATIONFor completeness, let us recall the definitions of Γ y,t and m(t) in Eq. ( 23):Γ y,t = 2 log(T ) m(t)ϵ t , m(t) = max 1, t log(T ) -t log(T )/2 .We define related variables Γ y,j,t and m j (t) as followed:EQUATIONSince for log(T ) > 1 min j∈[M ] pj and t > T (see definition of the cutoff time T in (24) ) such that m(t) > 1, we know m j (t) ≥ m(t) > 1 and thus Γ y,t ≥ Γ y,j,t for any j ∈ [M ]. We thus haveEQUATIONHence,EQUATION≤EQUATION≤EQUATIONwhere (a) follows from ( 46); (b) follows directly from the concentration inequality to bound empirical distribution estimates; in particular, we use Lemma G.3 and take δ = 1 T . Hence, in the following, it suffices to bound P |ŷ i,j,t+1 -y i,j | ≥ Γ y,j,t for any i ∈[N ], j ∈ [M ].Recall that n j,t is the total number of type j arrivals up to time t. Then, consider the following P |ŷ i,j,t+1 -y i,j | ≥ Γ y,j,t = P |ŷ i,j,t+1 -y i,j | ≥ Γ y,j,t , n j,t ≥ m j (t) + P |ŷ i,j,t+1 -y i,j | ≥ Γ y,j,t , n j,t < m j (t)EQUATIONWe would bound terms A and B respectively.Bounding A. Recall that τ j,k ∈ [T ]is the round at which the kth consumer of type j arrived.EQUATIONwhere in the final inequality we used the definition of Γ y,j,t in (45) and the fact that n ≥ m j (t). Note that for any k ∈ N, we have EI{Iτ j,k =i,zτ j,k =1} xτ j,k ,i,j F τ j,k = y i,j, where F τ j,k is the sigma-algebra generated from all randomness up to round τ j,k . Therefore,M k = I{Iτ j,k =i,zτ j,k =1} xτ j,k ,i,j-y i,j is a Martingale difference sequence. Further, we haveEQUATIONwhere (a) follows from the fact thatEQUATIONHence, by Bernstein's inequality (see Lemma G.4), we haveEQUATIONwhere (a) follows from invoking Lemma G.4 by taking c k = 1 ϵt and V k = 2k log(T ) (e-2)ϵt , and δ = 1 2T 2 . Combining Eq. ( 49) and Eq. ( 52) yieldsEQUATIONBounding B. Denote M t = I{J t = j} -p j and it is easy to see M t is a Martingale difference sequence bounded between [-1, 1]. Hence, by recognizing n j,t -t • p j = τ ∈[t] M τ and applying the Azuma-Hoeffding inequality, for any ϵ > 0, we haveEQUATIONwhere in (a) we take ϵ = t log(T )/2.Our fair online recommendation framework, Problem (FAIR), and method FORM can be extended to accommodate additional variants of our setup. In Section E.1, we discuss how our framework/method can additionally handle periodic arrivals with the same performance guarantees. In Section E.2, we detail how our framework/method extends to handling the assortment recommendation setting.In real-world scenarios, user arrivals are often non-stationary, displaying variations over time due to periodic user preferences and behavior. This is particularly evident in many recommendation systems that exhibit daily or weekly periodicity, with consistent patterns of user arrivals and interactions throughout the day or week. For instance, in an e-commerce setting, higher user activity and engagement may be observed during lunch breaks, evenings, or late-night browsing. Similarly, recommendation systems may experience increased user engagement during weekends compared to weekdays. Recognizing the presence of these periodic patterns, we extend our concept of a fair solution and our algorithm FORM to accommodate the online setting with periodic arrivals.Consider a scenario where users arrive in each round t ∈ [T ] according to a probability distribution p t ∈ ∆ M . Additionally, suppose that there exists a period length Q ∈ (0, T ) and distributions p (1) . . . p (Q) such that p mQ+q = p (q) for any m = 0, 1, 2 . . . and q = 0, 1 . . . Q -1. By defining p as the time-averaged arrival distribution, represented by p = 1T t∈[T ] p t , we can generalize the fair recommendation problem, Problem (FAIR), to incorporate this periodic arrival setup.Yet, similar to the stationary setting, the platform does not have prior knowledge of the sequence of user arrival distributions p 1 . . . p T , nor the time-averaged distribution p. Although solving Problem (FAIR) w.r.t. the time-averaged distribution p seems to be more challenging compared to that under stationary arrivals, we can in fact still obtain accurate estimates by slightly modifying the design of FORM as follows: instead of estimating p using all historical data (as done in Eq. ( 2)), we only obtain estimates over a sliding window of length W > 0. That is, we estimate the arrival rates of type-j user at round t + 1 via the following:EQUATIONBy doing so and keeping all other procedures unchanged, we show in Theorem E.1 that FORM would yield the same theoretical guarantees for its final output under the setting with periodic arrivals, when the size of the sliding window size W is chosen appropriately. . Then, for sufficiently large T , we have the following:• the revenue regret is at most E[R(T )] ≤ O(M N 1 3 T -1 3 ) • the fairness regret is at most E[R F (T )] ≤ O(M N 1 3 T -13 )The proof of Theorem E.1 is provided in Section E.1.1.Remark E.1 (Lack of knowledge of the period length) We remark that in the periodic setup, we assume knowledge of the period length Q > 0. This assumption aligns with practical scenarios where platforms are aware of intraday, daily, weekly, or seasonal user arrival cycles. However, if the period length Q is unknown, one might consider employing a standard meta "expert" algorithm from the bandit literature on top of FORM. This approach involves using sliding window lengths as experts, representing different expert windows in the set A = aT 2 3 : a = 1, 2 . . . Q for some Q > Q. Each expert produces estimates of p and the fair solution based on their window length. We maintain weights over these estimates using an EXP3 algorithm. However, while this approach may eventually approximate the cumulative revenue of the best expert with the correct period length Q, the expected constraint violation w.r.t. the true parameters θ may not be sublinear or vanishing over time. This is because the estimates from experts with incorrect period lengths can significantly violate constraints, resulting in overall large constraint violations. Therefore, optimizing the fair solution under a periodic arrival setup with an unknown period length remains an open question.First, similar to Lemma D.2 that presents a concentration bound for empirical estimates of p using all historical data, if we construct an empirical estimate for p with Eq. ( 55) using sliding window length W, again applying Lemma G.3, we have for any t > W s.t.EQUATIONRecall the definition of T in Eq. (24) . We additionally defineEQUATION) .Following the same analysis as bounding the regret for Theorem 3.1 in Eq. ( 29), while replacing T with T and considering Γ p,t = 5 √ log(3T ) √ W, we have1 T t∈[T ] E REV(x ⋆ , θ) -REV(x t , θ) ≤ O T T + M T t>T (Γ p,t + Γ y,t ) + M N T t>T ϵ t = O(M N 1 3 T -1 3 ) .A similar analysis as Eq. ( 31) applies to bounding the fairness regret R F (T ). ■Our model in Section 2 primarily considered a setting where a single item is offered to each user at each round, which applies to various real-world settings. In this section, we discuss an extension of our framework/method to a setting in which the platform might wish to recommend an assortment to its users, which applies to real-world scenarios such as job recommendation, where a number of most relevant jobs are recommended to a candidate, or e-commerce sites, where a small assortment of items might be featured on the front page whenever a user arrives.Extension of our framework. To consider an assortment recommendation setting, we let w i,j > 0 be the weight associated with each item i for a type-j user. If a type-j user arrives onto the platform and gets offered assortment S, he/she will choose/purchase item i from the assortment with probability wi,j 1+wj (S) , where w j (S) = i∈S w i,j , based on the MNL model [65] . This is different from the single-item recommendation setting, where we have well-defined purchase probability y i,j for each item-user pair. When we recommend assortments, the purchase probability not only depends on an item's weight, but also the assortment it gets presented in. Given that, we define the problem instance as θ = (p, w, r).Our fair recommendation framework, Problem (FAIR), can be readily extended by letting our decision variable be q = {q j (S) : S ⊆ [N ], |S| ≤ K, j ∈ [M ]}, where q j (S) denote the probability of presenting assortment S to a type-j user. Then, we can formulate the fair recommendaton problem under the same idea:max q REV(q) s.t. O I i (q) ≥ δ I • O I i (f I ) ∀ i ∈ [N ] O U j (q) ≥ δ U • O U j (f U ) ∀ j ∈ [M ] ,(FAIR-ASSORT)whereREV(q) = j∈[M ] p j S∈[N ],|S|≤K q j (S) i∈S r i w i,j 1 + w j (S)denote the expected revenue under recommendation q. On the other hand, the forms of the item/user outcome functions O I i (q, θ), O U j (q, θ) as well as their respective fair solutions f I (θ), f U (θ) can again take any forms that depend on the problem instance θ, based on their own needs.Extension of our algorithm for the online setting. Given the extended framework Problem (FAIR-ASSORT), we can similarly extend the algorithm FORM for the assortment recommendation setting, which is outlined in Algorithm 2.Here, Algorithm 2 follows the same relaxation-then-exploration design as discussed in Section 3.3 and Algorithm 1. Whenever our estimate of the problem instance θ is updated, the algorithm first solves a relaxed version of Problem (FAIR-ASSORT) using the updated estimate, and then adds randomized exploration to stimulate learning; see Steps 2(b) and 2(c) in Algorithm 2. 5The main difference between Algorithm 2 and Algorithm 1 lies in the learning mechanism. In order to learn the weights w in the assortment setting, we adopt the learning mechanism from MNL-Bandit [3] . The rounds in which type-j arrives are divided into epochs. In each epoch ℓ j , the same assortment S j is offered until a no-purchase option is observed. We then apply Eq. ( 58) to estimate w :,j , which is an unbiased estimator according to Corollary A.1 in [3] . To estimate arrival probabilities, we (58) (c) Solve a Relaxed Problem (FAIR-ASSORT) with the Estimated Instance. Given estimated instance θ = ( pt, ŵt, r) and the magnitude of relaxation ηt, let qt be the optimal solution to the following: EQUATION-Else, E ℓ J t ,J t ← E ℓ J t ,J t ∪ {t}• t ← t + 1 .again use the sample mean for p. As discussed in Section 3.3, any learning mechanism that provides accurate estimates for sufficiently large T would be suitable here. The magnitudes of exploration and relaxation, ϵ t and η t , are adjustable inputs for platforms to fine-tune in practice.While a detailed theoretical analysis of the expanded algorithm is reserved for future work, it is clear that our high-level ideas behind FORM, including incorporating relaxations for fair recommendations and adding exploration to stimulate learning, seamlessly transition to the assortment recommendation context. The efficacy of our extended framework/method in the assortment recommendation setting is further validated in our case study on Amazon review data (see Section 4).In this section, we discuss the baselines introduced in existing works, specifically FairRec [55] and TFROM [71] , which are state-of-the-art approaches targeting multi-sided fairness. We detail the main setups of both approaches and highlight the key differences between these methods and ours.FairRec [55] . As we briefly remarked in Section 4, FairRec targets a single-shot recommendation problem where there are N items and M users, and makes a single recommendation decision that displays K items to each of the M users, assuming full knowledge of the exact relevance score between each pair of item and user. Let A = {(A j ) j∈[M ] : A j ⊂ [N ], |A j | ≤ K} denote the the algorithm's recommendation decision. The authors of [55] show that FairRec can achieve (i) maxmin share (MMS) of visibility (exposure) for most of the items and non-zero visibility for the rest; (ii) envy-free up to one item (EF1) fairness for every user, meaning that for every pair of users j, j ′ ∈ [M ], there should exist an item p ∈ A j ′ such that the utility that user j receives from A j is at least the utility that user j ′ receives from A j ′ \ {p}.There are several key differences between our setting/method and FairRec. (i) FairRec focuses on an offline setting where the platform makes a single-shot recommendation with full knowledge of user preferences (i.e., relevance scores). In contrast, our work targets the more challenging online setting where user data is unknown and must be continuously learned. We maintain fairness in this online setting, dealing with users who arrive stochastically, and ensuring fairness over a longer time horizon. (ii) FairRec assumes specific fairness notions (i.e., maxmin fairness regarding visibility for items and envy-free fairness up to one item for users). Our framework, on the other hand, is much more flexible, accommodating a wide range of outcome functions and fairness notions, as discussed in Section 2.2. See, also, Section F.2 where we conduct additional experiments on the Amazon review data under alternative outcome functions and fairness notions, and demonstrate that FORM remains effective in making fair recommendations in an online environment.TFROM [71] . Similar to FairRec, the authors of [71] consider a recommendation problem where relevance scores between items and users are known in advance. To impose fairness for items, TFROM enforces either uniform fairness or quality-weighted fairness regarding item visibility (see Definitions 1 and 2 in [71] ). For user fairness, TFROM aims to achieve uniform normalized discounted cumulative gain (NDCG) among users. [71] does not provide theoretical performance results, but numerically shows that TFROM achieves low variance in item visibility and NDCG among users in online settings, thus ensuring two-sided fairness. TFROM is provided in two versions: one for the offline setting and one for the online setting, with the latter dynamically maintaining low variance in item exposure and user NDCG scores over time. We compare our algorithm with the online version of TFROM in our experiments in Section 4.While TFROM addresses online user arrivals, it again differs significantly from our work in several ways: (i) Like FairRec, it assumes full knowledge of user preferences (i.e., relevance scores) and lacks a learning stage, ignoring potential biases from corrupted data; (ii) It focuses on pre-specified outcomes and fairness notions for items/users, lacking the flexibility of our framework; (iii) No theoretical guarantees are provided for TFROM's performance, whereas we offer full theoretical guarantees for our algorithm despite data uncertainty.Finally, it is important to note that neither FairRec nor TFROM considers the platform's revenue, which is another key focus of our work. While the aforementioned works focus on two-sided fairness in recommender systems, our framework takes a step forward and adopts a multi-sided perspective, balancing the interests of the platform, items, users, and potentially other stakeholders. The efficacy of our framework is highlighted in Figure 1b , showing how our algorithm manages to maintain high platform revenue while ensuring fairness for other stakeholders.To demonstrate the generality of our results, we have replicated our experiments on Amazon review data from Section 4 under alternative fairness notions and outcomes for items. In particular, we have considered the following definitions of the item-fair solutions f I , while keeping all other setups and baselines the same as in Section 4: Overall, the results from Figures 3, 4 , and 5 are consistent with those previously observed in Figure 1 . In terms of the platform's revenue, we again observe the convergence of time-averaged revenue towards the optimal revenue in hindsight, confirming FORM's low regret. Regarding normalized revenue, item outcomes, and user outcomes, FORM consistently strikes an effective balance among multiple stakeholders' interests under the specified fairness parameters δ I and δ U , regardless of the fairness notion or outcome that stakeholders care about. The performance of our baselines, however, is more affected by the fairness notion or outcomes when defining within-group fairness. For instance, while min-revenue achieves high levels of fairness for all items when the item-fair solution considers maxmin fairness w.r.t. item revenues, its performance deteriorates when items instead care about visibility or adopt K-S fairness. In comparison, FORM quickly adapts to various fairness notions and outcomes, while maintaining its good performance. To show generality of our framework/method, we have conducted additional experiments in an alternative setting (movie recommendation) using the MovieLens data, which complements our case study on Amazon review data in Section 4. Overall, the results are consistent with our Amazon case study, showing our method's effectiveness in balancing platform revenue and stakeholder fairness in various types of recommender systems.Here, we act as a movie recommendation platform that shows a "trending action movie" to any arriving user. We considered the N = 50 action movies from MovieLens (ML-100K) data [35] with the highest number of ratings and clustered users into 6 types based on their preferences. As the movies are not associated with revenues, we let r i = 1 for all i ∈ [N ]. Here, the platform's main objective is to maximize its expected marketshare. The item-fair solution adopts maxmin fairness w.r.t. each movie's marketshare, with user utilities captured by the MNL model. In this set of experiments, we consider a total of T = 2000 rounds, where at each round there are 100 user arrivals.During each round t, we would solve the relaxed constrained optimization problem and update our recommendation probabilities only once, given scalability considerations as stated in Section 3.5; however, we will update our estimates for item weights and arrival probabilities based on Eq. ( 58) throughout the user arrivals.Figure 6 shows the results obtained from our MovieLens experiments. It is evident the results are largely in line with what we observed in our case study on Amazon review data (Section 4), both in terms of the platform's revenue and the outcomes received by items/users. Our framework and method also remain effective when we only resolve the relaxed constrained optimization problem after a given number of user arrivals. It is noteworthy that in a movie recommendation setting with homogeneous revenues, the interests of the platform and the users completely align. This explains why the curves of greedy and max-utility completely overlaps with each other in our figures. However, greedy still suffers from 7-8% loss in marketshare (Figure 6b )), which is precisely because inadequate exploration of user data makes it overlook potentially more popular items and stick with a sub-optimal item. Overall, our algorithm FORM again adeptly balances the interests of both the platform and its stakeholders, while handling the tradeoff between learning and fair recommendation.In this section, we state some useful lemmas that would be invoked in this work. (A) = {λ ∈ R m : λ ≥ 0, ∥λ ⊤ A∥ 1 ≤ 1}. Then, for each b ∈ R m such that {x ∈ R n : Ax ≤ b} ̸ = ∅ and for each x ′ ∈ R n , we have: min Ax≤b ∥x -x ′ ∥ ∞ ≤ H(A) • (Ax ′ -b) + ∞ ,where H(A) ≥ 0 is known as the Hoffman constant.Lemma G.2 (Characterization of Hoffman constant ([56], Proposition 2)) Let A ∈ R m×n . The Hoffman constant H(A) defined in Lemma G.1 can be characterized as follows:H(A) = max J⊆{1,...,m} A J full row rank max ∥v∥ 1 : v ∈ R J + , A ⊤ J v 1 ≤ 1 = max J⊆{1,...,m} A J full row rank 1 min v∈R J + ,∥v∥1=1 A ⊤ J v 1, where A J denotes the submatrix of A that only includes the rows in J ⊆ {1, . . . , m}.Lemma G. EQUATIONNeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: As discussed in our abstract and Section 1, our main contributions include (i) introducing a novel fair recommendation framework, Problem (FAIR), that flexibly balances multi-stakeholder interests, and (ii) introducing a low-regret algorithm FORM that simultaneously learns user data and performs fair recommendation in a dynamic online setting, whose efficacy is further validated in a real-world case study. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.38th Conference on Neural Information Processing Systems (NeurIPS 2024).See our additional experiments on MovieLens data in Section F.3, where we resolve the constrained optimization problem at most once every 100 user arrivals, while our algorithm remains effective.For solving Problem (FAIR-ASSORT) in our numerical experiments in Sections 4 and F.2, we use the CBC solver accessed via the PuLP library in Python. 


Decision: This paper addresses the important problem of balancing multiple stakeholder interests in online recommendation systems. The authors propose a novel framework called FAIR that aims to optimize platform revenue while maintaining fairness for both items (sellers) and users (customers). They also introduce an algorithm, FORM, designed to learn user preferences and enforce fairness constraints simultaneously in an online setting. The reviewers unanimously agree on the significance and timeliness of the problem addressed. The paper's key strengths include a flexible framework that can accommodate various fairness notions and stakeholder objectives, a theoretical analysis providing sublinear regret bounds for the proposed algorithm, and empirical validation on real-world data demonstrating the effectiveness of the approach. The paper makes a solid contribution to the field of fair recommendation systems and has the potential for significant impact in both academic and practical contexts.
However, the reviewers have raised some concerns that the authors should address in the final version, for example, computational complexity and scalability (a more detailed discussion on the algorithm's scalability for large-scale systems and potential optimizations), parameter selection (offer better guidance on selecting appropriate fairness notions and parameters in practical settings). The assumption around static user preferences was deemed as restrictive by the authors, and the reviewers also asked questions about the long-term effects based on (for example) platform dynamics and stakeholder behaviors. The authors are encouraged to pursue real-world deployments as future work. In conclusion, despite the noted areas for improvement, this paper presents a significant contribution to the field of fair recommendation systems. The novel multi-stakeholder perspective, coupled with the theoretical guarantees and empirical validation, make a compelling case for acceptance. The authors are advised to address the reviewers' concerns in their final revision to further enhance the paper's impact.

Reviews: review: paper_summary: paper_summary: The paper introduces a fair recommendation framework, FAIR, for balancing the interests of multiple stakeholders in recommendation systems, namely the platform, sellers, and users. The framework is formulated as a constrained optimization problem that addresses fairness concerns for both items and users in a dynamic online setting. The paper proposes a no-regret algorithm, FORM, which ensures real-time learning and fair recommendations. The effectiveness of the framework and the algorithm is demonstrated through theoretical analysis and a case studies on real-world data.
strength_weakness: strength_weakness: While the paper presents promising results on a dataset with 30 items and 5 user types, it does not thoroughly address how the framework and algorithm would scale to much larger datasets with a large set of items and more diverse user profiles. My main concern is the proposed solution's scalability, a critical factor for real-world deployment but the proposed solution involves solving a constrained optimization problem at every time step, which could be complex and computationally intensive. This complexity might limit the feasibility of implementation for platforms with limited computational resources. I urge the author to include some discussion about the computational complexity of the proposed solution and also the limitations regarding the scalability.
questions: questions: 1. do you think the regret upper bound given in Theorem 3.1 is optimal? If it is not, any idea how can we improve upon this result?
2. If the platform wants to tradeoff between user fairness and item fairness, how does it need to set the parameters delta^{I} and delta^{U}? The current fairness regret simply cares about the maximum of R^I and R^U, what if we care about both, e.g., R^I + \lambda R^U? Does the proposed method still applicable to this situation?
3. I'm wondering if there could be any intrinsic tradeoff between the revenue guarantee and fairness guarantee.
limitations: limitations: Yes
paper_summary: paper_summary: This paper presents a novel fairness recommendation framework called FAIR, and an online algorithm called FORM for solving multi-stakeholder fairness problems. The main contributions include 1. The FAIR framework is proposed to balance the platform revenue and the fairness of multi-stakeholders (items and users) through the form of constrained optimization problems. The framework can flexibly define fair solutions for items/users and adjust the trade-off between platform goals and stakeholder fairness.2. A FORM algorithm is designed for simultaneous learning and fair recommendation in online settings. The algorithm balances learning and fairness by relaxing the fairness constraints and introducing random exploration.3. Theoretical analyses demonstrate that the FORM algorithm achieves sub-linear regret in terms of both gain and fairness.4. A case study on Amazon review data verifies the effectiveness of the proposed method. The paper solves the fairness problem in multi-party recommender systems, and the proposed method can flexibly weigh the interests of multiple parties while maintaining the platform's revenue and demonstrates good performance in both theory and experiment. This is an important research direction, which is significant for the fairness of practical recommender systems.
strength_weakness: strength_weakness: 1. The computational complexity of the algorithm, especially its scalability in large-scale systems, is not discussed in detail in the paper.
2. The choice of δ_I and δ_U may require a lot of experiments to find suitable values.
3. The model assumes that the user type is known, which may not always hold in practical applications.
4. the paper mainly focuses on short-term fairness and does not delve into the impact of long-term fairness.
5. this paper mainly uses gain and fairness regret as evaluation metrics and more metrics may be needed to fully evaluate system performance.
questions: questions: 1. The paper assumes that user types are fixed, but in practice, user preferences may change over time.
2. the universality of the fairness definition: is the definition of fairness proposed in the thesis applicable to all types of recommender systems?
3. the case study uses only one category of data from Amazon, is it sufficient to demonstrate the universality of the approach?
limitations: limitations: please refer to "weakness"
paper_summary: paper_summary: This paper focuses on an important and interesting research direction: achieving multi-sided fairness for recommendation. Specifically, the authors aim to answer two research questions: (1) What constitutes a fair recommendation within a multi-sided platform? and (2) How would a platform implement a fair recommendation in a practical online setting? The contributions of this work include a novel multi-sided perspective that achieves within-group and across-group fairness among users/items, and also an online recommendation algorithm for multi-sided fairness. Empirical and theoretical results show the advantage of the authors' contributions over prior baselines, especially in online settings.
strength_weakness: strength_weakness: 1. After doing a quick search on "multisided fairness + recommendation", it seems some related works [1, 2, 3] are missing. Even though the setting might be different, the authors should mention and discuss them somewhere in the paper since the topics seem related.
2. An efficiency comparison on the algorithm running time is missing.

Ref:

[1] Naghiaei et al. CPFair: Personalized Consumer and Producer Fairness Re-ranking for Recommender Systems, SIGIR, 2022.

[2] Wu et al. Joint Multisided Exposure Fairness for Recommendation. SIGIR, 2022.

[3] Wu et al. A multi-objective optimization framework for multi-stakeholder fairness-aware recommendation. ACM Transactions on Information Systems, 2022.
questions: questions: 1. Can the proposed method be applied to the scenario in which each user/item has multiple sensitive attributes? For instance, there may be multiple facets in describing a user, in terms of race, gender, occupation, age, income level, ... The number of facets here may be large sometimes, and it is hard to treat a specific combination of multiple facets as a single type. How does this algorithm deal with such "intersectional fairness" (e.g., to achieve fairness not only to "black"/"women"/"nurse"/"elder" separately, but also to the intersectional demographic groups)?
limitations: limitations: 1. In the checklist, the authors claim that "We have clearly stated the assumptions needed for our theoretical results and the setups adopted for our numerical experiments" and "There is no negative societal impact of the work performed". However, these claims are too strong and I actually do not think the limitations and negative societal impact of this work are clearly or comprehensively discussed. For instance, one of the important challenges in recommendation is the "cold-start" problem, the author did not discuss whether their algorithm is capable of applying in this scenario, or it is also some limitation and future work. Also, one potential negative societal impact to me is the leakage of user/item sensitive information as the algorithm needs to use the "type" information. This is also not discussed or mentioned.
paper_summary: paper_summary: The paper addresses the challenge of balancing multiple stakeholder interests in online recommendation systems, which include platforms, items (sellers), and users (customers). To tackle this challenge, the authors introduce a novel fair recommendation framework, FAIR, formulated as a constrained optimization problem to balance these competing interests. They further explore this problem in a dynamic online setting, introducing FORM, a low-regret algorithm that simultaneously learns user preferences and enforces fairness in real-time recommendations. Through theoretical analysis and a real-world case study, the paper demonstrates that FORM can maintain platform revenue while achieving fairness for both items and users, contributing to more sustainable and inclusive digital platforms.
strength_weakness: strength_weakness: This is not a weakness specific to this paper, but choosing the right fairness notion and the values of $\delta$ is non-trivial


Even though the paper performs offline experiments on public real-world datasets, it fails to perform any online production A/B test; so it might be risky to be overly optimistic about the empirical results of the paper until the proposed approach is verified in an online environment and provides some tangible business benefits
questions: questions: How can we reasonably choose the right fairness notion and the values of $\delta$ in practice?


Do the authors have any plan to deploy and evaluate the proposed algorithms in some real production environment?
limitations: limitations: Yes

Comments: title: Re: Rebuttal
comment: Thanks to the authors for the detailed response. I keep my positive score.
I thank the authors for their detailed response, which addresses most of my concerns. I maintain my score and weakly lean towards acceptance.
Thank you to the authors for their useful clarification. I will maintain my positive assessment.
Thanks the authors for the responses during the rebuttal. I keep my positive score.