Abstract: 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.

Joint work with Jacob Leshno, Amin Saberi and Pengyu Qian

Bio: Itai Ashlagi is an Associate Professor at the Management Science & Engineering Department. He is interested in game theory and the design and analysis of marketplaces. He is especially interested in marketplaces, in which matching is an essential activity. markets, for which he developed mechanisms using tools from operations/cs and economics. His work influenced the practice of Kidney exchange, for which he has become a Franz Edelman Laureate. Ashlagi received his PhD in operations research from the Technion-Israel Institute of Technology. Before coming to Stanford he was an assistant professor of Operations Management at Sloan, MIT and prior to that a postdoctoral researcher at HBS. He is the recipient of the outstanding paper award in the ACM conference of Electronic Commerce 2009. His research is supported by the NSF including an NSF-CAREER award.