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. /sets-and-relations/countable-set
2. /analysis/sup-inf
3. σ-algebra
4. Set function
5. Fair division
6. Proportional allocation
7. Maximin share of a set function
8. Maximin share allocations
9. Submodular function
10. PROPx
11. PROPm
12. Optimization: Dual and Lagrangian
13. Dual of a linear program
14. Linear programming: strong duality (incomplete)
15. AnyPrice share
16. Bound on k extreme values
17. APS implies pessShare