Randomized FIFO Mechanisms

We study the matching of jobs to workers in a queue, e.g. a ridesharing platform dispatching drivers to pick up riders at an airport. Under FIFO dispatching, the heterogeneity in earnings from different trips incentivizes drivers to cherrypick, increasing riders' waiting times for a match, and resulting in a loss of efficiency and reliability. We first propose a direct FIFO mechanism, which offers lower-earning trips to drivers further down the queue, where the option to skip the rest of the line incentivizes the drivers to accept. We show that it is is a subgame perfect equilibrium for drivers to accept all dispatches, and the equilibrium outcome is envy-free and achieves the second best revenue and throughput. To achieve fairness in the sense that drivers closer to the head of the queue always have higher priority for trips to all destinations, we introduce a family of randomized FIFO mechanisms. A randomized FIFO mechanism gradually sends declined trips down the queue in a randomized manner, achieving the second best outcome in equilibrium at the cost of a small variance in driver payoffs which diminishes as riders' patience increases. Extensive counterfactual simulations using ridesharing data from the City of Chicago demonstrate substantial improvements of revenue and throughput in comparison to the status-quo FIFO dispatching.

Joint work with Francisco Castro, Hamid Nazerzadeh, and Chiwei Yan.