Guarantees in Fair Division: beyond Divide & Choose and Moving Knifes

Printer-friendly version
Anna Bogomolnaia, Hervé Moulin, Richard Stong
Divide and Choose among two agents, and the Diminishing Share (DS) and Moving Knife (MK) algorithms among many, elicit parsimonious information to guarantee to each a Fair Share, worth at least 1/n-th of the whole manna. Our n-person Divide and Choose (D&C) rule, unlike DS and MK, works if the manna has subjectively good and bad parts. If utilities are additive over indivisible items, it implements the canonical "Fair Share up to one item" approximation. The D&C rule also offers one interpretation of the Fair Share when utilities are neither additive nor monotonic . Under a mild continuity assumption, it guarantees to each agent her minMax utility: that of her best share in the worst possible partition. This is lower than her Maxmin utility: that of her worst share in the best possible partition. When the manna is unanimously good, or unanimously bad, better guarantees than minMax are feasible. Our Bid & Choose rules fix an additive benchmark measure of shares, and ask agents to bid the smallest size of a share they find acceptable. The resulting Guarantee is between the minMax and Maxmin utilities
Developed by Paolo Gittoi