Computer Science – Computer Science and Game Theory
Scientific paper
2011-12-15
Computer Science
Computer Science and Game Theory
WINE'11
Scientific paper
We study the inefficiency of equilibria for various classes of games when players are (partially) altruistic. We model altruistic behavior by assuming that player i's perceived cost is a convex combination of 1-\alpha_i times his direct cost and \alpha_i times the social cost. Tuning the parameters \alpha_i allows smooth interpolation between purely selfish and purely altruistic behavior. Within this framework, we study altruistic extensions of linear congestion games, fair cost-sharing games and valid utility games. We derive (tight) bounds on the price of anarchy of these games for several solution concepts. Thereto, we suitably adapt the smoothness notion introduced by Roughgarden and show that it captures the essential properties to determine the robust price of anarchy of these games. Our bounds show that for congestion games and cost-sharing games, the worst-case robust price of anarchy increases with increasing altruism, while for valid utility games, it remains constant and is not affected by altruism. However, the increase in the price of anarchy is not a universal phenomenon: for symmetric singleton linear congestion games, we derive a bound on the pure price of anarchy that decreases as the level of altruism increases. Since the bound is also strictly lower than the robust price of anarchy, it exhibits a natural example in which Nash equilibria are more efficient than more permissive notions of equilibrium.
Chen Po-An
Keijzer Bart de
Kempe David
Schaefer Guido
No associations
LandOfFree
The Robust Price of Anarchy of Altruistic Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Robust Price of Anarchy of Altruistic Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Robust Price of Anarchy of Altruistic Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-136208