Friday, October 19, 2007
3:30 pm, MC 5158

Jochen Könemann
University of Waterloo

Group-Strategy Proof Mechanisms for Network Design Games

About 15 years ago, Goemans and Williamson formally introduced the primal-dual framework for approximation algorithms and applied it to a class of network design optimization problems. Since then literally hundreds of results appeared that extended, modified and applied the technique to a wide range of optimization problems.
In this talk we define a class of cost-sharing games arising from Goemans' and Williamson's original network design problems. We then show how to derive a group-strategyproof ( i.e., collusion resistant) mechanism for such a game from an existing primal-dual algorithm for the underlying optimization problem. We further show that the budget-balance factor of the resulting mechanism is proportional to the performance ratio of the primal-dual algorithm if the optimization problem satisfies an additional technical condition.

Joint work with S. Leonardi, G. Schaefer and D. Wheatley.