Amortized analysis of asynchronous price dynamics

Yun Kuen Cheung, Richard Cole

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We extend a recently developed framework for analyzing asynchronous coordinate descent algorithms to show that an asynchronous version of tatonnement, a fundamental price dynamic widely studied in general equilibrium theory, converges toward a market equilibrium for Fisher markets with CES utilities or Leontief utilities, for which tatonnement is equivalent to coordinate descent.

Original languageEnglish (US)
Title of host publication26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770811
DOIs
StatePublished - Aug 1 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: Aug 20 2018Aug 22 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume112
ISSN (Print)1868-8969

Other

Other26th European Symposium on Algorithms, ESA 2018
CountryFinland
CityHelsinki
Period8/20/188/22/18

Keywords

  • Amortized analysis
  • Asynchronous tatonnement
  • Fisher market
  • Market equilibrium

ASJC Scopus subject areas

  • Software

Cite this