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 items and each item may have multiple units. Although the ascending auction is known to find an equilibrium price vector in finite 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 ℓ ∞ distance between the initial price vector and an equilibrium, and an efficient algorithm to update a price vector is designedbased on a min-max theorem for submodular function minimization.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ausubel, L.M.: An efficient dynamic auction for heterogeneous commodities. American Economic Review 96, 602–629 (2006)
Ausubel, L.M., Milgrom, P.: Ascending auctions with package bidding. Front. Theor. Econ. 1, Article 1 (2002)
Bichler, M., Shabalin, P., Pikovsky, A.: A computational analysis of linear price iterative combinatorial auction formats. Inform. Syst. Res. 20, 33–59 (2009)
Bing, M., Lehmann, D., Milgrom, P.: Presentation and structure of substitutes valuations. In: Proc. EC 2004, pp. 238–239 (2004)
Blumrosen, L., Nisan, N.: Combinatorial auction. In: Nisan, N., et al. (eds.) Algorithmic Game Theory, pp. 267–299. Cambridge Univ. Press (2007)
Cramton, P., Shoham, Y., Steinberg, R.: Combinatorial Auctions. MIT Press (2006)
Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier (2005)
Fujishige, S., Yang, Z.: A note on Kelso and Crawford’s gross substitutes condition. Math. Oper. Res. 28, 463–469 (2003)
Gul, F., Stacchetti, E.: Walrasian equilibrium with gross substitutes. J. Econ. Theory 87, 95–124 (1999)
Gul, F., Stacchetti, E.: The English auction with differentiated commodities. J. Economic Theory 92, 66–95 (2000)
Iwata, S.: A faster scaling algorithm for minimizing submodular functions. SIAM J. Comp. 32, 833–840 (2002)
Kelso, A.S., Crawford, V.P.: Job matching, coalition formation and gross substitutes. Econometrica 50, 1483–1504 (1982)
Kolmogorov, V., Shioura, A.: New algorithms for convex cost tension problem with application to computer vision. Discrete Optimization 6, 378–393 (2009)
Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55, 270–296 (2006)
Milgrom, P., Strulovici, B.: Substitute goods, auctions, and equilibrium. J. Economic Theory 144, 212–247 (2009)
Murota, K.: Convexity and Steinitz’s exchange property. Adv. Math. 124, 272–311 (1996)
Murota, K.: Discrete Convex Analysis. SIAM, Philadelphia (2003)
Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24, 95–105 (1999)
Murota, K., Tamura, A.: New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities. Discrete Appl. Math. 131, 495–512 (2003)
Parkes, D.C., Ungar, L.H.: Iterative combinatorial auctions: theory and practice. In: Proc. 17th National Conference on Artificial Intelligence (AAAI 2000), pp. 74–81 (2000)
Sun, N., Yang, Z.: A double-track adjustment process for discrete markets with substitutes and complements. Econometrica 77, 933–952 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Murota, K., Shioura, A., Yang, Z. (2013). Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_44
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)