  Present bias, the tendency to weigh costs and benefits incurred in the
present too heavily, is one of the most widespread human behavioral biases. It
has also been the subject of extensive study in the behavioral economics
literature. While the simplest models assume that the agents are naive,
reasoning about the future without taking their bias into account, there is
considerable evidence that people often behave in ways that are sophisticated
with respect to present bias, making plans based on the belief that they will
be present-biased in the future. For example, committing to a course of action
to reduce future opportunities for procrastination or overconsumption are
instances of sophisticated behavior in everyday life.
  Models of sophisticated behavior have lacked an underlying formalism that
allows one to reason over the full space of multi-step tasks that a
sophisticated agent might face. This has made it correspondingly difficult to
make comparative or worst-case statements about the performance of
sophisticated agents in arbitrary scenarios. In this paper, we incorporate the
notion of sophistication into a graph-theoretic model that we used in recent
work for modeling naive agents. This new synthesis of two formalisms -
sophistication and graph-theoretic planning - uncovers a rich structure that
wasn't apparent in the earlier behavioral economics work on this problem.
  In particular, our graph-theoretic model makes two kinds of new results
possible. First, we give tight worst-case bounds on the performance of
sophisticated agents in arbitrary multi-step tasks relative to the optimal
plan. Second, the flexibility of our formalism makes it possible to identify
new phenomena that had not been seen in prior literature: these include a
surprising non-monotonic property in the use of rewards to motivate
sophisticated agents and a framework for reasoning about commitment devices.
