Cost sharing mechanisms for near-optimal traffic aggregation and network design

Abstract

A fundamental network design problem is the one of Traffic Aggregation or Network Design. The goal is to design a network which is able to support a unit flow for each commodity, at a time, between its source-sink pair, e.g., to support buffered multicast traffic. When the flows are unsplittable, this corresponds to the Steiner forest problem and to the problem of sharing cost of multicast by different users. As a result of greedy selfish behavior of users in the network design game, the overall quality of the resulting solution is often not as good as the globally optimum solution of the underlying problem. We are therefore interested in the problem of designing distributed cost sharing mechanisms that induce the selfish agents to converge to the near-optimum solutions. In this paper, our main contribution is showing that 1 + ε ratio can be achieved by (non-obvious) unfair cost sharing mechanism, at least for the fractional version of the problem. Our second contribution is showing how to implement our cost sharing mechanism which guarantees fast convergence to a near-optimum equilibrium. Copyright 2008 ACM.