Optimal Queue Design
We study the optimal method for rationing scarce resources through a queue system. The designer controls agents' entry into a queue and their exit, their service priority -- or queueing discipline -- as well as their information about queue priorities, while providing them with the incentive to join the queue and, importantly, to stay in the queue, when recommended by the designer. Under a mild condition, the optimal mechanism induces agents to enter up to a certain queue length and never removes any agents from the queue; serves them according to a first-come-first-served (FCFS) rule; and provides them with no information throughout the process beyond the recommendations they receive. FCFS is also necessary for optimality in a rich domain. We identify a novel role for queueing disciplines in regulating agents' beliefs and their dynamic incentives and uncover a hitherto unrecognized virtue of FCFS in this regard.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets
We study a two-sided market, wherein, price-sensitive heterogeneous customers and servers arrive and join their respective queues. A compatible customer-server pair can then be matched by the platform, at which point, th…
Design and Scheduling of an AI-based Queueing System
To leverage prediction models to make optimal scheduling decisions in service systems, we must understand how predictive errors impact congestion due to externalities on the delay of other jobs. Motivated by applications…
Model SelectionPredictionSchedulingOptimal Auction Design for Dynamic Stochastic Environments: Myerson Meets Naor
Allocation of goods and services often involves both stochastic supply and stochastic demand. Motivated by applications such as cloud computing, gig platforms, and blockchain auctions, we study the design of optimal sell…
Cloud ComputingLFQ: Online Learning of Per-flow Queuing Policies using Deep Reinforcement Learning
The increasing number of different, incompatible congestion control algorithms has led to an increased deployment of fair queuing. Fair queuing isolates each network flow and can thus guarantee fairness for each flow eve…
Deep Reinforcement LearningFairnessManagementreinforcement-learning+1Learning-Augmented Priority Queues
Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements with assigned priorities and the extrac…