Title :
Market equilibrium via a primal-dual-type algorithm
Author :
Devanur, Nikhil R. ; Papadimitriou, Christos H. ; Saberi, Amin ; Vazirani, Vijay V.
Author_Institution :
Coll. of Comput., Georgia Inst. of Technol., Atlanta, GA, USA
Abstract :
Although the study of market equilibria has occupied center stage within mathematical economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We provide the first such algorithm for the linear version of a problem defined by Irving Fisher in 1891. Our algorithm is modeled after Kuhn´s (1995) primal-dual algorithm for bipartite matching.
Keywords :
computational complexity; economic cybernetics; bipartite matching; linear problem; market equilibria; mathematical economics; polynomial time algorithms; primal-dual algorithm; Bipartite graph; Computer science; Educational institutions; Heart; Linear programming; Polynomials;
Conference_Titel :
Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on
Print_ISBN :
0-7695-1822-2
DOI :
10.1109/SFCS.2002.1181963
