Monday March 6th at 4.30pm

do not have incentives to deviate. Because Nash equilibria do not optimize any global criterion per se, there is no apparent reason

why the social utility extracted when users act selfishly has to be high. Actually, equilibria can be very inefficient as

exemplified by the famous Prisoners' Dilemma. From this perspective, it is surprising that equilibria of network games

turn out to be provably efficient. Recent research quantified the extent of this efficiency by providing worst-case bounds on the

ratio of the social utility of equilibria to that of the social optimum. These bounds are commonly referred to by the "Price of

Anarchy" of the game.

In this talk, we concentrate on network games with atomic players in which each player controls a fixed demand that needs to be

sent from its origin to its destination. The player has to decide how that demand is sent across the network, possibly using

multiple paths. We present a bound on the price of anarchy that guarantees that equilibria are not too inefficient. In the case

of affine cost functions, this bound implies that equilibria face a degradation of at most 50% with respect to a socially optimal

solution. We then refine this bound using the Herfindahl index, a measure of the market power variability among the different

players. In addition, we provide a new potential function formulation for the case of symmetric players. It implies that

the cost of a Nash equilibria is no more than that of the corresponding nonatomic game, ruling out paradoxical phenomena

that may arise in the general case. All our results extend to the more general atomic congestion games with divisible demands, and

to mixed atomic and nonatomic games. This is joint work with Roberto Cominetti and Jose Correa.