We study dynamic matching in a spatial setting. Drivers are distributed at random on some interval. Riders arrive in some (possibly adversarial) order at randomly drawn points. The platform observes the location of the drivers, and can match newly arrived riders immediately, or can wait for more riders to arrive. Unmatched riders incur a waiting cost $c$ per period. The platform can match riders and drivers, irrevocably. The cost of matching a driver to a rider is equal to the distance between them. We quantify the value of slightly increasing supply. We prove that when there are $(1+epsilon)$ drivers per rider (for any $epsilon > 0$), the cost of matching returned by a simple greedy algorithm which pairs each arriving rider to the closest available driver is $O(log^3(n))$, where $n$ is the number of riders. On the other hand, with equal number of drivers and riders, even the emph{ex post} optimal matching does not have a cost less than $Theta(sqrt{n})$. Our results shed light on the important role of (small) excess supply in spatial matching markets.
Download