This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Garg, R. Articles by Kapoor, S. Search for Related Content

Auction Algorithms for Market Equilibrium

IBM India Research Laboratory, Block-I, IIT Campus, Hauz Khas, New Delhi, India 110016
Illinois Institute of Technology, Chicago, Illinois 60616, USA
grahul{at}in.ibm.com
kapoor{at}iit.edu

In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. The buyers in the market have an initial endowment given by a portfolio of goods. The market equilibrium problem is to compute a price vector that ensures market clearing, i.e., the demand of a positively priced good equals its supply, and given the prices, each buyer maximizes its utility. The problem is of considerable interest in economics. This paper presents a formulation of the market equilibrium problem as a parameterized linear program. We construct a family of duals corrresponding to these parameterized linear programs and show that finding the market equilibrium is the same as finding a linear program from this family of linear programs. The market-clearing conditions arise naturally from complementary slackness conditions. We then define an auction mechanism that computes prices such that approximate market clearing is achieved. The algorithm we obtain outperforms previously known methods.

Key Words: market equilibrium; auction algorithm; Walrasian model
History: Received: June 1, 2004; revision received: May 27, 2006;