Order dispatching algorithms, which match passenger requests with vehicles (agents) in ridesharing systems, are able to achieve high service rates (percentage of requests served) using deep reinforcement learning techniques to estimate the relative values of the diferent combinations of passenger-vehicle matches. While the goal of such algorithms is to maximize the service rate, this may lead to unintended fairness issues (e.g., high disparity between the service rates of geographic zones in a city). To remedy this limitation, researchers have recently proposed deep reinforcement learning based techniques that incorporates fairness components in the value function approximated. However, this approach sufers from the need to retrain should one wish to tune the degree of fairness or optimize for a diferent fairness function, which can be computationally expensive. Towards this end, we propose a simpler online approach that uses state-of-art deep reinforcement learning techniques and augments their value functions with fairness components during the matching optimization step. As no additional training is needed, this approach can be adapted to use any existing value function approximator and benefits from improved flexibility in evaluating diferent fairness objectives eficiently. In this paper, we describe several fairness functions that can be used by this approach and evaluate them against existing state-of-the-art deep RL based fairness techniques on standard ridesharing benchmarks. Our experiments show that our fairness functions outperform existing fairness techniques (i.e., it finds matching solutions that result in higher service rates and lower service rate disparity across zones), demonstrating the practical promise of this approach.
On-demand ridesharing has been gaining traction over the past few years as a solution to the
growing need for urban mobility. Providing low cost rides to passengers at the expense of
small detours, higher earnings for drivers, and a way to reduce the number of vehicles on the
streets, it is a solution that benefits everyone. Consequently, there has been work on finding
eficient matches of passengers and vehicles to minimize delays and maximize system eficiency
for such ecosystems. Recent approaches have used concepts from dynamic programming
and deep reinforcement learning to learn policies for matching pools of passenger requests to
available drivers, achieving real-time performance capabilities. Some approaches, such as that
by Alonso-Mora et al. [
Optimizing for such metrics, however, can have unintended efects on the fairness of such
systems. The issue of fairness in ridesharing has been discussed in various contexts, ranging
from passenger-side fairness in terms of delay and partner choice, driver-side fairness in terms
of equitable earning, and even sub-group level fairness [
In our approach, we view the problem in the context of a fleet of autonomous vehicles
controlled by the platform. The optimization is formulated as a reinforcement learning problem,
drawing from state-of-art techniques [
Specifically, our contributions are as follows: ∙ We develop an online framework that uses of-the-shelf value function approximators and user-defined fairness objectives to trade of eficiency for fairness using state-of-art matching algorithms. ∙ We introduce new metrics for zonal fairness that consider fairness across source-destination zone pairs. ∙ We provide real-time tuneable parameters for changing between diferent types and degrees of fairness, allowing systems to adapt on the fly, and compare the results to existing benchmarks.
Order dispatching in ridesharing: Rideshare-matching has been extensively studied, and
researchers have introduced methods that improve the quality of the matches made in terms of
increasing the number of requests matched [
A work that is closest to ours is by Raman et al. [
A Ridesharing Matching Problem is a tuple = ⟨ℛ, , , ⟩ consisting of the set of requests ℛ, vehicles , road network , and constraints . The solution to this problem is an assignment that satisfies the constraints and provides a matching between vehicles and requests.
Specifically, a request = ⟨, , ⟩ contains the pickup location , dropof location and the arrival time of the request . The vehicle state = ⟨, , , ⟩ includes its location , current path , capacity and the requests it is currently serving . The street network = ⟨ℒ, ℰ , ()⟩ is a graph containing locations ℒ connected by roads ℰ , with a cost function : ℰ → R+ that defines the cost () of each edge ∈ ℰ in the graph. Intuitively, it corresponds to the time needed by a taxi to traverse that edge on the graph. The matching algorithm then needs to match requests to vehicles given some time and capacity constraints , while optimizing some metric (e.g., maximizing the service rate).
We now describe how NeurADP [
In typical reinforcement learning fashion, there is an agent and an environment. The environment simulates the motion of vehicles and the arrival of requests with the passage of time. Each decision epoch, the agent takes the current state of vehicles and pending requests as input and solves the RMP, matching requests to vehicles. The agent in our setting involves the combination of a VFA for each vehicle, combined with the ILP that finds the optimal assignment based on the values. Using the VFA in this fashion to predict expected returns allows it to make non-myopic decisions that eventually improve the performance of the system.
The VFA is learned based on TD-learning [
We define an action as the matching of a set of requests to a vehicle. If vehicle services request , we denote the reward for the vehicle as (, ). If the set of available (feasible) actions for vehicle is , then, for each action ∈ , the score is the corresponding immediate rewards obtained for servicing those requests plus the expected future value of the new vehicle state after being assigned those requests: where (· ) is the VFA and ′ is the new state of the vehicle after accepting all requests ∈ . As a shorthand, overloading some notation, we can write the reward for an action as: () = (′) + ( )
∑︁ (, ) ∈ (1) (2)
Let be an indicator variable for whether action was selected for vehicle . Then, we can write the objective function of the ILP as follows: subject to the constraints: max ∑︁ ∑︁ × () ∈||
∈ ∑︁
∑︁ ∈|| ∈ s.t. ∈ ∑︁ = 1, ∀ ∈ || ∈
≤ 1, ∀ ∈ ℛ
∈ {0, 1}, ∀ (3) (4) (5) (6)
Intuitively, the constraints ensure that each vehicle is assigned exactly one action (Eq. 4) and no request is assigned to more than one vehicle (Eq. 5). In each vehicle’s set of available actions, there is always the null action (i.e., accepting no new requests), so that there is always a solution. The final assignment is a concatenation of all vehicle assignments at a given decision epoch.
The objective function in NeurADP [
As discussed in earlier sections, there has been interest in preserving fairness across sub-groups of the passenger and driver populations. In our approach, we focus on the passengers, looking at service rate fairness across zone pairs for pickup and dropof locations. The motivation to select this metric is two-fold: (i) It is an intuitive metric and is consistent with other fairness objectives that aims for equity in eficiency across sub-groups; and (ii) It is dificult to get information about race, ethnicity, and other cultural factors from publicly-available ridesharing datasets.
Zonal fairness becomes a concern with algorithms like NeurADP [
We define zones as disjoint subsets of the locations ℒ in the city graph. Our sub-groups
of interest are people moving between pairs of zones. Recent work [
However, this metric does not take into account the destination of the requests, and there may be a disparity between fairness based on source zones and fairness based on zone-pairs, where some source-destination pairs may be severely under-served. To address this limitation, we define zone-pair service rate as the service rate for requests originating in zone and ending in zone . This gives us a grid Z of zone-pair service rates of size × , in addition to a vector Z of source-zone service rates of size .
Given these two sub-group statistics, we can compute fairness metrics of interest, namely the
minimum service rate (by source zone or zone-pair) and the Gini coeficient for the service rates
(also by source zone or zone-pair). We treat each zone/zone-pair as an individual and fairness is
defined by how high the minimum service rate is [
Optimizing Zonal Fairness The key idea of our approach is that the score function in Equation 1 can be modified to encourage particular request-vehicle matches by adding a bonus to particular vehicles servicing requests that would improve fairness. This bonus can be tuned to suit the need for fairness, and the original score function can be used otherwise. This gives us the flexibility of using the best value functions for general operation to maintain eficiency, and using the bonus to guide the system towards fairer decisions. It is important to note that we do not retrain the value function, only using predictions from an existing one.
Specifically, we define two fairness scores for source-zone ( ) and zone-pair () fairness. Here, is the request of interest, and and are the source and destination zones of the request. Intuitively, each score captures how much worse the request’s source zone (zone-pair) is, compared to the average score. A positive score means it is worse. For ease of representation, we also overload this function when used for an action as: (7) (8) (9) (10)
We propose a few methods that use the fairness score in conjunction with the ILP in diferent ways to improve fairness. Each approach modifies the score function (Eq. 1), and can be used with either or , but we find that is empirically stronger.
() = ||Z||1 − () = ||Z||1
2 − () = ∑︁ ()
∈ () = ∑︁ ()
∈ In this method, we designate a random fraction of the vehicles as “fairness-aware,” and these vehicles receive the fairness bonus. The identity of the fairness-aware vehicles does not change over time. Intuitively, this lets some dedicated vehicles improve fairness while most vehicles continue to improve the eficiency objective. Let denote the set of fairness-aware vehicles. We then have the following two variants: • -fair vehicles ( -Veh): The fairness bonus is added to the existing score function for with weight . In other words, Equation 1 is replaced with: () = {︃ (′) + ( ) + .(), if ∈
(′) + (), otherwise • -exclusive-fair vehicles (X -Veh): use only the reward and the fairness score, but not the estimated future value from the neural network. Thus, the fairness-aware vehicles are not concerned with maximizing the long-term value, just the fairness. () = {︃( ) + .(), if ∈
(′) + (), otherwise (11) (12) (13) Request-based Fairness: While having designated vehicles trying to enforce fairness is one solution, it is possible that those vehicles aren’t in the right place at the right time and are thus unable to help improve the inequity. To combat this, we can instead look at fairness on a per-request basis, adding the fairness bonus to the rewards of certain requests. Thus, vehicles will be incentivized to pick up requests that have the fairness bonus, even if the value function gives it a lower score. For this approach, we modify the reward ( ). Let ℛ denote the set of requests with the fairness bonus. We then have the following new reward function to replace Equation 2:
∑︀∈ (, ), {︃∑︀∈ ((, ) + .( )) , ∈ ℛ otherwise To select which requests get the fairness bonus, we propose two methods: • -subset of requests ( -Req): Using a pair of hyperparameters (, ) similar to the two used for fairness-aware vehicles, this approach selects requests by ranking all requests by decreasing .() and selecting the top fraction of requests. • Positive fairness score requests (+Req): In this approach, after ranking requests (as in -Req), we select all the requests that have a positive .(). It amounts to assigning a bonus to all requests going between zones whose service rate is worse than the average service rate.
We can vary and to change the degree of fairness we expect to see in the system. Each method may have a diferent response to the exact values, but in general, we expect larger values of and to improve the fairness objective, while causing a decrease in the overall service rate.
To evaluate the eficacy of the diferent approaches, we evaluate the performance and fairness
metrics after running the matching algorithm over a 24-hour period on the island of Manhattan
using demand data from the NY Yellow Taxi dataset [
We use pre-trained NeurADP models [
However, even with 200 vehicles, the demand from requests saturates the fleet’s capacity. To
simulate a more realistic scenario, we run the experiments with 1000 vehicles as well, similar to
the work by [
For the methods discussed in this paper ( -Veh, X -Veh, -Req, +Req), we perform a logarithmic grid-search over the hyperparameters (0-1) and (0-50). We run this search using both and as the fairness scores, independently. For each setting, we find the overall service rate, the Gini coeficient of the service rate by source zone (Gini( Z)) and by zone-pair (Gini(Z)), and the minimum service rate for any source zone (min(Z)) or zone-pair (min(Z )).
In this section, we go over the key results from our experiments. The full set of experiments had over 900 runs;2 we thus present selected results that illustrate the overall trend. We discuss 1https://github.com/erikgregorywebb/nyc-housing/blob/ master/Data/nyc-zip-codes.csv 2The complete results can be found at https://github.com/ashwinkwashu/ATT22ZonalFairness the results from the analysis of the 1000 vehicle case here, though the trends hold for 200 and 50 vehicles as well.
Pickup-only vs. pickup/dropof-pair fairness: Figure 3 shows the Pareto frontiers that represent the overall service rate and fairness tradeof.
Solid lines are associated with our approaches in which groups are defined with respect to pickup-only locations (), while dashed lines correspond to approaches that define groups based on pickup-dropof location pairs ().
Our first observation is that in nearly every instance the dashed lines (our approaches using zone-pairs) Pareto dominate solid lines (our approaches using source zones only), even when we use source zones (Z) for evaluation. This observation demonstrates the usefulness of the additional observation provided by the latter in improving geographic fairness, and is particularly noteworthy given that the prior FairNN approach defined zones using only pickup locations. Due to this observation, the remaining analysis focuses on pickup-dropof variants of our approaches.
Baseline comparisons: Figure 3 compares the proposed approaches (consider only the dashed lines henceforth) with two baselines: NeurADP and FairNN. For FairNN, we construct the Pareto frontier by considering many values of and omitting any that were Pareto dominated (in some cases, there was only a single Pareto dominant result for FairNN, in which we plotted just this point). First, observe that our approaches Pareto dominate FairNN by a considerable margin. Thus, in addition to computational benefits (we do not have to retrain the value function), the proposed methods can achieve both higher service rate and greater fairness than FairNN. We also observe that the proposed methods can yield considerable fairness improvement over NeurADP, with relatively minor degradation in service rate. This is further illustrated in Table 1. Consider comparison between NeurADP, FairNN( = 107), the best parameter value we identified, and +Req( = 15) in this table. +Req yields nearly the same overall service rate as NeurADP, but with a dramatic increase in the minimum service rate and a dramatic reduction in the Gini coeficient. It also outperforms FairNN on all of these metrics, in several cases by a large margin. Fairness-eficiency tradeof: Figure 2 shows how the various metrics change with changing hyperparameters for -Veh, using the zone-pair fairness score . controls the weight of the fairness score and is the fraction of fairness-aware vehicles. We see that as and increase (stronger fairness), overall service rate decreases and the fairness objective used in the fairness score (here, Gini(Z)) improves. Other fairness metrics like the min(Z) also improve, but the change is not monotonic, as can be seen in the third heatmap. This trend is seen across all diferent methods and both fairness scores. This suggests that there is a direct tradeof between eficiency and the selected fairness metric, and it is possible to use the other metrics to select a suitable value for the hyperparameters.
Further, this shows that there is merit in applying the fairness score to a subset of the vehicle population, as the change in service rate along the axis is slower, while still giving gains for fairness. This is also shown by the fact that min(Z) is maximized when half the vehicles are fair. Specifically, it does not lie at = 1. We also observe that there are diminishing returns with respect to the fairness utility as increases. As shown in Figure 2, doubling the number of fair vehicles does not double the fairness gain.
Relative performance of our methods: We can observe from Figure 3 that request-based methods ( -Req and +Req) tend to outperform vehicle-based methods ( -Veh and X -Veh) across the board, with the only exception coming for very low Gini coeficients with respect to pickup-dropof-based zones (leftmost plot). This is likely because vehicle-based methods require the fairness-aware vehicles to be in the right place in order to have an impact on fairness (e.g., in order for the requests coming from underserved zones to be feasible for these). Request-based methods have comparable performance, but having the additional parameter in -Req helps it achieve lower Gini coeficients than +Req.
Driver fairness: While fairness in the distribution of driver profits is not our primary focus, it is an important additional consideration in ridesharing. We thus consider how the proposed methods compare to NeurADP and FairNN in terms of the distribution of number of requests served (equivalent to income in our setting, as we assume identical costs per trip for all trips) by the drivers for the scenarios in Table 1.
Figure 4 shows the distribution of the trips each driver served in one day. Interestingly, NeurADP exhibits a relatively low variance in the number of requests served, particularly compared to FairNN that uses fairness of requests in the objective, perhaps suggesting a significant tradeof between achieving these two types of equity. What is particularly noteworthy is that our vehicle-based methods yield considerable unfairness in requests served among drivers – not only is variance high, but the distribution itself becomes bimodal. In contrast, our request-based methods exhibit variance comparable to NeurADP, suggesting that it may be possible to achieve high overall service rate, and both a high level of rider and driver fairness.
As the demand for cutting edge algorithms for urban mobility increases, their efect on the underlying fairness of these systems needs to be studied, and measures taken to ensure that our algorithms do not inherit the implicit biases that result from pure optimization. In this work, we discussed the issue of zonal fairness in ridesharing systems, introducing new fairness metrics for zone-pair fairness. Through four simple methods that build on existing solutions for order dispatching, we showed how simple techniques can be used to trade of eficiency for fairness. Our methods outperform existing approaches to zonal fairness via an online modification to state-of-art techniques in ridesharing, with the added advantage of not needing any extra training and the ability to be used with any VFA. The tradeofs proposed in this work can be dynamically adjusted to have increased fairness at minimal cost to eficiency. Our experiments showed that it is better to apply fairness incentives to a subset of the driver or request population for maximum results, as opposed to a blanket approach to fairness.
Our work leaves some interesting avenues open for future work: ∙ The generalizability of our approach needs to be evaluated. While it can theoretically be applied with any VFA, experiments are needed to verify that. Similarly, this approach needs to be tested with diferent sub-group fairness measures apart from zonal fairness. ∙ Our approach is limited by the need to find the right hyperparameter setting for a desired fairness level, but this problem is shared across other solutions for fairness. A potential solution to this problem may involve learning to adapt the hyperparameters to the current state of the world. Such an approach would automatically be able to tune the fairness based on the changes in demand and supply. ∙ It is of interest to prove theoretical bounds on the expected gains such an approach can provide, given a particular method to improve fairness. We provide general intuition on why we expect our approaches to work, and to explain the results we see. Future work may find mathematical guarantees that confirm our empirical results.