Asymptotic existence of symEF1 allocations

Consider instances with a fixed number nn of agents and mm items, with probability taken over the paper's instance model. A symEF1 allocation is an allocation satisfying symmetric envy-freeness up to one item. Asymptotic existence conjecture. For any fixed number of agents nn, as the number of items mm tends to infinity, the probability that an instance has a symEF1 allocation tends to 11. The conjecture is motivated by simulations showing that the proportion of symEF1 instances increases rapidly with the number of items; it remains open.

Sources & referencesView supporting material

Primary source

Connor Johnston and Aleksandr M. Kazachkov, “Symmetrically Fair Allocations of Indivisible Goods”, arXiv:2406.13824 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.