Two-Person Fair Division of Indivisible Items when Envy-Freeness Is Impossible
Steven Brams (),
D. Marc Kilgour and
Christian Klamler
MPRA Paper from University Library of Munich, Germany
Abstract:
Assume two players, A and B, must divide a set of indivisible items that each strictly ranks from best to worst. If the number of items is even, assume that the players desire that the allocations be balanced (each player gets half the items), item-wise envy-free (EF), and Pareto-optimal (PO). Meeting this ideal is frequently impossible. If so, we find a balanced maximal partial allocation of items to the players that is EF, though it may not be PO. Then we show how to augment it in a way that makes it a complete allocation that is EF for one player (say, A) and almost-EF for the other player (B) in the sense that it is EF for B except for one item – it would be EF for B if a specific item assigned to A were removed. Moreover, we show how low-ranked that exceptional item can be for B, thereby finding an almost-EF allocation that is as close as possible to EF – as well as complete, balanced, and PO. We provide algorithms to find such almost-EF allocations, adapted from algorithms that apply when complete balanced EF-PO allocations are possible.
Keywords: 2-person fair division; indivisible items; envy-freeness up to one item; Pareto-optimality (search for similar items in EconPapers)
JEL-codes: C61 C72 D63 (search for similar items in EconPapers)
Date: 2021-03
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
https://mpra.ub.uni-muenchen.de/106775/1/MPRA_paper_106775.pdf original version (application/pdf)
Related works:
Journal Article: Two-Person Fair Division of Indivisible Items when Envy-Freeness is Impossible (2022) 
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:pra:mprapa:106775
Access Statistics for this paper
More papers in MPRA Paper from University Library of Munich, Germany Ludwigstraße 33, D-80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Joachim Winter ().