Two-Person Fair Division of Indivisible Items when Envy-Freeness is Impossible

Steven Brams (), D. Marc Kilgour () and Christian Klamler ()
Additional contact information
D. Marc Kilgour: Wilfrid Laurier University
Christian Klamler: University of Graz

SN Operations Research Forum, 2022, vol. 3, issue 2, 1-23

Abstract: Abstract Suppose that two players, P1 and P2, must divide a set of indivisible items that each strictly ranks from best to worst. Assuming that the number of items is even, suppose also 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 so that it becomes a complete allocation (all items are allocated) that is EF for one player (Pi) and almost-EF for the other player (Pj) in the sense that it is EF for Pj except for one item — it would be EF for Pj if a specific item assigned to Pi were removed. Moreover, we show how low-ranked (for Pj) that exceptional item may be, 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-optimal; 91B14; 91B32 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-021-00115-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
Working Paper: Two-Person Fair Division of Indivisible Items when Envy-Freeness Is Impossible (2021)
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:spr:snopef:v:3:y:2022:i:2:d:10.1007_s43069-021-00115-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-021-00115-7

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().