Market clearing by queuing, by Ashlagi, Leshno, Qian and Saberi

Queue Lengths as Constantly Adapting Prices: Allocative Efficiency Under Random Dynamics
Itai Ashlagi, Jacob Leshno, Pengyu Qian, and Amin Saberi
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation July 2020 Pages 317–318 https://doi.org/10.1145/3391403.3399539

ABSTRACT
"Waiting lists are common mechanisms for allocating scarce items without monetary transfers. Examples include the allocation of cadaver organs to patients in need of a transplant, public housing apartments to applicants, health care services to patients, and even spots at childcare centers to parents. In all these markets waiting times play the role of prices in guiding the allocation and rationing items. But while prices are set by the designer, waiting times are endogenously determined by the number of agents waiting. Moreover, waiting times are not fixed, and continuously adjust as items arrive or agents join. When agents and items arrive stochastically over time, waiting times stochastically adjust over time.

"The stochastic adaptation of waiting times adversely impacts the allocative efficiency. If utility is quasi-linear in waiting time, standard competitive equilibrium (CE) arguments show that fixed waiting times can serve as market clearing prices and yield the optimal allocative efficiency. But even if one may expect the endogenously generated waiting times to tend towards market clearing prices, the waiting times keep fluctuating and never converge. Agents may arrive when waiting times are far from the market clearing prices, and their assignment can be inefficient.

"This paper evaluates the allocative efficiency loss due to the random fluctuations. We consider a standard waiting list mechanism, which holds a separate First Come First Served (FCFS) queue for each of finitely many items. Items arrive over time according to a Poisson process, and are assigned to the first agent in the respective queue. Agents arrive over time according to a Poisson process, observe the length of each queue, and then choose a queue to join or leave the system. An agent who joins a queue must wait there until he receives the item. Agents have heterogeneous private values over the items, and their utility is quasi-linear in waiting costs. That is, all agents have the same waiting costs. We interpret the expected waiting costs at each queue as prices that stochastically adjust as items arrive or agents join the queues.

"Our key technical observation is that the waiting list's random price adaptation process is equivalent to that of a stochastic gradient descent algorithm (SGD). While each arrival randomly adjusts prices, the expected price adjustment from each arrival moves waiting times towards market clearing prices. However, waiting times never converge. Standard usage of SGD optimization algorithms requires reducing the step size to zero as the algorithm gets closer to the optimal solution. In contrast, the step-size for the waiting list mechanism is determined by the granularity of waiting costs C>0, which is the maximal price impact (i.e., increase in expected waiting costs) of adding one agent to a queue.

"Our first result states that the allocative efficiency loss from the random price fluctuations is O(C), and this bound is tight. We further show that, if there are finitely many agent types and the optimal static assignment problem has a unique dual solution (which generically holds), then the allocative efficiency loss becomes exponentially small as C -> 0."