Ph.D Thesis

Ph.D StudentPolukarov Mariya
SubjectCongestion Games with Resource Failures
DepartmentDepartment of Industrial Engineering and Management
Supervisors ASSOCIATE PROF. Michal Penn
PROF. Moshe Tennenholtz
Full Thesis textFull thesis text - English Version


The study of congestion in systems is central to many disciplines. This congestion may be a result of the actions taken by self-motivated participants, and therefore congestion settings deserve extensive study. Surprisingly, although the notion of machine failures is widely discussed in the OR and CS literature, the relationships between congestion settings with self-motivated participants and machine failures has not been studied. In order to address this need we introduce the concept of resource failures in congestion games. As it turns out, these new settings lead to interesting observations about the interplay between the need to deal with failures and the emergence of congestion in non-cooperative systems. Indeed, the classical idea of using several resources in order to overcome the possibility of failures may result in a highly congested system, hurting all agents in the system. A major goal of this research project is the introduction of models to deal with congestion games with failures. We introduce and study several models -- congestion games with failures (CGFs), taxed congestion games with failures (TCGFs) and congestion games with load-dependent failures (CGLFs) --  that differ in the following aspects: failure probabilities may be constant or congestion-dependent; agents may have different interests and utilities -- in a CGLF, a player wishes to maximize the difference between his benefit from a successful task completion and the total cost of the utilized resources, in a (T)CGF, the aim of a player is to minimize his expected delay. Although, as we show, CGLFs and (T)CGFs do not admit a potential function and therefore are not isomorphic to 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 pure strategy equilibria.

The idea of using several resources may also arise in asynchronous distributed systems, in which each process has its own independent clock. A player may assign his task to several resources, hoping that his task will be completed in a short time by at least one of the resources. To model such situations we present a class of asynchronous congestion games (ACGs), in which resources execute their assigned tasks in a randomly chosen order. We prove that ACGs possess Nash equilibria in pure strategies, despite the non-existence of a potential function, and present a polynomial time algorithm for finding such equilibria in a given ACG.