  We study the problem of allocating indivisible goods among agents in a fair
manner. While envy-free allocations of indivisible goods are not guaranteed to
exist, envy-freeness can be achieved by additionally providing some subsidy to
the agents. These subsidies can be alternatively viewed as a divisible good
(money) that is fractionally assigned among the agents to realize an envy-free
outcome. In this setup, we bound the subsidy required to attain envy-freeness
among agents with dichotomous valuations, i.e., among agents whose marginal
value for any good is either zero or one.
  We prove that, under dichotomous valuations, there exists an allocation that
achieves envy-freeness with a per-agent subsidy of either $0$ or $1$.
Furthermore, such an envy-free solution can be computed efficiently in the
standard value-oracle model. Notably, our results hold for general dichotomous
valuations and, in particular, do not require the (dichotomous) valuations to
be additive, submodular, or even subadditive. Also, our subsidy bounds are
tight and provide a linear (in the number of agents) factor improvement over
the bounds known for general monotone valuations.
