License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05011.7
URN: urn:nbn:de:0030-drops-2098
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/209/
Go to the corresponding Portal

Penn, Michal ; Polukarov, Maria ; Tennenholtz, Moshe

Congestion games with failures

pdf-format:
05011.PolukarovMaria.Paper.209.pdf (0.3 MB)

Abstract

We introduce a new class of games, congestion games with
failures (CGFs), which extends the class of congestion games to
allow for facility failures. In a CGF agents share a common set of
facilities (service providers), where each service provider (SP)
may fail with some known probability. For reliability reasons, an
agent may choose a subset of the SPs in order to try and perform
his task. The cost of an agent for utilizing any SP is an
agent-specific function of the total number of agents using this
SP. A main feature of this setting is that the cost for an agent
for successful completion of his task is the minimum of the costs
of his successful attempts. We show that although congestion games
with failures do not admit a potential function, and thus are not
isomorphic to classic congestion games, they always possess a
pure-strategy Nash equilibrium. Moreover, an efficient algorithm
for the construction of pure-strategy Nash equilibrium profile is
presented. We also show that the SPs congestion experienced in
different Nash equilibria is (almost) unique. For the subclass of
symmetric CGFs we give a characterization of best and worst Nash
equilibria, present algorithms for their construction, and compare
the social disutilities of the agents at these points.

BibTeX - Entry

@InProceedings{penn_et_al:DagSemProc.05011.7,
  author =	{Penn, Michal and Polukarov, Maria and Tennenholtz, Moshe},
  title =	{{Congestion games with failures}},
  booktitle =	{Computing and Markets},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/209},
  URN =		{urn:nbn:de:0030-drops-2098},
  doi =		{10.4230/DagSemProc.05011.7},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}

Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio
Collection: 05011 - Computing and Markets
Issue Date: 2005
Date of publication: 19.07.2005

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