Ph.D Student | Polukarov Mariya |
---|---|

Subject | Congestion Games with Resource Failures |

Department | Department of Industrial Engineering and Management |

Supervisors | Professor Michal Penn |

Professor Moshe Tennenholtz | |

Full Thesis text |

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.