Congestion games with faulty or asynchronous resources

Congestion games with faulty or asynchronous resources

Abstract

We introduce the concepts of resource failures and asynchronous task execution in congestion games. We present two models -- congestion games with load-dependent failures (CGLFs) in which resources may fail to execute their assigned tasks with some (congestion-dependent) probability, and asynchronous congestion games (ACGs) in which resources execute their assigned tasks not simultaneously but in a randomly chosen order. The random order of task execution reflects, for instance, a situation where players and resources are the elements of an asynchronous distributed system, in which each process has its own independent clock. As it turns out, these new settings lead to interesting observations about the interplay between the need to deal with failures or asynchronous nature of processes, and the emergence of congestion in non-cooperative systems. Indeed, the classical idea of using several resources in order to overcome the possibility of failure or to decrease the expected time of task completion, may result in a high congestion, hurting all agents in the system. Although, as we show, CGLFs and ACGs do not admit a potential function and therefore are not isomorphic to classic congestion games, we prove the existence of a pure strategy Nash equilibrium in the above classes of games. We also develop polynomial time algorithms for computing a pure strategy equilibrium in these games.