Concise Representations and Complexity of Combinatorial Assignment Problems

We consider the computational problem of partitioning items into bundles among alternatives to maximize social welfare. Unfortunately, many important classes of this problem are computationally hard, including well-known instances in the multi-agent systems literature. In this paper we analyze novel concise representations and restrictions that admit polynomial-time algorithms for many such combinatorial assignment problems, and prove several complexity results for them. We provide efficient approximation algorithms and non-trivial exponential-time algorithms for the hard cases.