The Price of Malice in Linear Congestion Games
Aaron Roth
[PDF]
We study the price of malice in linear congestion games using the
technique of no-regret analysis in the presence of Byzantine players.
Our assumptions about the behavior both of rational players, and of
malicious players are strictly weaker than have been previously used to
study the price of malice. Rather than assuming that rational players
route their flow according to a Nash equilibrium, we assume only that
the play so as to have no regret. Rather than assuming that malicious
players myopically seek to maximize the social cost of the game, we
study Byzantine players about whom we make no assumptions, who may be
seeking to optimize any utility function, and who may engage in an
arbitrary degree of counterspeculation. Because our assumptions are
strictly weaker than in previous work, the bounds we prove
on two measures of the price of malice hold also for the quantities
studied by Babaioff et al. and Moscibroda et al. We prove
tight bounds both for the special case of parallel link routing games,
and for general congestion games.