Share vs envy for identical valuations (chores)

Dependencies:

1. Fair division
2. AnyPrice share
3. Maximin share allocations
4. EF1
5. EFX
6. Epistemic fairness
7. APS implies pessShare
8. PROP implies APS

$\newcommand{\MMS}{\mathrm{MMS}}$ $\newcommand{\APS}{\mathrm{APS}}$ Consider a fair division instance having $n ≥ 3$ agents having equal entitlements and identical additive valuations, and $m = n+1$ chores, each of disutility 1. Let $A$ be an allocation where agents 1 and 2 gets 2 chores each, agent $n$ gets 0 chores, and the remaining agents get 1 chore each. Then this allocation is APS, MMS, and epistemic EFX, but not EF1.

Proof

$-2 = \MMS_i ≤ \APS_i ≤ v([m])/n = - 1 - 1/n$. Hence, $APS_i = -2$, since the APS is the value of some bundle. Hence, $A$ is APS and MMS.

Agents $[n] \setminus \{2\}$ do not EFX-envy anyone in $A$. Agent 1's epistemic-EFX-certificate can be obtained by transferring a chore from agent 2 to agent $n$. Agent 2's epistemic-EFX-certificate can be obtained by transferring a chore from agent 1 to agent $n$. Hence, $A$ is epistemic EFX.

$A$ is not EF1 because agents 1 and 2 EF1-envy agent $n$.

Dependency for: None

Info:

• Depth: 6
• Number of transitive dependencies: 21

Transitive dependencies:

1. /sets-and-relations/countable-set
2. /analysis/sup-inf
3. σ-algebra
4. Set function
5. Fair division
6. Proportional allocation
7. Envy-freeness
8. Epistemic fairness
9. EF1
10. Maximin share of a set function
11. Maximin share allocations
12. Additive set function
13. Submodular function
14. EFX
15. Optimization: Dual and Lagrangian
16. Dual of a linear program
17. Linear programming: strong duality (incomplete)
18. AnyPrice share
19. PROP implies APS
20. Bound on k extreme values
21. APS implies pessShare