ABSTRACT
Nowadays, understanding the Internet is one of the major issues in theoretical computer science [1]. Toward this direction, a number of researchers consider the Internet as a system of rational selfish agents (or users), each acting his/her own profit. This simplification makes the use of many notions introduced in noncooperative game theory possible [2,3], where every agent determines her behavior (strategy) based on the other agents’ strategies. The aim of every agent is to maximize her own individual profit, without taking into account the consequences of her choice to the other agents or to the system’s performances. A central notion in this field is the notion of Nash equilibrium [2] defined as a combination of (deterministic or randomized) choices (strategies), one for each agent, from which no agent has an incentive to unilaterally change her strategy. The existence of such an equilibrium is assured for every finite game from the famous theorem of Nash [2]. However, even if, in the last few years, some progress has been made for particular classes of games [4,5], it remains an open question to decide whether or not the problem of computing Nash equilibrium is in general solvable in polynomial time. This question is actually among the most challenging open questions in theoretical computer science [1]. However, a much progress has been made in the related question of evaluating the impact of the selfishness of the agents on the efficient use of the system, or, in other words, on the social welfare measured in terms of an appropriate global objective function. Given that for a finite game there are, in general, a number of different Nash equilibria that may have different objective function values, this question is very similar to the one of evaluating the quality of a feasible solution for a combinatorial optimization problem. Exploiting this relation, Koutsoupias and Papadimitriou [6] adopted a worst-case approach and they introduced the notion of the price of anarchy (also known as coordination ratio), which is defined as the ratio of the value of the objective function in the worst Nash equilibrium and its value at the optimum. In fact, the price of anarchy evaluates the cost of the lack of coordination-as opposed to the competitive ratio, that evaluates the lack of information
in the context of the on-line computation or the approximation ratio, that is used to evaluate the lack of unbounded computational resources in the context of the off-line computation.
