Congestion Games: Stochastic Extensions And Techniques For Reducing The Price Of Anarchy

Abstract

The subject of this thesis is the theoretical analysis and generalization of congestion games models and it aims to provide a study on methods for reducing the Price of Anarchy and a study related to stochastic extensions of congestion games and in which extend the Price of Anarchy may be affected within them. First, the literature that relates mostly to the problems studied is presented and rightafter an extensive presentation of the results of the thesis follows. The problem of finding or approximating the best subnetwork in bottleneck routing games is studied. Although the corresponding problem in additive costs congestion games is almost fully understood, for the problem studied here, the existing results hold for more general games and in fact are much weaker than the ones presented here. For the simplest version of this problem, via a complex reduction, an NP hardness results for finding or approximating the best subnetwork of the underlying network is proved: it is NP hard to approximate the best subnetwork by a factor less than O(n^0.121) (where n is the number of nodes of the network). In the positive side it is proven that in some subclasses of these games the paradox does not appear at all and also it is given an approximation algorithm for some cases where the NP hardness reductions cannot apply. Results that have to do with Braess paradox in additive costs congestion games are presented. Prior to the work presented here, it has been proved that if the underlying network of a congestion game is a random Erdos-Renyi graph then with high probability it suffers from Braess Paradox. Here, it is proven that the problem of finding the best subnetwork in such random networks can be essentially reduced to the problem of finding the best subnetwork of a network belonging to the simplest class of graphs that may suffer from the paradox. Using a very recent result from the theory of probabilities, it is given a polynomial approximation algorithm for finding best subnetworks in such networks. Then, the expansion properties of Erdos-Renyi graphs are used and an approximately good subnetwork for the initial network is drawn.By slightly changing direction, the basic properties of congestion games with uncertain delays and risk averse users are studied. The classic formulation of congestion games ignores uncertainty in delays that arises in many real life situations. Modelling the cause of uncertainty in delays, two orthogonal models are introduced, one with stochastic players, where each players participates in the game with a given probability and thus the actual delay on the edges that players choose gets uncertain, and another with stochastic edges where each edge, with a given probability, may ‘‘fail’’ and provide greater delay to the players using it. For the arising classes of games, the existence of pure Nash equilibrium and potentials and the behaviour of the price of anarchy is studied. Uniting the above directions, a new way for improving the price of anarchy in congestion games with uncertain delays and risk averse users is given. More specifically, it is shown that if one can insert uncertainty in the edges of the network in a way that the expected cost of those edges remains the same, then, because of the risk aversion of the players, these edges become less attractive for the players. Thus, the price of anarchy may improve as more players may turn to edges that the optimal solution would choose for them. The arising algorithmic problem relates to congestion games with restricted tolls and results can also be drawn from there. In this thesis Karush-Kuhn-Tucker conditions are closely followed and there are given results that give a better and ‘‘less cheap’’ use of extra uncertainty and provide better insight of the improvement in the price of anarchy.