# balancing_efficiency_and_fairness_in_ondemand_ridesourcing__02c3fbf5.pdf

Balancing Efﬁciency and Fairness in On-Demand Ridesourcing

Nixie S. Lesmana nixiesap001@e.ntu.edu.sg Xuan Zhang xuan6@illinois.edu Xiaohui Bei xhbei@ntu.edu.sg

We investigate the problem of assigning trip requests to available vehicles in ondemand ridesourcing. Much of the literature has focused on maximizing the total value of served requests, achieving efﬁciency on the passengers side. However, such solutions may result in some drivers being assigned to insufﬁcient or undesired trips, therefore losing fairness from the drivers perspective. In this paper, we focus on both the system efﬁciency and the fairness among drivers and quantitatively analyze the tradeoffs between these two objectives. In particular, we give an explicit answer to the question of whether there always exists an assignment that achieves any target efﬁciency and fairness. We also propose a simple reassignment algorithm that can achieve any selected tradeoff. Finally, we demonstrate the effectiveness of the algorithms through extensive experiments on real-world datasets.

1 Introduction

Ridesourcing refers to a mode of transportation that connects private car drivers with passengers via mobile devices and applications. Recent advances in technology provide the opportunity for ridesourcing platforms to dynamically match drivers and passengers in real time. This new generation of ridesourcing has the potential to signiﬁcantly increase the efﬁciency of urban transportation systems, consequently reducing congestion and pollution [23]. In most on-demand ridesourcing platforms, private-hire car drivers are not allowed to pick up passengers who hail them on the streets, but can only take booking requests assigned by the platform. One key function of these platforms is thus to automatically assign potential passengers to active drivers. The development of an efﬁcient real-time demand assignment algorithm is central to the concept and to the success of a ridesourcing enterprise.

Research into real-time ridesourcing has often focused on developing algorithms for optimal assignment of sets of requests to drivers [1, 33, 24]. In these studies, the common objective is to minimize the total waiting time for passengers and maximize the service rate, achieving efﬁciency on the passengers side. Admittedly, customer satisfaction should be the main goal in any service industry. However, in the ridesourcing domain, the role of drivers is as important as that of passengers in terms of sustaining the business. Drivers have preferences that might not align with those of the passengers that are optimized by the algorithm. A centralized algorithm that only focuses on system efﬁciency will inevitably result in some drivers being assigned to insufﬁcient or undesired trips. Leaving the system as it is would affect the sustainability of the ridesourcing business model in the long run, as unsatisﬁed drivers will not renew their memberships and new drivers will be deterred from signing up. Therefore, fairness on the drivers side should be assessed more carefully and should receive more attention.

Department of Mathematical Sciences, Nanyang Technological University, Singapore 637371 Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, Champaign, IL 61801-3080

33rd Conference on Neural Information Processing Systems (Neur IPS 2019), Vancouver, Canada.

In this paper, we study the batch request-vehicle assignment problem with a focus on both efﬁciency and fairness and address the problem of assigning requests to vehicles that account for the natural tension between these two objectives. In the basic setting, we consider a ﬂeet V of available vehicles and a set R of ride requests. Assignment constraints are captured by a bipartite graph G = (V, R, E), such that edge {v, r} E iff vehicle v can be assigned to serve request r under the speciﬁed constraints. Our goal is to design an assignment algorithm that matches each vehicle to at most one request, such that both efﬁciency and fairness are optimized. For efﬁciency, we adopt the utilitarian criterion, deﬁned as the sum of values of all served requests. This is one of the most axiomatically justiﬁed measures of efﬁciency; it has been studied extensively in the literature and employed as a natural metric for practical applications. For fairness, we adopt the max-min fairness criterion that emphasizes the maximization of the least value that a vehicle obtains. This criterion is built on the Rawlsian egalitarian justice [29] and is well-recognized in various application domains (see more discussions in [34]).

Efﬁciency and fairness are often competing objectives such that in most cases, the optimum of both cannot be achieved simultaneously. Thus, we are naturally led to the question of how to reconcile system efﬁciency and drivers fairness in a ridesourcing assignment. For instance, a central decision maker may choose a mild strategy that balances the tension between efﬁciency and fairness in normal trafﬁc conditions. However, as demand increases and trafﬁc conditions worsen, it may be desirable to move to a strategy that puts higher attention to efﬁciency to quickly serve the waiting passengers. Note that such changes are two-way (i.e., efﬁciency or fairness-oriented), gradual, and dependent on dynamically changing demand conditions. Therefore, to provide better managerial ﬂexibilities to decision makers, we need to provide a full set of candidate allocation solutions and characterize the trade-offs inherent in applying these concepts.

In general, through this paper, we aim to address the following question:

Given any problem instance and any required fairness threshold, how do we ﬁnd a request-vehicle assignment that meets the fairness threshold while also has sufﬁciently good system efﬁciency?

1.1 Our Contributions

Our contributions can be summarized as follows.

We answer the above generic question with an efﬁcient algorithm REASSIGN. Our algorithm takes any desired fairness threshold as a parameter, and through a surprisingly simple procedure, computes an assignment that satisﬁes the fairness threshold and has provably good efﬁciency. Our constructive answer to the question above provides extra managerial ﬂexibilities to decision makers with various needs. For example, in the aforementioned trafﬁc scenario, the requirements for efﬁciency and fairness vary at different stages. By applying our algorithm, one can simply set a speciﬁc fairness requirement as the input of the algorithm to generate an output assignment with the required efﬁciency and fairness.

We further show that the efﬁciency-fairness tradeoff guaranteed by our algorithm is provably optimal. That is, we prove that for any target efﬁciency and fairness that go beyond our guarantee, there exist a problem instance in which no assignment can achieve both targets simultaneously.

Finally, we demonstrate the performance of our algorithm in a case study that considers taxi assignment with real taxi data from New York City. Our experiment results show that in practical scenarios, algorithm REASSIGN is able to signiﬁcantly improve the fairness of the assignment with almost no loss on system efﬁciency.

1.2 Related Works

The problem of vehicle-request assignment in ridesourcing has been studied extensively. Several works have focused on real-time assignment using different approaches, such as greedy match [22], collaborative dispatch [32, 35, 25], planning and learning framework [33], and receding horizon control approach [27].

When requests do not arrive in real-time but are given beforehand, the problem is known as the Dial-a-Ride Problem (DARP) [12, 28]. Many variants of the dial-a-ride problem were proposed depending on the speciﬁc applications [11, 20, 31, 15, 13, 3, 8].

The idea that a fairness criterion may affect efﬁciency in resource allocation problems has been explored in numerous contexts and in a variety of models, such as multiportfolio optimization [18], cake cutting [10, 4, 7], load balancing in job scheduling [21, 2, 16], and bandwidth allocation [26, 17, 9]. Bertsimas et al. [5, 6] has speciﬁcally studied fairness and the corresponding efﬁciency loss in a general divisible resource allocation framework and applied their results to a case study in the context of air trafﬁc management. However, none of these works can easily incorporate additional waiting time and pick-up distance constraints because these are unique to the ridesourcing problem. To the best of our knowledge, the efﬁciency-fairness trade-off in the domain of ridesourcing has not been addressed in the literature.

2 Preliminaries

We consider the following bipartite matching problem that models the batch assignment of a set of requests to a set of available vehicles in on-demand ridesourcing. Let us deﬁne a bipartite graph G = (V, R, E), with V = {v1, v2, . . . , vn} the set of n available vehicles, R = {r1, r2, . . . , rm} the set of m requests, and E {{v, r} : v V, r R} the set of weighted edges such that {v, r} E iff the request r can be served by the vehicle v under some speciﬁed assignment constraints3. A utility uvr is the weight associated to each edge {v, r} and deﬁned as the sum of trip utility wvr (i.e. the proﬁt vehicle v could obtain by serving request r) and historical utility hv (i.e. the total utility v has obtained in preceding assignment periods).

We deﬁne trip value τr as the length of the trip or the shortest time needed to travel from r s pickup to its dropoff location and trip cost ιvr as the cruising time of v induced by serving r. Then, we set our trip utility function wvr = cτr ιvr with c being a constant to balance the value-cost effect.

Next, we will introduce , a parameter that proves to be critical for our tradeoff analysis in Section 3. Formally, := max r R max {v,r},{v ,r} E |wvr wv r| (1)

or the maximum trip utility difference across all pairs of edges corresponding to the same request, across all requests.

Remarks. It is important to note that by our deﬁnition of trip utility wvr, the same request r contributes the same value τr to this trip utility when matched with any vehicle. Thus, directly translates to the maximum difference in vehicle cruising time; it is easy to check that this is bounded above by some assignment constraints that we set, e.g. request waiting time constraint.

We now refer to a setting with graph G = (V, R, E), a set of trip utilities {wvr}{v,r} E and historical utilities {hv}v V as an instance I.

Given an instance I, our goal is to ﬁnd an assignment M that assigns each vehicle v to at most one request M(v) and each request r to at most one vehicle M(r). That is, M is always a matching in the bipartite graph G.

We focus on two main objectives:

The efﬁciency of an assignment M,

v V uv,M(v) = X

v V hv + wv,M(v)

The fairness of an assignment M,

F(M) := min v V {uv,M(v)} = min v V {hv + wv,M(v)}

3We make no restrictions on the structure of the set of edges E and allow it to encode any physical or performance-related constraints, such as that request waiting time should be within some threshold, or vehicle type (e.g. regular, luxury) should match the request type.

Let M be the set of all feasible assignments of instance I, we further deﬁne the optimal efﬁciency Eopt := max{E(M) | M M} and optimal fairness Fopt := max{F(M) | M M}. We will refer to the assignments that produce optimal efﬁciency and optimal fairness as efﬁcient assignment Meff and fair assignment Mfair, respectively.

Note that our model above is ﬂexible with respect to different features that may be of interest to the system. Below we discuss how to incorporate ridesharing (or carpooling) and how our model can handle real-time assignment with multiple time periods.

2.1 Ridesharing

Ridesharing refers to a ridesourcing mode in which a vehicle can serve multiple (usually no more than 2) requests simultaneously. Such a service has been provided by all major ridesourcing companies worldwide and has enormous potential for positive societal impacts in terms of pollution, energy consumption, and trafﬁc congestion.

Our model can be easily adapted to allow ridesharing and following are the speciﬁc changes needed to be made. First, we deﬁne a passenger to be a past request assigned in any preceding periods that had not been picked up, or had been picked up by some vehicle and is currently en route to its destination. At any batch assignment, each vehicle v V will have its own set of passengers Sv. Thus, to determine whether an edge {v, r} E, we need to update our assignment constraints such that, for instance, the total number of occupied seats by r and p, p Sv, does not exceed the vehicle s capacity or the delay (corresponding to r and each passenger p Sv) imposed by augmenting r to v s current route should be within some speciﬁed threshold.

Next, by allowing ridesharing, our deﬁnition of hv implies the inclusion of trip utility wvp of all passengers p Sv. It is particularly important to note the slight difference between the interpretation of trip cost in this setting and its single-ride counterpart.4

Note that all these changes only affect the structure (density) of graph G and the values in {hv}v V associated to its edge weights. The overall model remains the same. The deﬁnition of efﬁciency and fairness also remains unchanged. Hence, all the results and algorithm in Section 3 directly extend to this setting. We will describe more details on the speciﬁc constraints for ridesharing relevant to our case study in Section 4.

2.2 Multi-Period Assignment

The above model describes a vehicle-request assignment problem in a single-batch setting. In practice, requests are collected and matched in multiple batches in real-time throughout the day. To this end, we can generalize our model to the following multi-period setting.

We split the duration of one day into T discrete time periods {1, . . . , T} (e.g., 30s per period). Requests are collected and matched during each time period. Consider a vehicle v that is assigned to serve request r in the current time period. In the single-ride setting, v will become unavailable for tvr time periods while serving r and reappear at the r s destination afterward. In the ridesharing setting, r s pickup and destination locations will be appended to the route associated to the passenger set Sv, as long as this satisﬁes the speciﬁed assignment constraints.

The deﬁnition of historical utility hv extends naturally in the context of multi-period assignment in that hv is to be updated after each batch assignment, i.e. ht+1 v = ht v + wt+1 vr . Therefore, at t = T, the deﬁnition of utility, efﬁciency, and fairness remain the same.

4Generally, we deﬁne trip cost as follows,

ιvr := max{0, pu(r) max{t, do(p)}}

with t the assignment time of r, pu(r) the pickup time of r, and do(p) the last dropoff time of passenger p that has been on-board during the assignment of r. This deﬁnition caters to the case when Sv is not empty and that assigning r to v may involve the altering of v s original route in a non-trivial way. Meanwhile, in a single-ride setting, this deﬁnition just implies r s pickup duration.

3 Efﬁciency-Fairness Tradeoff

In this section we analyze the efﬁciency and fairness tradeoff in ridesharing. Our main result is the following theorem. Theorem 3.1. Given any ridesharing problem instance I and any 0 λ 1, there exists an assignment M with fairness F(M) λFopt and efﬁciency E(M) 2 2+λ(Eopt n ) simultaneously.

Our proof is constructive. In the following we present a simple reassignment algorithm that, starting from any existing assignment Mold, outputs a new assignment Mnew satisfying any desired fairness threshold with bounded efﬁciency loss from Mold.

Algorithm 1: REASSIGN (I, Mold, f) Input :Instance I = {G(V, R, E), {wvr}{v,r} E, {hv}v V}, current assignment Mold, fairness threshold f Fopt. Output :A new vehicle-request assignment Mnew 1 Compute a fair assignment Mfair 2 Set Mnew = Mold 3 while there exists v V such that hv + wv,Mnew(v) < f do

4 r Mnew(v)

6 while there exists v V such that Mnew(v ) = Mfair(v) do

8 Mnew(v) Mfair(v)

11 Mnew(v) = Mfair(v)

Intuitively, the algorithm repeatedly chooses a vehicle v whose total utility uv,Mnew(v) is lower than the fairness threshold f, and swap its assigned request to the one given out by the fair assignment, i.e. assign v to Mfair(v). Note that this new request Mfair(v) may be assigned to another vehicle v in Mnew and thus, the swapping of solution continues until no such v can be found, as described in line 6-10 of REASSIGN.

Compute a fair assignment Mfair. Line 1 of REASSIGN requires us to compute a fair assignment Mfair. This can be done efﬁciently using a simple variation of the standard bipartite matching algorithm: We add n no-serve requests r1, . . . , rn to set R. Each ri has only one vehicle vi connected to it with wvi,ri = 0; accordingly, we have uvi,ri = hvi. This edge represents the option of not assigning vehicle vi to any requests. Let the new request set be R+ and the new edge set be E+. Then for any value f, we deﬁne Gf := (V, R+, Ef = {{v, r} E+ | hv + wv,r f}). It is now easy to see that the optimal fairness Fopt is the largest value f such that Gf still has a perfect matching. Such f can be found via a binary search on all possible fairness thresholds. Mfair is then a perfect matching in GFopt.

To prove Theorem 3.1, we show a more general claim about the output of REASSIGN. Lemma 3.2. Given instance I, current assignment Mold and any fairness threshold f Fopt, algorithm REASSIGN(I, Mold, f) always outputs an assignment Mnew with fairness F(Mnew) f and efﬁciency E(Mnew) 2Fopt 2Fopt+f (E(Mold) n ).

The idea of the proof of Lemma 3.2 is to consider each iteration of chain swapping (line 6-10 of REASSIGN). For some request r, its contribution to the decrease in efﬁciency is at most if r is matched in Mnew, otherwise if r is dropped , it is bounded above by f. We can then bound above the number of dropped requests by constructing a lower bound for E(Mnew). The latter can be obtained from the fact that we swap the violating edges with its fair counterpart (i.e. the weight of this edge is bounded below by Fopt) and in a non-trivial case (i.e. Ei(Mnew) Ei(Mold)), we have at least 2 edges swapped in one iteration.

Finally, Theorem 3.1 can be proved directly by replacing f with λFopt in Lemma 3.2.

Lower Bound. Next we focus on the theoretical lower bound for the efﬁciency-fairness tradeoff that any algorithm could achieve. In particular, we show that the tradeoff achieved in Theorem 3.1 is actually tight in this model. Theorem 3.3. For any 0 λ 1 and any α strictly larger than 2 2+λ, there always exists a problem instance I, such that no assignment can achieve fairness F(M) λFopt and efﬁciency E(M) α(Eopt n ) simultaneously.

The proof uses a simple counter-example construction and is omitted.

Theorem 3.1 and 3.3 together show that among all possible algorithms that can achieve a certain fairness requirement, the efﬁciency achieved by our algorithm REASSIGN has the best theoretical guarantee.

4 Experiments

At a ﬁrst glance, the theoretical guarantee obtained in Section 3 may not be enough to convince the decision maker of a ridesourcing platform to consider fairer solutions. Because the loss in efﬁciency, which directly translates to a revenue loss of the platform, might be too signiﬁcant for fairness considerations. For example, if one wants to adopt the fairest solution, setting λ = 1 in Theorem 3.1 shows that in the worst case the platform needs to sacriﬁce more than 33% of efﬁciency. However, as we will demonstrate in this section, in practice such worst case scenario will almost never happen. Through extensive experiments on real-world datasets, we show that when moving towards fairer solutions, the incurred loss in efﬁciency is much smaller than the theoretical prediction and in many cases negligible.

We test the performance of our algorithm in two settings: the single-batch setting, in which we consider all requests within a short period of time and assign them to the set of available vehicles; and the multi-period setting, in which the requests are collected and assigned in multiple batches in real-time. We also consider both single-ride and ridesharing setting, as described in the Preliminaries Section.

Dataset. We use the publicly available dataset of taxi trips in New York City [14], which contains for each day the time and location of all of the pickups and drop-offs executed by each of the active taxis. We choose a representative 2-hour horizon, 1700 - 1900, and extract all requests originating and ﬁnishing within Manhattan, happening in May 2013. We consider the recorded pickup time as the request arrival time and the recorded passenger count as the request size. There are between 31,694 to 56,743 extracted requests each day. To reﬂect real road conditions and traveling time, we construct a road network of Manhattan with 3,671 nodes and 7,674 edges. For simplication purposes, we round the original pickup and drop-off location of data-extracted requests to their respective closest nodes. Travel time on each road or edge of the network is estimated based on the daily mean travel time estimate following the method in [30]. Shortest paths and travel times between all nodes are then precomputed and stored in a look-up table.

Construction of Bipartite Graph. Following, we describe the speciﬁc constraints that we use in the construction of the edge set E of G = (V, R, E)5: a vehicle v V and a request r R is connected by an edge {v, r} iff there exists a way for v to serve r such that (i) the difference between r s pick-up time and its request time is within a threshold Ω; (ii) the total travel delay time, deﬁned as the difference between r s actual drop-off time and its earliest possible drop-off time, is within a threshold Γ; (iii) the trip utility wvr 0; (iv) if ridesharing is allowed, the total number of passengers (inclusive of r) on the vehicle at any time does not exceed the vehicle capacity χ. For simpliﬁcation purposes, we assume that any vehicles can serve up to two requests at any time.

4.1 Single-Batch Assignment

Our single-batch setting experiment aims to elicit and analyze worst-case circumstances in terms of efﬁciency loss. For this purpose, we construct synthetic cross-sectional scenarios (i.e. when vehicles

5These are the same set of rules used in [1].

have been on the road for some time and are available to serve new request) by tuning the parameters that control request data extraction, vehicle positioning, and the structure of our bipartite graph (for example, by relaxing assignment contraints or changing the ratio |V |

4.1.1 Experimental Setup and Data Preprocessing

We pick several days in which there are more than 200 requests arriving in the ﬁrst 30 seconds of the 1700-1900 horizon and test our algorithm on each day under different scenarios. Following, we describe the exact setting that we used to produce our worst-case results. We consider all requests with trip length at least 400s such that we have m = |R| [105, 142]. Upon initialization, we locate n = 1.2m vehicles within a reasonable time-distance from the requests such that each vehicle is connected to at least 10 different requests in G. We deﬁne two groups of vehicles, VH and VL, with |VH| = m = 5|VL| to introduce some level of discrepancies to vehicle historical utilities and randomly generate hv such that v VH, hv U(200, 400) and v VL, hv U(50, 100). Finally, we set the maximum waiting time constraint Ω= 210s, constant c = 1, and vehicle capacity χ = 4.

4.1.2 Results

0.2 0.4 0.6 0.8 1.0 F(M)/Fopt

Reassign Lower-bound (Thm 3.1)

(a) Efﬁciency-Fairness Tradeoff

0 20 40 60 80 100 120 140 Vehicle ID

Utility (secs)

Eﬃcient Assignment Fair Assignment

(b) Utilities

Figure 1: (a) The efﬁciency and fairness of the assignments output by REASSIGN with respect to different fairness thresholds, compared with the theoretical lower bound implied by Thm 3.1 (b) The utilities of all vehicles in the efﬁcient assignment and the fair assignment, both sorted from smallest to largest.

Figure 1(a) demonstrates the tradeoff between efﬁciency and fairness when applying our algorithm REASSIGN with different values of fairness threshold f.

As one can see from the ﬁgure, when efﬁciency is the only concern (corresponding to the leftmost point6), the resulting assignment may have the lowest utility of all drivers as low as 51. However, as we start applying REASSIGN with higher and higher fairness thresholds, this lowest utility value gradually improves, until it reaches the highest point Fopt = 328 in the fair solution (corresponding to the rightmost point). For the worst-off driver, the utility improvement from efﬁcient assignment to the fair assignment is over 6-fold.

It is also important to note that, although Theorem 3.1 and 3.3 claim that the maximum efﬁciency loss may be as high as 33% (as indicated by the dashed curve in Figure 1(a)) in the worst case, this loss is much smaller in reality. In this example, the largest efﬁciency loss is less than 6% from the optimal efﬁciency. This is our worst-case result; the results corresponding to other days and settings preserve similar magnitudes of fairness improvement, while demonstrating even smaller efﬁciency losses, with many under 1%.

From our experiments, we observe three situations in which we could incur more efﬁciency loss: (i) when there is a denser bipartite graph, essentially more leeway to permutate between different vehicle-

6Note that the threshold f = 0 corresponding to no fairness constraint is not necessarily binding in the reassignment procedure. For instance, in this particular case, we can keep increasing f up to .16Fopt before the algorithm outputs a matching with different (and higher) fairness value.

request pairs; (ii) when efﬁcient allocation has a signiﬁcantly smaller overall trip cost compared to that of a fair allocation; (iii) when more requests are dropped by reassignment to a fairer solution. (i), (ii), and (iii) are intricately connected and may have competing effect up to some extent on the efﬁciency loss. Therefore, we can conclude that the theoretical worst-case efﬁciency loss does not necessarily arise even in artiﬁcial examples; here, we have seen the problem instances that show much more benign behaviour.

Finally, we compare the utilities of all vehicles (after assignment) in the efﬁcient and fair matching. In Figure 1(b), we plot these two sets of utilities, after sorting the elements from smallest to largest. It is evident that our algorithm manages to redistribute the trip utility increments to the vehicles with low historical utilities, without sacriﬁcing too much on the efﬁciency.

4.2 Multi-Period Assignment

We further assess the performance of our algorithm in the multi-period case, where we compute a matching assignment using REASSIGN in each period with available vehicles and requests. For this purpose, we ﬁx λ and set f = λFopt in REASSIGN for each period t {1, 2, . . . , T}. Note that due to the dependence of the future instances on current assignments and the uncertainty inherent to future demand distributions, we cannot claim the same theoretical guarantee as shown in Section 3 at the end of the multi-period assignment horizon. Nevertheless, experiment results show that our algorithm REASSIGN performs even better in the multi-period setting, demonstrating satisfactory fairness improvement with almost no loss in efﬁciency.

4.2.1 Experimental Setup and Data Preprocessing

We discretize the 1700-1900 horizon into T = 240 time-steps of 30 seconds. At t = 0, we initialize n = 2000 empty vehicles with capacity χ = 4 at reasonable locations based on the frequency and locations at which requests appear in the whole 2-hour horizon. Requests are generated from the dataset and collected in time windows of 30s. Each vehicle will continue to pickup and dropoff passengers following the routes assigned in batches by the central. Historical utility hv is set to 0 for all vehicles at the beginning of the simulation horizon. Then in any particular period, hv represents the accumulated trip utilities wvr from all the requests that vehicle v has been matched to (see Section 2 for more details on the updating of hv). In the case of ridesharing, hv should include the trip utilities wvp of all passengers p Sv. We set the maximum waiting time constraint Ω= 150s and maximum delay time constraint Γ = 300s.

Remarks. Note that the controlling of vehicle initial locations is in line with what we did in the single-batch setting; we make sure that there are sufﬁciently many requests each vehicle can serve during the 2-hour horizon. With this, we want to alleviate the adverse impact that exogenous factors, such as the neighbouring structure of our network, have on fairness. Speciﬁc to the multi-period setting, we also need to take care of vehicle s intermediate locations (after each assignment). Consider the case when vehicle is assigned to a request with dropoff node having very few degrees. Due to our assumption that any vehicle stays still until it is assigned a new request, this vehicle may be stuck forever in this node. In this respect, we removed the requests whose drop-off node is not close to sufﬁciently many pickup nodes. We keep such removal under 4 percents of all requests in the dataset.

Following, we present the average results of our algorithm tested on 10 different days.

4.2.2 Results

Figure 2 shows again the efﬁciency and fairness tradeoff for the algorithm REASSIGN given different values of λ, in both single-ride and ridesharing setting. Compared to the single-batch setting, these results are even more extreme: there is essentially negligible efﬁciency loss, even for the fairest solution with λ = 1. One explanation of such phenomenon is that as time progresses, the historical utilities of all vehicles will increase to larger and larger values relative to the batch-speciﬁc trip utility increments that we can control by specifying λ s. As a result, the analysis of Theorem 3.1 is no longer tight and correspondingly, the efﬁciency loss will be signiﬁcantly smaller than what the theorem claims.

Figure 3 then shows the fairness improvement when we set different λ as the parameter in REASSIGN. One can still observe a signiﬁcant increase in fairness value when we shift our λ from 0 to 1.

0.4 0.5 0.6 0.7 0.8 0.9 1.0 F(M)/Fopt

Reassign Lower-bound (Thm 3.1)

(a) Single-Ride

0.2 0.4 0.6 0.8 1.0 F(M)/Fopt

Reassign Lower-bound (Thm 3.1)

(b) Ridesharing

Figure 2: The efﬁciency and fairness of the assignments output by REASSIGN with respect to different fairness thresholds in the multi-period setting.

0.0 0.2 0.4 0.6 0.8 1.0 λ

(a) Single-Ride

0.0 0.2 0.4 0.6 0.8 1.0 λ

(b) Ridesharing

Figure 3: Relative fairness values of the assignments output by REASSIGN with regard to different λ in the multi-period setting. The vertical intervals represent the 95% conﬁdence intervals.

Overall, these results suggest that in practical scenarios, it is often possible to signiﬁcantly improve fairness with negligible loss in system efﬁciency. This essentially implies that by considering fair solutions, ridesourcing enterprises will have the capacity to do much greater good without sacriﬁcing their proﬁtability.

5 Conclusion

In this paper, we deal with the problem of balancing efﬁciency and fairness in the context of ridesourcing request assignment. We present a simple reassignment algorithm that can compute an assignment with any desired fairness and provably good efﬁciency. We also provide tight upper bound on the relative efﬁciency loss of our solution compared to the efﬁcient-maximizing assignment. Experiment results show that in practical scenarios, this algorithm is able to signiﬁcantly improve the fairness of the assignment to drivers with very little loss on the system efﬁciency.

The theoretical bounds derived in our work are of independent interest and can be applied to a broader family of matching problems. How to ﬁnd other suitable applications in which similar techniques or results can be applied to is one interesting future working direction. Other future research directions may include considering strictly passenger-side efﬁciency or different fairness criteria, such as proportional fairness [19], and measure their tradeoffs with efﬁciency. Finally, our investigations lead to the open question of designing a learning framework to obtain endogenously the optimal string of λ s, that interacts with and adjusts to real-time supply-demand dynamics.

[1] Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences, 114(3):462 467, 2017.

[2] Javed Aslam, April Rasala, Cliff Stein, and Neal Young. Improved bicriteria existence theorems for scheduling. ar Xiv preprint cs/0205008, 2002.

[3] Roberto Baldacci, Aristide Mingozzi, and Roberto Roberti. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1):1 6, 2012.

[4] Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, and Endong Yang. Optimal proportional cake cutting with connected pieces. In Twenty-sixth AAAI Conference on Artiﬁcial Intelligence, 2012.

[5] Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. The price of fairness. Operations research, 59(1):17 31, 2011.

[6] Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. On the efﬁciency-fairness trade-off. Management Science, 58(12):2234 2250, 2012.

[7] Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou. The efﬁciency of fair division. Theory of Computing Systems, 50(4):589 610, 2012.

[8] Zhi-Long Chen and Hang Xu. Dynamic column generation for dynamic vehicle routing with time windows. Transportation Science, 40(1):74 88, 2006.

[9] Sung-woo Cho and Ashish Goel. Pricing for fairness: distributed resource allocation for multiple objectives. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 197 204. ACM, 2006.

[10] Yuga J Cohler, John K Lai, David C Parkes, and Ariel D Procaccia. Optimal envy-free cake cutting. In Twenty-Fifth AAAI Conference on Artiﬁcial Intelligence, 2011.

[11] Jean-François Cordeau. A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3):573 586, 2006.

[12] Jean-François Cordeau and Gilbert Laporte. The dial-a-ride problem: models and algorithms. Annals of operations research, 153(1):29 46, 2007.

[13] Guy Desaulniers, Fausto Errico, Stefan Irnich, and Michael Schneider. Exact algorithms for electric vehicle-routing problems with time windows. Operations Research, 64(6):1388 1405, 2016.

[14] Dan Donovan, Brian; Work. New york city taxi trip data (2010-2013), 2016.

[15] Alain Faye and Dimitri Watel. Static dial-a-ride problem with money as an incentive: Study of the cost constraint. 2016.

[16] Ashish Goel, Adam Meyerson, and Serge Plotkin. Approximate majorization and fair online load balancing. In Symposium on Discrete Algorithms: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, volume 7, pages 384 390, 2001.

[17] Ashish Goel, Adam Meyerson, and Serge Plotkin. Combining fairness with throughput: Online routing with multiple objectives. Journal of Computer and System Sciences, 63(1):62 79, 2001.

[18] Dan A Iancu and Nikolaos Trichakis. Fairness and efﬁciency in multiportfolio optimization. Operations Research, 62(6):1285 1301, 2014.

[19] Frank P Kelly, Aman K Maulloo, and David KH Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society, 49(3):237 252, 1998.

[20] Taehyeong Kim. Model and algorithm for solving real time dial-a-ride problem. Ph D thesis, 2011.

[21] Jon Kleinberg, Yuval Rabani, and Éva Tardos. Fairness in routing and load balancing. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 568 578. IEEE, 1999.

[22] Der-Horng Lee, Hao Wang, Ruey Cheu, and Siew Teo. Taxi dispatch system based on current demands and real-time trafﬁc conditions. Transportation Research Record: Journal of the Transportation Research Board, (1882):193 200, 2004.

[23] Yanwei Li, Araz Taeihagh, and Martin de Jong. The governance of risks in ridesharing: A revelatory case from singapore. Energies, 11(5):1277, 2018.

[24] Kaixiang Lin, Renyu Zhao, Zhe Xu, and Jiayu Zhou. Efﬁcient large-scale ﬂeet management via multi-agent deep reinforcement learning. ar Xiv preprint ar Xiv:1802.06444, 2018.

[25] Shuo Ma, Yu Zheng, and Ouri Wolfson. T-share: A large-scale dynamic taxi ridesharing service. In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 410 421. IEEE, 2013.

[26] Nimrod Megiddo. Optimal ﬂows in networks with multiple sources and sinks. Mathematical Programming, 7(1):97 107, 1974.

[27] Fei Miao, Shuo Han, Shan Lin, John A Stankovic, Desheng Zhang, Sirajum Munir, Hua Huang, Tian He, and George J Pappas. Taxi dispatch with real-time sensing data in metropolitan areas: A receding horizon control approach. IEEE Transactions on Automation Science and Engineering, 13(2):463 478, 2016.

[28] Ida Nedregård. The integrated dial-a-ride problem-balancing costs and convenience. Master s thesis, NTNU, 2015.

[29] John Rawls. A theory of justice. Harvard university press, 2009.

[30] Paolo Santi, Giovanni Resta, Michael Szell, Stanislav Sobolevsky, Steven H Strogatz, and Carlo Ratti. Quantifying the beneﬁts of vehicle pooling with shareability networks. Proceedings of the National Academy of Sciences, 111(37):13290 13294, 2014.

[31] Douglas O Santos and Eduardo C Xavier. Taxi and ride sharing: A dynamic dial-a-ride problem with money as an incentive. Expert Systems with Applications, 42(19):6728 6737, 2015.

[32] Kiam Tian Seow, Nam Hai Dang, and Der-Horng Lee. A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Science and Engineering, 7(3):607 616, 2010.

[33] Zhe Xu, Zhixin Li, Qingwen Guan, Dingshui Zhang, Qiang Li, Junxiao Nan, Chunyang Liu, Wei Bian, and Jieping Ye. Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 905 913. ACM, 2018.

[34] H Peyton Young. Equity: in theory and practice. Princeton University Press, 1995.

[35] Rick Zhang and Marco Pavone. Control of robotic mobility-on-demand systems: a queueingtheoretical perspective. The International Journal of Robotics Research, 35(1-3):186 203, 2016.