APS and MMS don't imply PROPm

Dependencies:

1. Fair division
2. Maximin share allocations
3. AnyPrice share
4. PROPm
5. APS implies pessShare

$\newcommand{\defeq}{:=}$ Consider a fair division instance with 3 agents having equal entitlements and identical additive valuations. There are 6 goods of values 6, 3, 1, 1, 1, 1. Let $A = (\{3\}, \{1, 1, 1\}, \{6, 1\})$. Then $A$ is APS and MMS but not PROPm.

Proof

It's easy to see that the MMS is 3. Hence, the APS is at least 3. On setting the prices as 4, 3, 1, 1, 1, 1, we get that the APS is at most 3. Hence, $A$ is APS and MMS.

The proportional share is $13/3 > 4$, so $A$ is not PROPm.

Dependency for: None

Info:

• Depth: 7
• Number of transitive dependencies: 17

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. AnyPrice share
11. Proportional allocation
12. Maximin share of a set function
13. Maximin share allocations
14. APS implies pessShare
15. Submodular function
16. PROPx
17. PROPm