A Polynomial-Time Combinatorial Algorithm for the Linear Arrow-Debreu Market.

10:00 c.t. - 12:00


Prof. Dr. Kurt Mehlhorn

Max-Planck-Institut für Informatik, Saarbrücken

Leon Walras (1874) formulated a simple model of an exchange economy and asked for the existence of market-clearing prices. If the utility functions of the market participants are linear, the equilibrium prices can be computed in polynomial time. This was shown by Jain using the Ellipsoid method and by Ye using the interior point method. Duan and Mehlhorn recently found a polynomial-time combinatorial algorithm. It works in phases. In each phase it increases the prices of a carefully chosen set of goods for which demands exceeds supply.

Zeit & Ort

18.06.2015, 10:00 c.t. - 12:00

SR 049, Takustr. 9