Online Combinatorial Optimization with Group Fairness Constraints

1 Introduction

Online combinatorial optimization problems, such as optimizing product rankings, assortment planning, or supplydemand matching for a sequence of arriving input instances, are prevalent in digital marketplaces. From a pure utilitarian perspective, an economically justified goal in several of these applications is to make combinatorial decisions across time steps that maximize the expected value of a global objective function representing the market share, i.e., the total/average user engagement for the entire population. However, these marketplaces typically have users with heterogeneous preferences based on demographics such as race, gender, and age [Hitsch et al., 2010]. Given these demographic groups, a more egalitarian decision maker might want to maximize the expected average market share while ensuring each group's share of this quantity is "large enough" based on some predetermined threshold, thus fostering inclusivity and fairness for all minority groups. This practice is not only ethically important but also beneficial for business, as it attracts new customers, retains existing ones, and contributes to a healthy ecosystem by fostering a positive reputation.

The full version of our paper, including all proofs, can be accessed at https://ssrn.com/abstract=4824251

While personalization is effective in achieving the above goal like, say, by displaying a unique assortment of products to each demographic group, the use of sensitive information for personalization can be restricted due to legal issues and privacy concerns that digital marketplaces face, which in turn affects the effectiveness and scope of personalized experiences [California Legislative Service, 2020]. Also, in some contexts, treating seemingly similar individuals differently can potentially be against the equal-protection doctrine and perceived as unlawful. This has motivated a concerted effort to introduce the notion of demographic group fairness guarantees into optimization problems by various mathematical semantics. For example, there is a growing literature on formulating the problem as a group distributional robust optimization (DRO) [Ben-Tal et al., 2013; Duchi et al., 2021; Sagawa et al., 2019; Soma et al., 2022], or incorporating parity among demographic groups by adding group fairness constraints [Kleinberg et al., 2018; Chouldechova and Roth, 2018; Chen et al., 2022; Rahmattalabi et al., 2019].

However, most existing approaches are limited to continuous and offline decision-making settings where the decisionmaker can efficiently solve the (unfair) offline optimization problem. Hence, these approaches do not provide general solutions for online combinatorial optimization problems with discrete and exponential size decision spaces at each time step, where the decision-maker should learn and compute through explorations/exploitation. To complicate things further, the offline version of many of these combinatorial optimization problems, e.g., assortment planning under a large class of consumer choice models or maximizing market-share through sub-modular function maximization, are NP-Hard [Goyal et al., 2016; Nemhauser et al., 1978; Asadpour et al., 2022; Niazadeh et al., 2021] and thus any robust/fair approach must employ existing approximation algorithms for these problems. We bridge this gap in this paper by providing a general learning and computing framework for online combinatorial optimization with group fairness constraints, where our algorithms can employ (an online learning variant of) algorithms for the unfair version of the problem in a black-box oracle fashion. We now describe our problem.

1.1 ProblemFormulation and Examples

Let F be a conic-closed 1 function class defined over (an exponentially large) domain D of actions. At every time step t ∈ [T], there are L functions {f i t ∈ F}i∈[L] such that f i t : D → [0, fmax] for all i ∈ [L], where L is the number of demographic groups and f i t is the reward function of group i at time t. Furthermore, let {τ i }i∈[L] be a set of non-negative fairness thresholds in [0, fmax], and C ⊆ D be a constrained domain space. A learner, denoted by ALG, is aware of these fairness thresholds, and at time step t ∈ [T], ALG picks an action xt ∈ C. Then,

1. either the L functions {f i t ∈ F}i∈[L] (in the fullinformation setting);
2. or just the rewards {f i t (xt) ∈ F}i∈[L] (in the banditinformation setting),

are revealed to the learner ALG, and it receives a reward ∑i∈[L] f i t (xt). The action xt is chosen based on the knowledge of all the functions up to time t-1. In contrast, the functions {f i t }t∈[L] can depend on the knowledge of the previous functions {f ik }i∈[L],k∈[t-1] and actions {xk}k∈[t-1], s.t. 2 ,

where we define a sequence of filtrations for t ∈ [T + 1] as,

In general ALG might select a distribution of actions P ∈ ∆(C), where ∆(C) is the set of all distributions over C. Then, the online maximization benchmark with group fairness constraints, ONLINE-OPT, which we compete against, is,

Note that the online optimization problem (1) 3 considers ex-ante fairness constraints because we only require the expected value Ex∼P [f i (x)] to be greater than τ i . When τi = 0 for all i ∈ [L], we are only concerned about maximizing the total market share without any fairness considerations,

2 This stochastic adversarial/martingale setup is common in reinforcement learning [Ribeiro, 2002; Besbes et al., 2014; JafarniaJahromi et al., 2021]. The i.i.d. setting where for all i ∈ [L] the function f i t for group i is picked independently and identically from distribution Di ∈ ∆(F) which is fixed in advance, is a special case.

3 As is usual in optimization literature, we will refer to the optimization problem and its optimal value interchangeably.

On the other hand, is the following "robust" problem,

which is known as the group-DRO problem and has been studied extensively [Ben-Tal et al., 2013; Duchi et al., 2021; Sagawa et al., 2019] in machine learning literature. Suppose we have access to the value τ ⋆ of the robust problem (3). In that case, we can recover group-DRO by solving problem (1) with fairness constraints τi = τ ⋆ for all i ∈ [L]. More generally, problem (1) interpolates between the utilitarian objective when τi = 0 for all i ∈ [L] as we are only concerned about maximizing the total market share and the egalitarian objective when τi = τ ⋆ for all i ∈ [L], where we are maximizing the market share of the worst group. Notably, there are many ways to interpolate between these objectives. With a symmetric threshold τ i = τ that varies in the interval [0, τ ⋆ ], this approach recovers the Pareto frontier of fairness-efficiency, which is a canonical object of study at the intersection of fairness and decision making, for e.g., see [Bertsimas et al., 2011; Bertsimas et al., 2012]. Using constraints to trace the utilityfairness curve is related to scalarization and ϵ-constraint approaches [Miettinen, 1999] in vector optimization.

Remark 1 (Offline Problem). A very special case of our problem is the following offline problem (see the full version of our paper for more discussion):

Compared to the online problem (1), the functions {f i }i∈[L] are known in advance for the offline problem. We will refer to the optimal value of problem (4) by OFFLINE-OPT.

Running Examples. We will consider two running examples to illustrate the generality of our framework.

Example 1 (Online Shortest Path Problem). Consider routing traffic through a city in real-time using a navigation service. Different neighborhoods (some of which might be marginalized) would be affected differently [Park and Kwan, 2020] due to factors such as exposure to air pollution, traffic congestion, road accidents, economic opportunities, etc. This problem can be reduced to an "online shortest path" problem-one of the core combinatorial prediction problems in online learning. Consider a graph G = (V, E), with vertices V connected by a set of directed edges E ⊆ V 2 . Let u ∈ V and v ∈ V be the source and sink vertex, respectively. Let C be the set of all cycle-free paths from u to v, where each edge only appears once. Note that C is potentially exponential in |E|. At time t ∈ [T], for i ∈ [L], f i t : E → [0, 1], and f i t (e) measures the reward for picking an edge e ∈ E for group i. Then, for a given path xt ∈ C, the total reward for group i is measured as f i t (xt) = ∑e∈xt f i t (e) which is a noisy measurement of the mean reward f i (xt). This repeats each day, and at the end of the day t the reward functions are revealed for all the edges, {f i t (e) : e ∈ E, i ∈ [L]}.

Example 2 (Online Sub-modular Maximization). The notion of sub-modularity is commonly used to describe the diminishing return property in discrete and continuous domains. Many optimization problems that arise in the real world such as viral marketing in a social network [Kempe et al., 2003], ranking an assortment of products [Asadpour et al., 2022], welfare maximization [Dobzinski and Schapira, 2006] and speeding up satisfiability solvers [Streeter and Golovin, 2008] can be expressed as maximizing a submodular function under constraints. In our setting, assume that f i t : C → [0, 1] is a set function defined on some constrained set of sets C ⊆ 2[n] , such that, for all S, T ∈ [n], f i t (S ∪ T) + f i t (S ∩ T) ≤ f i t (S) + f i t (T ), i.e., f i t is sub-modular. A common set constraint is the cardinality constraint which only allows sets of size at most k ≤ n. It is well-known that sub-modular function maximization (SMM) with cardinality constraints is an NP-hard problem that admits the classic (1- 1e )-approximation greedy algorithm [Nemhauser et al., 1978]. Many applications of SMM have fairness considerations in the presence of multiple groups. For instance, recommendations on a digital marketplace should not be unreasonably worse for any gender.

Our proposed framework in this paper can accommodate NP-hard problems such as sub-modular function maximization. Naturally, we can only hope to attain the value ONLINEOPT of problem (1) up to a multiplicative factor γ ∈ (0, 1). We will choose γ as the best approximation factor for the offline version of the problem of maximizing the individual function for each group. Thus it will arise from the inherent hardness of the problem. For instance, for SMM with cardinality constraints, we will pick γ = (1- 1e ). Furthermore, since the optimization problem (1) is equivalent to solving a series of feasibility problems, we can only satisfy the fairness constraints up to this multiplicative factor γ. In particular, in section 3, we propose Algorithm 1 to minimize the following approximate regret metric often used in the literature [Niazadeh et al., 2021; Kakade et al., 2007; Dudik et al., 2020],

while also γ-approximately satisfying the fairness constraints for all i ∈ [L],

We will refer to the regret in (5) as γ-average regret.

1.2 Our Contributions

The contributions of our paper are as follows,

• We provide a general framework to incorporate group fairness constraints to any online combinatorial optimization problem that we know how to solve with a single group. Our approach is easy to implement and accommodates both full and bandit information feedback.
• We provide theoretical guarantees for both the regret and fairness of our approach (see algorithm 1) with blackbox access to an online optimization oracle (see definition 1) for the combinatorial problem with a single group. In particular, we show vanishing γ-average regret while being approximately fair (violating the fairness constraint by, at most, some small error δ > 0) for large T . Thus, we extend prior work on primal-dual algorithms for online optimization [Shalev-Shwartz and Singer, 2007] to our setting with group fairness.
• We present an empirical evaluation of our algorithm using parameters derived from the widely used MovieLens ratings dataset [Harper and Konstan, 2015]. Our results demonstrate that our online algorithm achieves sub-linear regret when comparing it to the approximate optimal benchmark. Additionally, we investigate the effects of fairness constraints on the total expected market share, providing insights into the trade-offs between group fairness and assortment optimization.

2 RelatedWork

Recently, machine learning algorithms have increasingly entered various fields, sparking a growing interest in algorithmic fairness in optimization, including combinatorial optimization. Researchers have studied a wide range of problems such as matching [Chierichetti et al., 2019], bandit optimization [Liu et al., 2022; Joseph et al., 2016], resource allocation [Bertsimas et al., 2012; Manshadi et al., 2021], assortment planning [Singh and Joachims, 2018; Biega et al., 2018; Chen et al., 2022], and reserve pricing in search ad markets [Deng et al., 2022]. Algorithmic fairness generally falls into three categories: 1) individual fairness, where algorithms make comparable predictions for similar individuals [Dwork et al., 2012; Loi et al., 2019; Chen et al., 2022], 2) group fairness, which ensures equal treatment of distinct groups, often in resource use or performance in combinatorial optimization [Singh and Joachims, 2018; Balseiro et al., 2021], and 3) subgroup fairness, which combines elements of both [Kearns et al., 2018; Kearns et al., 2019].

For fairness in assortment planning, previous research mainly targets individual fairness for sellers on online platforms. [Chen et al., 2022] use pairwise fairness to ensure that items of similar quality get similar visibility. They solve their constrained assortment optimization problem by framing it as a linear program and using the Ellipsoid method to find a nearly optimal solution. Fairness in ranking represents another related field. Essentially, assortment planning acts as a specialized case of ranking: items in the top K positions get full visibility, while the rest remain invisible. [Garcia-Soriano and Bonchi, 2021] work on minimizing individual unfairness and imposing group fairness constraints in offline ranking. They propose a polynomial-time algorithm to solve the problem. [Celis et al., 2018] focus on group fairness across demographics, formulate their problem as a linear program, prove its computational hardness, and introduce an LP-based approximation algorithm with theoretical guarantees. However, they do not explore online scenarios.

Our paper differs from previous literature in several ways.

We focus on group fairness in general combinatorial optimization problems, unlike most previous works that center on individual fairness for specific problems. We also tackle optimization problems that might be unsolvable as a whole, such as NP-hard problems, and that do not have objectives that are linear in actions. This approach enables us to address various problems relevant to online platforms, from sub-modular function maximization to assortment planning. Our offline results most closely relate to concurrent work by [Tang and Yuan, 2023], who employ the Ellipsoid method to solve offline combinatorial optimization problems with fairness constraints. However, our work has two main advantages. First, we use a simple primal-dual framework that is easy to implement, unlike the numerically unstable and more complex Ellipsoid method. Second, we can extend our framework easily to online settings that are more pertinent to online markets where decision-making usually occurs sequentially.

3 Our Algorithm and Theoretical Guarantees

In this section, we present our algorithm 1 and provide its theoretical guarantees. Recall that we focus on functions that are difficult to optimize, where even the individual problems maxx∈C f i t (x) for each i ∈ [L], t ∈ [T ] are NP-hard. To solve the online variants of such problems with group fairness constraints, we need access to the online algorithm used to solve the problem with a single group. In particular, we assume the existence of the following no-regret online oracle Z.

Definition 1 (γ-no-regret Online Oracle). A γ-no-regret online oracle, denoted as Z, is an algorithm that produces a sequence of probability distributions {Pt ∈ ∆(C)}t∈[T] such that the following γ-average regret is diminishing over time,

In the full-information setting, at time t, the oracle knows its past actions x1, . . . , xt-1 and the past functions f1, . . . , ft-1 ∈ F, while in the bandit setting, it is only aware of its past actions and the past function values f1(x1), . . . , ft-1(xt-1).

We can obtain a γ-no-regret online oracle for several combinatorial problems, including our two running examples.

Remark 2 (Oracle for Online Shortest Path Problem). Online shortest path problem can be solved exactly, with γ = 1 to get an O (1/√T ) averaged regret. One standard approach (see [Dekel, 2012] for details) first obtains a convex relaxation of the problem at each time-step to select an action yt from the convex hull of all the paths in C. This reduces the problem into an online linear optimization problem with full-information feedback, which can be optimized with an algorithm such as projected online gradient descent to get O(√T) regret. This is followed by a randomization procedure that samples a path xt at each time step using yt.

Remark 3 (Oracle for Online Sub-modular Maximization). There are several online approximation oracles known for different variants of SMM. [Niazadeh et al., 2021] provide

Algorithm 1 Robust Online Algorithm

Input: A γ-no-regret online approximation oracle Z with action space ∆(C) (such as Blackwell algorithms in [Niazadeh et al., 2021]), a no-regret online linear optimization algorithm A with action space [0, L/δ]L (such as projected online gradient descent with optimal step sizes), the fairness violation threshold δ, and the total period T .

Output: An (random) action for each period.

• 1: Initialize α1 ← (L/δ,L/δ, . . . ,L/δ).
• 2: for t = 1, . . . , T do
• 3: Max player calls the oracle Z to get Pt ∈ ∆(C).
• 4: Max player plays xt ∼ Pt.
• 5: Max player receives one of the following feedbacks:
• 6: The min player gets a loss vector

Full-information: functions {f i t }i∈[L] .

Bandit: function values {f i t (xt)}i∈[L] .

.

• 7: The min player updates αt+1 ←A(αt, {ℓk}1≤k≤t).
• 8: The oracle Z receives one of the following feedbacks:

Full-information: function

Bandit: function value

9: end for

one instance of such an algorithm that achieves O(1/√T) γ-average regret in the full-information and O(1/T 1/3 ) γaverage regret in the bandit-information setting for various classes of sub-modular functions, including monotone submodular functions with cardinality constraints (γ = 1-1/e) and non-monotone discrete sub-modular functions (γ = 1/2). Other works have also presented no-regret oracles for specific sub-modular problems. [Streeter and Golovin, 2008] proposed an oracle that achieves O(1/√T ) (1-1/e)- average regret for monotone sub-modular functions with cardinality constraints, based on the randomized weighted majority algorithm, [Chen et al., 2018] introduced a FrankWolfe based online oracle that achieves O(1/√T ) (1-1/e)- average regret for monotone continuous sub-modular maximization in the downward closed convex set, and [Roughgarden and Wang, 2018] presented a potential function based oracle for non-monotone set sub-modular maximization. For a survey, see the paper by [Niazadeh et al., 2021].

We will also need an online linear optimization oracle.

Definition 2 (No-regret OLO Oracle). Let X,L ⊂ Rd be two compact spaces. Assume at each time step j ∈ [N] we see an arbitrary loss function lj ∈ L ⊂ Rd , and an algorithm A : (X × L)⋆ → X outputs an action xj ∈ X based on the history at time j. Then A is a no-regret online linear optimization (OLO) if it has a zero average regret RA(N) in the limit N → ∞, where

Remark 4. A few examples of no-regret online linear optimization oracles are projected Online Gradient Descent (OGD) [Zinkevich, 2003], Follow the Regularized Leader (FTRL), and Follow the Perturbed Leader (FTPL) [Kalai and Vempala, 2005] algorithms. For a survey of these algorithms and their relative comparisons, see [Hazan, 2016].

Our complete online algorithm using the above two oracles is presented in Algorithm 1. Our algorithm is primaldual-based and simulates the problem as an online max-min game: the min player A runs a no-regret online minimization algorithm, and the max player Z runs an approximate online algorithm on a conic combination of the functions at any given time t ∈ [T ]. For the min player, who is ignorant of the combinatorial structure of the problem, there is no difference between full and bandit information feedback because it only requires the values of functions for each group at each round and each group's fairness threshold. Algorithm 1 satisfies the bounds in the following Theorem (c.f. full paper for proof).

Theorem 1. Suppose that the online maximization problem with ex-ante fairness constraints, defined by ({f i t }i∈[L],t∈[T], {τi}i∈[L]) as shown in Equation 1 is feasible. Let δ > 0 be some fairness violation threshold, and let γ be the approximation constant. Suppose that we have a γ-no-regret online approximation oracle Z with a γ-average regret of RZ (·) and an OLO algorithm A with an average regret of RA(·). Then, Algorithm 1 outputs a (random) sequence of actions {xt}t∈[T] that satisfies the following:

meaning that the sequence is γ-approximately fair, and the violation converges to δfmax as T →∞.

• The total reward function evaluated on the sequence is a γ-approximation to the optimal value in hindsight, γ · ONLINE-OPT, with the following regret

Here, the functions {f i t }i∈[L],t∈[T] ∈ F satisfy Ef i t [f i t (·)|Ht] = f i (·) where Ht = σ({f ik }i∈[L],k∈[t-1] , {xk}k∈[t-1]).

Proof sketch. We rely on the expected average Lagrangian dual quantity, defined as

to establish an upper bound on γ · ONLINE-OPT and a lower bound on the algorithm's total reward, ∑i∈[L],t∈[T ] Ext∼Pt ,f i t [f i t (xt)|Ht ]. Specifically, we first upper-bound the expected average Lagrangian dual quantity by taking the minimum overall expected average Lagrangian duals evaluated at {xt}t∈[T], where the minimum is taken over α ∈ [0,L/δ]L, along with using the definition of the no-regret OLO oracle A. This step gives the following bound,

Next, we establish a lower bound on the expected average dual by leveraging the γ-approximation of ONLINE-OPT by Z and the definition of the functions gt.

Combining the upper bound (9) and the lower bound (10), followed by some algebraic manipulations, directly gives the fairness bound. Additionally, using the realization that the first quantity on the right of (9), i.e., the minimum overall expected average Lagrangian duals evaluated on {xt}t∈[T] is upper bounded by the algorithm's average reward finishes the proof for the γ-averaged regret bound.

From the statement of Theorem 1, it might seem like δ can be set to 0 to avoid the slack in the fairness constraint completely. However, there is a hiding delta in RA(T) because the action space of the oracle A is restricted to [0,L/δ]L in Algorithm 1. For instance, if we pick A to be the projected online gradient descent algorithm, then with optimal step size, RA(T ) = O ( fmaxL2 δ√T ) (c.f., [Hazan, 2016] and the discussion in our full version). This implies that decreasing δ improves the slackness in the fairness constraint but worsens the upper bound for γ-averaged regret. Fixing A as projected online gradient descent with optimal step sizes (c.f., discussion in our full version), we recover the final guarantees for our two running examples.

Remark 5 (Online Shortest Paths). For our first running example using Z as the oracle described in remark 2, the above theorem implies an average regret guarantee of O(1/√T ) as both RA(T ) and RZ (T ) are O(1/√T ).

Remark 6 (Sub-modular Maximization). For our second running example by picking Z as the Blackwell approachability-based algorithm by [Niazadeh et al., 2021], we can get RZ (T) = O(1/√T), implying an overall γ averaged regret of O(1/√T) (γ factor depends on the additional structure in SMM) in the full-information setting. Similarly, in the bandit information setting the algorithm by [Niazadeh et al., 2021] implies RZ (T ) = O(1/T 1/3 ), implying an overall regret of O(1/T 1/3 ).

4 Experiments

In this section, we present a case study using the MovieLens 1M dataset due to [Harper and Konstan, 2015] to evaluate the effectiveness of our offline (c.f., our full version for more details) and online algorithms for movie recommendation. Specifically, we simulate a movie recommendation platform that aims to offer an assortment of movies tailored to users' diverse preferences. We partition the users into demographic groups based on gender and seek to maximize the overall market share while ensuring that the market share of each group meets a predetermined threshold to satisfy the group fairness constraint. Here, the market share of an assortment for a group represents the probability that a user in the respective group selects at least one movie from the assortment. Our experiments demonstrate that our online algorithm produces a sequence of sets with diminishing γ regret while meeting the fairness constraint. Furthermore, we examine the impact of various thresholds on the algorithm's performance.

Diminishing regret of the online algorithm. Figure 1 displays the cumulative regret of Algorithm 1 over time. To compute the regret of our algorithms, we use (1 - 1/e) of the optimal market share as the regret benchmark, where (1-1/e) is the γ factor for the offline greedy algorithm. The optimal market share is the highest possible among all assortments of size 5, assuming that we know all the parameters (weights and probability of each mixture) beforehand, which we obtain by enumerating all possible assortments. In the experiment, we consider three sets of thresholds for the average market share for each group: (0.5, 0.5), (0.6, 0.6), and

(0.7, 0.7), where all of these thresholds are feasible. We set the maximum allowed violation δ to be 0.01. For each threshold, we take the average performance over 50 runs. The results in Figure 1 show that the cumulative regrets are negative for all thresholds. The cumulative regret is also smaller (better) for a bigger feasible threshold. This may be because our online algorithm learns faster by updating the dual variables more aggressively when the threshold is bigger.

Demographic Groups. For the demographic groups, we first divide the users into two groups based on gender and further divide each group into three subgroups based on age (124, 25-44, 45+), which we use when constructing the market share function. To ensure diverse preferences for each group, we select the top 20 movies with the largest absolute difference in average ratings between the two groups, which also have been rated by at least 1000 users. We use a mixed multinomial logit (MMNL) as our choice model for each group, where the mixture comes from the different age groups. We set the probability of each mixture as the empirical probability of each age group within the specific gender in the user data. Moreover, we set the weight for each movie proportional to users' average rating of the corresponding movie in the particular subgroup (based on gender and age). We provide an example in the full version of our paper and highlight that our market share function is monotone submodular, and the class of monotone submodular functions is conic-closed.

In the offline setting, each group's mixture probability and market share parameters are known beforehand. However, the decision time (choosing the set) does not know these parameters in the online setting. To introduce stochasticity into the market share function in the online setting, we make the probability of the mixtures of each group stochastic. This is achieved by drawing the probabilities from a Dirichlet distribution, parameterized by the means obtained from the offline setting. Specifically, for group i at time t, the probability of each mixture is sampled from a Dirichlet distribution with mean (pi,1, pi,2, pi,3) obtained from the offline setting. Moreover, we set the number of periods to be T = 10, 000 and the allowed violation to be δ = 0.01 for both settings. The allowed violation controls the maximum violation allowed to satisfy the group fairness.

Implementation. For our offline algorithm, we use projected OGD as our online linear optimization method (c.f., discussion in our full version). We then use the greedy algorithm for maximizing monotone submodular functions with a cardinality constraint, as proposed by [Nemhauser et al., 1978], as the (1 - 1/e)-approximate oracle. Meanwhile, we also use projected OGD as our OLO for the online algorithm. Additionally, we apply the framework proposed by [Niazadeh et al., 2021] for the offline greedy algorithm. We use the Multiplicative Weight/Hedge algorithm to update the weights of each item for each position in the assortment with a learning rate of ϵt = √1/t. The Hedge algorithm is a no-regret adversarial learning algorithm that keeps weight over the different arms at each time step and updates those weights based on the observed feedback. In our problem, subproblem i corresponds to determining the item for the ith position in the assortment. (See [Niazadeh et al., 2021] for more details.)

The effect of fairness threshold. The results in Figure 2 provide insights into the effect of varying the fairness threshold on the performance of the offline and online algorithms. The presented values are the averages of 50 runs. In the offline setting, the total expected market share remains similar (almost constant) when the thresholds are feasible, as depicted in Figure 2a (green line). However, as the threshold approaches the boundaries of feasibility (in the range of [0.74, 0.76]), the performance decreases since the algorithm has to adjust the assortment to increase the market share of one group (female users in this case), while in turn decreasing the market share of the other group (male users), as seen in Figure 2c. Moreover, when the threshold becomes infeasible, the algorithm no longer tries to balance the two groups, resulting in a higher total expected market share. This is expected, as we do not have any fairness guarantees when the optimization problem is infeasible. Additionally, we limit the domain of the dual variable α, causing the algorithm to no longer balance the two groups.

In contrast, in the online setting, the total average market share increases as the threshold increases (averaged over T = 10, 000 rounds), as indicated by the blue line in Figure 2a. This may be because when the thresholds are higher, the online algorithm updates the dual variable faster, thus converging to the optimal solution more quickly. However, as the threshold approaches the boundaries of feasibility (in [0.74, 0.76]), the performance decreases and fluctuates. The algorithm adjusts the market shares of both groups to either satisfy or violate the fairness constraints by at most δ = 0.01.

Notably, in the boundary region, the average market share of females increases, while the market share of males decreases while still satisfying the constraint. When the threshold becomes infeasible, the algorithm maximizes the total average market share with no fairness guarantee.

5 Discussion

This paper provides a general framework for incorporating fairness constraints into online combinatorial problems, as our methods use approximation algorithms for the base problem and OLO algorithms as black boxes. Our framework is easy to state and implement, making it especially relevant for applications in online markets. There are two important future directions for our work. In the online setting, we consider a stochastic adversary, and the stronger adaptive adversary, which can provide arbitrary functions at each time step, is much more challenging and probably requires new techniques. Note that there is a slack variable in our fairness guarantees, appearing from technical requirements for online gradient descent. We believe this is avoidable in some settings (where a barrier function can be constructed) using an interior point method to solve our lagrangian max-min game.

Acknowledgements

R.N. was supported by the Asness junior faculty fellowship at Chicago Booth. F.S. and N.G. were supported by an award from the Office of Naval Research (ONR) (Award Number: N00014-23-1-2584). K.K.P. was supported through the NSF TRIPOD Institute on Data, Economics, Algorithms and Learning (IDEAL) and other awards from DARPA and NSF.

Contribution Statement

Author names appear alphabetically, and all authors contributed equally to this submission.