Abstract: We investigate the problem of assigning trip requests to available vehicles in on-demand ridesourcing. Much of the literature has focused on maximizing the total value of served requests, achieving efficiency on the passengers’ side. However, such solutions may result in some drivers being assigned to insufficient or undesired trips, therefore losing fairness from the drivers’ perspective.
Introduction
Most ridesourcing algorithms (like those used by Uber or Lyft) are designed to be "utilitarian"—they aim to maximize total system efficiency, which usually means minimizing passenger wait times or maximizing the total value of all trips. While this is highly beneficial for passengers and the platform's bottom line, it often ignores the drivers' experience.
A purely efficiency-driven model can result in some drivers being consistently assigned "bad" trips (short, low-profit, or high-cruising-time requests), leading to frustration and high turnover. For a ridesourcing business to be sustainable, it must incorporate fairness—specifically "max-min fairness," which focuses on improving the situation for the worst-off drivers in the fleet. The challenge is that efficiency and fairness are often competing goals; increasing one usually decreases the other. This paper introduces a framework for balancing this inherent tension, proposing an efficient algorithm that allows platform operators to set a specific fairness threshold and significantly improve driver equity with negligible loss to overall system revenue.
Methodology
The authors model the assignment task as a weighted bipartite matching problem where a set of available vehicles is matched to a set of ride requests.
- Utility Definition: A driver’s utility is defined as the sum of their "trip utility" (profit minus cruising costs) and their "historical utility" (earnings accumulated in previous periods).
- The REASSIGN Algorithm: Instead of building a fair matching from scratch, the authors propose a "reassignment" approach. The algorithm takes an existing efficient assignment and a desired fairness threshold. It identifies "violating" drivers (those below the threshold) and performs a chain-swapping procedure, replacing their current trips with trips from a pre-calculated "fair" assignment until the threshold is met.
- Theoretical Bounds: The paper provides a mathematical proof establishing a guaranteed lower bound on efficiency for any given fairness target. They also prove this bound is "tight," meaning no other algorithm can guarantee a better tradeoff in the worst-case scenario.
Experimental Setup
The researchers evaluated their algorithm using the publicly available NYC taxi trip dataset from 2013. They focused on a representative 2-hour window (17:00–19:00) in Manhattan, processing between 31,694 and 56,743 requests per day. To estimate travel times accurately, they constructed a realistic road network of Manhattan with over 3,600 nodes and 7,600 edges. The tests covered both "single-batch" (matching everyone at once) and "multi-period" (matching in 30-second intervals) scenarios, as well as single-ride versus ridesharing (carpooling) modes.
Results and Insights
The "Price of Fairness" is Lower Than Expected: While the theoretical worst-case suggests a platform might have to sacrifice up to 33% of its efficiency to achieve perfect fairness, the experiments show that in real-world urban environments, the loss is usually less than 1%.
Massive Gains for the "Worst-Off": In single-batch tests, the utility of the least-favored driver improved by over 6-fold when moving from a purely efficient assignment to a fair one.
As shown in the figure above, the REASSIGN algorithm maintains near-optimal efficiency even as the fairness threshold approaches 1.0 (left panel), performing well above the theoretical lower bound. Simultaneously, the fair assignment drastically lifts the utility of the lowest-earning drivers (right panel) with only minor reductions for the top earners.
Additional Key Findings: * Chain Swapping is Powerful: The REASSIGN algorithm’s ability to "ripple" changes through the matching allows it to fix unfairness locally without disrupting the global efficiency of the entire network. * Time is a Natural Leveler: In multi-period settings, fairness is easier to achieve. Because the algorithm tracks historical utility, a driver who gets a "bad" trip in one 30-second window is much more likely to be prioritized for a "good" trip in the next, smoothing out inequality over the course of a shift. * Ridesharing Synergy: The algorithm works effectively even when vehicles carry multiple passengers, suggesting that fairness constraints don't break the complex logic required for carpooling.
Limitations and Future Work
While the results are promising, the paper focuses exclusively on fairness among drivers and does not address potential unfairness toward passengers (e.g., certain neighborhoods experiencing longer wait times). Furthermore, the model assumes a central platform has full control over assignments, which doesn't account for drivers who might "cherry-pick" or reject assignments in a decentralized way.
For future work, the authors suggest exploring a learning framework to dynamically adjust the fairness-efficiency tradeoff in real-time based on fluctuating supply and demand.
Summary updated