MXS doesn't imply PROP1 for chores

Dependencies:

1. Fair division
2. PROP1
3. EFX
4. Minimum fair share

$\newcommand{\defeq}{:=}$ Consider a fair division instance with 3 agents having equal entitlements and identical additive valuations. Let there be 2 chores of disutility $4$ each (big chores) and 10 chores of disutility $1$ each (small chores). Let $A$ be an allocation where agent 1 has 8 small chores, agent 2 has a big chore and a small chore, and agent 3 has a big chore and a small chore. Then $A$ is MXS, but agent 1 is not PROP1-satisfied.

Proof

The proportional share is $-6$, so agent 1 is not PROP1-satisfied by $A$.

Let $B$ be an allocation where agent 1 has both big chores, and agents 2 and 3 have 5 small chores each. Then $d(B_i) = d(A_i)$ for every agent $i$, and each agent is EFX-satisifed in $B$. Hence, $B$ is every agent's MXS certificate for $A$. Hence, $A$ is an MXS allocation.

Dependency for: None

Info:

• Depth: 6
• Number of transitive dependencies: 9

Transitive dependencies:

1. /sets-and-relations/countable-set
2. σ-algebra
3. Set function
4. Fair division
5. Envy-freeness
6. PROP1
7. Minimum fair share
8. Submodular function
9. EFX