  Multiagent planning and coordination problems are common and known to be
computationally hard. We show that a wide range of two-agent problems can be
formulated as bilinear programs. We present a successive approximation
algorithm that significantly outperforms the coverage set algorithm, which is
the state-of-the-art method for this class of multiagent problems. Because the
algorithm is formulated for bilinear programs, it is more general and simpler
to implement. The new algorithm can be terminated at any time and-unlike the
coverage set algorithm-it facilitates the derivation of a useful online
performance bound. It is also much more efficient, on average reducing the
computation time of the optimal solution by about four orders of magnitude.
Finally, we introduce an automatic dimensionality reduction method that
improves the effectiveness of the algorithm, extending its applicability to new
domains and providing a new way to analyze a subclass of bilinear programs.
