Computing optimal allocations is a ubiquitous and notoriously hard computational problem that is significant in settings such as combinatorial auctions. This paper considers an expressive representation of such settings in which agents care about not only what they receive but also what is allocated to other agents. The authors undertake a detailed computational analysis of computing optimal allocations. The results also include some natural restrictions on the preferences of the agents for which an optimal allocation can be computed in polynomial time. The paper manages to present a clearer understanding of the computational complexity of computing optimal combinatorial allocations.

The intended audience includes theoreticians and practitioners of combinatorial auctions in particular, and resource allocation and multiagent systems in general.