Fall 2005 Seminar Series

DATE: Thursday, December 1, 2005
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
Lisa Fleischer
Research Staff Member
IBM Watson Research Center

TITLE
Toward Discrete and Local Tatonnement Algorithms for the Market Problem

ABSTRACT
In the market equilibrium problem, 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. It was shown by a fixed point argument in the 1950's that an equilibrium always exists.

 

Since then, focus has been on developing constructive roofs or computable mechanisms. Prior work focuses either on global optimization procedures or continuous-time mechanisms (differential equations).

 

In contrast, we propose a dynamic, discrete time, distributed mechanism that may indicate how a market arrives at an equilibrium. We prove convergence properties for this mechanism in some types of markets. This is, to the best of our knowledge, the first convergent, discrete, local algorithm for any version of the market problem.

 

Joint work with Richard Cole of NYU