Home ] Auction ] Bargaining ] Other ] Album ] Courses ] Links ] Vita ] Workshop ]

Combinatorial Auctions, MIT Press, 2006
Peter Cramton, Yoav Shoham, and Richard Steinberg (editors)
foreword by Vernon L. Smith

Amazon 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 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

Author Index        Subject Index 

Vernon Smith

Introduction to Combinatorial Auctions
Peter Cramton, Yoav Shoham, and Richard Steinberg

Part I: Mechanisms

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

Part V: Applications

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

Home ] Auction ] Bargaining ] Other ] Album ] Courses ] Links ] Vita ] Workshop ]