We study the problem of fairly and truthfully allocating m indivisible items to n agents with additive preferences. Specifically, we consider truthful mechanisms outputting allocations that satisfy $\mathrm{EF}_{-v}^{+u}$, where, in an $\mathrm{EF}_{-v}^{+u}$ allocation, for any pair of agents i and j, agent i will not envy agent j if u items were added to i ‘s bundle and v items were removed from j ‘s bundle. Previous work easily indicates that, when restricted to deterministic mechanisms, truthfulness will lead to a poor guarantee of fairness: even with two agents, for any u and $v, \mathrm{EF}_{-v}^{+u}$ cannot be guaranteed by truthful mechanisms when the number of items is large enough. In this work, we focus on randomized mechanisms, where we consider ex-ante truthfulness and ex-post fairness. For two agents, we present a truthful mechanism that achieves $\mathrm{EF}_{-1}^{+0}$ (i.e., the well-studied fairness notion EF1). For three agents, we present a truthful mechanism that achieves $\mathrm{EF}_{-1}^{+1}$. For n agents in general, we show that there exists a truthful mechanism that achieves $\mathrm{EF}_{-O(\sqrt{n})}^{+0}$. We further consider fair and truthful mechanisms that also satisfy the standard efficiency guarantee: Pareto-optimality. We provide a mechanism that simultaneously achieves truthfulness, EF1, and Pareto-optimality for bi-valued utilities (where agents’ valuation on each item is either p or q for some $p\gt q \geq 0$). For tri-valued utilities (where agents’ valuations on each item belong to $\{p, q, r\}$ for some $p\gt q\gt r \geq 0$) and any $u, v$, we show that truthfulness is incompatible with $\mathbf{E F}_{-v}^{+u}$ and Pareto-optimality even for two agents.

The problem of fair allocation of indivisible goods studies allocating a set of m goods among n agents in a fair manner. While fairness is a fundamental requirement in many real-world applications, it often conflicts with (economic) efficiency. This raises a natural and important question: How can we identify the most welfare-efficient allocation among all fair allocations? This paper gives an answer from the perspective of computational complexity. Specifically, we study the problem of maximizing utilitarian social welfare (the sum of agents' utilities) under two widely studied fairness criteria: envy-freeness up to any item (EFX) and envy-freeness up to one item (EF1). We examine both normalized and unnormalized valuations, where normalized valuations require that each agent's total utility for all items is identical.

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.

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 [1] and subsequently raised in reference [2] , [3] , [4] , [5] , [6] , [7] , etc., 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: • there are only two agents; • each agent's valuation is a piecewise-constant function; • 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. We also present a truthful and envy-free mechanism when each agent's valuation is piecewise-constant and monotone. However, if we require Pareto-optimality, we show that truthful is incompatible with approximate proportionality for any positive approximation ratio even for piecewise-constant and monotone value density functions. To circumvent the main 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, 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.