{'fraction_non_alphanumeric': 0.05204506490325741, 'fraction_numerical': 0.015062454077883909, 'mean_word_length': 3.9688165500456343, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Trading the System Efficiency for the Income Equality of Drivers in Rideshare

Several scientific studies have reported the existence of the income gap among rideshare drivers based on demographic factors such as gender, age, race, etc. In this paper, we study the income inequality among rideshare drivers due to discriminative cancellations from riders, and the tradeoff between the income inequality (called fairness objective) with the system efficiency (called profit objective). We proposed an online bipartite-matching model where riders are assumed to arrive sequentially following a distribution known in advance. The highlight of our model is the concept of acceptance rate between any pair of driver-rider types, where types are defined based on demographic factors. Specially, we assume each rider can accept or cancel the driver assigned to her, each occurs with a certain probability which reflects the acceptance degree from the rider type towards the driver type. We construct a bi-objective linear program as a valid benchmark and propose two LP-based parameterized online algorithms. Rigorous online competitive ratio analysis is offered to demonstrate the flexibility and efficiency of our online algorithms in balancing the two conflicting goals, promotions of fairness and profit. Experimental results on a real-world dataset are provided as well, which confirm our theoretical predictions.


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;Curry et al., 2019;Ashlagi et al., 2019;Lowalekar et al., 2018;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) v 1 (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 B u ∈ Z + , which captures the number of drivers belonging to the type u. Additionally, we have the following key assumptions in the model. 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 {q v } such that v∈V q v = 1. Note that the sampling process is independent and identical across the online T rounds. For each v, let r v = T · q v , which is called the arrival rate of request v with v∈V r v = 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;. 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 p f ∈ (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 p f 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 {p f } 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 p f . Assume that the platform will gain a profit w f from a successful assignment f = (u, v) (we call a match then). For a given policy ALG, let M be the set of (possibly random) suc-cessful 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 objectives, 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 Fairness: Let M u be the set of edges in M incident to u. Define the fairness achieved by ALG over all driver types as min u∈U

Preliminaries and Main 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) = E I∼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 min I

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

Related Work
Fairness in operations is an interesting topic which has a large body of work [Bertsimas et al., 2011;Bertsimas et al., 2012;Chen and Wang, 2018;Lyu et al., 2019;Cohen et al., 2019;Ma and Xu, 2020;Chen et al., 2020]. 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 rideshare 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 p f = 1). The recent work [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;Grandoni et al., 2009;Korula et al., 2013;Aggarwal et al., 2014;Esfandiari et al., 2016]. The work of [Bansal et al., 2012;Brubach et al., 2018;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.

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 x f 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 E u (E v ) 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 x f p f 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 , x f 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 B u . Note that the expected arrivals of v during the whole online phase is r v 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 r v ∆ v and r v , 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.

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.
Lemma 2. Let ALG be an online algorithm achieving an (α, β)-competitive ratio on instances with unit matching capacity (i.e., all B u =1). We can twist ALG to ALG such that ALG achieves at least an (α, β)-competitive ratio on instances with general integral matching capacities.
Proof. Let ALG be online algorithm with an (α, β)competitive ratio when all u have a unit matching capacity. Consider a given instance I with general matching capacities. We can create a corresponding instance I with unit capacities by replacing each u with a set S u of identical copies of u where |S u | = B u . Note that for any feasible solution {x f } to LP-(1) and LP-(2) on the instance I , we can create another feasible solution {x f } to LP-(1) and LP-(2) on I where x f = x f /B u for every f ∈ S u and u. We can verify that the objective values of LP-(1) and LP- (2)  x f = f ∈Su x f for each u. We can verify that the objective value of LP-(1) remains the same on {x f } and {x f }. Let {y f } be an optimal solution LP-(2) on the instance I and w.lo.g. assume that all y w .
= f ∈Ew y f p f are the same over all w ∈ ∪ u S u (otherwise we can decrease some {y f } until all y w are the same). Thus, we claim that the objective value of LP-(2) remains the same on {y f } and {y f }. From the above analysis, we conclude that the optimal LP values of LP-(1) and LP-(2) each remains the same on I and I. Now let ALG be such an online algorithm on I that it first replaces I with I and then apply ALG to I. We can verify that ALG is valid online algorithm on I since (1) each u will be matched at most B u times since each w ∈ S u will be matched at most once when applying ALG to I; and (2) each v will be probed at most ∆ v times upon arrival. Let P (I) and F (I) be the profit and fairness achieved by ALG on I. Similarly let P (I ) and F (I ) be the profit and fairness achieved by ALG on I . Let W = ∪ u S u be the set of offline vertices in I, and for each w ∈ W , let γ w be the expected number of matches of w when ALG is applied to I. Observe that P (I ) = P (I) and Note that benchmark LP values of LP-(1) and LP-(2) each remains the same on I and I . Thus, we get our claim.
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., 2018]. 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 E v 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 = {z f , f ∈ E v , z f ∈ [0, 1]} on E v , and output a random binary vector 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) B u = 1 for all u from Lemma 2; (4) which are scaled solutions from x * and y * respectively restricted on E v . Note that from Constraints (4), (5) and (6), we have that x v and y v are two fractional solutions on E v and each has a total sum at most ∆ v . The first algorithm WarmUp(α, β). Let an online vertex v arrive at t. Our job is to probe at most ∆ v edges in E v un-til v is matched. Let z be a given fractional solution on E v . WarmUp(α, β) invokes the following procedures (denoted by SR(z)) as a subroutine during each online round: it first selects a set S v of at most ∆ v edges from E v in a random way guided by a given fractional vector z on E v and then follows a random order to process all edges in S v one by one. The details of SR are stated in Algorithm 1.
Algorithm 1: Sub-Routine SR(z): Dependent rounding combined with random permutation 1 Apply GKPS to the fractional vector z and let Z be the random binary vector output. 2 Choose a random permutation π over E v . 3 Follow the order π to process each f = (u, v) ∈ E v until v is matched: 4 if Z f = 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.
Based on SR, the main idea of WarmUp(α, β) is as simple as follows: each round when an online vertex v arrives, it invokes SR(x v ) and SR(y v ) with probabilities α and β respectively. Recall that x v and y v are the scaled optimal solutions to LP-(1) and LP-(2) restricted to E v , each has a total sum at most ∆ v . Thus, when we run SR(x v ) or SR(y v ) 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 SF u,t be the event that u is available at (the beginning of) t. Lemma 3. For any given u and t ∈ [T ], we have Pr [SF u,t Proof. Recall that we assume w.l.o.g. that each B u =1 due to Lemma 2. For each given < t and f = (u, v) ∈ E u , let X f, indicate if v arrives at time t; Y f, indicate if f is probed during round ; Z f, indicate if f is present when probed. Note that in each subroutine of SR(x v ) and SR(y v ) after v arrives, f will be probed only when the final rounded vector has the entry one on f . Thus we claim that E[Y f, ] ≤ αx * f /r v +βy * f /r v due to Property of Marginal Distribution in dependent rounding and statements of WarmUp(α, β). Thus, Now assume SF u,t occurs (i.e., u is available at t). Consider a given f = (u, v) and let 1 f,t indicate f is probed during round t in WarmUp(α, β). Notice that 1 f,t occurs if (1) v arrives at time t and (2) f is probed either in SR(x v ) or SR(y v ).
Proof. We focus on the first inequality and try to show that f is probed at t in SR(x v ) 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 x v both happen with probability αrv T . Let X v be the rounded binary vector from x v and we use X v f to denote its entry on f .
Inequality (10) follows from Markov's inequality. Inequality (12) is due to these two observations: (13) follows from the fact f ∈Ev x * f p f ≤ r v 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 κ x f and κ y f be the expected number of successful probes of f in SR(x v ) and SR(y v ) 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 κ y f ≥ βy * f (1−1/e) 2 . Let Profit(α, β) be the expected total profit obtained by WarmUp(α, β). By linearity of expectation, we have Profit(α, β) f ∈E x * f p e w e . From Lemma 1, we know that the expected profit in offline optimal is upper bounded by f ∈E x * f p e w e . 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.
Inspired by [Brubach et al., 2018], 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 E v 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 worst-case performance.
Let {γ t , µ t |t ∈ [T ]} be such a series that is defined as Let E v,t be the set of available edges f = (u, v) ∈ E v 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 to the Appendix.

3
Let v arrive at time t.

5
Run SR(x v ). Apply edge-attenuation such that With probability β, 7 Run SR(y v ). Apply edge-attenuation such that each edge f ∈ E v,t is probed in SR(y v ) with probability equal to µ t y * f /r v .

Hardness Results
We prove Theorem 3 in this section. Consider the below example. Example 1. Consider a graph which consists of n identical units, each unit i ∈ [n] is a star graph which includes the center of v i and two other neighbors u a i and u b i . Set p i,a = 1 and p i,b = where we use {i, a} ({i, b}) to index the edges (u a i , v i ) and (u b i , v i ) respectively. Assume that (1) unit edge weight on all edges; (2) T = n and unit arrival rate on all v i (i.e., all r v = 1); (3) unit matching capacity on all u (i.e., all B u =1); and (4) unit patience on all v (i.e., all ∆ v = 1).
Let OPT-P and OPT-F be the optimal LP values of LP-(1) and LP-(2) on the above example respectively. We can verify that: (1) OPT-P = n, where there is a unique optimal solution x * i,a = 1 and x * i,b = 0 for all i ∈ [n]; (2) OPT-F = /(1+ ), where there is a unique optimal solution y * i,a = 1+ and y * i,b = 1 1+ for all i ∈ [n]. Now based on Example 1, we prove the below lemma. Lemma 5. Consider Example 1 and assume LP-(1) and LP-(2) as benchmarks. We have (1) no algorithm can achieve a competitive ratio larger than 1−1/e on the profit; (2) no algorithm can achieve competitive ratios on the profit and fairness with a sum larger than 1.
Proof. Consider a given online algorithm ALG, in which the expected number of probes for (u a i , v i ) and (u b i , v i ) are α i and β i for each i ∈ [n], respectively. Let ALG-P and ALG-F be the profit and fairness achieved by ALG. We have that ALG-P = i∈[n] (α i + β i ), ALG-P = min i∈[n] α i , β i . Set α . = i∈[n] α i and β . = i∈[n] β i . Note that (1) α + β ≤ n, and (2) α ≤ (1−1/e)n. The latter inequality is due to each α i ≤ 1 − 1/e. Thus, the sum of competitive ratios on profit and fairness should be As for profit, we see that ALG-P OPT-P = α+ β n ≤ 1 − 1/e + .
Based on the example presented in Lemma 5 of Section 3.1 of [Fata et al., 2019], we can get a stronger version of statement (2) in Lemma 5, which states that no online algorithm can get an online ratio better than 0.51 for either the profit or fairness based on LP-(1) and LP-(2). Summarizing all analysis we prove Theorem 3.

Experiments
In this section, we describe our experimental results on a real dataset: the New York City yellow cabs dataset 2 which contains the trip histories for thousands of taxis across Manhattan, Brooklyn, and Queens. Data preprocessing. The dataset is collected during the year of 2013. Each trip record includes the (desensitized) driver's license, the pick-up and drop-off locations for the passenger, the duration and distance to complete the trip, the starting and ending time of the trip and some other information such as the number of customers. 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, we set the ratio of D to A among drivers to be 1 : 2 [Thorton and Kiersten, 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 p f = η + (1 − η) · p f . In our experiments we set η = 0.5. Note that we can apply our model straightforwardly to the case when the real-world distribution of {p f } values is known or can be learned. We collect records during the off-peak period of 4-5 PM when a lot of drivers are on the road while the requests are relatively lower than peak hours. On January 31, 2013, 20, 701 trips were completed in the off-peak hour (from 16:00 to 17:00), compared to 35, 109 trips in the peak hour (from 19:00 to 20:00). 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. Each grid is indexed by a unique number to represent a specific pick-up and drop-off location.
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 B u with a random value uniformly sampled from [1, B] where we vary B ∈ {10, 15, 20, 25}. For each request of type v, we sample a random patience value ∆ v uniformly from {1, 2} and a random arrival rate r v ∼ N (5, 1) (Normal distribution), and then set T = v∈V r v . 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 w f for each f is defined as the normalized trip length of the request type v such that 0 ≤ w f ≤ 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 Greedy-Fairness) 3 . Suppose a request type of v arrives at time t.
Recall that E v is the set of neighboring edges incident to v (i.e., the set of assignments feasible to v). Let E v ⊆ E v 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 w f p f 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. We run  all WarmUp(α, β) algorithms for 1000 independent trials and take the average as the expectations. We also run Greedy-P and Greedy-F for 1000 instances and take the average values as the final performance. Note that we use LP-(1) and LP-(2) as the default benchmarks for profit and fairness, respectively.
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(d), 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.

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.