Combinatorial Auctions: Some Random Notes
These notes will undated frequently (i hope so).
Multi Unit Auctions:
Homogeneous Goods
Heterogeneous Goods
Most classic auction theory deals with single indivisible items. A multi unit auction for homogeneous generalizes this by specifying a set of price-quantity bids for multiple identical goods. Two kinds of pricing strategies are used for these auctions:
Discriminatory Pricing: Bidders who bid the highest prices pay their bids
Uniform Pricing: All successful bidders pay the lowest accepted bid or the highest loosing bid. There are other variations also.
Uniform price auctions correspond to second price auctions in the sense that each bidder has a dominant strategy of bidding his/her private valuation. Discriminatory auctions correspond to first price auctions.
Hansen showed that first price auctions lead to a higher expected prices and revenue equivalence theorem is not valid anymore. Revenue equivalence theorem is one of the most celebrated results in auction theory. [ Klemperer, Paul, "Auction Theory: A guide to the Literature", Journal of Economic Surveys, July 1999. ].
Combinatorial Auctions is an approach for heterogeneous goods. Of course it can also be deployed in the case of homogeneous items. Many auctions involve the sale of a variety of distinct assets. Examples include, auctions for airport time slots, FCC spectrum auctions, bandwidth auctions, etc. Because of the complementarities and substitutabilities between different assets, bidders have preferences for sets or bundles of items. Combinatorial auctions is desirable since it allows bidders to express their true valuations. This should result in greater revenue for bid takers and economically more efficient allocations of assets to bidders.
Basic Issues in combinatorial auctions:
Bidding
Allocation
Payment
Strategy
Bidding: Each bidder must be able to express a bid on combination of items. Since there are an exponential number of combinations the auction protocol determines the bidding communication is done.
Bidding languages: OR bids, XOR bids, OR-of-XOR bids, XOR-of-OR bids, OR/XOR formulae, OR bids with phantom items called OR* bids, and applet bids. A bidding language can polynomial time interpretable or polynomial time verifiable. Read Noam Nissan's paper for a detailed overview.
Allocation: This is perhaps the most important problem that arise in combinatorial auctions i.e. How to determine the winners. This problem can be formulated as an integer programming problem. And also can be shown to be NP-complete. Read Vries and Vohra's survey paper to get to know the details. I'll attach an appendix later to describe some of the details.
Payment: Well pricing is quite an important issue in auctions i.e. How much does each winner of a bundle pay? As i mentioned earlier we have to broad classes: uniform and discriminatory pricing. Read the following two papers to get an overview of various pricing strategies. And if you are interested in going deeper, follow the references.
Bichler, Martin, "A Roadmap to Auction-based Negotiation Protocols for Electronic Commerce" and
Wurman, P.R. and Wellman, M.P. and Walsh, W.E., "A Parametrization of the Auction Design Space".
Strategy: Once auction's bidding, allocation, and payments rules are fixed, each bidder can choose any bidding strategy. A well designed auction will ensure that the intended goals of auction are met when all players choose their selfish strategies. I've given some references down about selfish agents but i've really not done much survey of this topic.
Reading List for Combined Value Problems over heterogeneous goods: This is not an exhaustive list. There are lot more papers. Also most of the papers are available online. Just google. Also look in http://citeseer.nj.nec.com.
1. Auctions
Armstrong, Mark, "Optimal Multi-Object Auctions," May 1999.
Ausubel, Lawrence M., "An Efficient Ascending-Bid Auction for Dissimilar Objects,"
preliminary paper, January 4, 1996.
Ausubel, Lawrence M., Peter Cramton, R. Preston McAfee, and John McMillan (1997),
"Synergies in Wireless Telephony: Evidence from the Broadband PCS Auctions,"
Journal of Economics and Management Strategy, 6:3, 497-527.
Bali, Valentina, "Auctions with Multidimensional Bids," June 1998.
Banks, J., J. Ledyard, D. Porter, "Allocating Uncertain and Unresponsive Resources,"
The Rand Journal of Economics 20, No. 1, Spring 1989
Benoit, Jean-Pierre, and Vijay Krishna, "Multiple-Object Auctions with Budget
Constrained Bidders," April 30, 1998.
Bichler, Martin, "A Roadmap to Auction-based Negotiation Protocols for Electronic Commerce", In: Proceedings of the 33th Hawai'i International Conference on Systems Sciences (HICSS), Maui, Hawaii; January 4 - 7, 2000.
Bikhchandani, Sushil, "Auctions of Heterogeneous Objects," in Games and Economic
Behavior
Bikhchandani, Sushil, and Josephy M. Ostroy, "The Package Assignment Model," Nov.
1998.
Branco, Fernando, "Multi-Object Auctions with Synergies," January 1996.
Branco, Fernando, "Multi-Object Auctions: On the Use of Combinational Bids," April
1995.
Branco, Fernando, "The Design of Multidimensional Auctions," RAND Journal of
Economics 28, No. 1, Spring 1997.
Brenner, David, and John Morgan, "The Vickrey-Clarke-Groves Versus the Simultaneous
Ascending Auction: An Experimental Approach," June 1997.
Brewer, Paul J., "Network Externalities and the BICAP Auction," Draft 971020.
Brewer, Paul J., and Charles R. Plott, "A Binary Conflict Ascending Price (BICAP)
Mechanism For The Decentralized Allocation of the Right to Use Railroad Tracks,"
International Journal of Industrial Organization 14, 1996.
Brusco, Sandro, and Giuseppe Lopomo, "Collusion via Signaling in Open Ascending
Auctions with Multiple Objects and Complementarities," April 1999.
Bykowsky, Mark M., Robert J. Cull, John O. Ledyard, "Mutually Destructive Bidding:
The FCC Auction Design Problem," to appear in Journal of Regulatory Economics
Campbell, Colin M., "Efficient Auctions of Multiple Objects," September 1996.
Chakravorti, B., W.W. Sharkey, Y. Spiegel and S. Wilkie, "Auctioning the Airwaves:
The Contest for Broadband PCS Spectrum," Journal of Economics & Management
Strategy, 4(2), 267-343, 1995.
Cramton, Peter, John McMillan, Paul Milgrom, Bradley Miller, Bridger Mitchell, Daniel
Vincent, and Robert Wilson (1997), Package Bidding for Spectrum Licenses, Report 1b,
Charles River Associates and Market Design Inc.
Cramton, Peter, John McMillan, Paul Milgrom, Bradley Miller, Bridger Mitchell, Daniel
Vincent, and Robert Wilson (1997), Auction Design Enhancements for Non-
Combinatorial Auctions, Report 1a, Charles River Associates and Market Design Inc.
Cramton, Peter, John McMillan, Paul Milgrom, Bradley Miller, Bridger Mitchell, Daniel
Vincent, and Robert Wilson (1998), Simultaneous Ascending Auctions with Package
Bidding, Report 2, Charles River Associates and Market Design Inc.
Cramton, Peter (1997), "The FCC Spectrum Auctions: An Early Assessment," Journal of
Economics and Management Strategy, 6:3, 431-495.
Cramton, Peter (1998), "The Efficiency of the FCC Spectrum Auctions," Journal of Law
and Economics, 41, 727-736.
Cramton, Peter (2000), "Lessons from the United States Spectrum Auctions," Prepared
Testimony for the Senate Budget Committee, February 10.
Cramton, Peter and Jesse Schwartz (1999), "Collusive Bidding in the FCC Spectrum
Auctions," Working Paper, University of Maryland.
Cramton, Peter and Jesse Schwartz (2000), "Collusive Bidding: Lessons from the FCC
Spectrum Auctions," Journal of Regulatory Economics, 17, forthcoming.
de Vries, Sven, and Rakesh Vohra, "Combinatorial Auctions: A Brief Survey," draft,
January 2000.
DeMartini, Christine, Anthony M. Kwasnica, John O. Ledyard, and David Porter, "A
New and Improved Design for Multi-Object Iterative Auctions," March, 1999. Available
at <http://masada.hss.caltech.edu/~jledyard/Ledyard.html>.
Marta Eso & Manoj Kumar, " Bidding for Airline seats" , IBM
Bob Forsythe and Mark Isaac, "Demand-Revealing Mechanisms for Private Good
Auctions," in Research in Experimental Economics 2, V.L. Smith,
ed.,(Greenwich, Conn.: JAI Press, Inc., 1982)
Fujishima, Yuzo and Leyto-Brown, Kevin and Shoham Yoav, "Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches"
Gale, Ian, "A Multiple-Object Auction with Superadditive Values," Economics Letters
34: 323-328, 1990.
Graves, Sankaran, and Schrage, "An Auction Method for Course Registration",
INTERFACES, vol. 23, no. 5, 1993
David M. Grether, R. Mark Isaac and Charles R. Plott, "The Allocation Of Scarce
Resources: Experimental Economics and the Problem of Allocating Airport Slots"
Westview Press Underground Classics in Economics series, 1989.
Groves, Theodore, "Efficient Collective Consumption when Compensation is Possible" ,
R.E.Studies, 46, 1979
Gul, Faruk, and Ennio Stacchetti, "English and Double Auctions With Differentiated
Commodities," July 11, 1996.
Gul, Faruk, and Ennio Stacchetti, "English Auctions With Multiple Goods," May 13,
1996.
Hansen, R.G., "Auctions with endogeneous quantity", Rand Journal of Economics, vol 19, 1988.
Isaac, R. Mark, and Duncan James, "Robustness of the Incentive Compatible
Combinatorial Auction," March 1997, to appear in Experimental Economics
James, Duncan, and R. Mark Isaac, "Explaining Efficiency in the Incentive Compatible
Combinatorial Auction," September 1997.
Kelly, Frank, and Richard Steinberg. 1997. "A Combinatorial Auction with Muliple
Winners for COLR," University of Cambridge, 17 March. [Submitted ex parte 18 March
1997 by Citizens for a Sound Economy Foundation to US Federal Communications
Commission re CC Docket No. 96-45, Federal-State Board on Universal Service.]
Kelly, Frank, and Richard Steinberg. 2000. "A Combinatorial Auction with Multiple
Winners for Universal Service," Management Science 46(4).
Kim, Hee-Su, "Equilibrium and Efficiency in Auctions of Complementary Goods
Without Bundling," Economics Letters 52: 49-54, 1996.
Krishna, Vijay, and Robert Rosenthal, "Simultaneous Auctions with Synergies," GEB 17,
1-31 (1996)
Ledyard, John O., Mark Olson, David Porter, Joseph Swanson, & David Torma, "The
First Use of a Combined Value Auction for Transportation Services," January 2000.
Available at <http://masada.hss.caltech.edu/~jledyard/Ledyard.html>.
Ledyard, John, Mark M. Bykowsky and Robert J. Cull "Mutually Destructive Bidding:
The FCC Auction Design Problem," Social Science Working Paper No. 916, California
Institute of Technology, Pasadena, rev. June 1998. Journal of Regulatory Economics,
March 2000. At <http://masada.hss.caltech.edu/~jledyard/Ledyard.html>.
Ledyard, John, Charles Noussair and David Porter, "The Allocation of Shared Resources
within an Organization," Economic Design, Vol. 2, No. 2, November 1996, pp. 163-192.
Ledyard, John, David Porter and Antonio Rangel, "Experiments Testing Multi-object
Allocation Mechanisms," Journal of Economics and Management Strategy, Vol. 6, No. 3,
1997.
Lehmann, Daniel, Liadan Ita O'Callaghan, and Yoav Shoham, "Truth Revelation in
Rapid, Approximately Efficient Combinatorial Auctions," May 1999.
Levin, Jonathan, " An Optimal Auction for Complements," Games and Economic
Behavior 18, 1997.
McAfee & McMillan, "Multidimensional Incentive Compatibility and Mechanism
Design", Journal of Economic Theory 46, December 1988: 335-54
McAfee & John McMillan, "Analyzing the Airwaves Auction", Journal of Economic
Perspectives 10, no.1, Winter 1996, 159-75
Milgrom, Paul, "Putting Auction Theory to Work: The Simultaneous Ascending
Auction," December 8, 1997.
Olson, Mark & David Porter. "An Experimental Examination into the Design of
Decentralized Methods to Solve the Assignment Problem with and without Money,"
Economic Theory, January 1994.
David Parkes. "An Iterative Generalized Vickrey Auction: Strategy-Proofness without Complete Revelation", To appear, AAAI Spring Symposium on Game Theoretic and Decision Theoretic Agents, March, 2001.
Parkes, David C., "iBundle: An Efficient Ascending Price Bundle Auction."
Parkes, David C., "Primal-Dual Analysis: Providing the Efficiency of iBundle,"
November 1999.
Plott, Charles R, "Laboratory Experimental Testbeds: Application To The PCS Auction,"
Journal of Economics and Management Strategy, Vol. 6, No. 3, 1997.
Plott, Charles R. & David Porter, "Market architectures and institutional testbedding: An
experiment with space station pricing policies", Journal of Economic Behavior &
Organization, 31 1996
Porter, David P., "The Effect of Bid Withdrawal in a Multi-Object Auction," Caltech
Working Paper No. 982, February 1997.
Rasenti, S.J., V.L. Smith, R.L. Bulfin, "A Combinatorial Auction Mechanism for Airport
Time Slot Allocation," Bell Journal of Economics, August 1982.
Rosenthal, Robert W., and Ruqu Wang, "Simultaneous Auctions with Synergies and
Common Values," Boston University, ISP Discussion Paper #60, August 1995.
Rosenthal, Robert W., and Ruqu Wang, "Simultaneous Auctions with Synergies," GEB
17, 32-55 (1996)
Michael H. Rothkopf, Elmer Dougherty and Marshall Rose, "Comment on 'Multi-Object
Auctions: Sequential vs. Simultaneous Sales," Management Science 32, pp. 1611-1612,
1986.
Rothkopf, Michael H., Aleksandar Pekec, and Ronald M. Harstad, "Computationally
Manageable Combinatorial Auctions," Management Science 44, No. 8, August 1998.
Sandholm, Tuomas, "An Algorithm for Optimal Winner Determination in Combinatorial
Auctions."
Sandholm, Tuomas, "Approaches to winner determination in combinatorial auctions", Decision Support Systems 28(2000).
Wellman, Michael P., and William E. Walsh, "Auction Protocols for Decentralized
Scheduling," June 1999.
Williams, Steven R., "A Characterization of Efficient, Bayesian Incentive Compatible
Mechanisms," Economic Theory 14, 155-180 (1999)
Wurman, Peter R., "Market Structure and Multidimensional Auction Design for
Computational Economies," 1999.
Wurman, P.R. and Wellman, M.P. and Walsh, W.E., "A Parametrization of the Auction Design Space", Games and Economic Behavior, to appear.
Zheng, Charles Z., "A Recipe for Optimal Multidimensional Auctions," September 1999.
II. Markets
Bossaerts, Leslie Fine, and John Ledyard, "Inducing Liquidity In Thin Financial Markets
Through Combined-Value Trading Mechanisms,", March 2000. Available at
<http://masada.hss.caltech.edu/~jledyard/Ledyard.html>.
Brewer, Paul J., "Decentralized Computation Procurement and Computational
Robustness in a Smart Market," in Economic Theory,
Dinar, A., R. Howitt, S. Rasenti, and V. Smith, "Development of Water Markets Using
Experimental Economics," Markets for Water Potential and Performance, edited
by K. W. Easter, M. Rosegrant and A. Dinar. Boston, MA: Kluwar, 1998.
Fan, Ming, Jan Stallaert, and Andrew B. Whinston, "The Design and Development of a
Financial Cybermarket with a Bundle Trading Mechanism", U. of Texas, Sept. 1998
Benjamin F. Hobbs, Michael H. Rothkopf, Laurel C. Hyde, and Richard P. O'Neill,
"Evaluation of an Incentive Compatible Auction for Energy Markets with Non-concave
Benefits," To appear in Journal of Regulatory Economics.
Ishikda, Takashi, John Ledyard, Mark Olson, and David Porter, "Experimental Test-
bedding of a Pollution Trading System: Southern California's RECLAIM Emissions
Market," Available at <http://masada.hss.caltech.edu/~jledyard/Ledyard.html>.
Ledyard, John, David Porter and Antonio Rangel "Using Computerized Exchange
Systems to Solve an Allocation Problem in Project Management," Journal of
Organizational Computing, Vol. 4, Number 3, 1994, pp. 271-296.
MacKie-Mason, Jeffrey K, "A Smart Market for Resource Reservation in a Multiple
Quality of Service Information Network," September 1997.
Marron, Donald B., and Carlton W. Bartels, "The Use of Computer-Assisted Auctions for
Allocating Tradable Pollution Permits," in Market-Based Control: A Paradigm for
Distributed Resource Allocation, S. Clearwater, Ed., World Scientific Pub. Co., New
York 1996
McCabe, Kevin, Stephen Rasenti, and Vernon Smith, "Auction Design for Composite
Goods: The Natural Gas Industry," Journal of Economic Behavior and Organization,
September 1990, pp. 127-149.
McCabe, Kevin, Stephen Rasenti, and Vernon Smith, "Designing a Real Time Computer
Assisted Auction for Natural Gas Networks," in New Directions in Computational
Economics (edited by W. Cooper and A. Whinston), Kluwer Academic Publishers, 1994,
pp. 41-54.
Miller, Ross, "The Design of Decentralized Auction Mechanisms that Coordinate
Continuous Trade in Synthetic Securities", Journal of Economic Dynamics and Control
1990
Miller, Ross, "Smart Market Mechanisms: From Practice to Theory", Journal of
Economic Dynamics and Control, 1996
Nisan, Noam, "Bidding and Allocation in Combinatorial Auctions", ACM Conference on Electronic Commerce 1999.
Nisan, Noam and Ronen, Amir, "Computationally Feasible VCG Mechanisms", ACM Conference on Electronic Commerce, 2000.
Plott, Charles R., "Research on Pricing in a gas transport network", Office of Economic
Policy Technical Report 88-2, Federal Energy Regulatory Commission, 1988
Plott, Charles R. and Paul Brewer, "A Smart Market Solution to a Class of Back-haul
Transportation Problems: Concept and Experimental Testbeds" 1999
Rassenti, Stephen, and Vernon L. Smith, "Deregulating Electric Power: Market Design
Issues and Experiments," Designing Competitive Electricity Markets, edited by Hung-po
Chao and Hillard G. Huntington. Boston, MA: 1998.
Srinivasan, Sayee, "Trading Portfolios Electronically An Experimental Approach,"
April 1999.
Srinivasan, Sayee, Jan Stallaert, and Andrew B. Whinston, "Portfolio Trading and
Electronic Networks," February 1998.
Walsh, William E., Michael P. Wellman, and Peter R. Wurman, "Some Economics of
Market-based Distributed Scheduling," October 1997.
Wessen, Randii R., and David Porter, "Market-Based Approaches for Controlling Space
Mission Costs: The Cassini Resource Exchange."
III. Related
Alkan, Ahmet, "Matching Market Equilibria and Multi-Object Auction," Laboratoire
D'Econometrie No. 361, April 1991.
Ausubel, Lawrence M. and Peter Cramton (1999), "The Optimality of Being Efficient,"
Working Paper, University of Maryland.
Ausubel, Lawrence M. and Peter Cramton (1999), "Vickrey Auctions with Reserve
Pricing," Working Paper, University of Maryland.
Ausubel, Lawrence M. and Peter Cramton (1996), "Demand Reduction and Inefficiency
in Multi-Unit Auctions," Working Paper, University of Maryland.
Bikhchandani, Sushil, and John W. Mamer, "Competitive Equilibrium in an Exchange
Economy with Indivisibilities," December 16, 1994.
Sushil Bikhchandani and Joseph M. Ostroy, "Ascending Price Vickrey Auctions"
January 2000
Branco, Fernando, "Sequential Auctions With Synergies: An Example," Economics
Letters 54, 1997.
Cramton, Peter (1995), "Money Out of Thin Air: The Nationwide Narrowband PCS
Auction," Journal of Economics and Management Strategy, 4, 267-343.
Cramton, Peter (1998), "Ascending Auctions," European Economic Review, 42, 745-756.
Cramton, Peter, Robert Gibbons, and Paul Klemperer (1987), "Dissolving a Partnership
Efficiently," Econometrica, 55, 615-632.
Cramton, Peter, Evan Kwerel, and John Williams (1998), "Efficient Relocation of
Spectrum Incumbents," Journal of Law and Economics, 41, 647-675.
Cranor, Lorrie Faith, and Paul Resnick, "Protocols for Automated Negotiations with
Buyer Anonymity and Seller Reputations, 1997.
Frutos, M. A. de, and R. W. Rosenthal, "On Some Myths about Sequenced Common-
value Auctions, Games and Economic Behavior Vol. 23 (1998), pp. 201-221.
Edward P. Kahn, Michael H. Rothkopf, Joseph Ito and Jean-Michel Nataf, "Auctions for
PURPA Purchases: A Simulation Study," Journal of Regulatory Economics 2, pp. 129-
149,1990.
Kephart, Jeffrey O., Rajarshi Das, Jeffrey MacKie-Mason, "Two-Sided Learning in an
Agent Economy for Information Bundles,"
Klemperer, Paul, "Applying Auction Theory to Economics". 2000 .
www.nuffield.ox.ac.uk/economics/people/klemperer.htm
Klemperer, Paul, "Auction Theory: A guide to the Literature", Journal of Economic
Surveys, July 1999.
Ledyard, J.O., "The Design of Coordination Mechanisms and Organizational
Computing," Journal of Organizational Computing 3, No. 1, 1993.
Ledyard, John "Coordination in Shared Facilities: A New Methodology" Journal of
Organizational Computing, Vol.1, No. 1 (1991):41-59.
McAfee, R. Preston, John McMillan, Michael D. Whinston, "Multiproduct Monopoly,
Commodity Bundling, and Correlation of Values," The Quarterly Journal of Economics,
May 1989.
McAfee & Reny, "Correlated Information and Mechanism Design", Econometrica 60,
No. 2, March 1992, 395-421
McCabe, Rasenti, Smith, Science V.254, October 25, 1991.
Nilsson, Jan-Eric, "Allocation of Track Capacity: Experimental Evidence on the Use of
Vickreyish Auctioning in the Railway Industry," October 28, 1994.
Nisan, Noam, and Amir Ronen, "Algorithmic Mechanism Design."
Palfrey, Thomas R., "Bundling Decisions by a Multiproduct Monopolist with Incomplete
Information," Graduate School of Industrial Administration, Carnegie-Mellon University,
Reprint No. 1029.
Palfrey, Thomas R., "Multiple-Object, Discriminatory Auctions with Bidding
Constraints: A Game-Theoretic Analysis," Graduate School of Industrial Administration,
Carnegie-Mellon University, Reprint No. 935.
Michael H. Rothkopf, "Bidding in Simultaneous Auctions with a Constraint on
Exposure," Operations Research 25, pp. 620-629, 1977.
Michael H. Rothkopf, Edward P. Kahn, Thomas J. Teisberg, Joseph Eto and Jean-Michel
Nataf, "Designing Purpa Power Purchase Auctions: Theory and Practice," Competition in
Electricity: New Markets and New Structures, James Plummer and Susan Troppmann,
Eds., Public Utilities Reports, Inc., Arlington, VA, pp. 139-194,1990.
Michael H. Rothkopf, "On Misusing Auctions to Value Stranded Assets," The Electricity
Journal 10(10), pp. 10-17, December, 1997.
Michael H. Rothkopf, "Valuing Stranded Costs: Can You Sell Your Lunch and eat it
Too?" The Electricity Journal 11(3), pp.3-5, April, 1998
Michael H. Rothkopf, "Daily Repetition: A Neglected Factor in the Analysis of
Electricity Auctions," The Electricity Journal 12, pp. 60-70, April 1999.
Ronen, Amir "Solving Optimization Problems Among Selfish Agents", 2000
Stephen A. Smith and Michael H. Rothkopf, "Simultaneous Bidding with a Fixed Charge
if Any Bid Succeeds," Operations Research 33, pp. 28-37, 1985
Wessen, Randii R., and David Porter, "A Management Approach for Allocating
Instrument Development Resources," in Space Policy, November 1997