← All problems

Benade–et al. semi-random envy-free allocation question

Fix an integer n≥3n\ge 3. For each number of items mm divisible by nn, let v1,…,vn:2[m]→Rv_1,\ldots,v_n:2^{[m]}\to\mathbb{R} be arbitrary base valuations. Independently choose uniformly random permutations π1,…,πn\pi_1,\ldots,\pi_n of [m][m], and define the realized valuation of agent ii by Vi(S)=vi(πi(S))V_i(S)=v_i(\pi_i(S)). Is it true that, as m→∞m\to\infty through multiples of nn, with probability 1−o(1)1-o(1) there exists a partition (A1,…,An)(A_1,\ldots,A_n) of [m][m] with ∣Ai∣=m/n|A_i|=m/n for every ii such that Vi(Ai)≥Vi(Aj)V_i(A_i)\ge V_i(A_j) for all agents i,j∈[n]i,j\in[n]?

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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 1−1/(m/2+1)1-1/(m/2+1) when mm 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.

Sources

Solutions 0

No solutions have been posted yet.