  We consider the problem of allocating a set on indivisible items to players
with private preferences in an efficient and fair way. We focus on valuations
that have dichotomous marginals, in which the added value of any item to a set
is either 0 or 1, and aim to design truthful allocation mechanisms (without
money) that maximize welfare and are fair. For the case that players have
submodular valuations with dichotomous marginals, we design such a
deterministic truthful allocation mechanism. The allocation output by our
mechanism is Lorenz dominating, and consequently satisfies many desired
fairness properties, such as being envy-free up to any item (EFX), and
maximizing the Nash Social Welfare (NSW). We then show that our mechanism with
random priorities is envy-free ex-ante, while having all the above properties
ex-post. Furthermore, we present several impossibility results precluding
similar results for the larger class of XOS valuations.
  To gauge the robustness of our positive results, we also study
$\epsilon$-dichotomous valuations, in which the added value of any item to a
set is either non-positive, or in the range $[1, 1 + \epsilon]$. We show
several impossibility results in this setting, and also a positive result: for
players that have additive $\epsilon$-dichotomous valuations with sufficiently
small $\epsilon$, we design a randomized truthful mechanism with strong ex-post
guarantees. For $\rho = \frac{1}{1 + \epsilon}$, the allocations that it
produces generate at least a $\rho$-fraction of the maximum welfare, and enjoy
$\rho$-approximations for various fairness properties, such as being envy-free
up to one item (EF1), and giving each player at least her maximin share.
