University of Twente Student Theses

Login

Asymptotic price of anarchy for affine, symmetric, k-uniform congestion games

Steenhuisen, Berend (2017) Asymptotic price of anarchy for affine, symmetric, k-uniform congestion games.

[img] PDF
1MB
Abstract:We consider the class of affine, symmetric, k-affine congestion games and calculate the maximum Price of Anarchy for large number of players. The Price of Anarchy is defined as the ratio between the total cost of a stable equilibrium (Nash Equilbrium) and the total cost of the system’s optimum. The Nash Equilibrium is defined as a solution where no player can deviate and thereby lower his individual total cost, while the system’s optimum is defined as a solution where the social cost is minimized. Recent work has shown that the maximum Price of Anarchy for affine, symmetric, k-uniform congestion games lies between 7−4√2 ≈ 1.343 and 28/13 ≈ 2.15. In this thesis we will improve the upper and lower bound to a constant of ≈ 1.35188. We do this by calculating both an upper bound via an alternating paths based approach that examines the difference between the equilibrium and the optimal solution, and a lower bound by way of example. The alternating paths compare the system’s Nash Equilibrium with the Optimal solution in critical case games, which is a set of games for which the Price of Anarchy is highest. We show that for critical case games and when N → ∞, the price of anarchy can never be higher than ≈ 1.35188. We construct the lower bound by giving an example of a (near) critical case game with a Price of anarchy of ≈ 1.35188, thus proving that critical case games have a Price of Anarchy of at least this value.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:https://purl.utwente.nl/essays/74764
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page