# University of Twente Student Theses

## 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.*

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