Two-stage Matching and Pricing with Applications to Ride Hailing

Matching and pricing are two critical levers in ride sharing marketplaces to match demand and supply. There, the platform can produce more efficient matching and pricing decisions by batching the requests. The goal of this paper is extending this batching paradigm to enable the platform to make such decisions in a batch with an eye toward the future. We therefore study the "two-stage stochastic matching problem", with or without pricing.We design online competitive algorithms for driver-weighted two-stage stochastic matching for maximizing supply efficiency, and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, by a primal-dual analysis, we show a family of convex-programming based matchings that distribute the demand in a balanced way among supply obtain the optimal 3/4-competitive ratio against the optimum offline benchmark. Using a novel factor revealing program and connections to submodular optimization, we improve this ratio against the optimum online benchmark to (1-1/e+1/e^2)=0.767 for the unweighted and 0.761 for the weighted case. In the latter problem, we show optimal 1/2-competitive pricing and matching algorithm by borrowing ideas from the ex-ante prophet inequality literature. We also show an improved (1-1/e)-competitive algorithm for the special case of demand efficiency using the correlation gap of submodular functions