University of Twente Student Theses
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