University of Twente Student Theses
The Price of Anarchy of Symmetric and Semi-Symmetric Uniform Congestion Games
Kraakman, Yanna (2021) The Price of Anarchy of Symmetric and Semi-Symmetric Uniform Congestion Games.
|
PDF
1MB |
| Abstract: | The price of anarchy of a system indicates how bad the system may perform if it is not regulated and actors act selfishly. In this research, we analyse the price of anarchy of two subclasses of atomic congestion games: symmetric uniform congestion games, in which all players pick the same number of resources from a set, and semi-symmetric uniform congestion games, in which the number of resources that players pick may differ. For the symmetric games, we prove that the price of anarchy lies between 1.34 and 2.02 if there are affine cost functions. For such games in which every player picks exactly 2 resources, the price of anarchy lies between 4/3 and 1.81. The results are generalised for games with cost functions of maximum degree d and for small d improve upon the known upper bound for the price of anarchy of general atomic congestion games. For semi-symmetric games, we prove that the price of anarchy is at least 5/3 if there are affine cost functions. For such games in which every player picks at most 2 resources, the price of anarchy lies between 1.4 and 2. Again, the results are generalised for games with cost functions of maximum degree d and for small d improve upon the known upper bound for the price of anarchy of general atomic congestion games. |
| 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/89018 |
| 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