Fast-Converging Tatonnement Algorithms for the Market Problem
Monday, May 7, 2007
Why might markets tend toward and remain near equilibrium prices? In an effort to shed light on this question from an
algorithmic perspective, this paper defines and analyzes two simple tatonnement algorithms in which each price updater
uses only information about the corresponding good. The price updates for each good can occur asynchronously. The
analysis shows that the algorithms converge quickly toward equilibrium prices in a natural subset of markets satisfying
the weak gross substitutes. These are the first analyses for pure tatonnement algorithms that demonstrate polynomial
Our analysis identifies three parameters characterizing the markets, which govern the rate of convergence of our
protocols. These parameters are, broadly speaking:
1. A bound on the fractional rate of change of demand for each good with respect to fractional changes in its price.
2. A bound on the fractional rate of change of demand for each good with respect to fractional changes in wealth.
3. The relative demand for money at equilibrium prices.
For the first of our protocols, we provide a matching lower bound in terms of these parameters.
This is joint work with Richard Cole of NYU.
Hosted by: Petros Drineas (x8265)
Administrative support: Chris Coonrad (x8412)