A study of general and security Stackelberg game formulations

Casorrán, C.; Fortz, Bernard; Labbé, M.; Ordóñez, F.

doi:10.1016/j.ejor.2019.05.012

Download

Article (Scientific journals)

A study of general and security Stackelberg game formulations

Casorrán, C.; Fortz, Bernard; Labbé, M. et al.

2019 • In European Journal of Operational Research, 278 (3), p. 855-868

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/318166

DOI
10.1016/j.ejor.2019.05.012

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Casorran.pdf

Author postprint (777.72 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Integer programming; Discrete optimization; Game theory; Bilevel optimization

Abstract :

[en] In this paper, we analyze different mathematical formulations for general Stackelberg games (GSGs) and Stackelberg security games (SSGs). We consider GSGs in which a single leader commits to a utility maximizing strategy knowing that p possible followers optimize their own utility taking the leader’s strategy into account. SSGs are a type of GSG that arise in security applications where the strategies of the leader consist of protecting a subset of targets and the strategies of the p followers consist of attacking a single target. We compare existing mixed integer linear programming (MILP) formulations for GSGs, ranking them according to the tightness of their linear programming (LP) relaxations. We show that SSG formulations are projections of GSG formulations and exploit this link to derive a new SSG MILP formulation that (i) has the tightest LP relaxation known among SSG MILP formulations and (ii) has an LP relaxation that coincides with the convex hull of feasible solutions in the case of a single follower. We present computational experiments empirically comparing the difficulty of solving the formulations in the general and security settings. The new SSG MILP formulation remains computationally efficient as problem size increases.

Disciplines :

Quantitative methods in economics & management

Author, co-author :

Casorrán, C.

Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt

Labbé, M.

Ordóñez, F.

Language :

English

Title :

A study of general and security Stackelberg game formulations

Publication date :

2019

Journal title :

European Journal of Operational Research

ISSN :

0377-2217

eISSN :

1872-6860

Volume :

278

Issue :

Pages :

855-868

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85066082600&doi=10.1016%2fj.ejor.2019.05.012&partnerID=40&md5=ce03aa55c030541cbf6dee9821f64a55

Available on ORBi :

since 15 May 2024

Statistics

Number of views

7 (1 by ULiège)

Number of downloads

7 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Anandalingam, G., Friesz, T.L., Hierarchical optimization: an introduction. Annals of Operations Research 34:1 (1992), 1–11, 10.1007/BF02098169.
Bard, J.F., Practial Bilevel optimization: Algorithms and applications. 1998, Kluwer Academic Publishers.
Bracken, J., McGill, J.T., Mathematical programs with optimization problems in the constraints. Operations Research 21:1 (1973), 37–44.
Brown, G., Carlyle, M., Salmerón, J., Wood, K., Defending critical infrastructure. Interfaces 36 (2006), 530–544.
Colson, B., Marcotte, P., Savard, G., An overview of bilevel optimization. Annals of Operations Research 153 (2007), 235–256, 10.1007/s10479-007-0176-2.
Conitzer, V., Korzhyk, D., Commitment to correlated strategies. Burgard, W., Roth, D., (eds.)Proceedings of the AAAI, 2011, AAAI Press.
Conitzer, V., Sandholm, T., Computing the optimal strategy to commit to. ACM, (eds.)Proceedings of the seventh ACM conference on electronic commerce, EC ’06, 2006, ACM, New York, NY, USA, 82–90.
Dantzig, G.B., Eaves, C.B., Fourier-Motzkin Elimination and Its Dual. Journal of Combinatorial Theory Series A 14:3 (1973), 288–297.
Farkas, J., Theorie der einfachen ungleichungen. Journal für die reine und angewandte Mathematik 124 (1902), 1–27.
Fischetti, M., Ljubic, I., Monaci, M., & Sinnl, M. (2018a). Interdiction games and monotonicity. INFORMS Journal on Computing,. To appear.
Fischetti, M., Monaci, M., Sinnl, M., A dynamic reformulation heuristic for generalized interdiction problems. European Journal of Operational Research 267:1 (2018), 40–51, 10.1016/j.ejor.2017.11.043.
Harsanyi, J.C., Selten, R., A generalized Nash solution for two-person bargaining games with incomplete information. Management Science 18:5 (1972), 80–106.
Jain, M., Kiekintveld, C., Tambe, M., Quality-bounded solutions for finite Bayesian Stackelberg games: scaling up. Proceedings of the International conference on autonomous agents and multiagent systems – volume 3, 2011, 997–1004.
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.
Jiang, J., Liu, X., Multi-objective stackelberg game model for water supply networks against interdictions with incomplete information. European Journal of Operational Research 266:3 (2018), 920–933, 10.1016/j.ejor.2017.10.034.
Karwowski, J., Mańdziuk, J., A Monte Carlo tree search approach to finding efficient patrolling schemes on graphs. European Journal of Operational Research, 2019, 10.1016/j.ejor.2019.02.017.
Kiekintveld, C., Jain, M., Tsai, J., Pita, J., Ordóñez, F., Tambe, M., Computing optimal randomized resource allocations for massive security games. International conference on autonomous agents and multiagent systems – volume 1, 2009, 689–696.
Kolstad, C., A review of the literature on bi-level mathematical programming. Technical Report, 1985, Los Alamos Nat. Lab.
Krichene, W., Reilly, J.D., Amin, S., Bayen, A.M., Stackelberg routing on parallel networks with horizontal queues. IEEE Transactions on Automatic Control 59:3 (2014), 714–727.
Labbé, M., Marcotte, P., Savard, G., A bilevel model of taxation and its application to optimal highway pricing. Management science 44:12-part-1 (1998), 1608–1622.
Labbé, M., Violin, A., Bilevel programming and price setting problems. Annals of Operations Research 240:1 (2016), 141–169, 10.1007/s10479-015-2016-0.
Leitman, G., On generalized stackelberg strategies. Journal of Optimization Theory and Applications 26:4 (1978), 637–643.
Li, Y., Qiao, S., Deng, Y., Wu, J., Stackelberg game in critical infrastructures from a network science perspective. Physica A: Statistical Mechanics and its Applications 521 (2019), 705–714, 10.1016/j.physa.2019.01.119.
McMasters, A.W., Mustin, T.M., Optimal interdiction of a supply network. Naval Research Logistics Quarterly 17:3 (1970), 261–268, 10.1002/nav.3800170302.
Paruchuri, P., Pearce, J.P., Marecki, J., Tambe, M., Ordóñez, F., Kraus, S., Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games. International joint conference on autonomous agents and multiagent systems – volume 2, 2008, 895–902.
Pochet, Y., Wolsey, L.A., Production planning by mixed integer programming. Springer series in operations research and financial engineering, 2006, Springer-Verlag New York, Inc.
Savard, G., Contirbutions à la programmation mathématique a deux niveaux, 1989, École Polytechnique, Université de Montreal Ph.D. thesis.
Sherali, H.D., Adams, W.P., A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Applied Mathematics 52:1 (1994), 83–106.
Shieh, E., An, B., Yang, R., Tambe, M., Baldwin, C., DiRenzo, J., Maule, B., Meyer, G., Protect: a deployed game theoretic system to protect the ports of the united states. Proceedings of the international conference on autonomous agents and multiagent systems – volume 1, 1, 2012, 13–20.
Smith, J., Lim, C., Algorithms for network interdiction and fortification games. Chinchuluun, A., Pardalos, P.M., Migdalas, A., Pitsoulis, L., (eds.)Pareto optimality, game theory and equilbiria. Springer optimization and its applications, 17, 2008, Springer, New York, NY.
Snyder, L.V., Atan, Z., Peng, P., Rong, Y., Schmitt, A.J., Sinsoysal, B., OR/MS models for supply chain disruptions: a review. IIE Transactions 48:2 (2016), 89–109, 10.1080/0740817X.2015.1067735.
von Stackelberg, H. (2011). Market Structure and Equilibrium. Springer. Translated by Bazin, D., Urch, L. and Hill, R.
Yang, R., Ford, B., Tambe, M., Lemieux, A., Adaptive resource allocation for wildlife protection against illegal poachers. International conference on autonomous agents and multiagent systems, 2014, 453–460.
Yang, R., Jiang, A.X., Tambe, M., Ordóñez, F., Scaling-up security games with boundedly rational adversaries: a cutting-plane approach. Rossi, F., (eds.)Proceedings of the international joint conference on artificial intelligence, IJCAI, 2013, IJCAI/AAAI, 404–410.
Yin, Y., Vorobeychik, Y., An, B., Hazon, N., Optimal defense against election control by deleting voter groups. Artificial Intelligence 259 (2018), 32–51, 10.1016/j.artint.2018.02.001.
Yin, Z., Jiang, A.X., Tambe, M., Kiekintveld, C., Leyton-Brown, K., Sandholm, T., Sullivan, J.P., Trusts: Scheduling randomized patrols for fare inspection in transit systems using game theory. AI Magazine 33:4 (2012), 59–72.
Yin, Z., Tambe, M., A unified method for handling discrete and continuous uncertainty in Bayesian Stackelberg games. Conitzer, W., van der Hoek, (eds.)Proceedings of the autonomous agents and multiagent systems AAMAS, 2012.