Social Context and Cost-Sharing in Congestion Games

Kotsialou, G (2017) Social Context and Cost-Sharing in Congestion Games. PhD thesis, University of Liverpool.

Text 200974248_Jul17.pdf - Unspecified Download (1MB)

Abstract

Congestion games are one of the most prominent classes of games in non- cooperative game theory as they model a large collection of important applications in networks, such as selfish routing in traffic or telecommunications. For this reason, congestion games have been a driving force in recent research and my thesis lies on two major extensions of this class of games. The first extension considers congestion games embedded in a social network where players are not necessarily selfish and might care about others. We call this class social context congestion games and study how the social interactions among players affect it. In particular, we study existence of approximate pure Nash equilibria and our main result is the following. For any given set of cost functions, we provide a threshold value such that: for the class of social context congestion games with cost functions within the given set, sequences of improvement steps of players, are guaranteed to converge to an approximate pure Nash equilibrium if and only if the improvement step factor is larger than this threshold value. The second topic considers weighted congestion games under a fair cost sharing system which depends on the weight of each player, the (weighted) Shapley values. This class considers weighted congestion games where (weighted) Shapley values are used as an alternative (to proportional shares) for distributing the total cost of each resource among its users. We study the efficiency of this class of games in terms of the price of anarchy and the price of stability. Regard- ing the price of anarchy, we show general tight bounds, which apply to general equilibrium concepts. For the price of stability, we prove an upper bound for the special case of Shapley values. This bound holds for general sets of cost functions and is tight in special cases of interest, such as bounded degree polynomials. Also for bounded degree polynomials, we show that a slight deviation from the Shapley value has a huge impact on the price of stability. In fact, the price of stability becomes as bad as the price of anarchy. For this model, we also study computation of equilibria. We propose an algorithm to compute approximate pure Nash equilibria which executes a polynomial number of strategy updates. Due to the complex nature of Shapley values, computing a single strategy update is hard, however, applying sampling techniques allow us to achieve polynomial running time. We generalise the previous model allowing each player to control multiple flows. For this generalised model, we study existence and efficiency of equilibria. We exhibit a separation from the original model (each player controls only one flow) by proving that Shapley values are the only cost-sharing method that guarantees pure Nash equilibria existence in the generalised model. Also, we prove that the price of anarchy and price of stability become no larger than in the original model.

Item Type:	Thesis (PhD)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	21 Dec 2017 10:21
Last Modified:	16 Jan 2024 17:21
DOI:	10.17638/03010452
Supervisors:	Gairing, MG
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3010452