Strategy-Proof Auctions for Complex Procurement

6 June 2013
Paul Milgrom
Some real resource allocation problems are so large and complex that optimization would computationally infeasible, even with complete information about all the relevant values. For example, the proposal in the US to use television broadcasters' bids to determine which stations go off air to make room for wireless broadband is characterized by hundreds of thousands of integer constraints. We use game theory and auction theory to characterize a class of simple, strategy-proof auctions for such problems and show their equivalence to a class of "clock auctions," which make the optimal bidding strategy obvious to all bidders. We adapt the results of optimal auction theory to reduce expected procurement costs and prove that the procurement cost of each clock auction is the same as that of the full information equilibrium of its related paid-as-bid (sealed-bid) auction.