×

Strong activity rules for iterative combinatorial auctions. (English) Zbl 1178.90289

Summary: Activity rules have emerged in recent years as an important aspect of practical auction design. The role of an activity rule in an iterative auction is to suppress strategic behavior by bidders and promote simple, continual, meaningful bidding and thus, price discovery. These rules find application in the design of iterative combinatorial auctions for real world scenarios, for example in spectrum auctions, in airline landing slot auctions, and in procurement auctions. We introduce the notion of strong activity rules, which allow simple, consistent bidding strategies while precluding all behaviors that cannot be rationalized in this way. We design such a rule for auctions with budget-constrained bidders, i.e., bidders with valuations for resources that are greater than their ability to pay. Such bidders are of practical importance in many market environments, and hindered from bidding in a simple and consistent way by the commonly used revealed-preference activity rule, which is too strong in such an environment. We consider issues of complexity, and provide two useful forms of information feedback to guide bidders in meeting strong activity rules. As a special case, we derive a strong activity rule for non-budget-constrained bidders. The ultimate choice of activity rule must depend, in part, on beliefs about the types of bidders likely to participate in an auction event because one cannot have a rule that is simultaneously strong for both budget-constrained bidders and quasi-linear bidders.

MSC:

90C27 Combinatorial optimization
91B26 Auctions, bargaining, bidding and selling, and other market models
91B16 Utility theory

Software:

CABOB
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006.; Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006. · Zbl 1194.91018
[2] Parkes DC. Iterative combinatorial auctions. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 2].; Parkes DC. Iterative combinatorial auctions. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 2].
[3] Cramton, P. C., Money out of thin air: the nationwide narrowband PCS auction, Journal of Economics and Management Strategy, 4, 267-343 (1995)
[4] Ball MO, Donohue G, Hoffman K. Auctions for the safe, efficient and equitable allocation of airspace resources. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 20].; Ball MO, Donohue G, Hoffman K. Auctions for the safe, efficient and equitable allocation of airspace resources. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 20].
[5] Ausubel LM, Cramton P, Milgrom P. The clock-proxy auction: a practical combinatorial auction design. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 5].; Ausubel LM, Cramton P, Milgrom P. The clock-proxy auction: a practical combinatorial auction design. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 5].
[6] Milgrom, P., Putting auction theory to work: the simultaneous ascending auction, Journal of Political Economy, 108, 245-272 (2000)
[7] Wilson, R., Activity rules for an iterated double auction, (Samuelson, W. F.; Chatterjee, K., Game theory and business applications (2001), Springer: Springer Berlin), [Chapter 12]
[8] Ausubel, L. M.; Milgrom, P., Ascending auctions with package bidding, Frontiers of Theoretical Economics, 1, 1, 1-42 (2002)
[9] Parkes DC, Ungar LH. Iterative combinatorial auctions: theory and practice. In: Proceedings of the national conference on artificial intelligence, 2000. p. 74-81.; Parkes DC, Ungar LH. Iterative combinatorial auctions: theory and practice. In: Proceedings of the national conference on artificial intelligence, 2000. p. 74-81.
[10] Ausubel, L. M., An efficient ascending-bid auction for multiple objects, American Economic Review, 94, 5, 1452-1475 (2004)
[11] Mishra, D.; Parkes, D. C., Ascending price Vickrey auctions for general valuations, Journal of Economic Theory, 127, 1, 335-366 (2007) · Zbl 1142.91492
[12] de Vries, S.; Schummer, J.; Vohra, R. V., On ascending Vickrey auctions for heterogeneous objects, Journal of Economic Theory, 127, 1, 95-118 (2007) · Zbl 1142.91474
[13] Cramton P. The revealed preference activity rule. Working paper, 2007.; Cramton P. The revealed preference activity rule. Working paper, 2007.
[14] Ball MO, Ausubel LM, Berardino F, Donohue G, Hansen M, Hoffman K. Market-based alternatives for managing congestion at New York’s LaGuardia Airport. In: Proceedings of AirNeth annual conference, 2007.; Ball MO, Ausubel LM, Berardino F, Donohue G, Hansen M, Hoffman K. Market-based alternatives for managing congestion at New York’s LaGuardia Airport. In: Proceedings of AirNeth annual conference, 2007.
[15] ATA, Outlook: reaching for the skies? Air Transport Association, 2007.; ATA, Outlook: reaching for the skies? Air Transport Association, 2007.
[16] Belobaba P. Impacts of 9/11 on US airline performance. In: MIT research and development conference, 2005.; Belobaba P. Impacts of 9/11 on US airline performance. In: MIT research and development conference, 2005.
[17] Salant, D. J., Up in the air: GTE’s experience in the MTA auction for personal communication services licenses, Journal of Economics and Management Strategy, 6, 3, 549-572 (1997)
[18] Pitchik C. Budget-constrained sequential auctions with incomplete information. Working paper, 2006.; Pitchik C. Budget-constrained sequential auctions with incomplete information. Working paper, 2006. · Zbl 1165.91388
[19] Che, Y.-K.; Gale, I., Standard auctions with financially constrained bidders, Review of Economic Studies, 65, 1, 1-21 (1998) · Zbl 0909.90121
[20] Porter, D.; Rassenti, S.; Roopnarine, A.; Smith, V., Combinatorial auction design, Proceedings of the National Academy of Sciences, 100, 10, 11153-11157 (2003) · Zbl 1063.91025
[21] Ausubel, L. M., An efficient dynamic auction for heterogeneous, American Economic Review, 96, 3, 602-629 (2006)
[22] Kwasnica, A. M.; Ledyard, J. O.; Porter, D.; DeMartini, C., A new and improved design for multiobject iterative auctions, Management Science, 51, 3, 419-434 (2005) · Zbl 1232.91317
[23] Wurman PR, Wellman MP, A \(k\); Wurman PR, Wellman MP, A \(k\)
[24] Laffont, J.-J.; Robert, J., Optimal auctions with financially constrained buyers, Economic Letters, 52, 181-186 (1996) · Zbl 0875.90278
[25] Che, Y.-K.; Gale, I., The optimal mechanism for selling to a budget-constrained buyer, Journal of Economic Theory, 92, 198-233 (2000) · Zbl 0998.91017
[26] Maskin, E. S., Auctions, development and privatization: efficient auctions with liquidity-constrained bidders, European Economic Review, 44, 667-681 (2000)
[27] Benoit, J.-P.; Krishna, V., Multiple-object auctions with budget-constrained bidders, Refiew of Economic Studies, 68, 155-179 (2001) · Zbl 1114.91314
[28] Borgs C, Chayes J, Immorlica N, Mahdian M, Saberi A. Multi-unit auctions with budget-constrained bidders. In: Proceedings of the ACM conference on electronic commerce, 2005. p. 44-51.; Borgs C, Chayes J, Immorlica N, Mahdian M, Saberi A. Multi-unit auctions with budget-constrained bidders. In: Proceedings of the ACM conference on electronic commerce, 2005. p. 44-51.
[29] Dobzinski S, Lavi R, Nisan N. Multi-unit auctions with budget limits. In: Proceedings of 49th annual IEEE symposium on foundations of computer science, 2008. p. 260-9.; Dobzinski S, Lavi R, Nisan N. Multi-unit auctions with budget limits. In: Proceedings of 49th annual IEEE symposium on foundations of computer science, 2008. p. 260-9. · Zbl 1279.91080
[30] Pai MM, Vohra R. Optimal auctions with financially constrained bidders. Technical Report, Kellogg School of Management, Northwestern University; 2008.; Pai MM, Vohra R. Optimal auctions with financially constrained bidders. Technical Report, Kellogg School of Management, Northwestern University; 2008.
[31] Aggarwal G, Muthukrishnan S, Pal D, Pal M. General auction mechanism for search advertising, Technical Report CoRR abs/0807.1297, Google; 2008.; Aggarwal G, Muthukrishnan S, Pal D, Pal M. General auction mechanism for search advertising, Technical Report CoRR abs/0807.1297, Google; 2008.
[32] Ausubel LM, Milgrom P. Ascending proxy auctions. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 3].; Ausubel LM, Milgrom P. Ascending proxy auctions. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 3].
[33] Kornai, J.; Maskin, E.; Roland, G., Understanding the soft budget constraint, Journal of Economic Literature, 41, 4, 1095-1136 (2003)
[34] Afriat, S. N., The construction of utility functions from expenditure data, International Economic Review, 8, 1, 67-77 (1967) · Zbl 0248.90001
[35] Vohra R. Paths, cycles and mechanism design, Technical Report, Kellogg School of Management; 2007.; Vohra R. Paths, cycles and mechanism design, Technical Report, Kellogg School of Management; 2007.
[36] Day RW. A revealed-preference activity rule for quasi-linear utilities with budget constraints. Working paper, 2007.; Day RW. A revealed-preference activity rule for quasi-linear utilities with budget constraints. Working paper, 2007.
[37] Cramton, P., Ascending auctions, European Economic Review, 42, 3-5, 745-756 (1998)
[38] Cramton P, Stoft S. Colombia firm energy market. In: Proceedings of the Hawaii international conference on system sciences, 2007.; Cramton P, Stoft S. Colombia firm energy market. In: Proceedings of the Hawaii international conference on system sciences, 2007.
[39] Leyton-Brown K, Shoham Y. A test suite for combinatorial auctions. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 18].; Leyton-Brown K, Shoham Y. A test suite for combinatorial auctions. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge, MA: MIT Press; 2006 [Chapter 18].
[40] Sandholm, T., Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, 135, 1-2, 1-54 (2002) · Zbl 0984.68039
[41] Sandholm, T.; Suri, S.; Gilpin, A.; Levine, D., CABOB: a fast optimal algorithm for winner determination in combinatorial auctions, Management Science, 51, 3, 374-391 (2005) · Zbl 1232.91329
[42] Pikovsky A, Shabalin P, Bichler M. Iterative combinatorial auctions with linear prices: results of numerical experiments. In: Proceedings of the 8th IEEE international conference on E-commerce technology, 2006. p. 39.; Pikovsky A, Shabalin P, Bichler M. Iterative combinatorial auctions with linear prices: results of numerical experiments. In: Proceedings of the 8th IEEE international conference on E-commerce technology, 2006. p. 39.
[43] Hoffman K. Hybrid clock proxy auction—implementation details. Private Correspondence, 2004.; Hoffman K. Hybrid clock proxy auction—implementation details. Private Correspondence, 2004.
[44] Gibbard, A., Manipulation of voting schemes: a general result, Econometrica, 41, 587-602 (1973) · Zbl 0325.90081
[45] Satterthwaite, M. A., Strategy-proofness and arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions, Journal of Economic Theory, 10, 187-217 (1975) · Zbl 0315.90088
[46] Dong R. Combinatorial clock auction for airport time slots: an agent-based analysis. Technical Report, Harvard University, senior thesis; 2005.; Dong R. Combinatorial clock auction for airport time slots: an agent-based analysis. Technical Report, Harvard University, senior thesis; 2005.
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.