Discrete Mathematics and Optimization Seminar


Nicolas Stier-Moses
Columbia Business School
Monday March 6th at 4.30pm
Burnside 1205



Title. The Efficiency of Equilibria in Network Games.

Abstract. According to standard solution concepts such as Nash equilibria, agents in a noncooperative game select strategies from which they
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.