On Domination and Control in Strategic Ability

We propose a technique to compare partial strategies for agents and coalitions in multi-agent environments with imperfect information. The proposed relation mimics the game-theoretic notion of strategic dominance: a stronger partial strategy can replace a weaker one in a full strategy, while preserving the enforceability of a given goal. Our version of dominance is based on a new notion of input/output characteristics for partial strategies. Intuitively, the inputs are the states where the strategy gains control over execution, and the outputs are the states where it returns the control to the environment. Moreover, we identify the sources of dependence between partial strategies, and show conditions under which they can be analysed in a fully independent way. We evaluate our approach on two scalable benchmarks from the literature. The experiments are carried out for the tasks of incremental synthesis of uniform strategies and optimization of a winning strategy, with very promising results.