A Fast and Simple Algorithm for Computing Market Equilibria

摘要

We give a new mathematical formulation of market equilibria using an indirect utility function: the function of prices and income that gives the maximum utility achievable. The formulation is a convex program and can be solved when the indirect utility function is convex in prices. We illustrate that many economies includingrn1. Homogeneous utilities of degree α ∈ [0,1] in Fisher economies -this includes Linear, Leontief, Cobb-Douglasrn2. Resource allocation utilities like multi-commodity flowsrnsatisfy this condition and can be efficiently solved.rnFurther, we give a natural and decentralized price-adjusting algorithm in these economies. Our algorithm, mimics the natural tatonnement dynamics for the markets as suggested by Walras: it iteratively adjusts a good's price upward when the demand for that good under current prices exceeds its supply; and downward when its supply exceeds its demand. The algorithm computes an approximate equilibrium in a number of iterations that is independent of the number of traders and is almost linear in the number of goods. Interestingly, our algorithm applies to certain classes of utility functions that are not weak gross substitutes.