Tatonnement for Linear and Gross Substitutes Markets

A central question in economics and computer science is when and how markets can arrive at an equilibrium. Many existing algorithms for computing equilibria in classes of Arrow-Debreu markets rely on full knowledge of the utility functions of all agents, while in reality we often face unknown markets without this information. A classic approach to unknown markets from economics is tatonnement -- dynamic price update processes that only require oracle access to query the aggregate demand of each good. In this paper, we design a new class of tatonnement algorithms. For the first time, we show how tatonnement can converge in polynomial time to market equilibria in linear markets and spending constraint markets, where the main obstacle is a non-continuous demand function. This also gives the first polynomial-time algorithm for spending constraint markets and settles an open question raised in [Duan and Mehlhorn, ICALP'13]. Moreover, our algorithms can be applied to unknown markets with weak gross substitutes (WGS) property, in which they converge to $(1+\epsilon)$-approximate market equilibria in time polynomial in market parameters and $\log(1/\epsilon)$. This exponentially improves the previous convergence rate of polynomial in market parameters and $1/\epsilon$. Our approach uses ideas developed for full information linear markets and applies them in unknown linear and non-linear markets. Since our oracles return demands based on real utility functions, precision and representation of prices and demands become a major technical challenge. Here we develop new tools and insights, which may be of independent interest.