Jump to ContentJump to Main Navigation
Combinatorial Auctions - MIT Press Scholarship Online
Users without a subscription are not able to see the full content.

Combinatorial Auctions

Peter Cramton, Yoav Shoham, and Richard Steinberg

Abstract

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 book integrates these three perspectives, offering a survey of developments in combinatorial auction theory and practice. 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. This book addresses each of these challenges. After describ ... More

Keywords: economics, operations research, computer science, economic efficiency, auction revenues, bidding languages, objective-maximizing allocation, alternative algorithms, spectrum auctions, airport takeoff

Bibliographic Information

Print publication date: 2005 Print ISBN-13: 9780262033428
Published to MIT Press Scholarship Online: August 2013 DOI:10.7551/mitpress/9780262033428.001.0001

Authors

Affiliations are at time of print publication.

Peter Cramton, editor

Yoav Shoham, editor

Richard Steinberg, editor

Show Summary Details

subscribe or login to access all content.

Contents

View:

Front Matter

Title Pages

Dedication

Foreword

Acknowledgements

Introduction to Combinatorial Auctions

Peter Cramton, Yoav Shoham, and Richard Steinberg

I Mechanisms

1 The Lovely but Lonely Vickrey Auction

Lawrence M. Ausubel, and Paul Milgrom

2 Iterative Combinatorial Auctions

David C. Parkes

3 Ascending Proxy Auctions

Lawrence M. Ausubel, and Paul Milgrom

4 Simultaneous Ascending Auctions

Peter Cramton

5 The Clock-Proxy Auction: A Practical Combinatorial Auction Design

Lawrence M. Ausubel, Peter Cramton, and Paul Milgrom

6 PAUSE: A Computationally Tractable Combinatorial Auction

Ailsa Land, Susan Powell, and Richard Steinberg

II Bidding and Efficiency

7 Pseudonymous Bidding in Combinatorial Auctions

Makoto Yokoo

8 From the Assignment Model to Combinatorial Auctions

Sushil Bikhchandani, and Joseph M. Ostroy

9 Bidding Languages for Combinatorial Auctions

Noam Nisan

10 Preference Elicitation in Combinatorial Auctions

Tuomas Sandholm, and Craig Boutilier

11 The Communication Requirements of Combinatorial Allocation Problems

Ilya Segal

III Complexity and Algorithmic Considerations

12 The Winner Determination Problem

Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm

13 Tractable Cases of the Winner Determination Problem

Rudolf Müller

14 Optimal Winner Determination Algorithms

Tuomas Sandholm

15 Incentive Compatibility in Computationally Feasible Combinatorial Auctions

Amir Ronen

16 Noncomputational Approaches to Mitigating Computational Problems in Combinatorial Auctions

Aleksandar Pekeč, and Michael H. Rothkopf

IV Testing and Implementation

17 Observations and Near-Direct Implementations of the Ascending Proxy Auction

Karla Hoffman, Dinesh Menon, Susara van den Heever, and Thomas Wilson

18 A Test Suite for Combinatorial Auctions

Kevin Leyton-Brown, and Yoav Shoham

19 Empirical Hardness Models for Combinatorial Auctions

Kevin Leyton-Brown, Nudelman Eugene, and Yoav Shoham

V Applications

20 Auctions for the Safe, Efficient, and Equitable Allocation of Airspace System Resources

Michael O Ball, George L Donohue, and Karla Hoffman

21 Combinatorial Auctions for Truckload Transportation

Chris Caplice, and Yossi Sheffi

22 Auctioning Bus Routes: The London Experience

Estelle Cantillon, and Martin Pesendorfer

23 Industrial Procurement Auctions

Martin Bichler, Andrew Davenport, Gail Hohner, and Jayant Kalagnanam

End Matter

Combinatorial Auction Glossary

Contributors

Author Index

Subject Index