Reproduce “Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Nicholas Teh
A study on fair division of indivisible goods establishes that eight goods is the tight threshold for two-agent envy-freeness up to one good (EF1) and Pareto optimality (PO) incompatibility under strictly increasing valuations. The work also strengthens the NP-hardness result for finding EF1 and PO allocations for three agents by showing it persists with only a fixed, small number of zero marginal values.
Key insights
- Strictly increasing valuations, where every good always adds value, are not sufficient to guarantee the existence of an allocation that is both EF1 and PO.
- The exact boundary for two-agent EF1 and PO compatibility under strictly increasing valuations is seven goods, with incompatibility robustly emerging at eight goods.
- The computational intractability of finding EF1 and PO allocations for three agents is robust, persisting even when the valuations are mostly positive and only a very limited, fixed number of agent-good pairs have zero marginal values.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.