Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Asynchronous Market Dynamics and Asynchronous Gradient Descent
Speaker:Yun Kuen Cheung
coming from:University of Vienna
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 24 February 2015
Duration:30 Minutes
Building:E1 4
In the studies of markets and general equilibrium theory, one important and long-lasting question is to seek market dynamics that converge quickly to market equilibrium. The importance in this line of research is: if an equilibrium is realizable, there ought to be a natural and realistic market process that finds it. Theoretical computer science has shed new insight on the problem in the past 20 years, both from algorithmic and complexity perspectives.

In this work, we focus on a natural market dynamic called tatonnement. My previous work with Cole and Devanur showed that in Fisher markets with CES utility functions, tatonnement is equivalent to gradient descent on a convex function, while each minimum of the convex function corresponds to a market equilibrium. This allowed us to show that tatonnement converges to a market equilibrium quickly, assuming prices updates are synchronous.

However, real markets are typically distributed with no central governance, i.e., prices are updated asynchronously, and possibly with outdated information. We design an asynchronous tatonnement rule that incorporates these features, and we develop an amortized technique to analyze asynchronous tatonnement. We show that asynchronous tatonnement converges to market equilibrium in Fisher markets with CES utility functions, by suitably reducing the step sizes used in the asynchronous tatonnement rule.

The update rule and the amortized analysis can be extended to the more general context of asynchronous gradient descent. We note that the amortized analysis may be of independent interests, particularly, in analyzing other asynchronous systems.

This is joint work with Richard Cole (New York University).

Name(s):Martin Hoefer
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Martin Hoefer, 02/11/2015 03:44 PM
  • Martin Hoefer, 02/03/2015 06:42 PM
  • Martin Hoefer, 02/03/2015 05:28 PM -- Created document.