  We consider the problem of random assignment of indivisible goods, in which
each agent has an ordinal preference and a constraint. Our goal is to
characterize the conditions under which there exists a random assignment that
simultaneously achieves efficiency and envy-freeness. The probabilistic serial
mechanism ensures the existence of such an assignment for the unconstrained
setting. In this paper, we consider a more general setting in which each agent
can consume a set of items only if the set satisfies her feasibility
constraint. Such constraints must be taken into account in student course
placements, employee shift assignments, and so on. We demonstrate that an
efficient and envy-free assignment may not exist even for the simple case of
partition matroid constraints, where the items are categorized and each agent
demands one item from each category. We then identify special cases in which an
efficient and envy-free assignment always exists. For these cases, the
probabilistic serial cannot be naturally extended; therefore, we provide
mechanisms to find the desired assignment using various approaches.
