MADALGO seminar

MADALGO theory seminar: Ran Duan, Max-Planck-Institut für Informatik

2014.05.27 | Trine Ji Holmgaard Jensen

Date Wed 28 May
Time 14:15 15:00

Speaker: Ran Duan, Max-Planck-Institut für Informatik

Location: Nygaard 395

Title: 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. Our algorithm performs O(n^6 log(nU)) 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(nlog(nU)) to guarantee an exact solution. Previously, [Jain 2007, Ye 2007] 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.