  Despite the significant progress in multiagent teamwork, existing research
does not address the optimality of its prescriptions nor the complexity of the
teamwork problem. Without a characterization of the optimality-complexity
tradeoffs, it is impossible to determine whether the assumptions and
approximations made by a particular theory gain enough efficiency to justify
the losses in overall performance. To provide a tool for use by multiagent
researchers in evaluating this tradeoff, we present a unified framework, the
COMmunicative Multiagent Team Decision Problem (COM-MTDP). The COM-MTDP model
combines and extends existing multiagent theories, such as decentralized
partially observable Markov decision processes and economic team theory. In
addition to their generality of representation, COM-MTDPs also support the
analysis of both the optimality of team performance and the computational
complexity of the agents' decision problem. In analyzing complexity, we present
a breakdown of the computational complexity of constructing optimal teams under
various classes of problem domains, along the dimensions of observability and
communication cost. In analyzing optimality, we exploit the COM-MTDP's ability
to encode existing teamwork theories and models to encode two instantiations of
joint intentions theory taken from the literature. Furthermore, the COM-MTDP
model provides a basis for the development of novel team coordination
algorithms. We derive a domain-independent criterion for optimal communication
and provide a comparative analysis of the two joint intentions instantiations
with respect to this optimal policy. We have implemented a reusable,
domain-independent software package based on COM-MTDPs to analyze teamwork
coordination strategies, and we demonstrate its use by encoding and evaluating
the two joint intentions strategies within an example domain.
