The Experts below are selected from a list of 42606 Experts worldwide ranked by ideXlab platform
Aniello Murano - One of the best experts on this subject based on the ideXlab platform.
-
Strategy Logic with Imperfect Information
ACM Transactions on Computational Logic, 2021Co-Authors: Raphaël Berthon, Aniello Murano, Bastien Maubert, Sasha Rubin, Moshe Y. VardiAbstract:We introduce an extension of Strategy Logic for the Imperfect-Information setting, called SLii and study its model-checking problem. As this logic naturally captures multi-player games with Imperfect Information, this problem is undecidable; but we introduce a syntactical class of “hierarchical instances” for which, intuitively, as one goes down the syntactic tree of the formula, strategy quantifications are concerned with finer observations of the model, and we prove that model-checking SLii restricted to hierarchical instances is decidable. This result, because it allows for complex patterns of existential and universal quantification on strategies, greatly generalises the decidability of distributed synthesis for systems with hierarchical Information. It allows us to easily derive new decidability results concerning strategic problems under Imperfect Information such as the existence of Nash equilibria or rational synthesis.To establish this result, we go through an intermediary, “low-level” logic much more adapted to automata techniques. QCTLa is an extension of CTLa with second-order quantification over atomic propositions that has been used to study strategic logics with perfect Information. We extend it to the Imperfect Information setting by parameterising second-order quantifiers with observations. The simple syntax of the resulting logic, QCTLaii, allows us to provide a conceptually neat reduction of SLii to QCTLaii that separates concerns, allowing one to forget about strategies and players and focus solely on second-order quantification. While the model-checking problem of QCTLaii is, in general, undecidable, we identify a syntactic fragment of hierarchical formulas and prove, using an automata-theoretic approach, that it is decidable.
-
Natural strategic ability under Imperfect Information
2019Co-Authors: Wojciech Jamroga, Vadim Malvone, Aniello MuranoAbstract:Strategies in game theory and multi-agent logics are mathematical objects of remarkable combinatorial complexity Recently, the concept of natural strategies has been proposed to model more human-like reasoning about simple plans and their outcomes So far, the theory of such simple strategic play was only considered in scenarios where all the agents have perfect Information about the state of the game In this paper, we extend the notion of natural strategies to games with Imperfect Information We also show that almost all the complexity results for model checking carry over from the perfect to Imperfect Information setting That is, verification of natural strategies is usually no more complex for agents with uncertainty This tells games of natural strategic ability clearly apart from most results in game theory and multi-agent logics.
-
Decidability results for ATL* with Imperfect Information and perfect recall
arXiv: Logic in Computer Science, 2018Co-Authors: Raphaël Berthon, Bastien Maubert, Aniello MuranoAbstract:Alternating-time Temporal Logic (ATL*) is a central logic for multiagent systems. Its extension to the Imperfect Information setting (ATL*i ) is well known to have an undecidable model-checking problem when agents have perfect recall. Studies have thus mostly focused either on agents without memory, or on alternative semantics to retrieve decidability. In this work we establish new decidability results for agents with perfect recall: We first prove a meta-theorem that allows the transfer of decidability results for classes of multiplayer games with Imperfect Information, such as games with hierarchical observation, to the model-checking problem for ATL*i . We then establish that model checking ATL* with strategy context and Imperfect Information is decidable when restricted to hierarchical instances.
-
Strategy logic with Imperfect Information
2017 32nd Annual ACM IEEE Symposium on Logic in Computer Science (LICS), 2017Co-Authors: Raphaël Berthon, Aniello Murano, Bastien Maubert, Sasha Rubin, Moshe Y. VardiAbstract:We introduce an extension of Strategy logic for the Imperfect-Information setting, called SLii, and study its model-checking problem. As this logic naturally captures multi-player games with Imperfect Information, the problem turns out to be undecidable. We introduce a syntactical class of “hierarchical instances” for which, intuitively, as one goes down the syntactic tree of the formula, strategy quantifications are concerned with finer observations of the model. We prove that model-checking SLii restricted to hierarchical instances is decidable. This result, because it allows for complex patterns of existential and universal quantification on strategies, greatly generalises previous ones, such as decidability of multi-player games with Imperfect Information and hierarchical observations, and decidability of distributed synthesis for hierarchical systems. To establish the decidability result, we introduce and study QCTLii*, an extension of QCTL (itself an extension of CTL with second-order quantification over atomic propositions) by parameterising its quantifiers with observations. The simple syntax of QCTLii* allows us to provide a conceptually neat reduction of SLii to QCTLii* that separates concerns, allowing one to forget about strategies and players and focus solely on second-order quantification. While the model-checking problem of QCTLii* is, in general, undecidable, we identify a syntactic fragment of hierarchical formulas and prove, using an automata-theoretic approach, that it is decidable. The decidability result for SLii follows since the reduction maps hierarchical instances of SLii to hierarchical formulas of QCTLii*.
-
AAMAS - Decidability Results for ATL* with Imperfect Information and Perfect Recall
2017Co-Authors: Raphaël Berthon, Bastien Maubert, Aniello MuranoAbstract:Alternating-time Temporal Logic (ATL*) is a central logic for multiagent systems. Its extension to the Imperfect Information setting (ATL*_i) is well known to have an undecidable model-checking problem when agents have perfect recall. Studies have thus mostly focused either on agents without memory, or on alternative semantics to retrieve decidability. In this work we establish new decidability results for agents with perfect recall: We first prove a meta-theorem that allows the transfer of decidability results for classes of multiplayer games with Imperfect Information, such as games with hierarchical observation, to the model-checking problem for ATL*_i. We then establish that model checking ATL* with strategy context and Imperfect Information is decidable when restricted to hierarchical instances.
Moshe Y. Vardi - One of the best experts on this subject based on the ideXlab platform.
-
Strategy Logic with Imperfect Information
ACM Transactions on Computational Logic, 2021Co-Authors: Raphaël Berthon, Aniello Murano, Bastien Maubert, Sasha Rubin, Moshe Y. VardiAbstract:We introduce an extension of Strategy Logic for the Imperfect-Information setting, called SLii and study its model-checking problem. As this logic naturally captures multi-player games with Imperfect Information, this problem is undecidable; but we introduce a syntactical class of “hierarchical instances” for which, intuitively, as one goes down the syntactic tree of the formula, strategy quantifications are concerned with finer observations of the model, and we prove that model-checking SLii restricted to hierarchical instances is decidable. This result, because it allows for complex patterns of existential and universal quantification on strategies, greatly generalises the decidability of distributed synthesis for systems with hierarchical Information. It allows us to easily derive new decidability results concerning strategic problems under Imperfect Information such as the existence of Nash equilibria or rational synthesis.To establish this result, we go through an intermediary, “low-level” logic much more adapted to automata techniques. QCTLa is an extension of CTLa with second-order quantification over atomic propositions that has been used to study strategic logics with perfect Information. We extend it to the Imperfect Information setting by parameterising second-order quantifiers with observations. The simple syntax of the resulting logic, QCTLaii, allows us to provide a conceptually neat reduction of SLii to QCTLaii that separates concerns, allowing one to forget about strategies and players and focus solely on second-order quantification. While the model-checking problem of QCTLaii is, in general, undecidable, we identify a syntactic fragment of hierarchical formulas and prove, using an automata-theoretic approach, that it is decidable.
-
Strategy logic with Imperfect Information
2017 32nd Annual ACM IEEE Symposium on Logic in Computer Science (LICS), 2017Co-Authors: Raphaël Berthon, Aniello Murano, Bastien Maubert, Sasha Rubin, Moshe Y. VardiAbstract:We introduce an extension of Strategy logic for the Imperfect-Information setting, called SLii, and study its model-checking problem. As this logic naturally captures multi-player games with Imperfect Information, the problem turns out to be undecidable. We introduce a syntactical class of “hierarchical instances” for which, intuitively, as one goes down the syntactic tree of the formula, strategy quantifications are concerned with finer observations of the model. We prove that model-checking SLii restricted to hierarchical instances is decidable. This result, because it allows for complex patterns of existential and universal quantification on strategies, greatly generalises previous ones, such as decidability of multi-player games with Imperfect Information and hierarchical observations, and decidability of distributed synthesis for hierarchical systems. To establish the decidability result, we introduce and study QCTLii*, an extension of QCTL (itself an extension of CTL with second-order quantification over atomic propositions) by parameterising its quantifiers with observations. The simple syntax of QCTLii* allows us to provide a conceptually neat reduction of SLii to QCTLii* that separates concerns, allowing one to forget about strategies and players and focus solely on second-order quantification. While the model-checking problem of QCTLii* is, in general, undecidable, we identify a syntactic fragment of hierarchical formulas and prove, using an automata-theoretic approach, that it is decidable. The decidability result for SLii follows since the reduction maps hierarchical instances of SLii to hierarchical formulas of QCTLii*.
-
Pushdown module checking with Imperfect Information
Information and Computation, 2013Co-Authors: Benjamin Aminof, Axel Legay, Aniello Murano, Olivier Serre, Moshe Y. VardiAbstract:The model checking problem for finite-state open systems (module checking) has been extensively studied in the literature, both in the context of environments with perfect and Imperfect Information about the system. Recently, the perfect Information case has been extended to infinite-state systems (pushdown module checking). In this paper, we extend pushdown module checking to the Imperfect Information setting; i.e., to the case where the environment has only a partial view of the [email protected]?s control states and pushdown store content. We study the complexity of this problem with respect to the branching-time temporal logics CTL, CTL^@? and the propositional @m-calculus. We show that pushdown module checking, which is by itself harder than pushdown model checking, becomes undecidable when the environment has Imperfect Information. We also show that undecidability relies on hiding Information about the pushdown store. Indeed, we prove that with Imperfect Information about the control states, but a visible pushdown store, the problem is decidable and its complexity is 2Exptime-complete for CTL and the propositional @m-calculus, and 3Exptime-complete for CTL^@?.
-
CONCUR - Pushdown module checking with Imperfect Information
CONCUR 2007 – Concurrency Theory, 1Co-Authors: Benjamin Aminof, Aniello Murano, Moshe Y. VardiAbstract:The model checking problem for finite-state open systems (module checking) has been extensively studied in the literature, both in the context of environments with perfect and Imperfect Information about the system. Recently, the perfect Information case has been extended to infinite-state systems (pushdown module checking). In this paper, we extend pushdown module checking to the Imperfect Information setting; i.e., the environment has only a partial view of the system's control states and pushdown store content. We study the complexity of this problem with respect to the branching-time temporal logic CTL, and show that pushdown module checking, which is by itself harder than pushdown model checking, becomes undecidable when the environment has Imperfect Information. We also show that undecidability relies on hiding Information about the pushdown store. Indeed, we prove that with Imperfect Information about the control states, but a visible pushdown store, the problem is decidable and its complexity is the same as that of (perfect Information) pushdown module checking.
Benjamin Aminof - One of the best experts on this subject based on the ideXlab platform.
-
Pushdown module checking with Imperfect Information
Information and Computation, 2013Co-Authors: Benjamin Aminof, Axel Legay, Aniello Murano, Olivier Serre, Moshe Y. VardiAbstract:The model checking problem for finite-state open systems (module checking) has been extensively studied in the literature, both in the context of environments with perfect and Imperfect Information about the system. Recently, the perfect Information case has been extended to infinite-state systems (pushdown module checking). In this paper, we extend pushdown module checking to the Imperfect Information setting; i.e., to the case where the environment has only a partial view of the [email protected]?s control states and pushdown store content. We study the complexity of this problem with respect to the branching-time temporal logics CTL, CTL^@? and the propositional @m-calculus. We show that pushdown module checking, which is by itself harder than pushdown model checking, becomes undecidable when the environment has Imperfect Information. We also show that undecidability relies on hiding Information about the pushdown store. Indeed, we prove that with Imperfect Information about the control states, but a visible pushdown store, the problem is decidable and its complexity is 2Exptime-complete for CTL and the propositional @m-calculus, and 3Exptime-complete for CTL^@?.
-
Pushdown Module Checking with Imperfect Information
Information and Computation, 2013Co-Authors: Benjamin Aminof, Axel Legay, Aniello Murano, Olivier Serre, Moshe VardiAbstract:The model checking problem for finite-state open systems (module checking) has been extensively studied in the literature, both in the context of environments with perfect and Imperfect Information about the system. Recently , the perfect Information case has been extended to infinite-state systems (pushdown module checking). In this paper, we extend pushdown module checking to the Imperfect Information setting; i.e., to the case where the environment has only a partial view of the system's control states and push-down store content. We study the complexity of this problem with respect to the branching-time temporal logics CTL, CTL * and the propositional µ-calculus. We show that pushdown module checking, which is by itself harder than pushdown model checking, becomes undecidable when the environment has Imperfect Information. We also show that undecidability relies on hiding Information about the pushdown store. Indeed, we prove that with Imperfect Information about the control states, but a visible pushdown store, the problem is decidable and its complexity is 2Exptime-complete for CTL and the propositional µ-calculus, and 3Exptime-complete for CTL * .
-
Pushdown Module Checking with Imperfect Information
2010Co-Authors: Benjamin Aminof, Axel Legay, Aniello Murano, Olivier Serre, Moshe VardiAbstract:The model checking problem for finite-state open systems (module checking) has been extensively studied in the literature, both in the context of environments with perfect and Imperfect Information about the system. Recently, the perfect Information case has been extended to infinite-state systems (pushdown module checking). In this part, we extend pushdown module checking to the Imperfect Information setting; i.e., to the case where the environment has only a partial view of the system's control states and pushdown store content. We study the complexity of this problem with respect to the branching-time temporal logics CTL, CTL* and the propositional mu-calculus. We show that pushdown module checking, which is by itself harder than pushdown model checking, becomes undecidable when the environment has Imperfect Information. We also show that undecidability relies on hiding Information about the pushdown store. Indeed, we prove that with Imperfect Information about the control states, but a visible pushdown store, the problem is decidable and its complexity is 2ExpTime-complete for CTL and the propositional mu-calculus, and 3ExpTime-complete for CTL*.
-
CONCUR - Pushdown module checking with Imperfect Information
CONCUR 2007 – Concurrency Theory, 1Co-Authors: Benjamin Aminof, Aniello Murano, Moshe Y. VardiAbstract:The model checking problem for finite-state open systems (module checking) has been extensively studied in the literature, both in the context of environments with perfect and Imperfect Information about the system. Recently, the perfect Information case has been extended to infinite-state systems (pushdown module checking). In this paper, we extend pushdown module checking to the Imperfect Information setting; i.e., the environment has only a partial view of the system's control states and pushdown store content. We study the complexity of this problem with respect to the branching-time temporal logic CTL, and show that pushdown module checking, which is by itself harder than pushdown model checking, becomes undecidable when the environment has Imperfect Information. We also show that undecidability relies on hiding Information about the pushdown store. Indeed, we prove that with Imperfect Information about the control states, but a visible pushdown store, the problem is decidable and its complexity is the same as that of (perfect Information) pushdown module checking.
Thomas A. Henzinger - One of the best experts on this subject based on the ideXlab platform.
-
Strategy construction for parity games with Imperfect Information
Information and Computation, 2010Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Martin De Wulf, Thomas A. HenzingerAbstract:We consider two-player parity games with Imperfect Information in which strategies rely on observations that provide Imperfect Information about the history of a play. To solve such games, i.e., to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-Information game. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of Imperfect Information. One major obstacle in adapting the classical procedure is that the complementation of attractor sets would break the invariant of downward-closedness on which the antichain representation relies. We overcome this difficulty by decomposing problem instances recursively into games with a combination of reachability, safety, and simpler parity conditions. We also report on an experimental implementation of our algorithm; to our knowledge, this is the first implementation of a procedure for solving Imperfect-Information parity games on graphs.
-
strategy construction for parity games with Imperfect Information
International Conference on Concurrency Theory, 2008Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Sangram RajeAbstract:We consider Imperfect-Informationparity games in which strategies rely on observations that provide Imperfect Information about the history of a play. To solve such games, i.e.to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-Informationgame. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of Imperfect Information. We have implemented this algorithm as a prototype. To our knowledge, this is the first implementation of a procedure for solving Imperfect-Information parity games on graphs.
-
CONCUR - Strategy Construction for Parity Games with Imperfect Information
CONCUR 2008 - Concurrency Theory, 2008Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Sangram RajeAbstract:We consider Imperfect-Informationparity games in which strategies rely on observations that provide Imperfect Information about the history of a play. To solve such games, i.e.to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-Informationgame. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of Imperfect Information. We have implemented this algorithm as a prototype. To our knowledge, this is the first implementation of a procedure for solving Imperfect-Information parity games on graphs.
Dietmar Berwanger - One of the best experts on this subject based on the ideXlab platform.
-
Strategy construction for parity games with Imperfect Information
Information and Computation, 2010Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Martin De Wulf, Thomas A. HenzingerAbstract:We consider two-player parity games with Imperfect Information in which strategies rely on observations that provide Imperfect Information about the history of a play. To solve such games, i.e., to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-Information game. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of Imperfect Information. One major obstacle in adapting the classical procedure is that the complementation of attractor sets would break the invariant of downward-closedness on which the antichain representation relies. We overcome this difficulty by decomposing problem instances recursively into games with a combination of reachability, safety, and simpler parity conditions. We also report on an experimental implementation of our algorithm; to our knowledge, this is the first implementation of a procedure for solving Imperfect-Information parity games on graphs.
-
strategy construction for parity games with Imperfect Information
International Conference on Concurrency Theory, 2008Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Sangram RajeAbstract:We consider Imperfect-Informationparity games in which strategies rely on observations that provide Imperfect Information about the history of a play. To solve such games, i.e.to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-Informationgame. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of Imperfect Information. We have implemented this algorithm as a prototype. To our knowledge, this is the first implementation of a procedure for solving Imperfect-Information parity games on graphs.
-
CONCUR - Strategy Construction for Parity Games with Imperfect Information
CONCUR 2008 - Concurrency Theory, 2008Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Sangram RajeAbstract:We consider Imperfect-Informationparity games in which strategies rely on observations that provide Imperfect Information about the history of a play. To solve such games, i.e.to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-Informationgame. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of Imperfect Information. We have implemented this algorithm as a prototype. To our knowledge, this is the first implementation of a procedure for solving Imperfect-Information parity games on graphs.
-
FSTTCS - On the power of Imperfect Information
2008Co-Authors: Dietmar Berwanger, Laurent DoyenAbstract:We present a polynomial-time reduction from parity games with Imperfect Information to safety games with Imperfect Information. Similar reductions for games with perfect Information typically increase the game size exponentially. Our construction avoids such a blow-up by using Imperfect Information to realise succinct counters which cover a range exponentially larger than their size. In particular, the reduction shows that the problem of solving Imperfect-Information games with safety conditions is EXPTIME-complete.
