We consider the fair allocation problem of indivisible items. Most previous work focuses on fairness and/or efficiency among agents given agents' preferences. However, besides the agents, the allocator as the resource owner may also be involved in many real-world scenarios, e.g., heritage division. The allocator has the inclination to obtain a fair or efficient allocation based on her own preference over the items and to whom each item is allocated. In this paper, we propose a new model and focus on the following two problems: 1) Is it possible to find an allocation that is fair for both the agents and the allocator? 2) What is the complexity of maximizing the allocator's social welfare while satisfying the agents' fairness? We consider the two fundamental fairness criteria: envy-freeness and proportionality. For the first problem, we study the existence of an allocation that is envy-free up to c goods (EF-c) or proportional up to c goods (PROP-c) from both the agents' and the allocator's perspectives, in which such an allocation is called doubly EF-c or doubly PROP-c respectively. When the allocator's utility depends exclusively on the items (but not to whom an item is allocated), we prove that a doubly EF-1 allocation always exists. For the general setting where the allocator has a preference over the items and to whom each item is allocated, we prove that a doubly EF-1 allocation always exists for two agents, a doubly PROP-2 allocation always exists for binary valuations, and a doubly PROP-O(log n) allocation always exists in general. For the second problem, we provide various (in)approximability results in which the gaps between approximation and inapproximation ratios are asymptotically closed under most settings. Most results are based on novel technical tools including the chromatic numbers of the Kneser graphs and linear programming-based analysis.

We study the fair division problem on divisible heterogeneous resources (the cake cutting problem) with strategic agents, where each agent can manipulate his/her private valuation to receive a better allocation. A (direct-revelation) mechanism takes agents' reported valuations as input and outputs an allocation that satisfies a given fairness requirement. A natural and fundamental open problem, first raised by Chen, Lai, Parkes, and Procaccia and subsequently raised in many other references, is whether there exists a deterministic, truthful, and envy-free (or even proportional) cake cutting mechanism.

In this paper, we resolve this open problem by proving that there does not exist a deterministic, truthful and proportional cake cutting mechanism, even in the special case where all of the following hold: 1. there are only two agents; 2. each agent's valuation is a piecewise-constant function; 3. each agent is hungry: each agent has a strictly positive value on any part of the cake. The impossibility result extends to the case where the mechanism is allowed to leave some part of the cake unallocated.

To circumvent this impossibility result, we aim to design mechanisms that possess a certain degree of truthfulness. Motivated by the kind of truthfulness possessed by the classical I-cut-you-choose protocol, we propose a weaker notion of truthfulness, \emph{the proportional risk-averse truthfulness}. We show that the well-known moving-knife (Dubins-Spanier) procedure and Even-Paz algorithm do not have this truthful property. We propose a mechanism that is proportionally risk-averse truthful and envy-free, and a mechanism that is proportionally risk-averse truthful that always outputs allocations with connected pieces.

We consider the fair division problem of indivisible items. It is well-known that an envy-free allocation may not exist, and a relaxed version of envy-freeness, envy-freeness up to one item (EF1), has been widely considered. In an EF1 allocation, an agent may envy others' allocated shares, but only up to one item. In many applications, we may wish to specify a subset of prioritized agents where strict envy-freeness needs to be guaranteed from these agents to the remaining agents, while ensuring the whole allocation is still EF1. Prioritized agents may be those agents who are envious in a previous EF1 allocation, those agents who belong to underrepresented groups, etc. Motivated by this, we propose a new fairness notion named envy-freeness with prioritized agents (EFPrior), and study the existence and the algorithmic aspects for the problem of computing an EFPrior allocation. With additive valuations, the simple round-robin algorithm is able to compute an EFPrior allocation. In this paper, we mainly focus on general valuations. In particular, we present a polynomial-time algorithm that outputs an EFPrior allocation with most of the items allocated. When all the items need to be allocated, we also present polynomial-time algorithms for some well-motivated special cases.