A Simple Approximation Algorithm for Computing Arrow-Debreu Prices

• 成果类型: Article
• 署名作者: Ghiyasvand, Mehdi; Orlin, James B.
• 署名单位: Bu Ali Sina University; Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1113
• 发表日期: 2012
• 页码: 1245-1248
• 关键词: market; equilibrium

摘要

We consider the Arrow-Debreu market with linear utilities in which there is a set G of divisible goods and a set B of buyers. Each buyer starts with an initial endowment of goods. The buyer's utility function is a linearly separable function of the goods that the buyer purchases. We develop a simple and efficient algorithm for determining an approximate market equilibrium. Our algorithm finds an E-approximate solution in O(n/epsilon(vertical bar B vertical bar vertical bar G vertical bar)) time, where n = vertical bar B vertical bar+ vertical bar G vertical bar. The running time can be further improved to O(n/epsilon(m+ vertical bar B vertical bar log vertical bar B vertical bar) where in is the number of pairs (i, j) such that buyer i has some utility for purchasing good j.