96 — Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources

Ride-sharing services like Lyft and Uber are — in tech-speak — bipartite matching markets. A finite demand resource (the ride requests) need to be optimally matched with the supply resource (the number of drivers on the road).

This matching process, unlike other “static” matching problems like assigning physicians to patients, or assigning academic papers to reviewers, is dynamic: The number of requesters and providers will likely change during the matching process.

It is important to understand that these problems, while “optimally solvable,” belong to the NP-hard set of problems; for a large number of match operations, these challenges are extremely time- and resource-intensive, and so it is generally smarter to have a cheap, “good enough” algorithm than an expensive and perfect one.

Dickerson et al take cues from another notoriously complex resource-matching problem: Online advertisement placement. There exists an edge in graph $G$ if a bidder bids value $u$ for a keyword $v$, where edges can be added (when new bids are placed) or removed (an advertiser wins the auction and is assigned the keyword).

One method of online matching is Online Matching with Known Identical Independent Distributions (OM-KIID), proposed first in the 90s. Certain resources, like drivers, are reusable (they can drive another person after their previous drive is complete). These are known as OM-Reusable Resource problems, where resources may go “offline” temporarily, but will return to the graph.

This paper presents OM-RR with Known Adversarial Distributions (OM-RR-KAD), the difference being that both sides of the matching challenge are reusable resources (riders will ride more than once, and drivers will drive more than once).

Though this increases the difficulty of the problem, the authors demonstrate that the method can be guaranteed to be mathematically bounded at certain limits of “idealness”, so you can fiddle with a parametric knob to balance algorithm run-cost and correctness of the answer.