University of Twente Student Theses
Asymptotic price of anarchy for affine, symmetric, kuniform congestion games
Steenhuisen, Berend (2017) Asymptotic price of anarchy for affine, symmetric, kuniform congestion games.

PDF
1MB 
Abstract:  We consider the class of affine, symmetric, kaffine 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 table 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, kunifo In this thesis we will improve the upper and lower bound to a constant of � 1:35188.rm congestion games lies between 74�2�1:343 and 28/13 � 2.15. 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 ! 1, 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:  http://purl.utwente.nl/essays/74764 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page