Congestion games with malicious players

ABSTRACT

We study the equilibria of non-atomic congestion games in which there are two types of players: rational players, who seek to minimize their own delay, and malicious players, who seek to maximize the average delay experienced by the rational players. We study the existence of pure and mixed Nash equilibria for these games, and we seek to quantify the impact of the malicious players on the equilibrium. One counter intuitive phenomenon which we demonstrate is the "windfall of malice": paradoxically, when a myopically malicious player gains control of a fraction of the flow, a fraction of the players change from rational to malicious, the new equilibrium may be more favorable for the remaining rational players than the previous equilibrium.

REFERENCES

• 1: Patrick Billingsley. Convergence of Probability Measures. John Wiley, 1999.
• 2: Felix Brandt, Tuomas Sandholm, and Yoav Shoham. Spiteful bidding in sealed-bid auctions. In Proceedingsof the 20th International Joint Conference on Artificial Intelligence (IJCAI), 2007.
• 3: Kfir Eliaz. Fault tolerant implementation. Review of Economic Studies, 69(3):589--610, July 2002.
• 4: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 5: I. L. Glicksberg. A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proc. American Math. Soc.,3(1):170--174, 1952.
• 6: George Karakostas and Anastasios Viglas. Equilibria for networks with malicious users. In Toshihide Ibaraki, Naoki Katoh, and Hirotaka Ono, editors, ISAAC, volume 2906 of Lecture Notes in Computer Science, pages 696--704. Springer, 2003.
• 7: John Morgan, Ken Steiglitz, and George Reis. The spite motive and equilibrium behavior in auctions. Contributions to Economic Analysis & Policy, 2(1):1102--1102, 2003.
• 8: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, When selfish meets evil: byzantine players in a virus inoculation game, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146391]
• 9: Martin J. Osborne and Ariel Rubinstein. A course in game theory. MIT Press, 1994.
• 10: Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, v.48 n.3, p.498-532, June 1994 [doi>10.1016/S0022-0000(05)80063-7]
• 11: R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 12: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 13: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Economics, Theory

Keywords:
congestion games, equilibrium, malicious behavior, selfish routing