License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.17
URN: urn:nbn:de:0030-drops-78576
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7857/
Go to the corresponding LIPIcs Volume Portal

Bilò, Vittorio ; Vinci, Cosimo

On the Impact of Singleton Strategies in Congestion Games

pdf-format:
LIPIcs-ESA-2017-17.pdf (0.5 MB)

Abstract

To what extent does the structure of the players' strategy space influence the efficiency of decentralized solutions in congestion games? In this work, we investigate whether better performance is possible when restricting to load balancing games in which players can only choose among single resources. We consider three different solutions concepts, namely, approximate pure Nash equilibria, approximate one-round walks generated by selfish players aiming at minimizing their personal cost and approximate one-round walks generated by cooperative players aiming at minimizing the marginal increase in the sum of the players' personal costs. The last two concepts can also be interpreted as solutions of simple greedy online algorithms for the related resource selection problem. Under fairly general latency functions on the resources, we show that, for all three types of solutions, better bounds cannot be achieved if players are either weighted or asymmetric. On the positive side, we prove that, under mild assumptions on the latency functions, improvements on the performance of approximate pure Nash equilibria are possible for load balancing games with weighted and symmetric players in the case of identical resources. We also design lower bounds on the performance of one-round walks in load balancing games with unweighted players and identical resources (in this case, solutions generated by selfish and cooperative players coincide).

BibTeX - Entry

@InProceedings{bil_et_al:LIPIcs:2017:7857,
  author =	{Vittorio Bil{\`o} and Cosimo Vinci},
  title =	{{On the Impact of Singleton Strategies in Congestion Games}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7857},
  URN =		{urn:nbn:de:0030-drops-78576},
  doi =		{10.4230/LIPIcs.ESA.2017.17},
  annote =	{Keywords: Congestion games, Nash equilibrium, price of anarchy, online load balancing, greedy algorithms}
}

Keywords: Congestion games, Nash equilibrium, price of anarchy, online load balancing, greedy algorithms
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI