Moreover, with this framework in place, it becomes easier to express formal questions about design for these contexts: if as a designer of a complex task we are able to specify
the underlying graph structure, which graphs will lead time-inconsistent agents to reach the goal efficiently?
Our core questions are based on quantifying the inefficiency from time-inconsistent behavior, designing task
structures to reduce this inefficiency, and comparing the
behavior of agents with different levels of time-inconsistency. Specifically, we ask:
1. In which graph structures does time-inconsistent
planning have the potential to cause the greatest waste
of effort relative to optimal planning?
2. How do agents with different levels of present bias
(encoded as different values of b) follow combinatorially different paths through a graph toward the same
3. Can we increase an agent’s efficiency in reaching a
goal by deleting nodes and/or edges from the underlying graph, thus reducing the number of options
In what follows, we address these questions in turn.
For the first question, we consider n-node graphs and ask
how large the cost ratio can be between the path followed
by a present-biased agent and the path of minimum
total cost. Since deviations from the minimum-cost plan
due to present bias are sometimes viewed as a form of
“irrational” behavior, this cost ratio effectively serves as
a “price of irrationality” for our system. We give a characterization of the worst-case graphs in terms of graph
minors; this enables us to show, roughly speaking, that
any instance with sufficiently high cost ratio must contain a large instance of the Akerlof example embedded
For the second question, we consider the possible paths
followed by agents with different present-bias parameters b.
As we sweep b over the interval [0, 1], we have a type of
parametric path problem, where the choice of path is governed
by a continuous parameter (b in this case). We show that in
any instance, the number of distinct paths is bounded by a
polynomial function of n, which forms an interesting contrast with canonical formulations of the parametric shortest-path problem, in which the number of distinct paths can
be super polynomial in n. 5, 13
Lastly, for the third question, we show how it is possible
for agents to be more efficient when nodes and/or edges
are deleted from the underlying graph; on the other hand,
if we want to motivate an agent to follow a particular path P
through the graph, it can be crucial to present the agent with
a subgraph that includes not just P but also certain additional nodes and edges that do not belong to P. We give a
graph-theoretic characterization of the possible subgraphs
supporting efficient traversal.
Before turning to these questions, we first discuss the
basic graph-theoretic problem in more detail, showing how
instances of this problem capture the time-inconsistency
phenomena discussed earlier in this section.
In the next section we will show how our graph-theoretic model easily captures time-inconsistency phenomena including procrastination, abandonment, and choice
reduction. But to make the definitions concrete, it is useful to work through the agent’s computation on the graph
depicted in Figure 1. As shown in Figure 1, an agent that has
a present-bias parameter of b = 1/2 needs to go from s to t.
From s, the agent evaluates the path s-a-b-t as having cost 16 +
2b + 2b = 18, the path s-c-d-t as having cost 8 + 8b + 8b = 16,
and the path s-c-e-t as having cost 8 + 2b + 16b = 17. Thus
the agent traverses the edge (s, c) and ends up at c. From c,
the agent now evaluates the path c-d-t as having cost 8 + 8b
= 12 and the path c-e-t as having cost 2 + 16b = 10, and so
the agent traverses the edge (c, e) and then (having no further
choices) continues on the edge (e, t).
This example illustrates a few points. First, when the
agent set out on the edge (s, c), it was intending to next follow the edge (c, d), but when it got to c, it changed its mind
and followed the edge (c, e). A time-consistent agent (with
b = 1), in contrast, would never do this; the path it decides
to take starting at s is the path it will continue to follow all
the way to t. Second, we are interested in whether the agent
minimizes the cost of traveling from s to t according to the
real costs, not according to its evaluation of the costs, and in
this regard it fails to do so; the shortest path is s-a-b-t, with a
cost of 20, while the agent incurs a cost of 26.
Overview of results
Our graph-theoretic framework makes it possible to reason
about time-inconsistency effects that arise in very different settings, provided simply that the underlying decisions
faced by the agent can be modeled as the search for a path
through a graph-structured sequence of options. And perhaps more importantly, since it is tractable to ask questions
that quantify over all possible graphs, we can cleanly compare different scenarios, and search for the best or worst
possible structures relative to specific objectives. This is difficult to do without an underlying combinatorial structure.
For example, suppose we were inspired by Akerlof’s example
to try identifying the scenario in which time-inconsistency
leads to the greatest waste of effort. A priori, it is not clear
how to formalize the search over all possible “scenarios.”
But as we will see, this is precisely something we can do if
we simply ask for the graph in which time-inconsistency
produces the greatest ratio between the cost of the path traversed and cost of the optimal path.
sc d t
Figure 1. A present-biased agent must choose a path from s to t.