Geodesic
Bilevel ``defender--attacker'' model with multiple attack scenarios
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 5-22.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a bilevel “defender–attacker” model built on the basis of the Stackelberg game. In this model, given is a set of the objects providing social services for a known set of customers and presenting potential targets for a possible attack. At the first step, the Leader (defender) makes a decision on the protection of some of the objects on the basis of his/her limited resources. Some Follower (attacker), who is also limited in resources, decides then to attack unprotected objects, knowing the decision of the Leader. It is assumed that the Follower can evaluate the importance of each object and makes a rational decision trying to maximize the total importance of the objects attacked. The Leader does not know the attack scenario (the Follower's priorities for selecting targets for the attack). But, the Leader can consider several possible scenarios that cover the Follower's plans. The Leader's problem is then to select the set of objects for protection so that, given the set of possible attack scenarios and assuming the rational behavior of the Follower, to minimize the total costs of protecting the objects and eliminating the consequences of the attack associated with the reassignment of the facilities for customer service. The proposed model may be presented as a bilevel mixed-integer programming problem that includes an upper-level problem (the Leader problem) and a lower-level problem (the Follower problem). The main efforts in this article are aimed at reformulation of the problem as some one-level mathematical programming problems. These formulations are constructed using the properties of the optimal solution of the Follower's problem, which makes it possible to formulate necessary and sufficient optimality conditions in the form of linear relations. Bibliogr. 16.
Keywords: bilevel programming, complementarity slackness, optimality criteria. 
@article{DA_2018_25_3_a0,
     author = {V. L. Beresnev and I. A. Davydov and P. A. Kononova and A. A. Melnikov},
     title = {Bilevel ``defender--attacker'' model with multiple attack scenarios},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--22},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_3_a0/}
}
TY  - JOUR
AU  - V. L. Beresnev
AU  - I. A. Davydov
AU  - P. A. Kononova
AU  - A. A. Melnikov
TI  - Bilevel ``defender--attacker'' model with multiple attack scenarios
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 5
EP  - 22
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_3_a0/
LA  - ru
ID  - DA_2018_25_3_a0
ER  - 
%0 Journal Article
%A V. L. Beresnev
%A I. A. Davydov
%A P. A. Kononova
%A A. A. Melnikov
%T Bilevel ``defender--attacker'' model with multiple attack scenarios
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 5-22
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_3_a0/
%G ru
%F DA_2018_25_3_a0
V. L. Beresnev; I. A. Davydov; P. A. Kononova; A. A. Melnikov. Bilevel ``defender--attacker'' model with multiple attack scenarios. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 5-22. http://geodesic.mathdoc.fr/item/DA_2018_25_3_a0/

[1] I. A. Davydov, A. A. Melnikov, P. A. Kononova, “Local search for load balancing problems for servers with large dimension”, Autom. Remote Control, 78:3 (2017), 412–424 | DOI | MR | Zbl

[2] Aksen D., Aras N., “A bilevel fixed charge location model for facilities under imminent attack”, Comput. Oper. Res., 39:1 (2012), 1364–1381 | DOI | MR | Zbl

[3] Aksen D., Piyade N., Aras N., “The budget constrained $r$-interdiction median problem with capacity expansion”, Central Eur. J. Oper. Res., 18:3 (2010), 269–291 | DOI | MR | Zbl

[4] An B., Ordóñez F., Tambe M., Shieh E., Yang R., Baldwin C., DiRenzo J., Moretti K., Maule B., Meyer G., “A deployed quantal response-based patrol planning system for the U. S. Coast Guard”, Interfaces, 43:5 (2013), 400–420 | DOI

[5] Angelo J. S., Barbosa H. J. C., “A study on the use of heuristics to solve a bilevel programming problem”, Int. Trans. Oper. Res., 22 (2015), 861–882 | DOI | MR | Zbl

[6] Beresnev V., Melnikov A., “Facility location in unfair competition”, Discrete Optimization and Operations Research, Proc. 9th Int. Conf. (Vladivostok, Russia, Sept. 19–23, 2016), Lect. Notes Comput. Sci., 9869, Springer, Cham, 2016, 325–335 | DOI | MR | Zbl

[7] Brotcorne L., Hanafi S., Mansi R., “One-level reformulation of the bilevel knapsack problem using dynamic programming”, Discrete Optimization, 10:1 (2013), 1–10 | DOI | MR | Zbl

[8] Delle Fave F. M., Jiang A. X., Yin Z., Zhang C., Tambe M., Kraus S., Sullivan J. P., “Game-theoretic security patrolling with dynamic execution uncertainty and a case study on a real transit system”, J. Artif. Intell. Res., 50 (2014), 321–367 | DOI | MR | Zbl

[9] Dempe S., Foundations of bilevel programming, Kluwer Acad. Publ., Dordrecht, 2002, 332 pp. | MR | Zbl

[10] Jain M., Tsai J., Pita J., Kiekintveld C., Rathi S., Tambe M., Ordóñez F., “Software assistants for randomized patrol planning for the LAX airport police and the federal air marshal service”, Interfaces, 40:4 (2010), 267–290 | DOI

[11] Jiang A. X., Yin Z., Zhang C., Tambe M., Kraus S., “Game-theoretic randomization for security patrolling with dynamic execution uncertainty”, Proc. 12th Int. Conf. Auton. Agents Multiagent Syst. (Saint Paul, MN, USA, May 6–10, 2013), Int. Found. Auton. Agents Multiagent Syst., Richland, SC, 2013, 207–214

[12] Martello S., Toth P., Knapsack problems: Algorithms and computer implementations, John Wiley Sons, New York, 1990 | MR | Zbl

[13] Melo M. T., Nickel S., Saldanha-Da-Gama F., “A tabu search heuristic for redesigning a multi-echelon supply chain network over a planning horizon”, Int. J. Production Econ., 136:1 (2012), 218–230 | DOI

[14] Scaparra M. P., Church R. L., “A bilevel mixed-integer program for critical infrastructure protection planning”, Comput. Oper. Res., 35 (2008), 1905–1923 | DOI | Zbl

[15] Stackelberg H., The theory of the market economy, Oxf. Univ. Press, Oxford, 1952, 289 pp.

[16] Zhu Y., Zheng Z., Zhang X., Cai K. Y., “The $r$-interdiction median problem with probabilistic protection and its solution algorithm”, Comput. Oper. Res., 40 (2013), 451–462 | DOI | MR | Zbl