Kawase et al. prove 1/ℓ efficiency limit for multidimensional allocation

Allocating indivisible items across multiple criteria—like cost, fairness, or environmental impact—is inherently tricky because optimizing one objective can tank others. In their new arXiv paper, Kawase, Roy, and Sanpui formalize this with the Multidimensional Efficient Allocation (MDEA) model. Each agent has additive valuations in ℓ different dimensions, and the goal is to guarantee simultaneous efficiency under both utilitarian (USW) and egalitarian (ESW) social welfare. The results are stark: for exact USW efficiency, you can achieve at best a c/ℓ approximation for any fixed constant c, and this linear dependence on ℓ is unavoidable. For ESW, even deciding whether two dimensions can be simultaneously optimized is NP-hard with binary valuations.

For approximate efficiency, the team identifies a tight threshold of order 1/ℓ—meaning you can always guarantee a 1/ℓ fraction of optimal welfare in every dimension, but any asymptotically better dependence is impossible. The paper also defines three natural multidimensional Pareto optimality criteria, maps their relationships, and proves their computational complexities. These findings have immediate practical implications for systems that must balance multiple objectives, such as cloud resource allocation, logistics routing, or public policy budgeting, where indivisible items (servers, shipments, projects) must satisfy competing stakeholders.