Approximation through Non-Cooperation

In the first part of the talk, we survey our recent results for congestion games and extensions thereof. In particular, we present results on the price of anarchy and the complexity of pure Nash equilibria.

In the second part, we will introduce a new class of congestion games that we call covering games. These games have a general covering problem as an underlying structure. For covering a resource the players receive a payoff which is given by a utility sharing function. This function defines the fraction that each covering player receives from the weights of the elements. We show how to construct a utility sharing function that optimizes the price of anarchy.
Moreover, we extend this to a local-search approximation algorithm with best possible approximation ratio.