untitled

c OR 2015 5 [1] OR 1. 2001 9.11 Homeland Security (OR) [2] OR 1972 Chaiken and Larson [3] (1) (2) (3) (4) (5) OR 68 Olson and Wright [4] 239 8686 1 10 20 hozaki@nda.ac.jp Koopman [5] Homeland Security (Stackelberg game) Homeland Security Patrolling security game (PSG) Stackelberg security game (SSG) (Security game) PSG SSG Olson and Wright 2. 226 28 Copyright c by ORSJ. Unauthorized reproduction of this article is prohibited.

Garnaev et al. [6] N x 1 =(x 1 1,...,x 1 N) y =(y 1,...,y N ) C i i v i(x 1, y) u 1 A(x 1, y) = N i=1 Civi(x1, y) x 2 y u 2 A(x 2, y) 1 2 q, 1 q u D(y, (x 1, x 2 )) = {qu 1 A(x 1, y)+(1 q)u 2 A(x 2, y)} x 1, x 2, y x 1, x 2, y u 1 A(x 1, y ) u 1 A(x 1, y ), u 2 A(x 2, y ) u 2 A(x 2, y ), U D(y, (x 1, x 2 )) U D(y, (x 1, x 2 )). u k A(x k, y) u 1 A(x 1, y) = N C ix 1 i (1 d iy i), (1) i=1 u 2 A(x 2, y) =D N x 2 i (1 d iy i), (2) i=1 C i = heipi g EjJ, d σe 2 i = σe 2 + geij P i i h Ei σ E J, g Ej D x k, y (1), (2) Yang et al. [7] SSG SSG Garnaev et al Yang et al 2 [8] Basilico et al. [9] PSG Olson and Wright SSG Tsai et al. [10] [11] [12 16] [1] 2007 ARMOR (Assistant for randomized monitoring over routes) 2009 IRIS (Intelligent randomization in scheduling) ARMOR DOBSS (Decomposed optimal Bayesian Stackelberg solver) 2016 4 Copyright c by ORSJ. Unauthorized reproduction of this article is prohibited. 29 227

400 GUARDS (Game-theoretic unpredictable and randomly deployed security) PROTECT (Port resilience operational/tactical enforcement to combat terrorism) Tambe [17] 3. 1 [18] Hohzaki et al. [19] 1 2 s t p s(t) j q j(i),i=1,...,l j (δ {1, 0}) (2) (d) (3) (α) δα/d 2 1 p s q j q j 1 35 7 1 1 0 1 3 2 0.0962 5 5 3 0.2118 8 8 4 0.2118 11 17 5 0.4281 19 19 6 0.5801 22 22 7 0.5801 24 1 1 t j f j(t) f j 1( ) f j( ) { } f j(t) =min z f j 1(z)+D j 1(z)+E j (t) (3) D j 1(z) z j 1 228 30 Copyright c by ORSJ. Unauthorized reproduction of this article is prohibited.

j E j (t) j t CCD (3) f j(t) j t f j(t) =minmin i z f i(z)+d j i (z)+ej (t) { } D j i (z) j i z j f j(t) j t [20] E2C AWACS (Airborne warning and control system) (P TR) (G A) (λ) (σ) (R) P TRG 2 Aλ 2 σ/(4π) 3 R 4 3 (3) z 2 6 IR1 IR6 IR4 4 PR1 PR4 FR 2016 4 Copyright c by ORSJ. Unauthorized reproduction of this article is prohibited. 31 229

2 PR3 PR4 0.725 0.275 IR4 IR5 0.309 0.691 IR4 IR5 4. Hohzaki and Chiba [21] 2 2 (Attrition game) 2 [22] N A H h H R0 h e 1 d h e Ω h S s S B0 s s U(s) h f(h) e h s γe hs h x s y y f e(x, y) =max{0, x γ hs e y} (4) 0 (4) 230 32 Copyright c by ORSJ. Unauthorized reproduction of this article is prohibited.

2 h H l π h (l) π h = {π h (l),l Ω h } s e ye s y s = {ye,e s A} s g(s) E l l El e l e h l s y s e Rhs(l, I y s )= d h e max 0,Rh 0 γ hs e ys e (5) e E l e E e l g(s) h π h Rh(l, I (g,y)) = g(s)rhs(l, I y s ) s S Rh(π I h, (g,y)) = π h (l)rh(l, I (g,y)) l Ω h (g,y)={(g(s), y s ),s S} h max πh Rh(π I h, (g,y)) π h f(h) h H f(h)maxπ h RI h(π h, (g,y)) (g,y) {π h,h H} (g,y) R I (π,(g,y)) = f(h) π h (l) g(s)rhs(l, I y s ) h H l Ω h s S 2 (5) R II (π, (g,y)) = f(h) π h (l) h H l Ω h max dh e R0 h γ hs e g(s)ys e, e E l s S e E l e d h e R0 h γ hs e g(s)ys e s S e E e l d h e d h e e 3 [23] 15 16 H = {1, 2} h =1 2 5, 6, 7, 8 1 14 h =2 2016 4 Copyright c by ORSJ. Unauthorized reproduction of this article is prohibited. 33 231

4 B 1 0 5 B 1 0 3 1 13, 14, 15 2 4 9 14 4 1 2 f(1) = 0.8, f(2) = 0.2 R0 1 =5,R0 2 =10 S = {1, 2} 2 s =1 s =2 U(2) = 0.3 γe hs s =2 γe hs B0,B 1 0 2 s = 2 s = 1 2 g(s) s C g(1)b0 1 +2g(2)B0 2 1 s =1 B0 1 s =2 γe hs s =1 g(2) = 0.3 s =2 B0 1 B0 2 (C 0.7B0 1 )/(2 0.3) C =20 4 5 B0 1 ye s 4 s =1 2 B0 1 =9, B0 2 =22.8 C 5 s =1 1 s =2 B0 1 B 0 1 12, 13 C (1) (2) 232 34 Copyright c by ORSJ. Unauthorized reproduction of this article is prohibited.

(i) γe hs (ii) d h e (iii) (3) 5. 4 [1] 60, pp. 266 273, 2015. [2] J. Herrmann (ed.), Handbook of Operations Research for Homeland Security, Springer Science & Business Media, 2012. [3]J.M.ChaikenandR.C.Larson, Methodsforallocating urban emergency units: A survey, Management Science, 19, pp. 110 130, 1972. [4] D. G. Olson and G. P. Wright, Models for allocating police preventive patrol effort, Operational Research Quarterly, 26, pp. 703 715, 1975. [5] B. O. Koopman, Search and screening, Operations Evaluation Group Report No. 56, 1946. [6] A. Garnaev, M. Baykal-Gursoy and H. V. Poor, Incorporating attack-type uncertainty into network protection, IEEE Transactions on Information Forensics and Security, 9, pp. 1278 1287, 2014. [7] R. Yang, C. Kiekintveld, F. Ordonez, M. Tambe and R. John, Improving resource allocation strategies against human adversaries in security games: An extended study, Artificial Intelligence, 195, pp. 440 469, 2013. [8] A. R. Washburn, TPZS applications: Blotto games, Wiley Encyclopedia of Operations Research and Management Science, 7, pp. 5504 5511, 2011. [9] N. Basilico, N. Gatti and F. Amigoni, Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder, Artificial Intelligence, 184, pp. 78 123, 2012. [10] J. Tsai, Z. Yin, J. Y. Kwak, D. Kempe, C. Kiekintveld and M. Tambe, Urban security: Gametheoretic resource allocation in networked physical domains, In Proceedings of the 24th AAAI Conference on Artificial Intelligence, pp. 881 886, 2010. [11] 2015 pp. 4 5, 2015. [12] J. Salmeron, R. K. Wood and R. Baldick, Analysis of electric grid security under terrorist threat, IEEE Transactions on Power Systems, 19, pp. 905 912, 2004. [13] J. Pita, M. Jain, F. Ordonez, C. Portway, M. Tambe and C. Western, Using game theory for Los Angeles airport security, AI Magazine, pp. 43 57, 2009. [14] M. Kodialam and T. V. Lakshman, Detecting network intrusions via sampling: A game theoretical approach, In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications (IEEE INFOCOM), 3, pp. 1880 1889, 2003. [15] F. Perea and J. Puerto, Revisiting a game theoretic framework for the robust railway network design against intentional attacks, European Journal of Operational Research, 226, pp. 286 292, 2013. [16] M. Bell, U. Kanturska, J. Schmocker and A. Fonzone, Attacker-defender models and road network vulnerability, Philosophical Transactions of the Royal Society, 366, pp. 1893 1906, 2008. [17] M. Tambe, Security and Game Theory-Algorithms, Deployed Systems, Lessons Learned, Cambridge University Press, 2012. [18] 4, pp. 19 35, 2011. [19] R. Hohzaki, S. Morita and Y. Terashima, A patrol problem in a building by search theory, In Proceedings of 2013 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA), pp. 104 111, 2013. [20] 60, pp. 437 442, 2015. [21] R. Hohzaki and T. Chiba, An attrition game on an acyclic network, Journal of the Operational Research Society, 66, pp. 979 992, 2015. [22] pp. 141 150, 2015. [23] http://www.ishigaki-airport. co.jp/facility.html 2015 12 1 2016 4 Copyright c by ORSJ. Unauthorized reproduction of this article is prohibited. 35 233