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