Title: Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue
Walras, while defining the quintessential notion of market equilibrium in 1874, also gave a simple and natural rule for updating prices and called it the tatonnement process. Does the tatonnement process converge to equilibrium prices? This was a central question in mathematical economics for almost a century. Positive news came in the 1950s, when convergence was established for the gross substitutes case. However, it was followed by negative news in the 1960s: an example by Scarf on which tatonnement cycles and the Sonnenschein-Debreu-Mantel theorem which showed that the task was hopeless for a general Arow-Debreu market.
In this work we have, for the first time, gone beyond the gross substitutes case. We define a class of markets for which tatonnement is equivalent to gradient descent. This is the class of markets for which there is a convex potential function whose gradient is always equal to the negative of the excess demand. We call this class the Convex Potential Function (CPF) markets. We show the following results:
- CPF markets contain the class of Eisenberg Gale (EG) markets, defined previously by Jain and Vazirani.
- The subclass of CPF markets for which the demand is a differentiable function contains exactly those markets whose demand function has a symmetric negative semi-definite Jacobian.
- We define a family of continuous versions of tatonnement based on gradient descent using a Bregman divergence. As we show, for many CPF markets, every process in this family will converge to an equilibrium and the process based on KL-divergence will converge for even more of these markets. This is analogous to the classic result for markets satisfying the Weak Gross Substitutes property. We use the theory of differential inclusions, a generalization of differential equations, to establish this result.
- A discrete version of tatonnement converges toward the equilibrium for Fisher markets with buyers having CES or Leontief utility functions; the convergence rates for these settings are analyzed using a common potential function. For the CES case, we prove that the tatonnement converges linearly by showing that the potential function satisfies strong sandwiching property, which is reminiscent of strong convexity.
I will also discuss our recent results on:
- ongoing Fisher markets, a model proposed by Cole and Fleischer. In this model, price updates are asynchronous, and warehouses are incorporated to meet excess demand and store excess supply;
- Fisher markets with NCES utility functions, a generalization of CES utility functions.
Joint work with Richard Cole and Nikhil Devanur.