Ascending-price algorithms for unknown markets

Xiaohui Bei, Jugal Garg, Martin Hoefer

Research output: Contribution to journalArticlepeer-review

Abstract

We design a simple ascending-price algorithm to compute a (1 + ϵ )-approximate equilibrium in Arrow- Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a global demand oracle. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which computes such an equilibrium with a number of calls to the demand oracle that is polynomial in log 1/ϵ and avoids heavy machinery such as the ellipsoid method. Demands can be real-valued functions of prices, but the oracles only return demand values of bounded precision. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, we give the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities. This resolves an open problem posed by Duan and Mehlhorn.

Original languageEnglish (US)
Article number0080
JournalACM Transactions on Algorithms
Volume15
Issue number3
DOIs
StatePublished - May 2019

Keywords

  • Equilibrium computation
  • Market equilibrium
  • Spending constraint utilities
  • Weak gross substitutes

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Ascending-price algorithms for unknown markets'. Together they form a unique fingerprint.

Cite this