University of Twente Student Theses
As of Friday, 8 August 2025, the current Student Theses repository is no longer available for thesis uploads. A new Student Theses repository will be available starting Friday, 15 August 2025.
The Price of Anarchy for Matching Congestion Games
Bleyenberg, S.D. (2022) The Price of Anarchy for Matching Congestion Games.
|
PDF
2MB |
| Abstract: | In this thesis we mainly study matching congestion games with identity cost functions and bipartite graphs. In a matching congestion game resources are represented by the edges of a graph and the edges in every strategy form a perfect matching. We are interested in the price of anarchy; the total cost of the worst equilibrium when agents choose selfishly their own strategy relative to the total cost of a strategy profile that minimizes total cost. With p the number of players, we found that the upper bound is equal to 2-1/p for two, three and four players. For five or more players the best bound is still the bound which was already known, namely 5/2. For a special case, when the graph allows as many disjoint matchings as there are players, our proof shows that the price of anarchy is at most 2-1/p. For this special case this bound also holds for five or more players. We found a lower bound example, which also holds for the special case, where the price of anarchy is equal to 2-1/p for two players, which makes the bound tight. |
| 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/92090 |
| 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