Title:

Fast-Converging Tatonnement Algorithms for One-Time and Ongoing Market Problems

Speaker:  Richard Cole, NYU. 

Abstract:

Why might markets tend toward and remain near equilibrium prices? In an 

effort to shed light on this question from an algorithmic perspective, 

we formalize the setting of Ongoing Markets, by contrast with the 

classic market scenario, which we term One-Time Markets.  The Ongoing 

Market allows trade at non-equilibrium prices, and, as its name 

suggests, continues over time.  As such, it appears to be a more 

plausible model of actual markets.



For both market settings, we define and analyze variants of a simple

 tatonnement algorithm that differs from previous algorithms that have 

been subject to asymptotic analysis in three significant respects: the 

price update for a good depends only on the price, demand, and supply 

for that good, and on no other information; the price update for each 

good occurs distributively and asynchronously; the algorithms work (and 

the analyses hold) from an arbitrary starting point.



Our algorithm introduces a new and natural update rule. We show that 

this update rule leads to fast convergence toward equilibrium prices in 

a broad class of markets that satisfy the weak gross substitutes 

property.



Our analysis identifies three parameters characterizing the markets, 

which govern the rate of convergence of our protocols.  These 

parameters are, broadly speaking:



* A bound on the fractional rate of change of demand for each good with 

respect to fractional changes in its price.




* A bound on the fractional rate of change of demand for each good with 

respect to fractional changes in wealth.



* The closeness of the market to a Fisher market (a market with


buyers starting with money alone)



(This is joint work with Lisa Fleischer.)