Time Bounds for Iterative Auctions: A Unified Approach by Discrete Convex Analysis

Kazuo Murota, Akiyoshi Shioura and Zaifu Yang

Discussion Papers from Department of Economics, University of York

Abstract: We examine an auction model where there are many different goods, each good has multiple units, and bidders have gross substitutes valuations over the goods. We analyze the number of iterations in iterative auction algorithms for the model based on the theory of discrete convex analysis. By making use of L♮-convexity of the Lyapunov function we derive exact bounds on the number of iterations in terms of the ℓ∞-distance between the initial price vector and the found equilibrium. Our results extend and unify the price adjustment algorithms of Ausubel (2006) and other existing algorithmsfor the unit-demand auction models, offering computational complexity results for these algorithms, and reinforcing the connection between auction theory and discrete convex analysis.

Keywords: Dynamic Auctions; Complexity Analysis; Indivisibility (search for similar items in EconPapers)
JEL-codes: D44 (search for similar items in EconPapers)
Date: 2014-12
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.york.ac.uk/media/economics/documents/discussionpapers/2014/1427.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:14/27

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 ().