Optimal Auction Design and Applications to FCC Spectrum Auctions

We consider the two-sided combinatorial auction design problem. A set of sellers are willing to sell items to the auctioneer and a set of buyers are willing to buy bundles of these items from the auctioneer. The problem is to design an auction which maximizes the revenue of the auctioneer when he has imperfect information about how much the sellers accept as payment or how much the buyers are willing to pay. The problem with complements between items - where the value of an item for a buyer may depend on the presence of other items - remains intractable in the general case. Motivated by FCC spectrum auctions, we present optimal mechanisms for single-minded buyers whose valuations correspond to connected subgraphs of a known graph that has bounded treewidth. We extend our results to the case of planar graphs and we show computational hardness results for more general settings.