Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items
We address the problem of computing a Walrasian equilibrium price in an ascending auction with gross substitutes valuations. In particular, an auction market is considered where there are multiple differentiated goods and each good may have multiple units. Although the ascending auction is known to ï¬nd an equilibrium price vector in ï¬nite time, little is known about its time complexity. The main aim of this paper is to analyze the time complexity of the ascending auction globally and locally, by utilizing the theory of discrete convex analysis. An exact bound on the number of iterations is given in terms of the L infinity distance between the initial price vector and an equilibrium, and an efficient algorithm to update a price vector is designed based on a min-max theorem for submodular function minimization.
|Date of creation:||Jun 2013|
|Date of revision:|
|Contact details of provider:|| Postal: Department of Economics and Related Studies, University of York, York, YO10 5DD, United Kingdom|
Phone: (0)1904 323776
Fax: (0)1904 323759
Web page: http://www.york.ac.uk/economics/
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:yor:yorken:13/13. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Paul Hodgson)
If references are entirely missing, you can add them using this form.