Optimal Cost-Sharing Mechanisms

We study auction design in settings where the auctioneer can incur a non-trivial cost. We insist on two basic properties: "truthfulness", meaning that no bidder has an incentive to misreport its valuation for a good; and "budget-balance", the minimal economic feasibility requirement that the prices charged to the winners of the auction are guaranteed to cover the cost incurred. The problem of designing truthful, budget-balanced auctions with non-trivial costs is difficult. For 30 years, it has been known that every such auction is suboptimal with respect to all reasonable objective functions, including the social surplus. Moreover, there is only one general technique known for designing such auctions, which is a variant of ascending auctions due to Moulin (1999). We call such auctions "Moulin mechanisms". We develop a theoretical framework for identifying optimal Moulin mechanisms---truthful, budget-balanced auctions with the minimum-possible worst-case surplus loss. We successfully apply this framework to a wide range of problems, including the fixed-tree multicast problem, submodular cost-sharing, and cost-sharing problems that arise from facility location and network design problems. Includes joint work with Shuchi Chawla and Mukund Sundararajan.