Interaction-driven Markov games for decentralized multiagent planning under uncertainty

In this paper we propose interaction-driven Markov games (IDMGs), a new model for multiagent decision making under uncertainty. IDMGs aim at describing multiagent decision problems in which interaction among agents is a local phe-nomenon. To this purpose, we explicitly distinguish between situations in which agents should interact and situations in which they can afford to act independently. The agents are coupled through the joint rewards and joint transitions in the states in which they interact. The model combines several fundamental properties from transition-independent Dec-MDPs and weakly coupled MDPs while allowing to ad-dress, in several aspects, more general problems. We in-troduce a fast approximate solution method for planning in IDMGs, exploiting their particular structure, and we illus-trate its successful application on several large multiagent tasks