Learning-Based Pricing and Matching for Two-Sided Queues

We consider a dynamic system with multiple types of customers and servers. Each type of waiting customer or server joins a separate queue, forming a bipartite graph with customer-side queues and server-side queues. The platform can match the servers and customers and then the matched pairs leave the system. The platform will charge a customer a price according to their type when they arrive and will pay a server a price according to their type. The arrival rate of each queue is determined by the price according to some unknown demand or supply functions. Our goal is to design pricing and matching algorithms to maximize the profit of the platform with unknown demand and supply functions while keeping queue lengths of both customers and servers below a predetermined threshold. The difficulties of the problem include simultaneous learning and decision making and the tradeoff between maximizing profit and minimizing queue length. We use a longest-queue-first matching algorithm and propose a learning-based pricing algorithm, which combines gradient-free stochastic projected gradient ascent with bisection search. We prove that our proposed algorithm yields a sublinear regret [Formula: see text] and queue-length bound [Formula: see text], where T is the time horizon. We further establish a tradeoff between the regret bound and the queue-length bound. Funding: This research was supported in part by the National Science Foundation [Grants 2112471, 2207548, 2228974, and 2240981]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/stsy.2024.0073 .