A Combinatorial Auction with Multiple Winners for Universal Service

Frank Kelly and Richard Steinberg

Management Science 46 (2000) 586-596.

We describe a discrete-time auction procedure called PAUSE (Progressive Adaptive User Selection Environment) for use in assigning COLR (Carrier of Last Resort) responsibility for Universal Service. The auction incorporates synergies by permitting all combinatorial bids, allows for multiple winners, and minimises the possibility of bidder collusion. The procedure is computationally tractable for the auctioneer and thus is very efficient to run. The inherent computational complexity of combinatorial bidding cannot be eliminated. However, in this auction the computational burden of evaluating synergies rests with the bidders claiming those synergies, while the auctioneer simply checks that a bid is valid.

Keywords: auctions, combinatorial bidding, universal service, carrier of last resort, telecommunications, synergies.

Paper is available as ps, or in a slightly earlier form, pdf

Google Scholar citations