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