2013 | OriginalPaper | Buchkapitel
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities. Our algorithm views the allocation of money as flows and iteratively improves the balanced flow as in [Devanur et al. 2008] for Fisher’s model. We develop new methods to carefully deal with the flows and surpluses during price adjustments. In our algorithm, we need
O
(
n
6
log(
nU
)) maximum flow computations, where
n
is the number of persons and
U
is the maximum integer utility, and the length of the numbers is at most
O
(
n
log(
nU
)) to guarantee an exact solution. The previous polynomial time algorithms [Nenakov and Primak 1983, Jain 2007, Ye 2007] for this problem are based on solving convex programs using the ellipsoid algorithm or interior-point method.
