{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:49Z","timestamp":1750309129322,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T00:00:00Z","timestamp":1713225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"PDR"},{"name":"ARC"},{"name":"EOS"},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            We study the framework of two-player Stackelberg games played on graphs in which Player\u00a00 announces a strategy and Player\u00a01 responds rationally with a strategy that is an optimal response. While it is usually assumed that Player\u00a01 has a single objective, we consider here the new setting where he has several. In this context, after responding with his strategy, Player\u00a01 gets a payoff in the form of a vector of Booleans corresponding to his satisfied objectives. Rationality of Player\u00a01 is encoded by the fact that his response must produce a Pareto-optimal payoff given the strategy of Player\u00a00. We study for several kinds of \u03c9-regular objectives the Stackelberg-Pareto Synthesis problem which asks whether Player\u00a00 can announce a strategy which satisfies his objective, whatever the rational response of Player\u00a01. We show that this problem is fixed-parameter tractable for games in which objectives are all reachability, safety, B\u00fcchi, co-B\u00fcchi, Boolean B\u00fcchi, parity, Muller, Streett, or Rabin objectives. We also show that this problem is\n            <jats:sans-serif>NEXPTIME<\/jats:sans-serif>\n            -complete except for the cases of B\u00fcchi objectives for which it is\n            <jats:sans-serif>NP<\/jats:sans-serif>\n            -complete and co-B\u00fcchi objectives for which it is in\n            <jats:sans-serif>NEXPTIME<\/jats:sans-serif>\n            and\n            <jats:sans-serif>NP<\/jats:sans-serif>\n            -hard. The problem is already\n            <jats:sans-serif>NP<\/jats:sans-serif>\n            -complete in the simple case of reachability objectives and graphs that are trees.\n          <\/jats:p>","DOI":"10.1145\/3651162","type":"journal-article","created":{"date-parts":[[2024,3,9]],"date-time":"2024-03-09T09:42:29Z","timestamp":1709977349000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Stackelberg-Pareto Synthesis"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9680-9140","authenticated-orcid":false,"given":"V\u00e9ronique","family":"Bruy\u00e8re","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Mons (UMONS), Mons, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4925-1105","authenticated-orcid":false,"given":"Baptiste","family":"Fievet","sequence":"additional","affiliation":[{"name":"Institut Galil\u00e9e, Universit\u00e9 Sorbonne Paris Nord, Villetaneuse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3673-1097","authenticated-orcid":false,"given":"Jean-Fran\u00e7ois","family":"Raskin","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles (ULB), Bruxelles, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1104-911X","authenticated-orcid":false,"given":"Cl\u00e9ment","family":"Tamines","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Mons (UMONS), Mons, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2021.9"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/13"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70918-3_17"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10575-8_27"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(2:9)2015"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9_1"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2015.100"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2021.8"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.MFCS.2023.26"},{"issue":"4","key":"e_1_3_3_11_2","article-title":"The complexity of subgame perfect equilibria in quantitative reachability games","volume":"16","author":"Brihaye Thomas","year":"2020","unstructured":"Thomas Brihaye, V\u00e9ronique Bruy\u00e8re, Aline Goeminne, Jean-Fran\u00e7ois Raskin, and Marie van den Bogaard. 2020. The complexity of subgame perfect equilibria in quantitative reachability games. Logical Methods in Computer Science 16, 4 (2020). Retrieved from https:\/\/lmcs.episciences.org\/6883","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-45286-4_6"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62809-7_1"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3467001.3467003"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2016.11"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2018.29"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2021.27"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1145288"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2597631"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71209-1_21"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.07.032"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.07.004"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.121"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.06.009"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/2464827"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614939"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.127"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12002-2_16"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36387-4"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2014.9"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.193.2"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/47"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103353"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2008.1756"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10575-8_4"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-016-9508-8"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_2"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2631917"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75293"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59152-6_7"},{"key":"e_1_3_3_44_2","first-page":"301\u2013324 and iss","article-title":"Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetr\u00e4gheit","volume":"121","author":"Selten Reinhard","year":"1965","unstructured":"Reinhard Selten. 1965. Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetr\u00e4gheit. Zeitschrift f\u00fcr die gesamte Staatswissenschaft 121 (1965), issue 2, 301\u2013324 and issue 4, 667\u2013689.","journal-title":"Zeitschrift f\u00fcr die gesamte Staatswissenschaft"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814619"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/11944836_21"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78499-9_3"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23217-6_32"},{"key":"e_1_3_3_49_2","volume-title":"Marktform und Gleichgewicht","author":"Stackelberg Heinrich Freiherr von","year":"1937","unstructured":"Heinrich Freiherr von Stackelberg. 1937. Marktform und Gleichgewicht. Wien und Berlin, J. Springer, Cambridge, MA."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651162","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:53Z","timestamp":1750286993000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,16]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3651162"],"URL":"https:\/\/doi.org\/10.1145\/3651162","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2024,4,16]]},"assertion":[{"value":"2023-04-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}