Fair division with prioritized agents

We study the fair division of indivisible items. Since an envy-free allocation may not exist, a standard relaxation is envy-freeness up to one item (EF1), where any envy can be eliminated by removing a single item from the envied agent's bundle. In many applications, however, it is desirable to designate a subset of prioritized agents for whom strict envy-freeness toward the remaining agents must be guaranteed, while the overall allocation remains EF1. Such agents may correspond to those who were envious in a previous EF1 allocation or to members of underrepresented groups. Motivated by this, we propose a new fairness notion named envy-freeness with prioritized agents EFprior, and study the existence and the algorithmic aspects of computing an EFprior allocation. For additive valuations, the simple round-robin algorithm suffices to compute an EFprior allocation. In this paper, we mainly focus on general valuations. In particular, we present a polynomial-time algorithm that computes an EFprior allocation with most of the items allocated. When all the items need to be allocated, we also present polynomial-time algorithms for several well-motivated special cases. We finally extend the setting to a general prioritized ordering case, where we are given a full ordering of agents and each agent with a higher priority cannot envy an agent with a lower priority. We propose a generalized fairness notion named envy-freeness under rank r EFr and present a polynomial-time algorithm with most of the items allocated.