PROPm doesn't exist for mixed manna

Dependencies:

  1. Fair division
  2. PROPm
  3. EFX
  4. Maximin share allocations
  5. AnyPrice share
  6. Restricted agents, pairwise fairness, and groupwise fairness

There exists a fair division instance $\Ical = ([3], [6], V, w)$ with equal entitlements and identical additive valuations, for which no allocation is PROPm. Moreover, an allocation $A$ exists for $\Ical$ that is EFX, groupwise MMS, and groupwise APS.

Proof

Let the items have values $(-3, -3, -3, -3, -3, 3ε)$, where $0 < ε < 1/2$. The proportional share is $v([m])/3 = -5 + ε$.

Without loss of generality, assume agent 1 receives the most number of chores, and agent 3 receives the least number of chores. Then agent 1 has at least 2 chores, and agent 3 has at most 1 chore.

Case 1: agent 1 receives at least 3 chores.

Then even after removing one of her chores, and even if she receives the good, her value for her bundle is at most $-6 + 3ε < -5 + ε$. Hence, she is not PROPm-satisfied.

Case 2: agent 1 receives 2 chores.

Then agent 2 also receives 2 chores, and agent 3 receives 1 chore. Assume without loss of generality that agent 2 receives the good. Then this allocation is EFX and groupwise MMS. On setting the price of each chore to -3 and the price of the good to 3, we get that the allocation is groupwise APS.

Now if agent 1 adds the good to her bundle, her value becomes $-6 + 3ε < -5 + ε$. Hence, she is not PROPm-satisfied.

Dependency for: None

Info:

Transitive dependencies:

  1. /sets-and-relations/countable-set
  2. /analysis/sup-inf
  3. σ-algebra
  4. Set function
  5. Fair division
  6. Proportional allocation
  7. Restricted agents, pairwise fairness, and groupwise fairness
  8. Envy-freeness
  9. Maximin share of a set function
  10. Maximin share allocations
  11. Submodular function
  12. PROPx
  13. PROPm
  14. EFX
  15. Optimization: Dual and Lagrangian
  16. Dual of a linear program
  17. Linear programming: strong duality (incomplete)
  18. AnyPrice share