The Price of Anarchy for Matching Congestion Games

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.