research-article

Altruism and Its Impact on the Price of Anarchy

Authors:

Bart De Keijzer,

Guido SchäferAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 2, Issue 4

Article No.: 17, Pages 1 - 45

https://doi.org/10.1145/2597893

Published: 28 October 2014 Publication History

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 α_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.

References

[1]

H. Ackermann, H. Röglin, and B. Vöcking. 2006. Pure Nash equilibria in player-specific and weighted congestion games. In Proceedings of the 2nd Workshop on Internet and Network Economics.

Digital Library

[2]

A. Anagnostopoulos, L. Becchetti, B. De Keijzer, and G. Schäfer. 2013. Inefficiency of games with social context. In Proceedings of the 6th International Symposium on Algorithmic Game Theory.

[3]

E. Anshelevich, O. Bhardwaj, and M. Hoefer. 2012. Friendship, altruism, and reward sharing in stable matching and contribution games. http://arxiv.org/pdf/1204.5780.pdf.

[4]

E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. 2004. The price of stability for network design with fair cost allocation. In Proceedings of the 45th Symposium on Foundations of Computer Science.

Digital Library

[5]

V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. 2004. Local search heuristics for K-median and facility location problems. SIAM J. Comput. 33, 3.

Digital Library

[6]

R. J. Aumann. 1974. Subjectivity and correlation in randomized strategies. J. Math. Econ. 1, 1.

[7]

B. Awerbuch, Y. Azar, and A. Epstein. 2005. Large the price of routing unsplittable flow. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing.

Digital Library

[8]

M. Babaioff, R. Kleinberg, and C. H. Papadimitriou. 2009. Congestion games with malicious players. Games Econ. Behav. 67, 1.

[9]

T. Bergstrom. 1999. Systems of benevolent utility functions. J. Public Econ. Theory 1, 1.

[10]

Vittorio Bilò, Alessandro Celi, Michele Flammini, and Vasco Gallotti. 2013. Social context congestion games. Theoret. Comput. Sci. 514, 21--35. (Graph Algorithms and Applications: in Honor of Professor Giorgio Ausiello.)

Digital Library

[11]

A. Blum, E. Even-Dar, and K. Ligett. 2006. Routing without regret: On convergence to Nash equilibria of regret-minimizing algorithms in routing games. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing.

Digital Library

[12]

A. Blum, M. T. Hajiaghayi, K. Ligett, and A. Roth. 2008. Regret minimization and the price of total anarchy. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing.

Digital Library

[13]

V. Bonifaci, T. Harks, and G. Schäfer. 2007. The impact of stackelberg routing in general networks. Tech. Rep. COGA Preprint 020-2007, TU Berlin.

[14]

M. Bradonjic, G. Ercal-Ozkaya, A. Meyerson, and A. Roytman. 2009. On the price of mediation. In Proceedings of the 11th ACM Conference on Electronic Commerce.

Digital Library

[15]

F. Brandt, T. Sandholm, and Y. Shoham. 2007. Spiteful bidding in sealed-bid auctions. In Proceedings of the 20th International Joint Conference on Artifical Intelligence.

Digital Library

[16]

R. Buehler, Z. Goldman, D. Liben-Nowell, Y. Pei, J. Quadri, A. Sharp, S. Taggart, T. Wexler, and K. Woods. 2011. The price of civil society. In Proceedings of the 7th International Workshop on Internet and Network Economics.

Digital Library

[17]

I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, M. Kyropoulou, and E. Papaioannou. 2010. The impact of altruism on the efficiency of atomic congestion games. In Proceedings of the 5th Symposium on Trustworthy Global Computing.

Digital Library

[18]

G. Charness and M. Rabin. 2002. Understanding social preferences with simple tests. Quart. J. Econ. 117.

[19]

P.-A. Chen, M. David, and D. Kempe. 2010. Better vaccination strategies for better people. In Proceedings of the 11th ACM Conference on Electronic Commerce.

Digital Library

[20]

P.-A. Chen, B. de Keijzer, D. Kempe, and G. Schäfer. 2011. The robust price of anarchy of altruistic games. In Proceedings of the 7th Workshop on Internet & Network Economics.

Digital Library

[21]

P.-A. Chen and D. Kempe. 2008. Altruism, selfishness, and spite in traffic routing. In Proceedings of the 9th ACM Conference on Electronic Commerce.

Digital Library

[22]

X. Chen and X. Deng. 2006. Settling the complexity of two-player Nash-equilibrium. In Proceedings of the 47rd Symposium on Foundations of Computer Science.

Digital Library

[23]

G. Christodoulou and E. Koutsoupias. 2005. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing.

Digital Library

[24]

R. Cole, Y. Dodis, and T. Roughgarden. 2003. Pricing network edges for heterogeneous selfish users. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing.

Digital Library

[25]

R. Cole, Y. Dodis, and T. Roughgarden. 2006. How much can taxes help selfish routing&quest; J. Comput. System Sci. 72.

Digital Library

[26]

S. Dafermos. 1972. The traffic assignment problem for multiclass-user transportation networks. Transport. Sci. 6.

[27]

J. Elias, F. Martignon, K. Avrachenkov, and G. Neglia. 2010. Socially-aware network design games. In Proceedings of the INFOCOM'10.

Digital Library

[28]

E. Fehr and K. M. Schmidt. 2005. The economics of fairness, reciprocity and altruism — Experimental evidence and new theories. Tech. Rep. Discussion Paper No. 2005-20, Department of Economics, Universität München.

[29]

A. Fiat, A. Karlin, E. Koutsoupias, and A. Vidali. 2013. Approaching utopia: Strong truthfulness and externality-resistant mechanisms. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science.

Digital Library

[30]

J. Geanakoplos, D. Pearce, and E. Stacchetti. 1989. Psychological games and sequential rationality. Games Econ. Behav. 1, 1.

[31]

H. Gintis, S. Bowles, R. Boyd, and E. Fehr. 2005. Moral Sentiments and Material Interests: The Foundations of Cooperation in Economic Life. MIT Press.

[32]

W. D. Hamilton. 1963. The evolution of altruistic behavior. Amer. Natural. 97.

[33]

W. D. Hamilton. 1964. The genetical evolution of social behavior, I&II. J. Theoret. Biol. 7.

[34]

J. Hannan. 1957. Approximation to Bayes risk in repeated plays. Contrib. Theory Games 3.

[35]

A. Hayrapetyan, E. Tardos, and T. Wexler. 2006. The effect of collusion in congestion games. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing.

Digital Library

[36]

M. Hoefer and A. Skopalik. 2009a. Altruism in atomic congestion games. In Proceedings of the 17th European Symposium on Algorithms.

[37]

M. Hoefer and A. Skopalik. 2009b. Stability and convergence in selfish scheduling with altruistic agents. In Proceedings of the 5th International Workshop on Internet and Network Economics.

Digital Library

[38]

P. Hui, K. Xu, V. O. K. Li, J. Crowcroft, V. Latora, and P. Lio. 2009a. Impact of altruism on opportunistic communications. In Proceedings of the 1st International Conference on Ubiquitous and Future Networks.

Digital Library

[39]

P. Hui, K. Xu, V. O. K. Li, J. Crowcroft, V. Latora, and P. Lio. 2009b. Selfishness, altruism and message spreading in mobile social networks. In Proceedings of the INFOCOM'09 Workshop.

Digital Library

[40]

G. Karakostas and A. Viglas. 2007. Equilibria for networks with malicious users. Math. Program. 110.

Digital Library

[41]

E. Koutsoupias and C. Papadimitriou. 1999. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science.

Digital Library

[42]

J. Ledyard. 1997. Public goods: A survey of experimental resesarch. In Handbook of Experimental Economics, J. Kagel and A. Roth (Eds.), Princeton University Press.

[43]

D. K. Levine. 1998. Modeling altruism and spitefulness in experiments. Rev. Econ. Dynam. 1, 3 (July 1998).

[44]

T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. 2008. A new model for selfish routing. Theoret. Comput. Sci. 406 (October 2008). Issue 3.

Digital Library

[45]

A. Mas-Colell. 1984. On a theorem of Schmeidler. J. Math. Econ. 13.

[46]

D. Meier, Y. A. Oswald, S. Schmid, and R. Wattenhofer. 2008. On the windfall of friendship: Inoculation strategies on social networks. In Proceedings of the 10th ACM Conference on Electronic Commerce.

Digital Library

[47]

I. Milchtaich. 1996. Congestion games with player-specific payoff functions. Games Econ. Behav. 13, 1.

[48]

I. Milchtaich. 2012. Comparative statics of altruism and spite. Games Econ. Behav. 75, 2.

[49]

T. Moscibroda, S. Schmid, and R. Wattenhofer. 2006. When selfish meets evil: Byzantine players in a virus inoculation game. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing.

Digital Library

[50]

U. Nadav and T. Roughgarden. 2010. The limits of smoothness: A primal-dual framework for price of anarchy bounds. In Proceedings of the 6th Workshop on Internet and Network Economics.

Digital Library

[51]

N. Nisan, T. Roughgarden, É. Tardos, and V. V. Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press.

Digital Library

[52]

A. Pigou. 1920. The Economics of Welfare. Macmillan.

[53]

M. Rabin. 1993. Incorporating fairness into game theory and economics. Amer. Econ. Rev. 83, 5 (December 1993).

[54]

M. Rahn and G. Schäfer. 2013. Bounding the inefficiency of altruism through social contribution games. In Proceedings of the 9th Conference on Web and Internet Economics.

[55]

R. W. Rosenthal. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2.

[56]

A. Roth. 2008. The price of malice in linear congestion games. In Proceedings of the 4th Workshop on Internet and Network Economics.

Digital Library

[57]

T. Roughgarden. 2004. Stackelberg scheduling strategies. SIAM J. Comput. 33.

Digital Library

[58]

T. Roughgarden. 2005. Selfish Routing and the Price of Anarchy. MIT Press.

Digital Library

[59]

T. Roughgarden. 2009. Intrinsic robustness of the price of anarchy. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing.

Digital Library

[60]

T. Roughgarden and F. Schoppmann. 2011. Local smoothness and the price of anarchy in atomic splittable congestion games. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms.

Digital Library

[61]

T. Roughgarden and E. Tardos. 2000. How bad is selfish routing&quest; In Proceedings of the 41st Symposium on Foundations of Computer Science.

Digital Library

[62]

M. Smith. 1979. The marginal cost taxation of a transportation network. Transport. Res. Part B, 13.

[63]

C. Swamy. 2007. The effectiveness of stackelberg strategies and tolls for network congestion games. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms.

Digital Library

[64]

A. Vetta. 2002. Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In Proceedings of the 43rd Symposium on Foundations of Computer Science.

Digital Library

[65]

S. A. West, C. El Mouden, and A. Gardner. 2011. Sixteen common misconceptions about the evolution of cooperation in humans. Evolut. Hum. Behav. 32, 4.

[66]

H. P. Young. 1995. Strategic Learning and its Limits. Oxford University Press.

Cited By

Takazawa K(2025)Pure Nash equilibria in weighted matroid congestion games with non-additive aggregation and beyondDiscrete Applied Mathematics10.1016/j.dam.2024.10.017361(226-235)Online publication date: Jan-2025
https://doi.org/10.1016/j.dam.2024.10.017
Hill CBrown PPaarporn K(2024)Conditions for Altruistic Perversity in Two-Strategy Population Games2024 American Control Conference (ACC)10.23919/ACC60939.2024.10644683(3915-3920)Online publication date: 10-Jul-2024
https://doi.org/10.23919/ACC60939.2024.10644683
Pulyassary HWu M(2024)Digital Transformation in Transportation Systems: Strategic User Behavior and System EfficiencyTutorials in Operations Research: Smarter Decisions for a Better World10.1287/educ.2024.0280(244-274)Online publication date: 17-Oct-2024
https://doi.org/10.1287/educ.2024.0280
Show More Cited By

Index Terms

Altruism and Its Impact on the Price of Anarchy
1. Theory of computation

Recommendations

Altruism in Atomic Congestion Games

This article studies the effects of altruism, a phenomenon widely observed in practice, in the model of atomic congestion games. Altruistic behavior is modeled by a linear trade-off between selfish and social objectives. Our model can be embedded in the ...
Altruism, selfishness, and spite in traffic routing
EC '08: Proceedings of the 9th ACM conference on Electronic commerce

In this paper, we study the price of anarchy of traffic routing, under the assumption that users are partially altruistic or spiteful. We model such behavior by positing that the "cost" perceived by a user is a linear combination of the actual latency ...
The price of anarchy of finite congestion games
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

We consider the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. For asymmetric games, the price of anarchy of maximum social cost is Θ(√N), where N is the number of players. For all other cases of symmetric or ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 2, Issue 4

October 2014

162 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/2684807

Editors:
Vincent Conitzer
Duke University
,
Preston McAfee
Microsoft

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2014

Accepted: 01 May 2014

Revised: 01 March 2014

Received: 01 August 2013

Published in TEAC Volume 2, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
442
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)5

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Takazawa K(2025)Pure Nash equilibria in weighted matroid congestion games with non-additive aggregation and beyondDiscrete Applied Mathematics10.1016/j.dam.2024.10.017361(226-235)Online publication date: Jan-2025
https://doi.org/10.1016/j.dam.2024.10.017
Hill CBrown PPaarporn K(2024)Conditions for Altruistic Perversity in Two-Strategy Population Games2024 American Control Conference (ACC)10.23919/ACC60939.2024.10644683(3915-3920)Online publication date: 10-Jul-2024
https://doi.org/10.23919/ACC60939.2024.10644683
Pulyassary HWu M(2024)Digital Transformation in Transportation Systems: Strategic User Behavior and System EfficiencyTutorials in Operations Research: Smarter Decisions for a Better World10.1287/educ.2024.0280(244-274)Online publication date: 17-Oct-2024
https://doi.org/10.1287/educ.2024.0280
Chandan RPaccagnan DMarden J(2024)Methodologies for Quantifying and Optimizing the Price of AnarchyIEEE Transactions on Automatic Control10.1109/TAC.2024.340178769:11(7742-7757)Online publication date: Nov-2024
https://doi.org/10.1109/TAC.2024.3401787
Ferguson BPaccagnan DPradelski BMarden J(2024)Bridging the Gap Between Central and Local Decision-Making: The Efficacy of Collaborative Equilibria in Altruistic Congestion Games2024 IEEE 63rd Conference on Decision and Control (CDC)10.1109/CDC56724.2024.10886104(5373-5378)Online publication date: 16-Dec-2024
https://doi.org/10.1109/CDC56724.2024.10886104
Hill CBrown P(2024)Altruism Improves Congestion in Series-Parallel Nonatomic Congestion Games2024 IEEE 63rd Conference on Decision and Control (CDC)10.1109/CDC56724.2024.10885983(3973-3978)Online publication date: 16-Dec-2024
https://doi.org/10.1109/CDC56724.2024.10885983
Murray TGarg JNagi R(2024)Limited trust in social network gamesPhysical Review E10.1103/PhysRevE.110.054311110:5Online publication date: 25-Nov-2024
https://doi.org/10.1103/PhysRevE.110.054311
Cominetti RScarsini MSchröder MStier-Moses N(2023)Approximation and Convergence of Large Atomic Congestion GamesMathematics of Operations Research10.1287/moor.2022.128148:2(784-811)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/moor.2022.1281
Ferguson BBrown PMarden J(2023)Value of Information in Incentive Design: A Case Study in Simple Congestion NetworksIEEE Transactions on Computational Social Systems10.1109/TCSS.2023.330587210:6(3077-3088)Online publication date: Dec-2023
https://doi.org/10.1109/TCSS.2023.3305872
Seaton JBrown P(2023)On the Intrinsic Fragility of the Price of AnarchyIEEE Control Systems Letters10.1109/LCSYS.2023.33353157(3573-3578)Online publication date: 2023
https://doi.org/10.1109/LCSYS.2023.3335315
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents