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-01-01
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 | 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.