Combinatorial Auctions

by Cramton, Peter; Shoham, Yoav; Steinberg, Richard; Smith, Vernon L.

• ISBN13: 9780262514132
• ISBN10: 0262514133
• Format: Paperback
• Copyright: 2010-01-22
• Publisher: The MIT Press

Summary

With a foreword by Vernon L. Smith, recipient of the 2002 Nobel Prize in Economics. The study of combinatorial auctions-auctions in which bidders can bid on combinations of items or "packages"-draws on the disciplines of economics, operations research, and computer science. This landmark collection integrates these three perspectives, offering a state-of-the art survey of developments in combinatorial auction theory and practice by leaders in the field. Combinatorial auctions (CAs), by allowing bidders to express their preferences more fully, can lead to improved economic efficiency and greater auction revenues. However, challenges arise in both design and implementation. Combinatorial Auctionsaddresses each of these challenges. After describing and analyzing various CA mechanisms, the book addresses bidding languages and questions of efficiency. Possible strategies for solving the computationally intractable problem of how to compute the objective-maximizing allocation (known as the winner determination problem) are considered, as are questions of how to test alternative algorithms. The book discusses five important applications of CAs: spectrum auctions, airport takeoff and landing slots, procurement of freight transportation services, the London bus routes market, and industrial procurement. This unique collection makes recent work in CAs available to a broad audience of researchers and practitioners. The integration of work from the three disciplines underlying CAs, using a common language throughout, serves to advance the field in theory and practice. Contributors: Lawrence M. Ausubel, Michael Ball, Martin Bichler, Sushil Bikhchandani, Craig Boutilier, Estelle Cantillon, Chris Caplice, Peter Cramton, Andrew Davenport, George Donohue, Karla Hoffman, Gail Hohner, Jayant R. Kalagnanam, Ailsa Land, Daniel Lehmann, Kevin Leyton-Brown, Dinesh Menon, Paul Milgrom, Rudolf Muller, Noam Nisan, Eugene Nudelman, Joseph M. Ostroy, David Parkes, Aleksandar Sasa Pekec, Martin Pesendorfer, Susan Powell, Amir Ronen, Michael H. Rothkopf, Tuomas Sandholm, Ilya Segal, Yossi Sheffi, Yoav Shoham, Vernon L. Smith, Richard Steinberg, Susara van den Heever, Thomas Wilson, Makoto Yokoo

Author Biography

Peter Cramton is Professor of Economics at the University of Maryland.

Yoav Shoham is Professor of Computer Science at Stanford University.

Richard Steinberg is Chair in Operations Research, London School of Economics.

Table of Contents

Foreword	p. xi
Acknowledgments	p. xvii
Introduction to Combinatorial Auctions	p. 1
Mechanisms
The Lovely but Lonely Vickrey Auction	p. 17
Iterative Combinatorial Auctions	p. 41
Ascending Proxy Auctions	p. 79
Simultaneous Ascending Auctions	p. 99
The Clock-Proxy Auction: A Practical Combinatorial Auction Design	p. 115
PAUSE: A Computationally Tractable Combinatorial Auction	p. 139
Bidding and Efficiency
Pseudonymous Bidding in Combinatorial Auctions	p. 161
From the Assignment Model to Combinatorial Auctions	p. 189
Bidding Languages for Combinatorial Auctions	p. 215
Preference Elicitation in Combinatorial Auctions	p. 233
The Communication Requirements of Combinatorial Allocation Problems	p. 265
Complexity and Algorithmic Considerations
The Winner Determination Problem	p. 297
Tractable Cases of the Winner Determination Problem	p. 319
Optimal Winner Determination Algorithms	p. 337
Incentive Compatibility in Computationally Feasible Combinatorial Auctions	p. 369
Noncomputational Approaches to Mitigating Computational Problems in Combinatorial Auctions	p. 395
Testing and Implementation
Observations and Near-Direct Implementation of the Ascending Proxy Auction	p. 415
A Test Suite for Combinatorial Auctions	p. 451
Empirical Hardness Models for Combinatorial Auctions	p. 479
Applications
Auctions for the Safe, Efficient, and Equitable Allocation of Airspace System Resources	p. 507
Combinatorial Auctions for Truckload Transportation	p. 539
Auctioning Bus Routes: The London Experience	p. 573
Industrial Procurement Auctions	p. 593
Combinatorial Auction Glossary	p. 613
Contributors	p. 627
Author Index	p. 633
Subject Index	p. 643
Table of Contents provided by Publisher. All Rights Reserved.