Congestion games with failures

Michal Penn, Maria Polukarov, Moshe Tennenholtz

Abstract

Congestion Games with Failures (CGFs) extend the classic game-theoretic framework of resource allocation to environments where resources are prone to failure. In these games, agents must navigate a trade-off between reliability—achieved through redundancy—and the increased costs resulting from congestion. This paper proves that while CGFs lack a universal potential function, they always admit a pure-strategy Nash equilibrium (PNE). We provide a polynomial-time algorithm for computing a PNE and analyze the efficiency of these equilibria, revealing that the Price of Anarchy can be significantly higher than in standard congestion games.

Introduction

In traditional congestion games, such as traffic routing or network flow, resources are assumed to be perfectly reliable. An agent's cost is determined solely by the number of other agents sharing the same resource. However, in real-world distributed systems, telecommunications, and service markets, resources frequently fail. To mitigate this risk, rational agents may employ redundancy, selecting multiple resources to ensure task completion.

This "selfish redundancy" introduces a new dynamic: adding resources to improve individual reliability increases congestion for others, potentially degrading the performance of the entire system. Before this work, the game-theoretic implications of this tension between reliability and rivalry had not been formally explored. This paper addresses whether stable outcomes exist when agents are free to choose redundant, yet congested, resources.

Modeling Redundancy and Congestion

The authors define a formal model involving $n$ agents and $m$ service providers (SPs). Each SP $j$ is characterized by a success probability $p_j$ (or failure probability $f_j = 1 - p_j$) and a cost function $c_j(k)$ that increases with the number of users $k$.

Unlike standard games where an agent picks a single resource, in a CGF, an agent's strategy is to choose a subset of resources. The agent's final cost is the minimum cost among their successful attempts. If all selected resources fail, the agent incurs a high failure cost $W_i$. This creates a complex payoff structure where the expected cost depends on the failure probabilities and the congestion levels of all chosen resources.

Example cost calculations for two agents across different resource selection strategies, illustrating the impact of failure probabilities and congestion costs.

Algorithmic Stability and the Potential Function Problem

A central challenge in game theory is determining whether a stable state—a Nash equilibrium—exists. In many congestion games, existence is guaranteed by a "potential function," a global scalar value that tracks individual improvements. The authors demonstrate that CGFs are not potential games, meaning they do not follow the standard mathematical path to stability used in classic congestion models.

Despite this, they prove that every CGF possesses at least one pure-strategy Nash equilibrium. They introduce a constructive NE-algorithm that finds an equilibrium in polynomial time. The algorithm operates by sorting agents based on their cost thresholds for specific service providers and assigning resources in a prioritized sequence, making it computationally practical for large systems.

Key Insights and Results

  • Congestion Invariance: While multiple Nash equilibria may exist, the authors show that the congestion levels on each resource remain nearly identical across different equilibrium profiles.
  • The Price of Anarchy: In symmetric games (where agents and resources are identical), the Price of Anarchy—the ratio of the worst selfish outcome to the social optimum—is not bounded by a constant. It can grow linearly with the number of resources $m$. This suggests that without coordination, agents' desire for redundancy can lead to massive system-wide inefficiency compared to classic models where the Price of Anarchy is often bounded by small constants (like 4/3).
  • Existence and Efficiency: The primary contribution is the proof of existence for PNE in a non-potential game and the provision of an efficient algorithm to locate it.

Conclusion and Future Directions

This research bridges the gap between reliability engineering in distributed systems and the strategic analysis of congestion games. While the current model assumes fixed failure probabilities and full information, it provides a rigorous foundation for future work. Potential extensions include modeling congestion-dependent failures—where high load increases the probability of a crash—and designing economic mechanisms, such as taxes or subsidies, to align selfish redundancy with social welfare.

Summary updated

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
@inproceedings{penn2005congestion,
  author = {Michal Penn and Maria Polukarov and Moshe Tennenholtz},
  title = {{Congestion games with failures}},
  booktitle = {EC},
  year = {2005},
  doi = {10.1145/1064009.1064037},
}
Figure