Altruism in atomic congestion games

Martin Hoefer*, Alexander Skopalik

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

21 Citations (Scopus)

Abstract

This paper studies the effects of introducing altruistic agents into atomic congestion games. Altruistic behavior is modeled by a trade-off between selfish and social objectives. In particular, we assume agents optimize a linear combination of personal delay of a strategy and the resulting social cost. Stable states are the Nash equilibria of these games, and we examine their existence and the convergence of sequential best-response dynamics. For symmetric singleton games with arbitrary delay functions we provide a polynomial time algorithm to decide existence for symmetric singleton games. Our algorithm can be extended to compute best and worst Nash equilibria if they exist. For more general congestion games existence becomes NP-hard to decide, even for symmetric network games with quadratic delay functions. Perhaps surprisingly, if all delay functions are linear, there exists a Nash equilibrium and any better-response dynamics converges. In addition, we consider a scenario in which a central altruistic institution can motivate agents to act altruistically. We provide constructive and hardness results for finding the minimum number of altruists to stabilize an optimal congestion profile and more general mechanisms to incentivize agents to adopt favorable behavior.

Original languageEnglish
Title of host publicationAlgorithms - ESA 2009
Subtitle of host publication17th Annual European Symposium, Proceedings
EditorsAmos Fiat, Peter Sanders
Pages179-189
Number of pages11
ISBN (Electronic)978-3-642-04128-0
DOIs
Publication statusPublished - 2 Nov 2009
Externally publishedYes
Event17th Annual European Symposium on Algorithms, ESA 2009 - Copenhagen, Denmark
Duration: 7 Sep 20099 Sep 2009
Conference number: 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5757 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th Annual European Symposium on Algorithms, ESA 2009
Abbreviated titleESA 2009
CountryDenmark
CityCopenhagen
Period7/09/099/09/09

Fingerprint Dive into the research topics of 'Altruism in atomic congestion games'. Together they form a unique fingerprint.

Cite this