The Maximin Share Dominance Relation

Abstract

Given a finite set $X$ and an ordering $⪰$ over its subsets, the $l$-out-of-$d$ maximin-share of $X$ is the maximal (by $⪰$) subset of $X$ that can be constructed by partitioning $X$ into $d$ parts and picking the worst union of $l$ parts. A pair of integers $(l,d)$ dominates a pair $(l^{\prime },d^{\prime })$ if, for any set $X$ and ordering $⪰$, the $l$-out-of-$d$ maximin-share of $X$ is at least as good (by $⪰$) as the $l^{\prime }$-out-of-$d^{\prime }$ maximin-share of $X$. This note presents a necessary and sufficient condition for deciding whether a given pair of integers dominates another pair, and an algorithm for finding all non-dominated pairs. It compares the $l$-out-of-$d$ maximin-share to some other criteria for fair allocation of indivisible objects among people with different entitlements.

First draft

References in corpus (1)

• Competitive Equilibrium with Generic Budgets: Beyond Additive

Cited by in corpus (1)

• Ordinal Maximin Share Approximation for Goods