  We study the envy-free house allocation problem when agents have uncertain
preferences over items and consider several well-studied preference uncertainty
models. The central problem that we focus on is computing an allocation that
has the highest probability of being envy-free. We show that each model leads
to a distinct set of algorithmic and complexity results, including detailed
results on (in-)approximability. En route, we consider two related problems of
checking whether there exists an allocation that is possibly or necessarily
envy-free. We give a complete picture of the computational complexity of these
two problems for all the uncertainty models we consider.
