Martin Hoefer
Abstract
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 framework of congestion games with player-specific latency functions. Stable states are the pure Nash equilibria of these games, and we examine their existence and the convergence of sequential best-response dynamics. In general, pure Nash equilibria are often absent, and existence is NP-hard to decide. Perhaps surprisingly, if all delay functions are affine, the games remain potential games, even when agents are arbitrarily altruistic. The construction underlying this result can be extended to a class of general potential games and social cost functions, and we study a number of prominent examples. These results give important insights into the robustness of multi-agent systems with heterogeneous altruistic incentives. Furthermore, they yield a general technique to prove that stabilization is robust, even with partly altruistic agents, which is of independent interest.
In addition to these results for uncoordinated dynamics, we consider a scenario with a central altruistic institution that can set incentives for the agents. 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. These results are closely related to Stackelberg routing and answer open questions raised recently in the literature.
- Ackermann, H., Röglin, H., and Vöcking, B. 2008. On the impact of combinatorial structure on congestion games. J. ACM 55, 6. Google Scholar
Digital Library
- Ackermann, H., Röglin, H., and Vöcking, B. 2009. Pure Nash equilibria in player-specific and weighted congestion games. Theoret. Comput. Sci. 410, 17, 1552--1563. Google ScholarDigital Library
- Babaioff, M., Kleinberg, R., and Papadimitriou, C. 2009. Congestion games with malicious players. Games Econom. Behav. 67, 1, 22--35.Google ScholarCross Ref
- Berenbrink, P., Goldberg, L. A., Goldberg, P., and Martin, R. 2006. Utilitarian resource assignment. J. Disc. Algorithms 4, 4, 567--587. Google ScholarDigital Library
- Bruno, J., Coffman Jr., E., and Sethi, R. 1974. Scheduling independent tasks to reduce mean finishing time. Comm. ACM 17, 7, 382--387. Google ScholarDigital Library
- Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., and Papaioannou, E. 2010. The impact of altruism on the efficiency of atomic congestion games. In Proceedings of the 5th Symposium on Trustworthy Global Computing (TGC). 172--188. Google ScholarDigital Library
- Chen, P.-A. and Kempe, D. 2008. Altruism, selfishness, and spite in traffic routing. In Proceedings of the 9th Conference on Electronic Commerce (EC). 140--149. Google ScholarDigital Library
- Chen, P.-A., Keijzer, B. D., Kempe, D., and Schaefer, G. 2011. On the robust price of anarchy of altruistic games. In Proceedings of the 7th International Workshop on Internet and Network Economics (WINE). 383--390. Google ScholarDigital Library
- Christodoulou, G., Koutsoupias, E., and Nanavati, A. 2009. Coordination mechanisms. Theoret. Comput. Sci. 410, 36, 3327--3336. Google ScholarDigital Library
- Cohen, J., Dürr, C., and Kim, T. N. 2011. Non-clairvoyant scheduling games. Theory Comput. Syst. 49, 1, 3--23. Google ScholarDigital Library
- Cook, W. and Rohe, A. 1999. Computing minimum-weight perfect matchings. INFORMS J. Comput. 11, 2, 138--148. Google ScholarDigital Library
- Eshel, I., Samuelson, L., and Shaked, A. 1998. Altruists, egoists and hooligans in a local interaction model. Amer. Econ. Rev. 88, 1, 157--179.Google Scholar
- Fabrikant, A., Papadimitriou, C., and Talwar, K. 2004. The complexity of pure Nash equilibria. In Proceedings of the 36th Symposium on Theory of Computing (STOC). 604--612. Google ScholarDigital Library
- Fehr, E. and Schmidt, K. 1999. A theory of fairness, competition, and cooperation. Quart. J. Econ. 114, 817--868.Google ScholarCross Ref
- Feldmann, R., Gairing, M., Lücking, T., Monien, B., and Rode, M. 2003. Nashification and the coordination ratio for a selfish routing game. In Proceedings of the 30th International Colloqium on Automata, Languages and Programming (ICALP). 514--526. Google ScholarDigital Library
- Fotakis, D. 2010. Stackelberg strategies for atomic congestion games. Theory Comput. Syst. 47, 1, 218--249. Google ScholarDigital Library
- Fotakis, D., Kontogiannis, S., and Spirakis, P. 2005. Selfish unsplittable flows. Theoret. Comput. Sci. 348, 2--3, 226--239. Google ScholarDigital Library
- Gairing, M. 2008. Malicious Bayesian congestion games. In Proceedings of the 6th International Workshop on Approximation and Online Algorithms (WAOA). 119--132.Google Scholar
- Gairing, M., Lücking, T., Mavronicolas, M., and Monien, B. 2010. Computing Nash equilibria for scheduling on restricted parallel links. Theory Comput. Syst. 47, 2, 405--432. Google ScholarDigital Library
- Gairing, M., Monien, B., and Tiemann, K. 2011. Routing (un-)splittable flow in games with player-specific linear latency functions. ACM Trans. Algorithms 7, 3, 31. Google ScholarDigital Library
- Gintis, H., Bowles, S., Boyd, R., and Fehr, E. 2005. Moral Sentiments and Material Interests: The Foundations of Cooperation in Economic Life. MIT Press.Google Scholar
- Hoefer, M. and Skopalik, A. 2009a. Altruism in atomic congestion games. In Proceedings of the 17th European Symposium on Algorithms (ESA). 179--189.Google Scholar
- Hoefer, M. and Skopalik, A. 2009b. Stability and convergence in selfish scheduling with altruistic agents. In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE). 616--622. Google ScholarDigital Library
- Hoefer, M. and Souza, A. 2010. Tradeoffs and average-case equilibria in selfish routing. ACM Trans. Comp. Theory 2, 1. Google ScholarDigital Library
- Hoefer, M. and Suri, S. 2012. Dynamics in network interaction games. Distrib. Comput. 25, 5, 359--370.Google ScholarCross Ref
- Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., and Sun, Q. 2005. Fast and compact: A simple class of congestion games. In Proceedings of the 20th Conference on Artificial Intelligence (AAAI). 489--494. Google ScholarDigital Library
- Immorlica, N., Li, L., Mirrokni, V., and Schulz, A. 2009. Coordination mechanisms for selfish scheduling. Theoret. Comput. Sci. 410, 17, 1589--1598. Google ScholarDigital Library
- Kaporis, A. and Spirakis, P. 2008. Stackelberg games: The price of optimum. In Encyclopedia of Algorithms. Springer Verlag, Berlin.Google Scholar
- Kaporis, A. and Spirakis, P. 2009. The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions. Theoret. Comput. Sci. 410, 8--10, 745--755. Google ScholarDigital Library
- Karakostas, G. and Viglas, A. 2007. Equilibria for networks with malicious users. Math. Prog. 110, 3, 591--613. Google ScholarDigital Library
- Kleinberg, J. 2007. Cascading behavior in netwoks: Algorithmic and economic issues. In Algorithmic Game Theory. Cambridge University Press, Chapter 24.Google Scholar
- Korilis, Y., Lazar, A., and Orda, A. 1997. Achieving network optima using Stackelberg routing strategies. IEEE/ACM Trans. Netw. 5, 1, 161--173. Google ScholarDigital Library
- Koutsoupias, E. and Papadimitriou, C. 2009. Worst-case equilibria. Comput. Sci. Rev. 3, 2, 65--69. Google ScholarDigital Library
- Ledyard, J. 1997. Public goods: A survey of experimental resesarch. In Handbook of Experimental Economics, J. Kagel and A. Roth Eds., Princeton University Press, 111--194.Google Scholar
- Levine, D. 1998. Modeling altruism and spitefulness in experiments. Rev. Econom. Dynamics 1, 593--622.Google ScholarCross Ref
- Milchtaich, I. 1996. Congestion games with player-specific payoff functions. Games Econom. Behav. 13, 1, 111--124.Google ScholarCross Ref
- Morris, S. 2000. Contagion. Rev. Econ. Stud. 67, 1, 57--78.Google ScholarCross Ref
- Moscibroda, T., Schmid, S., and Wattenhofer, R. 2009. The price of malice: A game-theoretic framework for malicious behavior in distributed systems. Internet Math. 6, 2, 125--155.Google ScholarCross Ref
- Nisan, N., Tardos, É., Roughgarden, T., and Vazirani, V., Eds. 2007. Algorithmic Game Theory. Cambridge University Press. Google ScholarDigital Library
- Rosenthal, R. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.Google ScholarDigital Library
- Roughgarden, T. 2004. Stackelberg scheduling strategies. SIAM J. Comput. 33, 2, 332--350. Google ScholarDigital Library
- Sharma, Y. and Williamson, D. 2009. Stackelberg thresholds in network routing games or the value of altruism. Games Econom. Behav. 67, 1, 174--190.Google ScholarCross Ref
- Tovey, C. 1984. A simplified NP-complete satisfiability problem. Disc. Appl. Math. 8, 85--89.Google ScholarCross Ref
Index Terms
- Altruism in Atomic Congestion Games
Recommendations
Altruism and Its Impact on the Price of Anarchy
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 ...
Conflicting Congestion Effects in Resource Allocation Games
We study strategic resource allocation settings, where jobs correspond to self-interested players who choose resources with the objective of minimizing their individual cost. Our framework departs from the existing game-theoretic models mainly in ...
Computing approximate pure Nash equilibria in congestion games
Among other solution concepts, the notion of the pure Nash equilibrium plays a central role in Game Theory. Pure Nash equilibria in a game characterize situations with non-cooperative deterministic players in which no player has any incentive to ...
Comments