Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar

Market equilibrium is an inherently algorithmic notion  -- this should be obvious from the fact that while defining this notion in 1874, Walras also gave a mechanism for arriving at an equilibrium, namely the tatonnement process. In the 1970s, attention shifted to centralized algorithms and impressive approaches were given by Scarf and Smale; however, these algorithms were slow, and moreover they suffered from issues of numerical instability. 

In 1975, Eaves gave a complementary pivot algorithm for computing an equilibrium for the linear case of the Arrow-Debreu market. Although this approach was far superior, since complementary pivot algorithms tend to be very fast in practice and do not suffer from issues of numerical instability, it was not extended to more general utility functions until two years ago.  We will summarize this new development, which led to complementary pivot algorithms for separable, piecewise-linear concave (SPLC) utility functions and SPLC production sets. 

Recently, they also led to the definition of a new class of utility functions, called Leontief-free, which are applicable when goods are substitutes, e.g., bread and bagels. We note that when goods are complements, e.g., bread and butter, the classical Leontief function does a splendid job. Surprisingly enough, for the former case, utility functions had been defined only for special cases in economics, e.g., CES utility function. A new min-max relation supports the claim that our notion is well-founded.

This talk is fully self-contained. It is designed for researchers in TCS and mathematical economics. It is based on joint works with Jugal Garg and Ruta Mehta, in particular:  http://www.cc.gatech.edu/~vazirani/LF.pdf