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

• 成果类型: Article
• 署名作者: Feng, Yiding; Niazadeh, Rad; Saberi, Amin
• 署名单位: Microsoft; University of Chicago; Stanford University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2398
• 发表日期: 2024
• 页码: 1574-1594
• 关键词: Approximation; algorithms; threshold

摘要

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/e2) approximate to 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.