--- _id: '14259' abstract: - lang: eng text: "We provide a learning-based technique for guessing a winning strategy in a parity game originating from an LTL synthesis problem. A cheaply obtained guess can be useful in several applications. Not only can the guessed strategy be applied as best-effort in cases where the game’s huge size prohibits rigorous approaches, but it can also increase the scalability of rigorous LTL synthesis in several ways. Firstly, checking whether a guessed strategy is winning is easier than constructing one. Secondly, even if the guess is wrong in some places, it can be fixed by strategy iteration faster than constructing one from scratch. Thirdly, the guess can be used in on-the-fly approaches to prioritize exploration in the most fruitful directions.\r\nIn contrast to previous works, we (i) reflect the highly structured logical information in game’s states, the so-called semantic labelling, coming from the recent LTL-to-automata translations, and (ii) learn to reflect it properly by learning from previously solved games, bringing the solving process closer to human-like reasoning." acknowledgement: This research was funded in part by the German Research Foundation (DFG) project 427755713 Group-By Objectives in Probabilistic Verification (GOPro). alternative_title: - LNCS article_processing_charge: Yes (in subscription journal) author: - first_name: Jan full_name: Kretinsky, Jan id: 44CEF464-F248-11E8-B48F-1D18A9856A87 last_name: Kretinsky orcid: 0000-0002-8122-2881 - first_name: Tobias full_name: Meggendorfer, Tobias id: b21b0c15-30a2-11eb-80dc-f13ca25802e1 last_name: Meggendorfer orcid: 0000-0002-1712-2165 - first_name: Maximilian full_name: Prokop, Maximilian last_name: Prokop - first_name: Sabine full_name: Rieder, Sabine last_name: Rieder citation: ama: 'Kretinsky J, Meggendorfer T, Prokop M, Rieder S. Guessing winning policies in LTL synthesis by semantic learning. In: 35th International Conference on Computer Aided Verification . Vol 13964. Springer Nature; 2023:390-414. doi:10.1007/978-3-031-37706-8_20' apa: 'Kretinsky, J., Meggendorfer, T., Prokop, M., & Rieder, S. (2023). Guessing winning policies in LTL synthesis by semantic learning. In 35th International Conference on Computer Aided Verification (Vol. 13964, pp. 390–414). Paris, France: Springer Nature. https://doi.org/10.1007/978-3-031-37706-8_20' chicago: Kretinsky, Jan, Tobias Meggendorfer, Maximilian Prokop, and Sabine Rieder. “Guessing Winning Policies in LTL Synthesis by Semantic Learning.” In 35th International Conference on Computer Aided Verification , 13964:390–414. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-37706-8_20. ieee: J. Kretinsky, T. Meggendorfer, M. Prokop, and S. Rieder, “Guessing winning policies in LTL synthesis by semantic learning,” in 35th International Conference on Computer Aided Verification , Paris, France, 2023, vol. 13964, pp. 390–414. ista: 'Kretinsky J, Meggendorfer T, Prokop M, Rieder S. 2023. Guessing winning policies in LTL synthesis by semantic learning. 35th International Conference on Computer Aided Verification . CAV: Computer Aided Verification, LNCS, vol. 13964, 390–414.' mla: Kretinsky, Jan, et al. “Guessing Winning Policies in LTL Synthesis by Semantic Learning.” 35th International Conference on Computer Aided Verification , vol. 13964, Springer Nature, 2023, pp. 390–414, doi:10.1007/978-3-031-37706-8_20. short: J. Kretinsky, T. Meggendorfer, M. Prokop, S. Rieder, in:, 35th International Conference on Computer Aided Verification , Springer Nature, 2023, pp. 390–414. conference: end_date: 2023-07-22 location: Paris, France name: 'CAV: Computer Aided Verification' start_date: 2023-07-17 date_created: 2023-09-03T22:01:16Z date_published: 2023-07-17T00:00:00Z date_updated: 2023-09-06T08:27:33Z day: '17' ddc: - '000' department: - _id: KrCh doi: 10.1007/978-3-031-37706-8_20 file: - access_level: open_access checksum: ed66278b61bb869e1baba3d9b9081271 content_type: application/pdf creator: dernst date_created: 2023-09-06T08:25:50Z date_updated: 2023-09-06T08:25:50Z file_id: '14276' file_name: 2023_LNCS_CAV_Kretinsky.pdf file_size: 428354 relation: main_file success: 1 file_date_updated: 2023-09-06T08:25:50Z has_accepted_license: '1' intvolume: ' 13964' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '07' oa: 1 oa_version: Published Version page: 390-414 publication: '35th International Conference on Computer Aided Verification ' publication_identifier: eissn: - 1611-3349 isbn: - '9783031377051' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Guessing winning policies in LTL synthesis by semantic learning tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 13964 year: '2023' ... --- _id: '14318' abstract: - lang: eng text: "Probabilistic recurrence relations (PRRs) are a standard formalism for describing the runtime of a randomized algorithm. Given a PRR and a time limit κ, we consider the tail probability Pr[T≥κ], i.e., the probability that the randomized runtime T of the PRR exceeds κ. Our focus is the formal analysis of tail bounds that aims at finding a tight asymptotic upper bound u≥Pr[T≥κ]. To address this problem, the classical and most well-known approach is the cookbook method by Karp (JACM 1994), while other approaches are mostly limited to deriving tail bounds of specific PRRs via involved custom analysis.\r\nIn this work, we propose a novel approach for deriving the common exponentially-decreasing tail bounds for PRRs whose preprocessing time and random passed sizes observe discrete or (piecewise) uniform distribution and whose recursive call is either a single procedure call or a divide-and-conquer. We first establish a theoretical approach via Markov’s inequality, and then instantiate the theoretical approach with a template-based algorithmic approach via a refined treatment of exponentiation. Experimental evaluation shows that our algorithmic approach is capable of deriving tail bounds that are (i) asymptotically tighter than Karp’s method, (ii) match the best-known manually-derived asymptotic tail bound for QuickSelect, and (iii) is only slightly worse (with a loglogn factor) than the manually-proven optimal asymptotic tail bound for QuickSort. Moreover, our algorithmic approach handles all examples (including realistic PRRs such as QuickSort, QuickSelect, DiameterComputation, etc.) in less than 0.1 s, showing that our approach is efficient in practice." acknowledgement: We thank Prof. Bican Xia for valuable information on the exponential theory of reals. The work is partially supported by the National Natural Science Foundation of China (NSFC) with Grant No. 62172271, ERC CoG 863818 (ForM-SMArt), the Hong Kong Research Grants Council ECS Project Number 26208122, the HKUST-Kaisa Joint Research Institute Project Grant HKJRI3A-055 and the HKUST Startup Grant R9272. alternative_title: - LNCS article_processing_charge: Yes (in subscription journal) author: - first_name: Yican full_name: Sun, Yican last_name: Sun - first_name: Hongfei full_name: Fu, Hongfei last_name: Fu - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Amir Kafshdar full_name: Goharshady, Amir Kafshdar id: 391365CE-F248-11E8-B48F-1D18A9856A87 last_name: Goharshady orcid: 0000-0003-1702-6584 citation: ama: 'Sun Y, Fu H, Chatterjee K, Goharshady AK. Automated tail bound analysis for probabilistic recurrence relations. In: Computer Aided Verification. Vol 13966. Springer Nature; 2023:16-39. doi:10.1007/978-3-031-37709-9_2' apa: 'Sun, Y., Fu, H., Chatterjee, K., & Goharshady, A. K. (2023). Automated tail bound analysis for probabilistic recurrence relations. In Computer Aided Verification (Vol. 13966, pp. 16–39). Paris, France: Springer Nature. https://doi.org/10.1007/978-3-031-37709-9_2' chicago: Sun, Yican, Hongfei Fu, Krishnendu Chatterjee, and Amir Kafshdar Goharshady. “Automated Tail Bound Analysis for Probabilistic Recurrence Relations.” In Computer Aided Verification, 13966:16–39. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-37709-9_2. ieee: Y. Sun, H. Fu, K. Chatterjee, and A. K. Goharshady, “Automated tail bound analysis for probabilistic recurrence relations,” in Computer Aided Verification, Paris, France, 2023, vol. 13966, pp. 16–39. ista: 'Sun Y, Fu H, Chatterjee K, Goharshady AK. 2023. Automated tail bound analysis for probabilistic recurrence relations. Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 13966, 16–39.' mla: Sun, Yican, et al. “Automated Tail Bound Analysis for Probabilistic Recurrence Relations.” Computer Aided Verification, vol. 13966, Springer Nature, 2023, pp. 16–39, doi:10.1007/978-3-031-37709-9_2. short: Y. Sun, H. Fu, K. Chatterjee, A.K. Goharshady, in:, Computer Aided Verification, Springer Nature, 2023, pp. 16–39. conference: end_date: 2023-07-22 location: Paris, France name: 'CAV: Computer Aided Verification' start_date: 2023-07-17 date_created: 2023-09-10T22:01:12Z date_published: 2023-07-17T00:00:00Z date_updated: 2023-09-20T08:25:57Z day: '17' ddc: - '000' department: - _id: KrCh doi: 10.1007/978-3-031-37709-9_2 ec_funded: 1 file: - access_level: open_access checksum: 42917e086f8c7699f3bccf84f74fe000 content_type: application/pdf creator: dernst date_created: 2023-09-20T08:24:47Z date_updated: 2023-09-20T08:24:47Z file_id: '14348' file_name: 2023_LNCS_Sun.pdf file_size: 624647 relation: main_file success: 1 file_date_updated: 2023-09-20T08:24:47Z has_accepted_license: '1' intvolume: ' 13966' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 16-39 project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: Computer Aided Verification publication_identifier: eissn: - 1611-3349 isbn: - '9783031377082' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: link: - relation: software url: https://github.com/boyvolcano/PRR scopus_import: '1' status: public title: Automated tail bound analysis for probabilistic recurrence relations tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 13966 year: '2023' ... --- _id: '14317' abstract: - lang: eng text: "Markov decision processes can be viewed as transformers of probability distributions. While this view is useful from a practical standpoint to reason about trajectories of distributions, basic reachability and safety problems are known to be computationally intractable (i.e., Skolem-hard) to solve in such models. Further, we show that even for simple examples of MDPs, strategies for safety objectives over distributions can require infinite memory and randomization.\r\nIn light of this, we present a novel overapproximation approach to synthesize strategies in an MDP, such that a safety objective over the distributions is met. More precisely, we develop a new framework for template-based synthesis of certificates as affine distributional and inductive invariants for safety objectives in MDPs. We provide two algorithms within this framework. One can only synthesize memoryless strategies, but has relative completeness guarantees, while the other can synthesize general strategies. The runtime complexity of both algorithms is in PSPACE. We implement these algorithms and show that they can solve several non-trivial examples." acknowledgement: This work was supported in part by the ERC CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385 as well as DST/CEFIPRA/INRIA project EQuaVE and SERB Matrices grant MTR/2018/00074. alternative_title: - LNCS article_processing_charge: Yes (in subscription journal) author: - first_name: S. full_name: Akshay, S. last_name: Akshay - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Tobias full_name: Meggendorfer, Tobias id: b21b0c15-30a2-11eb-80dc-f13ca25802e1 last_name: Meggendorfer orcid: 0000-0002-1712-2165 - first_name: Dorde full_name: Zikelic, Dorde id: 294AA7A6-F248-11E8-B48F-1D18A9856A87 last_name: Zikelic orcid: 0000-0002-4681-1699 citation: ama: 'Akshay S, Chatterjee K, Meggendorfer T, Zikelic D. MDPs as distribution transformers: Affine invariant synthesis for safety objectives. In: International Conference on Computer Aided Verification. Vol 13966. Springer Nature; 2023:86-112. doi:10.1007/978-3-031-37709-9_5' apa: 'Akshay, S., Chatterjee, K., Meggendorfer, T., & Zikelic, D. (2023). MDPs as distribution transformers: Affine invariant synthesis for safety objectives. In International Conference on Computer Aided Verification (Vol. 13966, pp. 86–112). Paris, France: Springer Nature. https://doi.org/10.1007/978-3-031-37709-9_5' chicago: 'Akshay, S., Krishnendu Chatterjee, Tobias Meggendorfer, and Dorde Zikelic. “MDPs as Distribution Transformers: Affine Invariant Synthesis for Safety Objectives.” In International Conference on Computer Aided Verification, 13966:86–112. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-37709-9_5.' ieee: 'S. Akshay, K. Chatterjee, T. Meggendorfer, and D. Zikelic, “MDPs as distribution transformers: Affine invariant synthesis for safety objectives,” in International Conference on Computer Aided Verification, Paris, France, 2023, vol. 13966, pp. 86–112.' ista: 'Akshay S, Chatterjee K, Meggendorfer T, Zikelic D. 2023. MDPs as distribution transformers: Affine invariant synthesis for safety objectives. International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 13966, 86–112.' mla: 'Akshay, S., et al. “MDPs as Distribution Transformers: Affine Invariant Synthesis for Safety Objectives.” International Conference on Computer Aided Verification, vol. 13966, Springer Nature, 2023, pp. 86–112, doi:10.1007/978-3-031-37709-9_5.' short: S. Akshay, K. Chatterjee, T. Meggendorfer, D. Zikelic, in:, International Conference on Computer Aided Verification, Springer Nature, 2023, pp. 86–112. conference: end_date: 2023-07-22 location: Paris, France name: 'CAV: Computer Aided Verification' start_date: 2023-07-17 date_created: 2023-09-10T22:01:12Z date_published: 2023-07-17T00:00:00Z date_updated: 2023-09-20T09:04:40Z day: '17' ddc: - '000' department: - _id: KrCh doi: 10.1007/978-3-031-37709-9_5 ec_funded: 1 file: - access_level: open_access checksum: f143c8eedf609f20f2aad2eeb496d53f content_type: application/pdf creator: dernst date_created: 2023-09-20T08:46:43Z date_updated: 2023-09-20T08:46:43Z file_id: '14349' file_name: 2023_LNCS_Akshay.pdf file_size: 531745 relation: main_file success: 1 file_date_updated: 2023-09-20T08:46:43Z has_accepted_license: '1' intvolume: ' 13966' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 86-112 project: - _id: 2564DBCA-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '665385' name: International IST Doctoral Program - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: International Conference on Computer Aided Verification publication_identifier: eissn: - 1611-3349 isbn: - '9783031377082' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: 'MDPs as distribution transformers: Affine invariant synthesis for safety objectives' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 13966 year: '2023' ... --- _id: '12738' abstract: - lang: eng text: We study turn-based stochastic zero-sum games with lexicographic preferences over objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as controllable and adversarial non-determinism. Lexicographic order allows one to consider multiple objectives with a strict preference order. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. For a mixture of reachability and safety objectives, we show that deterministic lexicographically optimal strategies exist and memory is only required to remember the already satisfied and violated objectives. For a constant number of objectives, we show that the relevant decision problem is in NP∩coNP, matching the current known bound for single objectives; and in general the decision problem is PSPACE-hard and can be solved in NEXPTIME∩coNEXPTIME. We present an algorithm that computes the lexicographically optimal strategies via a reduction to the computation of optimal strategies in a sequence of single-objectives games. For omega-regular objectives, we restrict our analysis to one-player games, also known as Markov decision processes. We show that lexicographically optimal strategies exist and need either randomization or finite memory. We present an algorithm that solves the relevant decision problem in polynomial time. We have implemented our algorithms and report experimental results on various case studies. acknowledgement: Tobias Winkler and Joost-Pieter Katoen are supported by the DFG RTG 2236 UnRAVeL and the innovation programme under the Marie Skłodowska-Curie grant agreement No. 101008233 (Mission). Krishnendu Chatterjee is supported by the ERC CoG 863818 (ForM-SMArt) and the Vienna Science and Technology Fund (WWTF) Project ICT15-003. Maximilian Weininger is supported by the DFG projects 383882557 Statistical Unbounded Verification (SUV) and 427755713 Group-By Objectives in Probabilistic Verification (GOPro). Stefanie Mohr is supported by the DFG RTG 2428 CONVEY. Open Access funding enabled and organized by Projekt DEAL. article_processing_charge: No article_type: original author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Joost P full_name: Katoen, Joost P id: 4524F760-F248-11E8-B48F-1D18A9856A87 last_name: Katoen - first_name: Stefanie full_name: Mohr, Stefanie last_name: Mohr - first_name: Maximilian full_name: Weininger, Maximilian last_name: Weininger - first_name: Tobias full_name: Winkler, Tobias last_name: Winkler citation: ama: Chatterjee K, Katoen JP, Mohr S, Weininger M, Winkler T. Stochastic games with lexicographic objectives. Formal Methods in System Design. 2023. doi:10.1007/s10703-023-00411-4 apa: Chatterjee, K., Katoen, J. P., Mohr, S., Weininger, M., & Winkler, T. (2023). Stochastic games with lexicographic objectives. Formal Methods in System Design. Springer Nature. https://doi.org/10.1007/s10703-023-00411-4 chicago: Chatterjee, Krishnendu, Joost P Katoen, Stefanie Mohr, Maximilian Weininger, and Tobias Winkler. “Stochastic Games with Lexicographic Objectives.” Formal Methods in System Design. Springer Nature, 2023. https://doi.org/10.1007/s10703-023-00411-4. ieee: K. Chatterjee, J. P. Katoen, S. Mohr, M. Weininger, and T. Winkler, “Stochastic games with lexicographic objectives,” Formal Methods in System Design. Springer Nature, 2023. ista: Chatterjee K, Katoen JP, Mohr S, Weininger M, Winkler T. 2023. Stochastic games with lexicographic objectives. Formal Methods in System Design. mla: Chatterjee, Krishnendu, et al. “Stochastic Games with Lexicographic Objectives.” Formal Methods in System Design, Springer Nature, 2023, doi:10.1007/s10703-023-00411-4. short: K. Chatterjee, J.P. Katoen, S. Mohr, M. Weininger, T. Winkler, Formal Methods in System Design (2023). date_created: 2023-03-19T23:00:59Z date_published: 2023-03-08T00:00:00Z date_updated: 2023-10-03T11:36:13Z day: '08' ddc: - '000' department: - _id: KrCh doi: 10.1007/s10703-023-00411-4 ec_funded: 1 external_id: isi: - '000946174300001' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1007/s10703-023-00411-4 month: '03' oa: 1 oa_version: Published Version project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' - _id: 25892FC0-B435-11E9-9278-68D0E5697425 grant_number: ICT15-003 name: Efficient Algorithms for Computer Aided Verification publication: Formal Methods in System Design publication_identifier: eissn: - 1572-8102 publication_status: epub_ahead publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '8272' relation: earlier_version status: public scopus_import: '1' status: public title: Stochastic games with lexicographic objectives tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2023' ... --- _id: '10770' abstract: - lang: eng text: Mathematical models often aim to describe a complicated mechanism in a cohesive and simple manner. However, reaching perfect balance between being simple enough or overly simplistic is a challenging task. Frequently, game-theoretic models have an underlying assumption that players, whenever they choose to execute a specific action, do so perfectly. In fact, it is rare that action execution perfectly coincides with intentions of individuals, giving rise to behavioural mistakes. The concept of incompetence of players was suggested to address this issue in game-theoretic settings. Under the assumption of incompetence, players have non-zero probabilities of executing a different strategy from the one they chose, leading to stochastic outcomes of the interactions. In this article, we survey results related to the concept of incompetence in classic as well as evolutionary game theory and provide several new results. We also suggest future extensions of the model and argue why it is important to take into account behavioural mistakes when analysing interactions among players in both economic and biological settings. acknowledgement: "The authors would like to acknowledge stimulating email discussions with Dr Wayne Lobb of W.A. Lobb LLC on the topic of evolutionary games. We also thank Dr Thomas Taimre for his input to the material in Sect. 3.\r\nThe authors would like to acknowledge partial support from the Australian Research Council under the Discovery grant DP180101602 and support by the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie Grant Agreement #754411." article_processing_charge: No article_type: original author: - first_name: Thomas full_name: Graham, Thomas last_name: Graham - first_name: Maria full_name: Kleshnina, Maria id: 4E21749C-F248-11E8-B48F-1D18A9856A87 last_name: Kleshnina - first_name: Jerzy A. full_name: Filar, Jerzy A. last_name: Filar citation: ama: Graham T, Kleshnina M, Filar JA. Where do mistakes lead? A survey of games with incompetent players. Dynamic Games and Applications. 2023;13:231-264. doi:10.1007/s13235-022-00425-3 apa: Graham, T., Kleshnina, M., & Filar, J. A. (2023). Where do mistakes lead? A survey of games with incompetent players. Dynamic Games and Applications. Springer Nature. https://doi.org/10.1007/s13235-022-00425-3 chicago: Graham, Thomas, Maria Kleshnina, and Jerzy A. Filar. “Where Do Mistakes Lead? A Survey of Games with Incompetent Players.” Dynamic Games and Applications. Springer Nature, 2023. https://doi.org/10.1007/s13235-022-00425-3. ieee: T. Graham, M. Kleshnina, and J. A. Filar, “Where do mistakes lead? A survey of games with incompetent players,” Dynamic Games and Applications, vol. 13. Springer Nature, pp. 231–264, 2023. ista: Graham T, Kleshnina M, Filar JA. 2023. Where do mistakes lead? A survey of games with incompetent players. Dynamic Games and Applications. 13, 231–264. mla: Graham, Thomas, et al. “Where Do Mistakes Lead? A Survey of Games with Incompetent Players.” Dynamic Games and Applications, vol. 13, Springer Nature, 2023, pp. 231–64, doi:10.1007/s13235-022-00425-3. short: T. Graham, M. Kleshnina, J.A. Filar, Dynamic Games and Applications 13 (2023) 231–264. date_created: 2022-02-20T23:01:32Z date_published: 2023-03-01T00:00:00Z date_updated: 2023-10-04T09:24:30Z day: '01' ddc: - '000' department: - _id: KrCh doi: 10.1007/s13235-022-00425-3 ec_funded: 1 external_id: isi: - '000753777100001' file: - access_level: open_access checksum: cd53b07e96f9030ddb348f305e5b58c7 content_type: application/pdf creator: dernst date_created: 2022-02-21T08:54:17Z date_updated: 2022-02-21T08:54:17Z file_id: '10781' file_name: 2022_DynamicGamesApplic_Graham.pdf file_size: 1890512 relation: main_file success: 1 file_date_updated: 2022-02-21T08:54:17Z has_accepted_license: '1' intvolume: ' 13' isi: 1 language: - iso: eng month: '03' oa: 1 oa_version: Published Version page: 231-264 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: Dynamic Games and Applications publication_identifier: eissn: - 2153-0793 issn: - 2153-0785 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Where do mistakes lead? A survey of games with incompetent players tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 13 year: '2023' ... --- _id: '14417' abstract: - lang: eng text: Entropic risk (ERisk) is an established risk measure in finance, quantifying risk by an exponential re-weighting of rewards. We study ERisk for the first time in the context of turn-based stochastic games with the total reward objective. This gives rise to an objective function that demands the control of systems in a risk-averse manner. We show that the resulting games are determined and, in particular, admit optimal memoryless deterministic strategies. This contrasts risk measures that previously have been considered in the special case of Markov decision processes and that require randomization and/or memory. We provide several results on the decidability and the computational complexity of the threshold problem, i.e. whether the optimal value of ERisk exceeds a given threshold. In the most general case, the problem is decidable subject to Shanuel’s conjecture. If all inputs are rational, the resulting threshold problem can be solved using algebraic numbers, leading to decidability via a polynomial-time reduction to the existential theory of the reals. Further restrictions on the encoding of the input allow the solution of the threshold problem in NP∩coNP. Finally, an approximation algorithm for the optimal value of ERisk is provided. acknowledgement: "This work was partly funded by the ERC CoG 863818 (ForM-SMArt), the DFG Grant\r\n389792660 as part of TRR 248 (Foundations of Perspicuous Software Systems), the Cluster of\r\nExcellence EXC 2050/1 (CeTI, project ID 390696704, as part of Germany’s Excellence Strategy), and the DFG projects BA-1679/11-1 and BA-1679/12-1." alternative_title: - LIPIcs article_number: '15' article_processing_charge: Yes author: - first_name: Christel full_name: Baier, Christel last_name: Baier - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Tobias full_name: Meggendorfer, Tobias id: b21b0c15-30a2-11eb-80dc-f13ca25802e1 last_name: Meggendorfer orcid: 0000-0002-1712-2165 - first_name: Jakob full_name: Piribauer, Jakob last_name: Piribauer citation: ama: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Entropic risk for turn-based stochastic games. In: 48th International Symposium on Mathematical Foundations of Computer Science. Vol 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.MFCS.2023.15' apa: 'Baier, C., Chatterjee, K., Meggendorfer, T., & Piribauer, J. (2023). Entropic risk for turn-based stochastic games. In 48th International Symposium on Mathematical Foundations of Computer Science (Vol. 272). Bordeaux, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2023.15' chicago: Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. “Entropic Risk for Turn-Based Stochastic Games.” In 48th International Symposium on Mathematical Foundations of Computer Science, Vol. 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.MFCS.2023.15. ieee: C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Entropic risk for turn-based stochastic games,” in 48th International Symposium on Mathematical Foundations of Computer Science, Bordeaux, France, 2023, vol. 272. ista: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2023. Entropic risk for turn-based stochastic games. 48th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 272, 15.' mla: Baier, Christel, et al. “Entropic Risk for Turn-Based Stochastic Games.” 48th International Symposium on Mathematical Foundations of Computer Science, vol. 272, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.MFCS.2023.15. short: C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 48th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-09-01 location: Bordeaux, France name: 'MFCS: Symposium on Mathematical Foundations of Computer Science' start_date: 2023-08-28 date_created: 2023-10-09T09:21:05Z date_published: 2023-08-21T00:00:00Z date_updated: 2023-10-09T09:22:37Z day: '21' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.MFCS.2023.15 ec_funded: 1 external_id: arxiv: - '2307.06611' file: - access_level: open_access checksum: 402281b17ed669bbf149d0fdf68ac201 content_type: application/pdf creator: dernst date_created: 2023-10-09T09:19:11Z date_updated: 2023-10-09T09:19:11Z file_id: '14418' file_name: 2023_LIPIcsMFCS_Baier.pdf file_size: 826843 relation: main_file success: 1 file_date_updated: 2023-10-09T09:19:11Z has_accepted_license: '1' intvolume: ' 272' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: 48th International Symposium on Mathematical Foundations of Computer Science publication_identifier: eissn: - 1868-8969 isbn: - '9783959772921' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Entropic risk for turn-based stochastic games tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 272 year: '2023' ... --- _id: '12706' abstract: - lang: eng text: Allometric settings of population dynamics models are appealing due to their parsimonious nature and broad utility when studying system level effects. Here, we parameterise the size-scaled Rosenzweig-MacArthur differential equations to eliminate prey-mass dependency, facilitating an in depth analytic study of the equations which incorporates scaling parameters’ contributions to coexistence. We define the functional response term to match empirical findings, and examine situations where metabolic theory derivations and observation diverge. The dynamical properties of the Rosenzweig-MacArthur system, encompassing the distribution of size-abundance equilibria, the scaling of period and amplitude of population cycling, and relationships between predator and prey abundances, are consistent with empirical observation. Our parameterisation is an accurate minimal model across 15+ orders of mass magnitude. acknowledgement: "This research was supported by an Australian Government Research Training Program\r\n(RTP) Scholarship to JCM (https://www.dese.gov.au), and LB is supported by the Centre de\r\nrecherche sur le vieillissement Fellowship Program. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript." article_processing_charge: No article_type: original author: - first_name: Jody C. full_name: Mckerral, Jody C. last_name: Mckerral - first_name: Maria full_name: Kleshnina, Maria id: 4E21749C-F248-11E8-B48F-1D18A9856A87 last_name: Kleshnina - first_name: Vladimir full_name: Ejov, Vladimir last_name: Ejov - first_name: Louise full_name: Bartle, Louise last_name: Bartle - first_name: James G. full_name: Mitchell, James G. last_name: Mitchell - first_name: Jerzy A. full_name: Filar, Jerzy A. last_name: Filar citation: ama: Mckerral JC, Kleshnina M, Ejov V, Bartle L, Mitchell JG, Filar JA. Empirical parameterisation and dynamical analysis of the allometric Rosenzweig-MacArthur equations. PLoS One. 2023;18(2):e0279838. doi:10.1371/journal.pone.0279838 apa: Mckerral, J. C., Kleshnina, M., Ejov, V., Bartle, L., Mitchell, J. G., & Filar, J. A. (2023). Empirical parameterisation and dynamical analysis of the allometric Rosenzweig-MacArthur equations. PLoS One. Public Library of Science. https://doi.org/10.1371/journal.pone.0279838 chicago: Mckerral, Jody C., Maria Kleshnina, Vladimir Ejov, Louise Bartle, James G. Mitchell, and Jerzy A. Filar. “Empirical Parameterisation and Dynamical Analysis of the Allometric Rosenzweig-MacArthur Equations.” PLoS One. Public Library of Science, 2023. https://doi.org/10.1371/journal.pone.0279838. ieee: J. C. Mckerral, M. Kleshnina, V. Ejov, L. Bartle, J. G. Mitchell, and J. A. Filar, “Empirical parameterisation and dynamical analysis of the allometric Rosenzweig-MacArthur equations,” PLoS One, vol. 18, no. 2. Public Library of Science, p. e0279838, 2023. ista: Mckerral JC, Kleshnina M, Ejov V, Bartle L, Mitchell JG, Filar JA. 2023. Empirical parameterisation and dynamical analysis of the allometric Rosenzweig-MacArthur equations. PLoS One. 18(2), e0279838. mla: Mckerral, Jody C., et al. “Empirical Parameterisation and Dynamical Analysis of the Allometric Rosenzweig-MacArthur Equations.” PLoS One, vol. 18, no. 2, Public Library of Science, 2023, p. e0279838, doi:10.1371/journal.pone.0279838. short: J.C. Mckerral, M. Kleshnina, V. Ejov, L. Bartle, J.G. Mitchell, J.A. Filar, PLoS One 18 (2023) e0279838. date_created: 2023-03-05T23:01:05Z date_published: 2023-02-27T00:00:00Z date_updated: 2023-10-17T12:53:30Z day: '27' ddc: - '000' department: - _id: KrCh doi: 10.1371/journal.pone.0279838 external_id: isi: - '000996122900022' pmid: - '36848357' file: - access_level: open_access checksum: 798ed5739a4117b03173e5d56e0534c9 content_type: application/pdf creator: cchlebak date_created: 2023-03-07T10:26:45Z date_updated: 2023-03-07T10:26:45Z file_id: '12712' file_name: 2023_PLOSOne_Mckerral.pdf file_size: 1257003 relation: main_file success: 1 file_date_updated: 2023-03-07T10:26:45Z has_accepted_license: '1' intvolume: ' 18' isi: 1 issue: '2' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: e0279838 pmid: 1 publication: PLoS One publication_identifier: eissn: - 1932-6203 publication_status: published publisher: Public Library of Science quality_controlled: '1' scopus_import: '1' status: public title: Empirical parameterisation and dynamical analysis of the allometric Rosenzweig-MacArthur equations tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 18 year: '2023' ... --- _id: '14518' abstract: - lang: eng text: We consider bidding games, a class of two-player zero-sum graph games. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token, where we break bidding ties in favor of Player 1. Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, poorman discrete-bidding in which the granularity of the bids is restricted and the higher bid is paid to the bank. Previous work either did not impose granularity restrictions or considered Richman bidding (bids are paid to the opponent). While the latter mechanisms are technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on threshold budgets, which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We first show existence of thresholds. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets. acknowledgement: This research was supported in part by ISF grant no. 1679/21, ERC CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie Grant Agreement No. 665385. article_processing_charge: No author: - first_name: Guy full_name: Avni, Guy id: 463C8BC2-F248-11E8-B48F-1D18A9856A87 last_name: Avni orcid: 0000-0001-5588-8287 - first_name: Tobias full_name: Meggendorfer, Tobias id: b21b0c15-30a2-11eb-80dc-f13ca25802e1 last_name: Meggendorfer orcid: 0000-0002-1712-2165 - first_name: Suman full_name: Sadhukhan, Suman last_name: Sadhukhan - first_name: Josef full_name: Tkadlec, Josef id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87 last_name: Tkadlec orcid: 0000-0002-1097-9684 - first_name: Dorde full_name: Zikelic, Dorde id: 294AA7A6-F248-11E8-B48F-1D18A9856A87 last_name: Zikelic orcid: 0000-0002-4681-1699 citation: ama: 'Avni G, Meggendorfer T, Sadhukhan S, Tkadlec J, Zikelic D. Reachability poorman discrete-bidding games. In: Frontiers in Artificial Intelligence and Applications. Vol 372. IOS Press; 2023:141-148. doi:10.3233/FAIA230264' apa: 'Avni, G., Meggendorfer, T., Sadhukhan, S., Tkadlec, J., & Zikelic, D. (2023). Reachability poorman discrete-bidding games. In Frontiers in Artificial Intelligence and Applications (Vol. 372, pp. 141–148). Krakow, Poland: IOS Press. https://doi.org/10.3233/FAIA230264' chicago: Avni, Guy, Tobias Meggendorfer, Suman Sadhukhan, Josef Tkadlec, and Dorde Zikelic. “Reachability Poorman Discrete-Bidding Games.” In Frontiers in Artificial Intelligence and Applications, 372:141–48. IOS Press, 2023. https://doi.org/10.3233/FAIA230264. ieee: G. Avni, T. Meggendorfer, S. Sadhukhan, J. Tkadlec, and D. Zikelic, “Reachability poorman discrete-bidding games,” in Frontiers in Artificial Intelligence and Applications, Krakow, Poland, 2023, vol. 372, pp. 141–148. ista: 'Avni G, Meggendorfer T, Sadhukhan S, Tkadlec J, Zikelic D. 2023. Reachability poorman discrete-bidding games. Frontiers in Artificial Intelligence and Applications. ECAI: European Conference on Artificial Intelligence vol. 372, 141–148.' mla: Avni, Guy, et al. “Reachability Poorman Discrete-Bidding Games.” Frontiers in Artificial Intelligence and Applications, vol. 372, IOS Press, 2023, pp. 141–48, doi:10.3233/FAIA230264. short: G. Avni, T. Meggendorfer, S. Sadhukhan, J. Tkadlec, D. Zikelic, in:, Frontiers in Artificial Intelligence and Applications, IOS Press, 2023, pp. 141–148. conference: end_date: 2023-10-04 location: Krakow, Poland name: 'ECAI: European Conference on Artificial Intelligence' start_date: 2023-09-30 date_created: 2023-11-12T23:00:56Z date_published: 2023-09-28T00:00:00Z date_updated: 2023-11-13T10:18:45Z day: '28' ddc: - '000' department: - _id: ToHe - _id: KrCh doi: 10.3233/FAIA230264 ec_funded: 1 external_id: arxiv: - '2307.15218' file: - access_level: open_access checksum: 1390ca38480fa4cf286b0f1a42e8c12f content_type: application/pdf creator: dernst date_created: 2023-11-13T10:16:10Z date_updated: 2023-11-13T10:16:10Z file_id: '14529' file_name: 2023_FAIA_Avni.pdf file_size: 501011 relation: main_file success: 1 file_date_updated: 2023-11-13T10:16:10Z has_accepted_license: '1' intvolume: ' 372' language: - iso: eng license: https://creativecommons.org/licenses/by-nc/4.0/ month: '09' oa: 1 oa_version: Published Version page: 141-148 project: - _id: 2564DBCA-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '665385' name: International IST Doctoral Program - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: Frontiers in Artificial Intelligence and Applications publication_identifier: isbn: - '9781643684369' issn: - 0922-6389 publication_status: published publisher: IOS Press quality_controlled: '1' scopus_import: '1' status: public title: Reachability poorman discrete-bidding games tmp: image: /images/cc_by_nc.png legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) short: CC BY-NC (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 372 year: '2023' ... --- _id: '14559' abstract: - lang: eng text: We consider the problem of learning control policies in discrete-time stochastic systems which guarantee that the system stabilizes within some specified stabilization region with probability 1. Our approach is based on the novel notion of stabilizing ranking supermartingales (sRSMs) that we introduce in this work. Our sRSMs overcome the limitation of methods proposed in previous works whose applicability is restricted to systems in which the stabilizing region cannot be left once entered under any control policy. We present a learning procedure that learns a control policy together with an sRSM that formally certifies probability 1 stability, both learned as neural networks. We show that this procedure can also be adapted to formally verifying that, under a given Lipschitz continuous control policy, the stochastic system stabilizes within some stabilizing region with probability 1. Our experimental evaluation shows that our learning procedure can successfully learn provably stabilizing policies in practice. acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093, ERC CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385. alternative_title: - LNCS article_processing_charge: No author: - first_name: Matin full_name: Ansaripour, Matin last_name: Ansaripour - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: Mathias full_name: Lechner, Mathias id: 3DC22916-F248-11E8-B48F-1D18A9856A87 last_name: Lechner - first_name: Dorde full_name: Zikelic, Dorde id: 294AA7A6-F248-11E8-B48F-1D18A9856A87 last_name: Zikelic orcid: 0000-0002-4681-1699 citation: ama: 'Ansaripour M, Chatterjee K, Henzinger TA, Lechner M, Zikelic D. Learning provably stabilizing neural controllers for discrete-time stochastic systems. In: 21st International Symposium on Automated Technology for Verification and Analysis. Vol 14215. Springer Nature; 2023:357-379. doi:10.1007/978-3-031-45329-8_17' apa: 'Ansaripour, M., Chatterjee, K., Henzinger, T. A., Lechner, M., & Zikelic, D. (2023). Learning provably stabilizing neural controllers for discrete-time stochastic systems. In 21st International Symposium on Automated Technology for Verification and Analysis (Vol. 14215, pp. 357–379). Singapore, Singapore: Springer Nature. https://doi.org/10.1007/978-3-031-45329-8_17' chicago: Ansaripour, Matin, Krishnendu Chatterjee, Thomas A Henzinger, Mathias Lechner, and Dorde Zikelic. “Learning Provably Stabilizing Neural Controllers for Discrete-Time Stochastic Systems.” In 21st International Symposium on Automated Technology for Verification and Analysis, 14215:357–79. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-45329-8_17. ieee: M. Ansaripour, K. Chatterjee, T. A. Henzinger, M. Lechner, and D. Zikelic, “Learning provably stabilizing neural controllers for discrete-time stochastic systems,” in 21st International Symposium on Automated Technology for Verification and Analysis, Singapore, Singapore, 2023, vol. 14215, pp. 357–379. ista: 'Ansaripour M, Chatterjee K, Henzinger TA, Lechner M, Zikelic D. 2023. Learning provably stabilizing neural controllers for discrete-time stochastic systems. 21st International Symposium on Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 14215, 357–379.' mla: Ansaripour, Matin, et al. “Learning Provably Stabilizing Neural Controllers for Discrete-Time Stochastic Systems.” 21st International Symposium on Automated Technology for Verification and Analysis, vol. 14215, Springer Nature, 2023, pp. 357–79, doi:10.1007/978-3-031-45329-8_17. short: M. Ansaripour, K. Chatterjee, T.A. Henzinger, M. Lechner, D. Zikelic, in:, 21st International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2023, pp. 357–379. conference: end_date: 2023-10-27 location: Singapore, Singapore name: 'ATVA: Automated Technology for Verification and Analysis' start_date: 2023-10-24 date_created: 2023-11-19T23:00:56Z date_published: 2023-10-22T00:00:00Z date_updated: 2023-11-20T08:30:20Z day: '22' department: - _id: ToHe - _id: KrCh doi: 10.1007/978-3-031-45329-8_17 ec_funded: 1 intvolume: ' 14215' language: - iso: eng month: '10' oa_version: None page: 357-379 project: - _id: 62781420-2b32-11ec-9570-8d9b63373d4d call_identifier: H2020 grant_number: '101020093' name: Vigilant Algorithmic Monitoring of Software - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' - _id: 2564DBCA-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '665385' name: International IST Doctoral Program publication: 21st International Symposium on Automated Technology for Verification and Analysis publication_identifier: eissn: - 1611-3349 isbn: - '9783031453281' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Learning provably stabilizing neural controllers for discrete-time stochastic systems type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 14215 year: '2023' ... --- _id: '13238' abstract: - lang: eng 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 much 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 (u, v) 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+ε)⋅(1+3–√) for some arbitrary ε>0.\r\n." 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. alternative_title: - LNCS article_processing_charge: No author: - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid - first_name: Jakub full_name: Svoboda, Jakub id: 130759D2-D7DD-11E9-87D2-DE0DE6697425 last_name: Svoboda orcid: 0000-0002-1419-3267 - first_name: Michelle X full_name: Yeo, Michelle X id: 2D82B818-F248-11E8-B48F-1D18A9856A87 last_name: Yeo citation: ama: 'Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In: SIROCCO 2023: Structural Information and Communication Complexity . Vol 13892. Springer Nature; 2023:576-594. doi:10.1007/978-3-031-32733-9_26' apa: 'Schmid, S., Svoboda, J., & Yeo, M. X. (2023). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In SIROCCO 2023: Structural Information and Communication Complexity (Vol. 13892, pp. 576–594). Alcala de Henares, Spain: Springer Nature. https://doi.org/10.1007/978-3-031-32733-9_26' chicago: 'Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” In SIROCCO 2023: Structural Information and Communication Complexity , 13892:576–94. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-32733-9_26.' ieee: 'S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” in SIROCCO 2023: Structural Information and Communication Complexity , Alcala de Henares, Spain, 2023, vol. 13892, pp. 576–594.' ista: 'Schmid S, Svoboda J, Yeo MX. 2023. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. SIROCCO 2023: Structural Information and Communication Complexity . SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 13892, 576–594.' mla: 'Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” SIROCCO 2023: Structural Information and Communication Complexity , vol. 13892, Springer Nature, 2023, pp. 576–94, doi:10.1007/978-3-031-32733-9_26.' short: 'S. Schmid, J. Svoboda, M.X. Yeo, in:, SIROCCO 2023: Structural Information and Communication Complexity , Springer Nature, 2023, pp. 576–594.' conference: end_date: 2023-06-09 location: Alcala de Henares, Spain name: 'SIROCCO: Structural Information and Communication Complexity' start_date: 2023-06-06 date_created: 2023-07-16T22:01:12Z date_published: 2023-05-25T00:00:00Z date_updated: 2023-11-30T10:54:51Z day: '25' department: - _id: KrPi - _id: KrCh doi: 10.1007/978-3-031-32733-9_26 ec_funded: 1 external_id: arxiv: - '2204.13459' intvolume: ' 13892' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2204.13459 month: '05' oa: 1 oa_version: Preprint page: 576-594 project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: 'SIROCCO 2023: Structural Information and Communication Complexity ' publication_identifier: eissn: - 1611-3349 isbn: - '9783031327322' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '14506' relation: dissertation_contains status: public scopus_import: '1' status: public title: 'Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 13892 year: '2023' ...