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.

[img] PDF
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:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page