Algorithmic game theory and games with a low Price of Anarchy

When we talk about a game, or game setting of certain process, this means we are in the world where there are selfish and greedy entities, which compete each other. It is much harder to control and manoeuvre this environment, when compared to a setting when there is a central authority which may impose any demand on the environment and all entities. Among such “anarchy” setting are for example computer networks on the Internet (hardly anyone can dictate how should the connected computers behave, but still we would like to impose certain protocols and recommended behaviour), democratic economies (we need to preserve some freedom of subjects on the market, but we would still like to collect taxes, punish unfair traders and manipulate the whole economics in a certain direction), and many other examples. In this talk we give a gentle introduction to the topic of algorithmic game theory with the focus on the “price of anarchy” concept. We then show the following result: when we consider the competitive setting of the vertex cover problem for graphs and its generalisations, where each vertex is controlled by an independent player, we design a game that reaches the same global quality vertex (set) cover as in the central-authority setting. Here we have to measure the quality of the reached cover in the terms of approximation of the optimal solution, as the vertex cover is a classical NP-complete problem.