Efficient reallocation under additive and responsive preferences (Q2272381)

This paper deals with problems involving multiple agents which consider a reallocation of resources that generate mutual benefits. The reassignment obtained is said to be Pareto optimal if a new reassignment cannot be found such that at least one of the agents prefers this new assignment to the previous one and none of the agents prefers their previous assignment to the new one. It should be said that finding an arbitrary optimal Pareto assignment is generally simple, but determining whether a given assignment is Pareto optimal can be more difficult. However, Pareto optimality is desirable, both from the point of view of welfare and individual rationality. It is known that the problem of maximizing egalitarian welfare is NP-hard [\textit{S. Demko} and \textit{T. P. Hill}, Math. Soc. Sci. 16, No. 2, 145--158 (1988; Zbl 0652.90027)]. It may be worth noting that Pareto optimality has been studied from the algorithmic point of view in previous works, as in the case of randomized allocation of indivisible goods [\textit{A. Bogomolnaia} and \textit{H. Moulin}, J. Econ. Theory 100, No. 2, 295--328 (2001; Zbl 1134.91357)], coalition formation under ordinal preferences [\textit{H. Aziz} et al., Games Econ. Behav. 82, 562--581 (2013; Zbl 1283.91011)], or probabilistic voting [\textit{H. Aziz} et al., J. Math. Econ. 60, 123--133 (2015; Zbl 1368.91083)], among others. For example, \textit{K. Cechlárová} et al. [Theory Comput. Syst. 59, No. 4, 700--721 (2016; Zbl 1356.91071)] proved that Pareto optimality of an assignment under lexicographic utilities can be tested in a polynomial time. In the first part of the paper, the problem is considered when the agents express additive cardinal profits on the resources. In this context, the first step was to relate the problem of computing an individually rational and Pareto optimal assignment to the more basic problem of testing the Pareto optimality of a given assignment. Computational hardness results are presented, as well as polynomial time algorithms for checking Pareto optimity under different restrictions, such as the lexicographic utility. In the second part of the paper, it is assumed that agents express only their ordinal preferences about resources and that the underlying preferences are separable. In this case, characterizations and polynomial time algorithms for Pareto optimality are presented.