{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:17:12Z","timestamp":1760203032834,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030995232"},{"type":"electronic","value":"9783030995249"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"vor","delay-in-days":88,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In<jats:italic>rational synthesis<\/jats:italic>, we automatically construct a reactive system that satisfies its specification in all rational environments, namely environments that have objectives and act to fulfill them. We complete the study of the complexity of LTL rational synthesis. Our contribution is threefold. First, we tighten the known upper bounds for settings that were left open in earlier work. Second, our complexity analysis is parametric, and we describe tight upper and lower bounds in each of the problem parameters: the game graph, the objectives of the system components, and the objectives of the environment components. Third, we generalize the definition of rational synthesis, combining the cooperative and non-cooperative approaches studied in earlier work, and extend our complexity analysis to the general definition.<\/jats:p>","DOI":"10.1007\/978-3-030-99524-9_2","type":"book-chapter","created":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T06:14:55Z","timestamp":1648534495000},"page":"25-45","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The Complexity of LTL Rational Synthesis"],"prefix":"10.1007","author":[{"given":"Orna","family":"Kupferman","sequence":"first","affiliation":[]},{"given":"Noam","family":"Shenwald","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,30]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Almagor, S., Kupferman, O., Perelli, G.: Synthesis of controllable Nash equilibria in quantitative objective game. In: Proc. 27th Int. Joint Conf. on Artificial Intelligence. pp. 35\u201341 (2018)","key":"2_CR1","DOI":"10.24963\/ijcai.2018\/5"},{"doi-asserted-by":"crossref","unstructured":"Alur, R., Henzinger, T., Kupferman, O.: Alternating-time temporal logic. Journal of the ACM 49(5), 672\u2013713 (2002)","key":"2_CR2","DOI":"10.1145\/585265.585270"},{"doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proc. 45th IEEE Symp. on Foundations of Computer Science. pp. 295\u2013304. IEEE Computer Society (2004)","key":"2_CR3","DOI":"10.1109\/FOCS.2004.68"},{"doi-asserted-by":"crossref","unstructured":"Bouyer-Decitre, P., Kupferman, O., Markey, N., Maubert, B., Murano, A., Perelli, G.: Reasoning about quality and fuzziness of strategic behaviours. In: Proc. 28th Int. Joint Conf. on Artificial Intelligence. pp. 1588\u20131594 (2019)","key":"2_CR4","DOI":"10.24963\/ijcai.2019\/220"},{"doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T., Jobstmann, B.: Environment assumptions for synthesis. In: Proc. 19th Int. Conf. on Concurrency Theory. Lecture Notes in Computer Science, vol.\u00a05201, pp. 147\u2013161. Springer (2008)","key":"2_CR5","DOI":"10.1007\/978-3-540-85361-9_14"},{"doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A., Piterman, N.: Strategy logic. In: Proc. 18th Int. Conf. on Concurrency Theory. pp. 59\u201373 (2007)","key":"2_CR6","DOI":"10.1007\/978-3-540-74407-8_5"},{"doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Majumdar, R., Jurdzinski, M.: On Nash equilibria in stochastic games. In: Proc. 13th Annual Conf. of the European Association for Computer Science Logic. Lecture Notes in Computer Science, vol. 3210, pp. 26\u201340. Springer (2004)","key":"2_CR7","DOI":"10.1007\/978-3-540-30124-0_6"},{"unstructured":"Church, A.: Logic, arithmetics, and automata. In: Proc. Int. Congress of Mathematicians, 1962. pp. 23\u201335. Institut Mittag-Leffler (1963)","key":"2_CR8"},{"unstructured":"Condurache, R., Filiot, E., Gentilini, R., Raskin, J.F.: The complexity of rational synthesis. In: Proc. 43th Int. Colloq. on Automata, Languages, and Programming. LIPIcs, vol. 55, pp. 121:1\u2013121:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)","key":"2_CR9"},{"doi-asserted-by":"crossref","unstructured":"Emerson, E., Jutla, C.: The complexity of tree automata and logics of programs. In: Proc. 29th IEEE Symp. on Foundations of Computer Science. pp. 328\u2013337 (1988)","key":"2_CR10","DOI":"10.1109\/SFCS.1988.21949"},{"doi-asserted-by":"crossref","unstructured":"Fisman, D., Kupferman, O., Lustig, Y.: Rational synthesis. In: Proc. 16th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science, vol.\u00a06015, pp. 190\u2013204. Springer (2010)","key":"2_CR11","DOI":"10.1007\/978-3-642-12002-2_16"},{"doi-asserted-by":"crossref","unstructured":"Gutierrez, J., Najib, M., Perelli, G., Wooldridge, M.: On computational tractability for rational verification. In: Proc. 28th Int. Joint Conf. on Artificial Intelligence. pp. 329\u2013335. International Joint Conferences on Artificial Intelligence Organization (2019)","key":"2_CR12","DOI":"10.24963\/ijcai.2019\/47"},{"doi-asserted-by":"crossref","unstructured":"Gutierrez, J., Perelli, G., Wooldridge, M.J.: Imperfect information in reactive modules games. Inf. Comput. 261, 650\u2013675 (2018)","key":"2_CR13","DOI":"10.1016\/j.ic.2018.02.023"},{"unstructured":"Kupferman, O., Lustig, Y., Vardi, M., Yannakakis, M.: Temporal synthesis for bounded systems and environments. In: Proc. 28th Symp. on Theoretical Aspects of Computer Science. pp. 615\u2013626 (2011)","key":"2_CR14"},{"doi-asserted-by":"crossref","unstructured":"Kupferman, O., Perelli, G., Vardi, M.: Synthesis with rational environments. Annals of Mathematics and Artificial Intelligence 78(1), 3\u201320 (2016)","key":"2_CR15","DOI":"10.1007\/s10472-016-9508-8"},{"doi-asserted-by":"crossref","unstructured":"Kupferman, O., Piterman, N.: Lower bounds on witnesses for nonemptiness of universal co-B\u00fcchi automata. In: Proc. 12th Int. Conf. on Foundations of Software Science and Computation Structures. Lecture Notes in Computer Science, vol.\u00a05504, pp. 182\u2013196. Springer (2009)","key":"2_CR16","DOI":"10.1007\/978-3-642-00596-1_14"},{"unstructured":"Kupferman, O., Shenwald, N.: Perspective games with notifications. In: Proc. 40th Conf. on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, vol. 182, pp. 51:1\u201351:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)","key":"2_CR17"},{"doi-asserted-by":"crossref","unstructured":"Kupferman, O., Shenwald, N.: Perspective multi-player games. In: Proc. 36th IEEE Symp. on Logic in Computer Science (2021)","key":"2_CR18","DOI":"10.1109\/LICS52264.2021.9470616"},{"doi-asserted-by":"crossref","unstructured":"Kupferman, O., Vardi, G.: Perspective games. In: Proc. 34th IEEE Symp. on Logic in Computer Science. pp. 1 \u2013 13 (2019)","key":"2_CR19","DOI":"10.1109\/LICS.2019.8785662"},{"doi-asserted-by":"crossref","unstructured":"Kupferman, O., Vardi, M.: Safraless decision procedures. In: Proc. 46th IEEE Symp. on Foundations of Computer Science. pp. 531\u2013540 (2005)","key":"2_CR20","DOI":"10.1109\/SFCS.2005.66"},{"unstructured":"Nash, J.: Equilibrium points in $$n$$-person games. In: Proceedings of the National Academy of Sciences of the United States of America (1950)","key":"2_CR21"},{"doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.: Algorithmic Game Theory. Cambridge University Press (2007)","key":"2_CR22","DOI":"10.1017\/CBO9780511800481"},{"doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Algorithms, games, and the internet. In: Proc. 33rd ACM Symp. on Theory of Computing. pp. 749\u2013753 (2001)","key":"2_CR23","DOI":"10.1145\/380752.380883"},{"doi-asserted-by":"crossref","unstructured":"Pnueli, A.: The temporal semantics of concurrent programs. Theoretical Computer Science 13, 45\u201360 (1981)","key":"2_CR24","DOI":"10.1016\/0304-3975(81)90110-9"},{"doi-asserted-by":"crossref","unstructured":"Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: Proc. 16th ACM Symp. on Principles of Programming Languages. pp. 179\u2013190 (1989)","key":"2_CR25","DOI":"10.1145\/75277.75293"},{"doi-asserted-by":"crossref","unstructured":"Vardi, M., Wolper, P.: Automata-theoretic techniques for modal logics of programs. Journal of Computer and Systems Science 32(2), 182\u2013221 (1986)","key":"2_CR26","DOI":"10.1016\/0022-0000(86)90026-7"},{"doi-asserted-by":"crossref","unstructured":"Wooldridge, M., Gutierrez, J., Harrenstein, P., Marchioni, E., Perelli, G., Toumi, A.: Rational verification: From model checking to equilibrium checking. In: Proc. of 30th National Conf. on Artificial Intelligence. pp. 4184\u20134190 (2016)","key":"2_CR27","DOI":"10.1609\/aaai.v30i1.9878"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-99524-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T05:09:23Z","timestamp":1726895363000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-99524-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030995232","9783030995249"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-99524-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"30 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 April 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 April 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2022\/tacas","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"159","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"16 tool papers of the affiliated competition SV-Comp and 1 paper consisting of the competition report are also included in the proceedings","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}