MEFS implies PROP for subadditive valuations

Dependencies:

1. Fair division
2. Subadditive and superadditive set functions
3. Proportional allocation
4. Envy-freeness
5. Minimum fair share

In fair division, suppose some agent $i$ has a subadditive valuation function. If allocation $A$ is MEFS-fair to $i$, then $A$ is also PROP-fair to $i$ (even for unequal entitlements).

Proof

Let $B$ be agent $i$'s MEFS-certificate for $A$. Then for all $j \in [n]$, we have $v_i(B_i)/w_i ≥ v_i(B_j)/w_j$. Sum these inequalities over all $j \in [n]$, weighting each by $w_j$, to get $v_i(B_i)/w_i ≥ \sum_{j=1}^n v_i(B_j)$. Since $v_i$ is subadditive, we get $v_i(M) \le \sum_{j=1}^n v_i(B_j)$. Hence, \[ \frac{v_i(A_i)}{w_i} ≥ \frac{v_i(B_i)}{w_i} \ge \sum_{j=1}^n v_i(B_j) \ge v_i(M). \]

Dependency for: None

Info:

• Depth: 5
• Number of transitive dependencies: 8

Transitive dependencies:

1. /sets-and-relations/countable-set
2. σ-algebra
3. Set function
4. Fair division
5. Proportional allocation
6. Envy-freeness
7. Minimum fair share
8. Subadditive and superadditive set functions