[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Malicious Bayesian Congestion Games

  • Conference paper
Approximation and Online Algorithms (WAOA 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5426))

Included in the following conference series:

  • 721 Accesses

Abstract

In this paper, we introduce malicious Bayesian congestion games as an extension to congestion games where players might act in a malicious way. In such a game each player has two types. Either the player is a rational player seeking to minimize her own delay, or – with a certain probability – the player is malicious in which case her only goal is to disturb the other players as much as possible.

We show that such games do in general not possess a Bayesian Nash equilibrium in pure strategies (i.e. a pure Bayesian Nash equilibrium). Moreover, given a game, we show that it is NP-complete to decide whether it admits a pure Bayesian Nash equilibrium. This result even holds when resource latency functions are linear, each player is malicious with the same probability, and all strategy sets consist of singleton sets of resources. For a slightly more restricted class of malicious Bayesian congestion games, we provide easy checkable properties that are necessary and sufficient for the existence of a pure Bayesian Nash equilibrium.

In the second part of the paper we study the impact of the malicious types on the overall performance of the system (i.e. the social cost). To measure this impact, we use the Price of Malice. We provide (tight) bounds on the Price of Malice for an interesting class of malicious Bayesian congestion games. Moreover, we show that for certain congestion games the advent of malicious types can also be beneficial to the system in the sense that the social cost of the worst case equilibrium decreases. We provide a tight bound on the maximum factor by which this happens.

This work was supported by a fellowship within the Postdoc-Programme of the German Academic Exchange Service (DAAD).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ackermann, H., Röglin, H., Vöcking, B.: On the Impact of Combinatorial Structure on Congestion Games. In: Proc. of the 47th Annual Symposium on Foundations of Computer Science (FOCS 2006), pp. 613–622 (2006)

    Google Scholar 

  2. Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 218–229. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  3. Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 57–66 (2005)

    Google Scholar 

  4. Babaioff, M., Kleinberg, R., Papadimitriou, C.H.: Congestion Games with Malicious Players. In: Proc. of the 8th ACM Conference on Electronic Commerce (EC 2007), pp. 103–112 (2007)

    Google Scholar 

  5. Christodoulou, G., Koutsoupias, E.: The Price of Anarchy of Finite Congestion Games. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 67–73 (2005)

    Google Scholar 

  6. Conitzer, V., Sandholm, T.: New Complexity Results about Nash Equilibria. In: Proc. of 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), pp. 765–771 (2003)

    Google Scholar 

  7. Dunkel, J., Schulz, A.S.: On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 62–73. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  8. Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The Complexity of Pure Nash Equilibria. In: Proc. of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 604–612 (2004)

    Google Scholar 

  9. Fotakis, D.A., Kontogiannis, S.C., Spirakis, P.G.: Symmetry in network congestion games: Pure equilibria and anarchy cost. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 161–175. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  10. Gairing, M., Monien, B., Tiemann, K.: Selfish Routing with Incomplete Information. Theory of Computing Systems 42(1), 91–130 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gairing, M., Schoppmann, F.: Total Latency in Singleton Congestion Games. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 381–387. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  12. Goemans, M.X., Mirrokni, V., Vetta, A.: Sink Equilibria and Convergence. In: Proc. of the 46th Annual Symposium on Foundations of Computer Science (FOCS 2005), pp. 142–154 (2005)

    Google Scholar 

  13. Gottlob, G., Greco, G., Mancini, T.: Complexity of Pure Equilibria in Bayesian Games. In: Proc. of 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 1294–1299 (2007)

    Google Scholar 

  14. Harsanyi, J.C.: Games with Incomplete Information Played by Bayesian Players, I, II, III. Management Science 14, 159–182, 320–332, 468–502 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  15. Karakostas, G., Viglas, A.: Equilibria for networks with malicious users. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 696–704. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  16. Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  17. Libman, L., Orda, A.: Atomic Resource Sharing in Noncooperative Networks. Telecommunication Systems 17(4), 385–409 (2001)

    Article  MATH  Google Scholar 

  18. Milchtaich, I.: Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior 13(1), 111–124 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  19. Moscibroda, T., Schmid, S., Wattenhofer, R.: When Selfish Meets Evil: Byzantine Players in a Virus Inoculation Game. In: Proc. of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC 2006), pp. 35–44 (2006)

    Google Scholar 

  20. Nash, J.F.: Non-Cooperative Games. Annals of Mathematics 54(2), 286–295 (1951)

    Article  MathSciNet  MATH  Google Scholar 

  21. Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory 2, 65–67 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  22. Roughgarden, T., Tardos, É.: How Bad Is Selfish Routing? Journal of the ACM 49(2), 236–259 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  23. Tovey, C.A.: A Simplified NP-complete Satisfiability Problem. Discrete Applied Mathematics 8, 85–89 (1984)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. International Computer Science Institute, Berkeley, CA, USA

    Martin Gairing

Authors
  1. Martin Gairing
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. IBISC, CNRS FRE 3190, Université d’Evry Val d’Essonne, Boulevard François Mitterand,, 91025, Evry Cedex, France

    Evripidis Bampis

  2. Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften, Straße des 17. Juni 136, 10623, Berlin, Germany

    Martin Skutella

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gairing, M. (2009). Malicious Bayesian Congestion Games. In: Bampis, E., Skutella, M. (eds) Approximation and Online Algorithms. WAOA 2008. Lecture Notes in Computer Science, vol 5426. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-93980-1_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-93980-1_10

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-93979-5

  • Online ISBN: 978-3-540-93980-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation