APS = MMS for n=2

Dependencies:

1. Fair division
2. AnyPrice share
3. Maximin share allocations
4. MMS is largest bundle value at most PROP when n=2
5. APS implies pessShare
6. PROP implies APS

$\newcommand{\defeq}{:=}$ $\newcommand{\argmax}{\mathop{\mathrm{argmax}}}$ $\newcommand{\MMS}{\mathrm{MMS}}$ $\newcommand{\WMMS}{\mathrm{WMMS}}$ $\newcommand{\APS}{\mathrm{APS}}$ Let $([2], [m], V, w)$ be a fair division instance with indivisible items and each agent $i$ has entitlement $w_i$. If $v_k$ is additive for some agent $k$, then $\APS_k ≤ \WMMS_k$. If entitlements are equal, then $\APS_k = \MMS_k$.

Proof

Let \[ \beta_k \defeq \max(\{v_k(S)/w_i: S \subseteq [m], i \in [2], v_k(S) ≤ w_iv_k([m])\}). \] Then $\WMMS_k = w_k\beta_k$. Let $p^*$ be the optimal APS price vector. Let \[ S^* \defeq \argmax_{S \subseteq [m]: p^*(S) ≤ w_kp^*([m])} v_k(S). \] Then $\APS_k = v_k(S^*)$. Since $\APS_k ≤ w_kv_k([m])$, we get $\APS_k/w_k ≤ \beta_k = \WMMS_k/w_k$. Hence, $\APS_k ≤ \WMMS_k$.

When entitlements are equal, $\APS_k ≥ \mathrm{pessShare}_k = \MMS_k$.

Dependency for: None

Info:

• Depth: 6
• Number of transitive dependencies: 17

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. Additive set function
10. MMS is largest bundle value at most PROP when n=2
11. Optimization: Dual and Lagrangian
12. Dual of a linear program
13. Linear programming: strong duality (incomplete)
14. AnyPrice share
15. PROP implies APS
16. Bound on k extreme values
17. APS implies pessShare