  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 EF$^{+u}_{-v}$, where,
in an EF$^{+u}_{-v}$ 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$,
EF$^{+u}_{-v}$ 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 EF$^{+0}_{-1}$ (i.e., the
well-studied fairness notion EF$1$). For three agents, we present a truthful
mechanism that achieves EF$^{+1}_{-1}$. For $n$ agents in general, we show that
there exist truthful mechanisms that achieve EF$^{+u}_{-v}$ for some $u$ and
$v$ that depend only on $n$ (not $m$).
  We further consider fair and truthful mechanisms that also satisfy the
standard efficiency guarantee: Pareto-optimality. We provide a mechanism that
simultaneously achieves truthfulness, EF$1$, and Pareto-optimality for
bi-valued utilities (where agents' valuation on each item is either $p$ or $q$
for some $p>q\geq0$). For tri-valued utilities (where agents' valuations on
each item belong to $\{p,q,r\}$ for some $p>q>r\geq0$) and any $u,v$, we show
that truthfulness is incompatible with EF$^{+u}_{-v}$ and Pareto-optimality
even for two agents.
