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

Suppose that two players, P₁ and P₂, 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 (P_i) and almost-EF for the other player (P_j) in the sense that it is EF for P_j except for one item — it would be EF for P_j if a specific item assigned to P_i were removed. Moreover, we show how low-ranked (for P_j) 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.