Unlike Gale-Shapley (everyone known upfront), here agents arrive over time and must be matched immediately. Explore the fundamental trade-off: match now (greedy) vs wait for a better match (patient).
No deterministic online algorithm can achieve more than 1 - 1/e ~ 0.632 of the offline optimal total utility (Karp, Vazirani, Vazirani, 1990). The BALANCE algorithm achieves this bound by assigning to the driver with the most remaining capacity, equalizing load across all drivers.
Real rideshare platforms (Uber, Lyft) and food delivery use sophisticated online matching enhanced with machine learning to predict future demand. The fundamental trade-off remains: match now (low latency, possibly suboptimal) vs wait for a better match (higher latency, potentially better global outcome).
In healthcare, organ transplant allocation (UNOS/OPTN) uses deadline-based matching where urgency and compatibility both factor into the online assignment decision.
Karp, R.M., Vazirani, U.V., & Vazirani, V.V. (1990). "An Optimal Algorithm for On-line Bipartite Matching." STOC 1990: 352-358.