Interpolating Item and User Fairness in Multi-Sided Recommendations
Authors: Qinyi Chen
Jason Cheuk Nam Liang
Negin Golrezaei
Djallel Bouneffouf
Venue: NeurIPS 2024 poster (2024)
Keywords: fair recommendation
multi-sided platform
multi-stakeholder fairness
recommendation system
online learning algorithms
Primary area: fairness
TL;DR: We present a fair recommendation framework that balances platform revenue and item/user fairness in multi-sided platforms, along with a low-regret algorithm that ensures fair recommendations in an online setting where user data must be learned.

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.

Interpolating Item and User Fairness in Multi-Sided Recommendations
Qinyi Chen' Jason Cheuk Nam Liang' Negin Golrezaei' Djallel Bouneffouf
Maasaahussetss Institute of Technology IBB Research
fqinyic, jcnliang golrezae edu bo wow.oooooffff@@iioooooo com
Abstract
Today's online platforms heavily lean on algorithmic recommendations for bolster- ing user engagement and driving revenue. However, these recommendations can impact multiple stakeholders simultaneously-ithe platform, items (sellers), and users (customers)-enn the right middle ground that accommodates all stakeholders. To address this, we introduce novel fair recommendation framework, Problem (FAIR). that flexibly balances stutii-ttakeholdrr interests via a constrained optimization formulation. We next explore Problem (FAIR) in 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 often odds. Via both theoretical analysis and numerical case study on real-world data, we demonstrate the efficacy of framework and method in maintaining platform revenue while ensuring desired levels of faimess for both items and users.
with their unique objectives, making it difficult to find
1 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 so- cial 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 an independent stakeholder due its unique objectives.
However, as these platforms play a more vital role in societal and economic realms, faimess concerns have prompted inereasing 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
key area of focus; the U.S. Algorithmic Accountability Act [7] requires companies to assess the impacts of their automated decision systems to ensure they are biased discriminatory. has also become increasingly evident, 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 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 disparity that affects items (sellers, content creators) alike. These underscore the necessity to address biases and create more inclusive environment for all stakeholders involved.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Despite the many efforts by companies to mitigate faimess issues, most of the existing measures solely focus on one stakeholder group, sometimes even the expense of another. For example, Airbnb has implemented strategies to mitigate racial discrimination among its users [. 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 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 also focus solely either users or items, but seldom both.
recommender systems (e.g.. [13 55
Addressing multi-sided faimness is inherently complex due to the competing interests and objectives of different stakeholders [39 12] If algorithms solely prioritize the platform's 's profits, this can lead to inequitable exposure for those more niche items and users who prefer them. 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 constitates a fair recommendation within a multi-sided platform? and (2) How would platform implement a fair recommendation a practical online setting? Our contributions are summarized follows:
1. novel fair recommendation framework, Problem (FAIR). Our fair recommendation problem, framed as constrained optimization problem, adopts novel multi-sided perspective that first achieves within- group fairness among items/users, and then enforces cross- gross-group fairness that addresses the trade-offs across groups. Notably, Problem (FATR) enables the platform to (i) flexibly define fair solutions for items/users rather than relying on a single predefined notion (see Section 2.2p; (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, low-regret algorithm tailored for fair online recommendation. whose efficacy is further validated via a real-world case study (Section[4) (4). The design of FORM contributes both methodologically and technically. (i) Methodologically, contrary to prior works (e.g., [55] (1I) that treats learning and enforcing fairness as two separate tasks, we recognize that these two tasks, when conducted simultaneously, are often 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 I.I), our setup disallows even verifying the satisfaction of item/user fairness constraints, demanding novel design in FORM.
1.1 Related Works
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 g
42] explored in various contexts such as supervised learning [14 24], resource allocation 9
37
opportunity allocation [36], scheduling
(50), online matching (46). bandits ( 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 faimess in recommender systems can be categorized into three streams based on their subjects: item fairness, user fairness and joint fairness. Item fairness focuses whether the decision treats items fairly, including fair ranking and display of search results [73
48 10 60
66 17 722. similar prediction errors for items' ratings
[57]. and long-term fair exposure B1.. User fairness examines whether the recommendation is fair to different users, encompassing aspects like
similar recommendation quality 226 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

---

suggested in [ Existing works mainly focuses on achieving item and user faimesss based on certain
pre-specified fairness notions: [T3] seeks to balance item and user neighborhoods; [55] proposes a method that guarantees maxmin fair exposure for items and envy-free fairness for users; 7 52
promote fairness with respect to item exposures and user normalized discounted cumulative gains. Additionally, [70] proposes and compares family of joint multi-sided fairness metrics to tackle systematic biases in content exposure, and [69] introduces a multi-objectivv optimization framework that jointly optimizes accuracy and fairness for consumers and producers.
Our work distinguishes from the above works on multi-sided fairness in several aspects. (i) We not only impose faimess for multi multi-stakehhn stakeholders (items/users), but also take the platform's 's revenue, which often neglected. into consideration. (ii) Our framework is not confined fairness/outcome notion. (iii) Most importantly, unlike works that solely focused on multi-sided fairness, we recognize the challenge of jointly handling fairness and learning, and propose an algorithm with theoretical guarantees (see Section 3)
single, pre-specified
Constrained optimization with bandit feedback. Our work formulates the fair recommendation problem in an online setting as a constrained optimization with bandit feedback (see Section 3.1) Our proposed algorithm (Algorithm makes a notable contribution the literature of constrained optimization with bandit feedback by addressing the challenge of having uncertain constraints.
Previous research has explored constrained optimization with bandit feedback in various contexts. Notably, works on online learning with knapsack [38, [3] 61 involves maximizing total reward while adhering resource consumption constraint, using feedhack rewards and resource usage. Other relevant studies include online bidding 28 (2), online allocation (7). and safe sequential decision-making [62] which develop algorithms to monitor and maintain "constraint balances" or address adversarial objectives and constraints. Our setting crucially differs from prior works by not assuming availability of constraint feedback or even the ability to monitor constraint satisfaction, making our problem more challenging (see, also, Section 3.2 for more discussions).
2 Preliminaries
Throughout this paper, boldface symbols denote vectors or matrices, while regular symbols represent scalars. For matrix A E R=*m A., is the element at the i-th row and j-th column; A.,: and A., are the i-th row and j-th column vectors, respectively. We set [n] == {1, 2........ nn. An as the probability distribution space over [ni], and A A. x x An (m times). For any E R. (v)+ := max(v, 0).
2.1 Platform's Recommendation Problem
Consider platform performing recommendations for T rounds, each indexed by & [2]. where one user visits the platform at each round. There are N items on the platform, each indexed by i [N]. and the users are classified into M types, each indexed by j [Md]. At each round a type-Je user arrives and the platform observes the user's type 11 Here, we consider a stochastic setting where the probability of having a type-j user arrival is P[J, o = Pj. where p = (P})}ε[M) E Am denotes the arrival probabilitiee The platform needs to select an item to display to the user, denoted by 4. If type-j user is presented with item i, he/she would choosc/purchase the item with probability Wi. E (0, 1), where y = (yi,) ve[v] denotes the purchase probabilities. The platform then observes sE[M]] the user's purchase decision 2n E [0, J.J. item gets chosen/purchased, it generates revenue r; > 0, where r - (ri)se[N) denotes the revenues.
Let 0 (p.y,r) r) O where + Am x (0, 1) R.N define instance of the platform's recommendation problem. Given the problem instance 0, the platform needs to determine its recommendation probabilities
AN where æijj is the probability of offering item i upon observing type-j user's arrival In Section we first fix the problem instance 0 and omit variables'
2
'Real-world recommendation systems can often categorize users based on available features, even when sensitive attributes (e.g., gender, race) are restricted. These systems use data such as device types [64], zip codes 44 and purchase histories, ensuring that users with similar attributes tend to have aligned preferences.
We later extend our model/method to handling periodic arrivals; our discussion in Sections 3.6 and E.I
$ II our setting, a platform can make personalized recommendations based on type of the arriving user. However, even if personalization is limited due to legal considerations (e.g., Digital Market Act [4 or user privacy settings, our framework, method and theoretical results all remain valid.
3

---

dependency on & whenever the context allows. Later, we will transition to an online setting where the problem instance 0 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 Spotify's "Song of the Day", Amazon's "Best Seller", Medium's 's daily "Must-Read" article, etc. Later in Section (36 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 Users
To properly address multi-sided fairness, we begin by first considering within-group fairnessssss..sssssss..... That is, we seek to answer: what constitutes a fair solution within our item/user group? To address this question, it is important 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 (x) be the expected outcome received by item i at a round with recommendation probabilities x. We let (x) take the following general form: and Lij can be any proxy for the expected outcome (=) = Li,,, where L = (Ls.)) SE(M)
received by item from type-j user if it gets offered. One can consider any of the following metrics or their weighted combinations as the item's 's outcome: (1) visibility: Lij- = Pj and (,(z) -,
(2) marketshare: Tag = Pyyt.j and Of (ax) E, Pis. (3) expected revenue: L4.j = TiPjyi.j and (x()) -, Σ,Tp, ".P
For items, common way achieve faimess is via the optimization of 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 broad spectrum of fairness notions commonly
adopted in practice, including maxmin fairness (58), Kalai-Smorodinsky (K-S) bargaining solution
[1] - 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 framework, we let the platform freely determine the outcome function and fairness notion for items, by broadly defining the fter-fair solution as follows.
Definition 2.1 (ltem-Fair Solution) Given items' outcome matrix L()), and SWF W AN + R. an itim-fair solution is given by: f E arg max W (()).
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 fairesss for the visibilities (exposure) flexibly accommodate any outcome functions as
received by the items. Our model, however, listed above and any fairness notions supported via SWF maximization (see Section A.2).
Let (z) be the expected outcome received by type-j user at round with recommendation probabilities æ. We again let (z(x)) take a general form: (²)))) = U.J where U (Us,s) se(M)) and Uz, the expected outcome received by 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 contexts. See Section A.I for some example forms of U()) based on discrete choice models (multinomial logit (MNL), probit) used in demand modeling 65 and valuation- models used in online auction design [5].. For generality, do
Single-Sided Usir Solutions.
not impose restrictions on the form of U U(f). but merely assume knowledge of it.
For users, achieving fairness is more straightforward. Since the platform can personalize recom- mendations based on user types, given the users' outcome matrix ((), is best for type-j users to consistently receive the item that offers the highest utility. We thus define the user-fair solution
Definition 2.2 (User-Fair Solution) Given users' outcome matrix U(O), the user-fair solution f A is given by f = 1 if argmax max, ULs and f = 0 otherwise, for all i [N],] E [M].

---

2.3 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 extensive costs for the rest of the stakeholders, as suggested by the following proposition.
Let = min y/ max y. = min U/ max U, and e max max <2. 62; 1/12.1/1 1/N]. There exists problem instance such that: (1) The platform's revemue-maximizzny 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 most 2e of its maximum attainable revenue and any user achieving at most 2c of their maximum attainable outcome.
Proposition 2.1
(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 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 balance the needs of all stakeholders.
2.4 Multi-Sided Solutions: From Within-Group Fairness Cross-Group Fairness
In this section, we proceed to investigate the concept of cross-grout fairness by proposing a fair recommendation framework, Problem (FAIR]. Specifically, we seek answer the following: what constitutes a fair recommendation policy across all stakeholder groups on multi-sided platform?
The platform, our main stakeholder, primarily wishes to optimize its expected revenue, denoted by REV(=) = E r.P,yi. Whenever a type-j user arrives, a revenue- maximmiinxiiiii platform with full knowledge of the instance would show the most profitable item, i.e., i = arg [aX;e[N] T:lk..- with probability one. We let OPT-REV = max,, (EV be platform's maximum attainable expected revenue in the absence of faimess. Such deterministic aveenu-maximizin approach, shown in Section 2.3 is evidently undesirable for the less profitable items and any user who prefer them.
To create 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 0, the platform can first compute item-fair and user-fair solutions ft, f and solve the following fair recommendation problem, Problem (FAIR), to prioritize its revenue maximization goal, while achieving cross- cross-group fairness via fairness constraints:
FAIR-REV = max (EV(#) s.t. (f(x) > 8 0, V [iE #EAM
(FAIR)
0²(a)2 8 0"((") A MEEM,
where 5t.5% E [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 certain proportion of the outcome that they would otherwise receive under their within- group fair solution. One can think of 8t and 6 as tunable handles that the platform can adjust to regulate the tradeoff between fairness and its own revenue (see how platform can tune these parameters in practice in Sections g and C.. a platform wishes to incorporate other operational considerations such as diversity constraints (Xmin I Ji.j I Xmaax 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 xx denote the optimal solution to Problem (FAIR). which serves as the benchmark that we compare algorithm against when 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 weighted sum of platform's 's revenue and items' /users' outcomes. Nonetheless, our constrained opti- mization 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 8' 88" are directly interpretable; (ii) our frumework accommodates additional operational considerations, with results remaining valid.
Remark 2.2 (Selecting fairness parameters via "price of fairness")) To choose the right fairness parameters 8 S9 it is important to understand both (i) the extent of fairness needed for items/users,
5

---

and (ii) the cost of implementing fairness constraints to balance its revenue and stakeholder interests, often known as the "price of faimess"" (PoF). In Section C we investigate the concept of PoF under our framework ( (Problem (FATR)), and show a piecewise linear dependency of the PoF on both (i) the amount of misalignment the platform's 's and its stakeholders' objectives, (ū) the fairness parameters 5², 8 (see Theorem C.I 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 for extended discussion).
3 Fair Online Recommendation Algorithm for Multi-Sided Platforms
In 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.J 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.
3.1 Online Setting and Goals
In an online setting, the platform no longer has prior knowledge of user preference and arrival rates p. At each round f, some con-anticipating algorithm AA generates the recommendation probabilities I, E AN only based on past recommendation { { hrice and purchase decisions {2y he <t. After observing the type of the arriving user Jr, the platform offers item i with probability Zr,,.J,- Following this recommendation, the platform only observes the user's binary purchase decision 2t E {0, 1] for offered item. We will measure the performance of our algorithm using the following metrics:
Definition 3.1 (Revenue and fairness regrets) Consider Problem (FAIR) under a problem instance E O dlm outcome function funcctionnn L(0)= : θ - TR.,,, user outcome function U(0)= O - TRM, item social welfare function W R. I. and fairness parameters 8¹, 3.8" [0, J. Let A be non-anticipating algorithm that generates reconmendattin probabilities Dt at each round t E [T"). We define the revenue regret, denoted by R(T),, and the fairness regret, denoted by (T') of A respectively as
R(T) 1
T Σ (REV(x*, 0) REV( 0)) and Rx(T) mm RT)),
where RT) = max, + (F (x,,,, 0))+ and R max, + ET= (8"
Of 0) (z) 0))* are respectively the maximum time- aveeaavedged violation of item/user constraints. Here, (EV T TIP is platform's 's expected revenue under instance O: ( 0) (0) æs; and O2(2z, 0) U., (0) TT) and (0) are the item/user-fair solutions w.r.t. L(0), U()) and SWF W. per Definition 2./and and 2.2
Eis
x.. are the item/user outcomes under 0: (0)
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 's revenue, item/user outcomes as well as item/user-fair solutions.
3.2 Challenges of the Online Setting
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 0 and limited feedback (as we only observe the purchase decision for the offered items), it is difficult to assess the quality of our recommendations æ; 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 (0), (O) and item/user outcomes O (f (0). 0), O (x,, 0) and (f (0), 0), (z,,, ,, 0), all of which heavily depend on
This sets our work apart from prior works on fairness in recommender systems, which assume full knowledge the problem instance (e.g., [55 7I),, and from works on constrained optimization with bandit feedback (c.g., [38 15 61) which rely on the availability of constraint feedback. As

---

discussed in Section 1.1 the latter works need to access the amount of constraint violation or verify constraint satisfaction after each decision update their policies. For example, in online learning with knapsack, the constraint is 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 B.1p.
(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, we barely offer these items the users, the lack of exploration could also lead to poor estimation for their purchase probability.
3.3 Algorithm Description
We now present algorithm, called FORM (Fair Online Recommendation algorithm for Multi-sided platforms), which handles the aforementioned challenges by adopting a technique, allowing it to achieve both low revenue regret and fairness regret. The design of FORM is outlined in Algorithm T
consisting of the following.
Algorithm 1 Fair Online Recommendation Algorithm for Multi- Sided Platforms (FORM)
Input: (i) N items with revenues RRW ittm outcome L(0): R2N item SWF W A R; (ii) M types of users with user outcome U()): -> I2 N xM, (iii) fairness parameters 8', 8 E [0. 1].
Initialization. Set $1. 1/2 and ûU 1 1/M for i E [N],j [M]. Let the magnitude of exploration be 6 min { (N-1, N at 3). and define the magnitude of relaxation as
= M Mog((T) max v.s. pp.).
(1)
where Fg. = llgg(T))///// m, max{1,t/log(()) -taoooog((((---/////// (o)(2)/2 and Ty.. 5v /1)
For I.....I'
(a) Solve relaxed version of Problem (FAIR) under data uncertainty. Given estimated instance
0: (pt. Wt. r) and relaxation fjc, let d; be the optimal solution to Problem (FIIRREELAX
(h) Recommend with randomized exploration.
Let the recommendation probability be 21,3, = (1 - Ne... + & for all i E [N], E [M]. Observe the type of the arriving user J: and offer item based on probabilities I ~ 26,
Observe purchase decision z E {0, 1} and update the number of user arrivals: rAJ,,t = 1JJ, +
(c) Update estimates for purchase and arrival probabilities. Let
Σ
2,,,, 1)/ 13/211 aed Pett,5 TTs, O.41 (p.41.941,7) (2)
where TyKk E [T' denote the round at which the kth type-j user arrives.
Solve a relaxed version of Problem FAIRR under the estimated instance. Recall, from our first challenge, that we cannot directly verity 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 fairesss for some stakeholders. In face of this, FORM solves a relaxed version of Problem (FAIR), defined as follows:
max (EV 0.) s.t. (x, 2 8" "O 0.) zp. Vi [N] =EAM
(FAIR-RELAX(0,,))) m))
(x 0.) 2 8 of 0.) - [M].
where 0 is the estimated instance at round t and m) 0 is parameter that regulates the magnitude of relaxation on fairness constraints (Fq. (T)). Here, Problem |FAIR-RELAX(( .))) differs from Problem (FAIR) in that (i) it uses the estimated instance ê, rather than the ground -tuth instance 0, and (ii) it relaxes all fairness constraints by the amount of πı. At 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 yy and pp... which are respectively confidence bounds associated with estimated purchase/arrival probabilities (see Definition[D.I] As our estimates become more accurate, both confidence bounds shrink, hence decreasing the magnitude of faimess relaxation.
7

---

Recommend with randomized exploration. In order to handle the second challenge of some items being inadequately explored, we incorporate randomized exploration by sampling from distribution that perturbs the estimated solution to Problem (FAIR). 2t, by carefully tailored amount et. This allows ongoing exploration of all items, with the magnitude of exploration 6 also decreasing over time as our parameter estimates improve, shifting from exploration towards greater exploitation.
Unbiased estimators for our problem instance. Algorithm|] | for simplicity, we estimate purchase probabilities using an inverse probability weighted estimator and estimate arrival probabilities with the sample mean (See Eq. ). For sufficiently large t, our estimates ÿt and p. will be accurate with high probability (see Lemma D.2p. 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.
3.4 Theoretical Analysis
We theoretically analyze the performance of FORM, under mild local Lipschitzness assumption.
Assumption 3.1 Given instance 0 E + there exists constants B, Ç > 0 such that for any 0 E O where 0 Oc I Ç. max - (x, (1 f= I| x<> S B
0 ozc
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 (sec examples in Section A.1p as long as is bounded away from the boundaries of O. For item-fair solutions (*), 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
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, desired. The proof of Theorem 3.1 is deferred to Section D
Theorem 3.1 (Performance of FORM) Given any problem instance E and assume that Assump- tion 3.7 holds, for T sufficiently large, we have that
the revenue regret of FORM is at most [T)) S O b); the fairness regret of FORM is most [[))(T)) S O(MNiT
3.5 Compatational complexity and scalability
In terms of the computational complexity of FORM, the dominant runtime cost in each iteration of FORM arises from solving Problem (FAIR-RELAN (ELAX((,.7))) Note that for a wide variety of commonly used
notions (e.g., maxmin, K-S, demographic parity; see Table I and item outcome functions (e.g., visibility, revenue), solving Problem REAAR-RELAX(O; ne involves solving two linear programs with MN variables, which is solvable in polynomial runtime (*((MN)2+1/1) 40 The remaining operations in each iteration of FORM takes O(MN) time. Consequently, each iteration of FORM has a worst-case complexity of O ((MN))+11115 In practice, however, much better performance can often be achieved by advanced LP solvers such 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(();.)) ) at every user arrival. Instead, platforms resolve the problem after given number of user arrivals or periodically fixed time intervals, while updating user data in real-time. This allows majority of the iterations to run in (MMN) time and removes the computational overhead 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-filterigg stages based on criteria like keywords or price range (e.g., 44)), allowing us to enforce fairness within smaller, context-specne specific subsets. Our fairness framework is also particularly impactful at this final stage, where items with similar attributes compete for visibility and a revenue-maxe maximizinn strategy could lead to extremely unfair outcomes.
"See our additional experiments on MovieLens data in Section F33 optimization problem at most once every 100 user arrivals, while algorithm remains effective.
where we resolve the constrained
8

---

3.6 Extensions to Additional Setups
Our framework, Problem (FIIR) 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 same OMNN /ANN///T1//// 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), J we will let {g, S E [S] s K, E [M]] be the decision variables, where (S) is the likelihood of proposing assortment S to a type-j user. We can then apply the same relaxation-then-ee -ex--ooootloooiiinnn 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/methhod in a real-world assortment recommendation problem.
4 Case Studies on Amazon Review Data
In our case study on Amazon review data, we act as an e-commerce platform displaying featured products incoming users, aiming to maximize revenue while ensuring fairness for items and users. Our experiments numerically validate the efficacy of our framework/methodd 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 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 Py is set 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 challenging instance. Item revenues r; 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 type-j user presented with assortment S, the e"i
probability of purchasing item i S yi.j I+EVes ".. where Vt,y is the relevance score. The
user's perceived utility log(1 + EpES eV.)). 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 ''s primary goal 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- relaxation-then-xpllon then-exploration techniques to produce fair recommendations while learning user data (see Section E.2 To establish generality of our /ramework/methhd, we have also performed additional experiments under alternative outcomes and fairness notions (see Section F22 and an alternative movie recommendation setting using MovieLens data (see Section F3 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 learning phase, we let them use our unbiased estimator 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 's goal; (ii) max-utility: offers K items with the highest user utilities, a user-centric approach; (ii)) min-revemue: offers K items generating the least revenue so far, promoting maxmin fairnsss for items w.r.t. revenue; (iv) random: offers K items uniformly at random, promoting maxmin faimess 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 single- shot recommendation solution. It ensures maxmin fairness for item visibility and envy-free fairness for users; (vi) TFROM [ addresses two-sided fairness in an online setting. focusing uniform item visibility and similar user normalized discounted cumulative gain. However, neither FairRec nor TFROM considers platform's 's revenue; see Section F.I for more details on these two basclines.

---

1O1N9 22.3
100%
65%
(a) Convergence of revenue.
(b) Normalized revenuc.
(c) Item outcomes.
(d) User outcomes.
Figure 1: Experiment results for Amazon review data. FAIR-REV(O" 8") is the platform's 's revenue from solving Problem (FAIR) in hindsight with fairness parameters 8", 5 and FORM(8', , 8.") is FORM when adopting fairnsss parameters 6' 88. In Figures Ic and Id item (user) outcomes shown in ascending order. All results averaged over 10 simulations, with the line indicating the mean and shaded region showing mean + std//
Platform's revenue. We first assess FORM'S efficacy in achieving a low-regret solution. Figure la shows that the time-averaged revenue of FORM, i.e., 7 E.= (EV(2;), converges rapidly to the optimal revenue for Problem (FAIR), complementing Theorem 3.1 Figure Tb compares the time- averaged revenue (normalized by OPT-REV) of FORM with other baselines. As expected, greedy achieves revenue close 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 lb] adjusting 8 and allows platforms to control revenue loss (c.g.. choosing 8", 8 0.2 keeps loss within 10%). See, also, Section[ for how a platform can tune fairness parameters to control its "price of fairness" in practice.
Item and user fairness. Figure Tc shows average outcomes for each item i, normalized by the outcome under item-fair solution, max O
As expected, since our item-fair solution f adopts maxmin fairness w.r.t. item revenues, min-revenue achieves the highest level of item fairness, though at high cost to the platform. Methods such 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 good balance. ensuring all items nearly attain or surpass the specified fairness levels, whether the level is high (6, 0.8) or moderate (ô₃ 0.2).
Figure Id shows the average outcomes for each user type, normalized by their outcome under the user-fair solution, max{ 1, O (zT)/O" 1]. In the Amazon review data, user interests align well with the platform's 's objectives (as validated in Section [C leading to most baselines performing fairly well and achieving high levels of faireess for the users. FORM again ensures good user outcomes, all while maintaining high platform revenue and desired item fairness levels.
5 Conclusion and Future Directions
Our work introduced 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 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 rec- ommendation 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 would be interesting to pursue real-world deployments of our frame- work/algorithm and evaluate their impact using an expanded set of metrics, such as user satisfaction, retention rates, and recommendation diversity.
10

---

Acknowledgments and Disclosure of Funding
N.G. and Q.C. were partially supported by funding from the Office of Naval Research (ONR) (Award Number: N00014-23-1-2584) and the MIT-IBM Watson AI Lab.
References
[1] H. Abdollahpouri and R. Burke. Multi-stakeholder recommendation and its connection to multi-sided fairness. arXiv preprint /907. 13158, 2019.
[2] R. Abebe, S. Barocas, J. Kleinberg, K. Levy, M. Raghavan, and D. G. Robinson. Roles for computing in social change. In Proceedings of the 2020 conference on fairness, accountabilityy and transparency, pages 252-260, 2020.
[3] Agrawal, Avadhanula, V. Goyal, and A. Zeevi. Mnl-bandit: A dynamic learning approach to assortment selection. Operations Research, 67(5):1453-1488 2019.
[4] Airbnb. A six-year update on airbnb's 's work to fight discrimination. https://newe http///ww.....bbbb....../....bbb airbnb com/ /am//ixxyeaadupaatee// 2022. Accessed: 2023-10--2 10-01.
[5] M. Aminian, V. Manshadi, and R. Niazadeh. Fair markovian search. Available at SSRN 4347447, 2023.
[6] J. Back and V. F. Farias. Fair exploration via axiomatic bargaining. arXiv preprint arXiv:2106. 02553, 2021.
[7] S. R. Balseiro, H. Lu, and V. Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 71(1):101-119 2023.
[8] S. Barocas and A. D. Selbst. Big data's disparate impact. California law review, pages 671-732, 2016.
[9] D. Bertsimas, V. F. Farias, and N. Trichakis. The price of fairness. Operations research, 59(1):17-1, 2011.
[10] A. Beutel, Chen, Doshi, H. Qian, L. Wei, Y. Wu, L. Heldt, Z. Zhao, L. Hong, E. H. Chi. et al. Fairness in recommendation ranking through pairwise comparisons. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pages 2019.
[11] A. J. Biega, K. P. Gummadi, and G. Weikum. Equity of attention: Amortizing individual fairness in rankings. The 4 international acm sigir conference on research development in information retrieval, pages 405-414, 2018.
[12] R. Burke. Multisided faimess for recommendation. arXiv e-prints, pages ar arXiv-1707, 2017.
[13] R. Burke, N. Sonboli, and A. Ordonez-Gauget Balanced neighborhoods for multi-sided faimesss in recommendation, In Conference on fairness, accountability and transparency, pages 202-214. PMLR, 2018.
[14] T. Calders, F. Kamiran, and M. Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pages 13-18. IEEE, 2009.
[15] M. Castiglioni, A. Celli, and C. Kroer. Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning, pages 2767-2783. PMLR, 2022.
[16] H. A. Chaudhari, S. Lin, and O. Linda. general framework for fairesss multistakeholder recommendations. arXiv preprint arXiv:2009.024233 2020.
[17] Q Chen, N. Golrezaei, and F. Susan. Fair assortment planning. arXiv preprint 2rX0v:2208.073411 2022.
[18] V. Chen and Hooker. Welfare-based fairness through optimization. Technical report, Working Paper, Carnegie-Mellon University, 2021.

---

[19] A. Dash, A. Chakraborty, S. Ghosh, A. Mukherjee, and K. P. Gummadi. When the umpire is also player: Bias private label product recommendations on e-commerce marketplaces. In Proceedings of the 2021 ACM Conference Fairness, Accountability, and Transparency, pages 873-884, 2021.
[20] Y. Deldjoo, Jannach, A. Bellogin, A. Difonzo, and D. Zanzonelli. Faimess in recommender systems: research landscape and future directions. User Modeling and User-Adapted Interaction, pages 1-50. 2023.
[21] Y. Deng, N. Golrezaei. P. Jaillet, J. N. Liang, and V. Mirrokni. Individual welfare guarantees in the autobidding world with machine-leammn advice. arXiv preprint 220V::2200004748, 2022.
[22] Y. Deng, N. Golrezaei, P. Jaillet, J. C. N. Liang, and V. Mirrokni. Multi-channel autohidding with budget and roi constraints. arXiv preprint arXiv:2302.0152: 2023.
[23] L. Devroye. The equivalence of weak, strong and complete convergence in 11 for kernel density estimates. The Annals of Statistics, pages 896-904, 1983.
[24] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[25] B. Edelman, M. Luca, and D. Svirsky. Racial discrimination in the sharing economy; Evidence from field experiment. American economic journal: applied economics, 92)
[26] M. D. Ekstrand, M. Tian, I. M. Azpiazu, J. D. Ekstrand, O. Anuyah, D. McNeill, and M. S. Pera. All the cool kids, how do they fit in?: Popularity and demographic biases in recommender evaluation and effectiveness. In Conference on faimess, accountabillty and transparency, pages 172-186. PMLR, 2018.
[27] Etsy. ing pages.
Search
engine
optimization
(seo) for shop and list-
https://help.cr etsy com http://///////////aiiillll//// for- and aid-t-pa----ssiinng-aaaaeee
115015663987 100015663997--Sarcc------ segment Accessed: 2024-02-28.
[28] Z. Feng, S. Padmanabhan, and D. Wang. Online bidding algorithms for return-on-spend constrained advertisers. arXiv preprint arXiv:2208. 13713, 2022.
[29] D. Freund, T. Lykouris, Paulson, B. Sturt, and W. Weng. Group fairness in dynamic refugee assignment. arXiv preprint 1.XXi:2331.10644 2023.
[30] Z. Fu, Y. Xian, R. Gao, J. Zhao, Q. Huang, Y. Ge, S. Xu, S. Geng, C. Shah, Y. Zhang, et al. Fairness aware explainable recommendation over knowledge graphs. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 69-78, 2020.
[31] Y. Ge. S. Liu, R. Gao, Y. Xian, Li, X. Zhao, C. Pei, F. Sun, Ge, W. Ou, al. Towards long- term fairness in recommendation. In Proceedings of the 14th ACM international conference on web search and data mining, pages 443-453, 2021.
[32] N. Golrezaei, R. Niazadch, K. K. Patel, and Susan. Online combinatorial optimization with group fairness constraints. Available at SSRN 4824251, 2024.
[33] O. Gülerr, A. J. Hoffman, and U. G. Rothblum. Approximations to solutions to systems of linear inequalities. SIAM Journal Matrix Analysis and Applications, 16(2):688-69) 1995.
[34] S. Gupta, J. Moondra, and M. Singh. Socially fair and hierarchical facility location problems. arXiv preprint 1rXiv:2211. 1481733,, 2022.
[35] M. Harper and J. A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), dec 2015.
[36] H. Heidari and J. Kleinberg. Allocating opportunities in a dynamic model of intergenerational mobility. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 15-25, 2021.
12

---

[37] J. N. Hooker and H. P. Williams. Combining equity and utilitarianism in a mathematical programming model. Management Science, 58(9):1682-1692, 2012.
[38] N. Immorlica, K. Sankararaman, R. Schapire, and A. Slivkins. Adversarial bandits with knapsacks. Journal of the ACM, 69(6):1-47, 2022.
[39] D. Jannach and G. Adomavicius. Price and profit awareness in recommender systems. arXiv preprint arXiv: 1707.0802.. 2017.
[40] S. Jiang, Z. Song. O. Weinstein, and H. Zhang. Faster dynamic matrix inverse for faster Ips. arXiv preprint arXiv:2004.07470, 2020.
[41] E. Kalai and M. Smorodinsky. Other solutions nash's bargaining problem. Econometrica: Journal of the Econometric Sociery, pages 513-518, 1975.
[42] M. Kasy and R. Abebe. Fairesss, equality, and power in algorithmic Decision-making In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 576-586, 2021.
[43] A. Lambrecht and C. Tucker. Algorithmic bias? an empirical study of apparent gender-based discrimination in the display of stem career ads. Management science, 65(7):2966-2981, 2019.
[44] J. Levandoski, M. Sarwat, A. Eldawy, and M. F. Mokbel. Lars: A location-aware recommender system. In 2012 IEEE 28th international conference on data engineering, pages 450-461. IEEE, 2012.
[45] Y. Li, Chen, Z. Fu, Y. Ge, and Y. Zhang. User-oriented fairness in recommendation. In Proceedings of the Web Conference 2021, pages 224-632, 2021.
[46] W. Ma, Xu, and Xu. Fairness maximization among offline agents online-matching markets. arXiv preprint arXiv:2109.0892: 2021.
[47] M. MacCarthy. An examination of the algorithmic accountability act of 2019. Available at SSRN 36/5731, 2019.
[48] R. Mchrotra, McInemny, H. Bouchard, M. Lalmas, and F. Diaz. Towards fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recom- mendation systems. In Proceedings of the 27th acm international conference on information and knowledge management, pages 2243-2251, 2018
[49] Meta. Powered by ai: Instagram's 's explore recommender system. https://aii meta. com/ blog/pooe woog/powered-bee by-ai- ai- 10-01.
Accessed: 2024-
[50] J. Mulvany and R. S. Randhawa. Fair scheduling of heterogeneous customer populations. Available at SSRN 3803016, 2021.
[51] R. Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
[52] M. Naghiaei, H. A. Rahmani, and Y. Deldjoo. Cpfair: Personalized consumer and producer fairness re-ranking for recommender systems. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 770-779, 2022.
[53] J. F. Nash Jr. The bargaining problem. Econometrica: Journal of the econometric society, pages 155-162, 1950.
[54] Official Journal of the European Union. Regulation (eu) 2022/1925 of the european parliament and the council of 14 september 2022 on contestable and fair markets the digital sector and amending directives (eu) 2019/1937 and (eu) 0020/1828 (digital markets act). https:// // leur- lex. europa. mur-lex.euuopp.ec /ttp///gallooootee////////AAA/ httpa//aaa.aaaaaa/////o/////////
2023. Ac-
cessed: 2023-04-19.
13

---

[55] G. K. Patro, A. Biswas, N. Ganguly, K. P. Gummadi, and A. Chakraborty. Fairrec: Two-sided fairness for personalized recommendations in two-sided platforms. In Proceedings of the web conference 2020, pages 199--1204, 2020.
[56] J. Pena, J. C. Vera, and L. F. Zuluaga. New characterizations of hoffman constants for systems of linear constraints. Mathematical Programming, 187:79-109, 2021.
[57] B. Rastegarpanah, K. P. Gummadi, and M. Crovella. Fighting fire with fire: Using antidote data to improve polarization and fairness of recommender systems. In Proceedings of the twelfth ACM international conference web search and data mining, pages 231-239 2019.
[58] J. Rawls. A theory of justice: Revised edition. Harvard university press, 2020.
[59] Y. Seldin, C. Szepesvári, P. Auer, and Y. Abbasi-Yadkori. Evaluation and analysis of the performance of the exp3 algorithm in stochastic environments. In European Workshop on Reinforcement Learning, pages 103-116. PMLR, 2013.
[60] A. Singh and T. Joachims. Policy learning for fairness in ranking. Advances in neural information processing systems, 32, 2019.
[61] A. Slivkins, K. A. Sankararaman, and D. J. Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, pages 4633-4656. PMLR, 2023.
[62] W. Sun, D. Dey, and A. Kapoor. Swfety-aware algorithms for adversarial contextual bandit. In International Conference on Machine Learning, pages 2280-3288. PMLR, 2017.
[63] The New York Times. Food businesses lose faith in instagram after algorithm changes. https /www.nytimes. nytimes. , com hwmm/2022003//// /ttp//////////////nnnnaaaaa///// /ttp://///../a/nagaaaaaaaaaaaa// rewhserrreeeeeeeeeeeeeeeeeeeeeee html 2022.
Accessed: 2022-03-22.
[64] The Wall Street Journal. On orbitz, mac users steered to pricier hotels. com htw.://cc.2888001220000777666663
htttps://wwx Msj Accessed: 2024-08-
01.
[65] K. E. Train. Discrete choice methods with simulation. Cambridge university press, 2009.
[66] L. Wang, Y. Bai, W. Sun, and T. Joachims. Fairness of exposure in stochastic bandits. In International Conference on Machine Learning, pages 10686-10696. PMLR, 2021.
[67] Y. Wang, W. Ma, M. Zhang, Y. Liu, and S. Ma. A survey on the fairness of recommender systems. ACM Transactions on Information Systems, 41(3):1-43, 2023.
[68] C. Wu, F. Wu, X. Wang, Y. Huang, and X. Xie. Fairnes--aware news recommendation with de- composed adversarial learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages
2021.
[69] H. Wu, C. Ma, B. Mitra, F. Diaz, and X. Liu. A multi-ohjective optimization framework for multi-stakeholder faimnes--aware recommendation. ACM Transactions Information Systems, 41 (1(2):1-29, 2022.
[70] H. Wu, B. Mitra, C. Ma, F. Diaz, and X. Liu. Joint multisided exposure fairness for recom- mendation. In Proceedings of the 45th International ACM SIGIR Conference on research and development in information retrieval, pages 703-714, 2022.
[71] Y. Wu, J. Cao, G. Xu, and Y. Tan. Tfrom: two-sided fairness-aware recommendation model for both customers and providers. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1013-1022. 2021.
[72] C. Xu, S. Chen, J. Xu, W. Shen, X. Zhang, G. Wang, and Z. Dong. P-mmf: Provider max-min fairness re-ranking in recommender system. In Proceedings of the ACM Web Conference 2023, pages 3701-371 2023.
[73] M. Zehlike, F. Bonchi, C. Castillo, S. Hajian, M. Megahed, and R. Baeza- Fat ir: A fair top-k ranking algorithm. Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 1569-1578, 2017.
14

---

Appendices for
Interpolating Item and User Fairness for Multi-Sided Recommendations
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 15 For all of these examples, Ui. is strictly increasing w.r.t. the purchase probability yi.-
Multinomial logit (MNL) model. Let the utility of item for a type user be Vi.j 6i, where Vi.j 2 and fi.j is the random part drawn i.i.d. from the standard Gumbel distribution. Let co.j be the utility of no-purchase option, again drawn i.i.d. from the standard Gumbel distribution. The expected utility is US = [max{ U.. + c.j. 60.rH log(1 + exp(es (x.))) + 7 where y is the Euler-Mascheroni constant. The purchase probability is given by Yi IP (U EL, 60,
exp(et.)) Hence, the expected utility can be viewed as Ul, = log( 1- +
Probit model. Let the utility of item i for type user again take the form of Vijj + eij. where the random part ei, and the utility of the no-purchase option co.; are drawn i.i.d. from normal distribution NN o), Here, the expected utility UL, = E [max((is + eigi fo,i]l =
Vi.j
2
Pi. V2a
where ((-) and (³.) are the CDF and PDF of a standard
V2G
normal distribution. The purchase probability is Yig +( V20
We thus have UL
(wr.)))
Valuation-based model. Let Us ~ Pr, be the value of item i for a type j user, where Fas is the distribution of V.g. Then, Vi. = P[[ r.) 0] and UJ, [B[(v,,) rI, where ri is the price (revenue) of item If the valuations follow exponential distribution Uy ~ Exp(A) for some X= > O, we have purchase probability yr, exp(-Ar,) and expected utility U 1 exxp(-Ar) /
A.2 Example Fairness Notions
Given a group of S stakeholders, each indexed by s [S], and any function that maps the platform's decision æ to the stakcholders' outcome (xx) E HR we solve the following optimization prob- lem to ensure that each of the S stakeholders are offered a fair outcome: f arg max (OO())) where the social welfare function W determines which faireess notion adopt. In Table 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 well-off as possible.
Kalai-Sman Smorodinsky (K-S) fairness [41] seeks an equitable outcome where each stakeholder
receives proportional share of their maximum possible outcome. This is represented by proportional allocation up to common factor 3.
Williams fairness (37]: It aims to balance the efficiency/equity tradeoff using parameter A, by prioritizing stakeholders whose outcomes are within of the minimum outcome.
Hooker- Hooker-Williams
Nash bargaining solution: It maximizes the product of stakeholders' outcomes, ensuring equitable distribution that reflects their relative negotiating power and achieves proportional faimess. Demographic parity: It ensures that outcomes equally distributed across different demographic groups, by minimizing the disparity in outcomes between a subset of stakeholders S' and the rest.
See [18 for comprehensive overview for all of the above faimess notions.
15

---

Table 1: Fairness notions and their social welfare functions (SWF).
Fairness notion
Social welfare function (SWF): ((O()))
Maxmin faimess [88
min, O.(z)
Soloo-Smorod (K-S)
Σ, O.(z)) 1 (0,(z)) = 9 max (z(z) for some for 8}
faimess [4
Wilkias fairesss
Σ. max (0.(z) A, min. (x)))), }. for some A >
Nash bargaining solution 53
Σ. log (2(z)
demographic parity
8 Exes Ox(x)) 3-18- Eeets O₂ (z) for some S' [S]
Choosing the right fairness notion is non-trivial and very much depends on the context. important considerations include:
Some
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 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 fairesss notion has a different implication, and platforms need evaluate which best suits their goals and stakcholder needs. For example, maxmin fairness maximizes the outcome received by the most disad vantaged stakcholder, which can be ideal for video streaming platforms like Netflix or YouTube that wish to ensure independent and lesser- known content creators receive fair visibility alongside popular creators. K-S fairness ensures that each individual receives 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 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 discussed in Section I, one important motivation for imposing fairness in online recommendations is the increasing regulatory action. Therefore, the choice of regulatory requirements. For example, since the
fairness notions can also depend on legislative 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 fair level of exposure.
A.3 Example Item-Fair Solutions with Local Lipschitzness
In this section, we discuss a number ftim-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 0 E ② the item outcome L and the social welfare function W are chosen such that
(i) Lig is Lipschitz in 0 for all i E [N],j E [M].
(ii) The item-fair solution f is unique.
Note that statement (i) in Condition A. is satisfied by all of the common definitions of item outcome,
such as (1) visibility: T.,j = P5; (2) marketshare: I..j = PjDl.j; (3) expected revenue: T4,j = PsPjVi.j- On the other hand, the uniqueness condition can be achieved via adding regularization or lexicographic optimization to the social welfare function. light of Condition A.I we enumerate several itir-fair solutions adopting prevalent fairness notions (see Section A.2 for definitions) such that local Lipschitzness satisfied, as outlined Assumption 3.1
Example 1: Item-Fair Solution with Maxmin Fairness. Suppose that an item-fair solution f adopts maxmin faireess, f would be the solution to the following linear program (LP):
s.t. L. D. 2 Vi [N].
#E M ,ER
16

---

Let (p..)))))))))) E θ be two problem instances such that 10 10-08 @c S Ç for some <>
O. We consider the two item-fair solutions enforeing maxmin fairness under the two problem instances. For simplicity of notation, we let ft (0) and f (=)0;; (()) and L L
The item-fair solutions obtained via the following:
(ft arg max FEAR
S.L. L L. 2 2 Vi E [N].
(3)
and
(ff arg
s.t. L L Vi [N].
(4)
M #E wEA N ER
We note that
|f
f' |(f 2-) 22)
(5)
Consider the region D ((xr, L. 2 2 for all i [M], 2 } Under Condition A.
know that (ff, 2²) only feasible point in D. We can then invoke Lemma G.1 (with æ
2²)
and x' = (ftt =*) and the feasibility region D) to bound the distance between (f*, and (ft 5*)
using a Hoffman constant H > and constraint violation term:
|((ft ll < H max -
L. + -2)
(6)
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; |1(2* - f.. loo and (z* ))),,, on the right-hand
side of (6) respectively. Let us first denote E =| Dl
To bound the first term, given that for all i E [N], fz satisfies LT 2 8*, we must have
(=* L. fi, L, f.) S ME.
To bound the second term, let us additionally consider the following auxiliary problem:
(f arg max s.t. LT, 2 + ME
Vi [N).
(8)
#EA FER
Note that if L ...: 2 + ME, we must also have L. _T ME Hence, the feasibility region of Problem 8 is included in the feasibility region of Problem which implies that
(9)
On the other hand, note that Problem 8 is equivalent to
max
ME s.t.
LT Vi (N].
(10)
x #EA OE ER
we perform change of variable 2' = 2 + ME. This implics that
3" ME
(11)
Equations (9) and 11 together imply that
3' S ME.
(12)
Finally, combining Equations
5 66 and
we get
| - 1l <
x*) , (f= (7,5)) || S H max - -I. + (=", =
< SH. H MF = H M L
By statement (i) in Condition
A.I we thus establish the local Lipschitzness of item-fair solution f
that enforces maxmin fairness.
Example Item-Fair Solution with Hooker- Williams Fairness. the platform adopts an item-fair solution f w.r.t. Hooker- Hooker-Williams faimesss with some given A 0 (see definition in Section A.2).
17

---

f 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::
max
s.t. -N
+
2
1m1
(13)
L. ti A S S L ..:: Ad; S S (T A
Vi
Vi
Here, A is a constant that regulates the equitylefficiency tradeoff, and can be any constant such that I' 2 L where L = bo We would fix I = 2M L - A in the following.
Let 0, E θ be two problem instances such that |00 0 S C for some <> 0. For simplicity of notation, we let L = L()) and L = L( Here, using the same techniques as in maxmin faimesss, we let (f), 2²" v² w.. (²)) denote the solution to Problem (13) under the problem instance 0, and (f*, 3", 0, wi, 8) denote the solution to Problem (13) under the problem instance 0. We can bound the difference in the two item- fair solutions similarly by
Ilf 1 I II(f", 2", U. w. 5) (f 27,2", 8. w. lo
< H max (1 (L. Ad:)) 11 max II((L,, A) 1lx, "
(14)
where the second inequality follows from uniqueness of ft in Condition A.1 and applying Lemma to the feasibility region of Problem (13) with the additional constraint 2 2 2". 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 0, which can be characterized using Lemma
G.2
suffices to bound the three terms on the right hand side of (1). The first two terms can be bounded using similar techniques as done in the case of maxmin fairness. Using E = || D and the fact
that L. ... A < 0 < ".. - Ad, for all E [N], we have
0: ( Ad.) < ME and (LI, A) 0. S ME
for all i [N]. To bound the third term in (4), we again adopt a similar technique as above and consider auxiliary problem
N
max mEAN w.w.weRR.,4
s.t. (N - 1)A
8 2
1=1
(15)
D D.. - A ME < U/ 1c + (T A)8;
L. D..
Ad;
ME
Vi
Vi
Let (fI, û, vē, denote the solution to Problem 133 Consider the feasibility region of Problem under the problem instance 0, which contains the feasibility region of Problem 15 This then gives
(16)
We note that if we solve Problem 13 under problem instance, we claim that we must have 6 < 1/2. This is because if 8 > 1/2, we would have w + (T A)o 2 2M > f. - Ad.. That is, the upper bound in the third constraint be tight. However, setting 5 = 1/2 would yield a better objective.
tight, so the upper bound in the second constraint should
Having this mind, we choose Ç > sufficiently small such that ME < 1A (this is doable since (0) is Lipschitz 0. Then, Problem (15) is feasible. We note that (ft, 2, 0, w,
5*) is feasible 2 N.E. This is
solution to Problem (15), where 0g D. ME and úe = w ME, ,=,=",, because under the optimal solution (fr, 2² v², w",,, 8*) Problem [33). both upper bounds for U;
should be tight (otherwise, there exists ā that yields better objective). We thus have
= -NME.
(17)
18

---

Equations 166 and 77
together give
S NMM,,
which bounds the third term in the right-hand side of (44
Having established the bounds in the right-hand side of (14.. we have shown that
| 1 S H NME = NM oloo
By statement (i) in Condition A.1 we thus establish the local Lipschitzness of item-fair solution ft that enforces Hooker- Williams fairness.
Example 3: Item-Fair Solution with Kalai-Smorodinsky (K-S) Fairness. To obtain item-fair solution f under K-S fairness, we solve the following problem given problem instance A:
max 3 s.t. æEAN JEOO11
vi [N].
(18)
where L 1x=xx -E,Li, denotes the maximum outcome that item i can receive. Note that this is achievable if the platform always show item regardless of the type of the arriving user.
By similar arguments as our discussion for maxmin fairness, we would get
H
| - 10 min,
-
min, 1
where the Hoffman constant that can characterized by invoking Lemma G.2
By statement (i)
in Condition A.1 we thus have the local Lipschitzness of item-fair solution J that enforces K-S
fairness.
B Proof of Proposition 2.1
As we discussed in Section 2.3 if 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 (.n.peeeBB.ssbbbiiiie establisssss Proposition 2.1 where we consider 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 problem instance with N items and M types of users. For i E j E [N], let the probability of purchases y1.j and Vi.j = 61 where 61 & 1 for all + 1; probability of arrival Pj 1/M; revenue 122 1/c and r; 1, for all + 2. For simplicity, let the utility of the users Ut. Va.j- Let c max I/N}. Under such instance, we have the following.
Platform's '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/61 >> However, such solution is extremely unfair for any items i + that receive zero outcome. This is also unfair to all users, as they would receive utility from item but only receives utility e from item 2.
An item-fair solution. Suppose items consider visibility as their outcome and adopts maxmin fairness, offering all items equal visibility Ii.j =1/N 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)/Ne1 E1 < 2e. This is also unfair to the platform that prefers item as its current revenue becomes 1/N 1/G 1/c, + 61 1/e1 S 2e 1/61.
1/N + (N 2)/N e1 <1/N 1/c1 1-
A user-fair solution. A user-fair solution would always display item 1 to all types of users. Nonethe- less, such solution is extremely unfair to the rest of the items that receives zero outcome. It is also unfair to the platform, always displaying item 1 results in expected revenue 1, while if displays item it would gain 1/61-
C Price of Fairness
In this section, formally characterize the conflicting interests among different stakeholders using 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.
19

---

The concept of price of fairness was first introduced by 19. which we formally define as follows.
Definition C.1 (Price of Fairness) Given a problem instance θ an item-fair solution f' and user-fair solution f". We let OPT-REV maX REV(Ø) be the maximum achievable expected revenue in the absence of fairness, and let LAI be the solution to Problem (FAIR). The price of fairness (PoF) is defined as
POF OPT-REV FAIR-RET
OPT-REV
The price of fairness, which depends on the problem instance O and between item/user fairness and platform interests, where a lower value is favored by the platform. In Theorem C.I we formally upper bound the price of fairness introduced by Problem (FIR) when we interpolate item and user fairness with parameters 87, 8".
quantifies the trade-off
Theorem C.1 Given a problem instance E θ item-fair solution f and user-fair solution f". Let arg maX (EV(x) (x) be the eovente-maximizing solution in the absence of fairness. If we solve Problem (FAIR) with parameters 8 and 8 and assuming that the problem is feasible, the price of
fairness at most
POF < H. max
max (8+
max (8". JE[M]
-O((9) -
iE(N)
where constant H is the Hoffmman 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 faimess arises from the
misalignment objectives, captured by the difference in items" items"/users' outcomes under the single- sided item/user-fait fair solution and the platform's 's optimal revenue solution, x (i.e., (81 O (f*)
O (x + and (6th Of (z( : A high price of fairness can result from high divergence of platform's s goals from item/user interests (as illustrated by Proposition and and Example [BI] (2)
Theorem C.1 also underscores the value of the parameters 8 and in achieving a balance among stakeholder interests. Both takeaways further supported empirically,
next investigate the price of fairness associated with our case study on Amazon review data in Section C.I
C.0.1 Proof for Theorem C.1
Recall from Section 2.4 that i7 = arg max,e[N] Fitli, is the item with the maximum expected revenue, if an arriving user is of type J. (Here, we assumed that ij is unique without loss of generality.) The
platform's 's revenue- revenue-maximizne maximizingiiigg solution is x:OPT = 1 if iž and 2e O otherwise.
Now, suppose that the platform solves Problem and assuming Problem (FAIR) is feasible. Let
FAIR with some fairness parameters 87,80 8 E [0.1]
F = { E A (x 2 8 ( (²(()) 2 8"h OO("""
Vi [N [M]
denote the feasibility region of Problem FAIR We define
x²
= arg min a F
x OPT
(19)
That is, x' feasible solution to Problem FAIR that closest to OPT w.r.t I1-1loo- Then, by Lemma G.I we have the following bound
||ae
x OPT
H max
max (5+ D. LT max (8" iE[N]
UU. U. U 0
JE(M]]
(20)
where the first term H the Hoffman constant associated with the feasibility region F, and the second term encapsulates how much orr violates the hem/user-faimess constraints.
Now, note that also have
||0'
x OPT
100
(n)
max max jEM
2'y 5
max 2( E9h1
(b)
max 1 - 2zys JEM
(21)
20

---

where (a) follows from the form of x and (b) follows from 1 - F/735 E
2 for Zizig Fhis 2
any + i* This then allows us bound the PoF follows
OPT-REV FAIR-REV
REV(2C) S
S EjE(M] Rey
PoF
OPT-REV
OPT-REV
ΣSE[AN Ri;
S
max JE[M]
1-1
1 12y || xx:00
where the first inequality follows from x' being feasible solution to Problem [FIIR) the second
inequality follows from REV(x') 2 Eje[M]] Rey and OPT-REV = Σ ]E([a]] Rg:, and the final
equality follows from 21..
Finally, combining Eq. 20 and Eq.
finishes the proof.
C.1 Price of Fairness for Our Case Study on Amazon Review Data
In this section, investigate the price of fairness from (Section 3 and shed light on how our fair recommendation framework, Problem (FAIR) can help the platform achieve the right middleground among multiple stakeholders.
study the Amazon review data
In our case study, we act as an e-commerce site (such as Amazon) recommending collection of at most K products to incoming users. There are total of N 30 items be shown to M types users, where the relevance score between items and users as well as users' arrival rates are both obtained from Amazon review dataset [71]; see Section 4 for complete description of the dataset. Assuming that the platform has full knowledge of the problem instance, we solve Problem (FAIR-ASSORT) (here, consider the assortment extension of Problem (FATR); see Section E.2 for details) under different values of fairness parameters 8 8 to investigate how much loss the platform needs to endure in order 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 (6+, 8)). Note that in recommendation problem based on Amazon review data, item fairness 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 lot from the outcome attained under platform's 's revenue- awvenue-mxximizing solution; and (ii) the objective of users (MNL utility) aligns fairly well with the platform's 's objective (revenue). As result, the item-fair constraints constraints in majority of the cases. This can be seen in the left-hand side plot, where we see that POF increases
the binding
significantly when increase 5I. This concurs with the first takeaway from Theorem which suggests that the misalignment objectives directly impacts the PoF.
In the right-hand side of Figure 2 we plot the evolution of PoF when fix 6 = 0 (upper-right plot) and 8 0 (lower-right plot) respectively. Given that the item fairness constraints are primarily the binding constraints, discussed above, observe a linear increase in PoF for the platform as the fairness parameter 8 for items increases. This observation again corroborates the findings presented in Theorem C.1 For the users, in the of Amazon review data, the misalignment of objectives (8" (f - (**TT) only becomes noteworthy as 8 gets close to 1. This indicates that under the Amazon review data, the platform potentially obtain a high level of fair-fairnes at very little
cost, which also matches our findings in our case study in Section
39%
1.0
0.9
PoF 1%)
6.8
6.7
6.6
19%
PoF (96)
10%
0%
0.0
0.2
0.4
0.6
0.8
1.0
6.0 0.4..............
0.0.5.....7.... 0.70.....
Figure 2: Price of Faimess (PoF) in our case study on the Amazon review data. Left: PoF when solving Problem PPIR-ASSORE under different fairness parameters ( The grid colored black if the problem is infeasible. Upper-right: PoF when 8 = 0. Lower-right: PoF when 5 = 0.
21

---

Insights from the case study. Our empirical analysis provides practical guidelines for selecting appropriate fairness parameters 8², 8 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 stakcholders experience the most unfair outcomes under the current recommendation policy. Then, using the piecewise linear relationship established in Theorem C.I 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 fairess 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 faimess parameters efficiently without extensive trial-and-error.
D Proof for Theorem 3.1
D.1 Definitions and Lemmas
We first state 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 4, denoted by & as the event under which our estimates for and p accurate w.r.t. t.
Definition D.1 (Good event) At round a good event &
& = (1p) plli $ Ppo flli- vllo S Tyyeh
(22)
where
T y.t 2og /T) m(())) and m(t) max { {,, //log(T)/22
(23)
Pp, = 53/))
Observe that I p. strictly decreases to 0 as + co. This is also the case for I v.s. To see that, note that m(t), used to define I yy,, strictly increases in and goes to oo as + co. Hence, we can additionally define the cutoff time T, which is time after which the good event becomes "sufficiently good";
T m-min/ {(E [T] y, < 1 - || max y.r. I p..) S G,and m(t) > 1) 0(1) (24)
where Ç is defined in Assumption
3.1 Here we also used yı, E (0, for all E [N], [M]] which is assumed in Section 2.1 so we must have ||y||oc < 1. Here, note that Ty = O( $).
p.t = O(t so T O(max(5 [1) and is ((1) w.r.t. T.
The following lemma states that under the good event, for optimal solution x" to Problem (FAIR) is feasible to the relaxed problem under the estimated instance, Problem
that is sufficiently large, the
Or, n.). while our solution è; is also feasible to the relaxed problem under the ground-truth truth instance, Problem (FAIR-RELAX( m))). The proof is presented in Section D.3
Lemma D.1 (Feasibility under the good event) Given problem instance 0 E Q. Suppose that Assumption /./ holds, where the Lipschitz constant. constant U be the maximum utility the
small neighborhood around 0; that is, (U(() ( xo < Ü for all 0 E ④ such that ||0 0l S Ç. Under the good event E,, when t > T (defined in (24) and log(T) > (2 + ||| loo) ) B, we have the following:
(i) |g < 1,, so Dt...jj (1 Ne, )a.. ; + e, according to FORM.
(i) x² is feasible to Problem FAIR-RELAX m) (ii) it is feasible to Problem (EIR-REL 2m))
where 0, and T) are defined in Eq. I and Eq. @
The second Lemma (Lemma D.2 shows that the good event happens with high probability. Its proof is deferred to Section D.4 D.4
Lemma D.2 (Concentration bounds for estimates) Assume log(T) 1 1/minge|M] Pj- Then for any > T defined in Eq. (24), we have P( < (MN + +2)/T.
22

---

D.2
Complete Statement and Proof of Theorem 3.1
Theorem D.3 (Complete statement of Theorem 3.1
Given problem instance 0 θ and assume max (2 + I| mingc(() Pj have
that Assumption 3.1 holds. Then, for log(T)
the revenue regret of FORM is at most E ( ( the fairness regret of FORM is at most E (T)) S O(MN
Proof of Theorem D.3 We bound the revenue regret and the fairness regret respectively.
(1) Bounding revenue regret.
For a given > T, assume that the good event & defined in Definition D. holds. Let R (Ra,) seini, where Rs,- = TiPzyii denotes the expected revenue that the platform receives from JE|M] offering item to user of type-j. That is, REV(Z, 0) = Σ EEIN Me
Ri, Similarly, for simplicity of
notation, let R. (Re,..) SE(M)) where Re.i.j riftt,
Let us first rewrite the revenue regret at round as the following:
REV(x", 0) REV(X, 0)
Σ
Ris
Σ
Rag
LEIN SE(M))
e JEGM
Σ
Re,i Tt.i.))
Σ
P -Reis) - Σ
(RiggBis R(ass)
KENN JE(M(]
[E[N]
NEN
JE(M
SE(Ae]
Re,s(1i,) (t.iis) + Σ
(1 Ir.i - Re,55)
[
JE(M)
Me(M]
We then have REV(x*
0) REV(E,, 0)
(1 Nea)
Reiis ((,is) + NNe Σ
Besjois Et Σ
Ress Σ
( Ir.is) Resss)
EENN SELM]
<c[N]
SEIM
se[M]]
JEIM
JEIM]
(h)
No
Resghis - 6x
Σ Resss + Σ
(xi - (ess)) Reas)
ME[M]
JE(M(]
NMe
R +M R Rell
NMc R R + NMc, & 2M | R
3M R - Rolloo + NM;
(25)
where (a) follows from statement (i) in Lemma D.I i.c., Feiiyt = (1 Ner a + eg: (b) follows from the fact that e, < N so Ne, > 0, and by statement (ii) Lemma D.I we have that x" and
2 both feasible Problem FAIR-RELAX (0,, m.), and hence REV a 0,) S REV(#, 0 (c)
follows from the fact that E S N.
Note that since
Ra,a.
rrhtssPes riliiipj Ro
=ri (Dr...Prss Vi.jPt. Di.j - VisPi)
ri (Crrs mij)d + Vio (pr.s pij)
(26)
S r. [1 vl1oo + -11ylloo 11pe:-P0 pPl1) hipe-pl11)
ri Ty.t TTpt))
We thus have
REV(x", 0) REV(2,, 0) < 33MF(L T'pc) + NM,, [R]
(27)
23

---

Hence, for any t > T, let F:-1 be the sigma-algbra generated from all randomness up to round t 1,
and
E REVV( 0) REV(,;, 0)]
E E REV( 0) REV( 0) Fr-1]]
$ E E (REV(x* .0) REV(Z 0))((())
Fr-1]]
(28)
(0)
S 3MF (Tus + pp.t - NM, R| 00 + +1
(6)
(MN 2)
R
$ 3MF
(Ty. + NM. R|
T
where (a) follows from (2); (b) follows from the high probability bound for event & in Lemma D.2
given that > T holds.
Finally, by
28 we have
Σ E REV(=* 0) REV(E,, NE[T]
0) [0
T M T
Σ iT
ErTp +w,)+ +
NM
Σ
O(MN+T
T
T
Et
tST
(29)
where in the final equality we recall 6 min {N-1 (N-1,N-3 3t b) and T.. 2log(T) m(()e
2 (og)
O(N $) since m(t) > for all > T defined in Eq.
24
v (T/log(T)) (t)))())/2)))
(2) Bounding constraint violation.
ftem-Fair Constraints. For any item i E [N], and any t >>> T, under the good event &, defined in Definition D.I we have
8 (0) f1 (0) 0t,s
8 (.) (0) (..
Ne) (1-NN)) &GM
8 (0) f,,(() (O) Di,ss + NM (..
2M log(T) max (T p.t: D. + N (.)
(30)
where (a) follows from Lemma D.1 part part (i), which states that under the good event & for > T, we
have Zt,,, (1-Ne) & according to Algorithm (b) follows from Lemma D.I part (iii).
which states 2; is feasible to Problem (FAIR-REE RELAX(6, TJ),, where 7)2 = llog(") max p.t. } according to Eq. (T).
Hence, we have
1
E (5t
(0) (0) [(x.:)]]]]]]
T
1=1
(0) T
2 T
max 11, F
+
T
(8T L., (0) fT, Li. (erna) (T.,())a
1>T
( T x T
m1
+
B3
(0) (0) (0) xTa..) [(86) -P(E) max(1,
T>
( T
- T
max maxx11,7]
+
Σ
22 2M log max (T PT.. T + NM + P(8)) max (1,
T
T>T
(0) T < T
(NM + 2) max 11
max
+
[2M log(T)) max(T n. F,d N M boc
7
-(MNETT3
(31)
24

---

where (a) and (b) follows from 8 < and (0) (0) S m1 depending on the item's
outcome; (c) follows from Eq. 30) (d) follows from Lemma f.2 sufficiently large T. Therefore, the time-averaged stem-fairness constraint violation for any item is at most O(MN
We can perform the same analysis for user-fairness constraints and obtain the same upper bound. The proof is thus omitted.
D.3 Proof of Lemma D.1
We prove the three statements in Lemma
D.1 respectively as follows.
Proof for (i). Consider the following under the good event E,, defined in Eq. (D.
| oc ||ylloo < 1 yl10o
S T M.t
1 - b
(32)
where (a) follows from > T and the definition of T in This gives | 1, and hence given the design of FORM, Zr.i.j
Ne) ce-
Proof for (ii). Here, would like show that xx is feasible for Problem (FAIR-RELAX(O). me)). where 0, and n are defined in Eq. ① and Eq. (2).
Item-Faair Constraints. Let L = || For any i E [N] and a: E A M N. under Assumption 3.1 we have
(.) wi, - (0) ay. S (0.) (,,(00)l S MB |00, - -01ox = MB max (Tp,, pn.t.
(33)
On the other hand, for any [N]. we also have
L. (0.) f.. (0) (0) (1)
(0)) ST. (0.) (..) (1 (0.) ST. - (T..()))
L, (0.) (0)) ft. (0) + (L..(0)) (0) (1)
(34)
ML (0,) - fi, (0)] + M (o:) - (0)
MLB 00 + MB -1@0, 011o0
BBL + 11) m p.t, I g.
where the last inequality from the fact that for all T (see definition in 24 ). under the good event &
100 Ol1cc max [ - y oo. 1p - plooo S max -yll 1pp. pll1} S max(T v.1. T. p..)
Since x= E AN is the optimal solution to Problem FAIIR. we know that L.. (O) Tot 2 8t. (0) TT, (0). We thus have
(0.) T x + MB- max(T p.t. Fy.c (0) at. > 8T. L. (0) (1. (O)
2 8F (0.) (0.) MBL 1) max (Tax(T yy.
(35)
where the first inequality holds because of Eq. Hence we have
33 and the third inequality holds because of Eq. (34).
L (..(0.) To) 8t. (O.) (0.) (MB 8 MB(L+ mmx p.t, Tv.c)
(36)
(0.) 2 6t. (o. TT ((.) M log(T)) max,T
where (a) follows from log (T) (2 F) B 5t BBL 1). Since the amount of relaxation
is 7/ = M log(T) max we ). as defined Eq. [ we show that x² satisfies the item-fair constraints for Problem FAIR- RELAX 0,,
25

---

User-Fair Constraints. For any j [M] and æ E AN under Assumption 3.1 we have
U.,(0.) (a.().)).... m..j (0) m. - [0,5(0)) (0.) U. (1)= - Bll0. Øl1co B max (T p.t, T y.t
(37)
Also note that for any problem instance 0' E O we have that
(0)(0") fhJ (0") max U (0')
ic N
Hence, we have the following:
f2 (O,)
(0) (0
U1 (0t) max (0) NE[N]
max iEIN]
U. (.) (0) S Bl - 01 = B max (Tptt l yx
(38)
where the second inequality follows from local Lipschitzness of (@)). Now, since x" E A is the optimal solution Problem FAIR we know that (.) 2
8" UU, (0). Combining this with the Eq. (37 and Eg. 38 we have
(O, 2.. + B max(1' me, ye 2 U (0) x 2 8 UU (0) (0
(39)
2 8 U., (1)) f.
5 max v.
Hence we have
U.) 2 (0. f") (0)())))))))))))()) (1 + 80) B max (T p. I 92 U.) æ. 2 U. 0.) f., (0.) M (Tg max (T' p.ts g.
(40)
Proof of (iii). We can show ã; is feasible to Problem RELAX(O, 17)) via a similar argument as our proof for (ii)
Item-Fair Constraints. First note that
(i) Lr MB max p.r, 3
(0)) Ta,,:
(41)
WS N
8T.
(0.) M log(T) mT p.t. y.
8t. (0)
T f.. (0) .M log(T) max P... yy.t 8LMB(L + 1) g.
Here, (a) follows from an identical argument as shown in 33 while replacing æ with 6;; (b) follows from feasibility of 2; Problem (FAIR-RELAX(B. m))); (c) follows from 34). Hence, since
lTg (2 + B) + B'L + 1), we conclude
(0) b.... 2 8 (0) fi,
2M log(T)) max(T p... y,
(42)
User-Fair Constraints. We again follow the same arguments as our proof for (ii) and establish the following:
(0) 2e,.5 max p... ma.. Ty.c
(O, De.is
(0))
(43)
8 (
(0.) fb (0.) MM log(T') max(T p.r, Ly,t
2 8 ( f (0) .M log(T) max(T p., I p, 80 max(T Py.h
which then gives
U. (0) Deis > 8" (0) (0) 2M log(T') max(T p.c. I Ty,c.
(44)
26

---

D.4
Proof of Lemma D.2
For completeness, let us recall the definitions of I y. and m(t) in Eq. (23
y.t Vm(()e, m(l) = max Tog(T) Volog())
We define related variables r v.d and (t) followed:
F F..j = 2 (T)
my (t) = max tp, - (loo(T)//).
(45)
v (t)
Since for log(T)) min and & > T (see definition of the cutoff time T in (24) such that m(t) > 1, we know my(() 2 m(t) and thus y, Fu.j. for any j E [M]. We thus have
PP ( - Fiyl 2 r v.1) - 12 [b6.5.011 - -i.l 2 v.,..))
(46)
Hence,
P(E)) < P((l yllo 2 F.,)) P( pll p.e))
Σ
Σ
P P(00:jic1--1 m..) + P( pll1 2 Tp.)
kE[N] JE[M]
Σ
Σ P (1065,41- - biit) P(((lp p1l 2 p.))
(47)
JE(M]
ΣΣ
1 (1015.41- Vayl v...) T
NEIN JE[M]
where (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 6 = 7-- Hence, in the following,
suffices to bound P [0r.j.e-1 - Vinl 2 v....) for any i E [N], E [M].
Recall that ni.a is the total number of type j arrivals up time 1.. Then, consider the following
IP (1065.41 - Vi.ll 2 T v....)) = 10i.j..-1 - Vcyl 2
π v.j.t Rz 2 mt(t)
(10,.,11111 - -hll 2 r v.d.a Rjaa < mmy(1)
< P 01..e11 - -isl 2 Tid Mj,t 2 (t) + IP (n < m)(())
(48)
We would bound terms A and B respectively.
Bounding A. Recall that TjA E [T] is the round at which the kth consumer of type j arrived.
A P (0441,55
Vio T Ty.ie Mijt m2(())
TU = -,, Zrz, = 13
SP(
2 >T Pu.jee Mija 2 mt(t))
max (ytt)Snge
VVij
11
i, Rr
2 [
max
Yis
Sn
(49)
I1I
i, Kry
Σ P
2 I w.iii
Yho
my St)
I
= i, 27, = 13
2 log 2lgg(T) Vnee
Σ
-Vhs
my Sn)tt
27

---

where in the final inequality we used the definition of r 9.j.t in 45) and the fact that m 2 (t()). Note
=1)
that for any & E N, we have E generated from all randomness up to round Tjkk- Therefore, Mr Martingale difference sequence. Further, we have
F T.
Mij. where Fr5,x is the sigma-algebra 11 =
yio is
(a)
0 M
S Mr I DT
(50)
CT,,K
Ct
where (a) follows from the fact that 2T,,a.h.
1 2 ET if 11 2 1 and Frya.d.f (1
Ne; ( + 6Tza ETyA if |1 < according FORM (Algorithm
1
(b) follows from
a S N so
2 2 and hence M₁ 2 -1
Also,
T( F3.k = i, ZTzN 1}
1
1 -
E
M
T.k
E
Frsh
Vi.s
(51)
Et.
Hence, by Bernstein's 's inequality (see Lemma G.4, we have
PP
Mr
2 V(e 2)Vn log(2/8)
kE(n)
(52)
[a)
11r,
i, Rrz
11
log
P
Vi.l 2
VNEi
T
where (a) follows from invoking Lemma Combining Eq.
G.4 by taking ca = Eo
and Vs
26 logg
(e-2)er and
277
449 and Eq.
522 yields
A S
Σ
2
2
2
(53)
T2
T2
T
My Sf)
Bounding B. Denote M: = [JJ, = j) PA and it is easy to see Mr is a Martingale difference
sequence bounded between [-1, Hence, by recognizing N2y, - L P3 = Σrete M, and applying the Azuma-Hoeffding inequality, for any > O, we have
P P(N3 t.p; < -c) =P -0)=
Σ
Mr < -c) s exp (-2:
TE(()
(54)
= B = 1C=P(nn n2, m,(t)) = P (2 t. Pÿ < - -Vtlog(T)//)
(a)
1
I
T
where in (a) we take = vt Vtlog(T)) 122
E Extensions to Additional Setups
Our fair online recommendation framework, Problem (FAIR and method FORM can be extended to accommodate additional variants of our setup. In Section E.1 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.
we discuss how our framework/method
E.1 Fair Online Recommendation with Periodic Arrivals
In real-world scenarios, user arrivals are often aoa-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
28

---

to weekdays, Recognizing the presence of these periodic patterns, we extend our concept of a fair solution and our algorithm FORM accommodate the online setting with periodic arrivals.
Consider a scenario where users arrive in each round t E (T) according to a probability distribution
P: E A M. Additionally, suppose that there exists period length Q E T) and distributions p()) ..... p()) such that PmQ+0 = p(9) for any m 0, 1, 2...... and g - 1... Q By defining p the time-averaged arrival distribution, represented by p + Etelry Pt. we generalize the fair recommendation problem, Problem (FIRR), 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 p1 .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 + via the following:
Po+1. min W)
1
Σ
1J= - j}
(55)
By 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.
Theorem E.1 (Performance of FORM under Periodic Arrivals) If we apply FORM (Algorithm !
5ylog(3T) with
with an estimated arriving probability Pit1, taking the form in Eq. (55) and T p.a VW
sliding window of size W- QT3, Then, for sufficiently large T. we have the following:
the revenue regret is at most [[R(T)) I O(MN3T $)
the fairness regret is most [ I O(MN
The proof of Theorem E is provided in Section E.I.I
Remark E.1 (Lack of knowledge of the period length) We remark that in the periodic setup, assume knowledge of the period length Q > 0. This assumption aligns with practical scenarios where platforms are aware of intraday, daily, weekly, 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' =a= 1,21,2.. Q for some Q >>0 Q. Each expert produces estimates of 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 signisicantly violate constraints, resulting in overall large constraint violations. Therefore, optimizing the fair solution under periodic arrival setup with an unknown period length remains open question.
E.1.1 Proof of Theorem
First, similar to Lemma D.2 that presents a concentration bound for empirical estimates of p using all historical data, if 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.
5 5v/log3T) VW
P P(Ip- pelli
(56)
Recall the definition of in Eq.
We additionally define
T max (W + 1,7) = -
(57)
29

---

Following the same analysis as bounding the regret for Theorem 3.1 in Eq. (29 while replacing T
with T and considering p,, á (31)
have
VW
Σ T 1El2
1
REV("", ,0) -E 0)
1 so T M
MN
Σ(l a
+
T DTT
T
t2T
O(MN
similar analysis as Eq. 31 applies to bounding the fairness regret (T)
E.2 Fair Online Assortment Recommendation
Our model in Section 2 primarily considered a setting where single item is offered to each user at each round, which applies to various real-world settings. this section, we discuss an extension of our framework/methodd to 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 number of most relevant jobs are recommended to candidate, e-commerce sites, where a small assortment of items might featured on the front page whenever a user arrives.
Extension of our framework. To consider an assortment recommendation setting, we let way > 0 be the weight associated with each item for type-j user. If type-j user arrives onto the platform and gets offered assortment S, he/she will choose/purchase item from the assortment with probability wh., (9)+ where wy (5) Lies Wi.j- based on the MNL model (65] This different from the single-item recommendation setting, where we have well-defined purchase probability yi, for each item-user pair. When recommend assortments, the purchase probability not only depends item's weight, but also the assortment it gets presented in. Given that, we define the problem instance as 0 (p, w,)).
Our fair recommendation framework, Problem (FAIR), can be readily extended by letting our decision variable be q {u, (S) S C [S] < K,j [M]]. where gj (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 REV()) s.t.
OF(a) 2 8 Of(S5) Y (N
(FAIR-ASSORT)
09(4)) 2 8 (f( v ije
where
IES EieST TAWLS wy
REV()) Στ Pj
Σ
(5(S)
JE[M]
SEINISSISK
denote the expected revenue under recommendation q. On the other hand, the forms of the item/user outcome functions O (q, 0), 0 (q, 0) as well as their respective fair solutions f= (0) can
again take any forms that depend the problem instance 0, based on their needs.
Extension of our algorithm for the online setting. Given the extended framework Problem (SSOR-ASSORT), we can similarly extend the algorithm FORM for the assortment recommendation setting, which outlined in Algorithm 2
Here, Algorithm@ follows the same relaxation wwwpaattionntee-eeeplle thee-expoooationn design as discussed in Section 3.3 and
Algorithm [ Whenever our estimate of the problem instance 0 is updated, the algorithm first solves relaxed version of Problem (FSIR-ASSORT] using the updated estimate, and then adds randomized exploration to stimulate learning: see Steps 2(b) and 2(c) in Algorithm 2
The main difference between Algorithm 2 and Algorithm I lies in the learning mechanism. order to learn the weights in the assortment setting, adopt the learning mechanism from MNL-Bandit 3. The rounds in which type-j arrives are divided into epochs. In each epoch f the same assortment Sy is offered until 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
FFor solving Problem FFIRR ASSORT) in our numerical experiments in Sections and F2 we use the CBC
solver accessed via the PuLP library in Python.
30

---

Algorithm 2 FORM for Assortment Recommendation
Input: (i) N items with revenues E RR item outcome OfG, ,, [N] and item-fair solution f'); (ii) M types of users with user outcome O :.... [M] and user-fair solution (.) (iii) fairness parameters 8", 5, E [0, 1]. (iv) parameters and Tj--
Initialization and Setting the Parameters. For
[N].j E [M] initialize dh..., = 1/2 and fi.j = 1/M. Randomly select S, ~ S, where S = {S _ MM & K} denote the collection of all possible assortments. Let lg = 0, Te 0.
2. While v T.
Observe the type of the arriving user Jj and offer assortment S Update number arrivals nu,ec + TAJ,, + 1.
Observe purchase decision 2, E (0) U Sy, (where 0 means no-purchase)
=0
(a) Tr.,, T. U (L., for E S.,, where Te,,, the epochs in which item gets shown user type Jc. Then, increment és, Ls, + 1, where fs, denotes the number epochs for user type Jr.
(b) Update estimates for item weights and arrival probabilities. Let
Σ
Σ
I[2, = vi [N] and Pr.j
1 T Vj E [M]
TE.
TET 1EE,,
(58)
(c) Solve Relaxed Problem [FIR-ASSORT)) with the Estimated Instance. Given estimated instance A = (pi, ii r)) and the magnitude of relaxation nj. let qi be the optimal solution to the following:
max REV 0c) Ol(g.0.) 8' Of To V Viell [N]
(59)
0, 2 Of 0.) V jE [M),
(d) Recommend with Randomized Exploration. Update the assortment be recommended type-Ja user based on the recommendation probabilities SJ, ~ qt, where
q (9) = (1 (Slec)
VS E E.j. [M].
(60)
Else, E E (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, e, and Tt, are adjustable inputs for platforms to fine-tune in practice.
While 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 stimulate learning, seamlessly transition to the assortment recommendation context. The efficacy of our extended framework/method in the assortment recommendation setting further validated in our study Amazon review data (see Section
F
Supplements for Case Study on Amazon Review Data
F.1 More Details of Our Baselines
In this section, we discuss the baselines introduced in existing works, specifically FairRec [55] and TFROM (71), which are state-of-the-ate approaches targeting multi-sided fairness. We detail the main setups of both approaches and highlight the key differences between these methods and ours.
As we briefly remarked in Section 4 FairRec targets single-shot recommendation problem where there are N items and M users, and makes 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)) A, C [N], A, < K} denote the the algorithm's 's recommendation decision. The authors of [55 show that FairRec can achieve (i) maxmin share (MMS) of visibility (exposure) for most the items and non-zero visibility for the rest; (ii) envy-free up to one item (EFI) fairness for every user, meaning that for every pair of users
FairRec 55
31

---

j.3 E [M], there should exist an item p E Ay such that the utility that user j receives from Ag is at least the utility that user j' receives from Ay {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 wide range of outcome functions and fairness notions, as discussed in Section [2.] See, also, Section F2 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 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 quality-weighted fairness regarding item visibility (see Definitions I and 2 in (7T). For user fairness, TFROM aims to achieve uniform normalized discounted cumulative gain (NDCG) among users. [7]] 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 faireess. TFROM is provided in two versions: one for the offline setting and one for the online setting, with the latter dynamically maintaining low variance item exposure and user NDCG scores over time. We compare our algorithm with the online version of TFROM in our experiments in Section
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 learning stage, ignoring potential biases from corrupted data; (ii) It focuses on pre-specified outcomes and fairess 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 faimess in recommender systems, balancing the interests of the platform, items, users, and potentially other stakeholders. The efficacy of our framework is highlighted in Figure Tb] showing how our algorithm manages maintain high platform revenue while ensuring fairness for other stakeholders.
framework takes step forward and adopts multi-sided perspective,
F.2 Additional Experiments under Alternative Outcomes and Fairness Notions
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", while keeping all other setups and baselines the same in Section 4
Maxmin fairness w.r.t item visibility. Results are shown Figure
K-S fairness w.r.t. item revenue. Results are shown in Figure 4
K-S fairness w.r.t. item visibility. Results are shown in Figure
Overall, the results from Figures 3 and are consistent with those previously observed in Figure [ 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 8 and 5", 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 wuthin-group faimess. 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.
32

---

100%
HOMME'S 7-6
5400 24
2010
(a) Convergence of revenuc. (b) Normalized revenuc.
(c) Item outcomes.
(d) User outcomes.
Figure 3: Additional experiment results for Amazon review data. Here, the item-fair solution adopts maxmin fairness w.r.t item visibility.
90%
00%
530
3008
1500
2009
(a) Convergence revenue. (b) Normalized revenue.
(c) Item outcomes.
(d) User outcomes.
Figure 4: Additional experiment results for Amazon review data. Here, the fair solution adopts K-S
foirness w.r.t item revenue.
E3
Additional Experiments on MovieLens Data
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 method's effectiveness balancing platform revenue and stakeholder fairness in various types of recommender systems.
Here, we act as a movie recommendation platform that shows "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 their preferences. As the movies are not associated with revenues, we let r; = 1 for all E [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 s marketshare, with user utilities captured by the MNL. model. In this set of experiments, consider a total of 7 2000 rounds, where at each round there 100 user arrivals. During each round f, 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 observed in in terms of the platform's '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 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
study Amazon review data (Section[4) both
G Supplementary Lemma
In this section, we state some useful lemmas that would be invoked in this work.
33

---

100%
4000 04
00%
(a) Convergence of revenuc.
(b) Normalized revenuc.
(c) Item outcomes.
(d) User outcomes.
Figure 5: Additional experiment results for Amazon review data. Here, the item-fair solution adopts K-S fairness w.r.t item visibility.
142 A.0-RAO1... 2021
(a) Convergence of revenue. (b) Normalized revenue.
(c) Item outcomes.
(d) User outcomes.
Figure 6: Additional experiment results on MovieLens data.
Lemma G.1 (Approximations to solutions systems of linear equations ((33), Theorem 2.1))
Let A E Ruxn and ((A)
max
A an extreme point of (A)) where
(AA = {A E Rm A 2 O, I1 All < 1}. Then, for each b E Ik such that
{ar E R" Ax < and for each xx
E R have:
min A
x x
((A)
| -A
b)
where ((A) is known the Hoffman constant.
Lemma G.2 (Characterization of Hoffman constant (156), Proposition 2)) Let A Rm The Hoffman constant (AA) defined Lemma G.1 can be characterized as follows:
(A)) max max {1|0| :0 |Jol 5 JEU A full rank
max J m min DEn. A AJ 1111 Ag full rink
where A denotes the submatrix of A that only includes the rows in J C (1....,m
Lemma G.3 (Empirical distribution concentration bound w.rt. {-1 norm ((23), Lemma 3))
Let p E AN and p ~ Multinomial(1. n, p). Then, for any ö E [0,3 -xN5(- have
[pp |p--1 - 11 5 5Vlog(3/8)
<8.
Vn
Lemma G.4 (Bernstein's inequality (159), Theorem 8)) Let M1,
a martingale differ-
ence sequence. Assume there exists deterministic sequences Ci, C2. ... and Vi, V2,... such that log(2/0) < 1.
[M I c and E M = Vi for all k. Then, if / (c-2)V, e,,'
we have
P Σ Mr 2 Vle 2)V log(2/5) $ 8.
(61)
kE|ml
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: As discussed in our abstract and Section D our main contributions include (i introducing a novel fair recommendation framework, Problem (FAIR). that flexibly balances stakeiittkee interests, and (ii) introducing low-regret algorithm FORM that simultaneously learns user data and performs fair recommendation in a dynamic online setting, whose efficacy is further validated in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
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.
Justification:
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 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 vell-specificattin, 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 few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
35

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have provided all necessary assumptions and proof's for our theoretical results (e.g,, see Section D for the proof our main result, Theorem B.I). We have also provided proofs for any theorems and lemmas that show up in our appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided code and data for our numerical experiments in the supple- mentary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
36

---

(d)
reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided code and data for our numerical experiments the supple- mentary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips ctcipsscc//ublicc/ee httppppwwwpppps.p.ppppppppaaaaae www.eoobmissiinnnoaii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e-g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have detailed the setups of our numerical experiments in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: As stated in Section 4 all results averaged over 10 simulations. In figures, the line indicates the mean value and the shaded region shows mean + std/vI0.
Guidelines:
37

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors 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 out of range (e.g. negative eтror 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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 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, 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
This paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
38

---

Justification:
This work contributes to enhancing fairnsss in algorithmic recommendation decisions, and we do not anticipate any negative societal impact from the research. If any concerns arise regarding the use of sensitive user or item attributes in determining user types, the platform can exclude such information and instead rely on non-sensitive attributes, as noted in Footnote [
Guidelines:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
All baselines used in our numerical experiments have been cited.
Guidelines:
The answer NA means that the paper does not existing assets.
39

---

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 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 datasets..paerssttt paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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 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 anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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 crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
40

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
41


Reviews:
[{"review_id": "h9OhLbfHTG", "reviewer": "Reviewer_Pu7z", "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.", "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?\n2. 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?\n3. I'm wondering if there could be any intrinsic tradeoff between the revenue guarantee and fairness guarantee.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses the often-overlooked complexity of balancing the interests of multiple stakeholders in optimizing recommendation systems. The proposed FAIR framework offers a solution by ensuring fairness for both items and users while maintaining platform revenue. The extension to a dynamic online setting where data uncertainty is present is reasonable. The FORM algorithm's ability to learn and adapt in real-time is a merit for practical applications in environments where user behavior and preferences are nonstationary. This work also provides a robust theoretical foundation for the proposed framework and algorithm, including proofs of sub-linear regret bounds.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We’d like to address each of your questions below. \n\n**W1. Regarding computational complexity and scalability,**\n- Please see (1) in our global response.\n\n**Q1. Regarding our sublinear regret upper bound**, we’d like to highlight the following:\n- **Challenges of designing no-regret algorithms in our setting.** While our algorithm essentially solves a constrained optimization problem at each round, it is important to note that one cannot directly apply other off-the-shelf algorithms for online constrained optimization with bandit feedback, including \n    - (i) Bandits with knapsack algorithms [37,15, 56]. In these works, their constraint is a budget constraint that can be directly evaluated, which is critical in helping attain a known optimal per-round regret of $O(T^{-1/2})$ in their setting.\n    - (ii) Gradient descent without a gradient (Flaxman et al. 2004, arXiv:cs/0408007), which assumes that the optimizer can analytically evaluate whether all constraints are satisfied and attains $O(T^{-1/4})$ per-round regret. \n\n  However, our setting is different from and more challenging than these off-the-shelf methods, as we can neither determine the amount of constraint violation, nor analytically evaluate the feasibility of our fairness constraints (see discussion in Sec. 3.2). Despite the extra challenge, our $O(T^{-1/3})$ regret upper bound is already superior to the $O(T^{-1/4})$ from the latter work.\n\n- **The optimal attainable regret remains an open question.** To the best of our knowledge, the optimal attainable regret for an online optimization problem with uncertain constraints like ours, where at each iteration we are only allowed a one-time bandit feedback (i.e., the purchase decision), remains an open problem. We appreciate the reviewer’s question and will mention this as an exciting future direction.\n\n**Q2.1 Regarding the tradeoff between item and user fairness,**\n- In our framework, there is no inherent tradeoff between item and user fairness. Since both are enforced as fairness constraints, increasing the level of item fairness (i.e., $\\delta_I$) does not reduce the level of user fairness (i.e., $\\delta_U$). The only thing to note is that if both $\\delta_I, \\delta_U$ approach 1, Problem (FAIR) might become infeasible, in which case the platform would need to decide whether to reduce the level of item fairness or user fairness. However, as observed in our case study, infeasibility occurs rarely—in our case study, Problem (FAIR) is only infeasible when $\\delta_U $ → 1, representing a strictly user-fair solution (see Fig. 2 in Sec C.1, where we evaluate Problem (FAIR) under different parameters). \n\n**Q2.2 Regarding choosing parameters $\\delta_I, \\delta_U$,**\n- Please see (2) in our global response.\n\n**Q2.3 Regarding \"What if we care about $R^I+\\lambda R^U$\",** \n- **Clarification on our metric.** We believe that there might be some misunderstanding regarding our framework's main objective and would like to first clarify the following. In contrast to a multi-objective optimization framework that **maximizes outcomes** for items and users, our framework Problem (FAIR) focuses on **minimizing regrets**. In Def. 3.1, our fairness regret is defined as $R_F(T) = \\max (R^I_F(T),R^U_F(T))$ because our goal is to find a regret upper bound that can simultaneously apply to **all items/users**. Here, the fairness regret $R_F(T)$ measures the maximum gap between the fair outcome and the time-averaged outcome for any item/user. Therefore, the $O(T^{-1/3})$ regret upper bound we established for $R_F(T)$ is an upper bound for the fairness regret of any item $i$ or user $j$. As a byproduct, for any linear combination of item/user fairness regrets ${regret}_i+\\lambda{regret}_j$, the same regret upper bound always holds. Our sublinear regret bound means that for any item/user, our algorithm guarantees that their long-run average outcome will reach the desired proportion of their fair outcome.   \n\n- **Our framework’s advantage over multi-objective optimization problems.** We also remark that our Problem (FAIR) is a constrained optimization problem, not a multi-objective optimization problem that jointly maximizes outcomes for platform, items, users. This distinction is critical as it impacts how fairness is achieved—via constraints rather than via direct optimization of outcomes. \nSuch a framework enjoys several advantages, as stated in Remark 2.1. At a high level, our framework uses interpretable parameters $\\delta_I,\\delta_U$ that directly relate to the level of fairness for items/users, rather than maximizing an aggregate function like $rev + \\sum\\lambda_iO_i+\\sum\\lambda_jO_j$ where the choice of Lagrangian multipliers $\\lambda_i,\\lambda_j$ are less straightforward.\nIn our framework, if one wishes to impose fairness w.r.t. some linear combination of item/user outcomes, they can simply include a similar fairness constraint: $AO_i(x)+BO_j(x)\\geq\\delta\\cdot(AO_i(f^I)+BO_j(f^U))$, where $f^I,f^U$ is the item-fair/user-fair solution and $x$ is the recommendation policy. All our methods/results continue to hold.\n\n**Q3. Regarding tradeoff between revenue and fairness,**\n- Our sublinear theoretical guarantees for **revenue regret** and **fairness regret** in Theorem 3.1 are always attainable under our framework/algorithm. \n- There indeed exists a tradeoff between platform’s revenue and fairness. As we highlighted in Remark 2.2 and discussed in detail in Sec. C, this tradeoff can be quantified by platform’s price of fairness (PoF), i.e., its loss in revenue due to maintaining fairness. See Fig. 2 for an illustration of PoF in our Amazon case study. As we showed in Theorem C.1, the PoF can be quantified by (i) the magnitude of fairness parameters $\\delta_I, \\delta_U$ and (ii) the amount of misalignment in platform’s and its stakeholders’ goals. As discussed in (2) of our global response, a platform can use PoF as an indicator for picking the right fairness parameters.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rz4wTCT5Ql", "reviewer": "Reviewer_kac1", "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.", "questions": "1. The paper assumes that user types are fixed, but in practice, user preferences may change over time.\n2. the universality of the fairness definition: is the definition of fairness proposed in the thesis applicable to all types of recommender systems?\n3. the case study uses only one category of data from Amazon, is it sufficient to demonstrate the universality of the approach?", "limitations": "please refer to \"weakness\"", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The needs of multiple stakeholders (users, items) are considered simultaneously and Fairness parameters can be adjusted as needed.\n2. Theoretical bounds on algorithmic performance are effectively proven.\n3. It has a degree of practicality, with case studies demonstrating application to real data.", "weaknesses": "1. The computational complexity of the algorithm, especially its scalability in large-scale systems, is not discussed in detail in the paper.\n2. The choice of δ_I and δ_U may require a lot of experiments to find suitable values.\n3. The model assumes that the user type is known, which may not always hold in practical applications.\n4. the paper mainly focuses on short-term fairness and does not delve into the impact of long-term fairness.\n5. this paper mainly uses gain and fairness regret as evaluation metrics and more metrics may be needed to fully evaluate system performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback! We’d like to address your questions below.\n\n**W1. Regarding complexity and scalability,**\n- Please see (1) in our global response.\n\n**W2. Regarding choosing fairness parameters,**\n- Please see (2) in our global response for a detailed answer to this question.\n- In our global response, we discussed how a platform can select fairness parameters based on its “price of fairness” (PoF) (see Sec. C in our paper for more details). We also explained how a platform can identify a small range of promising parameters for A/B testing based on desired fairness levels and acceptable PoF, thus avoiding extensive experimentation.\n\n**W3. Regarding unknown user types,**\n- In real-world recommendation systems, platforms often have access to features that can be used to determine user types, even when sensitive features (e.g., gender, race) are restricted due to regulations. For example, Orbitz.com [https://tinyurl.com/yatek26w ] categorizes users based on the type of device (Mac versus PC), while other platforms may use zip codes for user categorization [“LARS: A location-aware recommender system\"]. Historical data, such as purchase history, can also be used to cluster users, ensuring that users within each cluster have similar preferences, while users across different clusters exhibit distinct tastes. We'll include this discussion to our setup section. \n\n**W4. Regarding long-term fairness,**\n- This is a great point! Our method aims to calibrate the recommendation policy within a shorter time period (e.g., a month) when user preferences are relatively fixed. By imposing item/user-fairness over this shorter time period, we expect that in the long term, our approach can contribute in the following:\n    - **Long-term fairness.** By introducing more diversity in our recommendations, we can help mitigate the “winner-takes-all” phenomena often seen in online platforms [https://tinyurl.com/4efxc54k ].\n    - **Long-term growth.** The platform can attract more items (while retaining the existing ones) and more users (including those with niche tastes), due to its efforts to maintain fairness.\n- We leave formally quantifying such long-term effects as an exciting future direction and believe that our work lays a good foundation for such a study. We’ll discuss this in our conclusion section. \n\n**W5. Regarding alternative metrics,** \n- In our framework, we have considered various evaluation metrics:\n    - For items/users: Our framework accommodates different outcome metrics. E.g., items can consider visibility, marketshare, or revenue as their outcomes. In our case study, we verified that our fairness constraints are consistently met, regardless of the chosen metric (see Sec. F.2).\n    - For the platform, we not only evaluated the convergence of revenue regret (Fig 1a) and its revenue gain (Fig. 1b) but also examined its price of fairness under different fairness parameters (see Fig. 2).\n- We appreciate the reviewer’s suggestion and acknowledge that our evaluation can be further strengthened by incorporating additional metrics beyond the main objectives of our stakeholders, such as user satisfaction, user retention, and diversity of recommendations. These metrics can provide a more holistic view of our framework’s short/long-run impact on the system and are often best obtained through online experiments with real traffic. We’ll mention this in our future directions section.\n\n**Q1. Regarding changing user types/preference,**\n- As mentioned in our response on long-term fairness, our method attempts to calibrate the recommendation policy within the short period when user preferences are considered fixed. Over the long term, as user and item attributes evolve, adaptive fairness notions might need to be developed, which is something we mentioned in our future directions section (Sec. 5). We believe that our framework for multi-sided fairness under fixed user preference serves as a good starting point for such future studies. \n- One possible extension of our framework/method to accommodate changing user types/preferences can be inspired by existing adaptive partitioning methods (e.g.,the zooming method in “Contextual Bandits with Similarity Information”). This approach would involve using a meta-algorithm like the zooming method to update user types periodically at a slower pace, while our algorithm FORM can be applied as an inner algorithm that performs fair recommendation under the current user types/preferences. Exploring such ideas could be another interesting future direction.\n\n**Q2. Regarding applicability of fairness notions,**\n- Our proposed framework is meant to encapsulate a wide range of recommender systems, including e-commerce sites, social media, video streaming sites, etc. As remarked in Sec 2.4, we can even accommodate platforms with additional stakeholder groups (e.g., Doordash drivers, Airbnb hosts) by similarly incorporating additional fairness constraints. The generality of our framework allows these platforms to choose any fairness notions/outcomes that best suit their short-term and long-term goals (see Table 1 for example fairness notions; see Sec 2.3 for example outcome functions).\n- Determining the right fairness notion largely depends on the type of online platform and the desired outcomes for its stakeholders. See our response to reviewer pMvw for a more detailed discussion.\n\n**Q3. Regarding universality of our approach,**\n- Here, we worked with the clothing category of the Amazon review data because it was also used for evaluation in TFROM [63], which was one of the baselines we compared with. In addition to Amazon review data, we also performed experiments with the MovieLens data in a movie recommendation setting and obtained similar results. These results were previously omitted due to space constraints but are now included in our global response to demonstrate the broad applicability of our method. Please see the attached PDF in our global response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TnyEQzGK4Q", "reviewer": "Reviewer_zhjK", "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.", "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": "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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivation of this paper is clear, and it is well-written. The theoretical proof appears solid.\n2. Prior works on fairness-aware recommendation generally focus on either a single side or an offline setting. This work combines both aspects and proposes a novel framework and algorithm, which is useful in real-world settings.\n3. The authors compared their method with some well-studied offline and online fairness-aware recommendation methods, demonstrating that their proposed algorithm achieves a better tradeoff between fairness and revenue.", "weaknesses": "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.\n2. An efficiency comparison on the algorithm running time is missing.\n\nRef:\n\n[1] Naghiaei et al. CPFair: Personalized Consumer and Producer Fairness Re-ranking for Recommender Systems, SIGIR, 2022.\n\n[2] Wu et al. Joint Multisided Exposure Fairness for Recommendation. SIGIR, 2022.\n\n[3] Wu et al. A multi-objective optimization framework for multi-stakeholder fairness-aware recommendation. ACM Transactions on Information Systems, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback! We'd like to address your questions below.\n\n**Regarding related works,** thank you for pointing us to these works! We'll add them and the following discussion to our related works section.\n- **A short summary of [1,2,3]**. [1] focuses on achieving producer and customer fairness in re-ranking decisions, where fairness is promoted w.r.t. item exposure and user nDCG. In contrast, our framework is not confined to a single outcome or fairness notion. [2] proposed and compared a family of joint multi-sided fairness metrics that tackle systematic biases in content exposure, while our main focus is on proposing a new fairness framework/algorithm; [3] proposed a multi-objective optimization framework which jointly optimized accuracy and fairness for consumers and producers. We proposed a different framework that optimizes the platform's revenue while incorporating fairness constraints for items/users.\n- **Key differences.** As acknowledged by the reviewer, our setting differs from [1,2,3] in several ways: (i) Our work proposes a constrained optimization framework that not only imposes fairness for multi-stakeholders (items/users), but also takes the platform’s revenue into consideration; (ii) Our framework is not confined to a single fairness/outcome notion; (iii) Most importantly, unlike works that solely focused on multi-sided fairness, we recognize the challenge of jointly handling fairness and learning (Sec. 3.2), and propose an algorithm with theoretical guarantees (Sec. 3.4). The tradeoff between learning and fair recommendation, to the best of our knowledge, has not been studied in prior works. \n\n**Regarding efficiency comparison on algorithm runtime,**\n- Please see (1) in our global response for a complete discussion on our algorithm’s complexity & scalability considerations. \n- Overall, the complexity for our algorithm will be $O((MN)^{2+1/18})$ at each round when we solve (FAIR-RELAX) and $O(N)$ at each round when we simply recommend and update user preference. As stated in our global response, Problem (FAIR-RELAX) need only be solved for $O(\\log(T))$ rounds to maintain the same theoretical guarantee. In this way, our runtime will be greatly improved.\n-  In comparison to the two most relevant baselines—the per-round runtime of FairRec is $O(MN)$; the per-round runtime of TFROM is $O(NM^2log(M))$ in the offline setting and $O(N)$ in the online setting. While our runtime can be higher than these baselines during the rounds when (FAIR-RELAX) is solved, this is justified by the additional capabilities of our algorithm. Unlike the baselines, our method (i) maintains the platform’s revenue in addition to achieving item/user-fairness, and (ii) balances the processes of learning and making fair decisions, attaining strong theoretical guarantees. These enhancements lead to better performance (as validated by our case study in Sec. 4), all while maintaining a polynomial runtime under common fairness notions/outcomes.\n\n**Regarding users having multiple sensitive attributes,**\n- We’d like to first clarify that in our context, we expect user types to be primarily determined by user preferences rather than sensitive attributes such as gender, ethnicity, etc. Unlike scenarios like loan applications, where fairness involves ensuring equal opportunities across demographic groups, user-fairness in our personalized recommendation context focuses on ensuring users see items they prefer the most, rather than purely revenue-maximizing items (see our definition of user-fairness in Sec. 2.2).\n\n- With this in mind, when it comes to determining user types, we can cluster users based on their preferences, rather than directly grouping them based on genders or ethnicity. In real-world recommendation systems, platforms often have access to insensitive features such as the type of devices (Mac versus PC), zip code, as well as users’ past purchase history that can be used for clustering and determining user types. (See our response to reviewer kac1 for a complete discussion on how user type can be determined.) This is also how we determined user types in our case study (see Sec. 4). In this way, we can also incorporate multiple facets by clustering users based on comprehensive preference profiles rather than specific combinations of sensitive attributes. \n\n**Regarding the cold start problem,**\n- This can be readily addressed by design of our algorithm. As detailed in Sec. 3.1, FORM does not require any initial knowledge of user preferences or arrival rates. Instead, it employs an exploration mechanism to gather sufficient user data (see Sec. 3.3 for details on our “randomized exploration”). In practice, when new items or users join the platform mid-way through the time horizon, we can similarly enforce an initial exploration for them by having the algorithm recommend the new item with an additional small probability $\\epsilon$. The amount of exploration can then diminish as we accumulate more data for these new items or users. \n\n**Regarding leakage of user/item information,**\n- Thank you for raising this important issue! As discussed previously, our user types are primarily determined by user preferences rather than sensitive attributes. To alleviate concerns on sensitive information, user clustering can be performed based on insensitive features such as types of devices, zip codes, past purchase histories, etc. As for items, we can categorize them based on publicly available attributes such as keywords, types, prices without the use of sensitive attributes, and enforce fairness w.r.t. items within the same category (see (1) of our global response for a discussion of applying our framework to the last stage of recommendation pipeline). If there is concern about using specific attributes or features, our algorithm can also be configured to exclude such information during the user clustering process. We'll make sure to include a discussion on this issue in the conclusion section.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vr7EtW7VQ0", "reviewer": "Reviewer_pMvw", "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.", "questions": "How can we reasonably choose the right fairness notion and the values of $\\delta$ in practice?\n\n\nDo the authors have any plan to deploy and evaluate the proposed algorithms in some real production environment?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper tackles the practically relevant and challenging problem of balancing platform revenue, user fairness, and item fairness\n\n\nThe paper proposes an online algorithm to learn parameters of the problem while ensuring some given fairness constraints, not merely assuming that the parameters are given as done in most existing papers\n\n\nThe paper provides sound and thorough regret analysis of the proposed algorithm \n\n\nThe empirical results on real-world data shows that the proposed method effectively and flexibly control user-item fairness while maximizing the platform revenue", "weaknesses": "This is not a weakness specific to this paper, but choosing the right fairness notion and the values of $\\delta$ is non-trivial\n\n\nEven 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback! We'd like to address your questions below.\n\n**Regarding choosing the right fairness notion,**\n- Thank you for raising this insightful point! Indeed, choosing the right fairness notion is not trivial and very much depends on the context, such as the type of online platform and the stakeholder outcomes that matter. Here are some of the most important considerations:\n\n    - **Understanding stakeholders’ needs/outcomes.** One of the most crucial steps here is understanding the desired outcomes for items and users. Our framework, Problem (FAIR), is designed to handle various outcome functions, such as revenue, marketshare, and 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.\n\n    - **Assessing how each fairness notion aligns with the stakeholders' needs and the platform’s objective.**  Each fairness notion has a different implication, and platforms need to evaluate which best suits their goals and stakeholder needs. \n\n        For example, consider the following fairness notions from our Table 1:\n        - Maxmin fairness maximizes the outcome received by the most disadvantaged stakeholder. This can be ideal for video streaming platforms like Netflix or YouTube that wish to ensure independent and lesser-known content creators receive fair visibility alongside popular creators.\n        - 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.\n\n        Platforms may also need to experiment to understand how different fairness notions impact their \"price of fairness\" (i.e., platform's revenue loss in enforcing fairness) before determining the right fairness notion. For instance, in our Amazon review case study, maxmin fairness appears to have a slightly higher price of fairness compared to K-S fairness (see Fig. 1b in Sec. 4 and Fig. 3b in Sec. F.2).\n\n    - **Regulatory considerations.** As we discussed in Sec. 1, one important motivation for imposing fairness in online recommendation decisions is the increasing regulatory action, such as the Digital Markets Act proposed by EU. Therefore, the choice of fairness notions can also depend on legislative or regulatory requirements. For example, since the Digital Markets Act calls for a fair and open digital marketplace, maxmin fairness can be a suitable option as it ensures even the most disadvantaged item/content creator receive a fair level of exposure. \n\n- Our fairness framework is designed for a wide range of fairness notions and outcome functions, allowing it to be tailored to each platform's specific needs. We appreciate the reviewer’s question and will include the above discussion in the camera-ready version of our paper.\n\n**Regarding how to choose the right fairness parameter $\\delta_I, \\delta_U$,**\n- Please see (2) in our global response for all reviewers.\n\n**Regarding online A/B test and deployment,**\n- Thank you for your question! For now, the paper has a modeling and methodological focus. We believe that the offline experiments in our case study provide a strong initial validation for the efficacy of our approaches. The Amazon review dataset was also used for evaluation in prior works on multi-sided fairness (e.g. TFROM [63]). \n- In our paper, we have also discussed how a platform can use its “price of fairness” along with online A/B testing to select the right fairness parameters, which can potentially inform the design of real-world A/B tests (see Sec C.1). Please also see (2) in our global response for all reviewers for a complete discussion on this topic. \n\n  At a high level, we propose that (i) a platform can leverage the concept of the \"price of fairness” to identify a small range of fairness parameters to experiment with, ensuring that their fairness considerations do not negatively impact its key business objectives like revenue and marketshare. (ii) Upon determining a small subset of parameters for experimentation based on the desired fairness levels and acceptable price of fairness, a platform can then conduct A/B testing on segmented traffic to determine the best fairness parameters.\n\n- To facilitate potential real-world testing and deployments, we have presented this work to several online platforms and industry leaders and received positive feedback. While it is not known to us how these platforms intend to use our methodologies in their respective setups, we are open to collaborations with industry partners who have the necessary infrastructure to facilitate online A/B testing and deployments. We will mention this as an exciting future direction in our conclusion section.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We’d like to express our sincere gratitude to all reviewers for your insightful feedback! Below we’ve addressed several common questions from the reviewers. We’ll incorporate all discussions in our response into the revised version of the paper.

(1) **Regarding computational complexity and scalability,** 
- **Complexity analysis.** For most commonly used item-fairness notions (e.g., maxmin fairness, K-S fairness, demographic parity; see Table 1) and item outcome functions (visibility, marketshare, revenue; see Sec 2.2), solving Problem (FAIR-RELAX) involves solving two linear programs with MxN variables, leading to a polynomial runtime of $\tilde{O}((MN)^{2+1/18})$. Consequently, each iteration of FORM has a worst-case complexity of $\tilde{O}((MN)^{2+1/18})$. However, practical implementations often achieve much better performance than this worst-case scenario using fast LP solvers (e.g., we use the CBC solver in PuLP for our case study).
- **Real-world scalability considerations.** Our algorithm can be further adapted with scalability in consideration.
    - **No need to solve Problem (FAIR-RELAXED) at every round.** In real-world deployment, there is no need to solve the constrained optimization problem at every user arrival. Theoretically, solving the LP in $\log(T)$ rounds can already establish the same theoretical guarantee, as shown in other works (e.g., “Optimal learning for structured bandits”). Practically, platforms can resolve the problem after every X user arrivals or at X-minute intervals, while updating user data in real-time, which can remove the computational overhead. In our MovieLens experiments (see attached PDF), we also only solved (FAIR-RELAXED) at every 1k user arrivals, and the algorithm remains effective.
    - **Applying our framework to the last stage of recommendation.** To apply our framework in real-world recommendation systems, it's not always necessary to solve a large-scale optimization problem. The recommendation process typically proceeds in stages, initially using a lightweight model to narrow down items based on keywords and filtering criteria. This allows us to focus on smaller subsets within the same category, defined by keywords, types, prices, etc., (e.g., "a silicone cake pan in the price range 10-20 usd") and maintain fairness among these smaller subsets, thus reducing the computational burden. Our fairness framework is also particularly impactful at this final stage, where items with similar qualities or features now compete for visibility/revenue, and a purely revenue-maximizing solution would thus be extremely unfair.

(2) **Regarding how to determine fairness parameters $\delta_I$ and $\delta_U$,**

There are two main factors in determining the right fairness parameters: (i) the extent of fairness needed for items/users, and (ii) the "price of fairness" the platform is willing to pay.
- **$\delta_I, \delta_U$ are interpretable, tunabled handles.** As discussed in Sec. 2.4, in our framework, $\delta_I, \delta_U$ are tunable handles that determine how much share of the fair outcome a platform would like to ensure for items/users respectively. For instance, an e-commerce platform that values high user retention might choose to impose higher user fairness to ensure user satisfaction.
- **“Price of fairness” measures the tradeoff between a platform’s revenue and fairness.** As highlighted in Remark 2.2 and discussed in detail in Sec. C, a platform’s “price of fairness” (PoF) measures a platform’s revenue loss in maintaining fairness for its stakeholders. Understanding its PoF under different parameters $(\delta_I, \delta_U)$ is crucial as a platform needs to also understand the cost of implementing fairness constraints. We show in Theorem C.1 that the upper bound of the PoF grows roughly linearly with (i) the amount of misalignment in the platform’s and its stakeholders’ objectives, (ii) the fairness parameters $\delta_I, \delta_U$.  

Having these in mind, in Sec C.1 we’ve also illustrated how to determine the right fairness parameters using our case study on Amazon review data. 
- **Insights from the case study.** In Fig. 2, we explored the PoF under various $\delta_I, \delta_U$ on Amazon review data. We found that $\delta_U$ has little impact on PoF as the user-fair constraints are not binding, while $\delta_I$ impacts the PoF in a roughly piecewise linear manner. This suggests that under Amazon review data, the platform can achieve high user-fairness at little cost, while it can gauge the amount of tradeoff between its revenue and item fairness (the slope between PoF and $\delta_I$) by adjusting $\delta_I$ incrementally and performing experimentation. 
- **Guidelines to set $\delta_I, \delta_U$.** Similar methods can be applied to different online platforms in their respective contexts. A platform should first identify the binding constraints by determining which stakeholders experience the most unfairness under the current recommendation policy. Then, using the piecewise linear relationship, it can gauge the amount of tradeoff between binding fairness constraint and its PoF. Based on the desired fairness levels and acceptable PoF, the platform can 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 (e.g., 10-20%) to experiment with these parameters in parallel. This allows the platform to pick the most effective fairness parameters without extensive experimentation on all possible sets of parameters.

(3) **Additional Experiments on MovieLens Data.** In response to reviewer kac1’s question, in the attached PDF we’ve included experiments on the MovieLens data to validate the efficacy of our framework in an alternative setting (movie recommendation). The results are consistent with our Amazon case study, showing our method's effectiveness in balancing platform revenue and stakeholder fairness.

Meta-review: 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.
Decision: Accept (poster)