Group-Strategy Proof Mechanisms for Network Design Games
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1