Nondeterministic strategies are strategies (or protocols, or plans) that, given a history in a game, assign a set of possible actions, all of which are winning. An important problem is that of refining such strategies. For instance, given a nondeterministic strategy that allows only safe executions, refine it to, additionally, eventually reach a desired state of affairs. We show that strategic problems involving strategy refinement can be solved elegantly in the framework of Strategy Logic (SL), a very expressive logic to reason about strategic abilities. Specifically, we introduce an extension of SL with nondeterministic strategies and an operator expressing strategy refinement. We show that model checking this logic can be done at no additional computational cost with respect to standard SL, and can be used to solve a variety of problems such as synthesis of maximally permissive strategies or refinement of Nash equilibria.

Nondeterministic Strategies and their Refinement in Strategy Logic / De Giacomo, Giuseppe; Maubert, Bastien; Murano, Aniello. - (2020), pp. 294-303. (Intervento presentato al convegno 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020) tenutosi a Rhodes, Greece) [10.24963/kr.2020/30].

Nondeterministic Strategies and their Refinement in Strategy Logic

De Giacomo, Giuseppe
;
2020

Abstract

Nondeterministic strategies are strategies (or protocols, or plans) that, given a history in a game, assign a set of possible actions, all of which are winning. An important problem is that of refining such strategies. For instance, given a nondeterministic strategy that allows only safe executions, refine it to, additionally, eventually reach a desired state of affairs. We show that strategic problems involving strategy refinement can be solved elegantly in the framework of Strategy Logic (SL), a very expressive logic to reason about strategic abilities. Specifically, we introduce an extension of SL with nondeterministic strategies and an operator expressing strategy refinement. We show that model checking this logic can be done at no additional computational cost with respect to standard SL, and can be used to solve a variety of problems such as synthesis of maximally permissive strategies or refinement of Nash equilibria.
2020
17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020)
Artificial Intelligence; Knowledge Representation; Reasoning about Actions
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Nondeterministic Strategies and their Refinement in Strategy Logic / De Giacomo, Giuseppe; Maubert, Bastien; Murano, Aniello. - (2020), pp. 294-303. (Intervento presentato al convegno 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020) tenutosi a Rhodes, Greece) [10.24963/kr.2020/30].
File allegati a questo prodotto
File Dimensione Formato  
DeGiacomo_Nondeterministic_2020.pdf

accesso aperto

Note: https://doi.org/10.24963/kr.2020/30
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 202.27 kB
Formato Adobe PDF
202.27 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1506323
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact