Minimum fair share

Dependencies:

1. Fair division

$\newcommand{\defeq}{:=}$ $\newcommand{\Acal}{\mathcal{A}}$ $\newcommand{\Ical}{\mathcal{I}}$ $\newcommand{\minFS}{\operatorname{minFS}}$ In fair division, let $F$ be a fairness notion. An allocation $A$ is said to be min-$F$-share-fair to an agent $i$ if there exists another allocation $B$ such that $v_i(A_i) ≥ v_i(B_i)$ and $B$ is $F$-fair for agent $i$.

Here $B$ is called agent $i$'s min-$F$-share-certificate for $A$. Note that in a min-$F$-share-fair allocation, different agents can have different certificates.

Define agent $i$'s minimum $F$ share as the minimum value she gets across all allocations that are $F$-fair to her. Formally, for a fair division instance $\Ical \defeq ([n], [m], (v_i)_{i=1}^n, w)$, \[ \minFS(\Ical, F, i) \defeq \min_{A \in \Acal(\Ical, F, i)} v_i(A_i), \] where $\Acal(\Ical, F, i)$ is the set of all allocations over $\Ical$ that are $F$-fair to agent $i$. Then an allocation $A$ is min-$F$-share-fair to agent $i$ if $v_i(A_i) ≥ \minFS(\Ical, F, i)$.

Common abbreviations for min-$F$-share fairness notions:

• min-EFX-share = MXS
• min-EF1-share = M1S
• min-EF-share = MEFS

Dependency for:

1. MMS implies MXS
2. MXS implies EF1 for n=2
3. MEFS implies PROP for subadditive valuations
4. An MXS allocation is also PROP1
5. Additive chores and binary marginals
6. Additive goods and binary marginals
7. PROP but not MEFS
8. MEFS but not EEF
9. PROP1+M1S allocation doesn't exist
10. MEFS but not EEF for chores
11. PROP1 doesn't imply M1S for unit marginals and n=2
12. M1S doesn't imply PROP1
13. PROP doesn't imply M1S for unit-demand valuations
14. MXS doesn't imply PROP1 for chores
15. MEFS+PROP doesn't imply EEF1 for chores
16. EF1 doesn't imply PROPx or MXS
17. PROPx doesn't imply M1S
18. MXS doesn't imply PROPx or EFX

Info:

• Depth: 4
• Number of transitive dependencies: 4

Transitive dependencies:

1. /sets-and-relations/countable-set
2. σ-algebra
3. Set function
4. Fair division