Altruism, selfishness, and spite in traffic routing

ABSTRACT

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 of the route chosen (selfish component), and the increase in latency the user causes for others (altruistic component). We show that if all users have a coefficient of at least β > 0 for the altruistic component, then the price of anarchy is bounded by 1/β, for all network topologies, arbitrary commodities, and arbitrary semi-convex latency functions. We extend this result to give more precise bounds on the price of anarchy for specific classes of latency functions, even for β < 0 modeling spiteful behavior. In particular, we show that if all latency functions are linear, the price of anarchy is bounded by 4/(3+2β--β²).

We next study non-uniform altruism distributions, where different users may have different coefficients β. We prove that all such games, even with infinitely many types of players, have a Nash Equilibrium. We show that if the average of the coefficients for the altruistic components of all users is β, then the price of anarchy is bounded by 1/β, for single commodity parallel link networks, and arbitrary convex latency functions. In particular, this result generalizes, albeit non-constructively, the Stackelberg routing results of Roughgarden and of Swamy. More generally, we bound the price of anarchy based on the class of allowable latency functions, and as a corollary obtain tighter bounds for Stackelberg routing than a recent result of Swamy.

REFERENCES

• 1: Moshe Babaioff , Robert Kleinberg , Christos H. Papadimitriou, Congestion games with malicious players, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250926]
• 2: M. Beckmann, C. McGuire, and C. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
• 3: V. Bonifaci, T. Harks, and G. Schäfer. The impact of stackelberg routing in general networks. Technical Report COGA Preprint 020-2007, TU Berlin, 2007.
• 4: F. Brandt, T. Sandholm, and Y. Shoham. Spiteful bidding in sealed-bid auctions. In Proc. 20th Intl. Joint Conf. on Artificial Intelligence, pages 1207--1214, 2007.
• 5: Felix Brandt , Gerhard Weiß, Antisocial Agents and Vickrey Auctions, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.335-347, August 01-03, 2001
• 6: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 7: Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
• 8: Richard Cole , Yevgeniy Dodis , Tim Roughgarden, Pricing network edges for heterogeneous selfish users, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780618]
• 9: Richard Cole , Yevgeniy Dodis , Tim Roughgarden, How much can taxes help selfish routing?, Journal of Computer and System Sciences, v.72 n.3, p.444-467, May 2006 [doi>10.1016/j.jcss.2005.09.010]
• 10: R. Cominetti, J. Correa, and N. Stier-Moses. Network games with atomic players. In Proc. 33rd Intl. Colloq. on Automata, Languages and Programming, pages 525--536, 2006.
• 11: S. Dafermos. The traffic assignment problem for multiclass-user transportation networks. Transportation Science, 6:73--87, 1972.
• 12: E. Fehr and K. Schmidt. A theory of fairness, competition, and cooperation. The Quarterly Journal of Economics, 114:817--868, 1999.
• 13: Michal Feldman , Christos Papadimitriou , John Chuang , Ion Stoica, Free-riding and whitewashing in peer-to-peer systems, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016527.1016539]
• 14: Lisa Fleischer, Linear tolls suffice: new bounds and algorithms for tolls in single source networks, Theoretical Computer Science, v.348 n.2, p.217-225, 8 December 2005 [doi>10.1016/j.tcs.2005.09.014]
• 15: Lisa Fleischer , Kamal Jain , Mohammad Mahdian, Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.277-285, October 17-19, 2004 [doi>10.1109/FOCS.2004.69]
• 16: Nandan Garg , Daniel Grosu , Vipin Chaudhary, An Antisocial Strategy for Scheduling Mechanisms, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 8, p.203.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.86]
• 17: H. Gintis, S. Bowles, R. Boyd, and E. Fehr. Moral Sentiments and Material Interests : The Foundations of Cooperation in Economic Life. MIT Press, 2005.
• 18: Ara Hayrapetyan , Éva Tardos , Tom Wexler, The effect of collusion in congestion games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132529]
• 19: Olaf Jahn , Rolf H. Möhring , Andreas S. Schulz , Nicolás E. Stier-Moses, System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion, Operations Research, v.53 n.4, p.600-616, July-August 2005 [doi>10.1287/opre.1040.0197]
• 20: A.C. Kaporis , P.G. Spirakis, The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148113]
• 21: George Karakostas , Stavros G. Kolliopoulos, Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.268-276, October 17-19, 2004 [doi>10.1109/FOCS.2004.26]
• 22: G. Karakostas and S. Kolliopoulos. Stackelberg strategies for selfish routing in general multicommodity networks. Technical Report 2006/08, McMaster University, 2006.
• 23: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proc. 17th Annual Symp. on Theoretical Aspects of Computer Science. Springer, 1999.
• 24: J. Ledyard. Public goods: A survey of experimental resesarch. In J. Kagel and A. Roth, editors, Handbook of Experimental Economics, pages 111--194. Princeton University Press, 1997.
• 25: D. Levine. Modeling altruism and spitefulness in experiments. Review of Economic Dynamics, 1:593--622, 1998.
• 26: L. Liang and Q. Qi. Cooperative or vindictive: Bidding strategies in sponsored search auctions. In Proc. 3rd Workshop on Internet and Network Economics (WINE), pages 167--178, 2007.
• 27: H. Lin, T. Roughgarden, E. Tardos, and A. Walkover. Braess's paradox, fibonacci numbers, and exponential inapproximability. In Proc. 32nd Intl. Colloq. on Automata, Languages and Programming, pages 497--512, 2005.
• 28: A. Mas-Colell. On a theorem of Schmeidler. J. of Mathematical Economics, 13:201--206, 1984.
• 29: A. Pigou. The Economics of Welfare. Macmillan, 1920.
• 30: Tim Roughgarden, The price of anarchy is independent of the network topology, Journal of Computer and System Sciences, v.67 n.2, p.341-364, September 2003 [doi>10.1016/S0022-0000(03)00044-8]
• 31: Tim Roughgarden, The maximum latency of selfish routing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 32: Tim Roughgarden, Stackelberg Scheduling Strategies, SIAM Journal on Computing, v.33 n.2, p.332-350, 2004 [doi>10.1137/S0097539701397059]
• 33: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 34: Tim Roughgarden, Selfish routing with atomic players, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 35: Tim Roughgarden, On the severity of Braess's paradox: designing networks for selfish users is hard, Journal of Computer and System Sciences, v.72 n.5, p.922-953, August 2006 [doi>10.1016/j.jcss.2005.05.009]
• 36: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 37: T. Schelling. Micromotives and Macrobehavior. Norton, 1978.
• 38: Yogeshwer Sharma , David P. Williamson, Stackelberg thresholds in network routing games or the value of altruism, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250925]
• 39: M. Smith. The marginal cost taxation of a transportation network. Transportation Resesarch, Part B, 13:237--242, 1979.
• 40: Chaitanya Swamy, The effectiveness of Stackelberg strategies and tolls for network congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1133-1142, January 07-09, 2007, New Orleans, Louisiana
• 41: Ioannis A. Vetsikas , Nicholas R. Jennings, Outperforming the competition in multi-unit sealed bid auctions, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329252]
• 42: J. Wardrop. Some theoretical aspects of road traffic research. In Proc. of the Institute of Civil Engineers, Pt. II, volume 1, pages 325--378, 1952.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Economics, Theory

Keywords:
altruism, anarchy, routing, selfishness, spite