Reactive Synthesis of Dominant Strategies
Authors: Benjamin Aminof, Giuseppe De Giacomo, Sasha Rubin
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that dominant strategies may exist when enforcing ones do not, while still sharing with the latter many desirable properties such as being interchangeable with each other, and being monotone with respect to tightening of environment specifications. We give necessary and sufficient conditions for the existence of dominant strategies, and show that deciding if they exist is 2EXPTIME-complete the same as for enforcing strategies. Finally, we give a uniform, optimal, game-theoretic algorithm for simultaneously solving the three synthesis problems of enforcing, dominant, and best-effort strategies. |
| Researcher Affiliation | Academia | Benjamin Aminof1,3, Giuseppe De Giacomo2, 3, Sasha Rubin4 1 TU Wien 2 University of Oxford 3 Universit a degli Studi di Roma La Sapienza 4 University of Sydney |
| Pseudocode | Yes | Unifying Algorithm. Given LTL/LTLf formulas ϕ, E: 1. Using Theorem 11, for every ξ { E, E ϕ, E ϕ} compute the DPAs (resp. DFAs) Aξ = (Dξ, Fξ). 2. Using Definition 7 form (in linear time) the product D = D E DE ϕ DE ϕ. ... (steps 3-11 follow) |
| Open Source Code | No | The paper does not provide any statement about concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not mention using any datasets for training or provide access information for a public dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe any empirical experiments or provide specific dataset split information. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers needed to replicate any experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details, hyperparameters, or training configurations. |