CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe 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.
| Titolo: | Selfishness, Collusion and Power of Local Search for the ADMs Minimization Problem | |
| Autori: | ||
| Data di pubblicazione: | 2008 | |
| Rivista: | ||
| 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. | |
| Handle: | http://hdl.handle.net/20.500.12571/648 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| 2008_ComputNetw_52_Flammini.pdf | Documento in Pre-print | Accesso gratuito | Open Access Visualizza/Apri |
http://hdl.handle.net/20.500.12571/648
Copyright © 2022