Stability and convergence in selfish scheduling with altruistic agents

Martin Hoefer*, Alexander Skopalik

*Corresponding author for this work

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

8 Citations (Scopus)

Abstract

In this paper we consider altruism, a phenomenon widely observed in nature and practical applications, in the prominent model of selfish load balancing with coordination mechanisms. Our model of altruistic behavior follows recent work by assuming that agent incentives are 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. Our results show that even in very simple cases a variety of standard coordination mechanisms are not robust against altruistic behavior, as pure Nash equilibria are absent or better response dynamics cycle. In contrast, we show that a recently introduced Time-Sharing policy yields a potential game even for partially altruistic agents. In addition, for this policy a Nash equilibrium can be computed in polynomial time. In this way our work provides new insights on the robustness of coordination mechanisms. On a more fundamental level, our results highlight the limitations of stability and convergence when altruistic agents are introduced into games with weighted and lexicographical potential functions.

Original languageEnglish
Title of host publicationInternet and Network Economics
Subtitle of host publication5th International Workshop, WINE 2009, Proceedings
Pages616-622
Number of pages7
ISBN (Electronic)978-3-642-10841-9
DOIs
Publication statusPublished - 1 Dec 2009
Externally publishedYes
Event5th International Workshop on Internet and Network Economics, WINE 2009 - Rome, Italy
Duration: 14 Dec 200918 Dec 2009
Conference number: 5

Publication series

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

Conference

Conference5th International Workshop on Internet and Network Economics, WINE 2009
Abbreviated titleWINE 2009
CountryItaly
CityRome
Period14/12/0918/12/09

Fingerprint Dive into the research topics of 'Stability and convergence in selfish scheduling with altruistic agents'. Together they form a unique fingerprint.

Cite this