We study assignment problems in a model where agents have strict preferences over objects, allowing preference lists to be incomplete. We investigate the questions whether an agent can obtain or necessarily obtains a given object under serial dictatorship. We prove that both problems are computationally hard even if agents have preference lists of length at most 3; by contrast, we give linear-time algorithms for the case where preference lists are of length at most 2. We also study a capacitated version of these problems where objects come in several copies.
展开▼
