Additive chores and binary marginals

Dependencies:

1. Fair division
2. PROP1
3. Minimum fair share
4. EF1
5. PROPx
6. Maximin share allocations
7. EFX
8. Epistemic fairness
9. AnyPrice share
10. Additive set function
11. Bound on k extreme values
12. PROP-unsat implies someone is superPROP
13. Restricted agents, pairwise fairness, and groupwise fairness
14. EF1 implies PROP1

$\newcommand{\defeq}{:=}$ $\newcommand{\ceil}[1]{\lceil #1 \rceil}$ $\newcommand{\MMS}{\mathrm{MMS}}$ $\newcommand{\APS}{\mathrm{APS}}$ Let $([n], M, V, w)$ be a fair division instance of indivisible chores, where each agent $i$ has entitlement $w_i$. For some agent $i$, let $v_i$ be additive and $v_i(c) \in \{0, 1\}$ for all $c \in M$. Let $M_- \defeq \{c \in M: v_i(c) = 1\}$ and $m \defeq |M_-|$. Then for any allocation $A$,

1. $i$ is PROP1-satisfied by $A$ iff $d_i(A_i) ≤ \ceil{w_im}$.
2. $i$ is PROPx-satisfied by $A$ iff $d_i(A_i) ≤ \ceil{w_im}$.
3. $\APS_i = -\ceil{w_im}$.
4. If $i$ is EF1-satisfied by $A$, then $i$ is also groupwise-APS-satisfied by $A$.

Furthermore, when entitlements are equal, we have

1. If $i$ is M1S-satisfied by $A$, then $d_i(A_i) ≤ \ceil{m/n}$.
2. $\MMS_i = -\ceil{m/n}$.
3. If $d_i(A_i) ≤ \ceil{m/n}$, then $i$ is EEFX-satisfied by $A$.

Proof

The statements about PROP1, PROPx, and MMS are trivial.

Set the price of each chore to its value. Then $i$'s budget is $-w_im$, so the maximum value $i$ can buy is $-\ceil{w_im}$. Hence, $\APS_i ≤ -\ceil{w_im}$.

For any non-positive price vector $p$, let $S$ be the cheapest $\ceil{w_im}$ chores. Then $p(S) ≤ \frac{\ceil{w_im}}{m}p(M) ≤ w_ip(M)$. Hence, $S$ is affordable, and has disutility at most $\ceil{w_im}$. Hence, $\APS_i ≥ -\ceil{w_im}$. Therefore, $\APS_i = \ceil{w_im}$.

Points 1 and 3 show that if an allocation is PROP1-satisfied, then it is also APS-satisfied. Suppose $i$ is EF1-satisfied by $A$. Pick a subset $S$ of agents containing $i$. Let $B$ be the allocation restricted to $S$. Then $i$ is also EF1-satisfied by $B$, and so, $i$ is PROP1-satisfied by $B$, and hence, $i$ is APS-satisfied by $B$. Since this holds for every subset $S$, we get that $i$ is groupwise-APS-satisfied by $A$.

Suppose $i$ is M1S-satisfied by $A$. Let $Y$ be $i$'s M1S-certificate for $A$. Suppose $d_i(Y_i) ≥ \ceil{m/n}+1$. Then $d_i(Y_i) > m/n = d_i(M)/n$, so there exists another agent $j$ such that $d_i(Y_j) < v_i(M)/n = m/n$. Hence, $d_i(Y_j) ≤ \ceil{m/n}-1$. Then $i$ EF1-envies $j$, which contradicts the fact that $Y$ is $i$'s M1S-certificate for $A$. Hence, $d_i(A_i) ≤ d_i(Y_i) ≤ \ceil{m/n}$.

Suppose $d_i(A_i) ≤ \ceil{m/n}$. Create another allocation $B$ where $B_i = A_i$ and give at least $\ceil{m/n}-1$ chores of disutility 1 to the other agents. This is possible because $\ceil{m/n} + (n-1)(\ceil{m/n}-1) = n(\ceil{m/n}-1) + 1 < m + 1$. Then $i$ is EFX-satisfied by $B$, so $i$ is EEFX-satisfied by $A$.

Dependency for: None

Info:

• Depth: 7
• Number of transitive dependencies: 26

Transitive dependencies:

1. /analysis/sup-inf
2. /sets-and-relations/countable-set
3. Bound on k extreme values
4. Optimization: Dual and Lagrangian
5. Dual of a linear program
6. Linear programming: strong duality (incomplete)
7. σ-algebra
8. Set function
9. Fair division
10. PROP1
11. Minimum fair share
12. Epistemic fairness
13. AnyPrice share
14. Restricted agents, pairwise fairness, and groupwise fairness
15. Proportional allocation
16. Envy-freeness
17. EF1
18. Additive set function
19. Maximin share of a set function
20. Maximin share allocations
21. Subadditive and superadditive set functions
22. PROP-unsat implies someone is superPROP
23. EF1 implies PROP1
24. Submodular function
25. EFX
26. PROPx