ICE: An Expressive Iterative Combinatorial Exchange

doi:10.1017/9781316471609.040

39 - ICE: An Expressive Iterative Combinatorial Exchange

from Part VI - Secondary Markets and Exchanges

Published online by Cambridge University Press: 26 October 2017

Jeffrey Shneidman and

David C. Parkes

Edited by

Martin Bichler and

Jacob K. Goeree

Show author details

Benjamin Lubin: Affiliation:
Information Systems Department, Questrom School of Business, Boston University
Adam I. Juda: Affiliation:
Google
Ruggiero Cavallo: Affiliation:
Yahoo Research
Sébastien Lahaie: Affiliation:
Google
Jeffrey Shneidman: Affiliation:
Fish & Richardson
David C. Parkes: Affiliation:
Paulson School of Engineering and Applied Sciences, Harvard University
Martin Bichler: Affiliation:
Technische Universität München
Jacob K. Goeree: Affiliation:
University of New South Wales, Sydney

Book contents

Get access

Summary

Introduction

Combinatorial exchanges combine and generalize two different mechanisms: double auctions and combinatorial auctions. In a double auction (DA), multiple buyers and sellers trade units of an identical good (McAfee, 1992). In a combinatorial auction (CA), a single seller has multiple heterogeneous items up for sale (de Vries & Vohra, 2003; Cramton, Shoham, & Steinberg, 2006). Buyer valuations can exhibit complements (“I want A and B”) and substitutes (“I want A or B”) properties. CAs provide an expressive bidding language to describe buyer valuations. A common design goal in DAs and CAs is to implement the efficient allocation, which is the allocation that maximizes social welfare, i.e. the total value.

A combinatorial exchange (CE) (Parkes, Kalagnanam, & Eso, 2001) is a combinatorial double auction and allows multiple buyers and sellers to trade on multiple, heterogeneous goods. A motivating application is to the reallocation of U.S. wireless spectrum from low-volume television stations to digital cell phone services (Cramton, Kwerel, & Williams, 1998; Cramton, Lopez, Malec, & Sujarittanonta, 2015). An incentive auction has been proposed for this application. This auction design uses a reverse auction to buy back existing spectrum rights followed by a forward auction to sell these rights to new owners. (See “Designing the US Incentive Auction” by Mulgrom and Segal.) One advantage of the incentive auction design is that it enables the use of existing CA technology for both the forward and reverse stages. In addition, the proposed design uses optimization to solve the complex repacking problem of shifting incumbent users’ allocation to new bands, which can free up a significant amount of bandwidth (Frechette, Newman, & Leyton-Brown, 2015).

CEs present an alternative design where both demand-side and supply-side price discovery happen in tandem, leading to coordinated information revelation and potential efficiency gains. The separation between stages in an incentive auction opens the possibility of the government purchasing either too little or too much spectrum in the reverse stage for subsequent sale in the forward stage. CEs avoid this problem by enabling the simultaneous purchase and sale of bandwidth by incumbents and new entrants alike. The (approximate) clearing prices obtained in CEs also provide meaningful value estimates for various spectrum combinations. These prices are useful in guiding demand and supply revelation (or preference elicitation, in the language of computer science).

Information

Type: Chapter
Information: Handbook of Spectrum Auction Design , pp. 828 - 873
DOI: https://doi.org/10.1017/9781316471609.040 [Opens in a new window]
Publisher: Cambridge University Press
Print publication year: 2017

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

Ausubel, L., Cramton, P., & Milgrom, P. 2006. The clock-proxy auction: A practical combinatorial auction design. In Cramton, P., Shoham, Y., & Steinberg, R. (Eds.). Combinatorial Auctions. MIT Press, chap. 5. Ausubel, L. M., & Milgrom, P. 2002. Ascending auctions with package bidding. Frontiers of TheoreticalEconomics, 1, 1–42.Google Scholar

Babaioff, M., & Walsh, W. E. 2005. Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation. Decision Support Systems, 39, 123–149.Google Scholar

Ball, M.,Donohue, G., & Hoffman, K. 2006. Auctions for the safe, efficient, and equitable allocation of airspace system resources. In Cramton, P., Shoham, Y., & Steinberg, R. (Eds.). CombinatorialAuctions . MIT Press, chap. 20.

Ball, M. O., Ausubel, L. M., Berardino, F., Cramton, P., Donohue, G., Hansen, M., & Hoffman, K. 2007. Market-based alternatives for managing congestion at new york's laguardia airport.

Ball, M. O., Ausubel, L. M., Berardino, F., Cramton, P., Donohue, G., Hansen, M., & Hoffman, K. 2007. Market-based alternatives for managing congestion at new york's laguardia airport. In Proceedings of the AirNeth Annual Conference.

Bererton, C., Gordon, G., & Thrun, S. 2003. Auction mechanism design for multi-robot coordination. In Proceedings of the 17th Annual Conference on Neural Information Processing Systems(NIPS-03).

Bertsimas, D., & Tsitsiklis, J. 1997. Introduction to Linear Optimization . Athena Scientific.

Bikhchandani, S., & Mamer, J. W. 1997. Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory, 74, 385–413.Google Scholar

Bikhchandani, S., & Ostroy, J. M. 2002. The package assignment model. Journal of EconomicTheory, 107(2), 377–406.Google Scholar

Blum, A., Sandholm, T., & Zinkevich, M. 2006. Online algorithms for market clearing. Journal ofthe ACM, 53, 845–879.Google Scholar

Bossaerts, P., Fine, L., & Ledyard, J. 2002. Inducing liquidity in thin financial markets through combined-value trading mechanisms. European Economic Review, 46(9), 1671–1695.Google Scholar

Boutilier, C. 2002. Solving concisely expressed combinatorial auction problems. In Proceedings ofthe 18th Conference of the Association for the Advancement of Artificial Intelligence (AAAI-02), pp. 359–366.

Boutilier, C., & Hoos, H. 2001. Bidding languages for combinatorial auctions. In Proceedingsof the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), pp. 1121–1217.

Bredin, J., Parkes, D. C., & Duong, Q. 2007. Chain: A dynamic double auction framework for matching patient agents. Journal of Artificial Intelligence Research, 30, 133–179.Google Scholar

Cavallo, R., Parkes, D. C., Juda, A. I., Kirsch, A., Kulesza, A., Lahaie, S., Lubin, B., Michael, L., & Shneidman, J. 2005. TBBL: A tree-based bidding language for iterative combinatorial exchanges. In Multi-Disciplinary Workshop on Advances in Preference Handling (IJCAI-05).

Chu, L. Y., & Shen, Z.-J. M. 2008. Truthful double auction mechanisms. Operations Research, 56(1), 102–120.Google Scholar

Compte, O., & Jehiel, P. 2007. Auctions and information acquisition: Sealed-bid or Dynamic Formats?. RAND Journal of Economics, 38(2), 355–372.Google Scholar

Conen, W., & Sandholm, T. 2001. Preference elicitation in combinatorial auctions. In Proceedingsof the 3rd ACM Conference on Electronic Commerce (EC-01) , pp. 256–259. ACM.

Cramton, P. 2003. Electricity Market Design: The Good, the Bad, and the Ugly. In Proceedings ofthe Hawaii International Conference on System Sciences.

Cramton, P. 2006. Simultaneous ascending auctions. In Cramton, P., Shoham, Y., & Steinberg, R. (Eds.). Combinatorial Auctions . MIT Press, chap. 3.

Cramton, P., Kwerel, E., & Williams, J. 1998. Efficient relocation of spectrum incumbents. Journalof Law and Economics, 41, 647–675.Google Scholar

Cramton, P., Lopez, H., Malec, D., & Sujarittanonta, P. 2015. Design of the reverse auction in the fcc incentive auction. Available at: http://www.cramton.umd.edu/papers2015–2019/cramton-reverseauction- design-fcc-comment-pn.pdf.

Cramton, P., Shoham, Y., & Steinberg, R. (Eds.). 2006. Combinatorial Auctions . MIT Press.

Day, R., & Raghavan, S. 2007. Fair payments for efficient allocations in public sector combinatorial auctions. Management Science , 53(9), 1389.Google Scholar

de Vries, S., Schummer, J., & Vohra, R. V. 2007. On ascending Vickrey auctions for heterogeneous objects. Journal of Economic Theory, 132, 95–118.Google Scholar

de Vries, S., & Vohra, R. V. 2003. Combinatorial auctions: A survey. INFORMS Journal on Computing, 15(3), 284–309.Google Scholar

Dias, M., Zlot, R., Kalra, N., & Stentz, A. 2006. Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE, 94, 1257–1270.Google Scholar

Dunford, M., Hoffman, K., Menon, D., Sultana, R., & Wilson, T. 2003. Testing linear pricing algorithms for use in ascending combinatorial auctions. Tech. rep., SEOR, George Mason University.

Fan, M., Stallaert, J., & Whinston, A. B. 1999. A web-based financial trading system. Computer, 32(4), 64–70.Google Scholar

Frechette, A., Newman, N., & Leyton-Brown K.; 2015. Solving the station repacking problem. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI-15).

Fu, Y., Chase, J., Chun, B., Schwab, S., & Vahdat, A. 2003. SHARP: an architecture for secure resource peering. In Proceedings of the 19th ACM Symposium on Operating Systems Principles(SOSP-03), pp. 133–148. ACM.

Gerkey, B. P., & Mataric, M. J. 2002. Sold!: Auction methods for multi-robot coordination. IEEE Transactions on Robotics and Automation, Special Issue on Multi-robot Systems, 18, 758–768.Google Scholar

Hudson, B., & Sandholm, T. 2004. Effectiveness of query types and policies for preference elicitation in combinatorial auctions. In Proceedings of the 3rd International Joint Conference onAutonomous Agents and Multi-Agent Systems (AAMAS-04), pp. 386–393.

Kelso, A. S., & Crawford, V. P. 1982. Job matching, coalition formation, and gross substitutes. Econometrica, 50, 1483–1504.Google Scholar

Krishna, V. 2002. Auction Theory . Academic Press.

Kwasnica, A.M., Ledyard, J. O., Porter, D., & DeMartini, C. 2005. A new and improved design for multi-object iterative auctions. Management Science, 51, 419–434.Google Scholar

Kwerel, E., & Williams, J. 2002. A proposal for a rapid transition to market allocation of spectrum. Tech. rep., FCC Office of Plans and Policy.

Lahaie, S., Constantin, F., & Parkes, D. C. 2005. More on the power of demand queries in combinatorial auctions: Learning atomic languages and handling incentives. In Proceedings of the 19thInternational Joint Conference on Artificial Intelligence (IJCAI-05).

Lahaie, S., & Parkes, D. C. 2004. Applying learning algorithms to preference elicitation. In Proceedingsof the 5th ACM Conference on Electronic Commerce (EC-04), pp. 180–188.

Lubin, B. 2015. Games and metagames: Pricing rules for combinatorial mechanisms. Working Paper, Boston University.

Lubin, B., & Parkes, D. C. 2009. Quantifying the strategyproofness of mechanisms via metrics on payoff distributions. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pp. 349–358. AUAI Press.

McAfee, R. P. 1992.Adominant strategy double auction. Journal of Economic Theory , 56, 434–450.Google Scholar

Milgrom, P. 2004. Putting Auction Theory to Work . Cambridge University Press.

Milgrom, P. 2007. Package auctions and package exchanges (2004 Fisher-Schultz lecture). Econometrica, 75, 935–966.Google Scholar

Mishra, D., & Parkes, D. C. 2007. Ascending price Vickrey auctions for general valuations. Journalof Economic Theory, 132, 335–366.Google Scholar

Myerson, R. B., & Satterthwaite, M. A. 1983. Efficient mechanisms for bilateral trading. Journalof Economic Theory, 28, 265–281.Google Scholar

Nemhauser, G., & Wolsey, L. 1999. Integer and Combinatorial Optimization . Wiley-Interscience.

Nisan, N. 2006. Bidding languages for combinatorial auctions. In Cramton, P., Shoham, Y., & Steinberg, R. (Eds.). Combinatorial Auctions . MIT Press, chap. 9.

O'Neill, R. P., Sotkiewicz, P. M., Hobbs, B. F., Rothkopf,M. H., & Stewart, Jr.,W. R. 2005. Efficient market-clearing prices in markets with nonconvexities. European Journal of Operations Research, 164, 269–285.Google Scholar

Parkes, D. C. 2007. On-line mechanisms. In Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. (Eds.), Algorithmic Game Theory , chap. 16. Cambridge University Press.

Parkes, D. C., Kalagnanam, J. R., & Eso, M. 2001. Achieving budget-balance with Vickrey-based payment schemes in exchanges. In Proceedings of the 17th International Joint Conference on ArtificialIntelligence (IJCAI-01), pp. 1161–1168.

Parkes, D. C., & Ungar, L. H. (2000a). Iterative combinatorial auctions: Theory and practice. In Proceedingsof the 17th Conference of the Association for the Advancement of Artificial Intelligence(AAAI-00), pp. 74–81.

Parkes, D. C., & Ungar, L. H. (2000b). Preventing strategic manipulation in iterative auctions: Proxy agents and price-adjustment. In Proceedings of the 17th Conference of the Association for theAdvancement of Artificial Intelligence (AAAI-00), pp. 82–89.

Rassenti, S. J., Smith, V. L., & Bulfin, R. L. 1982. A combinatorial mechanism for airport time slot allocation. Bell Journal of Economics, 13, 402–417.Google Scholar

Rothkopf, M. H., Pekec, A., & Harstad, R. M. 1998. Computationally manageable combinatorial auctions. Management Science, 44(8), 1131–1147.Google Scholar

Saatcioglu, K., Stallaert, J., & Whinston, A. B. 2001. Design of a financial portal. Communicationsof the ACM, 44, 33–38.Google Scholar

Sandholm, T. 2006. Optimal winner determination algorithms. In Cramton, P., Shoham, Y., & Steinberg, R. (Eds.). Combinatorial Auctions . MIT Press, chap. 14.

Sandholm, T. 2007. Expressive Commerce and Its Application to Sourcing: How We Conducted $35 Billion of Generalized Combinatorial Auctions. AI Magazine , 28(3), 45.Google Scholar

Sandholm, T., & Boutilier, C. 2006. Preference elicitation in combinatorial auctions. In Cramton et al. (Cramton, Shoham, & Steinberg, 2006), chap. 10.

Shapley, L. S., & Shubik, M. 1972. The assignment game I: The core. International Journal ofGame Theory, 1, 111–130.Google Scholar

Smith, T., Sandholm, T., & Simmons, R. 2002. Constructing and clearing combinatorial exchanges using preference elicitation. In AAAI-02 workshop on Preferences in AI and CP: SymbolicApproaches.

Stokely, M.,Winget, J., Keyes, E., Grimes, C., & Yolken, B. 2009. Using a market economy to provision compute resources across planet-wide clusters. In Proceedings for the International Paralleland Distributed Processing Symposium (IPPS-09), pp. 1–8.

Vossen, T. W.|M., & Ball, M. O. 2006. Slot trading opportunities in collaborative ground delay programs. Transportation Science, 40, 15–28.Google Scholar

Wurman, P. R., & Wellman, M. P. 2000. AkBA: A progressive, anonymous-price combinatorial auction. In Proceedings of the 2nd ACM Conference on Electronic Commerce (EC-00) , pp. 21–29.Google Scholar

Accessibility standard: Unknown

Why this information is here

This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.

Accessibility Information

Accessibility compliance for the PDF of this chapter is currently unknown and may be updated in the future.