# Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

arXiv: https://arxiv.org/abs/2607.23367 · HTML: https://mlsanity.com/paper/2607.23367/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 18 references that are in the map.
- First posted on arXiv 25 Jul 2026.

## Builds on (most cited first, 12 of 12)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Finding Fair and Efficient Allocations](https://mlsanity.com/paper/1707.04731/) (2017)
- [Finding Fair and Efficient Allocations When Valuations Don't Add Up](https://mlsanity.com/paper/2003.07060/) (2020)
- [On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources](https://mlsanity.com/paper/2012.06788/) (2020)
- [Compatibility of Fairness and Nash Welfare under Subadditive Valuations](https://mlsanity.com/paper/2407.12461/) (2024)
- [Existence of Fair and Efficient Allocation of Indivisible Chores](https://mlsanity.com/paper/2507.09544/) (2025)
- [Fair Distribution of Delivery Orders](https://mlsanity.com/paper/2305.00040/) (2023)
- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)
- [Fair Division with Binary Valuations: Characterizations](https://mlsanity.com/paper/2607.10064/) (2026)
- [When One Good Is Not Enough: EF1 and Pareto Optimality Are Not Compatible for Submodular Valuations](https://mlsanity.com/paper/2607.17811/) (2026)
- [Nonexistence of Simultaneously EF1 and Pareto Optimal Allocations for Submodular Valuations](https://mlsanity.com/paper/2607.18220/) (2026)

## Abstract (arXiv)

We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent.