Stochastic Price Adaptation, Waiting Lists, and Stochastic Gradient Descent

Waiting lists allocate items by offering agents a choice among items with associated waiting times. These waiting times serve as prices that are determined endogenously and adjust according to the stochastic arrivals and departures of agents. We study the allocative efficiency under such dynamically adjusting prices by drawing a connection between this price adjustment process and the stochastic gradient descent optimization algorithm. We show that the loss due to price fluctuations is bounded by the granularity of price changes. Additional conditions allow us to identify markets where the loss is close to the bound or exponentially small. Our results show that a simple price adjustment heuristic can perform well, but may be slow to adjust to changes in demand because of a trade-off between the speed of adaptation and loss from price fluctuations.