Equilibria in Congestion Game Models: Existence, Complexity and Efficiency

This diploma thesis lies in the general area of Game Theory and copes with the study of the interaction of independent selfish agents under the absence of some central authority. We mainly focus on situations where players want to allocate resources in order to perform some task and hence affect the other players implicitly. Such situations are typically modeled with Congestion Games. Initially, we present some basic notions of Game Theory, mainly focusing on its aspects that are related to Computer Science. Subsequently we study the characteristics of Congestion Games and present some interesting game theoretic models related to them. The first question that we focus on is the existence of a Pure Nash Equilibrium (PNE) in the most important models related to Congestion Games. We present significant results from bibliography and we give a novel proof on the existence of PNE in matroid weighted congestion games with non-increasing facility cost functions. The second issue we investigate is the complexity of computing a PNE in Con- gestion Games. We give analytic proofs on recent results concerning this problem. Moreover, we present some new results on the complexity of computing a PNE in an alternative model of Congestion Games. Moreover, we examine the deterioration caused by selfishness in congestion games and present some recent results on the Price of Anarchy for some interesting Congestion Game models. Finally, we introduce a new model that is related to selfish routing and wavelenght assignment in multifiber all-optical networks and we compute its Price of Anarchy for several intuitively interesting social cost functions.