Abstract
We consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering malicious behavior. While selfish users follow a strategy that minimizes their individual cost, a malicious user will use his flow through the network in an effort to cause the maximum possible damage to the overall cost. We define a generalized model, present characterizations of flows at equilibrium and prove bounds for the ratio of the social cost of a flow at equilibrium over the cost when centralized coordination among users is allowed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aashtiani H.Z., Magnanti T.L.(1981). Equilibria on a congested transportation network. SIAM J. Algebraic Discrete Methods 2(3): 213–226
Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press (1956)
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. In: Proceedings of the 13th Annual ACM–SIAM Symposium On Discrete Mathematics, pp. 413–420 (2002)
Dafermos S., Sparrow F.(1969). The traffic assignment problem for a general network. J. Res. Nat. Bureau Standards 73B: 91–118
Haurie A., Marcotte P.(1985). On the relationship between Nash–Cournot and Wardrop equilibria. Networks 15, 295–308
Karakostas, G., Viglas, A.: Equilibria for networks with malicious users. In: Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC), pp. 696–704 (2003)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, LNCS 1563, pp. 404–413 (1999)
Mavronicolas, M., Spirakis, P.: The price of selfish routing. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 510–519 (2001)
Pigou A.(1920). The economics of Welfare. Macmillan, London
Rockafellar R.T.(1970). Convex Analysis. Princeton University Press, New Jersey
Roughgarden, T.: Designing networks for selfish users is hard. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 472–481 (2001)
Roughgarden, T.: Stackelberg scheduling strategies. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 104–113(2001)
Roughgarden T.(2003). The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67(2): 341–364
Roughgarden T., Tardos É.(2002). How bad is selfish routing?. J. ACM 49(2): 236–259
Schulz, A.S., Stier Moses, N.E.: On the performance of user equilibria in traffic networks. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 86–87 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of this work appeared in the Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC) 2003.
G. Karakostas’ research was supported by an NSERC Discovery research grant and MITACS.
Part of this research was done when Viglas was a postdoctoral fellow at the University of Toronto, Canada.
Rights and permissions
About this article
Cite this article
Karakostas, G., Viglas, A. Equilibria for networks with malicious users. Math. Program. 110, 591–613 (2007). https://doi.org/10.1007/s10107-006-0015-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0015-2