Benade–et al. semi-random envy-free allocation question
Fix an integer . For each number of items divisible by , let be arbitrary base valuations. Independently choose uniformly random permutations of , and define the realized valuation of agent by . Is it true that, as through multiples of , with probability there exists a partition of with for every such that for all agents ?
References
- Envy-Free Allocations for Random Non-Additive Valuations — arXiv — Pasin Manurangsi
Source: arXiv
Progress summary
A new unrefereed preprint claims to settle the question for any fixed number of agents, but the claim has not been independently checked.
The question asks whether independently randomizing each agent’s item labels makes an envy-free allocation likely in the semi-random model. Benadè, Halpern, Psomas, and Verma established the main partial results in 2024, while the arbitrary-valuation case beyond two agents was explicitly left open.
Known results
- For two agents with arbitrary valuations, an envy-free allocation exists with probability at least when is even; this is nearly tight (Benadè et al., 2024).
- For any fixed number of agents with order-consistent valuations, SD-envy-free allocations exist with high probability when the number of items grows faster than the square of the number of agents (Benadè et al., 2024).
- For arbitrary valuations and more than two agents, the 2024 paper identified existence as open.
October 25, 2026 claimed extension
Pasin Manurangsi’s preprint claims envy-free allocations with high probability for every fixed number of agents, extending the arbitrary-valuation question beyond two agents and using generalized Johnson-graph expansion. This is a claimed resolution, not an independently verified result.
Current status (as of October 2026): The two-agent arbitrary-valuation case and broader order-consistent cases are established; the general fixed-agent claim is reported in a new preprint but remains unverified.
Solutions 0
No solutions have been posted yet.