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.

This is joint work with Mukund Sundararajan and Shuchi Chawla.