On the Value of Penalties in Time-Inconsistent Planning

arXiv:1702.01677v1 [cs.DS] 6 Feb 2017

Susanne Albers ∗

Dennis Kraft†

Abstract
People tend to behave inconsistently over time due to an inherent present bias. As this may impair
performance, social and economic settings need to be adapted accordingly. Common tools to reduce the
impact of time-inconsistent behavior are penalties and prohibition. Such tools are called commitment devices. In recent work Kleinberg and Oren [5] connect the design of prohibition-based commitment devices
to a combinatorial problem in which edges are removed from√a task graph G with n nodes. However, this
problem is NP-hard to approximate within a ratio less than n/3 [2]. To address this issue, we propose
a penalty-based commitment device that does not delete edges but raises their cost. The benefits of our
approach are twofold. On the conceptual side, we show that penalties are up to 1/β times more efficient
than prohibition, where β ∈ (0, 1] parameterizes the present bias. On the computational side, we significantly improve approximability by presenting a 2-approximation algorithm for allocating the penalties.
To complement this result, we prove that optimal penalties are NP-hard to approximate within a ratio of
1.08192.

1 Introduction
Most people make long term plans. They intend to eat healthy, save money, prepare for exams, exercise
regularly and so on. Curiously, the same people often change their plans at a later point in time. They indulge
in fast food, squander their money, fail to study and skip workouts. Although change may be necessary due
to unforeseen events, people often change their plans even if the circumstances stay the same. This type of
time-inconsistent behavior is a well-known phenomenon in behavioral economics and might impair a person’s
performance in social or economic domains [1, 8].
A sensible explanation for time-inconsistent behavior is that people are present biased and assign disproportionately greater value to the present than to the future. Consider, for instance, a scenario in which
a student named Alice attends a course over several weeks. To pass the course, Alice either needs to solve
a homework exercise each week or give a presentation once. The presentation incurs a onetime effort of 3,
whereas each homework exercise incurs an effort of 1. Assume that she automatically fails the course if she
misses a homework assignment before she has given a presentation. If the course lasts for more than 3 weeks,
she clearly minimizes her effort by giving a presentation in the first week. Paradoxically, if Alice is present
biased, she might solve all homework exercises instead. The reason for this is the following:
Suppose Alice perceives present effort accurately, but discounts future effort by a factor of β = 1/3. In
the first week Alice must decide between solving the homework exercise or giving a presentation. Clearly, the
homework incurs less immediate effort than the presentation. Furthermore, Alice can still give a presentation
next week. Her perceived effort for doing the homework this week and giving the presentation the week
after is 1 + β3 = 2. To Alice this plan appears more convenient than giving the presentation right away.
Consequently, she does the homework. However, come next week she changes this plan and postpones the
∗

Department of Computer Science, Technical University of Munich, 85748 Garching, Germany; albers@in.tum.de. Work
supported by the European Research Council, Grant Agreement No. 691672.
†
Department of Computer Science, Technical University of Munich, 85748 Garching, Germany. kraftd@in.tum.de

1

presentation once more. Her reasoning is the same as in the first week. Due to her time-inconsistent behavior,
Alice continues to postpone the presentation and ends up doing all the homework assignments.
Previous Work Time-inconsistent behavior has been studied extensively in behavioral economics. For
an introduction to the topic refer for example to [1]. Alice’s scenario demonstrates how time-inconsistency
arises whenever people are present biased. Alice evaluates her preferences based on a well-established discounting model called quasi-hyperbolic-discounting [7]. As her story shows, quasi-hyperbolic-discounting
tempts people to make poor decisions. To prevent poor decisions, social and economic settings need to be
adapted accordingly. Depending on the domain, such adaptations might be implemented by governments,
companies, teachers or people themselves. We call these entities designers and their motivation can be benevolent or self-serving. In either case, the designer’s objective is to commit people to a certain goal. Their tools
are called commitment devices and may include rewards, penalty fees and strict prohibition [3, 9].
Until recently, the study of time-inconsistent behavior lacked a unifying and expressive framework. However, groundbreaking work by Kleinberg and Oren closed this gap by reducing the behavior of a quasihyperbolic-discounting person to a simple planning problem in task graphs [5]. Their framework has helped
to identify various structural properties of social and economic settings that affect the performance of present
biased individuals [5, 10]. It has also been extended to people whose present bias varies over time [4] as well
as people who are aware of their present bias and act accordingly [6]. We will formally introduce the framework in Section 2. A significant part of Kleinberg and Oren’s work is concerned with the study of a simple
yet powerful commitment device based on prohibition [5]. In particular, they demonstrate how performance
can be improved by removing a strategically chosen set of edges from the task graph. The drawback of their
approach is its computational complexity. As it turns out, an optimal commitment device is NP-hard to ap√
proximate within a ratio less than n/3, where n denotes the number nodes in the task graph [2]. Currently,
√
the best known polynomial-time approximation achieves a ratio of 1 + n [2]. It should be mentioned that
Kleinberg and Oren’s framework has also been used to analyze reward-based commitment devices [2, 10].
Unfortunately, their computational complexity does not permit a polynomial-time approximation within a
finite ratio unless P = NP [2].
Our Contribution To circumvent the theoretical bottleneck mentioned above, we propose a natural
generalization of Kleinberg and Oren’s commitment device. Instead of prohibition, our commitment device is
based on penalty fees, a standard tool in the economic literature [3, 9]. This means that the designer is free to
raise the cost of arbitrary edges in the task graph. We call such an assignment of penalties a cost configuration.
The designer’s objective is to construct cost configurations that are as efficient as possible.
In Section 3 we conduct a quantitative comparison between the efficiency of prohibition-based and penaltybased commitment devices. Assuming that optimal solutions are known, we show that penalties are strictly
more powerful than prohibitions. In particular, we show that penalties may outperform prohibitions by a factor
of 1/β where β parameterizes the present bias. This result is tight. In Section 4 we investigate the computational complexity of our commitment device. Using a reduction from 3-SAT, we argue that the construction
of an efficient cost configuration is NP-hard when posed as a decision problem. A generalization of this reduction proves NP-hardness for approximations within a ratio of 1.08192. Unless P = NP, this dismisses
the existence of a polynomial-time approximation scheme. While analyzing the complexity of our commitment device we also point to a remarkable structural property. More specifically, we show that every cost
configuration admits another cost configuration of comparable efficiency that assigns its cost entirely along
a single path. Assuming that the path is known in advance, we provide an algorithm for constructing such a
cost configuration in polynomial-time. This result is important for the design of exact algorithms as it reduces
the search space to the set of paths through the task graph. Finally, Section 5 introduces a 2-approximation
algorithm for our commitment device. This is the main result of our work and a considerable improvement to

2

the complexity theoretic barrier of

√

n/3 for approximating prohibition-based commitment devices [2].

2 The Formal Framework
In the following, we introduce Kleinberg and Oren’s framework [5]. Let G = (V, E) be a directed acyclic
graph with n nodes that models a given long-term project. The edges of G correspond to the tasks of the
project and the nodes represent the states. In particular, there exists a start state s and a target state t. Each
path from s to t corresponds to a valid sequence of tasks to complete the project. The effort of a specific task
is captured by a non-negative cost c(e) assigned to the associated edge e.
To complete the project, an agent with a present bias of β ∈ (0, 1] incrementally constructs a path from
s to t as follows: At any node v different from t, the agent evaluates her lowest perceived cost. For this
purpose she considers all paths P leading from v to t. However, she only anticipates the cost of the first
edge of P correctly; all other edges of P are discounted by her present bias. More formally, let d(w) denote the cost of a cheapest path from node w to t. The agent’s lowest perceived cost at v is defined as
ζ(v) = min{c(v, w) + βd(w) | (v, w) ∈ E}. We assume that she only traverses edges (v, w) that minimize
her anticipated cost, i.e. edges for which c(v, w) + βd(w) = ζ(v). Ties are broken arbitrarily. For convenience, we define the perceived cost of (v, w) as η(v, w) = c(v, w) + βd(w). The agent is motivated by an
intrinsic or extrinsic reward r collected at t. As she receives this reward in the future, she perceives its value as
βr at each node different from t. When located at v, she compares her lowest perceived cost to the anticipated
reward and continues moving if and only if ζ(v) ≤ βr. Otherwise, if ζ(v) > βr, we assume she abandons
the project. We call G motivating if she does not abandon while constructing her path from s to t. Note that
in some graphs the agent can take several paths from s to t due to ties between incident edges. In this case, G
is considered motivating if she does not abandon on any of these paths.
For the sake of a clear presentation, we will assume throughout this work that each node of G is located
on a path from s to t. This assumption is sensible for the following reason: Clearly, the agent can only visit
nodes that are reachable from s. Furthermore, she is not willing to enter nodes that do not lead to the reward.
Consequently, only nodes that are on a path from s to t are relevant to her behavior. Note that all nodes that
do not satisfy this property can be removed from G in a simple preprocessing step.
To illustrate the model, we revisit Alice’s scenario from Section 1. Assume that the course takes m weeks.
We represent each week i by a distinct node vi and set s = v1 . Furthermore, we introduce a target node t that
marks the passing of the course. Each week i < m Alice can either give a presentation or proceed with the
homework. We model the first case by an edge (vi , t) of cost 3 and the latter case by an edge (vi , vi+1 ) of cost
1. In the last week, i.e. i = m, Alice’s only sensible choice is to do the homework. Therefore, edge (vm , t) is
of cost 1. Recall that Alice’s present bias is β = 1/3. Moreover, assume that her intrinsic reward for passing
is r = 6. For i < m her perceived cost of the edges (vi , t) is η(vi , t) = c(vi , t) = 3. As this is less than her
perceived reward, which is β6 = 2, she is never motivated to give a presentation right away. However, her
perceived cost of the edges (vi , vi+1 ) is at most η(vi , vi+1 ) ≤ c(vi , vi+1 ) + βc(vi+1 , t) ≤ 2. This matches her
perceived reward. As a result, she walks from v1 to vm along the edge (vi , vi+1 ). Once she reaches vm she
traverses the only remaining edge for a perceived cost of η(vm , t) = c(vm , t) = 1 and passes the course. This
matches our analysis from Section 1.

3 Prohibition versus Penalty
In this section we demonstrate how the designer can modify a given project to help the agent reach t. For this
purpose, the designer may have several commitment devices at her disposal. A straightforward approach is to
increase the reward that the agent collects at t. Although this may keep the agent from abandoning the project
prematurely, it has no influence on the path taken by the agent. Furthermore, increasing the reward may be
3

costly for the designer. As a result, the designer has two conflicting objectives. On the one hand, she must
ensure that the agent reaches t. On the other hand, she needs to minimize the resources spent. To deal with
this dilemma, Kleinberg and Oren allow the designer to prohibit a strategically chosen set of tasks [5]. This
commitment device is readily implemented in their framework. In fact, it is sufficient to remove all edges of
prohibited tasks. The result is a subgraph G′ that may significantly reduce the reward required to motivate the
√
agent. Unfortunately, an optimal subgraph G′ is NP-hard to approximate within a ratio less than n/3 [2].
To circumvent this theoretical bottleneck, we propose a different approach. Instead of prohibiting certain
tasks we allow the designer to charge penalty fees. Such fees could be implemented in several ways; for
instance in the form of donations to charity. Our only assumption is that the designer does not benefit from
the fees, i.e. there is no incentive to maximize the fees payed by the agent. Similar to commitment devices
based on prohibition, our commitment device is readily implemented in Kleinberg and Oren’s framework.
The designer simply assigns a positive extra cost c̃(e) to the desired edges e. The new cost of e is equal to
c(e) + c̃(e). We call c̃ a cost configuration. Applying a cost configuration to G yields a new task graph with
increased edge cost. All concepts of the original framework carry over immediately. Sometimes it will be
necessary to compare different commitment devices with each other. To clarify which commitment device we
are talking about, we use the following notation whenever necessary: If we consider a subgraph G′ , we write
dG′ , ηG′ and ζG′ . Similarly, if we consider a cost configuration c̃, we write dc̃ , ηc̃ and ζc̃ . Moreover, we denote
the trivial cost configuration, i.e. the one that assigns no extra cost, by 0̃.
It is interesting to think of penalty fees as a natural generalization of prohibition. This becomes particularly
apparent in the context of Kleinberg and Oren’s framework as we can recreate the properties of any subgraph
G′ by a cost configuration c̃. For this purpose, it is sufficient to assign an extra cost of c̃(e) = r + 1 to
any edge e not contained in G′ . As a result, the agent’s perceived cost of paths along e certainly exceeds her
perceived reward. However, this means that e is irrelevant to the agent’s planning and could be deleted from G
altogether. Consequently, penalties are at least as powerful as prohibitions. But how much more efficient are
penalties in the best case? As the following theorem suggests, cost configurations may outperform subgraphs
by a factor of almost 1/β.
Theorem 1. The ratio between the minimum reward r that admits a motivating subgraph and the reward q of
a motivating cost configuration is at most 1/β. This bound is tight.
Proof. To see that r/q ≤ 1/β, let G be an arbitrary task graph and consider a subgraph G′ whose only edges
are those of a cheapest path P from s to t. Recall that d(s) denotes the cost of P . In G′ the agent’s only choice
is to follow P . Because her perceived cost is a discounted version of the actual cost, she never perceives a
cost greater than d(s) in G′ . Consequently, d(s)/β is an upper bound on r. Next, consider an arbitrary cost
configuration c̃. As c̃ only increases edge cost, the agent’s lowest perceived cost at s is at least βd(s). We
conclude that q must be at least d(s) to be motivating. This yields the desired ratio.
It remains to show the tightness of the result. For this purpose, we construct a task graph G such that: (a)
The minimum reward that admits a motivating subgraph is 1/β 2 . (b) There exists a cost configuration that
is motivating for a reward of (1 + ε)/β, where ε is a positive value strictly less than 1. Our construction is
a modified version of Alice’s task graph. Let m = ⌈β −2 (1 − β)−1 ε−2 ⌉ and assume that G contains a path
v1 , . . . , v2m+1 whose edges are all of cost (1−β)ε2 . We call this the main path and set s = v1 and t = v2m+1 .
In addition to the main path, each vi with i ≤ 2m has a shortcut to t via a common node w. The edges (vi , w)
are free, whereas (w, t) is of cost 1/β. Figure 1 illustrates the structure of G. Note that the drawing merges
some of the edges (vi , w) for a concise representation.
We proceed to argue that G satisfies (a). For the sake of contradiction, assume the existence of a subgraph
G′ that is motivating for a reward r < 1/β 2 . In this case the agent must not take shortcuts as her perceived cost
at w exceeds her perceived reward. Therefore, she must follow the main path. In particular, she must visit each
node vi on the first half of the path, i.e. i ≤ m+1. At each of these nodes, her lowest perceived cost is realized
along the edge (vi , vi+1 ). Essentially, there are two ways she can come up with this cost. First, she might
4

w

...
0
s

v2
(1 − β)ε2

0

v3

0

...

1/β

v2m 0

(1 − β)ε2

(1 − β)ε2

t

Figure 1: Graph maximizing the ratio between the efficiency of subgraphs and cost configurations
plan to take a shortcut at a later point in time. As a result, we get ηG′ (vi , vi+1 ) ≥ c(vi , vi+1 ) + βc(w, t) > 1.
Secondly, she might plan to stay on the main path. In this case she must traverse at least m edges, each of
which contributes β(1 − β)ε2 or more to ηG′ (vi , vi+1 ). Consequently, we get ηG′ (vi , vi+1 ) ≥ mβ(1 − β)ε2 ≥
1/β ≥ 1. Either way her perceived cost for taking the main path is at least 1. As this tempts her to take the
shortcut at vi , all of the first m + 1 shortcuts must be interrupted in G′ . This means she must walk along at
least m edges of the main path before taking the first shortcut. As a result, her lowest perceived cost at v1 is
at least ζG′ (v1 ) ≥ mβ(1 − β)ε2 ≥ 1/β. This is a contradiction to the assumption that r is motivating.
Next we show how to construct a cost configuration c̃ that satisfies (b). For this purpose it is sufficient to
add an extra cost of ε to all edges (vi , w). To upper bound the agent’s perceived cost of (vi , vi+1 ), assume
she plans to take a shortcut in the next step, i.e. at vi+1 . For i < 2m we get ηc̃ (vi , vi+1 ) ≤ c(vi , vi+1 ) +
β(c̃(vi+1 , w) + c(w, t)) = (1 − β)ε2 + βε + 1 < 1 + ε. In the special case of i = 2m, the inequality
ηc̃ (vi , vi+1 ) < 1 + ε is still satisfied, this time via the direct edge (v2m , t). In contrast, the agent’s perceived
cost of an immediate shortcut is ηc̃ (vi , t) = ε + βc(w, t) = 1 + ε for all i ≤ 2m. Therefore, she is never
tempted to divert from the main path. Furthermore, a reward of q = (1 + ε)/β is sufficient to keep her
motivated.

4 Computing Motivating Cost Configurations
We now turn our attention to the computational aspects of designing efficient penalty fees. In this section, we
assume that the agent’s reward is fixed to some value r > 0. Our goal is to compute cost configurations that
are motivating for r whenever they exist. Similar to prohibition-based commitment devices [2], this task is
NP-hard whenever the agent is present biased, i.e. β 6= 1. We will prove this claim at the end of the section.
But first, assume that we already have partial knowledge of the solution. More precisely, assume we know one
of the paths the agent might take in a motivating cost configuration provided a motivating cost configuration
exists. We call this path P . Based on P , Algorithm 1 constructs a cost configuration c̃ that is motivating for a
slightly larger reward r + ε.
Algorithm 1: PATH A ND F ENCE
Input: Task graph G, present bias β, path P = v1 , . . . , vm , positive value ε
Output: Cost configuration c̃
1 c̃ ← 0̃;
2 for i from m − 1 to 1 do
3
foreach w ∈ {w′ | (vi , w′ ) ∈ E} do
4
if w 6= vi+1 then c̃(vi , w) ← max{0, ηc̃ (vi , vi+1 ) − ηc̃ (vi , w) + βε/(m − 2)}
5

return c̃;

The basic idea of Algorithm 1 is simple. Starting with vm−1 , it considers all nodes vi of P in reverse
order. For each vi it assigns an extra cost of max{0, ηc̃ (vi , vi+1 ) − ηc̃ (vi , w) + βε/(m − 2)} to the edges
(vi , w) that leave P , i.e. edges different from (vi , vi+1 ). As a result, the agent’s perceived cost of (vi , w) is
5

greater than that of (vi , vi+1 ) by at least βε/(m − 2). Consequently, she has no incentive to divert from P
at vi . Since the algorithm runs in reverse order, extra cost assigned in iteration i has no effect on the agent’s
behavior at later nodes, i.e. nodes vj with j > i. Figuratively speaking, the algorithm builds a fence of penalty
fees along P preventing the agent from leaving P . For this reason, we call the algorithm PATH A ND F ENCE.
As the next proposition suggests, cost configurations of this particular fence structure can achieve almost the
same efficiency as any other cost configuration. Due to space constraints, refer to the Appendix for a proof.
Proposition 1. Let P be the agent’s path from s to t with respect to a cost configuration c̃∗ that is motivating
for a reward r. PATH A ND F ENCE constructs a cost configuration c̃ that is motivating for a reward of r + ε,
where ε is an arbitrary small but positive quantity.
Proposition 1 has some interesting implications. The first one is of conceptual nature. Note that PATH A ND F ENCE constructs a cost configuration that never actually charges the agent any extra cost. This suggests the
existence of efficient penalty-based commitment devices that do not require the designer to enforce penalties.
The mere threat of repercussions appears to be sufficient. The second implication is computational. Clearly,
PATH A ND F ENCE runs in polynomial-time with respect to n. In particular, the number of iterations does not
depend on the choice of ε. Consequently, PATH A ND F ENCE can be combined with an exhaustive search algorithm that considers all paths from s to t to search for a motivating cost configuration. Although the number
of such paths can be exponential in n, this approach still reduces the size of the search space considerably.
Finally, it should be noted that a similar result for commitment devices based on prohibition is unlikely to
exist. The reason is that subgraphs remain hard to approximate even if the agent’s optimal path is known [2],
indicating a favorable computational complexity for the design of penalty fees. Of course there is another
potential source of hardness: the computation of P . To prove that this is a limiting factor, we introduce the
decision problem MOTIVATING COST CONFIGURATION:
Definition 1 (MCC). Given a task graph G, a reward r > 0 and a present bias β ∈ (0, 1], decide the existence
of a motivating cost configuration.
We propose a reduction from 3-SAT to show that MCC is NP-complete for arbitrary β ∈ (0, 1). At a later
point we will use the same reduction to establish a hardness of approximation result.
Theorem 2. MCC is NP-complete for any present bias β ∈ (0, 1).
Proof. According to [2], whether or not a given task graph is motivating for a fixed reward can be verified
in polynomial-time. Of course, this remains valid if the edges are assigned extra cost. Consequently, any
motivating cost configuration is a suitable certificate for a ”yes”-instance of MCC. We conclude that MCC
is in NP. In the following, we present a reduction from 3-SAT to show that MCC is also NP-hard. This
establishes the theorem.
Let I be an arbitrary instance of 3-SAT consisting of ℓ clauses c1 , . . . , cℓ over m variables x1 , . . . , xm .
We construct a MCC instance J such that its task graph G admits a motivating cost configuration for a reward
of r = 1/β if and only if I has a satisfying variable assignment. Figure 2 depicts G for a small sample
instance of I. In general, G consists of a source s, a target t and five nodes u1 , . . . , u5 . Depending on I, G
also contains some extra nodes. For each variable xk , there are two variable nodes wk,T and wk,F . The idea
is to interpret xk as true whenever the agent visits wk,T and as false whenever she visits wk,F . As a result, the
agent’s walk through G yields a variable assignment τ . Furthermore, for each clause ci there is a literal node
vi,j corresponding to the j-th literal of ci . Our goal is to construct G in such a way that every motivating cost
configuration guides the agent along literal nodes that are satisfied with respect to τ .
All nodes vi,j and wk,y are connected via so-called forward edges. More specifically, for all 1 ≤ i < ℓ
and 1 ≤ j, j ′ ≤ 3 there is a forward edge from vi,j to vi+1,j ′ . Similarly, there is a forward edge from wk,y to
wk+1,y′ for all 1 ≤ k < m and y, y ′ ∈ {T, F }. We also have forward edges from s to each v1,j , from each
6

(1 − β)3 − ε
w1,T

w1,F

(1 − β)3 − ε

w2,T

w2,F

(1 − β)3 − ε

w3,T

w3,F

(1 − β)3 − ε

v1,1
s

v1,2

(1 − β)3 − ε

(1 − β)2 (1 − β)

u3

u4

(1 − β)2

v1,3

v2,1

u2

u1

v2,3

v3,1

v2,2
(1 − β)3 − ε

1

u5

t

(1 − β)3 − ε

v3,2

v3,3

(1 − β)3 − ε

Figure 2: Reduction from the 3-SAT instance: (x̄1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x̄2 ∨ x̄3 ) ∧ (x1 ∨ x̄2 ∨ x3 )
vℓ,j to u1 , from u2 to each w1,y and from each wm,y to u3 . For the sake of readability, some forward edges
are merged in Figure 2. The price of each forward edge is (1 − β)3 − ε, where the encoding length of β is
assumed to be polynomial in I. Furthermore, ε denotes a small but positive quantity such that
n
β(1 − β)3 β(1 − β)2 o
.
,
ε < min (1 − β)2 ,
1+β
1+β
In addition to the forward edges, there are three types of shortcuts. The first type, which is depicted as dashed
edges in Figure 2, connects each literal node vi,j to a distinct variable node via a single edge of cost (1 − β)2 .
If the j-th literal of ci is equal to xk , the shortcut goes to wk,F . Otherwise, if the literal is negated, i.e. x̄k ,
the shortcut goes to wk,T . The second type of shortcut goes from u2 to t along a single edge of cost 2 − β.
For clear representation, this shortcut is omitted in Figure 2. The third type of shortcut connects each variable
node wk,y to t via a distinct intermediate node. The first edge is free while the second costs 2 − β. Again,
shortcuts of this type are omitted in Figure 2 to keep the drawing simple. Finally, there are four more edges
(u1 , u2 ), (u3 , u4 ), (u4 , u5 ) and (u5 , t) of cost (1 − β)2 , (1 − β)2 , 1 − β and 1 respectively. Note that G is
acyclic and its encoding length is polynomial in I.
To establish the theorem, we must show that I has a satisfying variable assignment if and only if J has
a motivating cost configuration. A detailed argument is described in the Appendix. At this point we only
sketch the main ideas. For this purpose let c̃ be a cost configuration that is motivating for a reward of 1/β and
let P be the agent’s path through G with respect to c̃. Note that P cannot contain shortcuts of the second or
third type as their edges are too expensive. Furthermore, P cannot contain a shortcut of the first type because
the agent either perceives it as too expensive or is tempted to enter a shortcut of the third type immediately
afterwards. As a result, P contains exactly one of the two nodes wk,T and wk,F for each variable xk . Let
τ : {x1 , . . . , xm } → {T, F } be the corresponding variable assignment. To keep the agent on P , c̃ must
assign extra cost to all shortcuts that start at a variable node satisfied by τ . However, this raises the perceived
cost of all paths via literal nodes not satisfied by τ to values that are not motivating. Consequently, P cannot
contain such literal nodes. But P must contain exactly one literal node of each clause because P takes no
shortcuts. This means that τ satisfies at least one literal in each clause and is therefore a feasible solution
of I. Conversely, whenever I has a feasible solution τ , we can construct a motivating cost configuration c̃
as follows: First, assign an appropriate extra cost, e.g. (1 − β)2 , to the shortcuts of type three starting at the
variable nodes wk,τ (xk ) . Secondly, block the forward edges into the variable nodes wk,τ (x̄k ) with high extra
cost of e.g. 1.

7

(1 − β)2
s

v1
3

(1 − β)

w

v2
3

(1 − β)

2−β

v3
2

(1 − β)

v4
1−β

1

t

Figure 3: Task graph with no optimal cost configuration

5 Approximating Motivating Cost Configurations
The previous section showed that optimal penalty-based commitment devices are NP-hard to design. This section therefore focuses on an optimization version of the problem. Our goal is to construct cost configurations
that require the designer to raise the reward at t as little as possible. However, before we provide a formal
definition of the problem we should consider a curious technical detail; namely, not all task graphs admit an
optimal cost configuration.
Consider, for instance, the task graph in Figure 3. At v1 the agent is indifferent between the edges (v1 , v2 )
and (v1 , w). In both cases her perceived cost is 1. If she chooses (v1 , w), she faces a perceived cost of 2 − β
at w. Conversely, if she chooses (v1 , v2 ), she perceives a cost of 1 at v2 , v3 and v4 . Assuming that β < 1,
(v1 , v2 ) is the better choice. To break the tie between (v1 , w) and (v1 , v2 ) we must place a positive extra cost
of ε onto the upper path. However, when located at s the agent’s perceived cost of the upper path is 1 + βε.
In contrast, her perceived cost of the lower path is 1 + β(1 − β)3 . Assuming that ε < (1 − β)3 , she prefers
the upper path. Consequently, we can construct a cost configuration that is motivating for a reward arbitrarily
close to 1/β, but no cost configuration is motivating for a reward of exactly 1/β. To account for the potential
lack of an optimal solution, we compare our results to the infimum of all rewards that admit a motivating cost
configuration. The optimization problem MCC-OPT is defined accordingly:
Definition 2 (MCC-OPT). Given a task graph G and a present bias β ∈ (0, 1), determine the infimum of all
rewards for which a motivating cost configuration exists.
Algorithm 2: M IN M AX PATH A PPROX
Input: Task graph G, present bias β
Output: Cost configuration c̃
1 P ← minmax path from s to t with respect to η0̃ ;
2 ̺ ← max{η0̃ (e) | e ∈ P };
3 foreach v ∈ V \ {t} do
4
ς(v) ← successor node of v on a cheapest path from v to t;
5
6

7
8
9
10
11

foreach (v, w) ∈ E do
if (v, w) ∈ P ∨ (ς(v) = w ∧ v ∈
/ P ) then c̃(v, w) ← 0 else if (v, w) 6= P ∧ ς(v) 6= w then
c̃(v, w) ← 3̺/β else
P ′ ← v, ς(v), ς(ς(v)), . . . , t;
u ← first node of P ′ different from v that is also a node of P ;
e ← most expensive edge of P ′ , between v and u;
c̃(v, w) ← c(e);
return c̃;

We are now ready to introduce Algorithm 2. This algorithm enables us to construct cost configurations that
approximate MCC-OPT within a factor of 2. At a high level, the algorithm proceeds in two phases. First, it
8

computes a value ̺ such that ̺/β is a lower bound for any reward that admits a motivating cost configuration.
Secondly, it constructs a cost configuration c̃ that is motivating for a reward of 2̺/β. This yields the promised
approximation ratio of 2.
For a more detailed discussion of Algorithm 2 assume that each edge e is labeled with its perceived
cost η0̃ (e). Furthermore, let c̃′ be an arbitrary cost configuration and P ′ the agent’s corresponding path from
s to t. Our goal is to lower bound the minimum reward that is motivating for c̃′ by some value ̺/β. For this
purpose, it is instructive to observe that any motivating reward must be at least max{ηc̃′ (e) | e ∈ P ′ }/β ≥
max{η0̃ (e) | e ∈ P ′ }/β. Since P ′ can be an arbitrary path from s to t, we set

̺ = min max{η0̃ (e) | e ∈ P } P is a path from s to t .
In other words, ̺ is the maximum edge cost of a minmax path P from s to t with respect to η0̃ . Note that P
can be computed in polynomial-time by adding the edges of G in non-decreasing order of perceived cost to
an initially empty set E ′ until s and t become connected for the first time. Any path from s to t that only uses
edges of E ′ is a suitable minmax path.
We continue with the construction of c̃. To facilitate this task, Algorithm 2 sets up a cheapest path successor relation ς. More precisely, it assigns a distinct successor node ς(v) to each v ∈ V \ {t}. The successor is
chosen in such a way that (v, ς(v)) is the initial edge of a cheapest path from v to t. Since we may assume
that t is reachable from each node of G, all v 6= t must have at least one suitable successor. By construction
of ς, any path P ′ = v, ς(v), ς(ς(v)), . . . , t is a cheapest path from v to t. We call P ′ the ς-path of v.
Once ς has been created, Algorithm 2 starts to assign an appropriate extra cost to all edges of G. The
idea behind this assignment is to either keep the agent on P or guide her along a suitable ς-path. For this
reason, we also call the algorithm M IN M AX PATH A PPROX. While iterating through the edges (v, w) of G
the algorithm distinguishes between three types of edges: First, (v, w) might be an edge of P or an edge of a
ς-path. In the latter case v must not be a node of P . Any (v, w) that satisfies these requirements is an edge we
want the agent to traverse or use in her plans. Consequently, (v, w) is assigned no extra cost. Secondly, (v, w)
might neither be an edge of P nor of a ς-path. Since we do not want the agent to traverse or plan along such
an edge, the algorithm assigns an extra cost of 3̺/β to (v, w). This is sufficiently expensive for the agent to
lose interest in (v, w) provided that the reward is 2̺/β. Thirdly, (v, w) might not be an edge of P but of a
ς-path such that v is a node of P . This is the most involved case. To find an appropriate cost for (v, w), the
algorithm considers the ς-path P ′ of v. Let u be the first common node between P and P ′ that is different
from v. Because P and P ′ both end in t, such a node must exist. Moreover, let e be the most expensive edge
of P ′ between v and u. The algorithm assigns an extra cost of c(e) to (v, w). As we will show in Theorem 3,
this cost is either high enough to keep the agent on P or she travels to u along P ′ without encountering edges
that are too expensive.
Clearly, Algorithm 2 can be implemented to run in polynomial-time with respect to the size of G. It
remains to show that the algorithm returns a cost configuration c̃ that approximates MCC-OPT within a factor
of 2.
Theorem 3. M IN M AX PATH A PPROX has an approximation ratio of 2.
Proof. Recall that ̺ denotes the maximum perceived edge cost along the minmax path P . From the above
description of M IN M AX PATH A PPROX, it should be evident that ̺/β is a lower bound on the minimum motivating reward of any cost configuration. To prove the theorem, we need to show that the algorithm returns a
cost configuration c̃ that is motivating for a reward of 2̺/β.
As our first step we argue that the cost of a cheapest path from any node v to t with respect to c̃ is at
most twice the cost of a cheapest path with respect to 0̃. More formally, we prove that dc̃ (v) ≤ 2d0̃ (v). For
this purpose let P ′ be the ς-path of v. By construction of ς, P ′ is a cheapest path from v to t. It is crucial
to observe that M IN M AX A PPROX only assigns extra cost to an edge (v ′ , ς(v ′ )) of P ′ if v ′ is located on P .
9

Consequently, there is at most one edge with extra cost between any two consecutive intersections of P and
P ′ . Furthermore, this extra cost is equal to the cost of an edge on P ′ between v ′ and the next intersection of
P and P ′ . Therefore, each edge of P ′ can contribute at most once to the total extra cost assigned to P ′ . This
means that the price of P ′ with respect to c̃ is at most twice the price of P ′ with respect to 0̃. Because the
price of P ′ is an upper bound for dc̃ (v), we have shown that dc̃ (v) ≤ 2d0̃ (v).
We proceed to investigate the agent’s walk through G. Our goal is to show that her lowest perceived cost
is at most 2̺ at every node v on her way. This establishes the theorem. Our analysis is based on the following
case distinction: First, assume that v is located on P . The immediate successor of v on P is denoted by w.
Remember that c̃ assigns no extra cost to (v, w). Using the result from the previous paragraph, we get

ζc̃ (v) ≤ ηc̃ (v, w) = c(v, w) + βdc̃ (v, w) ≤ c(v, w) + β2d0̃ (v, w) ≤ 2 c(v, w) + βd0̃ (v, w)
= 2η0̃ (v, w) ≤ 2̺.

The last inequality is valid by definition of ̺.
Secondly, assume that v is not located on P and consider the last node v ′ on P the agent visited before
v. Because she traversed (v ′ , ς(v ′ )) to get to v, we know that ηc̃ (v ′ , ς(v ′ )) ≤ 2̺ and dc̃ (ς(v ′ )) ≤ 2̺/β.
We also know that she faces an extra cost of 3̺/β whenever she tries to leave the ς-path P ′ of v ′ before
the next intersection of P and P ′ . Since she is not willing to pay this much, v must be located on P ′ .
In particular, all paths from ς(v ′ ) to t either visit ς(v) or cross an edge that charges an extra cost of 3̺/β.
Consequently, a cheapest path from ς(v ′ ) to t with respect to c̃ costs at least dc̃ (ς(v ′ )) ≥ min{3̺/β, dc̃ (ς(v))}.
As dc̃ (ς(v ′ )) ≤ 2̺/β, this implies that dc̃ (ς(v ′ )) ≥ dc̃ (ς(v)). Our proof is almost complete. For the final part,
recall that (v, ς(v)) is located on P ′ between v ′ and the next intersection of P and P ′ . By construction of c̃
we have c̃(v ′ , ς(v ′ )) ≥ c(v, ς(v)). Furthermore, (v, ς(v)) has no extra cost. Putting all the pieces together we
get
ζc̃ (v) ≤ ηc̃ (v, ς(v)) = c(v, ς(v)) + βdc̃ (ς(v)) ≤ c̃(v ′ , ς(v ′ )) + βdc̃ (ς(v ′ ))
≤ c(v ′ , ς(v ′ )) + c̃(v ′ , ς(v ′ )) + βdc̃ (ς(v ′ )) = ηc̃ (v ′ , ς(v ′ )) ≤ 2̺.

To complement this result and emphasize the quality our approximation given the theoretical limitations,
we argue that MCC-OPT is NP-hard to approximate within any ratio of 1.08192 or less. In particular, assuming
that P 6= NP this rules out the existence of a polynomial-time approximation scheme.
Theorem 4. MCC-OPT is NP-hard to approximate within a ratio less or equal to 1.08192.
Proof. To establish the theorem, a reduction similar to the one from Theorem 2 can be used. In fact, given a
3-SAT instance I we can construct the corresponding MCC-OPT instance J the same way as in the proof of
Theorem 2. The only difference is that our choice of ε is slightly more restrictive as we require
n
β 2 (1 − β)3 β 2 (1 − β)2 (2 − β) o
.
,
ε < min β(1 − β)3 , β(1 − β)2 (2 − β),
1+β
1+β
The proof can be structured around the following properties of J : (a) If I has a solution, J admits a
motivating cost configuration for a reward of 1/β. (b) If I has no solution, J admits no motivating cost
configuration for a reward of (1 + β(1 − β)4 )/β or less. Consequently, any algorithm that approximates
MCC-OPT within a ratio of 1 + β(1 − β)4 or less must also solve I. To maximize this ratio we choose
β = 1/5 and obtain the desired approximability bound, namely 1 + (1 − 1/5)4 /5 = 1.08192. All that remains
to show is that J indeed satisfies (a) and (b). The correctness of (a) is an immediate consequence of the proof
of Theorem 2. A detailed proof of (b) can be found in the Appendix.

10

6 Conclusion
In this work we have used Kleinberg and Oren’s graph theoretic framework [5] to provide a systematic analysis of penalty-based commitment devices. We have shown that penalty fees are strictly more powerful than
commitment devices based on prohibition. In particular, we have shown that penalties may outperform prohibitions by a factor of up to 1/β. We have also been able to obtain some of the first positive computational
results for the algorithmic design of commitment devices. We have given a polynomial-time algorithm to construct penalty fees that match an optimal solution by a factor of 2. This is significant progress when compared
to prohibition-based commitment devices whose approximation is known to be NP-hard within a factor less
√
than n/3 [2]. Due to their versatility, expressiveness and favorable computational properties, we believe that
penalty-based commitment devices will prove to be a valuable tool for the targeted improvement of complex
social and economic settings in the context of time-inconsistent behavior.

References
[1] George A Akerlof. Procrastination and obedience. The American Economic Review, 81(2):1–19, 1991.
[2] Susanne Albers and Dennis Kraft. Motivating time-inconsistent agents: A computational approach. In
Proceedings of the 12th Conference on Web and Internet Economics, pages 309–323. Springer, 2016.
[3] Gharad Bryan, Dean Karlan, and Scott Nelson. Commitment devices. Annual Review of Economics,
2:671–698, 2010.
[4] Nick Gravin, Nicole Immorlica, Brendan Lucier, and Emmanouil Pountourakis. Procrastination with
variable present bias. In Proceedings of the 17th ACM Conference on Economics and Computation,
pages 361–361, New York, NY, USA, 2016. ACM.
[5] Jon Kleinberg and Sigal Oren. Time-inconsistent planning: A computational problem in behavioral
economics. In Proceedings of the 15th ACM Conference on Economics and Computation, pages 547–
564, New York, NY, USA, 2014. ACM.
[6] Jon Kleinberg, Sigal Oren, and Manish Raghavan. Planning problems for sophisticated agents with
present bias. In Proceedings of the 17th ACM Conference on Economics and Computation, pages 343–
360, New York, NY, USA, 2016. ACM.
[7] David Laibson. Golden eggs and hyperbolic discounting. The Quarterly Journal of Economics, pages
443–477, 1997.
[8] Ted O’Donoghue and Matthew Rabin. Doing it now or later. The American Economic Review, 89:103–
124, 1999.
[9] Ted O’Donoghue and Matthew Rabin. Incentives and self control. Advances in Economics and Econometrics: The 9th World Congress, 2:215–245, 2006.
[10] Pingzhong Tang, Yifeng Teng, Zihe Wang, Shenke Xiao, and Yichong Xu. Computational issues in
time-inconsistent planning. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, 2017.
To appear.

11

A Appendix
Proof of Proposition 1. Let P = v1 , . . . , vm and assume that s = v1 and t = vm . From the description of
PATH A ND F ENCE it should be clear that whenever the algorithm assigns extra cost to an edge (vi , w), the
perceived cost of that edge exceeds the perceived cost of (vi , vi+1 ) by at least βε/(m − 2). Furthermore,
since G is acyclic, the extra cost of (vi , w) does not affect the agent’s perceived cost of any previously processed edge (vj , w′ ) with j ≥ i. We conclude that PATH A ND F ENCE returns a cost configuration c̃ for which
ηc̃ (vi , vi+1 ) < ηc̃ (vi , vi+1 ) + βε/(m − 2) ≤ ηc̃ (vi , w). Consequently, the agent has no incentive to divert
from P .
In the remainder, we bound the perceived cost of each (vi , vi+1 ) by ηc̃ (vi , vi+1 ) ≤ ηc̃∗ (vi , vi+1 ) + βε.
Together with the observations from the previous paragraph, this concludes the proof. Our argument is based
on an induction on P . The main induction hypothesis is ηc̃ (vi , vi+1 ) ≤ ηc̃∗ (vi , vi+1 )+βε(m−1−i)/(m−2).
Clearly, this also implies that ηc̃ (vi , vi+1 ) ≤ ηc̃∗ (vi , vi+1 ) + βε. To simplify matters, we introduce dc̃ (vi ) ≤
dc̃∗ (vi ) + βε(m − 1 − i)/(m − 2) as an auxiliary induction hypothesis.
We start the induction at the last edge of P , i.e. i = m − 1. Our goal is to show that ηc̃ (vm−1 , t) ≤
ηc̃∗ (vm−1 , t) and dc̃ (vm−1 ) ≤ dc̃∗ (vm−1 ). Recall that (vm−1 , t) minimizes the agent’s perceived cost with
respect to c̃. By definition of P we also know that (vm−1 , t) minimizes her perceived cost with respect to c̃∗ .
Consequently, we have ηc̃ (vm−1 , t) = ζc̃ (vm−1 ) and ηc̃∗ (vm−1 , t) = ζc̃∗ (vm−1 ). Since (vm−1 , t) is the last
edge of P , we conclude that
ηc̃ (vm−1 , t) = ζc̃ (vm−1 ) ≤ dc̃ (vm−1 ) ≤ c(vm−1 , t) + c̃(vm−1 , t)
as well as
c(vm−1 , t) + c̃∗ (vm−1 , t) = ηc̃∗ (vm−1 , t) = ζc̃∗ (vm−1 ) ≤ dc̃∗ (vm−1 ).

Moreover, c̃ assigns no extra cost to (vm−1 , t). Therefore, c̃(vm−1 , t) = 0 ≤ c̃∗ (vm−1 , t) holds true. Combining the last three inequalities concludes the basis of our induction.
For the inductive step, assume that ηc̃ (vj , vj+1 ) ≤ ηc̃∗ (vj , vj+1 ) + βε(m − 1 − j)/(m − 2) and dc̃ (vj ) ≤
dc̃∗ (vj ) + βε(m − 1 − j)/(m − 2) are valid for all j such that i < j < m. We proceed to argue that both
of these inequalities are also valid for i. We start with the first inequality. By construction of c̃ we have
c̃(vi , vi+1 ) = 0 ≤ c̃∗ (vi , vi+1 ). Consequently, we can bound the perceived cost of (vi , vi+1 ) by ηc̃ (vi , vi+1 ) ≤
c(vi , vi+1 ) + c̃∗ (vi , vi+1 ) + βdc̃ (vi+1 ). The auxiliary induction hypothesis now implies the desired result

m − 1 − (i + 1) 
ηc̃ (vi , vi+1 ) ≤ c(vi , vi+1 ) + c̃∗ (vi , vi+1 ) + β dc̃∗ (vi+1 ) + βε
m−2
m
−
2
−
i
m−1−i
= ηc̃∗ (vi , vi+1 ) + β 2 ε
≤ ηc̃∗ (vi , vi+1 ) + βε
.
m−2
m−2
The proof of the second inequality, i.e. dc̃ (vi ) ≤ dc̃∗ (vi ) + βε(m − 1 − i)/(m − 2), is a bit more involved.
Let (vi , w) be the initial edge of a cheapest path P ′ from vi to t with respect to c̃∗ . In a first step, we show that
dc̃ (w) ≤ dc̃∗ (w) + βε(m − 2 − i)/(m − 2). For this purpose let vj be the node of smallest index different
from vi that is located at an intersection between P and P ′ . Because P and P ′ both end in t, such a node
must exist. Recall that c̃ only assigns extra cost to edges that leave a node of P . By definition of vj , no edge
in P ′ between w and vj can be such an edge. Let dc̃ (w, vj ) and dc̃∗ (w, vj ) denote the cost of a cheapest path
from w to vj with respect to c̃ and c̃∗ . According to our considerations, dc̃ (w, vj ) ≤ dc̃∗ (w, vj ) holds true. If
vj = t, this immediately implies dc̃ (w) ≤ dc̃∗ (w) + βε(m − 2 − i)/(m − 2). Otherwise, if vj 6= t, we can
apply the auxiliary induction hypothesis to obtain the desired result
dc̃ (w) = dc̃ (w, vj ) + dc̃ (vj ) ≤ dc̃∗ (w, vj ) + dc̃∗ (vj ) + βε
12

m−2−i
m−1−j
≤ dc̃∗ (w) + βε
.
m−2
m−2

Finally, we take a closer look at the initial edge of P ′ . We distinguish between two scenarios. First,
assume that c̃ assigns no extra cost to (vi , w). In this case, we have c̃(vi , w) = 0 ≤ c̃∗ (vi , w). Together with
the inequality from the previous paragraph, this immediately concludes the inductive step
m−2−i
m−2
m
−
1
−
i
m
−
1
−i
≤ c(vi , w) + c̃∗ (vi , w) + dc̃∗ (w) + βε
= dc̃∗ (vi ) + βε
.
m−2
m−2

dc̃ (vi ) ≤ c(vi , w) + c̃(vi , w) + dc̃ (w) ≤ c(vi , w) + c̃∗ (vi , w) + dc̃∗ (w) + βε

Secondly, assume that c̃ assigns positive cost to (vi , w). In this case, the perceived cost of (vi , w) with
respect to c̃ is just slightly greater than that of (vi , vi+1 ). More formally, it holds true that ηc̃ (vi , w) =
ηc̃ (vi , vi+1 ) + βε/(m − 2). This follows from the construction of c̃. Therefore, we can upper bound dc̃ (vi ) by
dc̃ (vi ) ≤ c(vi , w) + c̃(vi , w) + dc̃ (w) = ηc̃ (vi , w) + (1 − β)dc̃ (w)
1
= ηc̃ (vi , vi+1 ) + βε
+ (1 − β)dc̃ (w).
m−2
Recall that ηc̃ (vi , vi+1 ) ≤ ηc̃∗ (vi , vi+1 ) + β 2 ε(m − 2 − i)/(m − 2). In combination with our upper bound on
dc̃ (w), we obtain

1
m − 2 − i
m−2−i
+ βε
+ (1 − β) dc̃∗ (w) + βε
m−2
m−2
m−2
m−1−i
βε.
= ηc̃∗ (vi , vi+1 ) + (1 − β)dc̃∗ (w) +
m−2

dc̃ (vi ) ≤ ηc̃∗ (vi , vi+1 ) + β 2 ε

Because (vi , vi+1 ) minimizes the perceived cost at vi with respect to c̃∗ , we may assume that ηc̃∗ (vi , vi+1 ) ≤
ηc̃∗ (vi , w) and obtain
dc̃ (vi ) ≤ ηc̃∗ (vi , w) + (1 − β)dc̃∗ (w) +

m−1−i
m−1−i
βε = dc̃∗ (vi ) +
βε.
m−2
m−2

Proof of Theorem 2 (continued). It remains to show that I has a satisfying variable assignment if and only
if J has a cost configuration c̃ that is motivating for a reward of 1/β. (⇒) We start by constructing c̃ from
an assignment of truth values τ : {x1 , . . . , xm } → {T, F } that satisfies each clause of I. For this purpose
we assign an extra cost of (1 − β)2 to the first edge of all shortcuts that start at variable nodes wk,τ (xk ) .
Furthermore, we assign an extra cost of 1 to all forward edges ending in a variable node of the from wk,τ (x̄k ) .
To show that c̃ is indeed motivating, we divide the agent’s walk into two separate parts.
The first part contains the literal nodes from s to u2 . When located at a specific node vi,j , the agent has
two options: either she takes the shortcut or she follows a forward edge. In the first case, she ends up at a
variable node. By construction of G, the cost of a cheapest path from any variable node to t is at least 2 − β.
This holds true regardless of extra cost. As a result, her perceived cost for taking the shortcut at vi,j is at least
(1 − β)2 + β(2 − β) = 1. Her other option is to take a forward edge. Assuming that i < ℓ, let j ′ be the
index of a literal in ci+1 that evaluates to true with respect to τ . Because τ is a satisfying variable assignment,
such a literal must exist. The agent’s perceived cost for traversing (vi,j , vi+1,j ′ ) and then taking the two direct
shortcuts to t is (1 − β)3 − ε + β((1 − β)2 + (2 − β)) = 1 − ε. In the special case that i = ℓ we obtain the
same perceived cost along the path vℓ,j , u1 , u2 , t. Consequently, the agent always prefers at least one forward
edge to the current shortcut. A similar argument shows that there is one forward edge with a perceived cost of
1 − ε out of s. Furthermore, there are no immediate shortcuts at s. Finally, when located at u1 , the agent has
no choice but to traverse (u1 , u2 ). At this point her perceived cost of the path u1 , u2 , t is 1. Considering that
her perceived value of the reward is 1, we conclude that she follows the forward edges until she successfully
completes the first part of her walk.
13

The second part of the agent’s walk contains the variable nodes from u2 to t. At u2 the agent has three
options. First, she can follow the shortcut of type two. This has a cost of 2 − β and is clearly not motivating.
Secondly, she can traverse the forward edge to w1,τ (x̄1 ) . By construction of c̃, this edge has a cost greater than
1. Again, this is not motivating. Thirdly, she can traverse the forward edge to w1,τ (x1 ) . If the she plans to take
the shortcut to t immediately afterwards, the perceived cost is (1 − β)3 − ε + β((1 − β)2 + (2 − β)) = 1 − ε.
Therefore, this is her preferred choice. Because it is also a motivating choice, she moves to w1,τ (x1 ) where
she faces the same three options. The only difference is that this time the first option is a shortcut is of the
third type and has a perceived cost of (1 − β)2 + β(2 − β) = 1. Repeating the argument shows that the agent
travels from one variable node wk,τ (xk ) to the next wk+1,τ (xk+1 ) until she gets to u3 . At this point the only
path to t is along the nodes u3 , u4 and u5 . Since the agent’s lowest perceived cost at all three nodes is 1, she
remains motivated and eventually reaches t. We conclude that c̃ is motivating.
(⇐) Next, assume that J has a solution, i.e. there exists a cost configuration c̃ that is motivating for a
reward of 1/β. We proceed to show how to obtain a variable assignment τ that satisfies each clause of I. For
this purpose we make the following two observations: First, no motivating cost configuration can guide the
agent onto a shortcut of type two or three. This is because these shortcuts have an edge of cost (2 − β) > 1
and are too expensive to traverse for the given reward. Secondly, the agent cannot enter a shortcut of the first
type either. To understand this, assume for a moment that she does take such a shortcut. The shortcut takes
her from some literal node vi,j to a variable node wk,y . Her perceived cost of (vi,j , wk,y ) can be at most 1,
otherwise the shortcut would not be motivating. By construction of G there is exactly one cheapest path from
wk,y to t, namely the direct shortcut to t. As the total cost of this shortcut is 2 − β, the only way to achieve
a perceived cost of 1 for (vi,j , wk,y ) is along this very shortcut. In particular, no extra cost can be assigned to
this shortcut. However, once the agent has reached wk,y , her perceived cost for taking the direct shortcut to t
is β(2 − β) as no extra cost is placed on this path. Conversely, her perceived cost of any forward edge at wk,y
is at least 1 − ε, even if we neglect extra cost. By choice of ε, it holds true that

(1 − ε) − β(2 − β) > 1 − (1 − β)2 − β(2 − β) = 0.
Consequently, the agent prefers the shortcut to any of the forward edges. This contradicts our previous observation that she does not take shortcuts of type three.
Because no motivating cost configuration can guide the agent onto a shortcut, we conclude that her walk
from s to t must contain exactly one literal node vi,j and one variable node wk,y for each clause and variable
of I. Let P be one of possibly several paths the agent can walk from s to t. Based on P , we construct a
suitable variable assignment τ as follows: If she visits wk,T along P , we set τ (xk ) = T . Otherwise, if she
visits wk,F , we set τ (xk ) = F . To conclude the proof, we argue that τ satisfies all clauses of I.
Consider an arbitrary clause ci and let vi,j be the corresponding literal node in P . Furthermore, let vi−1,j ′
be the literal node preceding vi,j in P . If i = 1, let vi−1,j ′ = s. We denote the agent’s planned path to t
when located at vi−1,j ′ by P ′ . Clearly, the first edge of P ′ must be (vi−1,j ′ , vi,j ) as this edge is also on P .
For the next edge of P ′ we have two options: The first is another forward edge. As a result, there must be
some additional edge of cost (1 − β)2 in P ′ . This can either be a subsequent shortcut of type one or (u1 , u2 ).
Moreover, P ′ must include the edges (u4 , u5 ) and (u5 , t) or a shortcut of type two or three. In all cases, the
total cost of these edges is at least (1 − β)2 + (2 − β). Therefore, the agent’s perceived cost of the first option
sums up to a value greater or equal to

 β(1 − β)3

− ε > 1.
(1 − β)3 − ε + β (1 − β)3 − ε + (1 − β)2 + (2 − β) = 1 + (1 + β)
1+β
The inequality is valid by choice of ε. Clearly, this is not motivating. The second option is that the next edge
of P ′ is the shortcut from vi,j to the corresponding variable node wk,y . Again, we can distinguish between
two cases. First, P ′ might include a forward edge from wk,y to a subsequent variable node wk+1,y′ , or to
14

u5 if k = m. However, similar calculations to the one above indicate that this is not motivating. The only
remaining option is that P ′ contains the shortcut from wk,y to t. In this case, the perceived cost of P ′ is at
least 1 − ε. This leaves an extra cost of at most ε/β to place onto the shortcut from wk,y to t.
Now assume that P includes wk,y , i.e. the agent visits wk,y at a later point. Recall that her perceived cost
for taking a forward edge at wk,y is at least 1 − ε. By choice of ε, an extra cost of ε/β is not sufficient to
prevent her from entering the shortcut at wk,y as
(1 − ε) −

 1 + β  β(1 − β)2

+ β(2 − β) =
− ε > 0.
β
β
1+β

ε

Of course, this contradicts the fact that the agent cannot take shortcuts. Consequently, the agent cannot visit
wk,y but must visit wk,ȳ instead. By construction of G, this implies that τ satisfies the j-th literal of ci .
Because this holds true for all clauses of I, τ must be a satisfying variable assignment.
Proof of Theorem 4 (continued). In the following, we prove that J satisfies (b). For the sake of contradiction
assume that there exists a cost configuration c̃ that is motivating for a reward of at most (1 + β(1 − β)4 )/β,
but I has no solution. Let P be a path that corresponds to the agent’s walk from s to t.
Similar to the proof of Theorem 2 we first argue that P cannot include shortcuts. Recall that shortcuts
of the second and third type have an edge of cost 2 − β. However, the agent’s perceived reward is at most
1 + β(1 − β)4 . Because 2 − β = 1 + (1 − β) > 1 + β(1 − β)4 , she has no incentive to traverse such an
edge. It remains to show that she does not take a shortcut of the first type either. For this purpose assume she
travels from a literal node vi,j to some variable node wk,y via a shortcut of type one. Let P ′ be her planned
path when located at vi,j . We distinguish between two scenarios. First, P ′ might include a forward edge after
(vi,j , wk,y ). Even if we neglect extra cost, her perceived cost of P is at least


(1 − β)2 + β (1 − β)3 − ε + (2 − β) > (1 − β)2 + β (1 − β)3 − β(1 − b)3 + (2 − β)
= 1 + β(1 − β)4 .

The inequality is valid by choice of ε. Because her perceived cost of P ′ exceeds her perceived reward, this
scenario is not possible. Secondly, P ′ might contain the shortcut from wk,y to t. In this case, the agent’s
perceived cost of P ′ is at least 1. Consequently, c̃ may assign an extra cost of no more than (β(1 − β)4 )/β =
(1 − β)4 to the edges of P ′ . This holds particularly true for edges of the shortcut from wk,y to t. Therefore,
her perceived cost for taking the shortcut at wk,y is at most (1 − β)4 + β(2 − β). Conversely, even without
extra cost, her cost for taking a forward edge at wk,y is at least 1 − ε. By choice of ε, she prefers the shortcut
1 − ε > 1 − β(1 − β)2 (2 − β) = (1 − β)4 + β(2 − β).
This contradicts the fact that she does not enter a shortcut of type three.
Because c̃ does not guide the agent onto a shortcut, we conclude that P must contain exactly one literal
node vi,j and one variable node wk,y for each clause and each variable of I. Similar to the proof of Theorem 2
we use P to construct a variable assignment τ in the following way: If the agent visits wk,T along P , we set
τ (xk ) = T . Otherwise, if she visits wk,F , we set τ (xk ) = F . To conclude the proof we argue that τ satisfies
all clauses of I. This is a contradiction to our initial assumption that I has no solution.
Consider an arbitrary clause ci and let vi,j be the corresponding literal node in P . Furthermore, let vi−1,j ′
be the literal node that precedes vi,j in P . If i = 1, let vi−1,j ′ = s. The agent’s planned path from vi−1,j ′
to t is denoted by P ′ . Clearly, the first edge of P ′ must be (vi−1,j ′ , vi,j ). In the next step two directions are
possible. The first one is another forward edge. As argued in the proof of Theorem 2 the perceived cost of P ′
is at least

(1 − β)3 − ε + β (1 − β)3 − ε + (1 − β)2 + (2 − β) = 1 + β(1 − β)3 − (1 + β)ε.
15

By choice of ε, this is not motivating
1 + β(1 − β)3 − (1 + β)ε > 1 + β(1 − β)3 − (1 + β)

β 2 (1 − β)3
= 1 + β(1 − β)4 .
1+β

The second direction is along the shortcut from vi,j to some variable node wk,y . Again, we can distinguish
between two cases. First, P ′ might contain a forward edge from wk,y to some variable node wk+1,y′ or u5
if k = m. However, a calculation similar to the one above indicates that this is not motivating. The only
remaining possibility is that P ′ also contains the shortcut from wk,y to t. In this case, the perceived cost of P ′
is at least 1 − ε. This leaves an extra cost of no more than (ε + β(1 − β)4 )/β = ε/β + (1 − β)4 to place onto
the shortcut from wk,y to t.
Now assume that P also includes wk,y . The agent’s perceived cost for taking a forward edge from wk,y is
at least 1 − ε. By choice of ε, we conclude that an extra cost of ε/β + (1 − β)4 is not sufficient to prevent the
agent from entering the shortcut as
(1 − ε) −

 1 + β  β 2 (1 − β)2 (2 − β)

+ (1 − β)4 + β(2 − β) =
− ε > 0.
β
β
1+β

ε

Of course, this contradicts the fact that the agent cannot take shortcuts. Consequently, the agent cannot visit
wk,y but must visit wk,ȳ instead. By construction of G, this implies that τ satisfies the j-th literal of clause ci .
Because this holds true for all clauses of I, τ must be a satisfying variable assignment.

16

