  Reallocating resources to get mutually beneficial outcomes is a fundamental
problem in various multi-agent settings. While finding an arbitrary Pareto
optimal allocation is generally easy, checking whether a particular allocation
is Pareto optimal can be much more difficult. This problem is equivalent to
checking that the allocated objects cannot be reallocated in such a way that at
least one agent prefers her new share to his old one, and no agent prefers her
old share to her new one. We consider the problem for two related types of
preference relations over sets of objects. In the first part of the paper we
focus on the setting in which agents express additive cardinal utilities over
objects. We present computational hardness results as well as polynomial-time
algorithms for testing Pareto optimality under different restrictions such as
two utility values or lexicographic utilities. In the second part of the paper
we assume that agents express only their (ordinal) preferences over single
objects, and that their preferences are additively separable. In this setting,
we present characterizations and polynomial-time algorithms for possible and
necessary Pareto optimality.
