Combinatorial Auctions, MIT Press, 2006
Peter Cramton, Yoav Shoham, and Richard Steinberg (editors)
foreword by Vernon L. SmithAmazon order
MIT Press examination copy
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.
Review: "Combinatorial Auctions is excellent and exceptional in practically all attributes I would care about in this type of work. This includes the breadth and depth of the topics covered and the language employed. Additionally, my praise also extends to minor details, such as the existence of an exhaustive author and subject index, and the quality of its typesetting, especially with regard to the mathematical apparatus used in some of the chapters. For researchers and practitioners, both on the seller side and on the buyer side, who deal with (combinatorial) auctions, this book is a must-read." – Christoph F. Strnadl, Computing Reviews
Review: "Anyone with an interest in auction theory, market design, and more broadly, practical applications of game theory, will find this book extremely valuable both as a reference to the existing work on combinatorial auctions and as a source of topics and ideas for new research." - Michael Ostrovsky, Journal of Economic Literature
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 UniversityThe 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 ChicagoCombinatorial 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 SmithIntroduction to Combinatorial Auctions
Peter Cramton, Yoav Shoham, and Richard SteinbergChapter 1 The Lovely but Lonely Vickrey Auction
Lawrence M. Ausubel and Paul MilgromChapter 2 Iterative Combinatorial Auctions
David C. ParkesChapter 3 Ascending Proxy Auctions
Lawrence M. Ausubel and Paul MilgromChapter 4 Simultaneous Ascending Auctions
Peter CramtonChapter 5 The Clock-Proxy Auction: A Practical Combinatorial Auction Design
Lawrence M. Ausubel, Peter Cramton, and Paul MilgromChapter 6 PAUSE: A Computationally Tractable Combinatorial Auction
Ailsa Land, Susan Powell, and Richard SteinbergPart II: Bidding and Efficiency
Chapter 7 Pseudonymous Bidding in Combinatorial Auctions
Makoto YokooChapter 8 From the Assignment Model to Combinatorial Auctions
Sushil Bikhchandani and Joseph M. OstroyChapter 9 Bidding Languages for Combinatorial Auctions
Noam NisanChapter 10 Preference Elicitation in Combinatorial Auctions
Tuomas Sandholm and Craig BoutilierChapter 11 The Communication Requirements of Combinatorial Allocation Problems
Ilya SegalPart III: Complexity and Algorithmic Considerations
Chapter 12 The Winner Determination Problem
Daniel Lehmann, Rudolf Müller, and Tuomas SandholmChapter 13 Tractable Cases of the Winner Determination Problem
Rudolf MüllerChapter 14 Optimal Winner Determination Algorithms
Tuomas SandholmChapter 15 Incentive Compatibility in Computationally Feasible Combinatorial Auctions
Amir RonenChapter 16 Noncomputational Approaches to Mitigating Computational Problems in Combinatorial Auctions
Aleksandar Pekec and Michael RothkopfPart 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 WilsonChapter 18 A Test Suite for Combinatorial Auctions
Kevin Leyton-Brown and Yoav ShohamChapter 19 Empirical Hardness Models for Combinatorial Auctions
Kevin Leyton-Brown, Eugene Nudelman, and Yoav ShohamChapter 20 Auctions for the Safe, Efficient and Equitable Allocation of Airspace System Resources
Michael O. Ball, George L. Donohue, and Karla HoffmanChapter 21 Combinatorial Auctions for Truckload Transportation
Chris Caplice and Yossi SheffiChapter 22 Auctioning Bus Routes: The London Experience
Estelle Cantillon and Martin PesendorferChapter 23 Industrial Procurement Auctions
Martin Bichler, Andrew Davenport, Gail Hohner, and Jayant Kalagnanam
