A rational convex program for linear Arrow-Debreu markets

被引：14

作者：

Devanur N.R. ^{[1
]}

Garg J. ^{[2
]}

Végh L.A. ^{[3
]}

机构：

[1] Microsoft Research, One Microsoft Way, Redmond, 98052, WA

[2] Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, 104 S Mathews Ave, Urbana, 61801, IL

[3] Department of Mathematics, London School of Economics and Political Science, Houghton Street, London

来源：

ACM Transactions on Economics and Computation | 2016年 / 5卷 / 01期

关键词：

Convex programming; Linear exchange market; Market equilibrium;

D O I：

10.1145/2930658

中图分类号：

学科分类号：

摘要：

We present a new flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known ([Nenakov and Primak 1983; Jain 2007; Cornet 1989]), our program exhibits several new features. It provides a simple necessary and sufficient condition and a concise proof of the existence and rationality of equilibria, settling an open question raised by Vazirani [2012]. As a consequence, we also obtain a simple new proof of the result in Mertens [2003] that the equilibrium prices form a convex polyhedral set. © 2016 ACM.

引用

共 26 条

[1]

Arrow K.J., Debreu G., Existence of an equilibrium for a competitive economy, Econometrica: Journal of the Econometric Society, pp. 265-290, (1954)

[2]

Birnbaum B.E., Devanur N.R., Xiao L., Distributed algorithms via gradient descent for Fisher markets, ACM Conference on Electronic Commerce, pp. 127-136, (2011)

[3]

Boyd S.P., Vandenberghe L., Convex Optimization, (2004)

[4]

Brainard W.C., Scarf H.E., How to Compute Equilibrium Prices in 1891, (2000)

[5]

Codenotti B., Pemmaraju S., Varadarajan K., The computation of market equilibria, ACM SIGACT News, 35, 4, pp. 23-37, (2004)

[6]

Cornet B., Linear Exchange Economies, (1989)

[7]

Devanur N.R., Fisher Markets and Convex Programs, (2009)

[8]

Devanur N.R., Papadimitriou C.H., Saberi A., Vazirani V.V., Market equilibrium via a primal-dual algorithm for a convex program, Journal of the ACM, 55, 5, (2008)

[9]

Duan R., Mehlhorn K., A combinatorial polynomial algorithm for the linear Arrow-Debreu market, Information and Computation, 243, pp. 112-132, (2015)

[10]

Eaves C.B., A finite algorithm for the linear exchange model, Journal of Mathematical Economics, 3, 2, pp. 197-203, (1976)

← 1 2 3 →