zbMATH — the first resource for mathematics

Bundling equilibrium in combinatorial auctions. (English) Zbl 1077.91023
Summary: This paper analyzes ex post equilibria in the VCG combinatorial auctions. If \(\Sigma\) is a family of bundles of goods, the organizer may restrict the bundles on which the participants submit bids, and the bundles allocated to them, to be in \(\Sigma\). The \(\Sigma\)-VCG combinatorial auctions obtained in this way are known to be truth-telling mechanisms. In contrast, this paper deals with non-restricted VCG auctions, in which the buyers choose strategies that involve bidding only on bundles in \(\Sigma\), and these strategies form an equilibrium. We fully characterize those \(\Sigma\) that induce an equilibrium in every VCG auction, and we refer to the associated equilibrium as a bundling equilibrium. The main motivation for studying all these equilibria, and not just the domination equilibrium, is that they afford a reduction of the communication complexity. We analyze the tradeoff between communication complexity and economic efficiency of bundling equilibrium.

91B26 Auctions, bargaining, bidding and selling, and other market models
Full Text: DOI
[1] Anderson, A.; Tenhunen, M.; Ygge, F., Integer programming for combinatorial auction winner determination, (), 39-46
[2] Ausubel, L., 2000. An efficient dynamic auction for heterogeneous commodities. Mimeo. Univ. of Maryland
[3] Ausubel, L., Milgrom, P., 2001. Ascending auctions with package bidding. Mimeo. Univ. of Maryland
[4] Ausubel, L.M.; Cramton, P., The optimality of being efficient, Univ. of Maryland. Available from
[5] Ausubel, L.M.; Cramton, P., Vickrey auctions with reserve pricing, Univ. of Maryland. Available from · Zbl 1068.91018
[6] Bikhchandani, S.; Vries, S.; Schummer, J.; Vohra, R., Linear programming and vickrey auctions, Available from · Zbl 1012.91019
[7] Boutilier, C.; Hoos, H.H., Bidding languages for combinatorial auctions, (), 1211-1216
[8] Clarke, E., Multipart pricing of public goods, Public choice, 18, 19-33, (1971)
[9] Cramton, P.C., Money out of thin air: the nationwide narrowband pcs auction, J. econ. manage. strategy, (1995)
[10] Dasgupta, P.; Maskin, E., Efficient auctions, Quart. J. econ., 65, 341-388, (2000) · Zbl 0960.91029
[11] de Vries, S., Vohra, R., 2000. Combinatorial auctions: a brief survey. Unpublished manuscript · Zbl 1238.91003
[12] Dembowski, P., Finite geometries, (1968), Springer · Zbl 0159.50001
[13] Ephrati, E.; Rosenschein, J., The Clarke tax as a consensus mechanism among automated agents, (), 173-178
[14] Fujishima, Y.; Leyton-Brown, K.; Shoham, Y., Taming the computational complexity of combinatorial auctions: optimal and approximate approaches, Ijcai-99, (1999)
[15] Füredi, Z., Covering pairs by q2+q+1 sets, J. combin. theory ser. A, 54, 2, 248-271, (1990) · Zbl 0734.05033
[16] Groves, T., Incentives in teams, Econometrica, 41, 617-631, (1973) · Zbl 0311.90002
[17] Gul, F.; Stacchetti, E., Walrasian equilibrium with Gross substitutes, J. econ. theory, 87, 95-124, (1999) · Zbl 0998.91010
[18] Gul, F.; Stacchetti, E., The English auction with differentiated commodities, J. econ. theory, 92, 1, 66-95, (2000) · Zbl 0962.91027
[19] Holzman, R.; Monderer, D., Characterization of ex post equilibrium in the VCG combinatorial auctions, Working paper. Technion. Available from · Zbl 1078.91007
[20] Hon-Snir, S.; Monderer, D.; Sela, A., A learning approach to auctions, J. econ. theory, 82, 65-88, (1998) · Zbl 0910.90119
[21] Hoos, H.H.; Boutilier, C., Solving combinatorial auctions using stochastic local search, (), 22-29
[22] Hurwicz, L., On the dimensional requirements of informationally decentralized Pareto-satisfactory processes, (), 413-424
[23] Jehiel, P.; Moldovanu, B., Efficient design with interdependent valuations, Econometrica, 69, 1237-1259, (2001) · Zbl 1055.91517
[24] Krishna, V., Perry, M., 1998. Efficient mechanism design. Working paper
[25] Kushilevitz, E.; Nisan, N., Communication complexity, (1997), Cambridge Univ. Press · Zbl 0869.68048
[26] Lehmann, D.; O’Callaghan, L.I.; Shoham, Y., Truth revelation in rapid, approximately efficient combinatorial auctions, () · Zbl 1326.91011
[27] McAfee, P.R.; Reny, P., Correlated information and mechanism design, Econometrica, 60, 395-421, (1992) · Zbl 0761.90024
[28] McMillan, J., Selling spectrum rights, J. econ. perspect., 8, 145-162, (1994)
[29] Milgrom, P., 1998. Putting auction theory to work: The simultaneous ascending auction. Technical report 98-0002. Department of Economics, Stanford University
[30] Milgrom, P.; Weber, R.J., A theory of auctions and competitive bidding, Econometrica, 50, 1089-1122, (1982) · Zbl 0487.90017
[31] Monderer, D.; Tennenholtz, M., Asymptotically optimal multi-object auctions, Working paper. Technion. Available from · Zbl 0947.68564
[32] Myerson, R., Incentive compatibility and the bargaining problem, Econometrica, 47, 61-74, (1979) · Zbl 0399.90008
[33] Myerson, R., Optimal auction design, Math. oper. res., 6, 58-73, (1981) · Zbl 0496.90099
[34] Nisan, N., Bidding and allocation in combinatorial auctions, ACM conference on electronic commerce, (2000)
[35] Nisan, N.; Ronen, A., Algorithmic mechanism design, Games econ. behav., 35, 166-196, (2001) · Zbl 0996.68251
[36] Nisan, N., Segal, I., 2002. The communication complexity of efficient allocation problems. Working paper
[37] Parkes, D.C., I-bundle: an efficient ascending price bundle auction, ACM conference on electronic commerce, (1999)
[38] Parkes, D.C.; Ungar, L.H., Iterative combinatorial auctions: theory and practice, (), 74-81
[39] Perry, M., Reny, P., 1999. An ex post efficient multi-unit ascending auction for agents with interdependent valuations. Working paper. Univ. of Chicago
[40] Perry, M., Reny, P., 1999a. An ex post efficient multi-unit auction for agents with interdependent valuations. Working paper. Univ. of Pittsburgh
[41] Rothkopf, M.H.; Pekec, A.; Harstad, R.M., Computationally manageable combinatorial auctions, Manage. sci., 44, 8, 1131-1147, (1998) · Zbl 0989.90094
[42] Sandholm, T., An algorithm for optimal winner determination in combinatorial auctions, Ijcai-99, (1999)
[43] Sandholm, T.; Suri, S.; Gilpin, A.; Levine, D., Cabob: A fast optimal algorithm for combinatorial auctions, (), 1102-1108
[44] Shapley, L.S., On balanced sets and cores, Naval res. logist., 14, 453-460, (1967)
[45] Shoham, Y.; Tennenholtz, M., On rational computability and communication complexity, Games econ. behav., 35, 197-211, (2001) · Zbl 1103.91323
[46] Tennenholtz, M., Electronic commerce: from game-theoretic and economic models to working protocols, Ijcai-99, (1999)
[47] Tennenholtz, M., Some tractable combinatorial auctions, () · Zbl 0999.68003
[48] Varian, H.R., Economic mechanism design for computerized agents, ()
[49] Vickrey, W., Counterspeculations, auctions, and competitive sealed tenders, J. finance, 16, 15-27, (1961)
[50] Weber, R.J., Multiple-object auctions, (), 165-191
[51] Wellman, M.P.; Wurman, P.R.; Walsh, W.E.; MacKie-Mason, J.K., Auction protocols for decentralized scheduling, Games econ. behav., 35, 271-303, (2001) · Zbl 0996.90047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.