[{"article_number":"114353","ec_funded":1,"publication_status":"epub_ahead","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"publisher":"Elsevier","acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021-2024.","year":"2024","date_updated":"2024-01-17T09:23:03Z","date_created":"2024-01-16T13:40:41Z","volume":989,"author":[{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","first_name":"Jakub","last_name":"Svoboda","full_name":"Svoboda, Jakub"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X","last_name":"Yeo","full_name":"Yeo, Michelle X"}],"month":"01","publication_identifier":{"issn":["0304-3975"]},"quality_controlled":"1","project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1016/j.tcs.2023.114353"}],"language":[{"iso":"eng"}],"doi":"10.1016/j.tcs.2023.114353","type":"journal_article","abstract":[{"text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on \r\n increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3) for some arbitrary E>0.","lang":"eng"}],"status":"public","title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","intvolume":" 989","_id":"14820","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","keyword":["General Computer Science","Theoretical Computer Science"],"day":"11","article_processing_charge":"Yes (via OA deal)","article_type":"original","publication":"Theoretical Computer Science","citation":{"chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” Theoretical Computer Science. Elsevier, 2024. https://doi.org/10.1016/j.tcs.2023.114353.","short":"S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).","mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” Theoretical Computer Science, vol. 989, 114353, Elsevier, 2024, doi:10.1016/j.tcs.2023.114353.","apa":"Schmid, S., Svoboda, J., & Yeo, M. X. (2024). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.114353","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” Theoretical Computer Science, vol. 989. Elsevier, 2024.","ista":"Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 989, 114353.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 2024;989. doi:10.1016/j.tcs.2023.114353"},"date_published":"2024-01-11T00:00:00Z"},{"department":[{"_id":"KrCh"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","acknowledgement":"This work was partially funded by the Academy of Finland, grant 314888, the European Research Council CoG 863818 (ForM-SMArt), and the Austrian Science Fund (FWF) project I 4800-N (ADVISE). LS was supported by the Stochastic Analysis and Application Research Center (SAARC) under National Research Foundation of Korea grant NRF-2019R1A5A1028324.","year":"2024","volume":286,"date_updated":"2024-02-26T09:16:12Z","date_created":"2024-02-18T23:01:01Z","author":[{"full_name":"Hirvonen, Juho","last_name":"Hirvonen","first_name":"Juho"},{"full_name":"Schmid, Laura","last_name":"Schmid","first_name":"Laura","orcid":"0000-0002-6978-7329","id":"38B437DE-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"}],"article_number":"11","ec_funded":1,"file_date_updated":"2024-02-26T09:04:58Z","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2102.13457"]},"oa":1,"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.OPODIS.2023.11","conference":{"end_date":"2023-12-08","location":"Tokyo, Japan","start_date":"2023-12-06","name":"OPODIS: Conference on Principles of Distributed Systems"},"publication_identifier":{"issn":["18688969"],"isbn":["9783959773089"]},"month":"01","intvolume":" 286","status":"public","title":"On the convergence time in graphical games: A locality-sensitive approach","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"15006","oa_version":"Published Version","file":[{"content_type":"application/pdf","file_size":867363,"creator":"dernst","access_level":"open_access","file_name":"2024_LIPICs_Hirvonen.pdf","checksum":"4fc7eea6e4ba140b904781fc7df868ec","success":1,"date_created":"2024-02-26T09:04:58Z","date_updated":"2024-02-26T09:04:58Z","relation":"main_file","file_id":"15028"}],"alternative_title":["LIPIcs"],"type":"conference","abstract":[{"text":"Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of \"natural\" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of \"time-constrained\" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.","lang":"eng"}],"citation":{"chicago":"Hirvonen, Juho, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” In 27th International Conference on Principles of Distributed Systems, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.OPODIS.2023.11.","mla":"Hirvonen, Juho, et al. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” 27th International Conference on Principles of Distributed Systems, vol. 286, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.OPODIS.2023.11.","short":"J. Hirvonen, L. Schmid, K. Chatterjee, S. Schmid, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. 2024. On the convergence time in graphical games: A locality-sensitive approach. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 11.","apa":"Hirvonen, J., Schmid, L., Chatterjee, K., & Schmid, S. (2024). On the convergence time in graphical games: A locality-sensitive approach. In 27th International Conference on Principles of Distributed Systems (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2023.11","ieee":"J. Hirvonen, L. Schmid, K. Chatterjee, and S. Schmid, “On the convergence time in graphical games: A locality-sensitive approach,” in 27th International Conference on Principles of Distributed Systems, Tokyo, Japan, 2024, vol. 286.","ama":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. On the convergence time in graphical games: A locality-sensitive approach. In: 27th International Conference on Principles of Distributed Systems. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.OPODIS.2023.11"},"publication":"27th International Conference on Principles of Distributed Systems","date_published":"2024-01-18T00:00:00Z","scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","day":"18"},{"abstract":[{"lang":"eng","text":"Direct reciprocity is a powerful mechanism for cooperation in social dilemmas. The very logic of reciprocity, however, seems to require that individuals are symmetric, and that everyone has the same means to influence each others’ payoffs. Yet in many applications, individuals are asymmetric. Herein, we study the effect of asymmetry in linear public good games. Individuals may differ in their endowments (their ability to contribute to a public good) and in their productivities (how effective their contributions are). Given the individuals’ productivities, we ask which allocation of endowments is optimal for cooperation. To this end, we consider two notions of optimality. The first notion focuses on the resilience of cooperation. The respective endowment distribution ensures that full cooperation is feasible even under the most adverse conditions. The second notion focuses on efficiency. The corresponding endowment distribution maximizes group welfare. Using analytical methods, we fully characterize these two endowment distributions. This analysis reveals that both optimality notions favor some endowment inequality: More productive players ought to get higher endowments. Yet the two notions disagree on how unequal endowments are supposed to be. A focus on resilience results in less inequality. With additional simulations, we show that the optimal endowment allocation needs to account for both the resilience and the efficiency of cooperation."}],"issue":"10","type":"journal_article","oa_version":"Published Version","file":[{"relation":"main_file","file_id":"15109","checksum":"068520e3efd4d008bb9177e8aedb7d22","success":1,"date_created":"2024-03-12T13:12:22Z","date_updated":"2024-03-12T13:12:22Z","access_level":"open_access","file_name":"2024_PNAS_Huebner.pdf","content_type":"application/pdf","file_size":2203220,"creator":"dernst"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"15083","ddc":["000"],"status":"public","title":"Efficiency and resilience of cooperation in asymmetric social dilemmas","intvolume":" 121","day":"05","article_processing_charge":"Yes (in subscription journal)","has_accepted_license":"1","date_published":"2024-03-05T00:00:00Z","publication":"Proceedings of the National Academy of Sciences","citation":{"mla":"Hübner, Valentin, et al. “Efficiency and Resilience of Cooperation in Asymmetric Social Dilemmas.” Proceedings of the National Academy of Sciences, vol. 121, no. 10, e2315558121, Proceedings of the National Academy of Sciences, 2024, doi:10.1073/pnas.2315558121.","short":"V. Hübner, M. Staab, C. Hilbe, K. Chatterjee, M. Kleshnina, Proceedings of the National Academy of Sciences 121 (2024).","chicago":"Hübner, Valentin, Manuel Staab, Christian Hilbe, Krishnendu Chatterjee, and Maria Kleshnina. “Efficiency and Resilience of Cooperation in Asymmetric Social Dilemmas.” Proceedings of the National Academy of Sciences. Proceedings of the National Academy of Sciences, 2024. https://doi.org/10.1073/pnas.2315558121.","ama":"Hübner V, Staab M, Hilbe C, Chatterjee K, Kleshnina M. Efficiency and resilience of cooperation in asymmetric social dilemmas. Proceedings of the National Academy of Sciences. 2024;121(10). doi:10.1073/pnas.2315558121","ista":"Hübner V, Staab M, Hilbe C, Chatterjee K, Kleshnina M. 2024. Efficiency and resilience of cooperation in asymmetric social dilemmas. Proceedings of the National Academy of Sciences. 121(10), e2315558121.","ieee":"V. Hübner, M. Staab, C. Hilbe, K. Chatterjee, and M. Kleshnina, “Efficiency and resilience of cooperation in asymmetric social dilemmas,” Proceedings of the National Academy of Sciences, vol. 121, no. 10. Proceedings of the National Academy of Sciences, 2024.","apa":"Hübner, V., Staab, M., Hilbe, C., Chatterjee, K., & Kleshnina, M. (2024). Efficiency and resilience of cooperation in asymmetric social dilemmas. Proceedings of the National Academy of Sciences. Proceedings of the National Academy of Sciences. https://doi.org/10.1073/pnas.2315558121"},"article_type":"original","file_date_updated":"2024-03-12T13:12:22Z","ec_funded":1,"article_number":"e2315558121","author":[{"full_name":"Hübner, Valentin","first_name":"Valentin","last_name":"Hübner","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910"},{"full_name":"Staab, Manuel","first_name":"Manuel","last_name":"Staab"},{"orcid":"0000-0001-5116-955X","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","last_name":"Hilbe","first_name":"Christian","full_name":"Hilbe, Christian"},{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Kleshnina, Maria","first_name":"Maria","last_name":"Kleshnina"}],"related_material":{"record":[{"id":"15108","relation":"research_data","status":"public"}],"link":[{"url":"https://ista.ac.at/en/news/what-math-tells-us-about-social-dilemmas/","relation":"press_release","description":"News on ISTA Website"}]},"date_created":"2024-03-05T09:18:49Z","date_updated":"2024-03-12T13:29:25Z","volume":121,"acknowledgement":"This work was supported by the European Research Council CoG 863818 (ForM-SMArt) (to K.C.) and the European Research Council Starting Grant 850529: E-DIRECT (to C.H.), the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie Grant Agreement #754411 and the French Agence Nationale de la Recherche (under the Investissement d’Avenir Programme, ANR-17-EURE-0010) (to M.K.).","year":"2024","pmid":1,"publication_status":"published","publisher":"Proceedings of the National Academy of Sciences","department":[{"_id":"KrCh"}],"month":"03","publication_identifier":{"issn":["0027-8424"],"eissn":["1091-6490"]},"doi":"10.1073/pnas.2315558121","language":[{"iso":"eng"}],"oa":1,"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png"},"external_id":{"pmid":["38408249"]},"quality_controlled":"1","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}]},{"type":"research_data_reference","abstract":[{"text":"in the research article \"Efficiency and resilience of cooperation in asymmetric social dilemmas\" (by Valentin Hübner, Manuel Staab, Christian Hilbe, Krishnendu Chatterjee, and Maria Kleshnina).\r\n\r\nWe used different implementations for the case of two and three players, both described below.","lang":"eng"}],"_id":"15108","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2024","department":[{"_id":"KrCh"}],"publisher":"Zenodo","ddc":["000"],"title":"Computer code for \"Efficiency and resilience of cooperation in asymmetric social dilemmas\"","status":"public","related_material":{"record":[{"id":"15083","status":"public","relation":"used_in_publication"}]},"author":[{"last_name":"Hübner","first_name":"Valentin","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910","full_name":"Hübner, Valentin"},{"full_name":"Kleshnina, Maria","last_name":"Kleshnina","first_name":"Maria"}],"oa_version":"Published Version","date_updated":"2024-03-12T13:29:26Z","date_created":"2024-03-12T13:02:58Z","article_processing_charge":"No","has_accepted_license":"1","day":"09","month":"02","citation":{"chicago":"Hübner, Valentin, and Maria Kleshnina. “Computer Code for ‘Efficiency and Resilience of Cooperation in Asymmetric Social Dilemmas.’” Zenodo, 2024. https://doi.org/10.5281/ZENODO.10639167.","mla":"Hübner, Valentin, and Maria Kleshnina. Computer Code for “Efficiency and Resilience of Cooperation in Asymmetric Social Dilemmas.” Zenodo, 2024, doi:10.5281/ZENODO.10639167.","short":"V. Hübner, M. Kleshnina, (2024).","ista":"Hübner V, Kleshnina M. 2024. Computer code for ‘Efficiency and resilience of cooperation in asymmetric social dilemmas’, Zenodo, 10.5281/ZENODO.10639167.","ieee":"V. Hübner and M. Kleshnina, “Computer code for ‘Efficiency and resilience of cooperation in asymmetric social dilemmas.’” Zenodo, 2024.","apa":"Hübner, V., & Kleshnina, M. (2024). Computer code for “Efficiency and resilience of cooperation in asymmetric social dilemmas.” Zenodo. https://doi.org/10.5281/ZENODO.10639167","ama":"Hübner V, Kleshnina M. Computer code for “Efficiency and resilience of cooperation in asymmetric social dilemmas.” 2024. doi:10.5281/ZENODO.10639167"},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"main_file_link":[{"open_access":"1","url":"https://10.5281/zenodo.10639167"}],"oa":1,"date_published":"2024-02-09T00:00:00Z","doi":"10.5281/ZENODO.10639167"},{"date_published":"2023-02-01T00:00:00Z","publication":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms","citation":{"ista":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. 2023. Faster algorithm for turn-based stochastic games with bounded treewidth. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 4590–4605.","ieee":"K. Chatterjee, T. Meggendorfer, R. J. Saona Urmeneta, and J. Svoboda, “Faster algorithm for turn-based stochastic games with bounded treewidth,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florence, Italy, 2023, pp. 4590–4605.","apa":"Chatterjee, K., Meggendorfer, T., Saona Urmeneta, R. J., & Svoboda, J. (2023). Faster algorithm for turn-based stochastic games with bounded treewidth. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 4590–4605). Florence, Italy: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch173","ama":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. Faster algorithm for turn-based stochastic games with bounded treewidth. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2023:4590-4605. doi:10.1137/1.9781611977554.ch173","chicago":"Chatterjee, Krishnendu, Tobias Meggendorfer, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, 4590–4605. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/1.9781611977554.ch173.","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 4590–605, doi:10.1137/1.9781611977554.ch173.","short":"K. Chatterjee, T. Meggendorfer, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 4590–4605."},"page":"4590-4605","day":"01","article_processing_charge":"No","oa_version":"Published Version","_id":"12676","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Faster algorithm for turn-based stochastic games with bounded treewidth","abstract":[{"text":"Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth.","lang":"eng"}],"type":"conference","conference":{"name":"SODA: Symposium on Discrete Algorithms","location":"Florence, Italy","start_date":"2023-01-22","end_date":"2023-01-25"},"doi":"10.1137/1.9781611977554.ch173","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://doi.org/10.1137/1.9781611977554.ch173","open_access":"1"}],"oa":1,"quality_controlled":"1","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"month":"02","publication_identifier":{"isbn":["9781611977554"]},"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Tobias","last_name":"Meggendorfer","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165","full_name":"Meggendorfer, Tobias"},{"orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J"},{"last_name":"Svoboda","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub"}],"date_updated":"2023-02-27T09:01:16Z","date_created":"2023-02-24T12:20:47Z","year":"2023","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","publication_status":"published","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"publisher":"Society for Industrial and Applied Mathematics","ec_funded":1}]