Congestion games with failures

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.