University of Twente Student Theses

Login

Computing the Sequential Price of Anarchy of Affine Congestion Games Using Linear Programming Techniques

Bosse, MSc Joran V. van den (2021) Computing the Sequential Price of Anarchy of Affine Congestion Games Using Linear Programming Techniques.

[img] PDF
1MB
Abstract:For the class of Congestion Games with affine cost functions the Sequential Price of Anarchy (SPoA) has been determined exactly when two or three players are involved. For more than three players, the exact value was unknown. There existed a Linear Program (LP) that could be used to determine the SPoA for any finite number of players. However, this Linear Program has too many variables to be solved in reasonable time when the number of players is 4 or higher. In this thesis column generation has been used to reduce the number of variables in that LP, in order to compute the SPoA for the 4 player case. Besides that, additional constraints have been added to analyse the worst case instance that the Linear Program describes for the 3 player case. Moreover, a variant of the LP has been presented that can determine the SPoA for any class of congestion games for which the number of resources and the action sets have been fixed. Finally, the LP has been modified in order to compute the exact SPoA for two classes of weighted congestion games, with the use of LP duality.
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/87784
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page