{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T21:54:14Z","timestamp":1773179654771,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000739","name":"University of Southampton","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000739","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The search problem of computing a<jats:italic>Stackelberg<\/jats:italic>(or<jats:italic>leader-follower)<\/jats:italic><jats:italic>equilibrium<\/jats:italic>(also referred to as an<jats:italic>optimal strategy to commit to<\/jats:italic>) has been widely investigated in the scientific literature in, almost exclusively, the single-follower setting. Although the<jats:italic>optimistic<\/jats:italic>and<jats:italic>pessimistic<\/jats:italic>versions of the problem, i.e., those where the single follower breaks any ties among multiple equilibria either in favour or against the leader, are solved with different methodologies, both cases allow for efficient, polynomial-time algorithms based on linear programming. The situation is different with multiple followers, where results are only sporadic and depend strictly on the nature of the followers\u2019 game. In this paper, we investigate the setting of a normal-form game with a single leader and multiple followers who, after observing the leader\u2019s commitment, play a Nash equilibrium. When both leader and followers are allowed to play mixed strategies, the corresponding search problem, both in the optimistic and pessimistic versions, is known to be inapproximable in polynomial time to within any multiplicative polynomial factor unless<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {P}=\\textsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>P<\/mml:mi><mml:mo>=<\/mml:mo><mml:mi>NP<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Exact algorithms are known only for the optimistic case. We focus on the case where the followers play pure strategies\u2014a restriction that applies to a number of real-world scenarios and which, in principle, makes the problem easier\u2014under the assumption of pessimism (the optimistic version of the problem can be straightforwardly solved in polynomial time). After casting this search problem (with followers playing pure strategies) as a<jats:italic>pessimistic bilevel programming problem<\/jats:italic>, we show that, with two followers, the problem is -hard and, with three or more followers, it cannot be approximated in polynomial time to within any multiplicative factor which is polynomial in the size of the normal-form game, nor, assuming utilities in [0,\u00a01], to within any constant additive loss stricly smaller than 1 unless<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {P}=\\textsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>P<\/mml:mi><mml:mo>=<\/mml:mo><mml:mi>NP<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This shows that, differently from what happens in the optimistic version, hardness and inapproximability in the pessimistic problem are not due to the adoption of mixed strategies. We then show that the problem admits, in the general case, a supremum but not a maximum, and we propose a single-level mathematical programming reformulation which asks for the maximization of a nonconcave quadratic function over an unbounded nonconvex feasible region defined by linear and quadratic constraints. Since, due to admitting a supremum but not a maximum, only a restricted version of this formulation can be solved to optimality with state-of-the-art methods, we propose an exact<jats:italic>ad hoc<\/jats:italic>algorithm (which we also embed within a branch-and-bound scheme) capable of computing the supremum of the problem and, for cases where there is no leader\u2019s strategy where such value is attained, also an<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03b1<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate strategy where<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha &gt; 0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03b1<\/mml:mi><mml:mo>&gt;<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is an arbitrary additive loss (at most as large as the supremum). We conclude the paper by evaluating the scalability of our algorithms via computational experiments on a well-established testbed of game instances.<\/jats:p>","DOI":"10.1007\/s00453-019-00648-8","type":"journal-article","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T13:02:20Z","timestamp":1573736540000},"page":"1189-1238","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Computing a Pessimistic Stackelberg Equilibrium with Multiple Followers: The Mixed-Pure Case"],"prefix":"10.1007","volume":"82","author":[{"given":"Stefano","family":"Coniglio","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7349-3932","authenticated-orcid":false,"given":"Nicola","family":"Gatti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marchesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"issue":"2","key":"648_CR1","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1287\/moor.8.2.273","volume":"8","author":"FA Al-Khayyal","year":"1983","unstructured":"Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273\u2013286 (1983)","journal-title":"Math. Oper. Res."},{"issue":"7","key":"648_CR2","doi-asserted-by":"publisher","first-page":"1463","DOI":"10.1109\/LCOMM.2013.060513.130351","volume":"17","author":"E Amaldi","year":"2013","unstructured":"Amaldi, E., Capone, A., Coniglio, S., Gianoli, L.G.: Network optimization problems subject to max-min fair flow allocation. IEEE Commun. Lett. 17(7), 1463\u20131466 (2013)","journal-title":"IEEE Commun. Lett."},{"issue":"1","key":"648_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1978721.1978729","volume":"10","author":"B An","year":"2011","unstructured":"An, B., Pita, J., Shieh, E., Tambe, M., Kiekintveld, C., Marecki, J.: Guards and protect: next generation applications of security games. ACM SIGecom Exch. 10(1), 31\u201334 (2011)","journal-title":"ACM SIGecom Exch."},{"key":"648_CR4","doi-asserted-by":"crossref","unstructured":"Basilico, N., Coniglio, S., Gatti, N.: Methods for finding leader-follower equilibria with multiple followers: (extended abstract). In: AAMAS, pp. 1363\u20131364 (2016)","DOI":"10.24963\/ijcai.2017\/25"},{"key":"648_CR5","unstructured":"Basilico, N., Coniglio, S., Gatti, N.: Methods for finding leader-follower equilibria with multiple followers. CoRR (2017a). http:\/\/arxiv.org\/abs\/1707.02174, 1707.02174"},{"key":"648_CR6","unstructured":"Basilico, N., Coniglio, S., Gatti, N., Marchesi, A.: Bilevel programming approaches to the computation of optimistic and pessimistic single-leader-multi-follower equilibria. In: 16th International Symposium on Experimental Algorithms (SEA 2017), Leibniz International Proceedings in Informatics, Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl Publishing, Germany, pp. 69:1\u201369:14 (2017b)"},{"key":"648_CR7","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.artint.2017.02.007","volume":"246","author":"N Basilico","year":"2017","unstructured":"Basilico, N., De Nittis, G., Gatti, N.: Adversarial patrolling with spatially uncertain alamr signals. Artif. Intell. 246, 220\u2013257 (2017c)","journal-title":"Artif. Intell."},{"key":"648_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/s13675-019-00114-8","author":"N Basilico","year":"2019","unstructured":"Basilico, N., Coniglio, S., Gatti, N., Marchesi, A.: Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games. EURO J. Comput. Optim. (2019). https:\/\/doi.org\/10.1007\/s13675-019-00114-8","journal-title":"EURO J. Comput. Optim."},{"key":"648_CR9","volume-title":"Introduction to Linear Optimization","author":"D Bertsimas","year":"1997","unstructured":"Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization, vol. 6. Athena Scientific, Belmont, MA (1997)"},{"issue":"2","key":"648_CR10","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1287\/ijoc.2015.0676","volume":"28","author":"A Caprara","year":"2016","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: Bilevel knapsack with interdiction constraints. Inform. J. Comput. 28(2), 319\u2013333 (2016)","journal-title":"Inform. J. Comput."},{"key":"648_CR11","doi-asserted-by":"crossref","unstructured":"Castiglioni, M., Marchesi, A., Gatti, N., Coniglio, S.: Leadership in singleton congestion games: what is hard and what is easy. Artif. Intell. 277 (2019)","DOI":"10.1016\/j.artint.2019.103177"},{"key":"648_CR12","doi-asserted-by":"crossref","unstructured":"Coniglio, S., Gatti, N., Marchesi, A.: Pessimistic leader-follower equilibria with multiple followers. In: IJCAI, pp. 171\u2013177 (2017)","DOI":"10.24963\/ijcai.2017\/25"},{"key":"648_CR13","doi-asserted-by":"crossref","unstructured":"Conitzer, V., Korzhyk, D.: Commitment to correlated strategies. In: AAAI, pp. 632\u2013637 (2011)","DOI":"10.1609\/aaai.v25i1.7875"},{"key":"648_CR14","doi-asserted-by":"crossref","unstructured":"Conitzer, V., Sandholm, T.: Computing the optimal strategy to commit to. In: ACM EC, pp. 82\u201390 (2006)","DOI":"10.1145\/1134707.1134717"},{"key":"648_CR15","unstructured":"Farina, G., Marchesi, A., Kroer, C., Gatti, N., Sandholm, T.: Trembling-hand perfection in extensive-form games with commitment. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13\u201319, 2018, Stockholm, Sweden, pp. 233\u2013239 (2018)"},{"key":"648_CR16","doi-asserted-by":"crossref","unstructured":"Karp, RM.: Reducibility among combinatorial problems. In: Complexity of Computer Computations. Springer, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"648_CR17","unstructured":"Kiekintveld, C., Jain, M., Tsai, J., Pita, J., Ord\u00f3\u00f1ez, F., Tambe, M.: Computing optimal randomized resource allocations for massive security games. In: AAMAS, pp. 689\u2013696 (2009)"},{"key":"648_CR18","unstructured":"Korzhyk, D., Conitzer, V., Parr, R.: Security games with multiple attacker resources. In: Twenty-Second International Joint Conference on Artificial Intelligence (2011)"},{"issue":"1","key":"648_CR19","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10479-015-2016-0","volume":"240","author":"M Labb\u00e9","year":"2016","unstructured":"Labb\u00e9, M., Violin, A.: Bilevel programming and price setting problems. Ann. Oper. Res. 240(1), 141\u2013169 (2016)","journal-title":"Ann. Oper. Res."},{"key":"648_CR20","doi-asserted-by":"crossref","unstructured":"Marchesi, A., Coniglio, S., Gatti, N.: Leadership in singleton congestion games. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, AAAI Press, pp. 447\u2013453 (2018)","DOI":"10.24963\/ijcai.2018\/62"},{"key":"648_CR21","unstructured":"Marchesi, A., Castiglioni, M., Gatti, N.: Leadership in congestion games: Multiple user classes and non-singleton actions. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10\u201316, 2019, pp. 485\u2013491 (2019a)"},{"key":"648_CR22","unstructured":"Marchesi, A., Farina, G., Kroer, C., Gatti, N., Sandholm, T.: Quasi-perfect stackelberg equilibrium. In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27\u2013February 1, 2019., pp. 2117\u20132124 (2019b)"},{"issue":"1","key":"648_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.orl.2016.11.005","volume":"45","author":"J Matuschke","year":"2017","unstructured":"Matuschke, J., McCormick, S.T., Oriolo, G., Peis, B., Skutella, M.: Protection of flows under targeted attacks. Oper. Res. Lett. 45(1), 53\u201359 (2017)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"648_CR24","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"G McCormick","year":"1976","unstructured":"McCormick, G.: Computability of global solutions to factorable nonconvex programs: part I\u2014convex underestimating problems. Math. Program. 10(1), 147\u2013175 (1976)","journal-title":"Math. Program."},{"issue":"1","key":"648_CR25","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.S.: Potential games. Game Econ. Behav. 14(1), 124\u2013143 (1996)","journal-title":"Game Econ. Behav."},{"issue":"2","key":"648_CR26","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"JF Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"648_CR27","unstructured":"Nudelman, E., Wortman, J., Leyton-Brown, K., Shoham, Y.: Run the GAMUT: a comprehensive approach to evaluating game\u2013theoretic algorithms. In: AAMAS, pp. 880\u2013887 (2004)"},{"key":"648_CR28","unstructured":"Paruchuri, P., Pearce, JP., Marecki, J., Tambe, M., Ordonez, F., Kraus, S.: Playing games for security: an efficient exact algorithm for solving bayesian stackelberg games. In: AAMAS, pp. 895\u2013902 (2008)"},{"issue":"1","key":"648_CR29","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"RW Rosenthal","year":"1973","unstructured":"Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65\u201367 (1973)","journal-title":"Int. J. Game Theory"},{"key":"648_CR30","unstructured":"Sahinidis, N.V.: BARON 14.3.1: Global optimization of mixed-integer nonlinear programs user\u2019s manual (2014)"},{"key":"648_CR31","unstructured":"Sandholm, T., Gilpin, A., Conitzer, V.: Mixed-integer programming methods for finding nash equilibria. In: AAAI, pp. 495\u2013501 (2005)"},{"key":"648_CR32","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811654","volume-title":"Multiagent Systems: Algorithmic, Game Theoretic and Logical Foundations","author":"Y Shoham","year":"2008","unstructured":"Shoham, Y., Leyton-Brown, K.: Multiagent Systems: Algorithmic, Game Theoretic and Logical Foundations. Cambridge University Press, Cambridge (2008)"},{"issue":"2","key":"648_CR33","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/game.1995.1019","volume":"9","author":"W Stanford","year":"1995","unstructured":"Stanford, W.: A note on the probability of k pure nash equilibria in matrix games. Games Econ. Behav. 9(2), 238\u2013246 (1995)","journal-title":"Games Econ. Behav."},{"key":"648_CR34","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1016\/j.geb.2009.11.008","volume":"69","author":"B von Stengel","year":"2010","unstructured":"von Stengel, B., Zamir, S.: Leadership games with convex strategy sets. Games Econ. Behav. 69, 446\u2013457 (2010)","journal-title":"Games Econ. Behav."},{"issue":"3","key":"648_CR35","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s11228-016-0371-x","volume":"24","author":"A Zemkoho","year":"2016","unstructured":"Zemkoho, A.: Solving ill-posed bilevel programs. Set-valued Anal. 24(3), 423\u2013448 (2016)","journal-title":"Set-valued Anal."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00648-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00648-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00648-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,5]],"date-time":"2022-10-05T04:27:50Z","timestamp":1664944070000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00648-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,14]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["648"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00648-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,14]]},"assertion":[{"value":"21 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}