Nondeterministic strategies are strategies (or protocols, or plans) that, given a history in a game, assign a set of possible actions, all of which should be 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 maximally permissive Nash equilibria.

Nondeterministic strategies and their refinement in strategy logic / De Giacomo, G.; Maubert, B.; Murano, A.. - 1:(2020), pp. 293-302. (Intervento presentato al convegno 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020 nel 2020) [10.24963/kr.2020/30].

Nondeterministic strategies and their refinement in strategy logic

Maubert B.;Murano A.
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 should be 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 maximally permissive Nash equilibria.
2020
978-0-9992411-7-2
Nondeterministic strategies and their refinement in strategy logic / De Giacomo, G.; Maubert, B.; Murano, A.. - 1:(2020), pp. 293-302. (Intervento presentato al convegno 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020 nel 2020) [10.24963/kr.2020/30].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11588/880494
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact