Search Results

Documents authored by Polukarov, Maria


Document
Congestion games with failures

Authors: Michal Penn, Maria Polukarov, and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)


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.

Cite as

Michal Penn, Maria Polukarov, and Moshe Tennenholtz. Congestion games with failures. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.05011.7},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail