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.
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. J. Aumann. 1974. Subjectivity and correlation in randomized strategies. J. Math. Econ. 1, 1.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- M. Babaioff, R. Kleinberg, and C. H. Papadimitriou. 2009. Congestion games with malicious players. Games Econ. Behav. 67, 1.Google ScholarCross Ref
- T. Bergstrom. 1999. Systems of benevolent utility functions. J. Public Econ. Theory 1, 1.Google ScholarCross Ref
- 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.) Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- G. Charness and M. Rabin. 2002. Understanding social preferences with simple tests. Quart. J. Econ. 117.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- P.-A. Chen and D. Kempe. 2008. Altruism, selfishness, and spite in traffic routing. In Proceedings of the 9th ACM Conference on Electronic Commerce. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. Cole, Y. Dodis, and T. Roughgarden. 2006. How much can taxes help selfish routing? J. Comput. System Sci. 72. Google ScholarDigital Library
- S. Dafermos. 1972. The traffic assignment problem for multiclass-user transportation networks. Transport. Sci. 6.Google Scholar
- J. Elias, F. Martignon, K. Avrachenkov, and G. Neglia. 2010. Socially-aware network design games. In Proceedings of the INFOCOM'10. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- J. Geanakoplos, D. Pearce, and E. Stacchetti. 1989. Psychological games and sequential rationality. Games Econ. Behav. 1, 1.Google ScholarCross Ref
- H. Gintis, S. Bowles, R. Boyd, and E. Fehr. 2005. Moral Sentiments and Material Interests: The Foundations of Cooperation in Economic Life. MIT Press.Google Scholar
- W. D. Hamilton. 1963. The evolution of altruistic behavior. Amer. Natural. 97.Google Scholar
- W. D. Hamilton. 1964. The genetical evolution of social behavior, I&II. J. Theoret. Biol. 7.Google Scholar
- J. Hannan. 1957. Approximation to Bayes risk in repeated plays. Contrib. Theory Games 3.Google Scholar
- 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. Google ScholarDigital Library
- M. Hoefer and A. Skopalik. 2009a. Altruism in atomic congestion games. In Proceedings of the 17th European Symposium on Algorithms.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- G. Karakostas and A. Viglas. 2007. Equilibria for networks with malicious users. Math. Program. 110. Google ScholarDigital Library
- E. Koutsoupias and C. Papadimitriou. 1999. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science. Google ScholarDigital Library
- J. Ledyard. 1997. Public goods: A survey of experimental resesarch. In Handbook of Experimental Economics, J. Kagel and A. Roth (Eds.), Princeton University Press.Google Scholar
- D. K. Levine. 1998. Modeling altruism and spitefulness in experiments. Rev. Econ. Dynam. 1, 3 (July 1998).Google ScholarCross Ref
- 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. Google ScholarDigital Library
- A. Mas-Colell. 1984. On a theorem of Schmeidler. J. Math. Econ. 13.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- I. Milchtaich. 1996. Congestion games with player-specific payoff functions. Games Econ. Behav. 13, 1.Google ScholarCross Ref
- I. Milchtaich. 2012. Comparative statics of altruism and spite. Games Econ. Behav. 75, 2.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- N. Nisan, T. Roughgarden, É. Tardos, and V. V. Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press. Google ScholarDigital Library
- A. Pigou. 1920. The Economics of Welfare. Macmillan.Google Scholar
- M. Rabin. 1993. Incorporating fairness into game theory and economics. Amer. Econ. Rev. 83, 5 (December 1993).Google Scholar
- 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.Google Scholar
- R. W. Rosenthal. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2.Google Scholar
- A. Roth. 2008. The price of malice in linear congestion games. In Proceedings of the 4th Workshop on Internet and Network Economics. Google ScholarDigital Library
- T. Roughgarden. 2004. Stackelberg scheduling strategies. SIAM J. Comput. 33. Google ScholarDigital Library
- T. Roughgarden. 2005. Selfish Routing and the Price of Anarchy. MIT Press. Google ScholarDigital Library
- T. Roughgarden. 2009. Intrinsic robustness of the price of anarchy. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- T. Roughgarden and E. Tardos. 2000. How bad is selfish routing? In Proceedings of the 41st Symposium on Foundations of Computer Science. Google ScholarDigital Library
- M. Smith. 1979. The marginal cost taxation of a transportation network. Transport. Res. Part B, 13.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- H. P. Young. 1995. Strategic Learning and its Limits. Oxford University Press.Google Scholar
Index Terms
- Altruism and Its Impact on the Price of Anarchy
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 commerceIn 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 computingWe 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