Publication
ACM Transactions on Algorithms
Paper

A simple and efficient algorithm for computing market equilibria

View publication

Abstract

We give a new mathematical formulation of market equilibria in exchange economies 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, including: - Homogeneous utilities of degree α ∈ [0, 1] in Fisher economies - this includes Linear, Leontief, Cobb-Douglas - Resource allocation utilities like multi-commodity flows satisfy this condition and can be efficiently solved. Further, we give a natural tâtonnement type price-adjusting algorithm in these economies. Our algorithm, which is applicable to a larger class of utility functions than previously known weak gross substitutes, mimics the natural 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.

Date

01 May 2016

Publication

ACM Transactions on Algorithms

Authors

Share