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.