{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:36:37Z","timestamp":1777390597734,"version":"3.51.4"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T00:00:00Z","timestamp":1619395200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T00:00:00Z","timestamp":1619395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"DFG","award":["RTG 2236"],"award-info":[{"award-number":["RTG 2236"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We survey optimization problems that allow natural simple formulations with one existential and one universal quantifier. We summarize the theoretical background from computational complexity theory, and we present a multitude of illustrating examples. We discuss the connections to robust optimization and to bilevel optimization, and we explain the reasons why the operational research community should be interested in the theoretical aspects of this area.<\/jats:p>","DOI":"10.1007\/s10288-021-00477-y","type":"journal-article","created":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T21:03:40Z","timestamp":1619471020000},"page":"157-181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["The trouble with the second quantifier"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8816-2693","authenticated-orcid":false,"given":"Gerhard J.","family":"Woeginger","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,26]]},"reference":[{"key":"477_CR1","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/j.ejor.2008.09.012","volume":"197","author":"H Aissi","year":"2010","unstructured":"Aissi H, Bazgan C, Vanderpooten D (2010) Min\u2013max and min\u2013max regret versions of combinatorial optimization problems: a survey. Eur J Oper Res 197:427\u2013438","journal-title":"Eur J Oper Res"},{"key":"477_CR2","first-page":"5:1","volume":"4","author":"N Alon","year":"2015","unstructured":"Alon N, Bredereck R, Chen J, Kratsch S, Niedermeier R, Woeginger GJ (2015) How to put through your agenda in collective binary decisions. ACM Trans Econ Comput 4:5:1\u20135:28","journal-title":"ACM Trans Econ Comput"},{"key":"477_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity: a modern approach","author":"S Arora","year":"2009","unstructured":"Arora S, Barak B (2009) Computational complexity: a modern approach. Cambridge University Press, Cambridge"},{"key":"477_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s003550000067","volume":"18","author":"S Banerjee","year":"2001","unstructured":"Banerjee S, Konishi H, S\u00f6nmez T (2001) Core in a simple coalition formation game. Soc Choice Welf 18:135\u2013153","journal-title":"Soc Choice Welf"},{"key":"477_CR5","first-page":"231","volume":"46","author":"L Brotcorne","year":"2008","unstructured":"Brotcorne L, Marcotte P, Savard G (2008) Bilevel programming: the Montreal school. INFOR Inf Syst Oper Res 46:231\u2013246","journal-title":"INFOR Inf Syst Oper Res"},{"key":"477_CR6","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/S0036144596297514","volume":"40","author":"RE Burkard","year":"1998","unstructured":"Burkard RE, van Dal R, Deineko VG, van der Veen J, Woeginger GJ (1998) Well-solvable special cases of the traveling salesman problem: a survey. SIAM Rev 40:496\u2013546","journal-title":"SIAM Rev"},{"key":"477_CR7","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1137\/130906593","volume":"24","author":"A Caprara","year":"2014","unstructured":"Caprara A, Carvalho M, Lodi A, Woeginger GJ (2014) A complexity and approximability study of the bilevel knapsack problem. SIAM J Optim 24:823\u2013838","journal-title":"SIAM J Optim"},{"key":"477_CR8","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 GJ (2016) Bilevel knapsack with interdiction constraints. INFORMS J Comput 28:319\u2013333","journal-title":"INFORMS J Comput"},{"key":"477_CR9","unstructured":"Chen Y, Cheung WS, Ng TW (2019) An upper bound on the dimension of the voting system of the European Union Council under the Lisbon rules. arXiv:1907.09711 [cs.GT]"},{"key":"477_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10288-005-0071-0","volume":"3","author":"B Colson","year":"2005","unstructured":"Colson B, Marcotte P, Savard G (2005) Bilevel programming: a survey. 4OR 3:87\u2013107","journal-title":"4OR"},{"key":"477_CR11","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ejor.2004.09.038","volume":"170","author":"VG Deineko","year":"2006","unstructured":"Deineko VG, Woeginger GJ (2006) On the dimension of simple monotonic games. Eur J Oper Res 170:315\u2013318","journal-title":"Eur J Oper Res"},{"key":"477_CR12","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.disopt.2010.03.008","volume":"7","author":"VG Deineko","year":"2010","unstructured":"Deineko VG, Woeginger GJ (2010) Pinpointing the complexity of the interval min\u2013max regret Knapsack problem. Discrete Optim 7:191\u2013196","journal-title":"Discrete Optim"},{"key":"477_CR13","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1137\/S0895480195281878","volume":"11","author":"VG Deineko","year":"1998","unstructured":"Deineko VG, Rudolf R, Woeginger GJ (1998) Sometimes travelling is easy: the master tour problem. SIAM J Discrete Math 11:81\u201393","journal-title":"SIAM J Discrete Math"},{"key":"477_CR14","unstructured":"Della Croce F, Scatamacchia R (2019) Lower bounds and a new exact approach for the bilevel knapsack with interdiction constraints. In: Proceedings of proceedings of the 3rd conference on integer programming and combinatorial optimization (IPCO\u20192019). Springer LNCS 11480, pp 329\u2013343"},{"key":"477_CR15","volume-title":"Foundations of bilevel programming","author":"S Dempe","year":"2002","unstructured":"Dempe S (2002) Foundations of bilevel programming. Kluwer Academic Publishers, Dordrecht"},{"key":"477_CR16","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1080\/0233193031000149894","volume":"52","author":"S Dempe","year":"2003","unstructured":"Dempe S (2003) Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52:333\u2013359","journal-title":"Optimization"},{"key":"477_CR17","unstructured":"DeNegre S (2011) Interdiction and discrete bilevel linear programming. PhD dissertation, Lehigh University"},{"key":"477_CR18","unstructured":"Erd\u00f6s P, Rubin AL, Taylor H (1979) Choosability in graphs. In: Proceedings of the west coast conference on combinatorics, graph theory and computing, Congressus Numerantium XXVI, pp 125\u2013157"},{"key":"477_CR19","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1287\/opre.2017.1650","volume":"65","author":"M Fischetti","year":"2017","unstructured":"Fischetti M, Ljubic I, Monaci M, Sinnl M (2017) A new general\u2013purpose algorithm for mixed-integer bilevel linear programs. Oper Res 65:1615\u20131637","journal-title":"Oper Res"},{"key":"477_CR20","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Monthly 69:9\u201315","journal-title":"Am Math Monthly"},{"key":"477_CR21","unstructured":"Gallai T (1968) On directed graphs and circuits. In: Theory of graphs (proceedings of the colloquium held at Tihany, Hungary, September 1966). Academic Press, New York, pp 115\u2013118"},{"key":"477_CR22","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco"},{"key":"477_CR23","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BFb0120887","volume":"12","author":"M Gr\u00f6tschel","year":"1980","unstructured":"Gr\u00f6tschel M (1980) On the symmetric travelling salesman problem: solution of a 120-city problem. Math Program Study 12:61\u201377","journal-title":"Math Program Study"},{"key":"477_CR24","unstructured":"Gutner S (1992) Choice numbers of graphs. Master\u2019s thesis, Tel Aviv University"},{"key":"477_CR25","doi-asserted-by":"crossref","unstructured":"Gutner S, Tarsi M (2009) Some results on (a:b)-choosability. Discrete Math 309:2260\u20132270","DOI":"10.1016\/j.disc.2008.04.061"},{"key":"477_CR26","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P Hall","year":"1935","unstructured":"Hall P (1935) On representatives of subsets. J Lond Math Soc 10:26\u201330","journal-title":"J Lond Math Soc"},{"key":"477_CR27","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1002\/mana.19650280503","volume":"28","author":"M Hasse","year":"1965","unstructured":"Hasse M (1965) Zur algebraischen Begr\u00fcndung der Graphentheorie. Math Nach 28:275\u2013290","journal-title":"Math Nach"},{"key":"477_CR28","first-page":"57","volume":"6","author":"V Jarn\u00edk","year":"1930","unstructured":"Jarn\u00edk V (1930) O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm (About a certain minimal problem) [in Czech]. Pr\u00e1ce Moravsk\u00e9 P\u0159odov\u011bck\u00e9 Spole\u010dnosti 6:57\u201363","journal-title":"Pr\u00e1ce Moravsk\u00e9 P\u0159odov\u011bck\u00e9 Spole\u010dnosti"},{"key":"477_CR29","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(75)90003-5","volume":"11","author":"R Jeroslow","year":"1975","unstructured":"Jeroslow R (1975) On defining sets of vertices of the hypercube by linear inequalities. Discrete Math 11:119\u2013124","journal-title":"Discrete Math"},{"key":"477_CR30","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01586088","volume":"32","author":"R Jeroslow","year":"1985","unstructured":"Jeroslow R (1985) The polynomial hierarchy and a simple model for competitive analysis. Math Program 32:146\u2013164","journal-title":"Math Program"},{"key":"477_CR31","unstructured":"Johannes B (2011) New classes of complete problems for the second level of the polynomial hierarchy. Doctoral thesis, Technische Universit\u00e4t Berlin"},{"key":"477_CR32","doi-asserted-by":"publisher","first-page":"1000","DOI":"10.4153\/CJM-1975-104-6","volume":"27","author":"K Kalmanson","year":"1975","unstructured":"Kalmanson K (1975) Edge-convex circuits and the travelling salesman problem. Can J Math 27:1000\u20131010","journal-title":"Can J Math"},{"key":"477_CR33","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF01204720","volume":"12","author":"R Kannan","year":"1992","unstructured":"Kannan R (1992) Lattice translates of a polytope and the Frobenius problem. Combinatorica 12:161\u2013177","journal-title":"Combinatorica"},{"key":"477_CR34","unstructured":"Khachiyan L (1979) A polynomial algorithm for linear programming [in Russian]. Doklady Akademii Nauk SSSR 224, 1093\u20131096. English translation: Soviet Mathematics Doklady 20:191\u2013194"},{"key":"477_CR35","doi-asserted-by":"crossref","unstructured":"Kober S, Weltge S (2020) Improved lower bound on the dimension of the EU council\u2019s voting rules. arXiv:2003.11366 [math.OC]","DOI":"10.1007\/s11590-020-01637-5"},{"key":"477_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2620-6","volume-title":"Robust discrete optimization and its applications","author":"P Kouvelis","year":"1997","unstructured":"Kouvelis P, Yu G (1997) Robust discrete optimization and its applications. Kluwer Academic Publishers, Boston"},{"key":"477_CR37","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1007\/s11590-015-0917-0","volume":"10","author":"PS Kurz","year":"2015","unstructured":"Kurz PS, Napel S (2015) Dimension of the Lisbon voting rules in the EU Council: a challenge and new world record. Optim Lett 10:1245\u20131256","journal-title":"Optim Lett"},{"key":"477_CR38","doi-asserted-by":"publisher","first-page":"3487","DOI":"10.1016\/j.tcs.2011.02.038","volume":"412","author":"D Marx","year":"2011","unstructured":"Marx D (2011) Complexity of clique coloring and related problems. Theoret Comput Sci 412:3487\u20133500","journal-title":"Theoret Comput Sci"},{"key":"477_CR39","unstructured":"Matsubara S (2016) The computational complexity of the Frobenius problem. arXiv:1602.05657 [cs.CC]"},{"key":"477_CR40","volume-title":"Computational complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Berlin"},{"key":"477_CR41","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF01300131","volume":"16","author":"J Ram\u00edrez Alfons\u00edn","year":"1996","unstructured":"Ram\u00edrez Alfons\u00edn J (1996) Complexity of the Frobenius problem. Combinatorica 16:143\u2013147","journal-title":"Combinatorica"},{"key":"477_CR42","volume-title":"The diophantine Frobenius problem","author":"J Ram\u00edrez Alfons\u00edn","year":"2006","unstructured":"Ram\u00edrez Alfons\u00edn J (2006) The diophantine Frobenius problem. Oxford University Press, Oxford"},{"key":"477_CR43","first-page":"129","volume":"1","author":"B Roy","year":"1967","unstructured":"Roy B (1967) Nombre chromatique et plus longs chemins d\u2019un graphe. Rev Fran\u00e7aise d\u2019Inf Recherche Op\u00e9r 1:129\u2013132","journal-title":"Rev Fran\u00e7aise d\u2019Inf Recherche Op\u00e9r"},{"key":"477_CR44","unstructured":"Schaefer M, Umans C (2002a) Completeness in the polynomial-time hierarchy: a compendium. SIGACT News 33(3):32\u201349"},{"key":"477_CR45","doi-asserted-by":"crossref","unstructured":"Schaefer M, Umans C (2002) Completeness in the polynomial-time hierarchy: Part II. SIGACT News 33(4):22\u201336","DOI":"10.1145\/601819.601829"},{"key":"477_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"LJ Stockmeyer","year":"1977","unstructured":"Stockmeyer LJ (1977) The polynomial-time hierarchy. Theoret Comput Sci 3:1\u201322","journal-title":"Theoret Comput Sci"},{"key":"477_CR47","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.orl.2006.03.011","volume":"35","author":"S-C Sung","year":"2007","unstructured":"Sung S-C, Dimitrov D (2007) On core membership testing for hedonic coalition formation games. Oper Res Lett 35:155\u2013158","journal-title":"Oper Res Lett"},{"key":"477_CR48","doi-asserted-by":"publisher","first-page":"79","DOI":"10.2307\/2369536","volume":"5","author":"JJ Sylvester","year":"1882","unstructured":"Sylvester JJ (1882) On subinvariants, i.e. semi-invariants to binary quantics of an unlimited order. Am J Math 5:79\u2013136","journal-title":"Am J Math"},{"key":"477_CR49","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1006\/game.1993.1009","volume":"5","author":"AD Taylor","year":"1993","unstructured":"Taylor AD, Zwicker WS (1993) Weighted voting, multicameral representation, and power. Games Econ Behav 5:170\u2013181","journal-title":"Games Econ Behav"},{"key":"477_CR50","volume-title":"Simple games: desirability relations, trading, and pseudoweightings","author":"AD Taylor","year":"1999","unstructured":"Taylor AD, Zwicker WS (1999) Simple games: desirability relations, trading, and pseudoweightings. Princeton University Press, Princeton"},{"key":"477_CR51","unstructured":"Vitaver LM (1962) Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix. Dokl Akad Nauk SSSR 147:758\u2013759 (in Russian)"},{"key":"477_CR52","unstructured":"von Stackelberg H (1934) Marktform und Gleichgewicht. Springer, Berlin [English translation: The theory of market economy. Oxford University Press, 1952]"},{"key":"477_CR53","doi-asserted-by":"crossref","unstructured":"Woeginger GJ (2013a) A hardness result for core stability in additive hedonic games. Math Soc Sci 65:101\u2013104","DOI":"10.1016\/j.mathsocsci.2012.10.001"},{"key":"477_CR54","doi-asserted-by":"crossref","unstructured":"Woeginger GJ (2013b) Core stability in hedonic coalition formation. In: Proceedings of the 39th international conference on current trends in theory and practice of computer science (SOFSEM\u20192013). Springer LNCS 7741, pp 33\u201350","DOI":"10.1007\/978-3-642-35843-2_4"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-021-00477-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-021-00477-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-021-00477-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,9]],"date-time":"2021-05-09T19:04:09Z","timestamp":1620587049000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-021-00477-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,26]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["477"],"URL":"https:\/\/doi.org\/10.1007\/s10288-021-00477-y","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"value":"1619-4500","type":"print"},{"value":"1614-2411","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,26]]},"assertion":[{"value":"6 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author certifies that he has no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}