Asynchronous Market Dynamics and Asynchronous Gradient Descent

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