We investigate the approximation ratio of the solutions achieved after a one-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 cost per player, as a measure of the quality of a given solution. For the social function SUM and one-round walks starting from the empty strategy profile, we close the gap 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 International Colloquium on Automata, Languages and Programming (ICALP), LNCS, vol. 4051, pp. 311–322, Springer, Berlin, 2006) by providing a matching lower bound whose construction 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) strategy profile.

Performance of One-Round Walks in Linear Congestion Games

FLAMMINI, MICHELE;
2011-01-01

Abstract

We investigate the approximation ratio of the solutions achieved after a one-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 cost per player, as a measure of the quality of a given solution. For the social function SUM and one-round walks starting from the empty strategy profile, we close the gap 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 International Colloquium on Automata, Languages and Programming (ICALP), LNCS, vol. 4051, pp. 311–322, Springer, Berlin, 2006) by providing a matching lower bound whose construction 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) strategy profile.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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: https://hdl.handle.net/11697/12861
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 17
social impact