Tutte seminar - Chaitanya Swamy

Friday, October 12, 2012 3:30 pm - 4:30 pm EDT (GMT -04:00)

Black-Box Reductions for Cost-Sharing Mechanism Design

Speaker: Levent Tunçel
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

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 reduce 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.