Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
verfasst von : Ran Duan, Kurt Mehlhorn
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.