UTCS Colloquium/Algorithms & Computation Theory Seminar: Richard Cole/New York University: When Might Markets be Self-Stabilizing? A Distributed Quickly Convergent Tatonnement Algorithm TAY 3.128 Friday December 5 2008 11:00 a.m.
There is a signup schedule for this event (UT EID required).
pe of Talk: UTCS Colloquium/Algorithms and Computation Theory Seminar
br>Speaker/Affiliation: Richard Cole/New York University
Friday December 5 2008 11:00 a.m.
Location: TAY 3.128
ost: Vivaya Ramachandran
Talk Title: When Might Markets be Self-St
abilizing? A Distributed Quickly Convergent Tatonnement Algorithm
Why might markets be self-stabilizing in the sense
converging toward new equilibria (a simultaneous
balancing of all supp
lies and demands) as conditions
change? In an effort to shed light on
this question from
an algorithmic perspective this talk proposes the s
of Ongoing Markets by contrast with the classic Fisher
Exchange markets. The Ongoing Market allows trade
at non-equilibrium pr
ices and as its name suggests
continues over time. Both would appear
to be features of
We consider a tatonnement-sty
le price update rule with the
ere is a distinct instance of the procedure for each good.
2. The proc
edure is distributed: (i) the instances are independent
and (ii) e
ach instance uses limited local information.
3. It is simple.
It is asynchronous: price updates do not have to be simultaneous.
d the rule enables:
5. Fast convergence.
6. Robustness in the
face of (somewhat) inaccurate data.
The main novel feature in the O
ngoing Market is the introduction
of warehouses which help to cope wit
h supply imbalances. An
important question is what size of warehouse su
We show fast convergence along with bounds on the warehouse
sizes for a subset of divisible markets obeying weak gross substitutes
(WGS) and extend these results to the discrete (indivisible) setting.
The latter work requires the introduction of a suitable generalization
of WGS to the indivisible setting. Broadly speaking our results are
parameterized by bounds on the rate of change of demands with
The analysis is potential function based.
k is based on joint works with Lisa Fleischer and Ashish Rastogi.
Richard Cole is a professor of Computer Science in the Couran
at NYU where he has been on the faculty since receiving hi
s Ph.D. in
1982. His Ph.D. was from Cornell supervised by John Hopcrof
t. He served
as department chair from 1994-2000 and as Acting Director
of the Courant
Institute in Fall 2005.
He was a fellow of the Gu
ggenheim 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 Pa
rallel Merge Sort algorithm the proof of the Dynamic
for Splay Trees and a tight analysis of the Boyer-Moore
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct