Abstract
In a combinatorial auction (CA) with item bidding, several goods are sold simultaneously via single-item auctions. We study how the equilibrium performance of such an auction depends on the choice of the underlying single-item auction. We provide a thorough understanding of the price of anarchy, as a function of the single-item auction payment rule.
When the payment rule depends on the winner’s bid, as in a first-price auction, we characterize the worst-case price of anarchy in the corresponding CAs with item bidding in terms of a sensitivity measure of the payment rule. As a corollary, we show that equilibrium existence guarantees broader than that of the first-price rule can only be achieved by sacrificing its property of having only fully efficient (pure) Nash equilibria.
For payment rules that are independent of the winner’s bid, we prove a strong optimality result for the canonical second-price auction. First, its set of pure Nash equilibria is always a superset of that of every other payment rule. Despite this, its worst-case POA is no worse than that of any other payment rule that is independent of the winner’s bid.
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
Babaioff, M., Lavi, R., Pavlov, E.: Single-value combinatorial auctions and algorithmic implementation in undominated strategies. Journal of the ACM (JACM) 56(1) (2009)
Bhawalkar, K., Roughgarden, T.: Welfare guarantees for combinatorial auctions with item bidding. In: ACM Symposium on Discrete Algorithms, pp. 700–709. SIAM, Philadelphia (2011)
Blumrosen, L., Nisan, N.: Combinatorial auctions. In: Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V. (eds.) Algorithmic Game Theory, ch. 11, pp. 267–300. Cambridge University Press (2007)
Boyan, J., Greenwald, A.: Bid determination in simultaneous auctions: An agent architecture. In: Third ACM Conference on Electronic Commerce, pp. 210–212 (2001)
Christodoulou, G., Kovács, A., Schapira, M.: Bayesian Combinatorial Auctions. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 820–832. Springer, Heidelberg (2008)
Crampton, P., Shoham, Y., Steinberg, R.: Combinatorial Auctions. MIT Press (2006)
Dobzinski, S.: An impossibility result for truthful combinatorial auctions with submodular valuations. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 139–148. ACM, New York (2011)
Dughmi, S., Roughgarden, T., Yan, Q.: From convex optimization to randomized mechanisms: toward optimal combinatorial auctions. In: STOC, pp. 149–158 (2011)
Dughmi, S., Vondrák, J.: Limitations of randomized mechanisms for combinatorial auctions. In: FOCS, pp. 502–511 (2011)
Fu, H., Kleinberg, R., Lavi, R.: Conditional equilibrium outcomes via ascending price processes (submission, 2012)
Gul, F., Stacchetti, E.: Walrasian equilibrium with gross substitutes. Journal of Economic Theory 87(1), 95–124 (1999)
Hassidim, A., Kaplan, H., Mansour, M., Nisan, N.: Non-price equilibria in markets of discrete goods. In: 12th ACM Conference on Electronic Commerce (EC), pp. 295–296. ACM, New York (2011)
Kagel, J.H., Levin, D.: Independent private value auctions: Bidder behaviour in first-, second-, and third-price auctions with varying numbers of bidders. The Economic Journal 103, 868–879 (1993)
Kelso, A.S., Crawford, V.P.: Job matching, coalition formation, and gross substitutes. Econometrica 50, 1483–1504 (1982)
Paes Leme, R., Tardos, É.: Pure and Bayes-Nash price of anarchy for generalized second price auction. In: 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 735–744 (2010)
Leme, R.P., Syrgkanis, V., Tardos, É.: Sequential auctions and externalities. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 869–886 (2012)
Lucier, B., Borodin, A.: Price of anarchy for greedy auctions. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 537–553 (2010)
Monderer, D., Tennenholtz, M.: K-price auctions. Games and Economic Behavior 31(2), 220–244 (2000)
Monderer, D., Tennenholtz, M.: K-price auctions: Revenue inequalities, utility equivalence, and competition in auction design. Economic Theory 24(2), 255–270 (2004)
Syrgkanis, V., Tardos, É.: Bayesian sequential auctions. In: ACM Conference on Electronic Commerce, pp. 929–944 (2012)
Yoon, D.Y., Wellman, M.P.: Self-confirming price prediction for bidding in simultaneous second-price sealed-bid auctions. In: IJCAI 2011 Workshop on Trading Agent Design and Analysis (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bhawalkar, K., Roughgarden, T. (2012). Simultaneous Single-Item Auctions. In: Goldberg, P.W. (eds) Internet and Network Economics. WINE 2012. Lecture Notes in Computer Science, vol 7695. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35311-6_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-35311-6_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35310-9
Online ISBN: 978-3-642-35311-6
eBook Packages: Computer ScienceComputer Science (R0)