  We study the problem of fairly allocating $m$ indivisible items among $n$
agents. Envy-free allocations, in which each agent prefers her bundle to the
bundle of every other agent, need not exist in the worst case. However, when
agents have additive preferences and the value $v_{i,j}$ of agent $i$ for item
$j$ is drawn independently from a distribution $D_i$, envy-free allocations
exist with high probability when $m \in \Omega( n \log n / \log \log n )$.
  In this paper, we study the existence of envy-free allocations under
stochastic valuations far beyond the additive setting. We introduce a new
stochastic model in which each agent's valuation is sampled by first fixing a
worst-case function, and then drawing a uniformly random renaming of the items,
independently for each agent. This strictly generalizes known settings; for
example, $v_{i,j} \sim D_i$ may be seen as picking a random (instead of a
worst-case) additive function before renaming. We prove that random renaming is
sufficient to ensure that envy-free allocations exist with high probability in
very general settings. When valuations are non-negative and
``order-consistent,'' a valuation class that generalizes additive,
budget-additive, unit-demand, and single-minded agents, SD-envy-free
allocations (a stronger notion of fairness than envy-freeness) exist for $m \in
\omega(n^2)$ when $n$ divides $m$, and SD-EFX allocations exist for all $m \in
\omega(n^2)$. The dependence on $n$ is tight, that is, for $m \in O(n^2)$
envy-free allocations don't exist with constant probability. For the case of
arbitrary valuations (allowing non-monotone, negative, or mixed-manna
valuations) and $n=2$ agents, we prove envy-free allocations exist with
probability $1 - \Theta(1/m)$ (and this is tight).
