PROP-unsat implies someone is superPROP

Dependencies:

1. Fair division
2. Subadditive and superadditive set functions

Let $([n], M, V, w)$ be a fair division instance where each agent $i$ has entitlement $w_i$.

Let $A$ be an allocation where for some agent $i$, $v_i$ is subadditive and $v_i(A_i) < w_iv_i(M)$. Then for some agent $j \in [n] \setminus \{i\}$, we have $v_i(A_j) > w_jv_i(M)$.

Proof

Suppose $v_i(A_j) ≤ w_jv_i(M)$ for all $j \in [n] \setminus \{i\}$. Then \[ v_i(M) ≤ \sum_{j=1}^n v_i(A_j) < \sum_{j=1}^n w_jv_i(M) = v_i(M). \] This is a contradiction. Hence, $v_i(A_j) > w_jv_i(M)$ for some $j \in [n] \setminus \{i\}$.

Dependency for:

1. EFX implies PROPm
2. An MXS allocation is also PROP1
3. EF1 implies PROP1
4. Additive chores and binary marginals
5. Additive goods and binary marginals

Info:

• Depth: 4
• Number of transitive dependencies: 5

Transitive dependencies:

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