Richard Cole Colloquium, 02/12, 4pm
David Kempe
our next theory talk in the colloquium is right around the corner:
Richard Cole from NYU will give a talk on "Explainint Market Price
Discovery as an Algorithmic Process" next Thursday.
Looking forward to seeing many of you there.
Date: 02/12/2009 4:00 PM
Location: SSL 150
Title: 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.
-- David Kempe <dke...@usc.edu>