{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:41:18Z","timestamp":1764402078565,"version":"3.46.0"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031906527"},{"type":"electronic","value":"9783031906534"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T00:00:00Z","timestamp":1746057600000},"content-version":"vor","delay-in-days":120,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We introduce and study\n                    <jats:italic>non-zero-sum multi-player games<\/jats:italic>\n                    with\n                    <jats:italic>weighted multiple objectives<\/jats:italic>\n                    . In these games, the objective of each player consists of a set\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\alpha $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b1<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of underlying objectives and a weight function\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$w: 2^\\alpha \\rightarrow \\mathbb {Z}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>w<\/mml:mi>\n                            <mml:mo>:<\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>2<\/mml:mn>\n                              <mml:mi>\u03b1<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>\u2192<\/mml:mo>\n                            <mml:mi>Z<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    that maps each subset\n                    <jats:italic>X<\/jats:italic>\n                    of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\alpha $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b1<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    to the utility of the player when exactly all the objectives in\n                    <jats:italic>X<\/jats:italic>\n                    are satisfied.\n                  <\/jats:p>\n                  <jats:p>\n                    We study the existence and synthesis of\n                    <jats:italic>stable outcomes<\/jats:italic>\n                    with\n                    <jats:italic>desired utilities<\/jats:italic>\n                    for the players. The problem generalizes rational synthesis and enables the synthesis of outcomes that satisfy wellness, fairness, and priority requirements.\n                  <\/jats:p>\n                  <jats:p>\n                    We study the extension of the game by\n                    <jats:italic>payments<\/jats:italic>\n                    , with which players can incentivize each other to follow strategies that are beneficial for the paying player. We show how such payments can be used in order to\n                    <jats:italic>repair<\/jats:italic>\n                    systems. We study the complexity of the setting for various classes of weight functions. In particular, general weight functions are related to Muller objectives, and the synthesis problem for them is PSPACE-complete. We study non-decreasing, additive, positive, and other classes of weight functions, and the way they affect the memory required for the players and the complexity of the synthesis problem.\n                  <\/jats:p>","DOI":"10.1007\/978-3-031-90653-4_15","type":"book-chapter","created":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T07:22:39Z","timestamp":1746170559000},"page":"303-322","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-Zero-Sum Games with Multiple Weighted Objectives"],"prefix":"10.1007","author":[{"given":"Yoav","family":"Feinstein","sequence":"first","affiliation":[]},{"given":"Orna","family":"Kupferman","sequence":"additional","affiliation":[]},{"given":"Noam","family":"Shenwald","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,1]]},"reference":[{"key":"15_CR1","unstructured":"S.\u00a0Almagor, G.\u00a0Avni, and O.\u00a0Kupferman. Repairing multi-player games. In Proc. 26th Int. Conf. on Concurrency Theory, volume\u00a042 of LIPIcs, pages 325\u2013339, 2015."},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"S. Almagor, U. Boker, and O. Kupferman. Formalizing and reasoning about quality. In Proc. 40th Int. Colloq. on Automata, Languages, and Programming, volume 7966 of Lecture Notes in Computer Science, pages 15 \u2013 27. Springer, 2013.","DOI":"10.1007\/978-3-642-39212-2_3"},{"key":"15_CR3","unstructured":"S.\u00a0Almagor and O.\u00a0Kupferman. High-quality synthesis against stochastic environments. In Proc. 25th Annual Conf. of the European Association for Computer Science Logic, volume\u00a062 of LIPIcs, pages 28:1\u201328:17, 2016."},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"S.\u00a0Almagor, O.\u00a0Kupferman, and G.\u00a0Perelli. Synthesis of controllable Nash equilibria in quantitative objective game. In Proc. 27th Int. Joint Conf. on Artificial Intelligence, pages 35\u201341, 2018.","DOI":"10.24963\/ijcai.2018\/5"},{"key":"15_CR5","unstructured":"G.\u00a0Avni, T.\u00a0A. Henzinger, and V.\u00a0Chonev. Infinite-duration bidding games. In Proc. 28th Int. Conf. on Concurrency Theory, volume\u00a085 of LIPIcs, pages 21:1\u201321:18, 2017."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"G. Avni and O. Kupferman. Synthesis from component libraries with costs. Theor. Comput. Sci., 712:50\u201372, 2018.","DOI":"10.1016\/j.tcs.2017.11.001"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"R.\u00a0Bloem, K.\u00a0Chatterjee, T.\u00a0Henzinger, and B.\u00a0Jobstmann. Better quality in synthesis through quantitative objectives. In Proc. 21st Int. Conf. on Computer Aided Verification, volume 5643 of Lecture Notes in Computer Science, pages 140\u2013156. Springer, 2009.","DOI":"10.1007\/978-3-642-02658-4_14"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"R.\u00a0Bloem, K.\u00a0Chatterjee, and B.\u00a0Jobstmann. Graph games and reactive synthesis. In Handbook of Model Checking., pages 921\u2013962. Springer, 2018.","DOI":"10.1007\/978-3-319-10575-8_27"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"A. Bohy, V. Bruy\u2018ere, E. Filiot, and J-F. Raskin. Synthesis from LTL specifications with mean-payoff objectives. In Proc. 19th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, volume 7795 of Lecture Notes in Computer Science, pages 169\u2013184. Springer, 2013.","DOI":"10.1007\/978-3-642-36742-7_12"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"P. Bouyer, R. Brenguier, N. Markey, and M. Ummels. Concurrent games with ordered objectives. In Proc. 15th Int. Conf. on Foundations of Software Science and Computation Structures, volume 7213 of Lecture Notes in Computer Science, pages 301\u2013315. Springer, 2012.","DOI":"10.1007\/978-3-642-28729-9_20"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"R. Brenguier. Robust equilibria in mean-payoff games. In Proc. 19th Int. Conf. on Foundations of Software Science and Computation Structures, volume 9634 of Lecture Notes in Computer Science, pages 217\u2013233. Springer, 2016.","DOI":"10.1007\/978-3-662-49630-5_13"},{"key":"15_CR12","unstructured":"V.\u00a0Bruy\u00e8re, C.\u00a0Grandmont, and J-F Raskin. As soon as possible but rationally. In Proc. 35th Int. Conf. on Concurrency Theory, volume 311 of LIPIcs, pages 14:1\u201314:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"key":"15_CR13","unstructured":"V.\u00a0Bruy\u00e8re, Q.\u00a0Hautem, and J-F Raskin. Parameterized complexity of games with monotonically ordered $$\\omega $$-regular objectives. In Proc. 29th Int. Conf. on Concurrency Theory, volume 118 of LIPIcs, pages 29:1\u201329:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018."},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"K. Chatterjee, A.K. Goharshady, and Y. Velner. Quantitative analysis of smart contracts. In 27th European Symposium on Programming Languages and Systems, volume 10801 of Lecture Notes in Computer Science, pages 739\u2013767. Springer, 2018.","DOI":"10.1007\/978-3-319-89884-1_26"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"K. Chatterjee, R. Majumdar, and T. A. Henzinger. Controller synthesis with budget constraints. In Proc 11th International Workshop on Hybrid Systems: Computation and Control, volume 4981 of Lecture Notes in Computer Science, pages 72\u201386. Springer, 2008.","DOI":"10.1007\/978-3-540-78929-1_6"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"K.\u00a0Chatterjee, R.\u00a0Majumdar, and M.\u00a0Jurdzinski. On Nash equilibria in stochastic games. In Proc. 13th Annual Conf. of the European Association for Computer Science Logic, volume 3210 of Lecture Notes in Computer Science, pages 26\u201340. Springer, 2004.","DOI":"10.1007\/978-3-540-30124-0_6"},{"key":"15_CR17","unstructured":"R.\u00a0Condurache, E.\u00a0Filiot, R.\u00a0Gentilini, and J.-F. Raskin. The complexity of rational synthesis. In Proc. 43th Int. Colloq. on Automata, Languages, and Programming, volume\u00a055 of LIPIcs, pages 121:1\u2013121:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2016."},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"S.\u00a0Dziembowski, M.\u00a0Jurdzinski, and I.\u00a0Walukiewicz. How much memory is needed to win infinite games. In Proc. 12th ACM\/IEEE Symp. on Logic in Computer Science, pages 99\u2013110, 1997.","DOI":"10.1109\/LICS.1997.614939"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"D. Fisman, O. Kupferman, and Y. Lustig. Rational synthesis. In Proc. 16th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, volume 6015 of Lecture Notes in Computer Science, pages 190\u2013204. Springer, 2010.","DOI":"10.1007\/978-3-642-12002-2_16"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"D.\u00a0Harel, G.\u00a0Katz, A.\u00a0Marron, and G.\u00a0Weiss. Non-intrusive repair of reactive programs. In ICECCS, pages 3\u201312, 2012.","DOI":"10.1109\/ICECCS20050.2012.6299199"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"T.A. Henzinger. From Boolean to quantitative notions of correctness. In Proc. 37th ACM Symp. on Principles of Programming Languages, pages 157\u2013158, 2010.","DOI":"10.1145\/1706299.1706319"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"P. Hunter and A. Dawar. Complexity bounds for regular games. In 30th Int. Symp. on Mathematical Foundations of Computer Science, volume 3618, pages 495\u2013506. Springer, 2005.","DOI":"10.1007\/11549345_43"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"B. Jobstmann, A. Griesmayer, and R. Bloem. Program repair as a game. In Proc. 17th Int. Conf. on Computer Aided Verification, volume 3576 of Lecture Notes in Computer Science, pages 226\u2013238, 2005.","DOI":"10.1007\/11513988_23"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"O. Kupferman, G. Perelli, and M.Y. Vardi. Synthesis with rational environments. Annals of Mathematics and Artificial Intelligence, 78(1):3\u201320, 2016.","DOI":"10.1007\/s10472-016-9508-8"},{"key":"15_CR25","unstructured":"O.\u00a0Kupferman and N.\u00a0Shenwald. Games with trading of control. In Proc. 34th Int. Conf. on Concurrency Theory, volume 279 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1\u201319:17. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2023."},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"O.\u00a0Kupferman and N.\u00a0Shenwald. Games with weighted multiple objectives. In 22nd Int. Symp. on Automated Technology for Verification and Analysis, Lecture Notes in Computer Science. Springer, 2024.","DOI":"10.1007\/978-3-031-78709-6_6"},{"key":"15_CR27","unstructured":"O.\u00a0Kupferman and T.\u00a0Tamir. Alternating reachability games with behavioral and revenue objectives. In Proc. 22nd Int. Conf. on Logic for Programming Artificial Intelligence and Reasoning, 2018."},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Y. Lustig and M.Y. Vardi. Synthesis from component libraries. Software Tools for Technology Transfer, 15(5-6):603\u2013618, 2013.","DOI":"10.1007\/s10009-012-0236-z"},{"key":"15_CR29","doi-asserted-by":"crossref","unstructured":"R. McNaughton. Infinite games played on finite graphs. Annals of Pure and Applied Logic, 65:149\u2013184, 1993.","DOI":"10.1016\/0168-0072(93)90036-D"},{"key":"15_CR30","unstructured":"J.F. Nash. Equilibrium points in $$n$$-person games. In Proceedings of the National Academy of Sciences of the United States of America, 1950."},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"J. Neumann, A. Szepietowski, and I. Walukiewicz. Complexity of weak acceptance conditions in tree automata. Inf. Process. Lett., 84(4):181\u2013187, 2002.","DOI":"10.1016\/S0020-0190(02)00285-5"},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"N.\u00a0Nisan, T.\u00a0Roughgarden, E.\u00a0Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.","DOI":"10.1017\/CBO9780511800481"},{"key":"15_CR33","unstructured":"S.\u00a0Paul and S-E. Simon. Nash equilibrium in generalised muller games. In Proc. 29th Conf. on Foundations of Software Technology and Theoretical Computer Science, volume\u00a04 of LIPIcs, pages 335\u2013346. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2009."},{"key":"15_CR34","doi-asserted-by":"crossref","unstructured":"A.\u00a0Pnueli and R.\u00a0Rosner. On the synthesis of a reactive module. In Proc. 16th ACM Symp. on Principles of Programming Languages, pages 179\u2013190, 1989.","DOI":"10.1145\/75277.75293"},{"key":"15_CR35","doi-asserted-by":"crossref","unstructured":"R.E. Tarjan. Depth first search and linear graph algorithms. SIAM Journal of Computing, 1(2):146\u2013160, 1972.","DOI":"10.1137\/0201010"},{"key":"15_CR36","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ummels. The complexity of Nash equilibria in infinite multiplayer games. In Proc. 11th Int. Conf. on Foundations of Software Science and Computation Structures, pages 20\u201334, 2008.","DOI":"10.1007\/978-3-540-78499-9_3"},{"key":"15_CR37","doi-asserted-by":"crossref","unstructured":"M. Ummels and D. Wojtczak. The complexity of nash equilibria in limit-average games. In Proc. 22nd Int. Conf. on Concurrency Theory, volume 6901 of Lecture Notes in Computer Science, pages 482\u2013496. Springer, 2011.","DOI":"10.1007\/978-3-642-23217-6_32"},{"key":"15_CR38","doi-asserted-by":"crossref","unstructured":"Y. Velner, K. Chatterjee, L. Doyen, T.A. Henzinger, A. Rabinovich, and J-F. Raskin. The complexity of multi-mean-payoff and multi-energy games. Information and Computation, 241:177\u2013196, 2015.","DOI":"10.1016\/j.ic.2015.03.001"},{"key":"15_CR39","unstructured":"J.\u00a0von Neumann and O.\u00a0Morgenstern. Theory of games and economic behavior. Princeton University Press, 1953."}],"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-031-90653-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:37:14Z","timestamp":1764401834000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-90653-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031906527","9783031906534"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-90653-4_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"1 May 2025","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":"Hamilton, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 May 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 May 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2025\/conferences\/tacas\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}