|
Article Excerpt
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 corresponding 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 MSC2000 subject classification: Primary: 91B50, 91B52; secondary: 91B26, 68W40 OR/MS subject classification: Primary: economics, algorithms; secondary: bidding/auctions History: Received June 1, 2004; revised September 21, 2005 and May 27, 2006.
1. Introduction. In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. Consider a market comprising n traders and m goods. Each trader has an endowment given by a portfolio of goods. A finite quantity of each good is available and is assumed to be divisible. Further, each (trader, good) pair has an associated utility function. This function is assumed to be nonnegative and linear. The market equilibrium problem is to compute a price vector and a feasible assignment of goods to buyers such that no buyer is induced to change his assignments with respect to the given set of prices, and market clearing is achieved--i.e., there is no surplus or deficit of the goods.
The problem is of considerable interest in economics and was first proposed in 1874 by Walras [21]. Independently, Fisher proposed a special case of this problem in 1891 (Brainard and Scarf [4]). Walras [21] proposed the notion of general equilibrium. Walras proposed that a general equilibrium could be achieved by a price adjustment process called tattonement. Establishing that an equilibrium can be achieved is a problem of considerable interest in descriptive and normative economics. The existence of equilibrium prices in a general setting was established by Arrow and Debreu [1] in 1954. The proof is nonconstructive, and the natural question is the existence of an efficient computation process that establishes equilibrium. The model proposed by Fisher is more amenable to computational methods. In Fisher's model, buyers (traders) initially have the endowment of money while the sellers initially have goods. Moreover, the buyers do not have any value for money and the sellers do not have any value for the goods. The more general model considered by us was proposed by Walras. In this model the traders have an initial endowment of goods (instead of money). The amount of money available for use by the trader is dependent on the final price of the goods.
Efficient computation of the market equilibrium is an important problem highlighted recently by Papadimitriou [18]. Computation of market equilibrium has been of considerable interest in the history of microeconomics. In 1891 Fisher (Brainard and Scarf [4]) presented a design of a hydraulic apparatus for calculating equilibrium prices when utilities are separable, additive, monotone, and concave. Around the same time, Walras suggested that market equilibrium prices may be discovered by a price adjustment process called tattonement. In 1959, Arrow et al. [2] showed the stability of the price adjustment process for a large class of utility functions that satisfied the property of gross substitutability. They showed that
[[P.bar].sup.*]Z([P.bar]) [greater than or equal to] 0, [for all] [P.bar]
where [[P.bar].sup.*] > is the vector of equilibrium prices, [P.bar] is a price vector, and Z([P.bar]) is a homogeneous (invariant under scaling) excess demand function. Using this property, algorithms utilizing circumscribed and inscribed ellipsoids have been discussed in Newman and Primak [17] and Primak [19]. The above characterization leads to an ellipsoid method for computation of market equilibrium in polynomial time. This approach has been surveyed in a recent note by Codenotti et al. [6].
Eaves [11] formulated the market equilibrium problem with linear utilities as a linear complementarity problem and used Lemke's algorithm to solve it. Eisenberg and Gale [12] have reduced the market equilibrium problem for the Fisher model with linear utilities, to an optimization problem. These results were derived for the Fisher model. In 1983, Nenakov and Primak [16] showed how to solve the equilibrium problem in the general Walrasian model via a convex program. Recently, Jain [13] also devised a similar convex inequality system for the general Walrasian model when the utilities are linear. The inequalities that characterize the solution are similar to the complementary slackness conditions that arise in the program of Eisenberg and Gale [12]. Using a similar approach and the model of Eisenberg and Gale [12], Ye [22] claims interior point methods for both the Fischer and the Walrasian models in the case of linear utility functions, resulting in finding the exact solution to the problem in O([n.sup.4]L) arithmetic operations. A bound on the precision required for executing these operations has not been provided (but should be better than the ellipsoid method).
Combinatorial methods to solve this problem are of importance because they avoid the numerical issues involved with the ellipsoid method and interior point algorithms. A polynomial-time combinatorial algorithm for the Fischer model was proposed in Devanur et al. [10] in 2002. In this paper we continue the combinatorial study and devise efficient approximation algorithms to solve the equilibrium problem in the general Walrasian model. The algorithms are based on an auction mechanism resulting in a tattonement process. To model the problem, we formulate a family of linear programs parameterized by the price vector. We construct the dual of these programs. The dual program corresponding to a market-clearing price has an optimal solution where dual variables corresponding to a family of inequalities in the primal program are all equal to zero. We show that whenever these dual variables are zero, the corresponding price vector achieves market clearing. The market-clearing conditions arise naturally from the complementary slackness conditions of the parameterized linear program.
We present a primal-dual formulation of the market equilibrium problem. Using this formulation, we define a (1 + [epsilon])-approximate market equilibrium where the the total money spent by any buyer is greater than or equal to a factor (l - [epsilon]) and less than or equal to a factor (1 + [epsilon]) of its total endowment; the quantity of any good sold is at least a factor 1/(1 + [epsilon]) of its availability; and complementary slackness conditions arising from the primal-dual formulations are satisified within a factor (1 + [epsilon]). We describe two auction-based algorithms for computing approximate market equilibrium. These algorithms resemble a primal-dual mechanism similar to Kuhn's [15] methodology for bipartite matching. These can also be viewed as an auction mechanism similar to Demange et al. [7] and Bertsekas [3] or an efficient tattonement-type process (Samuelson [20], Cheng and Wellman [5]) for computing approximate market clearing.
The time complexity of our first algorithm is O((1/[[epsilon].sup.2])nmlog(([p.sub.max]a)/([epsilon][a.sub.min])) log [p.sub.max]), where a = [[summation].sup.m.sub.j=1] [a.sub.j] the sum of all available goods, [P.sub.max] is the largest price (assuming that the smallest price is unity), [a.sub.min] = [min.sub.i,j] [a.sub.ij] > is the smallest quantity of a good endowed to a trader, n is the number of traders, and m is the number of goods in the market.
Our second algorithm is of complexity O((1/[epsilon])([nm.sup.2] + [mn.sup.2]) log [p.sub.max]), replacing a factor of 1/[epsilon] in the first algorithm by m. This is an improvement whenever 1/[epsilon] > m. The algorithm is polynomial in all the parameters of the problem, except in the specification length of the error tolerance [epsilon].
These algorithms ensure that the aggregate endowment of the buyers is approximately all spent (i.e., within a factor (1 + [epsilon])). However, this does not ensure that each buyer spends approximately all of its endowment. This stronger condition is achieved by a second phase in these algorithms, termed phase2, that ensures that the endowment of every buyer that is spent is greater than or equal to a factor (1 - [epsilon]) and less than or equal to a factor (1 + [epsilon]) of its total endowment. This leads to the desired (1 + [epsilon])-approximate market equilibrium.
After the development of this algorithm we have become aware of two approximation algorithms developed around the same time for this problem. The first algorithm (Jain et al. [14]) provides an approximation using the framework described in Nikhil et al. [10]. This algorithm achieves complete market clearing and approximates the optimality of the solution. The second algorithm (Devanur and Vazirani [9]) removes the dependence on the sizes of the numbers to achieve a strongly polynomial algorithm. The notion of the approximation achieved in the paper (Devanur and Vazirani [9]) is that of bounding the deficiency or surplus of the goods in terms of their monetary value and is weaker than our definition of (1 + [epsilon])-approximate market equilibrium.
The algorithm presented in Nikhil et al. [10] computes exact market-cleating prices in the Fisher model, which is a special case of the model we consider in this paper, using O([n.sup.4](log n + n log U + log M)) max-flow computations, where M is the total amount of money available in the market and U = [max.sub.ij] [v.sub.ij] is the maximum valuation of a good by a trader. The...
|
