Timezone: »
Waiting lists allocate items by offering agents a choice among items with associated waiting times. These waiting times serve as prices that are formed by 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.
Author Information
Itai Ashlagi (Stanford)
Jacob Leshno (University of Chicago)
Pengyu Qian (Purdue University)
Amin Saberi (Stanford University)
More from the Same Authors
-
2021 : Designing Defaults for School Choice »
Amel Awadelkarim · Johan Ugander · Itai Ashlagi · Irene Lo -
2021 : Price Discovery and Efficiency in Waiting Lists: A Connection to Stochastic Gradient Descent »
Itai Ashlagi · Jacob Leshno · Pengyu Qian · Amin Saberi -
2022 : Time-constrained decision making in deceased donor kidney allocation »
Nikhil Agarwal · Itai Ashlagi · Grace Guan · Paulo Somaini · Jiacheng Zou -
2022 : Time-constrained decision making in deceased donor kidney allocation »
Nikhil Agarwal · Itai Ashlagi · Grace Guan · Paulo Somaini · Jiacheng Zou -
2021 : Designing Defaults for School Choice »
Amel Awadelkarim · Johan Ugander · Itai Ashlagi · Irene Lo -
2021 Poster: Counterbalancing Learning and Strategic Incentives in Allocation Markets »
Jamie Kang · Faidra Monachou · Moran Koren · Itai Ashlagi -
2019 Poster: Discrimination in Online Markets: Effects of Social Bias on Learning from Reviews and Policy Design »
Faidra Monachou · Itai Ashlagi -
2018 Poster: Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons »
Nima Anari · Constantinos Daskalakis · Wolfgang Maass · Christos Papadimitriou · Amin Saberi · Santosh Vempala