×

A pricing scheme for combinatorial auctions based on bundle sizes. (English) Zbl 1394.91155

Summary: In combinatorial auctions not only single items but also bundles of items are sold simultaneously. A substantial ingredient to an auction mechanism is the way prices of bundles are determined. Prices determine the auctioneers revenue and, ideally, justify the outcome of the auction to the bidder. Each bidder should be able to see why he won or lost a certain bundle comparing the determined price for a bundle and his bids value. It is well known that linear prices cannot guarantee such a justification. We propose a new pricing scheme adding prices for bundle sizes to the traditional linear prices for items. We analyze this scheme and evaluate its ability to provide prices supporting a given allocation by means of a computational study using a well established combinatorial auctions test suite. We also compare our scheme to a scheme from literature with respect to the ability to generate market clearing prices.

MSC:

91B26 Auctions, bargaining, bidding and selling, and other market models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alcaly, R. E.; Klevorick, A. K., A note on dual prices of integer programs, Econometrica, 34, 206-214, (1966)
[2] An, N.; Elmaghraby, W.; Keskinocak, P., Bidding strategies and their impact on revenues in combinatorial auctions, J Revenue Pricing Manag, 3, 337-357, (2005)
[3] Ausubel LM, Milgrom P. The lovely but lonely Vickrey auction. In: Cramton et al. [11]; 2006. p. 17-40.
[4] Bichler M, Shabalin P, Ziegler G. Efficiency with linear prices: a theoretical and experimental analysis of the combinatorial clock auction. In: Proceedings of the 11th ACM conference on electronic commerce (EC ׳10). ACM, 2010. p. 285-6.
[5] Bichler, M.; Shabalin, P.; Ziegler, G., Efficiency with linear prices? A game-theoretical and computational analysis of the combinatorial clock auction, Inf Syst Res, 24, 394-417, (2013)
[6] Bikhchandani, S.; Ostroy, J. M., The package assignment model, J Econ Theory, 107, 377-406, (2002) · Zbl 1033.90064
[7] Bikhchandani S, Ostroy JM. From the assignment model to combinatorial auctions. In: Cramton et al. [11]; 2006. p. 189-214.
[8] Briskorn D, Jørnsten K, Nossack J. Pricing combinatorial auctions by a set of linear price vectors. Working Paper; 2014. · Zbl 1349.91116
[9] Cantillon E, Pesendorfer M. Auctioning bus routes: the London experience. In: Cramton et al. [11]; 2006. p. 573-92.
[10] Chu, C. S.; Leslie, P.; Sorensen, A., Bundle-size pricing as an approximation to mixed bundling, Am Econ Rev, 101, 263-303, (2011)
[11] (Cramton, P.; Shoham, Y.; Steinberg, R., Combinatorial auctions, (2006), MIT Press Cambridge) · Zbl 1194.91018
[12] Day, R. W.; Milgrom, P., Core-selecting package auctions, Int J Game Theory, 36, 3-4, 393-407, (2008) · Zbl 1151.91073
[13] Day, R. W.; Raghavan, S., Fair payments for efficient allocations in chapter 22 sector combinatorial auctions, Manag Sci, 53, 9, 1389-1406, (2007) · Zbl 1232.91286
[14] de Vries, S.; Vohra, R. V., Combinatorial auctionsa survey, INFORMS J Comput, 15, 3, 284-309, (2003) · Zbl 1238.91003
[15] Drexl, A.; Jørnsten, K., Reflections about pseudo-dual prices in combinatorial auctions, J Oper Res Soc, 58, 1652-1659, (2007) · Zbl 1141.91397
[16] Drexl, A.; Jørnsten, K.; Knof, D., Non-linear anonymous pricing combinatorial auctions, Eur J Oper Res, 199, 296-302, (2009) · Zbl 1176.91056
[17] Dunford M, Hoffman K, Menon D, Sultana R, Wilson T. Testing linear pricing algorithms for use in ascending combinatorial auctions. Technical Report, George Mason University; 2007.
[18] Gomory, R. E.; Baumol, W. J., Integer programming and pricing, Econometrica, 28, 521-550, (1960) · Zbl 0095.14502
[19] Hoffman, K., Choosing a combinatorial auction designan illustrated example, (Alt, F. B.; Fu, M. C.; Golden, B. L.; Sharda, R.; Voß, S., Perspectives in operations research, operations research/computer science interfaces series, vol. 36, (2006), Springer US), 153-177
[20] Kwasnica, A. M.; Ledyard, J. O.; Porter, D.; DeMartini, C., A new and improved design for multiobject iterative auctions, Manag Sci, 51, 419-434, (2005) · Zbl 1232.91317
[21] Lahaie S. A kernel method for market clearing. In: Proceedings of the 21st international joint conference on artificial intelligence (IJCAI׳09). San Francisco (CA, USA): Morgan Kaufmann Publishers Inc.; 2009. p. 208-13.
[22] Ledyard JO. Optimal combinatoric auctions with single-minded bidders. In: Proceedings of the 8th ACM conference on electronic commerce (EC ׳07). New York (NY, USA): ACM; 2007. p. 237-42.
[23] Ledyard, J. O.; Olson, M.; Porter, D.; Swanson, J. A.; Torma, D. P., The first use of a combined-value auction for transportation services, Interfaces, 32, 4-12, (2002)
[24] Lehmann D, Müller R, Sandholm T. The winner determination problem. In: Cramton et al. [11]; 2006. p. 297-318.
[25] Leyton-Brown K. Cats website, URL 〈http://www.cs.ubc.ca/ kevinlb/CATS/〉; July 2011.
[26] Leyton-Brown K, Shoham Y. A test suite for combinatorial auctions. In: Cramton et al. [11]; 2006. p. 451-78.
[27] Martin, A.; Müller, J. C.; Pokutta, S., Strict linear prices in non-convex European day-ahead electricity markets, Optim Methods Softw, 29, 1, 189-221, (2014) · Zbl 1282.90110
[28] Meeus, L.; Verhaegen, K.; Belmans, R., Block order restrictions in combinatorial electric energy auctions, Eur J Oper Res, 196, 1202-1206, (2009) · Zbl 1176.90419
[29] Müller R. Tractable cases of the winner determination problem. In: Cramton et al. [11]; 2006. p. 319-36.
[30] Parkes D. iBundle: an efficient ascending price bundle auction. In: Proceedings of the 1st ACM conference on electronic commerce; 1999. p. 148-57.
[31] Parkes DC. Iterative combinatorial auctions. In: Cramton et al. [11]; 2006. p. 41-78.
[32] Rassenti, S. J.; Smith, V. L.; Bulfin, R. L., A combinatorial auction mechanism for airport time slot allocation, Bell J Econ, 13, 402-417, (1982)
[33] Sandholm T. Optimal winner determination algorithms. In: Cramton et al. [11]; 2006. p. 337-68.
[34] Scheffel, T.; Pikovsky, A.; Bichler, M.; Guler, K., An experimental comparison of linear and nonlinear price combinatorial auctions, Inf Syst Res, 22, 346-368, (2011)
[35] Wolsey, L. A., Integer programming dualityprice functions and sensitivity analysis, Math Program, 20, 173-195, (1981) · Zbl 0458.90047
[36] Wurman PR, Wellman MP. Akba: a progressive, anonymous-price combinatorial auction. In: ACM conference on electronic commerce; 2000. p. 21-9.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.