Allocation of Indivisible Items with given Preference Graphs.

We study the allocation of indivisible items to agents, when each agent’s preferences are expressed by means of a directed acyclic graph.
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.
We seek an allocation of the items to the agents in a way that minimizes the total dissatisfaction over all agents.
We study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to natural underlying graph structures.
Joint work with Nina Chiarelli, Clément Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Ulrich Pferschy, Nevena Pivač.

Everyone is welcome and encouraged to attend!