{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:03Z","timestamp":1787017383453,"version":"3.56.0"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,4,1]],"date-time":"2021-04-01T00:00:00Z","timestamp":1617235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:p>In this survey, we propose a comprehensive introduction to game theory applied to computer-aided synthesis. We study multi-player turn-based infinite-duration games played on a finite directed graph such that each player aims at maximizing a payoff function. We present the well-known notions of Nash equilibrium and subgame perfect equilibrium, as well as interesting strategy profiles of players as response to the strategy announced by a specific player. We provide classical and recent results about the related threshold synthesis problem.<\/jats:p>","DOI":"10.1145\/3467001.3467003","type":"journal-article","created":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T18:04:31Z","timestamp":1621533871000},"page":"4-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Synthesis of equilibria in infinite-duration games on graphs"],"prefix":"10.1145","volume":"8","author":[{"given":"V\u00e9ronique","family":"Bruy\u00e8re","sequence":"first","affiliation":[{"name":"University of Mons (UMONS)"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,5,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585270"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/5"},{"key":"e_1_2_1_3_1","volume-title":"Fragility and Robustness in Mean-payoff Adversarial Stackelberg Games. CoRR abs\/2007.07209","author":"Balachander Mrudula","year":"2020","unstructured":"Mrudula Balachander , Shibashis Guha , and Jean-Francois Raskin . 2020. Fragility and Robustness in Mean-payoff Adversarial Stackelberg Games. CoRR abs\/2007.07209 ( 2020 ). https:\/\/arxiv.org\/abs\/2007.07209 Mrudula Balachander, Shibashis Guha, and Jean-Francois Raskin. 2020. Fragility and Robustness in Mean-payoff Adversarial Stackelberg Games. CoRR abs\/2007.07209 (2020). https:\/\/arxiv.org\/abs\/2007.07209"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.123"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63121-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3427955"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70918-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46681-0"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.74"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-89366-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15375-4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(2:9)2015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA200437"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2014.351"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2017.2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2016.42"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-016-0273-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603143"},{"key":"e_1_2_1_20_1","volume-title":"Subgame-perfect Equilibria in Mean-payoff Games. CoRR abs\/2101.10685","author":"Brice Leonard","year":"2021","unstructured":"Leonard Brice , Jean-Francois Raskin , and Marie van den Bogaard . 2021. Subgame-perfect Equilibria in Mean-payoff Games. CoRR abs\/2101.10685 ( 2021 ). https:\/\/arxiv.org\/abs\/2101.10685 Leonard Brice, Jean-Francois Raskin, and Marie van den Bogaard. 2021. Subgame-perfect Equilibria in Mean-payoff Games. CoRR abs\/2101.10685 (2021). https:\/\/arxiv.org\/abs\/2101.10685"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.277.2"},{"key":"e_1_2_1_22_1","volume-title":"Jean-Francois Raskin, and Marie van den Bogaard.","author":"Brihaye Thomas","year":"2020","unstructured":"Thomas Brihaye , Veronique Bruye ` re, Aline Goeminne , Jean-Francois Raskin, and Marie van den Bogaard. 2020 . The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Games. Log. Methods Comput. Sci . 16, 4 (2020). https:\/\/lmcs.episciences.org\/6883 Thomas Brihaye, Veronique Bruye`re, Aline Goeminne, Jean-Francois Raskin, and Marie van den Bogaard. 2020. The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Games. Log. Methods Comput. Sci. 16, 4 (2020). https:\/\/lmcs.episciences.org\/6883"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30806-3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2015.504"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35722-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.220.1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-57628-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62809-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603109"},{"key":"e_1_2_1_30_1","volume-title":"Stackelberg-Pareto Synthesis. CoRR abs\/2102.08925","author":"Bruyere Veronique","year":"2021","unstructured":"Veronique Bruyere , Jean-Francois Raskin , and Clement Tamines . 2021a. Stackelberg-Pareto Synthesis. CoRR abs\/2102.08925 ( 2021 ). https:\/\/arxiv.org\/abs\/2102.08925 Veronique Bruyere, Jean-Francois Raskin, and Clement Tamines. 2021a. Stackelberg-Pareto Synthesis. CoRR abs\/2102.08925 (2021). https:\/\/arxiv.org\/abs\/2102.08925"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104553"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15375-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.10.012"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805950.1805953"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71209-1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.07.032"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.07.004"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30124-0"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-013-0283-6"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-019-01199-3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.121"},{"key":"e_1_2_1_42_1","first-page":"765","volume-title":"Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence","author":"Conitzer Vincent","year":"2003","unstructured":"Vincent Conitzer and Tuomas Sandholm . 2003 . Complexity Results about Nash Equilibria. In IJCAI-03 , Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence , Acapulco, Mexico , August 9-15, 2003, Georg Gottlob and Toby Walsh (Eds.). Morgan Kaufmann, 765 - 771 . http:\/\/ijcai.org\/ Proceedings\/03\/Papers\/111.pdf Vincent Conitzer and Tuomas Sandholm. 2003. Complexity Results about Nash Equilibria. In IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9-15, 2003, Georg Gottlob and Toby Walsh (Eds.). Morgan Kaufmann, 765-771. http:\/\/ijcai.org\/ Proceedings\/03\/Papers\/111.pdf"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44465-8"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_2_1_45_1","volume-title":"Competitive Markov Decision Processes","author":"Filar Jerzy","unstructured":"Jerzy Filar and Koos Vrieze . 1997. Competitive Markov Decision Processes . Springer . Jerzy Filar and Koos Vrieze. 1997. Competitive Markov Decision Processes. Springer."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209164"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.127"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12002-2"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0469"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2015.0774"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0843"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/11539452"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.105996"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36387-4"},{"key":"e_1_2_1_55_1","first-page":"151","volume-title":"New Perspectives on Games and Interaction","volume":"4","author":"Gradel Erich","year":"2008","unstructured":"Erich Gradel and Michael Ummels . 2008 . Solution Concepts and Algorithms for Infinite Multiplayer Games . In New Perspectives on Games and Interaction , Vol. 4 . Amsterdam University Press , 151 - 178 . Erich Gradel and Michael Ummels. 2008. Solution Concepts and Algorithms for Infinite Multiplayer Games. In New Perspectives on Games and Interaction, Vol. 4. Amsterdam University Press, 151-178."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2014.9"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.193.2"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/148"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103353"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.023"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911658"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28332-1"},{"key":"e_1_2_1_63_1","volume-title":"Extensive games and the problem of information. Classics in Game Theory","author":"Kuhn Harold W.","year":"1953","unstructured":"Harold W. Kuhn . 1953. Extensive games and the problem of information. Classics in Game Theory ( 1953 ), 46-68. Harold W. Kuhn. 1953. Extensive games and the problem of information. Classics in Game Theory (1953), 46-68."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-016-9508-8"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2631917"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0504"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(2:3)2013"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104557"},{"key":"e_1_2_1_70_1","first-page":"301","article-title":"Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetragheit","volume":"121","author":"Selten Reinhard","year":"1965","unstructured":"Reinhard Selten . 1965 . Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetragheit . Zeitschrift fur die gesamte Staatswissenschaft 121 (1965), 301 - 324 and 667-689. Reinhard Selten. 1965. Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetragheit. Zeitschrift fur die gesamte Staatswissenschaft 121 (1965), 301-324 and 667-689.","journal-title":"Zeitschrift fur die gesamte Staatswissenschaft"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4068(03)00021-1"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944836"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78499-9"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23217-6"},{"key":"e_1_2_1_75_1","volume-title":"The Complexity of Nash Equilibria in Limit-Average Games. CoRR abs\/1109.6220","author":"Ummels Michael","year":"2011","unstructured":"Michael Ummels and Dominik Wojtczak . 2011b. The Complexity of Nash Equilibria in Limit-Average Games. CoRR abs\/1109.6220 ( 2011 ). http:\/\/arxiv.org\/abs\/1109.6220 Michael Ummels and Dominik Wojtczak. 2011b. The Complexity of Nash Equilibria in Limit-Average Games. CoRR abs\/1109.6220 (2011). http:\/\/arxiv.org\/abs\/1109.6220"},{"key":"e_1_2_1_76_1","volume-title":"Theory of Games and Economic Behavior","author":"von Neumann John","unstructured":"John von Neumann and Oskar Morgenstern . 1944. Theory of Games and Economic Behavior . Princeton University Press . John von Neumann and Oskar Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press."},{"key":"e_1_2_1_77_1","volume-title":"Marktform und Gleichgewicht. Wien und Berlin","author":"von Stackelberg Heinrich Freiherr","unstructured":"Heinrich Freiherr von Stackelberg . 1937. Marktform und Gleichgewicht. Wien und Berlin , J. Springer . Heinrich Freiherr von Stackelberg. 1937. Marktform und Gleichgewicht. Wien und Berlin, J. Springer."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3467001.3467003","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3467001.3467003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:25:06Z","timestamp":1750181106000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3467001.3467003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4]]},"references-count":78,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["10.1145\/3467001.3467003"],"URL":"https:\/\/doi.org\/10.1145\/3467001.3467003","relation":{},"ISSN":["2372-3491"],"issn-type":[{"value":"2372-3491","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4]]},"assertion":[{"value":"2021-05-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}