"The Broadcast Request"

When a rider requests a car, the platform can notify one driver and wait, or notify several and manage the contention.

Ekbatani, Niazadeh, and colleagues at Lyft (arXiv:2603.21533) formalize the Notification Set Selection Problem: given uncertain driver acceptance rates, how many drivers should receive each request, and which ones? Sending to one driver is simple but slow — if they decline, the platform starts over. Sending to many is fast but creates contention: multiple drivers might accept simultaneously, wasting the effort of all but one.

Two contention protocols emerge. First Acceptance takes whoever responds first — optimizing for speed at the cost of match quality. Best Acceptance waits briefly, then selects the best available pair — optimizing for quality at the cost of latency. The welfare-maximizing selection problem is NP-hard under both protocols.

For First Acceptance, a polynomial-time approximation scheme exists for single riders, and a 4-factor approximation handles the general matching setting. For Best Acceptance, the objective is monotone and submodular — a structure that immediately gives a (1 - 1/e) approximation via greedy algorithms. A custom oracle pushes past this bound. When acceptance probabilities are homogeneous (all drivers equally likely to accept), the problem collapses to a linear program — solvable exactly in polynomial time.

The structural insight: the platform's optimization problem is shaped by the contention protocol it chooses. First Acceptance and Best Acceptance produce different objective functions with different computational properties. The protocol isn't just a user experience decision — it determines whether the underlying optimization is tractable. The mechanism design is inseparable from the algorithm design.

Validation uses synthetic data and instances calibrated with actual Lyft data. The approximation algorithms perform close to optimal on realistic inputs, suggesting that the theoretical NP-hardness doesn't prevent practical deployment.