* Terschlüsen and Leupold [2016] C. Terschlüsen and S. Leupold, Renormalization of the low-energy constants of Chiral Perturbation Theory from loops with dynamical vector mesons, Phys. Rev. D 94, 014021 (2016), arXiv:1603.05524 [hep-ph] .
  * Cirigliano  _et al._ [2003] V. Cirigliano, G. Ecker, H. Neufeld, and A. Pich, Meson resonances, large $N_{c}$ and chiral symmetry, JHEP 6, 1, arXiv:hep-ph/0305311 .
  * Gell-Mann and Levy [1960] M. Gell-Mann and M. M. Levy, The axial vector current in beta decay, Nuovo Cim. 16, 705 (1960).
  * Parganlija  _et al._ [2013] D. Parganlija, P. Kovacs, G. Wolf, F. Giacosa, and D. H. Rischke, Meson vacuum phenomenology in a three-flavor linear sigma model with (axial-)vector mesons, Phys. Rev. D 87, 014011 (2013), arXiv:1208.0585 [hep-ph] .
  * Ko and Rudaz [1994] P. Ko and S. L. Rudaz, Phenomenology of scalar and vector mesons in the linear $\sigma$ model, Phys. Rev. D 50, 6877 (1994).
  * Carter  _et al._ [1996] G. W. Carter, P. J. Ellis, and S. L. Rudaz, An effective Lagrangian with broken scale and chiral symmetry II: pion phenomenology, Nucl. Phys. A 603, 367 (1996), [Erratum: Nucl.Phys.A 608, 514–514 (1996)], arXiv:nucl-th/9512033 .
  * Janowski  _et al._ [2014] S. Janowski, F. Giacosa, and D. H. Rischke, Is $f_{0}(1710)$ a glueball?, Phys. Rev. D 90, 114005 (2014), arXiv:1408.4921 [hep-ph] .
  * Koch [1997] V. Koch, Aspects of chiral symmetry, Int. J. Mod. Phys. E 6, 203 (1997), arXiv:nucl-th/9706075 .
  * Gies [2012] H. Gies, Introduction to the Functional RG and applications to gauge theories, Lect. Notes Phys. 852, 287 (2012), arXiv:hep-ph/0611146 .
  * Polonyi [2003] J. Polonyi, Lectures on the Functional Renormalization Group method, Central Eur. J. Phys. 1, 1 (2003), arXiv:hep-th/0110026 .
  * Wetterich [1993] C. Wetterich, Exact evolution equation for the effective potential, Phys. Lett. B 301, 90 (1993), arXiv:1710.05815 [hep-th] .
  * Morris [1994] T. R. Morris, The Exact Renormalization Group and approximate solutions, Int. J. Mod. Phys. A 9, 2411 (1994), arXiv:hep-ph/9308265 .
  * Dupuis  _et al._ [2020] N. Dupuis, L. Canet, A. Eichhorn, W. Metzner, J. M. Pawlowski, M. Tissier, and N. Wschebor, The nonperturbative functional renormalization group and its applications (2020), arXiv:2006.04853 [cond-mat.stat-mech] .
  * Pawlowski [2007] J. M. Pawlowski, Aspects of the functional renormalisation group, Annals Phys. 322, 2831 (2007), arXiv:hep-th/0512261 .
  * Grahl and Rischke [2013] M. Grahl and D. H. Rischke, Functional Renormalization Group study of the two-flavor linear sigma model in the presence of the axial anomaly, Phys. Rev. D 88, 056014 (2013), arXiv:1307.2184 [hep-th] .
  * Eser  _et al._ [2015] J. Eser, M. Grahl, and D. H. Rischke, Functional Renormalization Group study of the chiral phase transition including vector and axial-vector mesons, Phys. Rev. D 92, 096008 (2015), arXiv:1508.06928 [hep-ph] .
  * Rennecke and Schaefer [2017] F. Rennecke and B.-J. Schaefer, Fluctuation-induced modifications of the phase structure in $(2+1)$-flavor QCD, Phys. Rev. D 96, 016009 (2017), arXiv:1610.08748 [hep-ph] .
  * Pawlowski and Rennecke [2014] J. M. Pawlowski and F. Rennecke, Higher order quark-mesonic scattering processes and the phase structure of QCD, Phys. Rev. D 90, 076002 (2014), arXiv:1403.1179 [hep-ph] .
  * Eser  _et al._ [2018] J. Eser, F. Divotgey, M. Mitter, and D. H. Rischke, Low-energy limit of the $O(4)$ quark-meson model from the functional renormalization group approach, Phys. Rev. D 98, 014024 (2018), arXiv:1804.01787 [hep-ph] .
  * Divotgey  _et al._ [2019] F. Divotgey, J. Eser, and M. Mitter, Dynamical generation of low-energy couplings from quark-meson fluctuations, Phys. Rev. D 99, 054023 (2019), arXiv:1901.02472 [hep-ph] .
  * Eser  _et al._ [2020] J. Eser, F. Divotgey, and M. Mitter, Low-energy limit of the $O(4)$ quark-meson model, PoS CD2018, 060 (2020), arXiv:1902.04804 [hep-ph] .
  * Cichutek  _et al._ [2020] N. Cichutek, F. Divotgey, and J. Eser, Fluctuation-induced higher-derivative couplings and infrared dynamics of the Quark-Meson-Diquark Model, Phys. Rev. D 102, 034030 (2020), arXiv:2006.12473 [hep-ph] .
  * Otto  _et al._ [2020a] K. Otto, M. Oertel, and B.-J. Schaefer, Hybrid and quark star matter based on a nonperturbative equation of state, Phys. Rev. D 101, 103021 (2020a), arXiv:1910.11929 [hep-ph] .
  * Otto  _et al._ [2020b] K. Otto, M. Oertel, and B.-J. Schaefer, Nonperturbative quark matter equations of state with vector interactions, Eur. Phys. J. ST 229, 3629 (2020b), arXiv:2007.07394 [hep-ph] .
  * Jung and von Smekal [2019] C. Jung and L. von Smekal, Fluctuating vector mesons in analytically continued functional RG flow equations, Phys. Rev. D 100, 116009 (2019), arXiv:1909.13712 [hep-ph] .
  * Heller and Mitter [2016] M. Heller and M. Mitter, Pion and $\eta$-meson mass splitting at the two-flavour chiral crossover, Phys. Rev. D 94, 074002 (2016), arXiv:1512.05241 [hep-ph] .
  * ’t Hooft [1974] G. ’t Hooft, A planar diagram theory for strong interactions, Nucl. Phys. B 72, 461 (1974).
  * Witten [1979] E. Witten, Baryons in the $1/N$ expansion, Nucl. Phys. B 160, 57 (1979).
  * Lebed [1999] R. F. Lebed, Phenomenology of large $N_{c}$ QCD, Czech. J. Phys. 49, 1273 (1999), arXiv:nucl-th/9810080 .
  * Giacosa  _et al._ [2017] F. Giacosa, J. Sammet, and S. Janowski, Decays of the vector glueball, Phys. Rev. D 95, 114004 (2017), arXiv:1607.03640 [hep-ph] .
  * Divotgey  _et al._ [2018] F. Divotgey, P. Kovacs, F. Giacosa, and D. H. Rischke, Low-energy limit of the extended linear sigma model, Eur. Phys. J. A 54, 5 (2018), arXiv:1605.05154 [hep-ph] .
  * Amelino-Camelia  _et al._ [2010] G. Amelino-Camelia _et al._ , Physics with the KLOE-2 experiment at the upgraded DA$\phi$NE, Eur. Phys. J. C 68, 619 (2010), arXiv:1003.3868 [hep-ex] .
  * Feldmann  _et al._ [1998] T. Feldmann, P. Kroll, and B. Stech, Mixing and decay constants of pseudoscalar mesons, Phys. Rev. D 58, 114006 (1998), arXiv:hep-ph/9802409 .
  * ’t Hooft [1986] G. ’t Hooft, How instantons solve the $U(1)$ problem, Phys. Rept. 142, 357 (1986).
  * Giacosa  _et al._ [2018] F. Giacosa, A. Koenigstein, and R. D. Pisarski, How the axial anomaly controls flavor mixing among mesons, Phys. Rev. D 97, 091901 (2018), arXiv:1709.07454 [hep-ph] .
  * Burakovsky and Goldman [1998] L. Burakovsky and T. J. Goldman, Regarding the enigmas of $P$-wave meson spectroscopy, Phys. Rev. D 57, 2879 (1998), arXiv:hep-ph/9703271 .
  * Hatanaka and Yang [2008] H. Hatanaka and K.-C. Yang, $K_{1}(1270)$ – $K_{1}(1400)$ mixing angle and new-physics effects in $B\rightarrow K_{1}l^{+}l^{-}$ decays, Phys. Rev. D 78, 074007 (2008), arXiv:0808.3731 [hep-ph] .
  * Cheng [2012] H.-Y. Cheng, Revisiting axial-vector meson mixing, Phys. Lett. B 707, 116 (2012), arXiv:1110.2249 [hep-ph] .
  * Yang [2007] K.-C. Yang, Light-cone distribution amplitudes of axial-vector mesons, Nucl. Phys. B 776, 187 (2007), arXiv:0705.0692 [hep-ph] .
  * Amsler and Close [1995] C. Amsler and F. E. Close, Evidence for a scalar glueball, Phys. Lett. B 353, 385 (1995), arXiv:hep-ph/9505219 .
  * Amsler and Close [1996] C. Amsler and F. E. Close, Is $f_{0}(1500)$ a scalar glueball?, Phys. Rev. D 53, 295 (1996), arXiv:hep-ph/9507326 .
  * Strohmeier-Presicek  _et al._ [1999] M. Strohmeier-Presicek, T. Gutsche, R. Vinh Mau, and A. Faessler, Glueball-quarkonia content and decay of scalar-isoscalar mesons, Phys. Rev. D 60, 054010 (1999), arXiv:hep-ph/9904461 .
  * Lee and Weingarten [1999] W.-J. Lee and D. Weingarten, Scalar quarkonium masses and mixing with the lightest scalar glueball, Phys. Rev. D 61, 014015 (1999), arXiv:hep-lat/9910008 .
  * Cheng  _et al._ [2006] H.-Y. Cheng, C.-K. Chua, and K.-F. Liu, Scalar glueball, scalar quarkonia, and their mixing, Phys. Rev. D 74, 094005 (2006), arXiv:hep-ph/0607206 .
  * Gutsche  _et al._ [2016] T. Gutsche, S. Kuleshov, V. E. Lyubovitskij, and I. T. Obukhovsky, Search for the glueball content of hadrons in $\gamma p$ interactions at GlueX, Phys. Rev. D 94, 034010 (2016), arXiv:1605.01035 [hep-ph] .
  * Wang  _et al._ [2015] B. Wang, C.-Q. Pang, X. Liu, and T. Matsuki, Pseudotensor meson family, Phys. Rev. D 91, 014025 (2015), arXiv:1410.3930 [hep-ph] .
  * Chen  _et al._ [2013] B. Chen, K.-W. Wei, and A. Zhang, $X(1870)$ and $\eta_{2}(1870)$: Which can be assigned as a hybrid state?, Adv. High Energy Phys. 2013, 217858 (2013), arXiv:1304.6190 [hep-ph] .
  * Kuhn  _et al._ [2004] J. Kuhn _et al._ (E852), Exotic meson production in the $f_{1}(1285)\,\pi^{-}$ system observed in the reaction $\pi^{-}\,p\rightarrow\eta\,\pi^{+}\,\pi^{-}\,\pi^{-}\,p$ at $18\,\,$GeV/c, Phys. Lett. B 595, 109 (2004), arXiv:hep-ex/0401004 .
  * Giacosa and Pagliara [2007] F. Giacosa and G. Pagliara, Spectral functions of scalar mesons, Phys. Rev. C 76, 065204 (2007), arXiv:0707.3594 [hep-ph] .
  * Schneitzer  _et al._ [2014] J. Schneitzer, T. Wolkanowski, and F. Giacosa, The role of the next-to-leading order triangle-shaped diagram in two-body hadronic decays, Nucl. Phys. B 888, 287 (2014), arXiv:1407.7414 [hep-ph] .
  * Aston  _et al._ [1988] D. Aston _et al._ , Spin-parity determination of the $\phi_{J}(1850)$ from $K^{-}\,p$ interactions at $11\,\,$ GeV/$c$, Phys. Lett. B 208, 324 (1988).
  * Al-Harran  _et al._ [1981] S. Al-Harran _et al._ (Birmingham-CERN-Glasgow-Michigan State-Paris), Observation of a $K\,\bar{K}$ enhancement at $1.85\,\,$ GeV in the reaction $K^{-}\,p\rightarrow K\,\bar{K}\,\Lambda$ at $8.25\,\,$ GeV/c, Phys. Lett. B 101, 357 (1981).
  * Ebert and Volkov [1983] D. Ebert and M. K. Volkov, Composite-meson model with vector dominance based on $U(2)$ invariant four-quark interactions, Z. Phys. C 16, 205 (1983).
  * O’Connell  _et al._ [1997] H. B. O’Connell, B. C. Pearce, A. W. Thomas, and A. G. Williams, $\rho-\omega$ mixing, vector meson dominance and the pion form-factor, Prog. Part. Nucl. Phys. 39, 201 (1997), arXiv:hep-ph/9501251 .
  * Kim  _et al._ [1996] J. K. Kim, P. Ko, K. Y. Lee, and S. Rudaz, $a_{1}(1260)$ contribution to photon and dilepton productions from hot hadronic matter reexamined, Phys. Rev. D 53, 4787 (1996), arXiv:hep-ph/9602293 .
  * Amelin  _et al._ [2000] D. V. Amelin _et al._ (VES), Natural parity resonances in $\eta\,\pi^{+}\pi^{-}$, Nucl. Phys. A 668, 83 (2000).
  * Aston  _et al._ [1987] D. Aston _et al._ , The strange meson resonances observed in the reaction $K^{-}\,p\rightarrow\bar{K}^{0}\,\pi^{+}\,\pi^{-}\,n$ at $11\,\,$ GeV/$c$, Nucl. Phys. B 292, 693 (1987).
  * Baubillier  _et al._ [1979] M. Baubillier _et al._ (Birmingham-CERN-Glasgow-Michigan State-Paris), Evidence for the $B\,\pi$ decay mode of the $\omega(1670)$, Phys. Lett. B 89, 131 (1979).
  * Diaz  _et al._ [1974] J. Diaz _et al._ , Evidence for the omega $\omega\,\pi\,\pi$ decay modes of the $A_{2}$ and $\omega$(1675), Phys. Rev. Lett. 32, 260 (1974).
  * Baltay  _et al._ [1978] C. Baltay, V. C. Cautis, D. H. Cohen, S. E. Csorna, M. Kalelkar, D. Pisello, W. D. Smith, and N. Yeh, Meson resonance production in $\pi^{+}\,p$ interactions at $15\,\,$GeV/c, Phys. Rev. D 17, 62 (1978).
  * Bartsch  _et al._ [1970] J. Bartsch _et al._ (Aachen-Berlin-CERN), The $g$-meson, Nucl. Phys. B 22, 109 (1970).
  * Kliger  _et al._ [1974] G. Kliger _et al._ , Investigation of a four $\pi$ system in the $\rho^{\prime}(1710)$-meson mass region in the reaction $\pi^{-}\,\rho\rightarrow\rho\,\pi^{+}\,\pi^{-}\,\pi^{-}\,\pi^{0}$ at $4.5\,\,$GeV/c, Sov. J. Nucl. Phys. 19, 428 (1974).
  * Thompson  _et al._ [1974] G. Thompson _et al._ , Study of the $R$ Meson Produced in $13\,\,$GeV/c $\pi^{+}\,p$ Interactions, Nucl. Phys. B 69, 220 (1974).
  * Gregory  _et al._ [2012] E. B. Gregory, A. C. Irving, B. Lucini, C. C. McNeile, A. Rago, C. Richards, and E. Rinaldi, Towards the glueball spectrum from unquenched lattice QCD, JHEP 10, 170, arXiv:1208.1858 [hep-lat] .
  * Ochs [2013] W. Ochs, The status of glueballs, J. Phys. G 40, 043001 (2013), arXiv:1301.5183 [hep-ph] .
  * Mathieu  _et al._ [2009] V. Mathieu, N. Kochelev, and V. Vento, The physics of glueballs, Int. J. Mod. Phys. E 18, 1 (2009), arXiv:0810.4453 [hep-ph] .
  * Crede and Meyer [2009] V. Crede and C. A. Meyer, The experimental status of glueballs, Prog. Part. Nucl. Phys. 63, 74 (2009), arXiv:0812.0600 [hep-ex] .
  * Eshraim  _et al._ [2013] W. I. Eshraim, S. Janowski, F. Giacosa, and D. H. Rischke, Decay of the pseudoscalar glueball into scalar and pseudoscalar mesons, Phys. Rev. D 87, 054036 (2013), arXiv:1208.6474 [hep-ph] .
  * Collins  _et al._ [1977] J. C. Collins, A. Duncan, and S. D. Joglekar, Trace and dilatation anomalies in gauge theories, Phys. Rev. D 16, 438 (1977).
  * Greiner  _et al._ [2007] W. Greiner, S. Schramm, and E. Stein,  _Quantum Chromodynamics_, 3rd ed. (Springer-Verlag Berlin Heidelberg, 2007) p. 554.
  * Eshraim  _et al._ [2020] W. I. Eshraim, C. S. Fischer, F. Giacosa, and D. Parganlija, Hybrid phenomenology in a chiral approach, Eur. Phys. J. Plus 135, 945 (2020), arXiv:2001.06106 [hep-ph] .
  * Parganlija and Giacosa [2017] D. Parganlija and F. Giacosa, Excited scalar and pseudoscalar mesons in the extended linear sigma model, Eur. Phys. J. C 77, 450 (2017), arXiv:1612.09218 [hep-ph] .
  * Wilson [1971a] K. G. Wilson, Renormalization group and critical phenomena. 1. Renormalization group and the Kadanoff scaling picture, Phys. Rev. B 4, 3174 (1971a).
  * Wilson [1971b] K. G. Wilson, Renormalization group and critical phenomena. 2. Phase space cell analysis of critical behavior, Phys. Rev. B 4, 3184 (1971b).
  * Polchinski [1984] J. Polchinski, Renormalization and effective Lagrangians, Nucl. Phys. B 231, 269 (1984).
  * Gies and Wetterich [2002] H. Gies and C. Wetterich, Renormalization flow of bound states, Phys. Rev. D 65, 065001 (2002), arXiv:hep-th/0107221 .
  * Braun  _et al._ [2010] J. Braun, H. Gies, and J. M. Pawlowski, Quark confinement from color confinement, Phys. Lett. B 684, 262 (2010), arXiv:0708.2413 [hep-th] .
  * Braun  _et al._ [2016] J. Braun, L. Fister, J. M. Pawlowski, and F. Rennecke, From quarks and gluons to hadrons: Chiral symmetry breaking in dynamical QCD, Phys. Rev. D 94, 034016 (2016), arXiv:1412.1045 [hep-ph] .
  * Roca and Oset [2010] L. Roca and E. Oset, A description of the $f_{2}(1270)$, $\rho_{3}(1690)$, $f_{4}(2050)$, $\rho_{5}(2350)$ and $f_{6}(2510)$ resonances as multi-$\rho(770)$ states, Phys. Rev. D 82, 054013 (2010), arXiv:1005.0283 [hep-ph] .
  * Yamagata-Sekihara  _et al._ [2010] J. Yamagata-Sekihara, L. Roca, and E. Oset, On the nature of the $K^{*}_{2}(1430)$, $K^{*}_{3}(1780)$, $K^{*}_{4}(2045)$, $K^{*}_{5}(2380)$ and $K^{*}_{6}$ as $K^{*}$-multi-$\rho$ states, Phys. Rev. D 82, 094017 (2010), [Erratum: Phys.Rev.D 85, 119905 (2012)], arXiv:1010.0525 [hep-ph] .
  * Greiner and Reinhardt [1996] W. Greiner and J. Reinhardt,  _Field quantization_ (Springer, Berlin Heidelberg, 1996) p. 441.
  * Wolfram Research [2020] I. Wolfram Research, Mathematica, Version 12.1 (2020), champaign, IL, 2020.
  * Koenigstein  _et al._ [2016] A. Koenigstein, F. Giacosa, and D. H. Rischke, Classical and quantum theory of the massive spin-two field, Annals Phys. 368, 16 (2016), arXiv:1508.00110 [hep-th] .
  * Fierz [1939] M. E. Fierz, Über die relativistische Theorie kräftefreier Teilchen mit beliebigem Spin, Helv. Phys. Acta 12, 3 (1939).
  * Fierz and Pauli [1939] M. E. Fierz and W. Pauli, On relativistic wave equations for particles of arbitrary spin in an electromagnetic field, Proc. Roy. Soc. Lond. A 173, 211 (1939).
  * Huang  _et al._ [2002] S.-Z. Huang, T.-N. Ruan, N. Wu, and Z.-P. Zheng, Wavefunctions for particles with arbitrary spin, Commun. Theor. Phys. 37, 63 (2002).
  * Bouatta  _et al._ [2004] N. Bouatta, G. Compere, and A. Sagnotti, An introduction to free higher-spin fields, in  _1st Solvay Workshop on Higher Spin Gauge Theories_ (2004) pp. 79–99, arXiv:hep-th/0409068 .
  * Barut and Raczka [1986] A. O. Barut and R. Raczka,  _Theory of group representations and applications_ (World Scientific Singapore, 1986) p. 740.
  * Durand [1967] L. Durand, Subsidiary Regge trajectories with singular residues. Nucleon-nucleon scattering, Phys. Rev. Lett. 18, 58 (1967).
  * Zee [2010] A. Zee,  _Quantum field theory in a nutshell_ (Princeton University Press, 2010) p. 608.


# Synthesizing Efficient Solutions for Patrolling Problems
in the Internet Environment

Tomáš Brázdil, Antonín Kučera, Vojtěch Řehák
Faculty of Informatics, Masaryk University
Brno, Czech Republic
<EMAIL_ADDRESS>Supported by grant No. P202/12/G061, Czech
Science Foundation. Access to computing and storage facilities owned by
parties and projects contributing to the National Grid Infrastructure
MetaCentrum provided under the programme ”Projects of Large Research,
Development, and Innovations Infrastructures” (CESNET LM2015042), is greatly
appreciated.

###### Abstract

We propose an algorithm for constructing efficient patrolling strategies in
the Internet environment, where the protected targets are nodes connected to
the network and the patrollers are software agents capable of
detecting/preventing undesirable activities on the nodes. The algorithm is
based on a novel compositional principle designed for a special class of
strategies, and it can quickly construct (sub)optimal solutions even if the
number of targets reaches hundreds of millions.

##  1 Introduction

A _security game_ is a non-cooperative game where the Defender (leader)
commits to some strategy and the Attacker (follower) first observes this
strategy and then selects a best response. In _adversarial_ security games, it
is assumed that the Attacker not only knows the Defender’s strategy, but can
also observe the current positions and moves of the patrollers. This worst-
case assumption is adequate also in situations when the actual Attacker’s
abilities are _unknown_ and robust defending strategies are required.

In this paper, we concentrate on adversarial patrolling in the _Internet
environment_ , where the protected targets are fully connected by a network,
and the patrollers are software agents freely moving among the targets trying
to discover/prevent dangerous ongoing activities. We start by presenting two
concrete scenarios111These scenarios should be seen just as _examples_ of
possible application areas for our results, not as an exhaustive list.
illustrating the considered class of security problems.

1\. Large-scale surveillance systems. Contemporary surveillance systems may
comprise thousands (or even millions222According to IHS, there were 245
million professionally installed video surveillance cameras active and
operational globally in 2014.) of cameras watching complex scenes where real-
time detection and alert are crucial. For example, crime detection systems
assume fast response in case of crime or suspect detected. Also, they
typically need sophisticated and computation intensive analytics (see, e.g.,
Cotton (2015)) such as object detection, database retrieval of image data,
etc. Simple object detection tools running on high-end GPUs are capable of
processing hundreds full scale images per second Redmon et al. (2016). More
detailed analysis, such as search of a detected face in a large database of
suspects, causes even smaller number of processed images per second. This
means that the delay caused by the analytics may prevent _simultaneous_ real-
time analysis of _all_ video streams in a large-scale surveillance system, and
the system must intelligently switch among the streams in real-time. Since the
image processing time is substantially shorter than the intrusion time, there
is a chance of achieving a good level of protection even if the system runs
only a limited number of analytical processes concurrently. The crucial
question is how to schedule the “visits” of these processes (patrollers) to
the individual cameras (targets) so that the chance of discovering an ongoing
intrusion is maximized. Since the analytics is not perfect, a patroller
detects an ongoing intrusion in a currently visited target only with certain
probability. Hence, the chance of successful intrusion detection increases if
the target under attack is visited repeatedly before completing the attack.

2\. Remote software protection. Protecting software from man-at-the-end (MATE)
tampering is a hard problem in general. In client-server systems, where the
server part is considered trusted, _continuous software updates_ of the client
software have been proposed as a promising technique for achieving the
protection Ceccato and Tonella (2011); Collberg et al. (2012). Since
completing a MATE attack requires a substantial amount of time and effort, the
idea is to update some crucial components of the client software regularly (by
the trusted server) so that the malicious ongoing analysis becomes useless and
it must be restarted. If these updates are performed frequently enough, a MATE
attack cannot be completed. However, the server’s capacity is limited and the
number of clients is typically very large (especially when the clients are
split into independent submodules to decrease the update overhead). The
question is how to design a suitable update policy for the server achieving a
good protection against a MATE actively seeking for a weakly protected client.
A detailed discussion of all relevant aspects can be found in Basilico et al.
(2016a) where a _security game model_ of the problem is designed. The
patrollers are the update processes managed by the server, and the targets are
the client software modules. Each target is assigned the time needed to
complete a MATE attack and another natural number specifying its _importance_.
It is assumed that performing an update takes a constant time. Although the
patrollers cannot detect an ongoing MATE attack at the currently updated
target, it is assumed that a possible ongoing attack is always interrupted by
the update. Furthermore, it is shown how to compute a _positional_ Defender’s
strategy for updating the targets, where the Defender’s decisions depend only
on the current positions (i.e., the tuple of currently visited modules) of the
patrollers. In Basilico et al. (2016a), it is explicitly mentioned333A
rigorous proof revealing insufficiency of positional strategies can be found
in Kučera and Lamser (2016). that positional strategies are _weaker_ than
general _history-dependent_ strategies taking into account the whole history
of previous updates. Hence, positional strategies are generally not optimal,
and the computational framework of Basilico et al. (2016a) does not allow for
efficient construction of history-dependent strategies. This limitation is
overcome in the presented work (see below).

Our contribution. Before explaining our results, let us briefly summarize the
key _assumptions_ about the considered class of problems which are reflected
in the adopted game model (see Section 2):

1. _The environment is fully connected_. This is the basic property of Internet underpinning our (novel) approach to strategy synthesis based on game decomposition. The use of (non)linear programming is completely avoided.

2. _The patrollers are centrally coordinated._ The patrollers are software processes fully controlled by a server.

3. _The probability $p$ of recognizing an ongoing intrusion at a currently visited target is not necessarily equal to $1$._ That is, the intrusion detection is not fully accurate in general, as in Scenario 1. Note that is Scenario 2, an intrusion (MATE attack) is recognized (interrupted) with probability $1$.

4. _The time needed to complete an intrusion may depend on a concrete target, and the individual targets may have different importance._

5. _The time needed to complete a patroller’s activity is almost constant 444Technically, this means that time is random but strongly concentrated around its expected value. Note that in Scenario 1, the real-time detection consists of two phases where a given image is first quickly classified as either harmless or potentially dangerous (in almost constant time), and dangerous images are subsequently enqueued for a more advanced analysis, such as face recognition in a database of suspects. This queue is processed separately (possibly using special hardware), and hence the second phase does not influence the assignment of patrolling processes.._ This is satisfied in both scenarios.

6. _The number of targets is very large_. This influences mainly the methodology of algorithmic solutions. Algorithms for solving security games are mostly based on mathematical programming (see _Related work_). This approach becomes _infeasible_ in our setting where the number of targets can easily reach a billion.

We adopt the adversarial setting, i.e., assume that the Attacker knows the
Defender’s strategy (the server program assigning the patrolling processes to
targets) and can also determine the targets currently visited (e.g., by
analyzing the network traffic or deploying malware into the server). Since
there are no principal bounds on the duration of the patrolling task, our
games are of infinite horizon. The adopted solution concept is _Stackelberg
equilibrium_ (see, e.g, Yin et al. (2010)) where the Defender/Attacker
corresponds to the leader/follower.

Our main results can be summarized as follows:

A. We give an _upper bound_ on the level of protection achievable for a given
game structure and a given number of patrollers. Consequently, we can also
derive a _lower bound_ on the number of patrollers needed to achieve a given
level of protection. These bounds are valid for _general_ (i.e., history-
dependent and randomized) strategies. They are generally not tight, but good
enough to serve as a “yardstick” for measuring the quality of the constructed
Defender’s strategies.

B. We develop a novel _compositional_ approach to constructing Defender’s
strategies in Internet patrolling games. The method is based on splitting a
given game into disjoint subgames, solving them recursively, and then
combining the obtained solutions into a strategy for the original game. We
evaluate the quality of the constructed strategies against the bounds
described in A., and show that our algorithm produces _provably_ (sub)optimal
solutions. A precise formulation is given in Section 6.1.

The running time of our algorithm is low. Instances with millions of targets
are processed in units of seconds (see Section 6.1). The only potentially
costly part is solving a certain system of polynomial equations constructed by
the algorithm, but this was always achieved in less than a second for all
instances we analyzed (using Maple). The constructed strategies are randomized
and history-dependent. We call them _modular_ because they use a bounded
counter to count the units of elapsed time modulo certain constant. Hence,
modular strategies are still easy to implement.

One may also ask whether some “naive” strategy synthesis method can produce
strategies of comparable quality (i.e., whether our decomposition method is
really worth the invested effort). Perhaps, the most straightforward way of
constructing _some_ reasonable Defender’s strategy is to compute a positional
strategy where the probability of selecting a given vertex depends only on its
importance and attack length, and it is chosen so that all vertices are
protected equally well. We demonstrate that the strategies computed by our
algorithm are _substantially_ better than these naively constructed ones.

Related work. Most of the existing works about security games study either the
problem of computing an optimal static allocation of available resources to
the targets, or the problem of computing an optimal movement strategy for a
mobile Defender. Security games with static allocation have been studied in,
e.g., Jain et al. (2010); Kiekintveld et al. (2009); Pita et al. (2008); Tsai
et al. (2009). In patrolling games, the focus was primarily on finding locally
optimal strategies for robotic patrolling units either on restricted graphs
such as circles Agmon et al. (2008a, b), or arbitrary graphs with weighted
preference on the targets Basilico et al. (2009a, b). Alternatively, the work
focused on some novel aspects of the problem, such as variants with moving
targets Bosansky et al. (2011); Fang et al. (2013), multiple patrolling units
Basilico et al. (2010), or movement of the Attacker on the graph Basilico et
al. (2009b) and reaction to alarms de Cote et al. (2013); Basilico et al.
(2016b). Most of the existing literature assumes that the Defender is
following a positional strategy that depends solely on the current position of
the Defender in the graph and they seek for a solution using mathematical
programming Basilico et al. (2012). Few exceptions include duplicating each
node of the graph to distinguish internal states of the Defender (e.g., in
Agmon et al. (2008a) authors consider a direction of the patrolling robot as a
specific state; in Bosansky et al. (2012), this concept is further
generalized), or seeking for higher-order strategies in Basilico et al.
(2009a). In Abaffy et al. (2014), an algorithm for computing an
$\varepsilon$-optimal strategy for the Defender is designed, but this
algorithm is of exponential complexity. The existing works on multi-agent
patrolling mostly assume autonomous patrollers without a central supervision
(see, e.g., Almeida et al. (2004)).

A patrolling game model for remote software protection has been proposed in
Basilico et al. (2016a). The model is similar to ours, but the probability of
detecting (interrupting) an ongoing intrusion is set to $1$, which simplifies
the strategy synthesis (repeated visits to the same target during an ongoing
intrusion do not increase its protection). The constructed Defender’s
strategies are positional and computed by standard methods based on
mathematical programming, which limits their scalability and does not lead to
optimal solutions.

Continuous-time adversarial patrolling games with one patroller in fully
connected environment have recently been studied in Kempe et al. (2018). Based
on the Defender’s strategy, the Attacker selects which vertex to attack and
for how long. The Attacker expected utility grows linearly with the time spent
in the vertex but drops to 0 if being caught. The Defender’s goal is to
minimize the Attacker’s utility. This setup is technically different from
ours, although it is also motivated by possible applications in Internet
security problems (in Kempe et al. (2018), no concrete scenarios illustrating
the applicability of the considered model are given).

##  2 The Game Model

In this section we present our game-theoretic model of adversarial patrolling
in the Internet environment reflecting Assumptions 1.-6. formulated in Section
1.

Preliminaries. We use $\mathbb{N}_{0}$ and $\mathbb{N}$ to denote the sets of
non-negative and positive integers, respectively. The set of all probability
distributions over a finite set $M$ is denoted by $\Delta(M)$. The lower and
upper integer approximations of a real number $a$ are written as $\lfloor
a\rfloor$ and $\lceil a\rceil$, respectively. The number of elements of a set
$A$ is denoted by $|A|$. A $k$-subset of $A$ is a subset of $A$ with precisely
$k$ elements, and we use $A^{\langle k\rangle}$ to denote the set of all
$k$-subsets of $A$. For $f:A\rightarrow B$ and $X\subseteq A$, we use $f|_{X}$
to denote the restriction of $f$ to $X$.

Game structures. A _game structure_ is a tuple $\mathcal{G}=(V,d,\alpha,p)$,
where $V$ is a finite set of _vertices_ (targets), $d:V\rightarrow\mathbb{N}$
specifies the number of time units needed to complete an intrusion at a given
vertex, $\alpha:V\rightarrow\mathbb{N}$ is a _cost_ function specifying the
importance of each vertex (a higher number means higher importance), and
$p\in(0,1]$ is the probability of discovering an ongoing intrusion by a
patroller visiting a vertex under attack. We assume that a patroller spends
one unit of time when moving from vertex to vertex, which corresponds to
performing the patroller’s activity at the previously visited vertex.

Defeder’s strategy. Assume $\mathcal{G}$ is protected by $k\in\mathbb{N}$
patrollers (where $k\leq|V|$) centrally coordinated by the Defender who has a
complete knowledge about the history of previously visited vertices. Based on
the history, the Defender selects a $k$-subset of vertices where the
patrollers are sent in the next round, and this decision can be randomized.

Formally, a _Defender’s strategy_ is a function $\eta$ assigning to every
history $U_{1},\ldots,U_{\ell}$, where $\ell\geq 0$ and $U_{i}$ is the
$k$-subset of vertices visited in round $i$, a probability distribution over
$V^{\langle k\rangle}$. Note that a $k$-subset of vertices visited in the
first round is determined by $\eta(\varepsilon)$, where $\varepsilon$ is the
empty history. A strategy $\eta$ is _positional_ if
$\eta(U_{1},\ldots,U_{\ell})$ depends only on $U_{\ell}$.

Each strategy $\eta$ determines a unique probability space over all _walks_ ,
i.e., infinite sequences $U_{1},U_{2},\ldots$ where $U_{i}\in V^{\langle
k\rangle}$ for all $i\in\mathbb{N}$, in the standard way.

Attacker’s strategy. Depending on the observed history of visited vertices,
the Attacker may choose to attack some vertex or wait. Formally, an
_Attacker’s strategy_ is a function $\pi$ assigning to every history an
element of $V\cup\\{\bot\\}$ such that whenever
$\pi(U_{1},\ldots,U_{\ell})\neq{\bot}$, then for all $j<\ell$ we have that
$\pi(U_{1},\ldots,U_{j})={\bot}$, i.e., the Attacker may attack at most once
along a walk.

Level of protection. The aim of the Attacker is to maximize the _expected
damage_ , i.e., the expected cost of a successfully attacked target, and the
Defender aims at the opposite. Let us fix an Attacker’s strategy $\pi$, and
let $w=U_{1},U_{2},\ldots$ be a walk. The damage achieved by $\pi$ in $w$,
denoted by $\mathit{Damage}^{\pi}(w)$, is defined as follows:

  * •

If the Attacker does not attack along $w$, i.e.,
$\pi(U_{1},\ldots,U_{\ell})={\bot}$ for all $\ell\in\mathbb{N}_{0}$, then
$\mathit{Damage}^{\pi}(w){=}0$.

  * •

Otherwise, there is $\ell\in\mathbb{N}_{0}$ such that
$\pi(U_{1},\ldots,U_{\ell})=v$, where $v\in V$ is the attacked vertex. For a
given $i\in\\{1,\ldots,d(v)\\}$, we say that $v$ is _visited in round $i$_
(since the moment of initiating the attack) if $v\in U_{\ell+i}$. For each
such $i$, the probability of discovering the ongoing attack is $p$. The attack
is successful if it remains undiscovered after _all_ visits to $v$ in the next
$d(v)$ rounds (the individual trials are considered independent). That is, the
probability of performing the attack successfully is equal to $(1-p)^{c}$,
where $c$ is the total number of all $i\in\\{1,\ldots,d(v)\\}$ such that $v$
is visited in round $i$. We put

$\mathit{Damage}^{\pi}(w)\ =\ (1-p)^{c}\cdot\alpha(v)$

to reflect the importance of the attacked vertex $v$ (if $p=1$ and $c=0$, we
put $\mathit{Damage}^{\pi}(w)=\alpha(v)$).

Let $\eta$ be a Defender’s strategy for $k$ patrollers and $\pi$ an Attacker’s
strategy. The _expected damage_ caused by $\pi$ when the Defender commits to
$\eta$, denoted by $\mathbb{E}^{\eta}[\mathit{Damage}^{\pi}]$, is the expected
value of $\mathit{Damage}^{\pi}$ in the probability space over the walks
determined by $\eta$ (see above). Note that
$\mathbb{E}^{\eta}[\mathit{Damage}^{\pi}]\leq\alpha_{\max}$, where
$\alpha_{\max}$ is the maximal cost assigned to a vertex of $\mathcal{G}$.

In Section 1, we used the term “protection” instead of “damage”, and said that
the Defender aims at maximizing the protection rather than minimizing the
damage. This original terminology seems more intuitive, and it will be used
also in the rest of this paper. Formally, the _level of protection_ achieved
by $\eta$ against $\pi$ is defined as

$\mathit{Lev}(\eta,\pi)\ =\
\alpha_{\max}-\mathbb{E}^{\eta}[\mathit{Damage}^{\pi}]\,.$

Note that maximizing the level of protection is _equivalent_ to minimizing the
expected damage.

Furthermore, the level of protection achieved by $\eta$ (against _any_ $\pi$)
is defined by $\mathit{Lev}(\eta)=\inf_{\pi}\mathit{Lev}(\eta,\pi)\,.$
Finally, the maximal level of protection achievable with $k$ patrollers is
defined as $\mathit{Lev}_{k}\ =\ \sup_{\eta}\,\mathit{Lev}(\eta)$, where
$\eta$ ranges over all Defender’s strategies for $k$ patrollers. The
underlying $\mathcal{G}$ will always be clearly determined by the context. A
Defender’s strategy $\eta$ for $k$ patrollers is _$\delta$ -optimal_, where
$\delta\geq 0$, if $\mathit{Lev}(\eta)\geq\mathit{Lev}_{k}-\delta$. A
$0$-optimal strategy is called _optimal_.

##  3 The Bounds

In this section we give an upper bound on $\mathit{Lev}_{k}$ and a lower bound
on the number of patrollers needed to achieve a given level of protection.
These bounds are not always tight, but good enough for evaluating the
efficiency of Defender’s strategies computed by the algorithm of Section 6.

The bounds are obtained by solving a non-trivial system of exponential
equations constructed for a given game structure. In general, the solution can
only be computed by numerical methods, which is fully sufficient for our
purposes. Contemporary mathematical software such as Maple can perform the
required computations very efficiently even if for high parameter values.

Let $\mathcal{G}=(V,d,\alpha,p)$ be a game structure, and $\alpha_{\max}$ the
maximal cost assigned to a vertex of $\mathcal{G}$. Furthermore, let $\varrho$
be a fresh variable. For every $v\in V$, we construct the equation

$\varrho=\alpha_{\max}-\alpha(v)\cdot(1-p)^{\left\lfloor
Q_{v}\right\rfloor}\cdot(1-p\cdot(Q_{v}-{\left\lfloor Q_{v}\right\rfloor}))$

where $Q_{v}$ is a fresh variable (if $p=1$, the equation is simplified into
$\varrho=\alpha_{\max}-\alpha(v)\cdot(1-Q_{v})$). Let
$\mathcal{L}_{\mathcal{G}}$ be the resulting system of equations. Note that
$\mathcal{L}_{\mathcal{G}}$ has $|V|$ equations and $|V|+1$ variables.

######  Theorem 1.

Let $\mathcal{G}=(V,d,\alpha,p)$ be a game structure.

  * a)

The level of protection achievable with a given number of patrollers $k$ is
bounded from above by $\varrho$ obtained by solving the system
$\mathcal{L}_{\mathcal{G}}$ extended with the equation $k=\sum_{v\in
V,Q(v)>0}Q_{v}/d(v)$.

  * b)

Let $\tau\geq 0$ be a desired level of protection. Consider the system of
equations obtained by extending $\mathcal{L}_{\mathcal{G}}$ with the equation
$\tau=\varrho$. If this system has no solution such that $Q_{v}\leq d(v)$ for
all $v\in V$, then the level of protection $\tau$ is not achievable for an
arbitrarily large number of patrollers (if $p=1$, the condition is restricted
to $Q_{v}\leq 1$). Otherwise, the number of patrollers needed to achieve the
level of protection $\tau$ is bounded from below by ${\left\lceil\sum_{v\in
V,Q(v)>0}Q_{v}/d(v)\right\rceil}$, where the value of each $Q_{v}$ is obtained
by solving the system.

###### Proof.

The proof is based on a careful analysis of “uniform coverage” of all vertices
with $k$-patrollers reflecting the importance of individual vertices.
Intuitively, $Q_{v}$ stands for the expected number of visits to $v$ in
subsequent $d(v)$ steps.

Let us fix a game structure $\mathcal{G}$ and a number of patrollers
$k\in\mathbb{N}$. Let $\eta$ be an optimal strategy for $k$ patrollers (the
existence of $\eta$ follows by standard arguments). Let $T=\prod_{v\in
V}d(v)$. For all $1\leq i\leq T$ and $v\in V$, let $P_{i}(v)$ be the
probability of $v$ appearing in the $i$-th subset visited by a walk when the
Defender commits to $\eta$. Note that for each $1\leq i\leq T$, we have
$\sum_{v\in V}P_{i}(v)=k$ as there are $k$ patrollers assigned in each round.
Hence, the sum of all $P_{i}(v)$’s (for all $1\leq i\leq T$ and $v\in V$) is
equal to $T\cdot k$.

For every $v\in V$ and every $0\leq j<T$, where $j$ is a multiple of $d(v)$,
let $\pi_{v,j}$ be the Attacker’s strategy such that $\pi_{v,j}(w)=v$ for
every history $w$ of length $j$. A trivial calculation reveals

$\mathit{Lev}(\eta,\pi_{v,j})\ =\
\alpha_{\max}-\alpha(v)\cdot\prod_{i=1}^{d(v)}\left(1-p\cdot
P_{j+i}(v)\right)$ (1)

Further, let $Q_{v,j}=\sum_{i=1}^{d(v)}P_{j+i}(v)$. By analyzing Equation (1),
it follows the $\mathit{Lev}(\eta,\pi_{v,j})$ is maximized if the values
$P_{j+i}(v)$ satisfy

  * •

$P_{j+i}(v)=1$ for all $i=\\{1,\dots,{\left\lfloor Q_{v,j}\right\rfloor}\\}$,

  * •

$P_{j+i}(v)=Q_{v,j}-{\left\lfloor Q_{v,j}\right\rfloor}$ for $i={\left\lfloor
Q_{v,j}\right\rfloor}+1$, and

  * •

$P_{j+i}(v)=0$ for all $i>{\left\lfloor Q_{v,j}\right\rfloor}+1$.

The right-hand side of Equation (1) can then be rewritten to
$\alpha_{\max}-\alpha(v)\cdot(1-p)^{\left\lfloor
Q_{v,j}\right\rfloor}\cdot(1-p\cdot(Q_{v,j}-{\left\lfloor
Q_{v,j}\right\rfloor}))$. In the best case, when all $P_{i}(v)$ were
distributed optimally by $\eta$, all $Q_{v,j}$ are the _same_ for a given
$v\in V$, and the same level of protection $\varrho$ is achieved for every
vertex $v$. Thus, we use just $Q_{v}$ instead of $Q_{v,j}$ and obtain the
system $\mathcal{L}_{\mathcal{G}}$.

Further, the sum of all $P_{i}(v)$’s, for all $1\leq i\leq T$ and $v\in V$, is
equal to $T\cdot k$ (see above). By reordering the summands, the sum can be
rewritten into $\sum_{v\in V}T/d(v)\cdot Q_{v}$. Thus, we obtain $k=\sum_{v\in
V}Q_{v}/d(v)$. Observe that $0\leq Q_{v}\leq d(v)$, and if $p=1$, we have that
$0\leq Q_{v}\leq 1$, because then it does not make any sense to visit the same
vertex more than once.

Let us note that when solving the systems considered in Theorem 1, it may
happen that some $Q_{v}$’s become negative. This happens if (and only if) the
importance of some vertices is so low that even if the patrollers do not visit
them at all, they are still protected better than the other vertices (this
also explains why the sum $\sum_{v\in V,Q(v)>0}Q_{v}/d(v)$ is taken only over
positive $Q(v)$’s). The system of Theorem 1(b) may have no eligible solution
in situations when $p$ is so small that the protection $\tau$ is not
achievable even if each $v$ is visited with probability one in every step. If
$p=1$, no eligible solution is induced only by $\tau>\alpha_{\max}$. ∎

##  4 Modular strategies

In this section, we introduce _modular strategies_ and the associated
_compositional principle_ which are the cornerstones of our strategy synthesis
algorithm.

######  Definition 1.

Let $\mathcal{G}=(V,d,\alpha,p)$ be a game structure, and $c_{\mathcal{G}}$
the least common multiple of all $d(v)$ where $v\in V$. A Defender’s strategy
$\eta$ for $\mathcal{G}$ is _modular_ if for every $h\in\mathcal{H}$, the
distribution $\eta(h)$ depends only on
$\ell\mathrm{~{}mod~{}}c_{\mathcal{G}}$, where $\ell$ is the length of $h$.

Hence, a modular strategy “ignores” the precise structure of a history and
takes into account only $\ell\mathrm{~{}mod~{}}c_{\mathcal{G}}$. At first
glance, this looks like a severe restriction substantially limiting the
efficiency of modular strategies. Surprisingly, this intuition turns out to be
largely incorrect. As we shall see in Section 6.1, the level of protection
achievable by modular strategies approaches and in some cases even _matches_
the upper bound of Theorem 1 which proves their _(sub)optimality_ among
_general_ strategies. Also note that modular strategies require only a bounded
counter as auxiliary memory, which makes them easy to implement. To simplify
our notation, we formally consider modular strategies as functions
$\eta:\mathbb{N}_{0}\rightarrow\Delta(V^{\langle k\rangle})$, where
$\eta(\ell)$ depends just on $\ell\mathrm{~{}mod~{}}c_{\mathcal{G}}$.

The main advantage of modular strategies is their _compositionality_. A
modular strategy for a given game structure $\mathcal{G}$ can be constructed
by decomposing $\mathcal{G}$ into pairwise disjoint substructures
$\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$, computing modular strategies for
these substructures recursively, and then combining them into a modular
strategy for $\mathcal{G}$. The algorithm presented in Section 6 works in this
way. Now we describe the composition step in greater detail.

Let $\mathcal{G}=(V,d,\alpha,p)$, and let $k$ be the number of patrollers
protecting $\mathcal{G}$. Assume that we already managed to decompose
$\mathcal{G}$ into smaller disjoint substructures
$\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$, where
$\mathcal{G}_{i}=(V_{i},d|_{V_{i}},\alpha|_{V_{i}},p)$, so that, for all
$n\leq k$ and $i\leq m$, an efficient modular strategy $\eta_{i}[n]$ for
$\mathcal{G}_{i}$ and $n$ patrollers together with $\mathit{Lev}(\eta_{i}[n])$
can already be efficiently computed. In order to combine the constructed
strategies into a strategy for $\mathcal{G}$, we need to solve the following
problems:

  * •

How to assign the $k$ available patrollers to
$\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$ ?

  * •

How to compose the modular strategies constructed for
$\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$ into a modular strategy $\eta$ for
$\mathcal{G}$?

Assigning patrollers to substructures. Clearly, the number of patrollers
assigned to $\mathcal{G}_{i}$ should not exceed $|V_{i}|$. It is also clear
that if $k$ is smaller than $m$, the assignment cannot be deterministic,
because otherwise some substructures would remain completely unprotected, and
the Attacker could attack them without any risk (recall the Attacker knows the
Defender’s strategy). So, we need to assign the $k$ patrollers to
$\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$ _randomly_ in general. Formally, an
_assignment_ for $k$ patrollers and $\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$
is a probability distribution $\beta$ over the set of all _eligible_
allocations $\vec{\kappa}\in\mathbb{N}_{0}^{m}$, where the components of
$\vec{\kappa}$ sum up to $k$ and $\vec{\kappa}_{i}\leq|V_{i}|$ for all $i\leq
m$.

Composing strategies constructed for substructures. Assume we already
constructed a suitable assignment $\beta$ for $k$ patrollers and
$\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$. By our assumption, for all $n\leq k$
and $i\leq m$, an efficient modular strategy $\eta_{i}[n]$ for
$\mathcal{G}_{i}$ and $n$ patrollers can already by constructed. Our task is
to construct a suitable modular strategy $\eta$ for $\mathcal{G}$ and $k$
patrollers. For every $\ell\in\mathbb{N}_{0}$, the outcome of $\eta(\ell)$ is
determined as follows:

  * •

First, some eligible allocation $\vec{\kappa}\in\mathbb{N}_{0}^{m}$ is
selected randomly according to $\beta$ (independently of $\ell$).

  * •

Then, for each $i\in\\{1,\dots,m\\}$, we independently select a
$\vec{\kappa}_{i}$-subset $U_{i}$ of $V_{i}$ according to
$\eta_{i}[\vec{\kappa}_{i}](\ell)$. Thus, we obtain a $k$-subset
$U_{1}\cup\cdots\cup U_{m}$ of $V$, which is the (random) outcome of
$\eta(\ell)$.

Observe that the above definition makes a good sense because all
$\eta_{i}[\vec{\kappa}_{i}]$ are _modular_ strategies555If
$\eta_{i}[\vec{\kappa}_{i}]$ were general strategies, they could not be
combined in such a simple way, because in each step, a different number of
patrollers (including zero) can be assigned to a given $\mathcal{G}_{i}$, and
hence the history produced by $\eta$ would not have to contain a valid history
of $\eta_{i}[\vec{\kappa}_{i}]$. So, it would not be clear how to simulate
$\eta_{i}[\vec{\kappa}_{i}]$..

Hence, a concrete strategy synthesis algorithm based on the introduced
decomposition principle (such as the one presented in Section 6) must
implement the following:

  * •

a _decomposition procedure_ which, for given $k$ and $\mathcal{G}$, either
decomposes $\mathcal{G}$ into disjoint substructures to be solved recursively,
or computes a suitable modular strategy for $\mathcal{G}$ and $k$ patrollers;

  * •

an _assignment procedure_ which, for given $k$ and
$\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$, computes an assignment for $k$
patrollers and $\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$.

These procedures may reflect different decomposition tactics apt for specific
classes of instances.

##  5 Examples

In Section 6, we design a concrete decomposition algorithm based on the
presented method and evaluate the quality of the constructed strategies. To
get a preliminary intuition about its functionality, and to illustrate the
notions introduced above, we present two simple examples.

######  Example 1.

Let us consider $\mathcal{G}$ where $V=\\{v_{1},v_{2},v_{3}\\}$, $d(v_{i})=2$
and $\alpha(v_{i})=1$ for all $v_{i}$’s, and $p=1$. We aim at protecting
$\mathcal{G}$ with just one patroller. This appears like a trivial task—we
have three equally important vertices with attack length $2$, so a naive
attempt is to choose the visited vertex uniformly at random in each step. The
level of protection achieved in this way is equal to $1/3+2/3\cdot 1/3=5/9$
(if a given vertex is attacked, it is visited in the first step with
probability $1/3$, and if this does not happen (with probability $2/3$), there
is another chance of $1/3$ in the second step).

If we try to “improve” the above strategy naively by selecting randomly only
between the two vertices not visited in the previous step, the level of
protection becomes _worse_. If, say, $v_{1}$ is visited in step $i$, then in
step $i+1$ we choose just between $v_{2}$ and $v_{3}$, and in step $i+2$ we
choose $v_{1}$ with probability $1/2$. So, the achieved level of protection is
actually equal to $1/2$.

So, can we do better than $5/9$? If so, what is the _best_ achievable level of
protection? Given the simplicity of $\mathcal{G}$, the answers are perhaps
surprising.

The decomposition algorithm of Section 6 starts by splitting $V$ into
$V_{1}=\\{v_{1},v_{2}\\}$, $V_{2}=\\{v_{3}\\}$, and constructing two trivial
Defender’s strategies $\eta_{1}$ and $\eta_{2}$ for one patroller in $V_{1}$
and $V_{2}$. The strategy $\eta_{1}$ selects $v_{1}$/$v_{2}$ with probability
one at all even/odd steps, and $\eta_{2}$ always selects $v_{3}$. To combine
$\eta_{1}$ and $\eta_{2}$, we need to fix an appropriate assignment $\beta$
for the two eligible vectors $(1,0),(0,1)$. That is, we need to determine
$x\in[0,1]$ such that $\beta(1,0)=x$ and $\beta(0,1)=1-x$. Now what is an
appropriate value for $x$? The resulting strategy $\eta$ protects the vertices
$v_{1},v_{2}$ with probability $x$, but the vertex $v_{3}$ is protected with
probability $1-x^{2}$ (in order to miss $v_{3}$, we need to miss it twice,
each time with probability $1-(1-x)=x$). Ideally, $\eta$ should protect all
vertices equally well, which is satisfied when $x=1-x^{2}$. This yields
$x=(\sqrt{5}-1)/2\approx 0.618>5/9$. Thus, the composed strategy $\eta$
achieves the level of protection equal to $(\sqrt{5}-1)/2$, and one can show
that this is _optimal_ 666The argument is non-trivial and specific to this
instance.. This also shows that the best achievable level of protection can be
_irrational_ , even for very simple game structures.∎

######  Example 2.

Let $\mathcal{G}$ be a game structure with six vertices
$V=\\{v_{1},\ldots,v_{6}\\}$ such that $d(v_{i})=2$ for all $v_{i}$’s,
$\alpha(v_{1})=\alpha(v_{2})=6$, $\alpha(v_{3})=\alpha(v_{4})=3$,
$\alpha(v_{5})=\alpha(v_{6})=2$, and $p=1$. We aim at constructing a
Defender’s strategy for two patrollers. The algorithm of Section 6 splits $V$
into the subsets $V_{1}=\\{v_{1},v_{2}\\}$, $V_{2}=\\{v_{3},v_{4}\\}$,
$V_{3}=\\{v_{5},v_{6}\\}$. For every $i\in\\{1,2,3\\}$, a trivial modular
strategy $\eta_{i}$ for $\mathcal{G}_{i}$ and one patroller is constructed,
where $\eta_{i}$ visits one vertex of $V_{i}$ at all even steps, and the other
vertex of $V_{i}$ at all odd steps. Now, the strategies
$\eta_{1},\eta_{2},\eta_{2}$ are combined using an assignment $\beta$ which
assigns at most one patroller to each $\mathcal{G}_{i}$, i.e.,
$\beta(1,1,0)=x$, $\beta(1,0,1)=y$, and $\beta(0,1,1)=z$, where $x+y+z=1$.
Observe that the protection for the vertices of $V_{1}$, $V_{2}$, and $V_{3}$
achieved by $\eta$ is equal to

$6-(1-x-y)\cdot 6,\quad 6-(1-x-z)\cdot 3,\quad 6-(1-y-z)\cdot 2,$

respectively. Ideally, the above values should be equal. Thus, we obtain
$x=1/2$, $y=1/3$, and $z=1/6$. The level of protection achieved by the
resulting strategy $\eta$ for $\mathcal{G}$ is equal to $5$, which matches the
upper bound of Theorem 1, i.e., $\eta$ is _optimal_.∎

##  6 A Strategy Synthesis Algorithm

In this section we design and evaluate a concrete strategy synthesis algorithm
based on the compositional method presented in Section 4. This algorithm is
particularly apt for game structures where large subsets of vertices share the
same attack length and the same importance weight. This applies to, e.g.,
surveillance systems and remote software protection systems777The number of IP
camers or software modules can easily reach hundreds of millions, while the
time needed to complete an intrusion or a software update typically ranges
over a small interval of discretized time values. Similarly, the importance of
a target usually ranges over a small set of discrete levels. discussed in
Section 1.

Decomposition procedure. For a given $\mathcal{G}=(V,d,\alpha,p)$, the
decomposition starts by splitting the vertices of $V$ into pairwise disjoint
subsets $U_{D,\tau}$ consisting of all $v\in V$ such that $d(v)=D$ and
$\alpha(v)=\tau$ (for all $D$’s and $\tau$’s in the range of $d$ and $\alpha$,
respectively). Then, each $U_{D,\tau}$ is further split into
$\lceil|U_{D,\tau}|/D\rceil$ pairwise disjoint subsets of size precisely $D$
(these are called _full_), and possibly one extra set with
$(U_{D,\tau}~{}\textrm{mod}~{}D)$ elements (if $D$ does not divide
$|U_{D,\tau}|$). These sets, constructed for all eligible $D$’s and $\tau$’s,
are called the _basic sets of $\mathcal{G}$_, and they are not decomposed any
further. Note that the decomposition of $\mathcal{G}$ into basic sets is
independent of the number of patrollers assigned to protect $\mathcal{G}$.

For every basic set $U=\\{v_{0},\ldots,v_{q-1}\\}$ and every $k$, we need to
compute a modular strategy $\mu$ for $U$ and $k$ patrollers. Recall that all
vertices of $U$ have the same importance $\tau$ and the same attack length
$D$, where $q\leq D$. Let us first consider the simpler case when $q$ divides
$D$. Imagine there are $k$ tokens, initially put on the vertices
$v_{0},\ldots,v_{k-1}$, which are then moved simultaneously around a circle
formed by the vertices of $U$, where the successor of $v_{i}$ is
$v_{(i+1)~{}\textrm{mod}~{}D}$. That is, after $\ell$ steps, the first token
resides at $v_{\ell~{}\textrm{mod}~{}D}$, and the other tokens reside at the
next $k-1$ vertices of the circle. The strategy $\mu(\ell)$ deterministically
selects the $k$-tuple of vertices occupied by the tokens after $\ell$ steps.
Note that each token visits each vertex precisely $D/q$ times in $D$
consecutive steps.

Now consider the general case when $q$ does not necessarily divide $D$. In the
first $\lfloor D/q\rfloor\cdot q$ steps, $\mu$ simulates $k$ tokens moving
simultaneously around a circle similarly as above. In the remaining
($D~{}\textrm{mod}~{}q$) steps, a $k$-subset of $U$ is chosen uniformly at
random (independently in each step). Formally, for every
$\ell\in\\{0,\ldots,D{-}1\\}$, we have the following:

  * •

if $\ell<\lfloor D/q\rfloor\cdot q$, then $\mu(\ell)$ returns
$\\{v_{j_{0}},\ldots,v_{j_{k-1}}\\}$ with probability one, where
$j_{n}=(\ell+n)~{}\textrm{mod}~{}q$ for all $n\in\\{0,\ldots,k{-}1\\}$;

  * •

otherwise, $\mu(\ell)$ returns a $k$-subset of $U$ chosen uniformly at random.

Assignment procedure. This is the most advanced part of our algorithm. We need
to construct an assignment $\beta$ for $k$ patrollers and the basic sets. We
aim to construct $\beta$ so that the number of patrollers assigned to a given
basic set $U$ is either $K_{U}$ or $K_{U}+1$, where $K_{U}\in\mathbb{N}_{0}$
is a suitable constant depending only on $k$, the attack length, importance
level, and the number of vertices of $U$. The reason is that a wider
variability in the number of patrollers assigned to $U$ would actually
_decrease_ 888This claim follows from the structure of modular strategies
constructed for basic sets, and it can be proven rigorously. the protection
achieved for basic sets.

Now we explain how to compute the constant $K_{U}$ and the probability
$\lambda_{U}$ of sending precisely $K_{U}+1$ patrollers to $U$.

Let us fix a basic set $U=\\{v_{1},\ldots,v_{q}\\}$ where $\alpha(v_{i})=\tau$
and $d(v_{i})=D$ for all $v_{i}\in U$. If $\beta$ sends $K_{U}$ patrollers to
$U$ with probability $(1-\lambda_{U})$ and $K_{U}+1$ patrollers with
probability $\lambda_{U}$, then the expected number of patrollers sent to $U$,
denoted by $E_{U}$, is equal to $K_{U}+\lambda_{U}$. Furthermore, the
protection achieved for the vertices of $U$ is given by:

$\alpha_{\max}-\tau\cdot(1-p)^{K_{U}\cdot\lfloor
D/q\rfloor}\cdot(1-p\cdot\lambda_{U})^{\lfloor
D/q\rfloor}\cdot(1-p\cdot(K_{U}+\lambda_{U})/q)^{(D~{}\textrm{mod}~{}q)}$ (2)

Expression (2) is obtained by a straightforward calculation omitted in here
(possible subexpressions of the form $0^{0}$ are interpreted as $1$). Since we
wish to protect all basic sets equally well, the above expression should
produce the _same_ value for all $U\in W$. Hence, we can consider a system of
equations stipulating that the above expressions are equal for all $U$, and
the sum of all positive $E_{U}$’s is equal to $k$. The values for $K_{U}$ and
$\lambda_{U}$ are obtained by solving this system. Observe that (2) is
parameterized by _two_ unknowns $K_{U}$ and $\lambda_{U}$, so we have more
unknowns than equations. This is overcome by observing that $K_{U}=\lfloor
E_{U}\rfloor$ and $\lambda_{U}=E_{U}-\lfloor E_{U}\rfloor$, which allows to
use just _one_ variable $E_{U}$ instead of $K_{U}$ and $\lambda_{U}$.
Furthermore, it may happen that a solution contains some negative $E_{U}$’s,
which indicates that the importance of the vertices in $U$ is so low that $U$
is protected better than the other basic sets even if zero patrollers are
assigned to $U$. In this case, we simply remove $U$ from $\mathcal{G}$ and
restart the algorithm.

###  6.1 Evaluating the constructed strategies

For every Defender’s strategy $\eta$ for $k$ patrollers, the _relative
deviation of $\eta$ from optimal strategy_, denoted by $\mathit{Dev}(\eta)$,
is defined by $(\mathit{Lev}_{k}-\mathit{Lev}(\eta))/\mathit{Lev}(\eta)$.
Hence, $\eta$ is optimal iff $\mathit{Dev}(\eta)=0$.

First, let us note that when all basic sets of $\mathcal{G}$ are full, then
the achieved level of protection matches the upper bound of Theorem 1, i.e.,
the strategy constructed by our algorithm is _provably optimal_. For every
game structure $\mathcal{G}$, there are two “surrounding” game structures
obtained by decreasing/increasing the number of vertices in each $U_{D,\tau}$
to the nearest multiple of $D$, for which our algorithm produces optimal
strategies. With an increasing number of vertices, the levels of protection
achieved for the surrouding game structures are closer and closer, which
implies that $\mathit{Dev}(\eta)$ approaches zero. For a given $\delta>0$, one
can easily compute a threshold such that, for every game structure where the
number of vertices exceeds the threshold, the strategy $\eta$ constructed by
our algorithm satisfies $\mathit{Dev}(\eta)<\delta$. Hence, our algorithm
_provably_ produces strategies which are either optimal or very close to
optimal, and this claim does _not_ require further experimental evidence. The
aim of our experiments is to demonstrate that the time needed to solve the
constructed system of equations is low (using Maple), and also to show that
the protection achieved by our strategies is substantially better than the
protection achieved by naively constructed strategies.

More concretely, we consider a surveillance system with three types of
targets, where processing one image takes $0.1$ sec, an on-going intrusion is
detected with probability $0.7$, the time needed to complete an intrusion is
either $20$ secs, $2$ mins, or $15$ mins, and the target values are $100000,
$130000, and $400000, respectively. We analyze large instances where the
number of targets of each type is $7000000\cdot x$, $500000\cdot x$, and
$300000\cdot x$, respectively, where the $x$ ranges from $1$ to $3$ with a
step $0.01$. Hence, the total number of analyzed game structures is $200$ and
the largest one has more than $23$ million vertices. The number of patrollers
is set to $6000$. Since the time needed to compute $\eta$ was always
negligible (the constructed systems of equations were solved by Maple in less
than a second on an average PC), we do not report the running time details.
The achieved levels of protection are plotted in Figure 1. The levels of
protection achieved by $\eta$ strategies differ from the theoretical upper
bound by less than one dollar (for all instances). When we compare these
strategies against naively constructed strategies $\sigma$, where in each
round, the patrollers are identically distributed among the vertices so that
all vertices are protected equally well, the difference between the levels of
protection achieved by $\sigma$ strategies and the theoretical upper bound
ranges between $\$157$ and $\$740$.

In Figure 2, we show the number of patrollers needed to achieve a given level
of protection bounded by $270000$. Here we assume a fixed game with the same
parameters as above where $x=1$, i.e., we have $7000000$, $500000$, and
$300000$ vertices of the three types. The number of patrollers required by
$\eta$ differs from the theoretical bound by at most one, while the naive
strategies $\sigma$ need about $125\%$ of this amount on average. In the plot
of Figure 2, the theoretical lower bound on the number of patrollers and the
number of patrollers required by $\eta$ are indistinguishable.

$1$$1.5$$2$$2.5$$3$$310{,}000$$308{,}000$$306{,}000$$304{,}000$$x$ such that
the numbers of vertices are $7000000\cdot x$, $500000\cdot x$, and
$300000\cdot x$level of protection by 6000 patrollersbound of Theorem
1strategies $\eta$strategies $\sigma$ Figure 1: The level of protection
achieved by strategies.
$50{,}000$$100{,}000$$150{,}000$$200{,}000$$250{,}000$$10$$20$$30$$40$$50$level
of protectionrequired number of patrollersbound of Theorem 1strategies
$\eta$strategies $\sigma$ Figure 2: Achieving a given level of protection.

##  7 Conclusions

The presented method can also be extended to more general models. For example,
adapting our algorithm to a generalized model where $p$ is a _function_ from
$V$ to $(0,1]$ is easy—the compositional principle stays the same, and in the
algorithm, the equations used to compute an optimal assignment for the
patrollers are slightly adjusted. Another direction for future research is to
consider Attackers with limited capabilities.

The algorithm of Section 6 works well for game structures where the range of
$d$ and $\alpha$ is relatively small compared to the number of vertices. For
other classes of game structures, one may possibly develop other algorithms,
but some decomposition principle similar to ours seems _unavoidable_ when the
number of vertices reaches a certain threshold. Hence, we believe that the
presented approach may trigger the development of the whole spectrum of
decomposition techniques applicable to Internet security problems.

## References

  * Abaffy et al. (2014) M. Abaffy, T. Brázdil, V. Řehák, B. Bošanský, A. Kučera, and J. Krčál.  Solving adversarial patrolling games with bounded error.  In Proceedings of AAMAS 2014, pages 1617–1618, 2014.
  * Agmon et al. (2008a) N. Agmon, S. Kraus, and G. Kaminka.  Multi-robot perimeter patrol in adversarial settings.  In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA2008), pages 2339–2345. IEEE, 2008.
  * Agmon et al. (2008b) N. Agmon, V. Sadov, G. Kaminka, and S. Kraus.  The impact of adversarial knowledge on adversarial planning in perimeter patrol.  In Proceedings of AAMAS 2008, pages 55–62, 2008.
  * Almeida et al. (2004) A. Almeida, G. Ramalho, H. Santana, P. Tedesco, T. Menezes, V. Corruble, and Y. Chevaleyre.  Recent advances on multi-agent patrolling.  In Advances in Artificial Intelligence – SBIA 2004, volume 3171 of LNCS, pages 474–483. Springer, 2004.
  * Basilico et al. (2009a) N. Basilico, N. Gatti, and F. Amigoni.  Leader-follower strategies for robotic patrolling in environments with arbitrary topologies.  In AAMAS, pages 57–64, 2009.
  * Basilico et al. (2009b) N. Basilico, N. Gatti, T. Rossi, S. Ceppi, and F. Amigoni.  Extending algorithms for mobile robot patrolling in the presence of adversaries to more realistic settings.  In WI-IAT, pages 557–564, 2009.
  * Basilico et al. (2010) N. Basilico, N. Gatti, and F. Villa.  Asynchronous Multi-Robot Patrolling against Intrusion in Arbitrary Topologies.  In AAAI, 2010.
  * Basilico et al. (2012) N. Basilico, N. Gatti, and F. Amigoni.  Patrolling security games: Definitions and algorithms for solving large instances with single patroller and single intruder.  AI, 184–185:78–123, 2012.
  * Basilico et al. (2016a) N. Basilico, A. Lanzi, and M. Monga.  A security game model for remote software protection.  In Proceedings of ARES 2016, pages 437–443, 2016.
  * Basilico et al. (2016b) N. Basilico, G. De Nittis, and N. Gatti.  A security game combining patrolling and alarm-triggered responses under spatial and detection uncertainties.  In Proceedings of AAAI 2016, pages 404–410, 2016.
  * Bosansky et al. (2011) B. Bosansky, V. Lisy, M. Jakob, and M. Pechoucek.  Computing Time-Dependent Policies for Patrolling Games with Mobile Targets.  In AAMAS, 2011.
  * Bosansky et al. (2012) B. Bosansky, O. Vanek, and M. Pechoucek.  Strategy Representation Analysis for Patrolling Games.  In AAAI Spring Symposium, 2012.
  * Ceccato and Tonella (2011) M. Ceccato and P. Tonella.  Codebender: Remote software protection using orthogonal replacement.  IEEE Software, 28(2):28–34, 2011.
  * Collberg et al. (2012) C. Collberg, S. Martin, J. Myers, and J. Nagra.  Distributed application tamper detection via continuous software updates.  In Proceedings of the 28th Annual Computer Security Applications Conference, pages 319–328. ACM Press, 2012.
  * Cotton (2015) B. Cotton.  Enhancing a city’s ability to plan, protect and manage with intelligent video analytics.  Technical report, A Frost & Sullivan White Paper, 2015.
  * de Cote et al. (2013) E. Munoz de Cote, R. Stranders, N. Basilico, N. Gatti, and N. Jennings.  Introducing alarms in adversarial patrolling games: extended abstract.  In AAMAS, pages 1275–1276, 2013.
  * Fang et al. (2013) F. Fang, A.X. Jiang, and M. Tambe.  Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources.  In AAMAS, 2013.
  * Jain et al. (2010) M. Jain, E. Karde, C. Kiekintveld, F. Ordóñez, and M. Tambe.  Optimal defender allocation for massive security games: A branch and price approach.  In Workshop on Optimization in Multi-Agent Systems at AAMAS, 2010\.
  * Kempe et al. (2018) D. Kempe, L.J. Schulman, and O. Tamuz.  Quasi-regular sequences and optimal schedulers for security games.  In Proceedings of SODA 2018. SIAM, 2018.
  * Kiekintveld et al. (2009) C. Kiekintveld, M. Jain, J. Tsai, J. Pita, F. Ordóñez, and M. Tambe.  Computing optimal randomized resource allocations for massive security games.  In Proceedings of AAMAS 2009, pages 689–696, 2009.
  * Kučera and Lamser (2016) A. Kučera and T. Lamser.  Regular strategies and strategy improvement: Efficient tools for solving large patrolling problems.  In Proceedings of AAMAS 2016, pages 1171–1179, 2016.
  * Pita et al. (2008) J. Pita, M. Jain, J. Marecki, F. Ordónez, C. Portway, M. Tambe, C. Western, P. Paruchuri, and S. Kraus.  Deployed ARMOR protection: The application of a game theoretic model for security at the Los Angeles Int. Airport.  In Proceedings of AAMAS 2008, pages 125–132, 2008.
  * Redmon et al. (2016) J. Redmon, S.K. Divvala, R.B. Girshick, and A. Farhadi.  You only look once: Unified, real-time object detection.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, pages 779–788. IEEE, 2016.
  * Tsai et al. (2009) J. Tsai, S. Rathi, C. Kiekintveld, F. Ordóñez, and M. Tambe.  IRIS—a tool for strategic security allocation in transportation networks categories and subject descriptors.  In Proceedings of AAMAS 2009, pages 37–44, 2009.
  * Yin et al. (2010) Z. Yin, D. Korzhyk, C. Kiekintveld, V. Conitzer, and M. Tambe.  Stackelberg vs. Nash in security games: Interchangeability, equivalence, and uniqueness.  In AAMAS, pages 1139–1146, 2010.