Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Dynamic Games and Applications 1/2022

15.02.2022

A Partially Observable Stochastic Zero-sum Game for a Network Epidemic Control Problem

verfasst von: Olivier Tsemogne, Yezekael Hayel, Charles Kamhoua, Gabriel Deugoue

Erschienen in: Dynamic Games and Applications | Ausgabe 1/2022

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

The mathematical theory of epidemics borrows its fundamental notions from epidemiology. These notions encompass the division of the population of individuals into compartments and thereafter the classification of epidemics in models like SIR (susceptible-infected-removed). Unlike in biology, a broad number of epidemics are spread under the action of rational and intelligent malicious individuals, called attackers. The centralized control of such epidemics implies that a network defender is in conflict with the attacker and therefore should be modeled by a zero-sum noncooperative game theoretic concept. We design a new zero-sum partially observable stochastic game (POSG) theoretic framework in order to capture the interactions between network defender and an attacker. More, our model takes into account random node state transitions. The particularity of our model is that even though the attacker knows the state of the network, which is not the case for the defender, she cannot infer the defender’s actions. The tractability of the solution of classical POSG is improved by the mean of value backup iteration. We prove that the value backup operator converges even in our particular POSG coupled with a compartmental epidemic model.
Literatur
1.
Zurück zum Zitat Ansari A, Dadgar M, Hamzeh A, Schlötterer J, Granitzer M. Competitive influence maximization: integrating budget allocation and seed selection Ansari A, Dadgar M, Hamzeh A, Schlötterer J, Granitzer M. Competitive influence maximization: integrating budget allocation and seed selection
3.
Zurück zum Zitat Basu A, Stettner L (2015) Finite- and infinite-horizon Shapley games with nonsymmetric partial observation. SIAM J Control Optim 01(53):3584–3619 MathSciNetCrossRef Basu A, Stettner L (2015) Finite- and infinite-horizon Shapley games with nonsymmetric partial observation. SIAM J Control Optim 01(53):3584–3619 MathSciNetCrossRef
4.
Zurück zum Zitat Bernstein D, Givan R, Immerman N, Zilberstein S (2002) The complexity of decentralized control of Markov decision processes. Math Oper Res 27(4):819–840 MathSciNetCrossRef Bernstein D, Givan R, Immerman N, Zilberstein S (2002) The complexity of decentralized control of Markov decision processes. Math Oper Res 27(4):819–840 MathSciNetCrossRef
5.
Zurück zum Zitat Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. ACM Trans Inf Syst Security. 10(4) Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. ACM Trans Inf Syst Security. 10(4)
6.
Zurück zum Zitat Chatterjee K, Doyen L (2011) Partial-observation stochastic games: how to win when belief fails. ACM Trans Comput Logic 07:15 MATH Chatterjee K, Doyen L (2011) Partial-observation stochastic games: how to win when belief fails. ACM Trans Comput Logic 07:15 MATH
7.
Zurück zum Zitat Chen L, Wang Z, Li F, Guo Y, Geng K (2020) A Stackelberg security game for adversarial outbreak detection in the internet of things. Sensors. 02(20):804 CrossRef Chen L, Wang Z, Li F, Guo Y, Geng K (2020) A Stackelberg security game for adversarial outbreak detection in the internet of things. Sensors. 02(20):804 CrossRef
8.
Zurück zum Zitat Chen Z, Gao L, Kwiat K (2003) Modeling the spread of active worms. In: IEEE INFOCOM. vol. 3. IEEE. pp 1890–1900 Chen Z, Gao L, Kwiat K (2003) Modeling the spread of active worms. In: IEEE INFOCOM. vol. 3. IEEE. pp 1890–1900
9.
Zurück zum Zitat Cohen R, Havlin S, Ben-Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys Rev Lett. 91(24) Cohen R, Havlin S, Ben-Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys Rev Lett. 91(24)
10.
Zurück zum Zitat Fuchsberger A (2005) Intrusion detection systems and intrusion prevention systems. Inf Security Tech Report. 10(3):134–139 CrossRef Fuchsberger A (2005) Intrusion detection systems and intrusion prevention systems. Inf Security Tech Report. 10(3):134–139 CrossRef
11.
Zurück zum Zitat Garg N, Grosu D (2007) Deception in honeynets: a game-theoretic analysis. IEEE SMC Inf Assurance Security Workshop. 2007:107–113 Garg N, Grosu D (2007) Deception in honeynets: a game-theoretic analysis. IEEE SMC Inf Assurance Security Workshop. 2007:107–113
12.
Zurück zum Zitat Hansen E (2013) Solving POMDPs by searching in policy space. In: Proceedings of the fourteenth conference on uncertainty in artificial intelligence, 01 Hansen E (2013) Solving POMDPs by searching in policy space. In: Proceedings of the fourteenth conference on uncertainty in artificial intelligence, 01
13.
Zurück zum Zitat Horák K (2019) Scalable algorithms for solving stochastic games with limited partial observability. PhD thesis, Czech Technical University in Prague Horák K (2019) Scalable algorithms for solving stochastic games with limited partial observability. PhD thesis, Czech Technical University in Prague
14.
Zurück zum Zitat Horák K, Bosansky B (2019) Solving partially observable stochastic games with public observations. AAAI Conf Artif Intell 33:2029–2036 Horák K, Bosansky B (2019) Solving partially observable stochastic games with public observations. AAAI Conf Artif Intell 33:2029–2036
15.
Zurück zum Zitat Horák K, Bošanský B, Pĕchouček M (2017) Heuristic search value iteration for one-sided partially observable stochastic games. Int Joint Conf Artif Intell 31:558–564 Horák K, Bošanský B, Pĕchouček M (2017) Heuristic search value iteration for one-sided partially observable stochastic games. Int Joint Conf Artif Intell 31:558–564
16.
Zurück zum Zitat Horák K, Bosansky B, Tomášek P, Kiekintveld C, Kamhoua C (2019) Optimizing honeypot strategies against dynamic lateral movement using partially observable stochastic games. Comp Security. 07(87):101579 CrossRef Horák K, Bosansky B, Tomášek P, Kiekintveld C, Kamhoua C (2019) Optimizing honeypot strategies against dynamic lateral movement using partially observable stochastic games. Comp Security. 07(87):101579 CrossRef
17.
Zurück zum Zitat Horák K, Bosansky B, Kiekintveld C, Kamhoua C (2019) Compact representation of value function in partially observable stochastic games; pp 350–356 Horák K, Bosansky B, Kiekintveld C, Kamhoua C (2019) Compact representation of value function in partially observable stochastic games; pp 350–356
18.
Zurück zum Zitat Ierace N, Urrutia C, Bassett R (2005) Intrusion prevention systems. Ubiquity. 6(19):2–2 CrossRef Ierace N, Urrutia C, Bassett R (2005) Intrusion prevention systems. Ubiquity. 6(19):2–2 CrossRef
19.
Zurück zum Zitat Kiss IZ, Miller JC, Simon PL et al (2017) Mathematics of epidemics on networks, vol 598. Springer, Berlin CrossRef Kiss IZ, Miller JC, Simon PL et al (2017) Mathematics of epidemics on networks, vol 598. Springer, Berlin CrossRef
20.
Zurück zum Zitat Kolias C, Kambourakis G, Stavrou A, Voas J (2017) DDoS in the IoT: Mirai and other botnets. Computer 50(7):80–84 CrossRef Kolias C, Kambourakis G, Stavrou A, Voas J (2017) DDoS in the IoT: Mirai and other botnets. Computer 50(7):80–84 CrossRef
21.
22.
Zurück zum Zitat Melo E (2017) A variational approach to network games. SSRN Electron J 05 Melo E (2017) A variational approach to network games. SSRN Electron J 05
23.
Zurück zum Zitat Myerson RB (1997) Game theory: analysis of conflict. Havard University Press, Cambridge MATH Myerson RB (1997) Game theory: analysis of conflict. Havard University Press, Cambridge MATH
24.
Zurück zum Zitat Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A (2015) Epidemic processes in complex networks. Rev Mod Phys 87:925–979 MathSciNetCrossRef Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A (2015) Epidemic processes in complex networks. Rev Mod Phys 87:925–979 MathSciNetCrossRef
25.
Zurück zum Zitat Schneider C, Mihaljev T, Havlin S, Herrmann H (2011) Suppressing epidemics with a limited amount of immunization units. Phys Rev E Stat Nonlinear Soft Matter Phys 02:84 Schneider C, Mihaljev T, Havlin S, Herrmann H (2011) Suppressing epidemics with a limited amount of immunization units. Phys Rev E Stat Nonlinear Soft Matter Phys 02:84
26.
Zurück zum Zitat Smith T, Simmons R (2012) Heuristic search value iteration for POMDPs. Proceedings of UAI. 07 Smith T, Simmons R (2012) Heuristic search value iteration for POMDPs. Proceedings of UAI. 07
27.
Zurück zum Zitat Trajanovski S, Hayel Y, Altman E, Wang H, Mieghem P (2015) Decentralized protection strategies against SIS epidemics in networks. IEEE Trans Control of Netw Syst 2:406–419 MathSciNetCrossRef Trajanovski S, Hayel Y, Altman E, Wang H, Mieghem P (2015) Decentralized protection strategies against SIS epidemics in networks. IEEE Trans Control of Netw Syst 2:406–419 MathSciNetCrossRef
28.
Zurück zum Zitat Trajanovski S, Kuipers F, Hayel Y, Altman E, Mieghem P (2017) Designing virus-resistant, high-performance networks: a game-formation approach. IEEE Trans Control Netw Syst, 12 Trajanovski S, Kuipers F, Hayel Y, Altman E, Mieghem P (2017) Designing virus-resistant, high-performance networks: a game-formation approach. IEEE Trans Control Netw Syst, 12
29.
Zurück zum Zitat Tsemogne O, Hayel Y, Kamhoua C, Deugoué G (2020) Partially observable stochastic games for cyber deception against network epidemic. In: Decision and game theory for security, pp 312–325 Tsemogne O, Hayel Y, Kamhoua C, Deugoué G (2020) Partially observable stochastic games for cyber deception against network epidemic. In: Decision and game theory for security, pp 312–325
30.
Zurück zum Zitat Tsemogne O, Hayel Y, Kamhoua C, Deugoué G (2021) Game theoretic modeling of cyber deception against epidemic botnets in internet of things. IEEE Int Things J Tsemogne O, Hayel Y, Kamhoua C, Deugoué G (2021) Game theoretic modeling of cyber deception against epidemic botnets in internet of things. IEEE Int Things J
31.
Zurück zum Zitat Van Mieghem P, Omic J, Kooij R (2009) Virus spread in networks. IEEE/ACM Trans Netw 17(1):1–14 CrossRef Van Mieghem P, Omic J, Kooij R (2009) Virus spread in networks. IEEE/ACM Trans Netw 17(1):1–14 CrossRef
Metadaten
Titel
A Partially Observable Stochastic Zero-sum Game for a Network Epidemic Control Problem
verfasst von
Olivier Tsemogne
Yezekael Hayel
Charles Kamhoua
Gabriel Deugoue
Publikationsdatum
15.02.2022
Verlag
Springer US
Erschienen in
Dynamic Games and Applications / Ausgabe 1/2022
Print ISSN: 2153-0785
Elektronische ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-022-00430-6

Weitere Artikel der Ausgabe 1/2022

Dynamic Games and Applications 1/2022 Zur Ausgabe

Premium Partner