Market Equilibrium via a Primal-Dual Algorithm for a Convex Program

被引：120

作者：

Devanur, Nikhil R. ^{[1
]}

Papadimitriou, Christos H. ^{[2
]}

Saberi, Amin

Vazirani, Vijay V. ^{[1
]}

机构：

[1] Georgia Inst Technol, Atlanta, GA 30332 USA

[2] Univ Calif Berkeley, Div Comp Sci, Dept EECS, Berkeley, CA 94720 USA

来源：

JOURNAL OF THE ACM | 2008年 / 55卷 / 05期

基金：

美国国家科学基金会;

关键词：

Algorithms; Economics; Market equilibria; primal-dual algorithms;

D O I：

10.1145/1411509.1411512

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal-dual paradigm in the enhanced setting of KKT conditions and convex programs. We pinpoint the added difficulty raised by this setting and the manner in which our algorithm circumvents it.

引用

页数：18

共 29 条

[1] EXISTENCE OF AN EQUILIBRIUM FOR A COMPETITIVE ECONOMY [J].

Arrow, Kenneth J. ;

Debreu, Gerard .

ECONOMETRICA, 1954, 22 (03) :265-290

[2]

CHAKRABARTY D, 2006, P 2 WORKSH INT NETW

[3]

Codenotti Bruno, 2004, ACM SIGACT NEWS, V35, P23

[4]

DENG X, 2002, P ACM S THEOR COMP

[5]

DEVANUR NR, 2004, P 36 ANN ACM S THEOR

[6]

DEVANUR NR, 2003, P 23 FSTTCS

[7] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

[8] CONSENSUS OF SUBJECTIVE PROBABILITIES - THE PARI-MUTUEL METHOD [J].

EISENBERG, E ;

GALE, D .

ANNALS OF MATHEMATICAL STATISTICS, 1959, 30 (01) :165-168

[9]

Gale David, 1960, THEORY LINEAR EC MOD

[10]

GARG R, 2004, P 36 ANN ACM S THEOR

← 1 2 3 →