Selfishness, Collusion and Power of Local Search for the ADMs Minimization Problem

We consider non-cooperative games in all-optical networks where users share the cost ofthe used ADM switches for realizing given communication patterns. We show that the twofundamental cost sharing methods, Shapley and Egalitarian, induce polynomial converginggames with price of anarchy at most 5/3, regardless of the network topology. Such a bound istight even for rings. Then, we show that if collusion of at most k players is allowed, theEgalitarian method yields polynomially converging games with price of collusion between 3/2 and 3/2 + 1/k. This result is very interesting and quite surprising, as the best known approximationratio, that is 3/2 + epsilon, can be achieved in polynomial time by uncoordinated evolutionsof collusion games with coalitions of increasing size. Finally, the Shapley method does notinduce well defined collusion games, but can be exploited in the definition of local searchalgorithms with local optima arbitrarily close to optimal solutions. This would potentiallygenerate PTAS, but unfortunately the arising algorithm might not converge. The determinationof new cost sharing methods or local search algorithms reaching a compromisebetween Shapley and Egalitarian is thus outlined as being a promising and worth pursuinginvestigating direction.