University of Twente Student Theses
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.
|
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: | https://purl.utwente.nl/essays/87784 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page