We consider markets in the classical Arrow-Debreu model. There are n
agents and m goods. Each buyer has a concave utility function
(of the bundle of goods he/she buys) and an initial bundle. At an
``equilibrium'' set of prices for goods, if each individual buyer
separately exchanges the initial bundle for an optimal bundle at
the set prices, the market clears, i.e., all goods are exactly
consumed. Classical theorems guarantee the existence of equilibria,
but computing them has been the subject of much recent research.
In the related area of Multi-Agent Games, much attention has been paid to
the complexity as well as algorithms.
While most general problems are
hard, polynomial time algorithms have been developed for restricted
classes of games, when one assumes the
number of strategies is constant.
For the Market Equilibrium problem, several important special cases of
utility functions have been tackled.
Here we begin a program for this
problem similar to that for multi-agent games, where general utilities
are considered. We begin by showing that if the utilities are
separable piece-wise linear concave (PLC) functions, and the number of
goods (or alternatively the number of buyers) is constant, then we can
compute an exact equilibrium in polynomial time. Our
technique for the constant number of goods is to decompose the space
of price vectors into cells using certain hyperplanes, so that in each
cell, each buyer's threshold marginal utility is known. Still, one
needs to solve a linear optimization problem in each cell.
We then show the main result - that for general
(non-separable) PLC utilities, an exact equilibrium can be found in
polynomial time provided the number of goods is constant. The starting
point of the algorithm is a ``cell-decomposition'' of the space of
price vectors using polynomial surfaces (instead of hyperplanes).
We use results from computational algebraic geometry to bound the
number of such cells.
For solving the problem inside each cell, we introduce and use a novel
LP-duality based method. We note that if the number of
buyers and agents both can vary, the problem is PPAD hard even for the
very special case of PLC utilities such as Leontief utilities and separable PLC utilities.