Trade the System Efficiency for the Income Equality of Drivers in Rideshare

1 Introduction

Rideshares such as Uber and Lyft have received significant attention among research communities of computer science, operations research, and business, to name a few. One main research topic is the matching policy design of pairing drivers and riders, see, e.g., [Danassis et al., 2019; Ashlagi et al., 2019; Bei and Zhang, 2018; Dickerson et al., 2018; Zhao et al., 2019]. Most of the current work focuses on either the promotion of system efficiency or that of users' satisfaction or both.

In this paper, we study the fairness among rideshare drivers. There are several reports showing the earning gap among drivers based on their demographic factors such as age, gender and race, see, e.g., [Cook et al., 2018; Rosenblat et al., 2016]. In particular, [Hinchliffe, 2017] has reported that "Black Uber and Lyft drivers earned $13.96 an hour compared to the $16.08 average for all other drivers" and "Women drivers reported earning an average of $14.26 per hour, compared to $16.61 for men". The wage gap among drivers from different demographic groups is partially due to the discriminative cancellations from riders, which can be well spotted especially during off-peak hours when the number of riders is comparable or even less than that of drivers. Note that in rideshares like Uber and Lyft, after a driver accepts a rider: (1) all sensitive information of the driver such as name and photo will be accessible to the rider and (2) riders can cancel the driver for the first two minutes free of charge [Dough, 2019]. This makes the discriminative cancellations from riders technically possible and economically worry-free.

We aim to address the income disparity among drivers due to discriminative cancellations from riders and its tradeoff with system efficiency. Note that the two goals, promoting the group-level income equality among drivers and the system efficiency, are somewhat conflicting. Consider the offpeak hours for example, when riders are kinds of scarce resources. To maximize the system efficiency, rideshares like Uber should please riders by assigning them to their "favorite" drivers. This can effectively reduce any possible cancellations from riders and thus, minimize the risk of driving away riders to other rivals like Lyft. This measure, however, will offer those drivers "popular" among riders much more chances of getting orders than others and as a result, hurt the group-level income equality greatly.

In this paper, we propose two parameterized matching policies, which can smoothly tradeoff the above two goals with provable performances. We adopt the online-matching based model to capture the dynamics in rideshare, as commonly used before [Dickerson et al., 2018; Zhao et al., 2019]. Assume a bipartite graph G = (U, V, E) where U and V represent the sets of types of offline drivers and online requests, respectively. Each driver type represents a specific demographic group (defined by gender, age, race, etc.) with a given location, while each request type represents a specific demographic group with a given starting and ending location. There is an edge f = (u, v) if the driver (of type) u is capable of serving the request (of type) v1 (e.g., the distance between them is below a given threshold). The online phase consists of T rounds and in each round, a request v ∈ V arrives dynamically. Upon its arrival an immediate and irrevocable decision is required: either reject v or assign it to a neighboring driver in U. We assume each u has a matching capacity of Bu ∈ Z+, which captures the number of drivers belonging to the type u. Additionally, we have the following key assumptions in the model.

1 For simplicity, we refer to a driver of type u and a request of

Arrivals of online requests. We consider a finite time horizon T (known to the algorithm). For each time-step or round t ∈ [T] .= {1, 2, . . . , T}, a request of type v will be sampled (or v arrives) from a known distribution {qv} such that ∑v∈V qv = 1. Note that the sampling process is independent and identical across the online T rounds. For each v, let rv = T · qv, which is called the arrival rate of request v with ∑v∈V rv = T. Our arrival assumption is commonly called the known identical independent distributions (KIID). This is mainly inspired from the fact that we can often learn the arrival distribution from historical logs [Yao et al., 2018; Li et al., 2018]. KIID is widely used in many practical applications of online matching markets including rideshare and crowdsourcing [Zhao et al., 2019; Dickerson et al., 2018; Singer and Mittal, 2013; Singla and Krause, 2013].

Edge existence probabilities. Each edge f = (u, v) is associated with an existence probability pf ∈ (0, 1], which captures the statistical acceptance rate of a request of type v toward a driver of type u. The random process goes as follows. Once we assign u to v, we observe an immediate random outcome of the existence, which is present (i.e., v accepts u) with probability pf and not (v cancels u) otherwise. We assume that (1) the randomness associated with the edge existence is independent across all edges; (2) the values {pf} are given as part of the input. The first assumption is motivated by individual choice and the second from the fact that historical logs can be used to compute such statistics with high precision.

Patience of requests. Each request v is associated with patience ∆v ∈ Z+, which captures an upper bound of unsuccessful assignments the request v can tolerate before leaving the platform. Under patience constraints, we can dispatch each request v to at most ∆v different drives. Observe that we cannot broadcast v to a set of at most ∆v different drives simultaneously. Instead, we should assign v to at most ∆v distinct drives (maybe of the same type though) in a sequential manner until either v accepts one or v leaves the system after running out of patience. We refer to this as the online probing process (OPP). Note that OPP starts immediately after a request v arrives if v not rejected by the algorithm, and ends within one single round before the next request arrives.

We say an assignment f = (u, v) is successful if u is assigned to v, and v accepts u which occurs with probability pf . Assume that the platform will gain a profit wf from a successful assignment f = (u, v) (we call a match then). For a given policy ALG, let Mbe the set of (possibly random) successful assignments; we interchangeably use the term matching to denote this set M. Inspired by the work of [Nanda et al., 2019; Lesmana et al., 2019], we define two objec-

type v directly as a driver u and request v when the context is clear.

tives, namely profit and fairness, which capture the system efficiency and group-level income equality among drivers, respectively.

Profit: The expected total profit over all matches obtained by the platform, which is defined as E[∑f∈M wf ].

Fairness: Let Mu be the set of edges in M incident to u. Define the fairness achieved by ALG over all driver types as minu∈U E[|Mu|] Bu .

1.1 Preliminaries andMain Contributions

Competitive ratio. The competitive ratio is a commonlyused metric to evaluate the performance of online algorithms. Consider an online maximization problem for example. Let ALG(I) = EI∼I [ALG(I)] denote the expected performance of ALG on an input I, where the expectation is taken over the random arrival sequence I. Let OPT(I) = E[OPT(I)] denote the expected offline optimal, where OPT(I) refers to the optimal value after we observe the full arrival sequence I. Then, competitive ratio is defined as minI ALG(I) OPT(I) . It is a common technique to use an LP to upper bound the OPT(I) (called the benchmark LP) and hence get a valid lower bound on the target competitive ratio. In our paper, we conduct online competitive ratio analysis on both objectives.

Main Contributions

Our contributions can be summarized in the following three aspects. First, we propose a new online-matching based model to address the income inequality among drivers from different demographic groups and its trade-off with the system efficiency in rideshare. Second, we present a robust theoretical analysis for our model. We first construct a bi-objective linear program (LP-(1) and LP-(2)), which is proved to offer valid upper bounds for the respective maximum profit and fairness in the offline optimal. Then, we propose LP-based parameterized online algorithms WarmUp and AttenAlg with provable performances on both objectives. We say an online algorithm achieves an (α, β)-competitive ratio if it achieves competitive ratios α and β on the profit and fairness against benchmarks LP-(1) and LP-(2), respectively. Results in Theorems 2 and 3 suggest that AttenAlg can achieve a nearly optimal ratio on each single objective either fairness or profit, though there is some space of improvement left for the summation of both ratios.

Theorem 1. WarmUp(α, β) achieves a competitive ratio at least (α · 1-1/e 2 , β · 1-1/e 2 ) simultaneously on the profit and fairness for any α, β > 0 with α + β ≤ 1.

Theorem 2. AttenAlg(α, β) achieves a competitive ratio at least (α · e-1 e+1 , β · e-1 e+1 ) ∼ (0.46 · α, 0.46 · β) simultaneously on the profit and fairness for any α, β > 0 with α + β ≤ 1.

Theorem 3. No algorithm can achieve an (α, β)-competitive ratio simultaneously on the profit and fairness with α + β > 1 or α > 0.51 or β > 0.51 using LP-(1) and LP-(2) as benchmarks.

Last, we test our model and algorithms on a real dataset collected from a large on-demand taxi dispatching platform.

Experimental results confirm our theoretical predictions and demonstrate the flexibility of our algorithms in tradeoffing the two conflicting objectives and their efficiency compared to natural heuristics.

2 RelatedWork

Here is a few recent work addressing the fairness issue in rideshares. [Sühr et al., 2019] proposed two notions of amortized fairness for fair distribution of income among drivers, one is related to absolute income equality, while the other is averaged income equality over active time. [Lesmana et al., 2019] considered nearly the same two objectives as proposed in this paper. Note that both of the aforementioned work considered an essential offline setting in the way that all arrivals of online requests are known in advance by considering a short time window. Additionally, both ignore the potential cancellations from riders, and assume each rider will accept the assigned driver surely (i.e., all pf = 1). [Nanda et al., 2019] studied an interesting "dual" setting to us. They focused on the peak hours and examined the fairness on the rider side due to discriminative cancellations from drivers.

Our model technically belongs to a more general optimization paradigm, called Multi-Objective Optimization. Here are a few theoretical work which studied the design of approximation or online algorithms to achieve a bi-criterion approximation and/or online competitive ratios, see, e.g., [Ravi et al., 1993; Korula et al., 2013; Aggarwal et al., 2014; Esfandiari et al., 2016]. The work of [Brubach et al., 2020; Fata et al., 2019] have the closest setting to us: each edge has an independent existence probability and each vertex from the offline and/or online side has a patience constraint on it. However, all investigated one single objective: maximization of the total profit over all matched edges.

3 Valid Benchmarks for Profit and Fairness

We first present our benchmark LPs and then an LP-based parameterized algorithm. For each edge f = (u, v), let xf be the expected number of probes on edge f (i.e., assignments of v to u but not necessarily matches) in the offline optimal. For each u (v), let Eu (Ev) be the set of neighboring edges incident to u (v). Consider the following bi-objective LP.

Let LP-(1) and LP-(2) denote the two LPs with the respective objectives (1) and (2), each with Constraints (3), (4), (5), (6). Note that we can rewrite Objective (2) as a linear one like maxη with additional linear constraints as η ≤ ∑f∈Eu xf pf Bu for all u ∈ U. For presentation convenience, we keep the current compact version. The validity of LP-(1) and LP-(2) as benchmarks for our two objectives can be seen in the following lemma.

Lemma 1. LP-(1) and LP-(2) are valid benchmarks for the two respective objectives, profit and fairness. In other words, the optimal values to LP-(1) and LP-(2) are valid upper bounds for the expected profit and fairness achieved by the offline optimal, respectively.

Proof. We can verify that objective functions (1) and (2) each captures the exact expected profit and fairness achieved by the offline optimal by the linearity of expectation. To prove the validity of the benchmark for each objective, it suffices to show the feasibility of all constraints for any given offline optimal. Recall that for each edge f, xf denotes the expected number of probes on f (i.e., assignments of u to v but not necessarily matches) in the offline optimal. Constraint (3) is valid since each driver u has a matching capacity of Bu. Note that the expected arrivals of v during the whole online phase is rv and v can be probed at most ∆v times upon each online arrival. Thus, the expected number of total probes and matches over all edges incident to v should be no more than rv∆v and rv, respectively. This rationalizes Constraints (4) and (5). The last constraint is valid, since for each edge, the expected number of probes should be no more than that of arrivals. Therefore, we justify the feasibility of all constraints for any given offline optimal.

4 LP-based Parameterized Algorithms

The following lemma suggests that for any online algorithm ALG, the worst-case scenario (i.e., the instance on which ALG achieves the lowest competitive ratio) arrives when each driver type has a unit matching capacity. The proof is deferred to the full version 2 .

Lemma 2. Let ALG be an online algorithm achieving an (α, β)-competitive ratio on instances with unit matching capacity (i.e., all Bu=1). We can twist ALG to ALG′ such that ALG′ achieves at least an (α, β)-competitive ratio on instances with general integral matching capacities.

From Lemma 2, we assume unit capacity for all driver types throughout this paper w.l.o.g. In the following, we will present a warm-up algorithm (WarmUp) and then another refined algorithm (AttenAlg), which can be viewed as a polished version of WarmUp with simulation-based attenuation techniques. The main idea of AttenAlg is primarily inspired by the work [Brubach et al., 2020]. Both WarmUp and AttenAlg invoke the following dependent rounding techniques (denoted by GKPS) introduced by [Gandhi et al., 2006]. For simplicity, we state a simplified version of GKPS tailored to star graphs which suffices in our paper.

Recall that Ev is the set of edges incident to v in the compatible graph G. GKPS is such a dependent rounding technique that takes as input a fractional vector z = {zf , f ∈ Ev, zf ∈ [0, 1]} on Ev, and output a random binary vector Z = {Zf , f ∈ Ev}, which satisfied the following properties. (1) Marginal distribution: E[Zf ] = zf for all f ∈ Ev; (2) Degree preservation: Pr[∑f∈Ev Zf ≤ ∑f∈Ev zf ] = 1;

2 https://tinyurl.com/yd9ucv8p

Algorithm 1 Sub-Routine SR(z)

• 1 Apply GKPS to the fractional vector z and let Z be the random binary vector output.
• 2 Choose a random permutation π over Ev.
• 3 Follow the order π to process each f = (u, v) ∈ Ev until v is matched:
• Negative correlation: For any pair of edges f, f ′ ∈ Ev, E[Zf = 1|Zf ′ = 1] ≤ zf .

4 if Zf = 1 and u is available then 5 Probe the edge f (i.e., assign v to u). 6 else 7 Skip to the next one.

Throughout this section, we assume (1) x∗ = {x∗f } and y∗ = {y∗ f } are optimal solutions to LP-(1) and LP-(2) respectively; (2) (α, β) are two given parameters with 0 ≤ α, β ≤ 1, α+β ≤ 1; (3) Bu = 1 for all u from Lemma 2; (4) xv = {x∗f /rv, f ∈ Ev} and yv = {y∗ f /rv, f ∈ Ev}, which are scaled solutions from x∗ and y∗ respectively restricted on Ev. Note that from Constraints (4), (5) and (6), we have that xv and yv are two fractional solutions on Ev and each has a total sum at most ∆v.

4.1 The First AlgorithmWarmUp(α, β)

Let an online vertex v arrive at t. Our job is to probe at most ∆v edges in Ev until v is matched. Let z be a given fractional solution on Ev. WarmUp(α, β) invokes the following procedures (denoted by SR(z)) as a subroutine during each online round: it first selects a set Sv of at most ∆v edges from Ev in a random way guided by a given fractional vector z on Ev and then follows a random order to process all edges in Sv one by one. The details of SR are stated in Algorithm 1.

Based on SR, the main idea of WarmUp(α, β) is as simple as follows: each round when an online vertex v arrives, it invokes SR(xv ) and SR(yv ) with probabilities α and β respectively. Recall that xv and yv are the scaled optimal solutions to LP-(1) and LP-(2) restricted to Ev, each has a total sum at most ∆v. Thus, when we run SR(xv ) or SR(yv ) after v arrives online, we will probe at most ∆v edges incident to v since the final rounded binary vector has at most ∆v ones due to Property of Degree Preservation in the dependent rounding. The details of WarmUp(α, β) are as follows.

We conduct an edge-by-edge analysis. It would suffice to show that each f is probed with probability at least x∗f · α · (1-1/e)/2 and y∗ f · β · (1-1/e)/2 in WarmUp(α, β). Then by linearity of expectation, we can get Theorem 1. Focus on a given u and a time t ∈ [T]. Let SFu,t be the event that u is available at (the beginning of) t.

Proof. Recall that we assume w.l.o.g. that each Bu=1 due to Lemma 2. For each given ℓ < t and f = (u, v) ∈ Eu, let Xf,ℓ indicate if v arrives at time t; Yf,ℓ indicate if f is probed during round ℓ; Zf,ℓ indicate if f is present when probed. Note that in each subroutine of SR(xv ) and SR(yv ) after v

Algorithm 2 WarmUp(α, β)

• 1 Let v arrive at time t.
• 2 With probability α, run SR(xv ).
• 3 With probability β, run SR(yv ).
• 4 With probability 1-α-β, reject v.

arrives, f will be probed only when the final rounded vector has the entry one on f. Thus we claim that E[Yf,ℓ] ≤ αx∗f /rv +βy∗ f /rv due to Property of Marginal Distribution in dependent rounding and statements of WarmUp(α, β). Thus,

Now assume SFu,t occurs (i.e., u is available at t). Consider a given f = (u, v) and let 1f,t indicate f is probed during round t in WarmUp(α, β). Notice that 1f,t occurs if (1) v arrives at time t and (2) f is probed either in SR(xv ) or SR(yv ).

Proof. We focus on the first inequality and try to show that f is probed at t in SR(xv ) with probability at least αx∗f 2T (including the probability of its online arrival). Observe that events v arrives at time t and WarmUp(α, β) runs the subroutine xv both happen with probability αrv T . Let Xv be the rounded binary vector from xv and we use Xv f to denote its entry on f. Let Ev,¬f be the set of edges in Ev excluding f = (u, v). For each f ′ ∈ Ev,¬f , let Yf ′ indicate if f ′ falls before f in the randomorder π and Zf ′ indicate if f ′ is present when probed. Thus we have

Inequality (10) follows from Markov's inequality. Inequality (12) is due to these two observations: (1) E[Xv f ′ |Xv f =

1] ≤ x∗f /rv due to negative correlation in dependent rounding and (2) E[Yf ′ ] = 1/2, E[Zf ′ ] = pf . Inequality (13) follows from the fact ∑f ′∈Ev x∗f ′pf ′ ≤ rv due to Constraint (5). Following a similar analysis, we can prove the second part.

Now we have all ingredients to prove the main Theorem 1.

Proof. Consider a given f = (u, v) ∈ E, let κxf and κyf be the expected number of successful probes of f in SR(xv ) and SR(yv ) respectively. Here a probe of f = (v, u) is successful iff u is available when we assign v to u (but no necessarily means f is present).

The last term is obtained after taking T →∞. Similarly, we can show that κyf ≥ βy∗ f (1-1/e) 2 .

Let Profit(α, β) be the expected total profit obtained by WarmUp(α, β). By linearity of expectation, we have Profit(α, β) ≥ (1-1/e)α 2 ∑f∈E x∗f pewe. From Lemma 1, we know that the expected profit in offline optimal is upper bounded by ∑f∈E x∗f pewe. Thus we claim that WarmUp(α, β) achieves a ratio at least α(1 - 1/e)/2 on the profit. Similarly, we can argue that WarmUp(α, β) achieves a ratio at least β(1 - 1/e)/2 on the fairness.

4.2 The Second AlgorithmAttenAlg(α, β)

Inspired by [Brubach et al., 2020], we can improve at least the theoretical performance of WarmUp with attenuation techniques applied to edges and (offline) vertices. The motivation behind is very simple. Note that edges in Ev are competing for each other since we have to stop probing whenever v is matched. Thus, attenuating those edges which win the higher chance of probing over others can potentially boost the worstcase performance.

Let {γt, µt|t ∈ [T ]} be such a series that is defined as γ1 = 1, µt = 1 - γt/2, γt+1 = γt(1 - µt/T), and Ev,t be the set of available edges f = (u, v) ∈ Ev at time t (i.e., u is available at t). The formal description of AttenAlg is stated in Algorithm 3. We defer the proofs of Theorems 2 and 3 to the full version 2 .

5 Experiments

5.1 Data Preprocessing

We use the New York City yellow cabs dataset 3 , which is collected during the year of 2013. Although the demographics of the drivers and riders are not recorded in the original dataset, we synthesize the racial demographics for riders and drivers in a similar way to [Nanda et al., 2019]. To simplify the demonstration, we consider a single demographic factor of the race only, which takes two possible options between "disadvantaged" (D) or "advantaged" (A). We set the ratio of D to A to be 1 : 2 among riders, which roughly matches the racial demographics of NYC [Review, 2019]. Similarly,

3 http://www.andresmh.com/nyctaxitrips/

Algorithm 3 AttenAlg(α, β)

1 for t = 1, 2, . . . , T do 2 Apply vertex-attenuation such that each u ∈ U is available at t with probability equal to γt. 3 Let v arrive at time t. 4 With probability α, 5 Run SR(xv ). Apply edge-attenuation such that each edge f ∈ Ev,t is probed in SR(xv ) with probability equal to µtx∗f /rv. 6 With probability β, 7 Run SR(yv ). Apply edge-attenuation such that each edge f ∈ Ev,t is probed in SR(yv ) with probability equal to µty∗ f /rv . 8 With probability 1-α-β, reject v.

we set the ratio of D to A among drivers to be 1 : 2 [Hall and Krueger, 2017]. The acceptance rates among the four possible driver-rider pairs (based on race status only), (A,A), (A,D), (D,A), (D,D), are set to be 0.6, 0.1, 0.1 and 0.3, respectively. These probabilities are then scaled up by a factor η such that pf = η + (1 - η) · pf . In our experiments we set η = 0.5. Note that we can apply our model straightforwardly to the case when the real-world distribution of {pf} values is known or can be learned. We collect records during the offpeak period when a lot of drivers are on the road while the requests are relatively lower than peak hours. On January 31, 20, 701 trips were completed in the off-peak hour (4-5 PM), compared to 35, 109 trips in the peak hour (7-8 PM). We focus on longitude and latitude ranging from (-73,-75) and (40.4, 40.95) respectively. We partition the area into 40 × 11 grids with equal size.

We construct the compatibility graph G = (U, V,E) as follows. Each u ∈ U represents a driver type which has attributes of the starting location and race. Each v ∈ V represents a request type which has attributes of the starting location, ending location, and race. We downsample from all driver and request types such that |U| = 57 and |V | = 134. For each driver type u, we assign its capacity Bu with a random value uniformly sampled from [1, B] where we vary B ∈ {10, 15, 25}. For each request of type v, we sample a random patience value ∆v uniformly from {1, 2} and a random arrival rate rv ∼ N(5, 1) (Normal distribution), and then set T = ∑v∈V rv. We add an edge f = (u, v) if the Manhattan distance between starting location of request type v and the location of driver type u is not larger than 1. The profit wf for each f is defined as the normalized trip length of the request type v such that 0 ≤ wf ≤ 1.

Algorithms. We test the WarmUp(α, β) with α + β = 1 against two natural heuristic baselines, namely Greedy-P (short for Greedy-Profit) and Greedy-F (short for GreedyFairness) 4 . Suppose a request type of v arrives at time t. Recall that Ev is the set of neighboring edges incident to v (i.e., the set of assignments feasible to v). Let E′v ⊆ Ev be the set of available assignments f = (u, v) such that there exists at least one drive of type u at t. For Greedy-P, it will repeat greedily selecting an available assignment f ∈ E′v with the maximum weight wfpf over E′v (breaking ties arbitrarily) until either v accepts a driver or v runs out of patience. In contrast, Greedy-F will repeat greedily selecting an available f = (u∗ , v) ∈ E′v with u∗ having the least matching rate before either v accepts a driver or leaves the system. Note that we use LP-(1) and LP-(2) as the default benchmarks for profit and fairness, respectively.

4 A future direction is to consider a hybrid version of Greedy-P and Greedy-F, which optimizes the two objectives simultaneously.

5.2 Results and Discussions

Figure 1 shows the results of competitive ratios for the proposed algorithm with different values of α with (β = 1 - α). We can observe that the profit and fairness competitive ratios of WarmUp always stay above the theoretical lower bounds (in dotted lines), as predicted in Theorem 1. The gaps between performances and lower bounds suggest that theoretical worst scenarios occur rarely in the real world. Note that when B = 25 and α = 1 as shown in Figure 1(c), the lower bound is tight and matches the fairness performance.

Figure 2 shows the profit and fairness performances of WarmUp compared to Greedy-P and Greedy-F. Here are a few interesting observations. (1) As for profit, Greedy-P can always beat Greedy-F but not necessarily for WarmUp. The advantage of Greedy-P over WarmUp becomes more apparent when B is large and less when B is small. Note that in our experiment, the expected total number of arrivals of riders is fixed and therefore, B directly controls the degree of imbalance between drivers and riders. When B is larger, we have more available drivers compared to riders and thus, Greedy-P will outperform all the rest for profit. When B is small, however, we really need to carefully design the policy to boost profit. That's why WarmUp becomes dominant. (2) As for fairness, Greedy-F seemingly can always dominate the rest, though WarmUp shows high flexibility in the fairness performance. WarmUp shows a relatively low sensitivity toward the first parameter α for profit while high sensitivity toward the second parameter β for fairness: the latter becomes particularly obvious when B is large.

6 Conclusion

In this paper, we present a flexible approach for matching requests to drivers to balance the two conflicting goals, maximizations of income equality among all rideshare drivers and the total revenue earned by the system. Our proposed approach allows the policy designer to specify how fair and how profitable they want the system to be via two separate parameters. Extensive experimental results on the real-world dataset show that our proposed approaches not only are far above the theoretical lower bounds but also can smoothly tradeoff the two objectives between the two natural heuristics. Our work opens a few directions for future research. The most direct one is to shorten the gap between the sum of ratios of profit and fairness achieved by AttenAlg (which is 0.46). It will be interesting to give a tighter online analysis than what are presented here or offer a sharper hardness result which suggests the sum of the two ratios should be much lower than 1.

Acknowledgments

Pan Xu was partially supported by NSF CRII Award IIS1948157. The authors would like to thank the anonymous reviewers for their helpful feedback.