Dynamic Pricing and Matching for Two-Sided Queues

DOI10.1287/OPRE.2021.2233MaRDI QIDQ6202661zbMATH OpenOpenAlexFDO

Authors Sushil Mahavir Varma, Siva Theja Maguluri, He Wang

Publication date 26 February 2024

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.02213

zbMATH Keywords

dynamic pricingMarkov decision processmax-weight matchingqueueingstochastic models

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Markov and semi-Markov decision processes (90C40) Microeconomic theory (price theory and economic markets) (91B24)

Abstract: Motivated by diverse applications in sharing economy and online marketplaces, we consider optimal pricing and matching control in a two-sided queueing system. We assume that heterogeneous customers and servers arrive to the system with price-dependent arrival rates. The compatibility between servers and customers is specified by a bipartite graph. Once a pair of customer and server are matched, they depart from the system instantaneously. The objective is to maximize long-run average profits of the system while minimizing average waiting time. We first propose a static pricing and max-weight matching policy, which achieves $O(sqrteta)$ optimality rate when all of the arrival rates are scaled by $eta$. We further show that a dynamic pricing and modified max-weight matching policy achieves an improved $O(et{a}^{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(et{a}^{1/3})$. Thus, the dynamic pricing policy and modified max-weight matching policy achieves the optimal rate. In addition, we propose a constraint generation algorithm that solves an approximation of the MDP and demonstrate strong numerical performance of this algorithm.

Recommendations

• Two-stage stochastic matching and pricing with applications to ride hailing
• On the optimal design of a bipartite matching queueing system
• Quick or cheap? Breaking points in dynamic markets
• Ergodic control of bipartite matching queues with class change and matching failure

Cited in

(4)

• The strategic analysis of service mode selection for a ride-hailing platform
• Quick or cheap? Breaking points in dynamic markets
• Two-stage stochastic matching and pricing with applications to ride hailing
• Fluid models of bilateral matching queues with time-varying arrivals

This page was built for publication: Dynamic Pricing and Matching for Two-Sided Queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202661)