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

Yiding Feng (), Rad Niazadeh () and Amin Saberi ()
Additional contact information
Yiding Feng: Microsoft Research New England, Cambridge, Massachusetts 02142
Rad Niazadeh: University of Chicago Booth School of Business, Chicago, Illinois 60637
Amin Saberi: Management Science and Engineering, Stanford University, Stanford, California 94305

Operations Research, 2024, vol. 72, issue 4, 1574-1594

Abstract: 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.

Keywords: Optimization; two-stage matching; two-stage pricing; batching; ride hailing (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2398 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:4:p:1574-1594

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().