Efficient reallocation under additive and responsive preferences

DOI10.1016/J.TCS.2019.05.011MaRDI QIDQ2272381zbMATH OpenOpenAlexWikidataFDO

Authors Haris Aziz, Péter Biró, Jérôme Lang, Julien Lesca, Jérôme Monnot

Publication date 10 September 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.01091

fair division Pareto optimality resource allocation

Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: 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.

Review text

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.

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Efficient reallocation under additive and responsive preferences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272381)