We investigate the approximation ratio of the solutions achieved after aone-round walk in linear congestion games. We consider the social functions SUM,defined as the sum of the players’ costs, and MAX, defined as the maximum costper player, as a measure of the quality of a given solution. For the social functionSUM and one-round walks starting from the empty strategy profile, we close thegap between the upper bound of 2 + √5 ≈ 4.24 given in Christodoulou et al. Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), LNCS, vol. 3884, pp. 349–360, Springer, Berlin, 2006) and the lower bound of 4 derived in Caragiannis et al. (Proceedings of the 33rd InternationalColloquium on Automata, Languages and Programming (ICALP), LNCS, vol. 4051,pp. 311–322, Springer, Berlin, 2006) by providing a matching lower bound whoseconstruction and analysis require non-trivial arguments. For the social function MAX, for which, to the best of our knowledge, no results were known prior to this work, we show an approximation ratio of Theta(n^(3/4)) (resp. Theta(n √n)), where n is the number of players, for one-round walks starting from the empty (resp. an arbitrary) strategyprofile.

Performance of One-Round Walks in Linear Congestion Games

Flammini M;
2011

Abstract

We investigate the approximation ratio of the solutions achieved after aone-round walk in linear congestion games. We consider the social functions SUM,defined as the sum of the players’ costs, and MAX, defined as the maximum costper player, as a measure of the quality of a given solution. For the social functionSUM and one-round walks starting from the empty strategy profile, we close thegap between the upper bound of 2 + √5 ≈ 4.24 given in Christodoulou et al. Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), LNCS, vol. 3884, pp. 349–360, Springer, Berlin, 2006) and the lower bound of 4 derived in Caragiannis et al. (Proceedings of the 33rd InternationalColloquium on Automata, Languages and Programming (ICALP), LNCS, vol. 4051,pp. 311–322, Springer, Berlin, 2006) by providing a matching lower bound whoseconstruction and analysis require non-trivial arguments. For the social function MAX, for which, to the best of our knowledge, no results were known prior to this work, we show an approximation ratio of Theta(n^(3/4)) (resp. Theta(n √n)), where n is the number of players, for one-round walks starting from the empty (resp. an arbitrary) strategyprofile.
File in questo prodotto:
File Dimensione Formato  
2011_TheoryComputSyst_49_Bilo.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 750.63 kB
Formato Adobe PDF
750.63 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/2383
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 14
social impact