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.

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

FLAMMINI;
2008

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
2008_ComputNetw_52_Flammini.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Accesso gratuito
Dimensione 159.06 kB
Formato Adobe PDF
159.06 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12571/648
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact