Cost-sharing mechanisms for Network Design
Stefano Leonardi, Visiting Faculty from Universita' di Roma "La Sapienza"
September 23rd 2005

Abstract

Today's Internet seamlessly connects billions of users that mostly pursue selfish motives in both, single-handed and collaborative ways. By design the Internet is anarchic and hence, it is devoid of a central authority that possesses global knowledge and the power to regulate the agents' behavior. In this talk we focus on the design of so called 'mechanisms' that encourage truthful and fair behavior among the agents/users by means of issuing rewards and by postulating interaction rules.

We present a first mechanism able to share between users in a fair manner the cost of a Steiner forest that connects a set of terminal pairs. This mechanism is also proved to recover at least 1/2 the cost of the solution. This mechanism is a primal dual algorithm based on a new linear programming relaxation that is shown stronger than the classical undirected cut relaxation. We also prove that no such mechanism can recover more than 1/2 of the cost of the solution for the Steiner tree game, therefore implying tightness of our result.

This is joint work with Guido Schaefer (TU Berlin), Jochen Koenemann (University of Waterloo) and Stefan van Zwam (Eindhoven University of Technology).