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.
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