  In this paper we investigate the computational complexity of motivating
time-inconsistent agents to complete long term projects. We resort to an
elegant graph-theoretic model, introduced by Kleinberg and Oren, which consists
of a task graph $G$ with $n$ vertices, including a source $s$ and target $t$,
and an agent that incrementally constructs a path from $s$ to $t$ in order to
collect rewards. The twist is that the agent is present-biased and discounts
future costs and rewards by a factor $\beta\in [0,1]$. Our design objective is
to ensure that the agent reaches $t$ i.e.\ completes the project, for as little
reward as possible. Such graphs are called motivating. We consider two
strategies. First, we place a single reward $r$ at $t$ and try to guide the
agent by removing edges from $G$. We prove that deciding the existence of such
motivating subgraphs is NP-complete if $r$ is fixed. More importantly, we
generalize our reduction to a hardness of approximation result for computing
the minimum $r$ that admits a motivating subgraph. In particular, we show that
no polynomial-time approximation to within a ratio of $\sqrt{n}/4$ or less is
possible, unless ${\rm P}={\rm NP}$. Furthermore, we develop a
$(1+\sqrt{n})$-approximation algorithm and thus settle the approximability of
computing motivating subgraphs. Secondly, we study motivating reward
configurations, where non-negative rewards $r(v)$ may be placed on arbitrary
vertices $v$ of $G$. The agent only receives the rewards of visited vertices.
Again we give an NP-completeness result for deciding the existence of a
motivating reward configuration within a fixed budget $b$. This result even
holds if $b=0$, which in turn implies that no efficient approximation of a
minimum $b$ within a ration grater or equal to $1$ is possible, unless ${\rm
P}={\rm NP}$.
