Richard Cole Colloquium, 02/12, 4pm
David Kempe
a gentle reminder about tomorrow's (Thursday) colloquium talk by
Richard Cole. All important information is below.
We are looking forward to seeing many of you there.
02/12/2009 4:00 PM SSL 150
Explaining Market Price Discovery as an Algorithmic Process
Speaker: Prof. Richard Cole, New York University
Abstract:
Self-organizing behavior can often be characterized in terms of a
distributed process. It is natural to ask when and why it arises.
One instance of such a distributed process is pricing in markets. A basic
tenet of well-functioning markets is that they discover (converge toward)
prices that simultaneously balance supplies and demands of all goods;
these are called equilibrium prices. Further, the markets are
self-stabilizing, meaning that they converge toward new equilibria as
conditions change. This talk will seek to explain why this might happen by
taking an algorithmic approach.
More specifically, we introduce the setting of Ongoing Markets (by
contrast with the classic Fisher and Exchange markets). An Ongoing Market
allows trade at non-equilibrium prices, and, as its name suggests,
continues over time. The main task remaining is to specify and analyze a
price update rule. We consider a (tatonnement-style) rule with the
following characteristics:
1. The procedure is distributed: (i) the price updates for each good are
independent, and (ii) the update for each good uses only limited "local"
information. 2. It is asynchronous: price updates do not have to be
simultaneous. 3. It is simple.
And for appropriate markets the rule enables:
4. Fast convergence. 5. Robustness in the face of (somewhat) inaccurate
data.
This talk is intended for a general (Computer Science) audience; it is
based on joint works with Lisa Fleischer and Ashish Rastogi.
Biography:
Richard Cole is a professor of Computer Science in the Courant Institute
at NYU, where he has been on the faculty since receiving his Ph.D. in
1982. His Ph.D. was from Cornell, supervised by John Hopcroft. He served
as department chair from 1994-2000. He was a fellow of the Guggenheim
Foundation in 1988-89, and was named an ACM Fellow in 1998. He is the
author or coauthor of over 100 papers. Highlights include the Parallel
Merge Sort algorithm, the proof of the Dynamic Finger Conjecture for Splay
Trees, and a tight analysis of the Boyer-Moore string matching algorithm.