Altruism and its impact on the price of anarchy

Po-An Chen, Bart De Keijzer, David Kempe, Guido Schäfer

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

We study the inefficiency of equilibria for congestion games when players are (partially) altruistic.We model altruistic behavior by assuming that player i's perceived cost is a convex combination of 1 - α i times his direct cost and α i times the social cost. Tuning the parameters α i allows smooth interpolation between purely selfish and purely altruistic behavior. Within this framework, we study primarily altruistic extensions of (atomic and nonatomic) congestion games, but also obtain some results on 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 atomic congestion games and cost-sharing games, the robust price of anarchy gets worse 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 general nonatomic congestion games with uniform altruism, the price of anarchy improves with increasing altruism. For atomic and nonatomic symmetric singleton congestion games, we derive bounds on the pure price of anarchy that improve as the average level of altruism increases. (For atomic games, we only derive such bounds when cost functions are linear.) Since the bounds are also strictly lower than the robust price of anarchy, these games exhibit natural examples in which pure Nash equilibria are more efficient than more permissive notions of equilibrium.

Original languageEnglish
Article number17
JournalACM Transactions on Economics and Computation
Volume2
Issue number4
DOIs
StatePublished - 1 Oct 2014

Keywords

  • Altruism
  • Congestion games
  • Cost-sharing games
  • Economics
  • F.0 [theory of computation]: general
  • Price of anarchy
  • Selfishness
  • Theory
  • Valid utility games

Fingerprint Dive into the research topics of 'Altruism and its impact on the price of anarchy'. Together they form a unique fingerprint.

Cite this