Data-Driven Methods for Balancing Fairness and Efficiency in Ride-Pooling

1 Introduction

Ride-pooling platforms, such as UberPool and Lyft-Line, manage independent drivers who can service multiple riders concurrently. To match riders and drivers, they use artificial-intelligence-based matching algorithms [Turakhia, 2017]. While matching algorithms typically aim to maximize income, they can inadvertently have negative consequences on fairness, such as a gender wage gap [Cook et al., 2018] or rider discrimination based on race [Brown, 2018].

While the nascent literature on fairness in ride-pooling is limited, prior research has looked at maximizing the minimum utility across riders and drivers by approximating the problem as an instance of the bipartite matching problem [Lesmana et al., 2019]. There have also been past papers that have looked into the sub-problem of fairness in rideshare, where drivers can only service one rider request at a time (such as UberX), which simplifies the matching problem. Past work has used a bipartite matching problem framework to prove bounds on the trade-off between fairness and income [Nanda et al., 2020; Xu and Xu, 2020]. Additionally, past research into rideshare fairness has considered equalizing utility across riders and drivers [S¨uhr et al., 2019].

Recent work into the ride-pooling matching problem showed that using a Markov decision process (MDP) based approach, in combination with deep learning, maximizes the number of rider requests serviced because it makes nonmyopic decisions [Shah et al., 2020]. We build on prior ride-pooling work [Lesmana et al., 2019; Shah et al., 2020] to develop a simple yet robust method to improve fairness non-myopically, which can be generalized to different notions of fairness. Motivated by reports of wage inequality and rider discrimination [Brown, 2018; Cook et al., 2018; Moody et al., 2019], we develop two methods to reduce certain definitions of inequality within the MDP framework: (1) modifying the objective function of the MDP and (2) creating an income redistribution method. 1 Our contributions are the following:

1. We extend an MDP-based framework to non-myopically optimize for different definitions of fairness.
2. We propose new objective functions that aim to maintain profitability while minimizing inequality on the driver and rider-sides, and evaluate their effect on inequality. We show that certain objective functions can reduce inequality while maintaining or even improving profitability.
3. We implement an income redistribution scheme, where each driver contributes a certain percentage of income earned, which is then redistributed to other drivers to offset income fluctuation and reduce wage inequality. We show that, under certain levels of risk tolerance, we can use income redistribution to significantly reduce wage inequality while avoiding the free-rider problem. Additionally, we prove that our income redistribution scheme guarantees drivers a minimum wage.

We find that varying the objective function can positively impact rider-side fairness, and utilizing income redistribution can improve driver-side fairness. When used together, these methods can improve both rider and driver-side fairness, and could potentially be used not only for ride-pooling, but also for other matching and resource allocation problems.

1 Our code and data is publicly available at https://github.com/ naveenr414/ijcai-rideshare

2 RelatedWork

The complexity of the ride-pooling matching problem led to the need for algorithmic solutions. One attempt to solve the problem reduces it to a version of the bipartite matching [Zhao et al., 2019]. Other papers model this problem as an MDP which takes into account future consequences of matching [Lin et al., 2018; Li et al., 2019]. Our work builds on previous work that uses offline-online learning and approximate dynamic programming to match drivers and riders non-myopically [Shah et al., 2020].

While these algorithmic solutions serve more customers than traditional taxi services [Uber, 2015], recent literature has raised questions about the fairness of the matches generated by these algorithms. On the rider side, Brown et al. [Brown, 2018] highlight the disparate treatment of riders by ride-pooling companies, which results in higher rates of trip cancellation for black riders. Similarly, on the driver side, some ride-pooling drivers cannot achieve a living wage due to income inequality [Graham, 2017].

One approach to dealing with these issues is to reformulate the problem using bipartite matching and utilize a minmax objective function to maximize the minimum utility for drivers and riders [Lesmana et al., 2019]. Within the subproblem of rideshare matching, which is simpler because drivers cannot concurrently service multiple riders, past work has proven bounds on the trade-off between fairness and efficiency for a specific notion of fairness [Nanda et al., 2020; Xu and Xu, 2020; Ma and Xu, 2020]. Past empirical research has looked into equalizing utility across drivers and riders [S¨uhr et al., 2019], and improving the fairness of rideshare demand functions [Yan and Howe, 2020].

Our work builds on past ride-pooling work [Shah et al., 2020; Lesmana et al., 2019] to develop a general method that can be adapted for many definitions of fairness, while also matching non-myopically by using an MDP. We are the first study to look at fairness in MDP-based matching for ridepooling or rideshare, and so our work applies to the broader class of non-bipartite matching problems. Additionally, we use income redistribution to reduce income fluctuation and inequality without affecting profitability, which has not been explored in previous work.

3 Problem Statement

In this section, we formally describe our problem, methodology, and evaluation strategy.

3.1 ProblemDescription

We consider the problem of matching a stream of rider requests to one of n drivers. All riders and drivers reside on a graph, which consists of locations, L, and edges, E, where Ei,j represents the travel time in minutes between location i ∈ L and location j ∈ L. A trip between location i and location j is priced at Ei,j + δ, where δ is a constant, capturing both the fixed and variable costs inherent in ride-pooling pricing. Although the stream of rider requests is continuous, we batch requests and match once a minute, which emulates what ride-pooling companies perform in reality [Uber, 2020]. We define rider requests and driver states as follows:

1. We define a rider request, which refers to a rider requesting a ride, to be the tuple ui = (gi, ei, ti). In the tuple, gi, ei ∈ L are the starting and ending location for the rider request, and ti is the time when the rider request originated.
2. We define the state of each of the n drivers as ri = (mi, ci, di, pi, si), where mi is the capacity of driver i, and ci is the number of riders currently driven by driver i. di ∈ L is the location of the driver, pi is the set of current requests that driver i is servicing, and si is the set of previously completed requests, making |pi|+|si| the total number of requests that will be serviced by driver i.

3.2 Matching Riders and Drivers

We describe how we match m rider requests, U = u1 · · · um, with n drivers, R = r1 · · · rn, using an MDP framework. Because each driver can be matched to multiple riders, we reduce the number of rider-driver combinations by generating feasible matchings for each driver. We let F i represent all feasible matchings for driver i, where each matching, f ∈ F i is a set of requests that can be served simultaneously by driver i [Alonso-Mora et al., 2017]. We let ai,f denote an indicator value, determining whether the set of requests f is matched to driver i. Each driver is matched to one f ∈ F i , which could be the empty set, where the driver gets no new rider requests.

The problem reduces to selecting feasible matchings that maximize an objective function, subject to constraints, which we solve through an integer linear program. Let the objective function be o(R,W), which measures the benefit of having the drivers be in the state R, where W is the set of all previous unaccepted and accepted requests. If, after accepting a matching f ∈ F i , the approximate new state of the drivers is R′ , then the change in objective function is

We approximate the post-acceptance state, R′ , from prior work [Shah et al., 2020]. To avoid matching myopically, we compute the value function, V (R′ ) for the state of drivers after matching. We approximate the value function through deep learning following past work, where the value function is an approximation of the objective function, o(R,W), over a future state, R′ , essentially stating the value of a driver residing in a state R′ [Shah et al., 2020]. To perform deep learning, we utilize a neural network that takes as inputs, the locations of the drivers and their current path, and uses that to learn the value function. The details of training, network structure, and configuring the deep network can be found in our code, and prior work [Shah et al., 2020]. We then weight each feasible matching as ∆o(R, W, f ) + γV (R′ ), where the discount factor γ = 0.9. Our aim is to maximize:

While o could be non-linear, we pre-compute ∆o(R, W, f ) to avoid non-linearities. We use (2) as the objective function in an integer linear program subject to the following constraints:

1. Driver-side feasibility. One assigned action per vehicle: ∀i, ∑f∈F i ai,f = 1.
2. Rider-side feasibility. At most one assigned action per request: ∀j, ∑Ni=1 ∑f∈F i ,uj∈f ai,f ≤ 1.

Through the integer linear program (ILP), we compute ai,f , which determines which feasible matchings are selected. The ILP is run online using an offline-trained value function.

3.3 Evaluation Strategy

To evaluate our methods, we utilize the New York City taxi data set [New York City, 2016], a commonly used dataset [Lesmana et al., 2019; Shah et al., 2020; AlonsoMora et al., 2017] which contains pickup and drop-off locations and times for taxi passengers fromMarch 23rd to April 1st and from April 4th to April 8th, 2016. Data from ridepooling companies are generally proprietary, so we use taxi data to simulate ride-pooling under the assumption that the spatial and temporal distribution of rider requests are similar. The pickup and drop-off location for each rider request is reported in longitude-latitude coordinates; we discretize these into |L| locations in New York City and compute travel time and paths between each pair of locations. The driver locations are initially randomized, but remain consistent between experiments and trials. The data from both experiments (Sections 4 and 5) are available online. 2

4 Fairness-based Objective Functions

We develop fairness based objective functions to improve both driver-side and rider-side fairness. In Section 4.1, we discuss profitability metrics that prior work has optimized for. In Sections 4.2 and 4.3, we define our notions of driver and rider-side fairness, and then operationalize each of these by developing two objective functions. In Section 4.4 we discuss how we test each objective function, and in Sections 4.5 and 4.6, we discuss the results after running the experiments.

4.1 ProfitabilityMetrics

We develop two different measures of profitability: the number of riders serviced and the total income accumulated by drivers. To define these two metrics, if the driver states are R = r1 · · · rn, where ri = (mi, ci, di, pi, si), then the total number of rides serviced by driver i is |pi|+|si|, which represents ongoing requests (pi), and completed requests (si). We develop an objective function based on the total number of rider requests serviced by all drivers:

Similarly, the income for any request u = (g, e, t) is Eg,e+δ. So, if we let πi denote the income for driver i, where

2 https://www.dropbox.com/s/y9pkmzmbjclrfrx/testdata.zip?dl=0

then our income objective function is the total income:

The state-of-the-art method [Shah et al., 2020] matches based on maximizing the number of requests.

4.2 Rider-Side Fairness Metrics

We define fairness for both drivers and riders. We note that, as with all operationalizations of societally-relevant concepts such as fairness, the decision of which definition of fairness to use-if one is appropriate to use at all-is morallyladen, and one that should be made with the explicit input of stakeholders. Our definitions are drawn in part from recent reports of (primarily rider-side) unfairness in fielded ridepooling applications [Dillahunt et al., 2017; Brown, 2018; Pandey and Caliskan, 2020]; still, we acknowledge that these need not be one-size-fits-all formalizations of a complicated concept, and view them rather as illustrative examples of a class of fairness definitions that could be incorporated into automated matching algorithms used by ride-pooling platforms.

We base our conception of rider-side fairness on the differential treatment of riders based on membership in a protected group, such as race [Brown, 2018]. Because we lack access to any protected information in our data set, we instead measure fairness based on the distribution of neighborhoods serviced, though the method could be applied to any protected group.

We define a neighborhood as a set of locations in L, and so for any l ∈ L, we define the neighborhood function, 1 ≤ N(l) ≤ H, as the function which maps locations to neighborhood labels. The neighborhood function is constructed through the k-means algorithm, which divides the |L| locations into H neighborhoods based on their latitude and longitude. To determine the distribution of neighborhoods serviced, we define hj as the number of requests serviced starting in neighborhood j, where hj is

The total number of requests, serviced or non-serviced, originating from neighborhood j is kj ≥ hj defined as

Our aim is to equalize treatment across neighborhoods, and so we aim to equalize the percent of requests serviced, hj kj , which we call the success rate. To avoid making all success rates 0, we include a profitability term, and regulate the size of the two terms with a hyperparameter λ. This makes our objective function for rider-side fairness:

where Var is the variance function. We develop two metrics of rider-side fairness which capture the spread and scale of disparate treatment: min( hj kj ) and Var( hj kj ) respectively.

4.3 Driver-Side Fairness Metrics

We develop corresponding objective functions and metrics on the driver-side. Recent news has noted wage discrepancies among drivers [Graham, 2017; Bok´anyi and Hann´ak, 2020], so we aim to reduce income disparity. Similar to the riderside, our objective function minimizes the spread of income while maintaining profitability, which is represented as

We measure the scale and spread of driver-side inequality through two metrics. The first measures the scale of income disparity by calculating the minimum income for any driver, which is min(πi), and the second captures the spread using the variance function, which is Var(πi)

4.4 Experiment Setup

We compare the four objective functions, which we call request, income, rider-side fairness, and driver-side fairness. We utilize each objective function with the matching algorithm, train the corresponding value function, and test each objective function on data from April 4th. The details of hyperparameters and value function training are in Appendix B.

4.5 Experiment Results

We run experiments comparing the different objective functions on both profitability and fairness metrics. We describe the major conclusions from our experiments below:

1. Alignment of fairness and profitability metrics. We find that certain fairness metrics are aligned with profitability metrics. In particular, objective functions that improve the overall success rate for riders also improve the success rate in the worst-off neighborhood (Figure 1). Similarly, the objective function which maximizes total income at 200 drivers, the request objective function, also maximizes income for those earning lower wages. However, efforts to decrease the spread of income do not result in higher wages for those at the bottom, and instead lower wages across the board (Figure 2).
2. Driver-side fairness objective functions improve riderside metrics. We find that using an objective function that maximizes driver-side fairness manages to reduce the spread of income and also positively impacts rider-side inequality and profitability. In particular, at 50 drivers, optimizing for driver-side fairness improves the overall success rate and the success rate in the worst-off neighborhood, but at 200 drivers, the state-of-the-art objective function, which optimizes for the number of requests, maximizes both rider-side fairness and profitability metrics. This is probably because, when optimizing for driver-side fairness, drivers tend to service lower value and shorter-distance rides to reduce the spread of income, allowing for more rides to get serviced. However, when there are too many drivers, there are not sufficient shortdistance requests.
3. Inability to raise wages for lowest wage earners. While objective functions that maximize driver-side fairness reduce the spread of income, they do so at a cost to profitability by lowering income across the board. This is a general problem, as no objective function was able to raise wages for the lowest-earning drivers when compared to the state-of-the-art objective function.

4.6 Discussion

Our experiments show that, by changing the objective function used in matching, it is possible to improve rider-side metrics. Additionally, we find that certain fairness metrics, such as the success rate (fraction of requests serviced) in the worst-off neighborhood, are aligned with profitability metrics. On the other hand, metrics that measure spread, such as the spread of income, are not aligned with profitability metrics. To tackle this issue, we introduce an income redistribution method (section 5) which tackles driver-side inequality without affecting profitability. The results from these experiments can be incorporated into other matching algorithms to improve fairness. Additionally, our methods can be extended to other definitions of fairness by varying the objective function, and so are robust to different definitions of fairness.

5 Income Redistribution

To reduce the spread and fluctuation of income, we propose an income redistribution method, where each driver takes home a certain percentage of their income, and the rest is redistributed at the end of each day. In Section 5.1, we formalize our income redistribution model, and we describe properties of the model in Section 5.2. In Section 5.3, we outline experiments to test out income redistribution method, and we detail the results in Section 5.4.

5.1 Model of Income Redistribution

Driver wages fluctuate day to day due to varying demand, making it difficult for drivers to earn a reliable wage. To counter this and reduce income inequality, we design an income redistribution scheme. To do this, we define the amount that drivers make before redistribution as πi, 1 ≤ i ≤ n, and the amount they make after redistribution as qi, which is dependent on the risk tolerance, r.

More valuable drivers should have a higher qi, as they might work longer hours or service higher need areas. To generate an objective measure of the value of a driver, we utilize a metric from game theory known as the Shapley value [Shapley, 1953], which measures the marginal contribution of an agent. The Shapley value helps assess the true contributions of each driver, and was previously used to determine the value of data points [Jia et al., 2019] and decide how much ridepooling riders should pay [Amano et al., 2020]. In our context, we can formally define the Shapley value, vi, as the marginal contribution of driver i to each subset of drivers; that is, if we let D = {1, 2, . . . , n}, and π(s) be the income that a subset s ∈ D would have made under the matching algorithm, for just those s drivers. Then

To compute the Shapley value of driver 1, consider the 4 subsets excluding driver 1: {}, {2}, {3}, {2,3}, which make 0, 10, 5, and 15 respectively. When adding driver 1 to each of these subsets, the total income increases by 10, 5, 10, and

0 respectively. We then average over these subsets, proportional to the number of permutations for each subset, to get

which is the Shapley value of the driver.

Due to Shapley value properties, ∑ni=1 vi = ∑ni=1 πi, or total value equals total income.

Calculating the Shapley value requires enumerating all O(2n ) subsets of drivers. To reduce this, we approximate vi in O(n) evaluations through a Monte Carlo simulation [Ghorbani and Zou, 2019]. Using the Shapley value of a driver, we redistribute income to reduce the difference between a driver's pre-redistribution income, πi, and their value, vi. The redistribution amount depends on a risk parameter, 0 ≤ r ≤ 1, which designates what fraction of their income is kept by drivers. We collect ∑ni=1 (1 - r)πi from all drivers, and redistribute it proportional to the difference between their value and earnings, which is max(0, vi -rπi). After redistribution, each driver earns qi, defined by

This essentially allows drivers to keep some income, and redistributes the rest proportional to the difference between earnings and value, which allows drivers who earned less than their value to recoup some of their losses.

5.2 Redistribution Properties

Our approach to income redistribution begets two attractive theoretical properties.

Theorem 5.1. When πi, ∑nj=1 πj, and r are constant, qi is maximized when vi is maximized.

Theorem 5.2. For a given vi, r, and fixed ∑nj=1 πj , the minimum value of qi is min(rvi, (1 - r)vi).

Theorem 5.1 incentivizes drivers to maximize their value, meaning that drivers are not better off putting in less effort under income redistribution. Theorem 5.2 gives a guarantee on the minimum amount that drivers can make, which is helpful in light of the recent debates over minimumwage for ride-pooling drivers [Keeton, 2016].

5.3 Experiments

To test the effect of income redistribution, we vary the risk parameter and determine its effect on the income distribution. We run experiments using a variety of objective functions and number of drivers, though we focus on 200 drivers with the requests objective function when describing results. While we previously proved that drivers will aim to maximize vi, making vi positively correlated with qi, we did not specify the magnitude of this correlation. To quantify the correlation, we define the gain metric, gi, as the ratio of change in qi to vi when vi is doubled. Because higher vi leads to higher qi, we know gi ≥ 0, and ideally, if vi for a driver is doubled, then so would qi, meaning gi = 1. We calculate g = 1n ∑ni=1 gi as the average gain metric over all drivers.

To determine the fairness of the income redistribution algorithm, we look at the distribution of the ratio of vi to qi. Ideally, each driver would earn their value, and so the spread of the distribution would be 0. However, as risk tolerance increases, less money will be redistributed, and so the spread will increase. To quantify this, we compute qi vi for all i, and then compute the standard deviation.

5.4 Experiment Results

We outline some of the findings from our experiments:

1. Ability to fairly redistribute. We find that, for 0.5 ≤ r ≤ 0.9, we can keep the gain larger than 0, while keeping the spread of income to value ratio near 0 (Figure 3). In practice, this means when r = 0.9, which corresponds to g = 0.8, drivers receive, on average, an 80% raise in income if they doubled their value. At the same time, the standard deviation of qi vi is low, and so most drivers earn close to their value. This allows for an equitable distribution of income while avoiding the free-rider problem,
2. where income is spread out despite all the value being concentrated in one driver.
3. Tightness of Theoretical Bounds. While the bounds in section 5.2 give results on the minimum amount that drivers are guaranteed to make, in reality, the worst-off drivers end up making significantly more than that. For all values of r, the worst-off driver made at least $2500, while the theoretical bounds peaked at $1500. The bounds assume the worst-case situation where one driver gets all the pre-redistribution income, however in practice, this rarely occurs, and so the bounds are not tight.

6 Conclusions &Future Research

With an increasing ubiquity of ride-pooling services comes the need to critically evaluate fairness for both sides of the market - riders and drivers alike. By modifying state-ofthe-art ride-pooling matching algorithms, we explored objective functions that increase the number of requests serviced for certain numbers of drivers, and also increased fairness across groups. We additionally proposed addressing income inequality by using income redistribution to allocate income and alleviate fluctuation in income between drivers. By using income redistribution, we found that it is possible to avoid free-riding while keeping income inequality low.

We discuss three potential avenues for future work:

1. By evaluating methods on other data sets, we can test the generalizability of our methods and determine the circumstances under which the methods perform optimally.
2. By developing provable guarantees for objective functions, we increase the robustness of our objective functions and guarantee that these objective functions work under different circumstances.
3. By exploring income redistribution in other resource allocation settings, we can tackle the fairness versus profitability trade-off for other problems.

Acknowledgements

NSF CAREER IIS-1846237, NIST MSE #20126334, DARPA #HR00112020007, DARPA #S4761, and DoD WHS #HQ003420F0035.

Ethical Impact

We address a specific application of the classic fairnessefficiency trade-off found in numerous economic systems. While we did derive our proposed definitions of fairness from reports of inequality in ride-pooling systems [Dillahunt et al., 2017; Brown, 2018; Pandey and Caliskan, 2020], we acknowledge that may not be the proper solution for all settings where ride-pooling is deployed. Indeed, measuring, defining, and incorporating definitions of fairness into automated systems is an area of extremely active research within the FATE community. We confidently make the prescriptive statement that considerations of fairness at both the driver and rider level should be taken into account in some way in ride-pooling platforms. However, open dialogue with stakeholders-e.g., local governments, riders and drivers hailing from various backgrounds-is imperative to understanding the desires of those stakeholders.