A bad example for the cost ratio
We first describe a simple construction showing that the
cost ratio can be exponential in the number of nodes n. We
then move on to the main result of this section, which is a
characterization of the instances in which the cost ratio
achieves this exponential lower bound.
Our construction is an adaptation of the Akerlof example
from the introduction. We have a graph that consists of a
directed path s = v0, v1, v2, . . ., vn, and with each vi also linking
directly to node t. (The case n = 5 is the graph in Figure 2(a).)
With b = b− 1, we choose any m < b; we let the cost of the edge
(vj, t) be m j, and let the cost of each edge (vj, vj+ 1) be 0.
Now, when the agent is standing at node vj, it evaluates
the cost of going directly to t as m j, while the cost of the two-step path through vj+ 1 to t is evaluated as 0 + bmj+ 1 = (bm)mj
< mj. Thus the agent will follow the edge (vj, vj+ 1) with the
plan of continuing from vj+ 1 to t. But this holds for all j, so
once it reaches vj+ 1, it changes its mind and continues on to
vj+ 2, and so forth. Ultimately it reaches vn, and then must go
directly to t at a cost of cb(s, t) = mn. Since d(s, t) = 1 by using
the edge directly from s to t, this establishes the exponential
lower bound on the cost ratio cb(s, t)/d(s, t). Essentially, this
construction shows that the Akerlof example can be made
quantitatively much worse than its original formulation by
having the cost of going directly to the goal grow by a modest constant factor in each time step; when a present-biased
agent procrastinates in this case, it ultimately incurs an
exponentially large cost.
The following observation establishes this is the highest
possible cost ratio
Observation 3. 1. Consider an agent currently at v and let u be
the next node on Pb(v, t). Then d(u, t) < b × d(v, t).
Proof. If u is on the shortest path from v to t then clearly
the claim holds. Else, since the agent chose to continue to u
instead of continuing on the shortest path from v to t we have
c(v, u) + bd(u, t) £ d(v, t). This implies that d(u, t) £ b × d(v, t).
The observation essentially implies that with each step
that the agent takes the cost of the path that it plans to take
increases by an extra factor of at most b relatively to d(s, t).
Hence, we have a tight upper bound on the cost ratio:
Corollary 3. 2. The cost ratio for a graph G with n nodes is at
most bn− 2.
A graph minor characterization
We now provide a structural description of the graphs on
which the cost ratio can be exponential in the number of
nodes n—essentially we show that a constant fraction of the
nodes in such a graph must have the structure of the Akerlof
We make this precise using the notion of a minor. Given
two undirected graphs H and K, we say that H contains a
K-minor if we can map each node κ of K to a connected sub-
graph Sκ in H, with the properties that (i) Sκ and Sκ¢ are dis-
joint for every two nodes κ, κ¢ of K, and (ii) if (κ, κ¢) is an edge
of K, then in H there is some edge connecting a node in Sκ to
Figure 2(b) shows how to represent this scenario using a
graph. Node vij corresponds to a state in which i weeks of the
course are finished, and the student has completed j proj-
ects so far; we have s = v00 and t = v32. All edges go one column
to the right, indicating that one week will elapse regardless;
what is under the student’s control is how many rows the
edge will span. Horizontal edges have cost one, edges that
descend one row have cost four, and edges that descend two
rows in a single hop have cost nine. In this way, the graph
precisely represents the story just described.
How does the student’s construction of an s-t path work
out? From s, she goes to v10 and then to v20, intending to complete the path to t via the edge (v20, t). But at v20, she evaluates
the cost of the edge (v20, t) as 9 > br = 16/2 = 8, and so she quits
without reaching t. The story is thus a familiar one: the student plans to do both projects in the final week of the course,
but when she reaches the final week, she concludes that it
would be too costly and so she drops the course instead.
The instructor can prevent this from happening through
a very simple intervention. If he requires that the first project
be completed by the end of the second week of the course,
this corresponds simply to deleting node v20 from the graph.
With v20 gone, the path-finding problem changes: now the
student starting at s decides to follow the path s-v10-v21-t, and
at v10 and then v21 she continues to select this path, thereby
reaching t. Thus, by reducing the set of options available to
the student—and in particular, by imposing an intermediate deadline to enforce progress—the instructor is able to
induce the student to complete the course.
There are many stories like this one about homework and
deadlines, and our point is not to focus too closely on it in
particular. Indeed, to return to one of the underpinnings of
our graph-theoretic formalism, our point is in a sense the
opposite: it is hard to reason about the space of possible
“stories,” whereas it is much more tractable to think about
the space of possible graphs. Thus by encoding the set of
stories mechanically in the form of graphs, it becomes feasible to reason about them as a whole.
We have thus seen how a number of different time-inconsistency phenomena arise in simple instances of the
path-finding problem. The full power of the model, however, lies in proving statements that quantify over all graphs;
we begin this next.
3. THE COST RATIO: A CHARACTERIZATION VIA
Our path-finding model naturally motivates a basic quantity
of interest: the cost ratio, defined as the ratio between the
cost of the path found by the agent and the cost of the shortest path. We work here within the fixed-goal version of the
model, in which the agent is required to reach the goal t and
the objective is to minimize the cost of the path used.
To fix notation for this discussion, given a directed acyclic
graph G on n nodes with positive edge costs, we let d(v, w)
denote the cost of the shortest v-w path in G (using the true
edge costs, not modified by present bias). Let Pb(v, t) denote
the the v-t path followed by an agent with present-bias b, and
let cb(v, t) be the total cost of this path. The cost ratio can thus
be written as cb(s, t)/d(s, t).