Simplifying multi-agent games with imperfect information against nature using predetermined strategies : Reducing the complexity of strategy synthesis for games by treating things in our control as if they were out of our control

Abstract: We study games on graphs, where a coalition of agents work against an adversarial nature to achieve an objective. The agents have to collaborate while making their moves simultaneously, while receiving differing information about the state of the game and without a means of agent-to-agent communication. Before the game starts the coalition agrees on a strategy profile, where each agent is provided with a strategy which it acts in accordance to. The challenge of finding a winning strategy profile, wherein the coalition achieves their objective regardless of any influence from the adversarial nature, is called the strategy synthesis problem. For games with coalitions consisting of more than one agent, the general case of the synthesis problem is undecidable. We formalize an abstraction construction of a game where a subset of agents with predetermined strategies are abstracted into the adversarial nature of another game, for the purpose of reducing the size of the coalition of agents and in turn reduce the complexity of the strategy synthesis problem. We then prove that any winning strategy profile in the new game with fewer agents is also winning in the original game when combined with the predetermined strategies. The most interesting case is reducing a game with a coalition of two agents into a game with a single agent, since the strategy synthesis problem is decidable for games with a single agent. This allows us to test the predetermined strategy of the abstracted agent to see if it is possible to create a winning strategy profile using it. If it is not possible then we can try a different strategy. This enables an iterative approach for solving the strategy synthesis problem instead of a deductive one.