Dynamic Pricing and Matching for Two-Sided Queues

Sushil Mahavir Varma (), Pornpawee Bumpensanti (), Siva Theja Maguluri () and He Wang ()
Additional contact information
Sushil Mahavir Varma: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Pornpawee Bumpensanti: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Siva Theja Maguluri: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
He Wang: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Operations Research, 2023, vol. 71, issue 1, 83-100

Abstract: Motivated by applications from gig economy and online marketplaces, we study a two-sided queueing system under joint pricing and matching controls. The queueing system is modeled by a bipartite graph, where the vertices represent customer or server types and the edges represent compatible customer-server pairs. Both customers and servers sequentially arrive to the system and join separate queues according to their types. The arrival rates of different types depend on the prices set by the system operator and the expected waiting time. At any point in time, the system operator can choose certain customers to match with compatible servers. The objective is to maximize the long-run average profit for the system. We first propose a fluid approximation-based pricing and maximum-weight (max-weight) matching policy, which achieves an O ( η ) optimality rate when all the arrival rates are scaled by η . We further show that a two-price and max-weight matching policy achieves an improved O ( η 1 / 3 ) optimality rate. Under a broad class of pricing policies, we prove that any matching policy has an optimality rate that is lower bounded by Ω ( η 1 / 3 ) . Thus, the latter policy achieves the optimal rate with respect to η . We also demonstrate the advantage of max-weight matching with respect to the number of server and customer types n . Under a complete resource pooling condition, we show that max-weight matching achieves O ( n ) and O ( n 1 / 3 ) optimality rates for static and two-price policies, respectively, and the latter matches the lower bound Ω ( n 1 / 3 ) . In comparison, the randomized matching policy may have an Ω ( n ) optimality rate.

Keywords: Stochastic Models; queueing; dynamic pricing; max-weight matching; Markov decision process (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2233 (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:71:y:2023:i:1:p:83-100

Access Statistics for this article

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