Concise representations and complexity results for welfare-maximizing combinatorial assignment

Abstract We revisit the computational problem of partitioning indivisibles into bundles among alternatives to maximize value (e.g., welfare). These problems have broad applications, yet many important variants are computationally hard, including well-known instances in operations research, computational economics, and artificial intelligence. To address this complexity, we analyze novel restrictions and concise representations for this problem class and establish new complexity results. Building on these findings, we present improved complexity bounds using a hypergraph-based characterization and introduce a novel “bootstrapped” dynamic programming method that significantly outperforms existing algorithms for a broad class of problems. Other findings include: polynomial-time solvability for problems with non-negative synergies and two alternatives; the problem remaining -hard even when bounding bundle sizes to two, with other instances being polynomial-time solvable; and exploration of bounds for more general cases allowing externalities and balanced (mixed) welfare, offering efficient approximation and non-trivial exponential-time algorithms for many hard cases.