Abstract Multiagent planning has seen much progress with the development of formal models such as DecPOMDPs. However, the complexity of these models—NEXP-Complete even for two agents— has limited scalability. We identify certain mild conditions that are suf?cient to make multiagent planning amenable to a scalable approximation w.r.t. the number of agents. This is achieved by constructing a graphical model in which likelihood maximization is equivalent to plan optimization. Using the Expectation-Maximization framework for likelihood maximization, we show that the necessary inference can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We derive a global update rule that combines these local inferences to monotonically increase the overall solution quality. Experiments on a large multiagent planning benchmark con?rm the bene?ts of the new approach in terms of runtime and scalability.