Combinatorial Auctions, MIT Press, 2006
|
 |
A comprehensive book on combinatorial auctions―auctions
in which bidders can bid on packages of items. The book consists of original
material intended for
researchers, students, and practitioners of auction design. It includes
a foreword by Vernon Smith, an introduction to combinatorial auctions, and twenty-three
cross-referenced chapters in five parts. Part I covers mechanisms, such as the Vickrey auction and the
ascending
proxy auction. Part II is on bidding and efficiency issues.
Part III
examines computational issues and algorithmic considerations, especially the
winner determination problem―how to identify the (tentative) winning set of bids that
maximizes revenue. Part IV
discusses implementation and methods of testing the performance of combinatorial
auctions, including simulation and experiment.
Part V considers four important applications: airport
runway access, trucking, bus routes, and industrial procurement. The chapters
develop and apply a unified language, integrating ideas from economics,
operations research, and computer science. A glossary defines over 150 central
terms. The
contributors are
Lawrence Ausubel,
Michael Ball, Martin Bichler, Sushil Bikhchandani, Craig Boutilier, Estelle
Cantillon, Chris Caplice, Peter Cramton, Andrew Davenport, George Donohue,
Karla Hoffman, Gail Hohner, Jayant Kalagnanam, Ailsa Land, Daniel Lehmann, Kevin
Leyton-Brown, Dinesh Menon, Paul Milgrom, Rudolf Müller, Noam Nisan, Eugene
Nudelman, Joseph
Ostroy, David Parkes, Aleksandar Pekec, Martin Pesendorfer, Susan Powell, Amir
Ronen, Michael Rothkopf, Tuomas Sandholm, Ilya Segal, Yossi Sheffi, Yoav Shoham,
Richard Steinberg, Susara van den Heever,
Thomas Wilson,
and Makoto Yokoo.
This important volume addresses many of the crucial issues
in modern auction design. Containing insightful contributions from many of the
world's leading market designers and auction theorists, it will be an essential
reference for scholars and practitioners alike.
– Paul Klemperer, Oxford University
The study of combinatorial auctions has importance both
practical and theoretical. In combinatorial auctions, our elegant models of
resource allocation confront the true complexity of markets, where potential
traders compete to buy or sell many different but related goods. Combinatorial
auctions are the great frontier of auction theory today, and this book provides
a state-of-the-art survey of this exciting field.
– Roger Myerson, University of Chicago
Combinatorial Auctions is an important interdisciplinary
field combining issues from economics, game theory, optimization, and computer
science. The book presents a great collection of state-of-the-art surveys with a
well-balanced view integrating all aspects. A very impressive accomplishment! It
will help us all appreciate the full range of issues, and will be a great
reference for years to come.
– Eva Tardos, Cornell University
“Smart” markets, which allow participants to bid for
packages of items, are now an attractive option for sales and procurements in a
variety of settings. This book provides a comprehensive overview of both
theoretical considerations and practical details. It is remarkable for combining
economics, game theory, optimization, and computer science in a unified
perspective. Combinatorial Auctions is a major advance in the theory and
practice of market design.
– Robert Wilson, Stanford University
Combinatorial Auction Glossary
Foreword
Vernon Smith
Introduction to Combinatorial Auctions
Peter Cramton, Yoav Shoham, and Richard Steinberg
Chapter
1 The Lovely but Lonely Vickrey Auction
Lawrence M. Ausubel and Paul Milgrom
Chapter 2
Iterative Combinatorial Auctions
David C. Parkes
Chapter 3
Ascending Proxy Auctions
Lawrence M. Ausubel and Paul Milgrom
Chapter 4
Simultaneous Ascending Auctions
Peter Cramton
Chapter 5
The Clock-Proxy Auction: A Practical Combinatorial Auction Design
Lawrence M. Ausubel, Peter Cramton, and Paul Milgrom
Chapter 6 PAUSE: A Computationally Tractable Combinatorial Auction
Ailsa Land, Susan Powell, and Richard Steinberg
Part II: Bidding and Efficiency
Chapter 7 Pseudonymous
Bidding in Combinatorial Auctions
Makoto Yokoo
Chapter 8 From the Assignment Model to Combinatorial Auctions
Sushil Bikhchandani and Joseph M. Ostroy
Chapter 9 Bidding Languages for Combinatorial Auctions
Noam Nisan
Chapter 10 Preference Elicitation in Combinatorial Auctions
Tuomas Sandholm and Craig Boutilier
Chapter 11 The
Communication Requirements of Combinatorial Allocation Problems
Ilya Segal
Part III: Complexity and Algorithmic Considerations
Chapter 12 The Winner Determination Problem
Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm
Chapter 13
Tractable Cases of the Winner Determination Problem
Rudolf Müller
Chapter 14 Optimal Winner Determination Algorithms
Tuomas Sandholm
Chapter 15 Incentive Compatibility in Computationally Feasible Combinatorial
Auctions
Amir Ronen
Chapter 16
Noncomputational Approaches to Mitigating Computational Problems in
Combinatorial Auctions
Aleksandar Pekec and Michael Rothkopf
Part IV: Testing and Implementation
Chapter 17
Observations and Near-Direct Implementations of the Ascending Proxy Auction
Karla Hoffman, Dinesh Menon, Susara van den Heever, and Thomas Wilson
Chapter 18 A Test
Suite for Combinatorial Auctions
Kevin Leyton-Brown and Yoav Shoham
Chapter 19 Empirical Hardness Models for Combinatorial Auctions
Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham
Chapter 20
Auctions for the Safe, Efficient and Equitable Allocation of Airspace System
Resources
Michael O. Ball, George L. Donohue, and Karla Hoffman
Chapter 21
Combinatorial Auctions for Truckload Transportation
Chris Caplice and Yossi Sheffi
Chapter 22
Auctioning Bus Routes: The London Experience
Estelle Cantillon and Martin Pesendorfer
Chapter
23 Industrial Procurement Auctions
Martin Bichler, Andrew Davenport, Gail Hohner, and
Jayant Kalagnanam