A polynomial time algorithm for computing an Arrow-Debreu market equilibrium for linear utilities

We provide the first polynomial time exact algorithm for computing an Arrow-Debreu market equilibrium for the case of linear utilities. Our algorithm is based on solving a convex program using the ellipsoid algorithm and simultaneous diophantine approximation. As a side result, we prove that the set of assignments at equilibria is convex and the equilibria prices themselves are log-convex. Our convex program is explicit and intuitive, which allows maximizing a concave function over the set of equilibria. On the practical side, Ye developed an interior point algorithm (Ye, 2004) to find an equilibrium based on our convex program. We also derive separate combinatorial characterizations of equilibrium for Arrow-Debreu and Fisher cases. Our convex program can be extended for many non-linear utilities (Codenotti and Varadarajan, 2004; Jain and Ye) and production models (Jain). Our paper also makes a powerful theorem even more powerful in the area of geometric algorithms and combinatorial optimization. The main idea in this generalization is to allow ellipsoids not to contain the whole convex region but a part of it. This theorem is of independent interest.