{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:42Z","timestamp":1760202702557,"version":"3.41.0"},"publisher-location":"Cham","reference-count":64,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319240237"},{"type":"electronic","value":"9783319240244"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24024-4_6","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T12:00:10Z","timestamp":1441368010000},"page":"49-86","source":"Crossref","is-referenced-by-count":1,"title":["Weighted Boolean Formula Games"],"prefix":"10.1007","author":[{"given":"Marios","family":"Mavronicolas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Burkhard","family":"Monien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus W.","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,22]]},"reference":[{"issue":"6","key":"6_CR1","doi-asserted-by":"publisher","first-page":"1172","DOI":"10.1016\/j.jcss.2011.01.001","volume":"77","author":"C \u00c1lvarez","year":"2011","unstructured":"\u00c1lvarez, C., Gabarr\u00f3, J., Serna, M.: Equilibria problems on games: complexity versus succinctness. J. Comput. Syst. Sci. 77(6), 1172\u20131197 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"6_CR2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0899-8256(89)90003-1","volume":"1","author":"RJ Aumann","year":"1989","unstructured":"Aumann, R.J., Sorin, S.: Cooperation and bounded recall. Game. Econ. Behav. 1(1), 5\u201339 (1989)","journal-title":"Game. Econ. Behav."},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/game.1997.0546","volume":"19","author":"M Bacharach","year":"1997","unstructured":"Bacharach, M., Bernasconi, M.: An experimental study of the variable frame theory of focal points. Game. Econ. Behav. 19(1), 1\u201345 (1997)","journal-title":"Game. Econ. Behav."},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-540-72870-2_22","volume-title":"Algorithmic Aspects in Information and Management","author":"V Bil\u00f2","year":"2007","unstructured":"Bil\u00f2, V.: On satisfiability games and the power of congestion games. In: Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol. 4508, pp. 231\u2013240. Springer, Heidelberg (2007)"},{"key":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-33996-7_4","volume-title":"Algorithmic Game Theory","author":"V Bil\u00f2","year":"2012","unstructured":"Bil\u00f2, V., Mavronicolas, M.: The complexity of decision problems about nash equilibria in win-lose games. In: Serna, M. (ed.) SAGT 2012. LNCS, vol. 7615, pp. 37\u201348. Springer, Heidelberg (2012)"},{"issue":"2","key":"6_CR6","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0304-4068(99)00008-7","volume":"34","author":"M Blonski","year":"2000","unstructured":"Blonski, M.: Characterization of pure-strategy equilibria in finite anonymous games. J. Math. Econ. 34(2), 225\u2013233 (2000)","journal-title":"J. Math. Econ."},{"key":"6_CR7","unstructured":"Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J., Zanuttini, B.: Boolean games revisited. In: Proceedings of the 17th European Conference on Artificial Intelligence, Series Frontiers in Artificial Intelligence and Applications, vol. 141, pp. 265\u2013269, August\/September 2006"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-36668-3_7","volume-title":"PRICAI 2006: Trends in Artificial Intelligence","author":"E Bonzon","year":"2006","unstructured":"Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J.: Compact preference representation for boolean games. In: Yang, Q., Webb, G. (eds.) PRICAI 2006. LNCS (LNAI), vol. 4099, pp. 41\u201350. Springer, Heidelberg (2006)"},{"issue":"1","key":"6_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10458-008-9040-2","volume":"18","author":"E Bonzon","year":"2009","unstructured":"Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J., Zanuttini, B.: Compact preference representation and boolean games. Auton. Agents Multi-Agent Syst. 18(1), 1\u201335 (2009)","journal-title":"Auton. Agents Multi-Agent Syst."},{"issue":"6","key":"6_CR10","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1016\/j.ijar.2009.02.008","volume":"50","author":"E Bonzon","year":"2009","unstructured":"Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J.: Dependencies between players in boolean games. Int. J. Approximate Reasoning 50(6), 899\u2013914 (2009)","journal-title":"Int. J. Approximate Reasoning"},{"issue":"1 Supplement","key":"6_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s11229-012-0130-y","volume":"187","author":"E Bonzon","year":"2012","unstructured":"Bonzon, E., Lagasquie-Schiex, M.-C., Lang, J.: Effectivity functions and efficient coalitions in boolean games. Synthese 187(1 Supplement), 73\u2013103 (2012)","journal-title":"Synthese"},{"issue":"3","key":"6_CR12","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.jcss.2008.09.001","volume":"75","author":"F Brandt","year":"2009","unstructured":"Brandt, F., Fischer, F., Holzer, M.: Symmetries and the complexity of pure nash equilibrium. J. Comput. Syst. Sci. 75(3), 163\u2013177 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF00934872","volume":"13","author":"J Case","year":"1974","unstructured":"Case, J.: A class of games having pareto optimal nash equilibria. J. Optim. Theory Appl. 13, 379\u2013385 (1974)","journal-title":"J. Optim. Theory Appl."},{"issue":"3","key":"6_CR14","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of two-player nash equilibria. J. ACM 56(3), 14 (2009)","journal-title":"J. ACM"},{"issue":"1","key":"6_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1004911723951","volume":"43","author":"AM Colman","year":"1997","unstructured":"Colman, A.M., Bacharach, M.: Payoff dominance and the stackelberg heuristic. Theory Decis. 43(1), 1\u201319 (1997)","journal-title":"Theory Decis."},{"issue":"2","key":"6_CR16","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.geb.2008.02.015","volume":"63","author":"V Conitzer","year":"2008","unstructured":"Conitzer, V., Sandholm, T.: Complexity results about nash equilibria. Game. Econ. Behav. 63(2), 621\u2013641 (2008)","journal-title":"Game. Econ. Behav."},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/11786986_45","volume-title":"Automata, Languages and Programming","author":"C Daskalakis","year":"2006","unstructured":"Daskalakis, C., Fabrikant, A., Papadimitriou, C.: The game world is flat: the complexity of nash equilibria in succinct games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 513\u2013524. Springer, Heidelberg (2006)"},{"issue":"1","key":"6_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/11561071_9","volume-title":"Algorithms \u2013 ESA 2005","author":"K Daskalakis","year":"2005","unstructured":"Daskalakis, K., Papadimitriou, C.: The complexity of games on highly regular graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 71\u201382. Springer, Heidelberg (2005)"},{"issue":"4","key":"6_CR20","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1287\/moor.1080.0322","volume":"33","author":"J Dunkel","year":"2008","unstructured":"Dunkel, J., Schulz, A.S.: On the complexity of pure-strategy nash equilibria in congestion and local-effect games. MatH. Oper. Res. 33(4), 851\u2013868 (2008)","journal-title":"MatH. Oper. Res."},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-540-30227-8_30","volume-title":"Logics in Artificial Intelligence","author":"PE Dunne","year":"2004","unstructured":"Dunne, P.E., van der Hoek, W.: Representation and complexity in boolean games. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 347\u2013359. Springer, Heidelberg (2004)"},{"key":"6_CR22","unstructured":"Dunne, P.E., Wooldridge, M.: Towards tractable boolean games. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 939\u2013946, June 2012"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 604\u2013612, June 2004","DOI":"10.1145\/1007352.1007445"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Feigenbaum, J., Koller, D., Shor, P.: A game-theoretic classification of interactive complexity classes. In: Proceedings of the 10th Annual IEEE Conference on Structure in Complexity Theory, pp. 227\u2013237, June 1995","DOI":"10.1109\/SCT.1995.514861"},{"issue":"6","key":"6_CR25","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.ipl.2006.03.010","volume":"99","author":"F Fischer","year":"2006","unstructured":"Fischer, F., Holzer, M., Katzenbeisser, S.: The influence of neighbourhood and choice on the complexity of finding pure nash equilibria. Inf. Process. Lett. 99(6), 239\u2013245 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"6_CR26","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00037-008-0252-2","volume":"17","author":"L Fortnow","year":"2008","unstructured":"Fortnow, L., Impagliazzo, R., Kabanets, V., Umans, C.: On the complexity of succinct zero-sum games. Comput. Complex. 17(3), 353\u2013376 (2008)","journal-title":"Comput. Complex."},{"issue":"2\u20133","key":"6_CR27","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/j.tcs.2005.09.024","volume":"348","author":"D Fotakis","year":"2005","unstructured":"Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish unsplittable flows. Theoret. Comput. Sci. 348(2\u20133), 226\u2013239 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"48","key":"6_CR28","doi-asserted-by":"publisher","first-page":"6675","DOI":"10.1016\/j.tcs.2011.07.022","volume":"412","author":"J Gabarr\u00f3","year":"2011","unstructured":"Gabarr\u00f3, J., Garc\u00eda, A., Serna, M.: The complexity of game isomorphism. Theoret. Comput. Sci. 412(48), 6675\u20136695 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"6_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1978782.1978786","volume":"7","author":"M Gairing","year":"2011","unstructured":"Gairing, M., Monien, B., Tiemann, K.: Routing (un-)splittable flow in games with player-specific linear latency functions. ACM Trans. Algorithms 7(3), 31 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"6_CR30","series-title":"Annals of Mathematics Studies","volume-title":"On symmetric games. Contributions to the Theory of Games","author":"D Gale","year":"1950","unstructured":"Gale, D., Kuhn, H.W., Tucker, A.W.: On symmetric games. Contributions to the Theory of Games. Annals of Mathematics Studies, vol. 24. Princeton University Press, Princeton (1950)"},{"key":"6_CR31","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1613\/jair.1683","volume":"24","author":"G Gottlob","year":"2005","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: Pure nash equilibria: hard and easy games. J. Artif. Intell. Res. 24, 357\u2013406 (2005)","journal-title":"J. Artif. Intell. Res."},{"key":"6_CR32","unstructured":"Harrenstein, P., van der Hoek, W., Meyer, J.-J., Witteveen, C.: Boolean games. In: Proceedings of the 8th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 287\u2013298, July 2001"},{"key":"6_CR33","unstructured":"Harrenstein, P.: Logic in conflict, Ph.D. thesis, Utrecht University (2004)"},{"key":"6_CR34","volume-title":"A General Theory of Equilibrium Selection in Games","author":"JC Harsanyi","year":"1988","unstructured":"Harsanyi, J.C., Selten, R.: A General Theory of Equilibrium Selection in Games. The MIT Press, Cambridge (1988)"},{"issue":"6","key":"6_CR35","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/268999.269002","volume":"44","author":"E Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Exact analysis of dodgson elections: lewis carroll\u2019s 1876 voting system is complete for parallel access to $${\\cal {NP}}$$ . J. ACM 44(6), 806\u2013825 (1997)","journal-title":"J. ACM"},{"issue":"5","key":"6_CR36","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1287\/mnsc.18.5.312","volume":"18","author":"JT Howson","year":"1972","unstructured":"Howson, J.T.: Equilibria of polymatrix games(Part I). Manag. Sci. 18(5), 312\u2013318 (1972)","journal-title":"Manag. Sci."},{"key":"6_CR37","unstructured":"Ianovski, E.: $${ \\text{ DValue }}$$ for boolean games is $${\\cal EXP}$$ -Hard. In: CoRR, abs\/1403.7428 (2014)"},{"key":"6_CR38","unstructured":"Ianovski, E., Ong, L.: $$\\exists { \\text{ GuaranteeNash }}$$ is $${\\cal NEXP}$$ -Hard. In: Proceedings of the 14th International Conference on Knowledge Representation and Reasoning, July 2014"},{"issue":"1","key":"6_CR39","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"6_CR40","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01770226","volume":"14","author":"E Kalai","year":"1985","unstructured":"Kalai, E., Samet, D.: Unanimity games and pareto optimality. Int. J. Game Theory 14(1), 41\u201350 (1985)","journal-title":"Int. J. Game Theory"},{"key":"6_CR41","unstructured":"Kearns, M.J., Littman, M.L., Singh, S.P.: Graphical models for game theory. In: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, pp. 253\u2013260, August 2001"},{"issue":"1","key":"6_CR42","first-page":"21","volume":"9","author":"VM Krapchenko","year":"1971","unstructured":"Krapchenko, V.M.: Complexity of the realization of a linear function in the class of $$\\Pi $$ -circuits. Math. Notes Acad. Sci. USSR 9(1), 21\u201323 (1971)","journal-title":"Math. Notes Acad. Sci. USSR"},{"issue":"3","key":"6_CR43","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"MW Krentel","year":"1988","unstructured":"Krentel, M.W.: The complexity of optimization problems. J. Comput. Syst. Sci. 36(3), 490\u2013509 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR44","unstructured":"Leyton-Brown, K., Tennenholtz, M.: Local-effect games. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence, pp. 772\u2013780, August 2003"},{"key":"6_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/978-3-540-74456-6_56","volume-title":"Mathematical Foundations of Computer Science 2007","author":"M Mavronicolas","year":"2007","unstructured":"Mavronicolas, M., Milchtaich, I., Monien, B., Tiemann, K.: Congestion games with player-specific constants. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 633\u2013644. Springer, Heidelberg (2007)"},{"key":"6_CR46","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. In: Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory, pp. 125\u2013129, October 1972","DOI":"10.1109\/SWAT.1972.29"},{"issue":"1","key":"6_CR47","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/game.1996.0027","volume":"13","author":"I Milchtaich","year":"1996","unstructured":"Milchtaich, I.: Congestion games with player-specific payoff functions. Game. Econ. Behav. 13(1), 111\u2013124 (1996)","journal-title":"Game. Econ. Behav."},{"issue":"1","key":"6_CR48","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."},{"key":"6_CR49","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, 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"6_CR50","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Boston (1994)"},{"issue":"3","key":"6_CR51","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1379759.1379762","volume":"55","author":"CH Papadimitriou","year":"2008","unstructured":"Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. ACM 55(3), 14 (2008)","journal-title":"J. ACM"},{"key":"6_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BFb0009651","volume-title":"Theoretical Computer Science","author":"CH Papadimitriou","year":"1983","unstructured":"Papadimitriou, C.H., Zachos, S.: Two remarks on the power of counting. In: Cremers, A.B., Kriegel, H.-P. (eds.) Theoretical Computer Science. LNCS, vol. 145, pp. 269\u2013275. Springer, Heidelberg (1983)"},{"issue":"3","key":"6_CR53","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/0304-3975(76)90090-6","volume":"2","author":"M Paterson","year":"1976","unstructured":"Paterson, M., Valiant, L.G.: Circuit size is nonlinear in depth. Theoret. Comput. Sci. 2(3), 397\u2013400 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"6_CR54","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0206030","volume":"6","author":"W Paul","year":"1977","unstructured":"Paul, W.: A 2.5 lower bound on the combinatorial complexity of boolean functions. SIAM J. Comput. 6(3), 427\u2013443 (1977)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"6_CR55","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"},{"issue":"4","key":"6_CR56","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S Sahni","year":"1974","unstructured":"Sahni, S.: Computationally related problems. SIAM J. Comput. 3(4), 262\u2013279 (1974)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"6_CR57","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/2189778.2189779","volume":"4","author":"G Schoenebeck","year":"2012","unstructured":"Schoenebeck, G., Vadhan, S.: The computational complexity of nash equilibria in concisely represented games. ACM Trans. Comput. Theory 4(2), 4 (2012)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"6_CR58","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"LJ Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial time hierarchy. Theoret. Comput. Sci. 3(1), 1\u201322 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"6_CR59","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1006\/inco.1995.1109","volume":"120","author":"H Vollmer","year":"1995","unstructured":"Vollmer, H., Wagner, K.W.: Complexity classes of optimization functions. Inf. Comput. 120(2), 198\u2013218 (1995)","journal-title":"Inf. Comput."},{"issue":"3\u20134","key":"6_CR60","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1142\/S0219198999000219","volume":"1","author":"M Voorneveld","year":"1999","unstructured":"Voorneveld, M., Borm, P., van Megan, F., Tijs, S., Facchini, G.: Congestion games and potentials reconsidered. Int. Game Theory Rev. 1(3\u20134), 283\u2013299 (1999)","journal-title":"Int. Game Theory Rev."},{"issue":"1\u20132","key":"6_CR61","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"KW Wagner","year":"1987","unstructured":"Wagner, K.W.: More complicated questions about maxima and minima, and some closures of $${\\cal NP}$$ . Theoret. Comput. Sci. 51(1\u20132), 53\u201380 (1987)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"6_CR62","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"KW Wagner","year":"1990","unstructured":"Wagner, K.W.: Bounded query classes. SIAM J. Comput. 19(5), 833\u2013846 (1990)","journal-title":"SIAM J. Comput."},{"key":"6_CR63","volume-title":"The Complexity of Boolean Functions","author":"I Wegener","year":"1991","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley, New York (1991)"},{"issue":"1","key":"6_CR64","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C Wrathall","year":"1976","unstructured":"Wrathall, C.: Complete sets and the polynomial time hierarchy. Theoret. Comput. Sci. 3(1), 23\u201333 (1976)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms, Probability, Networks, and Games"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24024-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T12:21:06Z","timestamp":1748607666000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24024-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319240237","9783319240244"],"references-count":64,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24024-4_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}