There is a signup schedule for this event (UT EID required).

Ty

pe of Talk: UTCS Colloquium/Algorithms and Computation Theory Seminar
<

br>Speaker/Affiliation: Richard Cole/New York University

Date/Time:
Friday December 5 2008 11:00 a.m.

Location: TAY 3.128

H

ost: Vivaya Ramachandran

Talk Title: When Might Markets be Self-St

abilizing? A Distributed Quickly Convergent Tatonnement Algorithm

T

alk Abstract:
Why might markets be self-stabilizing in the sense
of
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

etting
of Ongoing Markets by contrast with the classic Fisher
and

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
actual markets.

We consider a tatonnement-sty

le price update rule with the
following characteristics:

1. Th

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

It is asynchronous: price updates do not have to be simultaneous.

An

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

ffices.

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
respect

to prices.

The analysis is potential function based.

This tal

k is based on joint works with Lisa Fleischer and Ashish Rastogi.

Sp

eaker Bio:
Richard Cole is a professor of Computer Science in the Couran

t Institute
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
Finger Conjecture

for Splay Trees and a tight analysis of the Boyer-Moore
string matchin

g algorithm.