Dynamic Pricing and Matching for Two-Sided Queues

• 成果类型: Article
• 署名作者: Varma, Sushil Mahavir; Bumpensanti, Pornpawee; Maguluri, Siva Theja; Wang, He
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2233
• 发表日期: 2023
• 页码: 83-100
• 关键词: queueing; Dynamic pricing; max-weight matching; Markov Decision Process

摘要

Motivated by applications from gig economy and online marketplaces, we study a two-sided queueing system under joint pricing and matching controls. The queueing systemismodeled 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( root eta) optimality rate when all the arrival rates are scaled by eta. We further show that a two-price and maxweight matching policy achieves an improved O(eta(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 Omega(eta(1/3)). Thus, the latter policy achieves the optimal rate with respect to eta. 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( root eta) and O(n(1/3)) optimality rates for static and two-price policies, respectively, and the latter matches the lower bound Omega(n(1/3)). In comparison, the randomizedmatching policymay have an Omega(n) optimality rate.