Efficient reallocation under additive and responsive preferences
From MaRDI portal
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.
Recommendations
Cites work
- A new solution to the random assignment problem.
- Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
- Algorithms and Computation
- Equitable distribution of indivisible objects
- Fair division of indivisible items
- Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
- scientific article; zbMATH DE number 3769296 (Why is no real title available?)
- Manipulating picking sequences
- Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
- On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
- On the Shapley-Scarf economy: The case of multiple types of indivisible goods
- Pareto optimal matchings in many-to-many markets with ties
- Pareto optimal matchings in many-to-many markets with ties
- Pareto optimality in coalition formation
- Two-sided matching with indifferences
- Universal Pareto dominance and welfare for plausible utility functions
Cited in
(22)- Strategy-proofness of scoring allocation correspondences for indivisible goods
- Complexity of finding Pareto-efficient allocations of highest welfare
- Operations research in Hungary: VOCAL 2018
- Serial rules in a multi-unit Shapley-Scarf market
- Multiagent resource allocation in k-additive domains: preference representation and complexity
- Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity
- Refugee allocation in the setting of hedonic games
- A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
- Computing fair and efficient allocations with few utility values
- scientific article; zbMATH DE number 165312 (Why is no real title available?)
- Ordinal Maximin Share Approximation for Goods
- Multi-agent task allocation under unrestricted environments
- Computing fair and efficient allocations with few utility values
- On best-of-both-worlds fair-share allocations
- Strong core and Pareto-optimality in the multiple partners matching problem under lexicographic preference domains
- Fair division with two-sided preferences
- Settling the score: portioning with cardinal preferences
- Tractable graph structures in EFX orientation
- Partitioned matching games for international kidney exchange
- Efficiency in multiple-type housing markets
- Axiomatic characterizations of draft rules
- Reforming an unfair allocation by exchanging goods
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)
