  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 in order 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 et al., 2010] and
subsequently raised by [Procaccia, 2013] [Aziz and Ye, 2014] [Branzei and
Miltersen, 2015] [Menon and Larson, 2017] [Bei et al., 2017] [Bei et al.,
2020], 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: 1) there are only two agents; 2) agents' valuations are
piecewise-constant; 3) agents are hungry. 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 under this setting.
  To circumvent this impossibility result, motivated by the kind of
truthfulness possessed by the I-cut-you-choose protocol, we propose a weaker
notion of truthfulness: the proportional risk-averse truthfulness. We show that
several well-known algorithms 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.
