Two-Stage Stochastic Matching and Pricing with Applications to Ride Hailing

Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem, with or without pricing, to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces, such as ride-hailing platforms. We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency and two-stage joint matching and pricing for maximizing market efficiency. In the former problem, using a randomized primal-dual algorithm applied to a family of “balancing” convex programs, we obtain the optimal 3/4 competitive ratio against the optimum off-line benchmark. Using a 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 design an optimal 1/2-competitive joint 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 objective using the correlation gap of submodular functions. Finally, we complement our theoretical study by using DiDi’s ride-sharing data set for Chengdu city and numerically evaluating the performance of our proposed algorithms in practical instances of this problem.