PROP implies APS

Dependencies:

1. Fair division
2. Proportional allocation
3. AnyPrice share
4. Additive set function

$\newcommand{\defeq}{:=}$ $\newcommand{\APS}{\mathrm{APS}}$ Let $([n], [m], V, w)$ be a fair division instance of indivisible items (each agent $i$ has entitlement $w_i$). Then $\APS_i ≤ w_iv_i([m])$ for agent $i$ if $v_i$ is additive.

Proof

Set the price $p(g)$ of each item $g$ to $v_i(g)$. Then \[ \APS_i ≤ \max_{S \subseteq [m]: p(S) ≤ w_ip([m])} v_i(S) = \max_{S \subseteq [m]: v_i(S) ≤ w_iv_i([m])} v_i(S) ≤ w_iv_i([m]). \]

(Proof adapted from Proposition 4 of https://doi.org/10.1287/moor.2021.0199.)

Dependency for:

1. APS = MMS for n=2
2. Share vs envy for identical valuations (chores)
3. Share vs envy for identical valuations (goods)

Info:

• Depth: 5
• Number of transitive dependencies: 10

Transitive dependencies:

1. /sets-and-relations/countable-set
2. σ-algebra
3. Set function
4. Fair division
5. Proportional allocation
6. Additive set function
7. Optimization: Dual and Lagrangian
8. Dual of a linear program
9. Linear programming: strong duality (incomplete)
10. AnyPrice share