University of Twente Student Theses
Routing Games : analysis of nonatomic and atomic selfish routing models
Bloemberg, A.J. (2016) Routing Games : analysis of nonatomic and atomic selfish routing models.
PDF
1MB |
Abstract: | This work, based on work of Roughgarden (2007), analyzes two models in routing games: the nonatomic and the atomic selfish routing models. Players route a certain amount of traffic through a network consisting of vertices and edges. Each edge has a nondecreasing, nonnegative cost function. For both models, the notion of an equilibrium flow of traffic through the network is defined, as well as the optimal flow. The price of anarchy is defined as the ratio of the cost of the equilibrium flow with the highest total cost and the optimal flow. A proof is given for the existence of equilibrium flows in nonatomic instances and the fact that every equilibrium flow has equal cost. Furthermore, it is proven that the price of anarchy in affine nonatomic instances (instances with only affine cost functions) is at most 4/3. An equilibrium flow in atomic instances need not exist, but it is proven it does when every player routes the same amount of traffic or when all cost functions are affine. Lastly, the price of anarchy in affine weighted atomic instances is proven to be at most (3+√5)/2 and in affine unweighted atomic instances at most 5/2. |
Item Type: | Essay (Master) |
Faculty: | BMS: Behavioural, Management and Social Sciences |
Subject: | 31 mathematics |
Programme: | Science Education and Communication MSc (60708) |
Link to this item: | https://purl.utwente.nl/essays/69703 |
Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Repository Staff Only: item control page