Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914426311933952 |
|---|---|
| author | Ekbatani, Farbod Niazadeh, Rad Golari, Mehdi Camilleri, Romain Jehl, Titouan Sholley, Chris Leventi, Matthew Calderon, Theresa Lam, Angela Duclos, Paul Havard Holland, Tim Koch, James Reddy, Shreya |
| author_facet | Ekbatani, Farbod Niazadeh, Rad Golari, Mehdi Camilleri, Romain Jehl, Titouan Sholley, Chris Leventi, Matthew Calderon, Theresa Lam, Angela Duclos, Paul Havard Holland, Tim Koch, James Reddy, Shreya |
| contents | Ride-hailing platforms increasingly rely on non-exclusive notifications-broadcasting a single request to multiple drivers simultaneously-to mitigate inefficiencies caused by uncertain driver acceptance. In this paper, the first in a two-part collaboration with Lyft, we formally model the 'Notification Set Selection Problem' for a single decision cycle, where the platform determines the optimal subset of drivers to notify for each incoming ride request. We analyze this combinatorial optimization problem under two contention-resolution protocols: 'First Acceptance (FA)', which prioritizes speed by assigning the ride to the first responder, and 'Best Acceptance (BA)', which prioritizes match quality by selecting the highest-valued accepting driver.
We show that welfare maximization under both mechanisms is strongly NP-hard, ruling out a Fully Polynomial Time Approximation Scheme (FPTAS). Despite this, we derive several positive algorithmic results. For FA, we present a Polynomial Time Approximation Scheme (PTAS) for the single-rider case and a constant-factor approximation (factor 4) for the general matching setting. We highlight that the FA valuation function can be viewed as a novel discrete choice model with theoretical properties of independent interest. For BA, we prove that the objective is monotone and submodular, admitting a standard $(1 - 1/e)$-approximation. Moreover, using a polynomial-time demand oracle that we design for this problem, we show it is possible to surpass the $(1 - 1/e)$ barrier. Finally, in the special case of homogeneous acceptance probabilities, we show that the BA problem can be solved exactly in polynomial time via a linear programming formulation. We validate the empirical performance our algorithms through numerical experiments on synthetic data and on instances calibrated using real ride-sharing data from Lyft. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_21533 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms Ekbatani, Farbod Niazadeh, Rad Golari, Mehdi Camilleri, Romain Jehl, Titouan Sholley, Chris Leventi, Matthew Calderon, Theresa Lam, Angela Duclos, Paul Havard Holland, Tim Koch, James Reddy, Shreya Data Structures and Algorithms Discrete Mathematics Computer Science and Game Theory Ride-hailing platforms increasingly rely on non-exclusive notifications-broadcasting a single request to multiple drivers simultaneously-to mitigate inefficiencies caused by uncertain driver acceptance. In this paper, the first in a two-part collaboration with Lyft, we formally model the 'Notification Set Selection Problem' for a single decision cycle, where the platform determines the optimal subset of drivers to notify for each incoming ride request. We analyze this combinatorial optimization problem under two contention-resolution protocols: 'First Acceptance (FA)', which prioritizes speed by assigning the ride to the first responder, and 'Best Acceptance (BA)', which prioritizes match quality by selecting the highest-valued accepting driver. We show that welfare maximization under both mechanisms is strongly NP-hard, ruling out a Fully Polynomial Time Approximation Scheme (FPTAS). Despite this, we derive several positive algorithmic results. For FA, we present a Polynomial Time Approximation Scheme (PTAS) for the single-rider case and a constant-factor approximation (factor 4) for the general matching setting. We highlight that the FA valuation function can be viewed as a novel discrete choice model with theoretical properties of independent interest. For BA, we prove that the objective is monotone and submodular, admitting a standard $(1 - 1/e)$-approximation. Moreover, using a polynomial-time demand oracle that we design for this problem, we show it is possible to surpass the $(1 - 1/e)$ barrier. Finally, in the special case of homogeneous acceptance probabilities, we show that the BA problem can be solved exactly in polynomial time via a linear programming formulation. We validate the empirical performance our algorithms through numerical experiments on synthetic data and on instances calibrated using real ride-sharing data from Lyft. |
| title | Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms |
| topic | Data Structures and Algorithms Discrete Mathematics Computer Science and Game Theory |
| url | https://arxiv.org/abs/2603.21533 |