Paper 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. 

Read the Paper