Paper Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms

Ride-hailing platforms increasingly broadcast trip requests to multiple drivers simultaneously — rather than notifying a single driver at a time — to reduce inefficiencies arising from uncertain driver acceptance. This study, the first in a two-part collaboration with Lyft, formally introduces the Notification Set Selection Problem: given an incoming ride request, how should a platform optimally choose which subset of drivers to notify within a single decision cycle? The problem is analyzed under two contention-resolution protocols. Under First Acceptance, the ride is assigned to whichever notified driver responds first, prioritizing speed. Under Best Acceptance, the platform waits and assigns the ride to the highest-valued accepting driver, prioritizing match quality. Welfare maximization is shown to be strongly NP-hard under both protocols, ruling out exact efficient solutions in general. Despite this computational hardness, the study establishes several positive algorithmic results. For First Acceptance, a polynomial-time approximation scheme is derived for the single-rider case, along with a constant-factor approximation for the general matching setting. The underlying valuation function is also shown to constitute a novel discrete choice model with independently interesting theoretical properties. For Best Acceptance, the objective is proven to be monotone and submodular, enabling a standard approximation guarantee; a purpose-built polynomial-time demand oracle is further shown to push performance beyond this baseline. In the special case of homogeneous acceptance probabilities, the Best Acceptance problem admits an exact polynomial-time solution via linear programming. Algorithm performance is validated through numerical experiments on both synthetic data and instances calibrated using real Lyft ride-sharing data.

Get the Paper