  A fundamental resource allocation setting is the random assignment problem in
which agents express preferences over objects that are then randomly allocated
to the agents. In 2001, Bogomolnaia and Moulin presented the probabilistic
serial (PS) mechanism that is an anonymous, neutral, Pareto optimal, and weak
strategyproof mechanism when the preferences are considered with respect to
stochastic dominance. The result holds when agents have strict preferences over
individual objects. It has been an open problem whether there exists a
mechanism that satisfies the same properties when agents may have indifference
among the objects. We show that for this more general domain, there exists no
extension of PS that is ex post efficient and weak strategyproof. The result is
surprising because it does not even require additional symmetry or fairness
conditions such as anonymity, neutrality, or equal treatment of equals. Our
result further demonstrates that the lack of weak SD-strategyproofness of the
extended PS mechanism of Katta and Sethuraman (2006) is not a design flaw of
extended PS but is due to an inherent incompatibility of efficiency and
strategyproofness of PS in the full preference domain.
