Title: Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue

Speaker: Yun Kuen Cheung, New York University

Time/Date: Friday, Apr 4, 11-12
Location: Room 3501

Abstract:

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? 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 Arrow-Debreu
market.

In this work we have 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.
 
Joint work with Richard Cole and Nikhil Devanur.