A Simple Approximation Algorithm for Computing Arrow-Debreu Prices

Mehdi Ghiyasvand () and James B. Orlin ()
Additional contact information
Mehdi Ghiyasvand: Department of Mathematics, Faculty of Science, Bu-Ali Sina University, Hamedan, Iran
James B. Orlin: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2012, vol. 60, issue 5, 1245-1248

Abstract: 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 (epsilon)-approximate solution in O ( n /(epsilon)(| B || G |)) time, where n = | B | + | G |. The running time can be further improved to O ( n /(epsilon)( m + | B |log| B |)) where m is the number of pairs ( i, j ) such that buyer i has some utility for purchasing good j .

Keywords: network optimization; market equilibrium; Arrow-Debreu market (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1113 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:5:p:1245-1248

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().