Abstract
We study the price of malice in linear congestion games using the technique of no-regret analysis in the presence of Byzantine players. Our assumptions about the behavior both of rational players, and of malicious players are strictly weaker than have been previously used to study the price of malice. Rather than assuming that rational players route their flow according to a Nash equilibrium, we assume only that they play so as to have no regret. Rather than assuming that malicious players myopically seek to maximize the social cost of the game, we study Byzantine players about whom we make no assumptions, who may be seeking to optimize any utility function, and who may engage in an arbitrary degree of counter-speculation. Because our assumptions are strictly weaker than in previous work, the bounds we prove on two measures of the price of malice hold also for the quantities studied by Babaioff et al. [2] and Moscibroda et al. [15] We prove tight bounds both for the special case of parallel link routing games, and for general congestion games.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Awerbuch, B., Kleinberg, R.: Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC) (2004)
Babaioff, M., Kleinberg, R., Papadimitriou, C.H.: Congestion games with malicious players. In: EC 2007: Proceedings of the 8th ACM conference on Electronic commerce, pp. 103–112. ACM, New York (2007)
Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
Blum, A., Even-Dar, E., Ligett, K.: Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games. In: PODC 2006: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pp. 45–52. ACM, New York (2006)
Blum, A., Hajiaghayi, M., Ligett, K., Roth, A.: Regret minimization and the price of total anarchy. In: STOC 2008: Proceedings of the fortieth annual ACM symposium on Theory of computing (2008)
Brandt, F., Sandholm, T., Shoham, Y.: Spiteful bidding in sealed-bid auctions. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) (2007)
Chung, C., Ligett, K., Pruhs, K., Roth, A.: The price of stochastic anarchy. In: Monien, B., Schroeder, U.-P. (eds.) SAGT 2008. LNCS, vol. 4997, pp. 303–314. Springer, Heidelberg (2008)
Kalai, A., Vempala, S.: Efficient algorithms for on-line optimization. In: Proceedings of the The 16th Annual Conference on Learning Theory, pp. 26–40 (2003)
Karakostas, G., Viglas, A.: Equilibria for networks with malicious users. Math. Program. 110(3), 591–613 (2007)
Kleinberg, R.: Anytime algorithms for multi-armed bandit problems. In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 928–936. ACM Press, New York (2006)
Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Proceedings of 16th STACS, pp. 404–413 (1999)
Littlestone, N., Warmuth, M.K.: The weighted majority algorithm. Inf. Comput. 108(2), 212–261 (1994)
McMahan, B., Blum, A.: Online geometric optimization in the bandit setting against an adaptive adversary. In: Shawe-Taylor, J., Singer, Y. (eds.) COLT 2004. LNCS, vol. 3120, pp. 109–123. Springer, Heidelberg (2004)
Morgan, J., Steiglitz, K., Reis, G.: The spite motive and equilibrium behavior in auctions. Contributions to Economic Analysis & Policy 2(1), 1102–1127 (2003)
Moscibroda, T., Schmid, S., Wattenhofer, R.: When selfish meets evil: byzantine players in a virus inoculation game. In: PODC 2006: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pp. 35–44. ACM, New York (2006)
Roughgarden, T., Tardos, É.: How bad is selfish routing? J. ACM 49(2), 236–259 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Roth, A. (2008). The Price of Malice in Linear Congestion Games. In: Papadimitriou, C., Zhang, S. (eds) Internet and Network Economics. WINE 2008. Lecture Notes in Computer Science, vol 5385. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92185-1_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-92185-1_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92184-4
Online ISBN: 978-3-540-92185-1
eBook Packages: Computer ScienceComputer Science (R0)