News

Colloquia

Fast-Converging Tatonnement Algorithms for the Market Problem

Lisa Fleischer
Computer Science
Dartmouth

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 convergence.

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)