Friday, October 12, 2012
3:30 pm, MC 5158

Chaitanya Swamy
University of Waterloo

Black-Box Reductions for Cost-Sharing Mechanism Design

Given $n$ self-interested players who compete for some service or good, a cost-sharing mechanism (or protocol) must decide which players to serve and what prices to charge to the players so that the prices recover the cost incurred to serve the players, and the outcome computed has good social welfare. We focus on the design of strategyproof (or truthful) cost-sharing mechanisms, wherein the outcome computed and prices charged by the mechanism should be such that no player has any incentive to misreport her private value, and the goal is to minimize the (cost incurred) + (the total value of the players who do not receive service).
A central goal in algorithmic mechanism design is to understand when, and to what extent, can one reduce the truthful mechanism-design problem to the algorithm problem. In the context of cost-sharing mechanisms, where in addition to truthfulness, we also require the prices charged to recover the cost incurred, we can also ask: is there a reduction from the cost-sharing, truthful mechanism-design problem to the truthful mechanism-design problem?
We give two simple, but extremely versatile, black-box reductions, that answer the above questions affirmatively. In combination, they redduce the cost-sharing mechanism-design problem to the algorithmic cost-minimization problem of finding a minimum-cost solution for a set of players.
The talk will be self contained.