Eisenberg-Gale markets: Algorithms and game-theoretic properties

• 成果类型: Article
• 署名作者: Jain, Kamal; Vazirani, Vijay V.
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2008.11.011
• 发表日期: 2010
• 页码: 84-106
• 关键词: General equilibrium theory; Fisher market model; Combinatorial algorithm; primal-dual algorithm; Convex program; resource allocation; Ascending price auctions; Weak gross substitutability; Competition monotonicity; fairness

摘要

We define a new class of markets, the Eisenberg-Gale markets. This class contains Fisher's linear market, markets from the resource allocation framework of Kelly [Kelly, F.P., 1997. Charging and rate control for elastic traffic. Europ. Transactions Telecommunications 8, 33-37], as well as numerous interesting new markets. We obtain combinatorial, strongly polynomial algorithms for several markets in this class. Our algorithms have a simple description as ascending price auctions. Our algorithms lead to insights into game-theoretic properties of these markets, such as efficiency, fairness, and competition monotonicity. They also help determine if these markets always have rational equilibria. A classification of Eisenberg-Gale markets w.r.t. these properties reveals a surprisingly rich set of possibilities. (C) 2008 Elsevier Inc. All rights reserved.