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 [11] for Fisher's model. We develop new methods to carefully deal with the flows and surpluses during price adjustments. Our algorithm performs O ( n 6 log ⁡ ( n U ) ) maximum flow computations, where n is the number of agents and U is the maximum integer utility. The flows have to be presented as numbers of bitlength O ( n log ⁡ ( n U ) ) to guarantee an exact solution. Previously, [22, 29] have given polynomial time algorithms for this problem, which are based on solving convex programs using the ellipsoid algorithm and the interior-point method, respectively.

Authors

• Ran Duan
• Kurt Mehlhorn Max Planck Institute for Informatics, Saarland Informatics Campus

Keywords

No keywords are indexed for this paper.