Asymptotic existence of symEF1 allocations
Asymptotic existence of symEF1 allocations
Consider instances with a fixed number of agents and 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 , as the number of items tends to infinity, the probability that an instance has a symEF1 allocation tends to . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.