Quantifying Efficiency in Ridesharing Marketplaces
by Alex Chin and Tony Qin
The health of Lyft’s marketplace depends on how riders and drivers are distributed across space and time. Within the complex rideshare space, it is not easy to define typical marketplace concepts like “market efficiency” and “supply-demand balance”. A simple question such as “Do we have enough drivers right now?” has different answers depending on context:
- Are there enough drivers in the right places to maintain good service levels?
- Are there enough drivers system-wide, assuming a ride request will be accepted no matter how far away it is?
- Are there enough to maintain an attractive earning rate?
Each question leads in a different direction. Being able to answer such questions is the interesting (and challenging!) part of operating a healthy two-sided marketplace.
We must first develop diagnostics for measuring and monitoring the marketplace. Diagnostics come with their own big challenges. In this post, we’ll discuss how we addressed three major considerations:
- Abundance of metric options. There are many operational metrics, each with different pros, cons, and emphasis. Rider-side metrics include cancellation rates, expected-time-to-arrival (ETA), pickup times, and fulfillment rates. Driver-side metrics include driver hours (time spent on the platform), utilization (fraction of time spent with riders), and earnings. Platform metrics include ride volumes, incentive spend efficiency, and financial measures. Monitoring a dashboard of these metrics all at once is difficult even for skilled analysts, as it is hard to know where to focus. Furthermore, these metrics are noisy and subject to changing marketplace conditions and exogenous shocks such as traffic, weather, or airport delays.
- Lack of actionable output. Metric tracking does not automatically lead to the next best step. We have a varied toolbox of levers that can be used to improve marketplace health, including pricing, dispatch, and various incentive policies. How do we map from diagnostics to the optimal lever to pull?
- Mixed messages. A long list of noisy metrics often sends mixed messages, making it hard to grasp what is really happening at the core. In addition, these metrics are often heterogeneous in the unit of measurement, so making a quantitative trade-off among them is not straightforward.
Optimal transport
At the core of the Lyft platform is the matching algorithm that dispatches drivers to satisfy rider demand. By focusing on this core system, we are able to strip away a lot of the noise and complexity that comes from examining metrics further downstream. The profile of how riders and drivers are distributed across space and time determine how effective our dispatch system can be, and thus drive the efficiency of the marketplace.
Essentially, we want to quantify the distance between these two distributions. For simplicity, let us divide space and time into cellular units; for example, we could use geohashes, H3 cells, or S2 cells for space and 1-minute or 5-minute intervals for time. Let dᵢ and sᵢ be the rider and driver counts in cell i, respectively.
There are many ways to define distances between distributions, but our starting point will be the Wasserstein distance. First, define a non-negative valued transport function γ(i, j) and a cost function c(i, j). The Wasserstein distance is the minimum such total cost:
This is also known as the Earth mover’s distance, because it measures the amount of “work” needed to move the supply distribution to match the demand distribution or vice versa. We can see how it is solving an optimal transport problem because our aim is to perform the requisite amount of transport with as little work as possible. Here, “work” might not refer to physical work, but rather it incorporates any resource constraints that may apply to our system.
This is a good start, but there are still a number of shortcomings that make it ill-suited for our ridesharing setting. First, d and s may have different total measures, meaning there’s no feasible solution to the above optimization. In fact, it’d be surprising if we always have the exact same number of riders and drivers using Lyft at a given time. Second, Lyft works by dispatching drivers to travel to riders to pick them up and not vice versa. That is, we’d like our transport function to move drivers but not riders.
The graph-based equilibrium metrics (GEM) framework was proposed by Zhou et al. (2021) to rectify these shortcomings. The GEM computation is based on solving an asymmetric optimal transport problem that more closely resembles the rideshare dispatch process.
In this equation, γ is a matrix representing the transport plan; γ(i, j) is the amount of supply transported from cell i to cell j. c(i, j) captures the cost of transport, which could be encoded as distance or time to travel between cell i and cell j. The first term in the objective measures imbalance and the second term measures total cost; λ is a regularization parameter indicating how much we care about trading off between imbalance and cost. We have excluded some details for simplicity; the paper contains full detail.
From the solution to this optimization we can define some useful quantities. First, we define the local supply-demand (SD) gap:
As Zhou et al. (2021) propose, global diagnostic measures can be obtained by selecting a weight measure wᵢ and aggregating the local gaps:
In applying GEM as a diagnostic measure we found that the choice of weight has an outsized impact on the resulting conclusions. And, a single viewpoint is insufficient to answer our questions with precision. It cannot solely help us form a notion of marketplace efficiency in utilizing the supply for demand fulfillment because it is unable to represent any potential trade-off between the supply and demand-side states.
Motivated by these observations, we have developed SD-GEM, a two-sided framework that provides a comprehensive representation of rideshare market equilibrium states.
A two-sided view of the market
We can compute a demand-centric view and a supply-centric view of the marketplace by using the corresponding weights:
We’ll use a set of stylized dispatch examples to illustrate the two-sided views introduced above. The pink circles represent drivers, and the blue triangles represent requests. The entire region is divided into 4 cells. Drivers can be matched to only requests in their current or adjacent cells, not diagonal. Black arrows represent some non-obvious matches. The pairs of numbers around the grid represent the ratio of optimal dispatched supply to demand.
Figure (a) shows a globally balanced market. Both riders and drivers see the same balanced state. Figure (b) shows SD misalignment: riders see a generally under-supplied state, while drivers see a generally over-supplied state. The two views of GEM present SD indices of opposite signs. This indicates that some drivers are not at the right place (in space or time) to be matched to requests, and driver repositioning strategies are potentially of high value. Figure (c) shows a globally under-supplied market, where riders generally do not see enough drivers, and drivers generally have access to ample riders. Figure (d) shows the opposite case: a globally over-supplied market, where riders generally see plenty of available drivers whereas drivers generally do not see enough requests to fulfill an appropriate utilization level. The GEM dual view provides us with a low-dimensional representation of the marketplace, allowing us to take action without needing to manually parse the granular rider and driver states in the above figures.
City profiles
In order to turn the dual view into actionable insights, we find it helpful to plot a 2-D picture of the demand-centric and supply-centric indices at an aggregate level. For example, here is a scatterplot of the dual view where each dot represents a separate ridesharing market aggregated over many days of data, with the demand view on the x-axis and the supply view on the y-axis:
The best fit regression line is plotted in blue. It has a slope very close to positive 1, demonstrating that there’s generally a one-to-one tradeoff between supply and demand. By noticing where certain markets lie on this chart, we have an informative starting point for investigations into market health or particular market management actions.
More interesting patterns emerge when we zoom into individual markets and plot different times of day on the same chart. We see that the shapes of the point clouds are quite different, in which the unique road-network topologies and land zoning of each city play a role.
City 3 is an example of a dense urban area where streets have high connectivity, leading to high accessibility between supply and demand units. Thus, the supply and demand profiles match each other quite well. City 2 is elongated in geographical shape with a small number of arterial roads. Hence, the distribution of supply needs to be strategic to match well with the demand distribution. Accordingly, there tends to be more variability in the supply-centric index for any given value of demand-centric index due to the stochastic nature in the distributions of any incremental supply or demand units.
In general, points on the negative side of the demand index have smaller slopes than those on the positive side. An intuitive explanation is that when the demand index is negative, adding more supply into the market would more likely be absorbed by demand (i.e. additional supply is more likely to appear where supply is relatively low and demand is relatively high, possibly due to the effect of driver incentives). How flat or steep the slopes are depends on the topology of the city and effectiveness of particular demand/supply shaping strategies.
A queuing perspective
To better understand what the SD-GEM indices are exactly measuring, it helps to take a queuing theory perspective. At any given time, the request in-flow consists of new requests as well as open requests from the previous time window that are not yet matched. The request out-flow consists of matched and canceled requests. The driver in-flow consists of new drivers signing in, idle drivers from the previous time window, and drivers finishing a ride who are again available for new riders. The corresponding driver out-flow consists of matched drivers and drivers signing off.
For standard (non-shared) rides, matching is a one-to-one clearance mechanism in which riders and drivers exit the queue at the same rate. A balanced queue for a given cell means that there is little accumulation of demand or supply units from one dispatch cycle to the next. Any positive difference between the in-flow and out-flow will result in requests and/or drivers remaining in the queue for the next time window; the local SD gap is thus a snapshot of this expected accumulation.
At the system level, the story is complicated by the fact that there can be an accumulation of supply in some cells and demand in others. The SD-GEM indices introduced above are weighted aggregates of the cell-level accumulation conditions. The market-level system with a large number of cell-level queues has additional complexity due to endogeneity of the SD distributions — driver arrivals at a given time partially depend on the destinations of the requests from earlier time periods, so the demand patterns have an impact on the equilibrium of the queues. Understanding this phenomenon more completely is still an open question.
Marginal values
We can take advantage of duality in the GEM optimization problem to calculate the marginal values, or dual values, of the resource units (supply and demand). Marginal values are an important concept in economics and optimization theory, and indicate the value of an additional resource unit with respect to a particular objective function.
The demand duals provide convenient diagnostic analytics for demand shaping strategies to maintain a healthy market balance. A negative dual at a particular location and time, for example, means that demand could be increased because an incremental request would improve the GEM objective value. On the other hand, a positive dual means that the market balance may even improve with lower demand in the spatiotemporal zone. The left-hand plot in the figure above visualizes the demand duals distribution.
The supply duals, in turn, offer guiding analytics for supply positioning strategies because they indicate where drivers are needed the most and from where we may want to provide incentives for drivers to reposition themselves. The right-hand plot in the figure above visualizes the supply duals distribution. We see that it corresponds well to the inverse of the demand duals distribution, which makes sense — the areas where we need drivers the most are generally the areas that we may have too much demand. Where the demand marginal values are high, individual units of demand are contributing to inefficiency, and we should aim to reduce demand or increase supply in that location. Where the supply marginal values are high, we should aim to reduce supply or increase demand in that location. We can use this to diagnose whether our incentive and pricing systems are working as expected and to guide appropriate changes in policy.
Marketplace efficiency and policy evaluation
How can we use the GEM dual views to more precisely define a notion of marketplace efficiency? In a 2-D (Ad, As) plot, the origin represents the ideal efficient state. Any deviation from it leads to less efficient market health — drivers may idle more or riders may have to wait longer for their requests to be matched.
We can use the following picture to understand movements in this 2-D space. The pink line represents the unit-gradient hyperplane along which the market state will move due to a pure SD volume shift. The blue lines are the orthogonal complements representing SD distributional shifts conditional on the market volume.
Let’s take a specific case of supply influx. Assume that additional drivers appear in the market in such a way that the overall supply volume grows, but the shape of the supply distribution doesn’t change. It can be shown that both the supply- and demand- indices will increase by a constant α, represented by a movement R1 to R2 along the pink line. In contrast, a targeted intervention such as positioning incentives so that drivers are distributed more strategically and more aligned with the demand will lead to a movement R1 to R3, in the direction of the blue line.
We can refer to policy changes that move in the direction of the pink line as volume-targeting policies and those along the blue line as distribution-targeting policies. Which of these is better depends on the status quo state of the market. If we are currently in the second quadrant at R1 (SD misalignment), it is better to focus on aligning supply and demand (R3) rather than acquiring new supply or demand (R2). If we are currently in the first quadrant at R4 (over-supply), it is better to focus on global demand acquisition (R6) rather than alignment (R5).
Usage at Lyft
The SD-GEM framework has some major advantages over standard observational metrics:
- It has a unified scale of measurement for both supply- and demand-side effects, making it easier to analyze tradeoffs.
- It represents the market state in terms of equilibrium and efficiency simultaneously.
- It is a direct picture of what is happening at the dispatch/matching level, making it less subject to confounding and added variance.
Given its benefits, we have operationalized using SD-GEM statistics in a few impactful areas at Lyft. First, populating dashboards with these diagnostics help analysts monitor the health of the business. Second, we work with internal customers to ingest the SD-GEM statistics for use in ML and forecasting models, where they help improve predictive performance by providing granular market balance features. We also use SD-GEM for policy evaluation in A/B tests, especially when market efficiency is a priority and observational metrics do not provide a clear picture.
Developing a principled framework for marketplace efficiency and equilibrium has helped us chip away at some of the analytics challenges that we mentioned at the beginning of this post: an abundance of metric options, lack of actionable output, and mixed messages. We continue to find more use cases for this work across Lyft.
Acknowledgements
We would like to thank Ricky Chachra, Mark Huberty, John Kirn, Ido Bright, and Nicholas Chamandy for helpful discussions and suggestions.
If you’re interested in working with us on creating the world’s best transportation service through tackling challenging problems like marketplace efficiency, we’d love to hear from you! Visit www.lyft.com/careers to see our openings.
