PROP implies WMMS and pessShare

Dependencies:

1. Fair division
2. Proportional allocation
3. Maximin share allocations
4. Subadditive and superadditive set functions
5. Bound on k extreme values

$\newcommand{\defeq}{:=}$ $\newcommand{\WMMS}{\mathrm{WMMS}}$ $\newcommand{\pessShare}{\mathrm{pessShare}}$ Let $([n], [m], V, w)$ be a fair division instance of indivisible items (each agent $i$ has entitlement $w_i$). If $v_i$ is superadditive, then $\WMMS_i ≤ w_iv_i([m])$ and $\pessShare_i ≤ w_iv_i([m])$.

Proof

Let $P$ be agent $i$'s WMMS partition. Then \[ \frac{\WMMS_i}{w_i} = \min_{j=1}^n \frac{v_i(P_j)}{w_j} ≤ \sum_{j=1}^n w_j\left(\frac{v_i(P_j)}{w_j}\right) ≤ v_i([m]). \]

Let $P$ be agent $i$'s $\ell$-out-of-$d$-partition. Then her $\ell$-out-of-$d$-share is at most \[ \frac{\ell}{d}\sum_{j=1}^n v_i(P_j) ≤ \frac{\ell}{d}v_i([m]). \] \[ \pessShare_i \defeq \sup_{1 ≤ \ell ≤ d: \ell/d ≤ w_i} \ell\textrm{-out-of-}d\textrm{-share}_i ≤ \sup_{1 ≤ \ell ≤ d: \ell/d ≤ w_i} (\ell/d)v_i([m]) ≤ w_iv_i([m]). \]

Dependency for: None

Info:

• Depth: 5
• Number of transitive dependencies: 10

Transitive dependencies:

1. /sets-and-relations/countable-set
2. /analysis/sup-inf
3. σ-algebra
4. Set function
5. Fair division
6. Proportional allocation
7. Maximin share of a set function
8. Maximin share allocations
9. Subadditive and superadditive set functions
10. Bound on k extreme values