Finding Equilibria through Natural Play:

Tatonnement and the Market Problem

Lisa Fleischer

Dartmouth University and IBM TJ Watson Research

Monday  Aug. 28, 2006

4:00 PM, 5130 Upson

Abstract: While much recent attention has focussed on the computational tractability of computing equilibria of various multiplayer games, less attention has been paid to how the players themselves might converge to an equilibrium while making individually rational decisions.

We consider this question in the context of the classical market problem as put forth by Walras: There is a market consisting of a set of infinitely divisible goods; and a set of agents with an initial allocation of the goods and a utility function over combinations of goods. Trade is driven by the prices of the goods. Each agent can buy at most the worth of their initial allocation. Prices provide an equilibrium if, in addition, the demand for each good is bounded by the supply.

In 1874, Walras hypothesized that some form natural price adjustment should lead to equilibrium prices for the market problem. Much later, Arrow et al. showed that a differential process specified by Samuelson did indeed converge to equilibrium in markets of gross substitutes. Shortly afterward, Uzawa described a discrete process that also converges. However, Uzawa's process depends on global knowledge of the market --- information that market players are unlikely to consistently share.

We describe a discrete and distributed process in which player actions depend on reasonable local knowledge only. We show not only that this converges in many markets of gross substitutes, but also that it does so quickly --- in polynomial time.

This is joint work with Richard Cole of NYU.