  This paper studies the allocation of indivisible items to agents, when each
agent's preferences are expressed by means of a directed acyclic graph. The
vertices of each preference graph represent the subset of items approved of by
the respective agent. An arc $(a,b)$ in such a graph means that the respective
agent prefers item $a$ over item $b$. We introduce a new measure of
dissatisfaction of an agent by counting the number of non-assigned items which
are approved of by the agent and for which no more preferred item is allocated
to the agent. Considering two problem variants, we seek an allocation of the
items to the agents in a way that minimizes (i) the total dissatisfaction over
all agents or (ii) the maximum dissatisfaction among the agents. For both
optimization problems we study the status of computational complexity and
obtain NP-hardness results as well as polynomial algorithms with respect to
natural underlying graph structures, such as stars, trees, paths, and
matchings. We also analyze the parameterized complexity of the two problems
with respect to various parameters related to the number of agents, the
dissatisfaction threshold, the vertex degrees of the preference graphs, and the
treewidth.
