Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items

Kazuo Murota, Akiyoshi Shioura and Zaifu Yang

Discussion Papers from Department of Economics, University of York

Abstract: 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.

Keywords: Dynamic auction; gross substitutes; equilibrium; complexity (search for similar items in EconPapers)
JEL-codes: D44 (search for similar items in EconPapers)
Date: 2013-06
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://www.york.ac.uk/media/economics/documents/discussionpapers/2013/1313.pdf Main text (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:yor:yorken:13/13

Access Statistics for this paper

More papers in Discussion Papers from Department of Economics, University of York Department of Economics and Related Studies, University of York, York, YO10 5DD, United Kingdom. Contact information at EDIRC.
Bibliographic data for series maintained by Paul Hodgson ().