The Price of Uncertainty in Present-Biased Planning
Susanne Albers Dennis Kraft



1]Susanne Albers
1]Dennis Kraft
[1]Department of Computer Science, Technical University of Munich
[ ]{albers, kraftd}@in.tum.de

The Price of Uncertainty in Present-Biased PlanningWork supported by the European Research Council, Grant Agreement No. 691672.
    [
    
===============================================================================================================================








The tendency to overestimate immediate utility is a common cognitive bias.
As a result people behave inconsistently over time and fail to reach long-term goals.
Behavioral economics tries to help affected individuals by implementing external incentives.
However, designing robust incentives is often difficult due to imperfect knowledge of the parameter β∈ (0,1] quantifying a person's present bias.
Using the graphical model of Kleinberg and Oren <cit.>, we approach this problem from an algorithmic perspective.
Based on the assumption that the only information about β is its membership in some set B ⊂ (0,1], we distinguish between two models of uncertainty: one in which β is fixed and one in which it varies over time.
As our main result we show that the conceptual loss of efficiency incurred by incentives in the form of penalty fees is at most 2 in the former and 1 + max B/min B in the latter model.
We also give asymptotically matching lower bounds and approximation algorithms.







§ INTRODUCTION



Many goals in life such as losing weight, passing an exam or paying off a loan require long-term planning.
But while some people stick to their plans, others lack self-control; they eat unhealthy food, delay their studies and take out new loans.
In behavioral economics the tendency to change a plan for no apparent reason is known as time-inconsistent behavior.
The questions are, what causes these inconsistencies and why do they affect some more than others?
A common explanation is that people make present biased decisions, i.e., they assign disproportionately greater value to the present than to the future.
In this simplifying model a person's behavior is the mere result of her present bias and the setting in which she is placed.
However, the interplay between these two factors is intricate and sometimes counter-intuitive as the following example demonstrates:

Consider two runners Alice and Bob who have two weeks to prepare for an important race.
Each week they must choose between two types of workout.
Type A always incurs an effort of 1, whereas type B incurs an effort of 3 in the first and 9 in the second week.
Since A offers less preparation than B, Alice and Bob's effort in the final race is 13 if they consistently choose A and 1 if they consistently choose B.
Furthermore, A and B are incompatible in the sense that switching between the two will result in an effort of 16 in the final race.
Figure <ref> models this setting as a directed acyclic graph G with terminal nodes s and t.
The intermediate nodes v_X and v_XY represent a person's state after completing the workouts X,Y ∈{A,B}.
To move forward with the training, Alice and Bob must perform the tasks associated with the edges of G, i.e., complete workouts and run the race.
Looking at G it becomes clear that two consecutive workouts of type B are the most efficient routine in the long run.
However, this is not necessarily the routine a present biased person will choose.

For instance, assume that Alice and Bob discount future costs by a factor of a = 1/2 - ε and b = 1/2 + ε respectively.
We call a and b their present bias.
At the beginning of the first week Alice and Bob compare different workout routines.
From Alice's perspective two workouts of type A are strictly more preferable to two workouts of type B as she anticipates an effort of 1 + a(1 + 13) = 8 - 14ε for the former and 3 + a(9 + 1) = 8 - 10ε for the latter.
A similar calculation for Bob shows that he prefers two workouts of type B.
Considering that neither Alice nor Bob finds a mix of A and B particularly interesting at this point, we conclude that Alice chooses A in the first week and Bob B.
However, come next week, Bob expects an effort of 1 + b16 = 8 + 16ε for A and 9 + b = 19/2 + ε for B. 
Assuming ε is small enough, A suddenly becomes Bob's preferred option and he switches routines.
Alice on the other hand has no reason to change her mind and sticks to A.
As a result she pays much less than Bob during practice and in the final race.
This is remarkable considering that her present bias is only marginally different from Bob's.
Moreover, it seems surprising that only Bob behaves inconsistently, although he is less biased than Alice.





 §.§ Related Work

Traditional economics and game theory are based on the assumption that people maximize their utility in a rational way.
But despite their prevalence, these assumptions disregard psychological aspects of human decision making observed in empirical and experimental research <cit.>.
For instance, time-inconsistent behavior such as procrastination seems paradox in the light of traditional economics.
Nevertheless, it can be explained readily by a tendency to overestimate immediate utility in long-term planning, see e.g. <cit.>.
By studying such cognitive biases, behavioral economics tries to obtain more realistic economic models.

A significant amount of research in this field has been devoted to temporal discounting in general and quasi-hyperbolic discounting in particular, see <cit.> for a survey.
The quasi-hyperbolic discounting model proposed by Laibson <cit.> is characterized by two parameters: the present bias β∈ (0,1] and the exponential discount rate δ∈ (0,1].
People who plan according to this model have an accurate perception of the present, but scale down any costs and rewards realized t ≥ 1 time units in the future by a factor of βδ^t.
To keep our work clearly delineated in scope, we adopt Akerlof's model of quasi-hyperbolic discounting <cit.> and make the following two assumptions:
First, we focus on the present bias β and set the exponential discount rate to δ = 1.
Secondly, we assume people to be naive in the sense that they are unaware of their present bias and only optimize their current perceived utility when making a decision.
Note that Alice and Bob from the previous example behave like agents in Akerlof's model for a present bias of β = 1/2 - ε and β = 1/2 + ε respectively.

Until recently the economic literature lacked a unifying and expressive framework for analyzing time-inconsistent behavior in complex social and economic settings.
Kleinberg and Oren closed this gap by modeling the behavior of naively present biased individuals as a planning problem in task graphs like the one depicted in Figure <ref> <cit.>.
We introduce this framework formally in Section <ref>.
As a result of Kleinberg and Oren's work, an active line of research at the intersection of computer science and behavioral economics has emerged.
For instance, the graphical model has been used to systematically analyze different types of quasi-hyperbolic discounting agents such as sophisticated agents who are fully or partially aware of their present bias <cit.> and agents whose present bias varies randomly over time <cit.>.
Furthermore, the graphical model was used to shed light on the interplay between temporal biases and other types of cognitive biases <cit.>.

The graphical model is of particular interest to us as it provides a natural framework for a design problem frequently encountered in behavioral economics.
Given a certain social or economic setting, the problem is to improve a time-inconsistent person's performance via various sorts of incentives, such as  monetary rewards, deadlines or penalty fees, see e.g. <cit.>.
Using the graphical model, Kleinberg and Oren demonstrate how a strategic choice reduction can incentivize people to reach predefined goals <cit.>.
To implement their incentives, they simply remove the corresponding edges from the task graph.
However, there is a computational drawback to this approach.
As we have shown in previous work, an optimal set of edges to remove from a task graph with n nodes is NP-hard to approximate within a factor less than √(n)/3 <cit.>.
A more general form of incentives avoiding these harsh complexity theoretic limitations are penalty fees. 
In the graphical model penalty fees are at least as powerful as choice reduction and admit a polynomial time 2-approximation <cit.>.



 §.§ Incentive Design for an Uncertain Present Bias

Frederick, Loewenstein and O'Donoghue have surveyed several attempts to estimate people's temporal discount functions <cit.>.
But as estimates differ widely across studies and individuals, the difficulty of predicting a person's temporal discount function becomes apparent.
Clearly, this poses a serious challenge for the design of reliable incentives.
After all, Alice and Bob's scenario demonstrates how arbitrarily small changes in the present bias can cause significant changes in a person's behavior.
In this work we address the effects of incomplete information about a person's present bias in two different notions of uncertainty.

In Section <ref> we consider naive individuals whose exponential discount rate is δ = 1, but whose present bias β is unknown.
The only prior information we have about β is its membership in some larger set B.
Our goal is to construct incentives that are robust with respect to the uncertainty induced by B.
More precisely, we are interested in incentives that work well for any present bias contained in B.
An alternative perspective is that we try to construct incentives which are not limited to a single person, but serve an entire population of individuals with different present bias values.
A simple instance of this problem in which a single task must be partitioned and stretched over a longer period of time has been studied by Kleinberg and Oren <cit.>.
But like most research on incentivizing heterogeneous populations, see e.g. <cit.>, Kleinberg and Oren's results are restricted to a very specific setting.
They themselves suggest the design of more general incentives as a major research direction for the graphical framework <cit.>.

Using penalty fees as our incentive of choice and a fixed reward to keep people motivated, we present the first results in this area.
Our contribution is twofold.
On the one hand, we try to quantify the conceptual loss of efficiency caused by incomplete knowledge of β.
For this purpose we introduce a novel concept called price of uncertainty, which denotes the smallest ratio between the reward required by an incentive that accommodates all β∈ B and the reward required by an incentive designed for a specific β∈ B.
We present an elegant algorithmic argument to prove that the price of uncertainty is at most 2.
Remarkably, this bound holds true independent of the underlying graph G and present bias set B.
To complement our result, we construct a family of graphs G and present bias sets B for which the price of uncertainty converges to a value strictly greater than 1.
On the other hand, we consider the computational problem of constructing penalty fees that work for all β∈ B, but require as little reward as possible.
Drawing on the same algorithmic ideas we used to bound the price of uncertainty yields a polynomial time 2-approximation.
Furthermore, we present a non-trivial proof to show that the decision version of the problem is contained in NP.
Since all hardness results of <cit.> also apply under uncertainty, we know that there is no 1.08192-approximation unless P = NP.



 §.§ Incentive Design for a Variable Present Bias

In Section <ref> we generalize our notion of uncertainty to individuals whose present bias β may change arbitrarily over time within the set B.
This model is inspired by work of Gravin et al. <cit.>, except that we do not rely on the assumption that β is drawn independently from a fixed probability distribution.
Instead, our goal is to design penalty fees that work well for all possible sequences of β over time.
We believe this to be an interesting extension of the fixed parameter case as the variability of β may capture changes in a person's temporal discount function caused by unforeseen cognitive biases different from her present bias. 
As a result we obtain more robust penalty fees.

Again, our contribution is twofold.
On the one hand, we introduce the price of variability to quantify the conceptual loss of efficiency caused by unpredictable changes in β.
Similar to the price of uncertainty, we define this quantity to be the smallest ratio between the reward required by an incentive that accommodates all possible changes of β∈ B over time and the reward required by an incentive designed for a specific and fixed β∈ B.
However, unlike the price of uncertainty, the price of variability has no constant upper bound.
Instead, the ratio seems closely related to the range τ = maxB/minB of the set B.
By generalizing our algorithm from Section <ref> we obtain an upper bound of 1 + τ for the price of variability.
To complement this result, we construct a family of graphs G for which the price of variability converges to τ/2.
On the other hand, we consider the computational aspects of constructing penalty fees for a variable β.
As a result of the unbounded price of variability, we are not able to come up with a constant polynomial time approximation.
Instead, we obtain a (1 + τ)-approximation.
However, by using a sophisticated reduction from VECTOR SCHEDULING, we prove that no efficient constant approximation is possible unless NP = ZPP.
We conclude our work by studying a curious special case of variability in which individuals may temporarily lose their present bias.
For this scenario, which is characterized by the assumption that 1 ∈ B, optimal penalty fees can be computed in polynomial time.






§ THE MODEL



In the following we introduce Kleinberg and Oren's graphical framework <cit.>.
Let G =(V,E) be a directed acyclic graph with n nodes that models some long-term project.
The start and end states are denoted by the terminal nodes s and t.
Furthermore, each edge e of G corresponds to a specific task whose inured effort is captured by a non-negative cost c(e).
To finish the project, a present biased agent must sequentially complete all tasks along a path from s to t.
However, instead of following a fixed path, the agent constructs her path dynamically according to the following simple procedure: 

When located at any node v different from t, the agent tries to evaluate the minimum cost she needs to pay in order to reach t.
For this purpose she considers all outgoing edges (v,w) of her current position v.
Because the tasks associated with these edges must be performed immediately, the agent assesses their cost correctly.
In contrast, all future tasks, i.e., tasks on a path from v to t not incident to v, are discounted by her present bias of β∈ (0,1].
As a result, we define her perceived cost for taking (v,w) to be d_β(v,w) = c(v,w) + β d(w), where d(w) denotes the cost of a cheapest path from w to t.
Furthermore, we define d_β(v) = min{c(v,w) + β d(w) | (v,w) ∈ E} to be the agent's minimum perceived cost at v.
Since the agent is oblivious to her own present bias, she only traverses edges (v,w) for which d_β(v,w) = d_β(v).
Ties are broken arbitrarily.
Once the agent reaches the next node, she reiterates this process.

To motivate the agent, a non-negative reward r is placed at t.
Because the agent must reach t before she can collect r, her perceived reward for reaching t is β r at each node different from t.
When located at v ≠ t, the agent is only motivated to proceed if d_β(v) ≤β r.
Otherwise, if d_β(v) > β r, she quits.
We say that G is motivating, if she does not quit while constructing her path from s to t.
Note that sometimes the agent can construct more than one path from s to t due to ties in the perceived cost of incident edges.
In this case, G is considered motivating if she does not quit on any such path.

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 because the agent can only visit nodes reachable from s.
Furthermore, she is not willing to enter nodes that do not lead to the reward at t.
Consequently, only nodes that are on a path from s to t are relevant to her behavior.
All nodes not satisfying this property can be removed from G in a simple preprocessing step.



 §.§ Alice and Bob's Scenario


To illustrate the model, we revisit Alice and Bob's scenario.
The task graph G is depicted in Figure <ref>.
Remember that a = 1/2 - ε and b = 1/2 + ε denote Alice and Bob's respective present bias.
For convenience let 0 < ε≤ 1/54.
Furthermore, assume that a reward of r = 27 is awarded upon reaching t.

We proceed to analyze Alice and Bob's walk through G.
At their initial position s they must decide whether they move to v_A or v_B.
For this purpose they try to find a path that minimizes the perceived cost.
As the more present biased person, Alice's favorite path is s,v_A,v_AA,t with a perceived cost of d_a(s) = d_a(s,v_A) = 8 - 14ε.
By choice of ε this cost is covered by her perceived reward ar = 27/2 - 27ε.
Consequently, she is motivated to traverse the first edge and moves to v_A.
A similar argument shows that Bob moves to v_B.
Once they reach their new nodes, Alice and Bob reevaluate plans.
From Alice's perspective v_A,v_AA,t is still the cheapest path to t.
Bob, however, suddenly prefers v_B,v_AB,t to his original plan.
Nevertheless, both of their perceived cost remains covered by their perceived reward and they move to v_AA and v_AB respectively.
At this point the only option is to take the direct edge to t.
For Alice the perceived cost at v_AA is sufficiently small to let her reach t.
In contrast, Bob's perceived cost of d_b(v_AB) = 16 exceeds his perceived reward of br = 27/2 + 27ε and he quits.



 §.§ Cost Configurations


Bob's behavior in the previous example demonstrates how present biased decisions can deter people from reaching predefined goals.
To ensure an agent's success it is therefore sometimes necessary to implement external incentives such as penalty fees.
In the graphical model, penalty fees allow us to arbitrarily raise the cost of edges in G.
More formally, let c̃ be a so called cost configuration, which assigns a non-negative extra cost c̃(e) to all edges e of G.
The result is a new task graph G_c̃, whose edges e have a cost of c(e) + c̃(e).
A present biased agent navigates through G_c̃ according to the same rules applying in G.
We say that c̃ is motivating if and only if G_c̃ is.
To avoid ambiguity we annotate our notation whenever we consider a specific c̃, e.g., we write d_c̃ and d_β,c̃ instead of d and d_β.

We conclude this section with a brief demonstration of the positive effects penalty fees can have in Alice and Bob's scenario.
Let c̃ be a cost configuration that assigns an extra cost of c̃(v_B,v_AB) = 1/2 to (v_B,v_AB) and c̃(e) = 0 to all other edges e ≠ (v_B,v_AB).
Note that G and G_c̃ are identical task graphs except for the cost of (v_B,v_AB).
Because Alice does not plan to take (v_B,v_AB) on her way through G and has even less reason to do so in G_c̃, we know that c̃ does not affect her behavior.
For similar reasons, c̃ does not affect Bob's choice to move to v_B.
However, once Bob has reached v_B his perceived cost of the path v_B,v_AB,t is d_b,c̃(v_B, v_AB) = 19/2 + 16ε, whereas his perceived cost of v_B,v_BB,t is only d_b,c̃(v_B, v_BB) = 19/2 + ε.
Since the latter option appears to be cheaper and is covered by his perceived reward, Bob proceeds to v_BB and then onward to t.
As a result c̃ yields a task graph that is motivating for Alice and Bob alike.
This is a considerable improvement to the original task graph.






§ UNCERTAIN PRESENT BIAS



In this section we consider agents whose present bias β is uncertain in the sense that our only information about β is its membership in some set B ⊂ (0,1].
We call B the present bias set.
For technical reasons we assume that B can be expressed as the union of constantly many closed subintervals from the set (0,1].
This way the intersection of B with a closed interval is either empty or contains an efficiently computable minimal and maximal element.
To measure the degree of uncertainty induced by B, we define the range of B as τ = maxB/minB.



 §.§ A Decision Problem


Our goal is to construct a cost configuration c̃ that is motivating for all β∈ B, but requires as little reward as possible. 
To assess the complexity of this task, let UNCERTAIN PRESENT BIAS (UPB) be the following decision problem:

	Given a task graph G, present bias set B and reward r > 0, decide whether a cost configuration c̃ motivating for all β∈ B exists.

If τ = 1, i.e., B only contains a single present bias parameter, UPB is identical to the decision problem MOTIVATING COST CONFIGURATION (MCC) studied in <cit.>.
Since MCC is NP-complete, UPB must be NP-hard.
But unlike MCC it is not immediately clear if UPB is also contained in NP.
The reason is that proving MCC∈ NP only requires to verify whether a given cost configuration is motivating for a single value of β; a property that can be checked in polynomial time <cit.>.
However, proving UPB∈ NP requires to verify whether a given cost configuration is motivating for all β∈ B.
Taking into account that B may very well be an infinite set, it becomes clear that we cannot check all values of β individually.
Interestingly, we do not have to; checking a finite subset B' ⊆ B of size 𝒪(n^2) turns out to be sufficient.


	For any task graph G, reward r and present bias set B a finite subset B' ⊆ B of size 𝒪(n^2) exists such that G is motivating for all β∈ B if it is motivating for all β∈ B'.



	Our proof consists of two steps. 
	First, we determine for what β∈ [0,1] the preference profile p_β(v) = {(v,w') | d_β(v,w') = d_β(v)}, i.e., the set of edges an agent with present bias β is inclined to traverse, contains a given edge (v,w).
	Let B_v,w be the set of all β satisfying this property.
	More formally we define B_v,w as the intersection {β| (v,w) ∈ p_β(v)}∩ [0,1]. 
	As we are going to show, B_v,w is a closed, possibly empty, subinterval of [0,1]. 
	For the second step we define B' to be the set {min(B_e ∩ B) | B_e ∩ B ≠∅}.
	Note that by our assumption on B the minimum of B_e ∩ B is guaranteed to exist as long as B_e ∩ B ≠∅. 
	Furthermore, B' contains at most |E| elements and therefore has a size of 𝒪(n^2). 
	Using a proof by contradiction, we argue that G is motivating for all β∈ B if it is motivating for all β∈ B'.
	This completes the proof.
	
	To see that B_v,w is a closed subinterval of [0,1], it is instructive to observe how the perceived cost of (v,w) changes with respect to β.
	For this purpose, let ℓ_v,w(β) = c(v,w) + β d(w) denote the perceived cost d_β(v,w) with respect to β.
	Clearly, the function ℓ_v,w is linear and so are the functions ℓ_v,w' associated with the incident edges of (v,w).
	Together, these functions yield the line arrangement L_v = {ℓ_v,w'| (v,w') ∈ E}.
	By definition of the agent's preference profile, p_β(v) contains (v,w) if and only if d_β(v,w) ≤ d_β(v,w') for all (v,w') ∈ E.
	The values of β∈ [0,1] that satisfy this property are exactly those for which the line ℓ_v,w is on the lower envelope of the line arrangement L_v.
	From the basic structure of line arrangements such as L_v we can immediately conclude that B_v,w must be a closed subinterval of [0,1], see e.g. <cit.>.

	To conclude the proof it remains to show that G is motivating for each β∈ B if it is motivating for each β∈ B'.
	For the sake of contradiction assume that G is motivating for each β∈ B' but not for some b ∈ B.
	As a result there must exist a path P from s to t along which an agent with present bias b may walk and which contains an edge (v,w) such that d_b(v,w)/b > r.
	Let B_P = ⋂_e ∈ P B_e be the set of all present bias parameters for which agents can construct P.
	From this definition it is immediately apparent that b is contained B_P and therefore B_P ∩ B ≠∅.
	We now consider the structure of B_P.
	Since each set B_e associated with an e ∈ P is a closed interval, so is B_P.
	In particular, as B_P ∩ B is not empty, one of these sets B_e must satisfy min(B_e∩ B) = min(B_P ∩ B).
	Let a = min(B_e∩ B) denote the corresponding present bias value.
	By definition of a it holds true that a ∈ B' and a ≤ b.
	Moreover, because a ∈ B_P, we know that an agent with present bias a may very well construct the path P.
	However, once this agent reaches (v,w), her perceived cost exceeds her perceived reward as
	
    d_a(v,w)/a = c(v,w)/a + d(w) ≥c(v,w)/b + d(w) = d_b(v,w)/b > r.

	Consequently, G is not motivating for a.
	However, this is a contradiction to the assumption that G is motivating for all β∈ B'.


Note that the proof of Proposition <ref> does not only imply that B' exists, but also that it can be constructed in polynomial time.
We may therefore conclude that UPB is indeed contained in NP.


	UPB is NP-complete.




 §.§ The Price of Uncertainty


Since UPB is NP-complete, it makes sense to consider the corresponding optimization problem UPB-OPT.
For this purpose, let r(G,B) be the infimum over all rewards admitting a cost configuration motivating for all β∈ B and define:

	Given a task graph G and present bias set B, determine r(G,B).

Clearly, UPB-OPT must be at least as hard as the optimization version of MCC.
Consequently, we know that UPB has no PTAS and is NP-hard to approximate within a ratio less than 1.08192 <cit.>.
But does the transition from a certain to an uncertain β reduce approximability?

Setting complexity theoretic considerations aside for a moment, an even more general question arises:
How does the transition from a certain to an uncertain β affect the efficiency of cost configurations assuming unlimited computational resources?
To quantify this conceptual difference in efficiency, we look at the smallest ratio between optimal cost configurations motivating for all β∈ B and optimal cost configurations motivating for a specific β∈ B.
We call this ratio the price of uncertainty.

	Given a task graph G and a present bias set B, the price of uncertainty is defined as r(G,B)/sup{r(G,{β}) |β∈ B}.


Let us illustrate the price of uncertainty by going back to Alice and Bob's scenario and assume that B = {a,b} with a = 1/2 - ε and 1/2 + ε.
In other words, the agent either behaves like Alice or she behaves like Bob, but we do not know which.
It is easy to see that in either case the agent minimizes her maximum perceived cost on the way from s to t by taking the path P = s,v_B,v_BB,t.
This minmax cost, which is either d_a(v_B, v_BB) = 19/2 - ε or d_b(v_B, v_BB) = 19/2 + ε, provides two lower bounds for the necessary reward when divided by the respective present bias.
More formally, it holds true that r(G,{a}) ≥ (19/2 - ε)/(1/2 - ε) and r(G,{b}) ≥ (19/2 + ε)/(1/2 + ε).
However, as we have seen in Section <ref>, neither Alice nor Bob are willing to follow P without external incentives.
To discourage the agent from leaving P, we assign an extra cost of c̃(s,v_A) = 5ε to (s,v_A), c̃(v_B,v_AB) = 1/2 + 16ε to (v_B,v_AB) and c̃(e) = 0 otherwise.
This extra cost does not affect the agent's maximum perceived cost along P, which she still experiences at (v_B,v_BB).
As a result, our bounds for r(G,{a}) and r(G,{b}) are tight and we get sup{r(G,{β}) |β∈ B} = r(G,{a}).
Moreover, because we have used the same cost configuration c̃ to derive r(G,{a}) and r(G,{b}), it must hold true that r(G,B) = sup{r(G,{β}) |β∈ B}, implying that the price of uncertainty in Alice and Bob's scenario is 1.



 §.§ Bounding the Price of Uncertainty


As Alice and Bob's scenario demonstrates, cost configurations designed for an uncertain β are not necessarily less efficient than those designed for a specific β.
Therefore one might wonder whether scenarios exist in which a real loss of efficiency is bound to occur, i.e., can the price of uncertainty be greater than 1?
The following proposition shows that such scenarios indeed exist.


	There exists a family of task graphs and present bias sets for which the price of uncertainty converges to 1.1.



	Let 0 < a ≤ 3/8 be some present bias such that 4/a is integral and consider the task G consisting of a directed path v_0,v_1,…,v_12 + 4/a.
	We call this path the main path and charge a cost of 2 on its first edge while all other edges of the path have a cost of 1.
	In addition to the main path, we introduce a shortcut from v_1 to v_12 + 4/a along an intermediate node w.
	The cost of the two edges (v_1,w) and (w,v_12 + 4/a) is 4 and 6 + 3/a respectively.
	For a convenience let s = v_0 and t = v_12 + 4/a.
	Figure <ref> shows a sketch of G.
	
	Assume that G is traversed by an agent whose present bias is either a or b=1/2, but we do not know which, i.e., B = {a, 1/2}.
	Our goal is to construct two cost configurations ã and b̃ such that G_ã and G_b̃ are motivating for a reward of 10 + 5/a and the respective present bias.
	This implies sup{r(G,{a}),r(G,{1/2})}≤ 10 + 5/a.
	We then argue that a reward less than 9 + 11/(2a) is not sufficient to motivate both types of agents simultaneously, i.e., r(G,B) ≥ 9 + 11/(2a).
	As (9 + 11/(2a))/(10 + 5/a) converges to 11/10 for a → 0, this establishes the proposition.
	
	We begin with ã.
	For this purpose let ã assign no extra cost at all, i.e., ã(e) = 0 for all edges e.
	Furthermore, assume the agent has a present bias of a and a reward of 10 + 5/a is placed at t.
	When located at s, the agent's only choice is (s,v_1).
	If she plans to take the shortcut afterwards, her perceived cost of (s,v_1) is at most d_a,ã(s,v_1) ≤ 10a + 5.
	As this matches her perceived reward, she proceeds to v_1 where she faces two options:
	The first one is to take the shortcut for a perceived cost of d_a,ã(v_1,w) = 6a + 7.
	Considering that we chose a to satisfy a < 1/2, it follows that d_a,ã(v_1,w) > 10a + 5 and therefore the shortcut is not motivating.
	The second option is to take the main path along 11 + 4/a edges of cost 1, resulting in a perceived cost of d_a,ã(v_1,v_2) = 10a + 5.
	Similar to the situation at s, this cost matches the perceived reward and she proceeds to v_2.
	Since all remaining edges (v_i,v_i+1) have a perceived cost less than d_a,ã(v_1,v_2), the agent eventually reaches t and we conclude that G_ã is motivating.
	
		
	
	We continue to construct b̃ by setting b̃(v_1,w) = 1/(2a) and b̃(e) = 0 otherwise.
	In contrast to the previous scenario assume the agent has a present bias of b.
	The reward is still 10 + 5/a, but its perceived value has changed to 5 + 5/(2a).
	When located at the initial node s, the agent's perceived cost is at most d_b,b̃(s,v_1) ≤ 7 + 7/(4a) if she plans to take the shortcut afterwards.
	By choice of a it holds true that a < 3/8 and we get d_b,b̃(s,v_1) ≤ 5 + 5/(2a).
	Consequently, the agent is motivated to proceed to v_1.
	At this point, she has to choose between the shortcut and the main path.
	Her perceived cost of the former is d_b,b̃(v_1,w) = 7 + 2/a, whereas the latter has a perceived cost of  d_b,b̃(v_1,v_2) = 6 + 2/a.
	Clearly, the main path is her preferred choice and since a < 1/2, it is also a motivating one.
	Because all remaining edges (v_i,v_i+1) have a perceived cost less than d_b,ã(v_1,v_2), it follows that G_b̃ is motivating.
	
	It remains to show that no cost configuration can be motivating for both types of agents at the same time if the reward is less than 9 + 11/(2a).
	For the sake of contradiction assume such a cost configuration c̃ exists.
	Note that an agent with present bias b must not enter the shortcut as her perceived cost d_b,c̃(w,t) = 6 + 3/a exceeds her perceived reward of 9/2 + 11/(4a) for any a > 0.
	However, if we do not assign extra cost to G, such an agent prefers the shortcut to the main path when located at v_1.
	The difference in perceived cost is d_b(v_1,v_2) - d_b(v_1,w) = 1/(2a) - 1.
	Consequently, c̃ must assign extra cost greater than 1/(2a) - 1 to the shortcut.
	Next consider an agent with a present bias of a located at s.
	At this point her perceived cost for taking the shortcut is greater than 9a + 11/2, due to the extra cost assigned by c̃.
	Note that this cost exceeds her perceived reward.
	Her other option is to plan along the main path.
	In this case her perceived cost is 11a + 6.
	Clearly, this is even more expensive contradicting the assumption that c̃ is motivating for both types of agents.


As the price of uncertainty can be strictly greater than 1, the question for an upper bound arises.
Ideally, we would like to design a cost configuration c̃ motivating for all β∈ B assuming the reward is set to ϱ r(G,{b}) for some constant factor ϱ > 1 and b = min B.
Clearly, the existence of such a c̃ would imply a constant bound of ϱ for the price of uncertainty independent of G and B.
Using a generalized version of the approximation algorithm we proposed in <cit.>, it is indeed possible to construct a c̃ with the desired property for ϱ = 2.



The main idea of UncertainPresentBiasApprox is simple:
First, the algorithm computes a value α such that α/b is a lower bound on the reward necessary for agents with present bias b, i.e., r(G,{b}) ≥α/b.
In particular, this bound implies sup{r(G,{β}) |β∈ B}≥α/b.
Next the algorithm constructs a c̃ such that a reward of 2α/b is sufficiently motivating for all β∈ B, i.e., r(G,B) ≤ 2α/b.
As a result the price of uncertainty can be at most 2.
In the following we try to convey the intuition behind the algorithm in more detail.

We begin with the computation of α.
For this purpose let P be a path minimizing the maximum cost an agent with present bias b perceives on her way from s to t.
We call P a minmax path and define α = max{d_b(e) | e ∈ P} to be the maximum perceived edge cost of P.
Since cost configurations cannot decrease edge cost, it should be clear that α is a valid lower bound on the reward required for the present bias b, i.e., r(G,{b}) ≥α/b.

We proceed with c̃.
The goal is to assign extra cost in such a way that any agent with a present bias β∈ B traverses only two kinds of edges.
The first kind of edges are those on P.
It is instructive to note that each such edge (v,w) ∈ P is motivating for a reward of α/b if β≥ b.
The reason is that

    d_β(v,w) = β(c(v,w)/β + d(v,w)) ≤β(c(v,w)/b + d(v,w)) = βd_b(v,w)/b = βα/b.

In particular, P is motivating for each present bias β∈ B.
The second kind of edges are on cheapest paths to t.
To identify these edges, the algorithm assigns a distinct successor ς(v) to each node v ∈ V ∖{t} such that (v,ς(v)) is the initial edge of a cheapest path from v to t.
Since we assume t to be reachable from all other nodes of G at least one suitable successor must exist.
By definition of ς, we know that P' = v,ς(v),ς(ς(v)),…,t is a cheapest path from v to t.
We call P' the ς-path of v and T = {(v,ς(v)) | v ∈ V ∖{t}} a cheapest path tree.

Remember that we try to keep agents on the edges of P and T.
For this purpose, we assign an extra cost of c̃(e) = 2α/b + 1 to all other edges.
This raises their perceived cost to at least 2α/b + 1; a price no agent is willing to pay for a perceived reward of β2α/b.
However, since we have not assigned any extra cost to T so far, the perceived cost of edges in P and T is unaffected by the current c̃.
In particular, all edges of P are still motivating for a reward of α/b and any present bias β∈ B.
To keep agents from entering costly ς-paths P' = v,ς(v),ς(ς(v)),…,t, we assign an extra cost to the out-edges (v,ς(v)) of P, i.e., v ∈ P but ς(v) ∉ P.
The extra cost c̃(v,ς(v)) is chosen to match the cost of a most expensive edge on P' between v and the next intersection of P' and P.
It is easy to see that the resulting c̃ can no more than double the perceived cost of any edge in P, see the proof of Theorem <ref> for a precise argument.
Furthermore, the perceived cost of any out-edge (v,ς(v)) of P is either high enough to keep agents on P or they do not encounter edges exceeding the perceived cost of (v,ς(v)) until they reenter P.
We conclude that a reward of 2α/b is sufficiently motivating, leading us to one of the central results of our work.


	The price of uncertainty is at most 2.



	Let β be an arbitrary present bias from B.
	According to our considerations from Section <ref> it is evident that the theorem holds true if UncertainPresentBiasApprox yields a cost configuration c̃ such that a reward of 2α/b is motivating for β.
	In other words, we need to show that no agent with present bias β can reach a node v where her perceived cost d_β,c̃(v) exceeds her perceived reward of β2α/b.
	For this purpose we make a case distinction on v.
	
	First, assume that v is a node of P and let w be the direct successor of v on P. 
	In our previous discussion of UncertainPresentBiasApprox we have already argued that (v,w) is motivating for a reward of α/b if we ignore extra cost, i.e., d_β(v,w) ≤βα/b.
	Our goal is to show that c̃ can at most double the perceived cost of (v,w) in the sense that d_β,c̃(v,w) ≤ 2 d_β(v,w).
	Clearly, this directly implies the desired bound d_β,c̃(v) ≤ d_β,c̃(v,w) ≤β2α/b on the perceived cost of v.
	To prove our claim, let P' be the ς-path of w.
	Remember UncertainPresentBiasApprox does not raise the cost of (v,w).
	Moreover, the algorithm only assigns extra cost to edges (w',ς(w')) of P' that are out-edges of P, i.e., w' ∈ P but ς(w') ∉ P.
	Consequently, at most one edge of P' can charge extra cost between any two consecutive intersections of P and P'.
	Because this extra cost is equal to the cost of an edge between the two intersections, each edge of P' can contribute at most once to the total extra cost of P'.
	As a result, we know that the extra cost of P' is less or equal to its original cost.
	Together with the fact P' is a cheapest path from w to t we conclude that
	
	
    d_β,c̃(v,w) 	   = c(v,w) + β d_c̃(w) ≤ c(v,w) + β∑_e ∈ P'(c(e) + c̃(e))
       ≤ c(v,w) + β∑_e ∈ P' 2c(e) = c(v,w) + 2β d(w) ≤ 2 d_β(v,w).

	
	Next assume that v is not on P and let v' be the last node of P the agent visited before reaching v.
	Furthermore, let P_v = v,w,…,t and P_v' = v',w',…,t be the two paths the agent plans to take when located at v and v' respectively.
	Because the agent is willing to traverse (v',w'), we know d_β,c̃(v',w') ≤β2α/b.
	To obtain the desired bound d_β,c̃(v) ≤ d_β,c̃(v,ς(v)) ≤β2α/b, all that remains to be shown is d_β,c̃(v,w) ≤ d_β,c̃(v',w').
	At this point it is helpful to recall that the agent never plans to take an edge that is neither part of P or T.
	The reason is that those edges have an extra cost of 2α/b + 1, which certainly exceeds the perceived reward.
	As a result, we know that the first edges of P_v', i.e., the edges from v' to w, are all edges of T.
	Let Q, be the subpath of P_v' that goes from w' to w.
	By definition of P_v' we know that Q is part of a cheapest path from w' to t with respect to c̃ and it becomes apparent that
	
    d_c̃(w) ≤∑_e ∈ Q(c(e) + c̃(e)) + d_c̃(w) = d_c̃(w').

	Moreover, by design of c̃ we know that c(v,w) ≤c̃(v',w') and c̃(v,w) = 0.
	Combining these inequalities immediately yields
	
    d_β,c̃(v,w) = c(v,w) + β d_c̃(w) ≤ c(v',w') + c̃(v',w') + β d_c̃(w') = d_β,c̃(v',w').

	This completes the proof. 


It is interesting to note that UncertainPresentBiasApprox can be executed in polynomial time.
Furthermore, the proof of Theorem <ref> argues that α/b ≤ r(G,B) ≤ 2α/b.
As a result we have also found an efficient constant factor approximation of UPB-OPT.


	UPB-OPT admits a polynomial time 2-approximation.







§ VARIABLE PRESENT BIAS



So far we have considered agents with an unknown but fixed present bias.
We now generalize this model to agents whose β may vary arbitrarily within B as they progress through G.
It is convenient to think of β as a present bias configuration, i.e., an assignment of present bias values β(v) ∈ B to the nodes v of G.
Whenever the agent reaches a node v, she acts according to the current present bias value β(v).
We say that G is motivating with respect to a present bias configuration β if and only if the agent does not quit on a walk from s to t.

To illustrate the consequences of a variable present bias we revisit Alice and Bob's scenario once more.
Recall that the agent in this scenario is either like Alice with a present bias of a = 1/2 - ε or like Bob with a present bias of b = 1/2 + ε, i.e., B = {a,b}.
But while she had to commit to one present bias before, she is now free to change between a and b.
For instance, her present bias could be b at s and v_B, but a otherwise, i.e., β(v) = b for v ∈{s,v_B} and β(v) = a for v ∈ V ∖{s,v_B}.
In this case she walks along the same path Bob would take, i.e., s,v_B,v_AB,t.
However, there is a subtle difference.
At v_AB the agent behaves like Alice and needs strictly more reward than Bob to remain motivated while traversing (v_AB,t).
Under closer examination, which we will not go into detail here, it is in fact easy to see that the variability of β makes our agent more expensive to motivate than any agent with a fixed present bias from B.



 §.§ Computational Consideration


Let G be an arbitrary task graph and B a suitable present bias set.
We want to construct a cost configuration c̃ that is motivating for all present bias configuration β∈ B^V, but requires as little reward as possible.
Using arguments similar to those of Section <ref>, the computational challenges of this task are readily apparent.
In particular, the corresponding decision problem VARIABLE PRESENT BIAS (VPB) is equivalent to MCC whenever B only contains a single element.


	Given a task graph G, present bias set B and reward r > 0, decide whether a cost configuration c̃ motivating for all β∈ B^V exists.


Because MCC is NP-complete <cit.>, it immediately follows that VPB is NP-hard.
However, proving that UPB∈ NP requires a more careful argument.


  	VPB is contained in NP.



	Let B an arbitrary present bias set given as input and G the task graph resulting from some cost configuration.
	To prove that VPB is contained in NP we need to find an efficient way of confirming whether G is motivating for all β∈ B^V.
	Our strategy for this task consists of three steps:
	(a) Construct the set E' containing all edges (v,w) minimizing the agent's perceived cost at v for some present bias β(v) ∈ B.
	(b) Compute the set V' containing all nodes reachable from s via edges of E'.
	(c) For each node v ∈ V' check that the agent remains motivated for all possible present bias values β(v) ∈ B.
	To complete the proof we argue that each step can be completed in polynomial time and that (c) holds true if and only if G is motivating for all β∈ B^V.
	
	We begin with step (a).
	Observe that E' only contains edges (v,w) for which a β(v) ∈ B exists such that d_β(v)(v,w) ≤ d_β(v)(v,w') for all (v,w') ∈ E.
	From the proof of Proposition <ref> we already know that the present bias parameters β' ∈ [0,1] satisfying d_β'(v,w) ≤ d_β'(v,w') form a closed subinterval B_v,w⊆ [0,1].
	Moreover, the end points of this interval can be computed in polynomial time.
	Together with our assumptions on B, we may assume that B_v,w∩ B ≠∅ can be determined efficiently and therefore E' can be constructed in polynomial time.
	
	We continue with (b).
	Given the set E', it is trivial to construct V' in polynomial time.
	Furthermore, V' contains exactly those nodes an agent with variable present bias can reach if the reward is sufficiently large.
	To see this, let P be a path from s to v only using edges of E'.
	If we go through the edges (v',w') of P and choose β(v') as an element of the non-empty intersection B_v',w'∩ B, we obtain a valid present bias configuration that may lead the agent onto v for a sufficiently large reward.
	Conversely, we can find no such present bias configuration for nodes v ∉ V'.
	The reason is that all path P to v must contain at least one edge (v,w) ∉ E'.
	But by definition of E' the agent does not traverse (v,w) for any β(v) ∈ B.
	
	We conclude with (c).
	As a result of (b), we know that the agent can never reach nodes outside of V'.
	However, she can reach each v ∈ V', unless she quits at some other node of V' before she gets to v.
	As a result, we know that G is motivating for all β∈ B^V if and only if the agent never quits when located at any of the nodes v ∈ V'.
	Conveniently, we do not need to check the latter condition for all β(v) ∈ B.
	Instead, we only need to check for β(v) = b, with b denoting the minimum of B.
	The reason is that the minimum reward that is motivating in the case of β(v) = b is greater or equal to the reward required by any other present bias β(v) ≥ b, as the following inequality demonstrates
	
    d_b(v)/b   = min{c(v,w)/b + d(w) | (v,w) ∈ E }
       ≥min{c(v,w)/β(v) + d(w) | (v,w) ∈ E } = d_β(v)(v)/β(v).

	Therefore (c) can be decided in polynomial time.
	This completes the proof.


As a result of Proposition <ref>, we may conclude that VPB is NP-complete.


	VPB is NP-complete.


Since it is NP-hard to find optimal cost configurations for general B, we turn to an optimization version of the problem.
Assuming that r(G,B^V) denotes the infimum over all rewards admitting a cost configuration c̃ motivating for all β∈ B^V, we define VPB-OPT as:
 

	Given a task graph G and present bias set B, determine r(G,B^V).


Interestingly, approximating VPB-OPT seems to be much harder than UPB-OPT.
The reason why the 2-approximation for UPB-OPT, i.e., UncertainPresentBiasApprox, does not work anymore is simple.
Recall that the cost configuration c̃ returned by the algorithm lets the agent take shortcuts along cheapest paths to t.
To ensure that these shortcuts do not become too expensive, c̃ assigns extra cost to their initial edge.
This way the perceived cost within a shortcut should not be greater than that for entering.
As long as the present bias is fixed, this works fine.
However, if the present bias can change, the agent may become more biased within a shortcut and require higher rewards to stay motivated.
One way to fix this problem is to let the assigned extra cost depend on τ, i.e., the range of B.
More precisely, we multiply the cost assigned in line <ref> of Algorithm <ref> by τ and change line <ref> to assign a cost of c̃(e) = (1+τ)α/b + 1.
As a result we obtain a new algorithm VariablePresentBiasApprox with an approximation ration of 1 + τ.


	VPB-OPT admits a polynomial time (1+τ)-approximation.



	Let b = min B.
	From the analysis of UncertainPresentBiasApprox in Section <ref> it should be clear that α/b = max{d_b(e) | e ∈ P}/b is a lower bound for r(G,B^V) and can be computed in polynomial time.
	To establish the theorem, we argue that (1+τ)α/b is an upper bound for r(G,B^V).
	In particular, we prove that the cost configuration c̃ returned by VariablePresentBiasApprox is motivating for all β∈ B^V if the reward is set to (1+τ)α/b.
	
	Using the same reasoning as in proof of Theorem <ref>, we know that the agent's perceived cost at any node v of P is covered by a reward of (1+τ)α/b, i.e., d_β(v),c̃(v) = β(v)((1+τ)α/b). 
	All that remains to be shown is that this reward is also sufficient if the agent is located on a node v not on P.
	For this purpose, let v' be the last node of P the agent visited before reaching v.
	Furthermore, let (v,w) and (v',w') denote the two edges the agent plans to take when located at v and v' respectively.
	According to the same argument we made in the proof of Theorem <ref>, it holds true that a cheapest path from w' to t with respect to c̃ is more expensive than a cheapest path from w to t, i.e., d_c̃(w) ≤ d_c̃(w').
	We also know that τ c(v,w) ≤c̃(v',w') and c̃(v,w) = 0 hold true by construction of c̃.
	Finally the definition of τ = max B/min B implies that β(v) ≥β(v')/τ.
	Combining these inequalities yields
	
    d_β(v),c̃(v)	   ≤ d_β(v),c̃(v,w) = β(v)(c(v,w)/β(v) + d(w)) ≤β(v)(c(v,w)/β(v')/τ + d(w))
       ≤β(v)(c̃(v',w') + c(v'w')/β(v') + d(w')) = β(v)/β(v') d_β(v'),c̃(v',w').

	
	Recall that the agent already traversed (v',w').
	Therefore her perceived cost of (v',w') is at most d_β(v'),c̃(v',w') ≤β(v')((1+τ)α/b), implying that 
	
    d_β(v),c̃(v) ≤β(v)/β(v')β(v')((1+τ)α/b) = β(v)((1+τ)α/b).

	This completes the proof.


Although VariablePresentBiasApprox yields a good approximation for a moderately variable present bias, it does not provide a constant approximation bound like UncertainPresentBiasApprox.
However, this is not necessarily a shortcoming of the algorithm, but a complexity consequence.
To prove hardness for constant factor approximations of VPB-OPT, we consider the VECTOR SCHEDULING (VS) problem.


	Given m machines denoted by the sets M_1,…,M_m and ℓ jobs in the form of d-dimensional vectors q_1,…,q_ℓ∈ℝ_≥ 0^d, find the smallest makespan over all dimensions, i.e., minimize max{∑_q ∈ M_i q_∞| 1 ≤ i ≤ m} with respect to all partitions of the jobs into sets M_1,…,M_m.


As Chekuri and Khanna have shown, VS-OPT is unlikely to have an efficient constant factor approximation <cit.>.


	No polynomial time algorithm approximates VS-OPT within a constant factor ϱ>1, unless  NP = ZPP.
	This holds true even if the problem is restricted to 0-1 vectors.


By reducing VS-OPT to VPB-OPT, we are able to prove that VPB-OPT is unlikely to have an efficient constant factor approximation as well.


	No polynomial time algorithm approximates VPB-OPT within a constant factor ϱ > 1, unless NP = ZPP.



	Our proof is based on the following reduction from VS-OPT.
	Let ℐ be an arbitrary instance of VS-OPT with a set of m machines and ℓ≥ 2 jobs q_1,…,q_ℓ∈{0,1}^d.
	Our goal is to construct an instance 𝒥 of VPB-OPT with a size polynomial in that of ℐ such that the following two claims are satisfied:
	(a) If ℐ has a schedule with a makespan of κ, then 𝒥 has a cost configuration that is motivating for a reward of r = κℓ + ℓ + 1.
	(b) If 𝒥 has a cost configuration that is motivating for a reward of r, then ℐ has a schedule with a makespan of at most κ = 2r/ℓ.
	Consequently, if we have a polynomial time algorithm for VPB-OPT with a constant approximation ratio ϱ, we can apply this algorithm to 𝒥 and recover a 2ϱ + 𝒪(1) approximate solution for ℐ in polynomial time.
	According to Theorem <ref> this is not possible unless NP = ZPP.
	
	As our first step we need to construct the VPB-OPT instance 𝒥.
	In particular, we need to specify a present bias set B and a task graph G.
	We begin with B.
	From Theorem <ref> we know that VPB-OPT has a (1+τ)-approximation algorithm.
	Consequently, we should choose B in such a way that its range depends on the size of ℐ.
	Furthermore, Proposition <ref> implies that B should not include the value 1.
	For the sake of simplicity we set B = {1/2,1/ℓ^2}.
	
			
	
	We continue with the construction of G.
	For this purpose we introduce a column H_i,j for each machine i and dimension j.
	The structure of these columns, which is illustrated in Figure <ref>, is identical for all machines and dimensions.
	More precisely, each column H_i,j consists of ℓ levels and each level k, with 1 ≤ k ≤ℓ, consists of a directed path starting at a node v_i,j,k and ending at w_i,j,k.
	In between there are ℓ^4 edges of cost 1/ℓ^2 resulting in a total path cost of ℓ^2.
	Furthermore, each node of the path has a shortcut to the next level k+1, or to t in the special case of k = ℓ.
	For a convenient notation let t = v_i,j,ℓ+1.
	We distinguish between two types of shortcuts.
	Shortcuts of the first type connect v_i,j,k with v_i,j,k+1 via two edges of cost 0 and 1 respectively.
	Shortcuts of the second type connect all remaining nodes on level k with v_i,j,k+1 via a single edge of cost ℓ.
	For the sake of a concise representation Figure <ref> merges some shortcuts.
	
	To connect the individual columns, we construct a path P_i,k for each machine i and job q_k.
	The idea of P_i,k is to cross the k-th level of all columns H_i,j for which q_k has a cost of 1 in dimension j, i.e., (q_k)_j = 1.
	As start and endpoint of P_i,k we introduce additional nodes u_i-1 and u_i and set s = u_0 and t = u_ℓ.
	A more formal construction of P_i,k is as follows:
	Let j be an arbitrary dimension for which (q_k)_j = 1.
	Without loss of generality we may assume that at least one such dimension exists.
	Otherwise, q_k could be assigned to any machine without affecting the makespan and would therefore be irrelevant to the schedule.
	If j is the dimension of lowest index satisfying (q_k)_j = 1, we draw an edge of cost 1/ℓ^2 from u_k-1 to v_i,j,k.
	Similarly, we draw an edge of cost 1/ℓ^2 from w_i,j,k to u_k if j is the dimension of highest index for which (q_k)_j = 1.
	For all intermediate dimensions j satisfying (q_k)_j = 1, we draw an edge of cost 1/ℓ^2 from w_i,j,k to a distinct intermediate node u_i,j,k and another edge of the same cost from u_i,j,k to v_i,j',k with j' being the dimension of next higher index satisfying (q_k)_j' = 1.
	Figure <ref> illustrates this construction for a small sample instance of ℐ.
	Note that the nodes u_1 and u_2 appear twice in the figure, once on the left and once on the right, to keep the drawing simple.
	
	To complete our construction, we introduce a third type of shortcuts connecting all nodes u_k ≠ t and u_i,j,k to t via a single edge of cost ℓ.
	For the sake of a clear representation these shortcuts are not depicted in Figure <ref>.
	Note that the resulting task graph G is acyclic and can be constructed in polynomial time with respect to ℐ.
	It should also be mentioned that some columns of G might contain nodes which are not reachable from s.
	However, as argued in Section <ref> we may ignore these nodes as they do not affect the agent's behavior and can be removed from G in polynomial time.
	
	We proceed with the proof of statement (a), i.e., given a partition of jobs M_1,…,M_m for ℐ resulting in a makespan κ, we show how to construct a cost configuration c̃ such that 𝒥 is motivating for a reward of κℓ + ℓ + 1.
	The construction of c̃ is simple.
	For each job q_k it is sufficient to assign an extra cost of ℓ to the initial edge of all shortcuts starting at a node v_i,j,k for which i is the machine q_k is scheduled on, i.e., q_k ∈ M_i, and j is a dimension in which q_k has a cost of 1, i.e., (q_k)_j = 1.
	Furthermore, an extra cost of κℓ + ℓ + 2 needs to be assigned to the initial edge of all paths P_i',k associated with the machines i' job q_k is not scheduled on, i.e., q_k ∉ M_i'.
	
	To show that c̃ is motivating for a reward of κℓ + ℓ + 1, we argue that an agent with a present bias configuration β∈ B^V successfully constructs a path from s to t that only consists of paths P_i,k for which q_k ∈ M_i and possibly a shortcut of the third type.
	For this purpose, assume the agent is located at some node v ≠ t on P_i,k.
	A case distinction with respect to the type of v shows that the agent either stays on P_i,k or takes a shortcut of the third type.
	As the paths P_i,k are connected at their terminal nodes, this proves the claim.
	
	
	
	We begin with the case v = u_k-1.
	When located at such a node v the agent has three choices.
	First, she might plan to enter a path P_i',k for which i' ≠ i.
	However, c̃ assigns an extra cost of κℓ + ℓ + 2 to the initial edge of P_i',k.
	Therefore the agent is not motivated to take P_i',k no matter what the exact value of β(v) is.
	Secondly, the agent might plan to enter P_i,k from v.
	If she plans to follow the shortcuts of the first kind all the way to t after traversing the first edge of P_i,k, she faces an immediate edge of cost 1/ℓ^2 and at most ℓ future edges of cost 1, one per subsequent level.
	Furthermore, the number of future edges with an extra cost of ℓ is bounded by the makespan κ.
	Considering that 1/ℓ^2 ≤β(v), we conclude that the agent's perceived cost for entering P_i,k is at most 1/ℓ^2 + β(v) (ℓ + κℓ) ≤β(v) + β(v)(ℓ + κℓ) = β(v)(κℓ + ℓ + 1).
	As this matches her perceived reward, entering P_i,k must be motivating.
	Thirdly, the agent might plan to take the shortcut of the third type from v.
	If she does so, she immediately reaches t.
	If not, the only motivating option that remains is P_i,k.
	Either way our claim holds true.
	
	We continue with the case v = u_i,j,k, which is very similar to the previous one.
	Again the agent may either stay on P_i,k or take the shortcut of the third type.
	Analyzing the perceived cost of these two options is identical to the previous case.
	The only difference is that the agent is missing the first option, which is to enter a path P_i',k for which i' ≠ i.
	However, this does not affect her motivation to stay on P_i,k nor does it affect the possibility of her taking the shortcut.	
	
	Next we consider the case that v is a node on the k-th level of some column H_i,j different from w_i,j,k.
	When located at v the agent has two choices.
	Either she takes the immediate shortcut incident to v or she traverses an edge of P_i,k.
	Her perceived cost of the first option is ℓ + β(v) d_c̃(v_i,j,k+1) while her perceived cost of the second option is at most 1/ℓ^2 + β(v) (ℓ + d_c̃(v_i,j,k+1)) if she plans to take the shortcut of the second type immediately after traversing the edge of P_i,k.
	Consequently, the agent prefers to stay on P_i,k whenever ℓ > 1/ℓ^2 + β(v)ℓ or 1 - 1/ℓ^3 > β(v) if we rearrange the inequality.
	Considering that ℓ≥ 2 and β(v) ≤ 1/2 hold true, this inequality is certainly satisfied.
	It remains to show that staying on P_i,k is also a motivating option.
	However, following the same line of argument we have used for the perceived cost of P_i,k in the case v = u_i,j,k, this should be easy to see.
	
	Finally, we consider the remaining case v = w_i,j,k.
	Similar to the previous case the agent has two options.
	Either she takes the immediate shortcut incident to v or she traverses P_i,k and ends up at u_i,j,k.
	Her perceived cost of the first option is ℓ + β(v) d_c̃(v_i,j,k+1) ≥ℓ.
	In contrast, if she moves to u_i,j,k and then takes the shortcut of the third kind immediately after, her perceived cost is 1/ℓ^2 + β(v) ℓ.
	As a result she prefers the first option whenever ℓ > 1/ℓ^2 + β(v)ℓ.
	But from the previous case we already know that this inequality is always satisfied.
	Furthermore, the fact that 1/ℓ^2 ≤β(v) implies that the agent's perceived cost for moving to u_i,j,k is at most 1/ℓ^2 + β(v)ℓ≤β(v) + β(v)ℓ≤β(v)(κℓ + ℓ + 1).
	As this matches her perceived reward, we know that moving to u_i,j,k is motivating.
	
	We now come to the proof of (b).
	For this purpose assume 𝒥 has a cost configuration c̃ that is motivating for a reward of r.
	Our goal is to schedule the jobs of ℐ with a makespan of at most 2r/ℓ.
	Since any schedule has a makespan less or equal to ℓ, we focus on the case r < ℓ^2/2.
	As a result, the agent's perceived reward becomes r/ℓ^2 < 1/2 whenever her present bias takes the value 1/ℓ^2.
	However, this implies that the agent must not take shortcuts of the first kind.
	The reason is that her perceived cost at the intermediate node of the shortcut is at least 1 and therefore she might lose motivation.
	Furthermore, the agent is not motivated to take shortcuts of the second or third type whenever her present bias is 1/ℓ^2.
	Consequently, if we fix the agent's present bias to β(v) = 1/ℓ^2 at all nodes v of G, she must construct a path P from s to t that does not contain shortcuts of any type.
	This means that P can be divided into a sequence of paths P_i,k.
	By assigning job q_k to machine i if P_i,k is contained in P we obtain a feasible partition M_1,…,M_m.	
	
	Next we argue that the makespan of M_1,…,M_m is at most 2r/ℓ.
	For this purpose we first show that c̃ must assign an extra cost of at least ℓ/2 - 1 to all shortcuts starting at a node v_i,j,k for which q_k is scheduled on i, i.e., q_k∈ M_i.
	For this purpose, assume the agent is located at v_i,j,k.
	Note that this scenario is indeed possible if β(v) = 1/ℓ^2 for all nodes v of P that come before v_i,j,k.
	Furthermore, assume that β(v_i,j,k) = 1/2.
	As we have argued in the previous paragraph, the agent must not take the shortcut at v_i,j,k, but stay on P_i,k.
	Let P' denote her planned path.
	We distinguish between two possible scenarios for P'.
	First, P' might follow the path P_i,k until the agent reaches another column or the node u_k.
	In this case, the first ℓ^4 + 1 edges of P' are all of cost 1/ℓ^2.
	As a result, the perceived cost of P' is at least 1/ℓ^2 + β(v_i,j,k)ℓ^2 = 1/ℓ^2 + ℓ^2/2.
	Considering that r < ℓ^2/2, this cannot be motivating.
	Secondly, P' might contain a shortcut of the second type to the next level of H_i,j.
	Even if we neglect potential extra cost c̃ may assign to the current level of H_i,j and furthermore assume that the agent takes the very next shortcut, her perceived cost of P' is at least 1/ℓ^2 + β(v_i,j,k)(ℓ + d_c̃(v_i,j,k+1)) in this case.
	In contrast, the agent's perceived cost for taking the immediate shortcut at v_i,j,k is only β(v_i,j,k)(1 + d_c̃(v_i,j,k+1)) if we neglect potential extra cost.
	Since the agent must not enter the shortcut at v_i,j,k, we conclude that the cost configuration c̃ assigns an extra cost greater than 1/ℓ^2 + β(v_i,j,k)(ℓ - 1) > ℓ/2 - 1 to the shortcut.
	
	To see that the makespan of our schedule is at most 2r/ℓ, consider the workload κ on an arbitrary machine i in an arbitrary dimension j.
	Assuming that κ > 0, let q_k be the job of lowest index scheduled on i such that (q_k)_i = 1.
	Furthermore, assume that the agent is located at v_i,j,k and that her current present bias is β(v_i,j,k) = 1/ℓ^2.
	As argued in the previous paragraph, this assumption is justified.
	We continue with a case distinction on the path P' the agent plans when located at v_i,j,k.
	In general, P' can have one of the following two forms:
	Either it exits column H_i,k to the right or it is completely contained in H_i,k and climbs to the top level via shortcuts of the first and or second type.
	If P' exits to the right, it must contain at least ℓ^4 + 1 edges costing 1/ℓ^2 each.
	Clearly, the agent's perceived cost of such a P' is at least 1/ℓ^2 + β(v_i,j,k)(ℓ^4/ℓ^2) > 1 and cannot be motivating for a perceived reward β(v_i,j,k)r = r/ℓ^2 < 1/2.
	However, this means that some path P' of the second form must be motivating.
	In this case, P' consists of at least κ shortcuts that according to the result from the previous paragraph all have a cost of at least ℓ/2 with respect to c̃.
	As a result, the perceived cost of P' is at least β(v_i,j,k)κℓ/2 = κ/(2ℓ).
	To make sure that this cost does not exceed β(v_i,j,k)r = r/ℓ^2, the total load κ of machine i in dimension j can be at most 2r/ℓ.




 §.§ Occasionally Unbiased Agents


Although VPB is hard to solve in general, a curious special case consisting of all present bias sets B for which 1 ∈ B is not.
Note that agents whose present bias varies within such a B becomes temporarily unbiased whenever 1 is drawn.
For this reason we call these agents occasionally unbiased.
A behavioral pattern unique to occasionally unbiased agents is that they may start to walk along a cheapest path at any point in time whenever their present bias becomes 1.
As a result we can reduce VPB to a decision problem we call CRITICAL NODE SET (CNS) for occasionally unbiased agents.


	Given a task graph G, present bias set B and reward r, decide the existence of a critical node set W. 


We consider a node set W critical if the following properties hold:
(a) s ∈ W.
(b) Each node v ∈ W has a path P to t that only uses nodes of W.
(c) All edges e of P satisfy d_b(e) ≤ br with b = min B.
As it turns out, such a W contains exactly those nodes an occasionally unbiased agent may visit with respect to a motivating cost configuration.
This allows us to reduce VPB to CNS.


	Assuming that 1 ∈ B, then VPB has a solution if and only if CNS has one.



	(⇒) To prove the first implication, assume a critical node set W exists.
	Our goal is to construct a cost configuration c̃ that is motivating for all β∈ B^V.
	For this purpose, we assign an extra cost of c̃(v,w) = r+1 to all edges (v,w) that leave W, i.e., all edges for which v ∈ W but w ∉ W, and set c̃(e) = 0 for the remaining edges.
	The resulting c̃ is motivating for two reasons:
	(a) Whenever the agent is inside W, she is not motivated to leave W.
	(b) Each node v ∈ W ∖{t} has at least one successor w ∈ W the agent is motivated to visit next.
	Together with the fact that s ∈ W we conclude that the agent moves through W until she eventually reaches t.
	
	In the following we show (a) and (b).
	Since each edge (v,w) that leaves W has an extra cost of r + 1, the perceived cost of (v,w) trivially exceeds the agent's perceived reward of β(v) r.
	Therefore (v,w) cannot be motivating, which proves (a).
	We proceed with (b). 
	For each node v ∈ W ∖{t} we need to show the existence of a direct successor w ∈ W such that (v,w) is motivating for all β(v) ∈ B.
	To prove this, remember that W is a critical node set.
	Consequently, there must exist a path P = v,w,…,t that consists exclusively of nodes from W such that c(v,w) + b ∑_e ∈ P' c(e) ≤ br, with P' being the path obtained by removing the initial edge of P.
	Because P is contained in W, no edge of P charges extra cost.
	By definition of b we also know that β(v)/b ≥ 1 and we can bound the perceived cost of (v,w) from above by
	
    d_β(v),c̃(v,w) ≤ c(v,w) +  β(v) ∑_e ∈ P' c(e) ≤β(v)/b(c(v,w) + b ∑_e ∈ P' c(e)) ≤β r.

	As this bound matches the perceived reward, (v,w) must be motivating.
	
	(⇐) To prove the reverse, assume that G has a cost configuration c̃ such that G_c̃ is motivating for all present bias configurations β∈ B^V.
	Moreover, let W' be the set of all nodes the agent might visit on her path from s to t.
	Our goal is to argue that W' is a critical node set, i.e., W' meets the following requirements:
	(a) s ∈ W'.
	(b) Each node v ∈ W' has a path P to t that only uses nodes of W'.
	(c) All edges e of P satisfy d_b(e) ≤ br with b = min B.
	By definition of W' (a) is trivially satisfied.
	To prove (b) and (c), let v be some node of W' and choose w as the immediate successor of v the agent visits for a present bias of β(v) = b.
	Furthermore, let P' be a cheapest path from w to t with respect to c̃.
	By adding (v,w) to the initial node of P', we obtain a path P satisfying (b) and (c).


	
	We first show (c).
	Recall that the agent is motivated to traverse (v,w) for a present bias of β(v) = b.
	The fact that P' is a cheapest path from w to t with respect to c̃ immediately implies that the perceived cost of P is at most
	
    c(v,w) + b ∑_e ∈ P c(e) ≤ c(v,w) + c̃(v,w) + b ∑_e ∈ P(c(e) + c̃(e)) = d_b,c̃(v,w) ≤ br.

	We continue with (b).
	Assuming the agent is located at v, consider a present bias configuration β that assigns a value of β(v) = b to v and β(v') = 1 to all nodes v' ≠ v located on paths from v to t.
	Because 1 ∈ B, such a present bias configuration is possible.
	By choice of (v,w), we also know that the agent potentially traverses w and at that point follows a cheapest path to t with respect to c̃.
	Since P' is such a path, we conclude that the agent may visit any node of P and therefore all nodes of P are certainly contained in W'.


All that remains to show is that CNS is decidable in polynomial time.
A straight forward approach to this simple algorithmic problem is DecideCriticalNodeSet, see Algorithm <ref>.
The main idea of this algorithm is simple.
Going through each node v of G in reverse topological order, DecideCriticalNodeSet computes the values δ(v) denoting the cost of a cheapest path from v to t with respect to the δ values computed so far.
If the perceived cost at v with respect to δ is too expensive, then v cannot be contained in any critical node set and the algorithm sets δ(v) = ∞.
Consequently, only nodes with δ(v) < ∞ can be part of a critical node set.
In particular, we know that a critical node set exists if and only if δ(s) < ∞.
Clearly, DecideCriticalNodeSet can be executed in polynomial time which proves that CNS, can be decided in polynomial time for occasionally unbiased agents.
As a corollary of Proposition <ref>, so can VPB.


	If 1 ∈ B, then VPB can be solved in polynomial time.




 §.§ The Price of Variability


To conclude our work, we take a step back from computational considerations and look at the implications of variability from a more general perspective.
Our goal is to quantify the conceptual loss of efficiency incurred by going from a fixed and known present bias to an unpredictable and variable one.
Similar to the price of uncertainty we define the price of variability as the following ratio.


	Given a task graph G and a present bias set B, the price of variability is defined as r(G,B^V)/sup{r(G,{β}) |β∈ B}.


It seems obvious that the price of variability depends closely on the structure of G and B.
Nevertheless, we would like to find general bounds for the price of variability much like we did in Section <ref> for the price of uncertainty.
As a first step, it is instructive to note that the price of uncertainty is a natural lower bound for the price of variability.
The reason for this is that each cost configuration that motivates an agent whose present bias varies arbitrarily in B must also motivate an agent whose present bias is a fixed value from B.
Therefore it holds true that r(G,B^V) ≥ r(G,B), which immediately implies the stated bound. 
Sometimes this bound is tight.
Consider for instance Alice and Bob's scenario.
As we have shown in Section <ref>, it is possible to construct a cost configuration c̃ verifying a price of uncertainty of 1.
Using similar arguments, it is easy to see that c̃ remains motivating if we allow the present bias to vary, implying an identical price of variability.
However, for general instances of G and B this tight relation between the price of uncertainty and the price of variability is lost.
In fact, we can show that unlike the price of uncertainty, which has a constant upper bound of 2, the price of variability may become arbitrarily large as the range of B increases.


	There exists a family of task graphs and present bias sets for which the price of variability converges to τ/2.



	To obtain a price of variability close to τ/2 we consider an occasionally unbiased agent with respect to the set B = {a,1} for some 0 < a < 1/2 such that 1/a is integral.
	Furthermore, we construct a task graph G consisting of a directed path v_0,v_1,…,v_1/a^2+1/a+2 whose edges are all of cost 1.
	We call this the main path.
	In addition to the main path we introduce 1/a^2 + 1 shortcuts via a common node w.
	Each shortcut i with 0 ≤ i ≤ 1/a^2 consists of two edges.
	The first edge goes from v_i to w for a cost of 2 while the second edge goes from w to t for a cost of 1/a.
	As source and target node, we choose s = v_0 and t = v_1/a^2+1/a+2.
	Figure <ref> shows a sketch of G.
	Note that some edges of the shortcuts are merged for the sake of a concise representation.
	
	
	
	The remainder of the proof has a similar structure to that of Proposition <ref>.
	We first argue that a reward of 2/a+2 is sufficiently motivating for any agent with a fixed present bias of either a or 1, implying sup{r(G,{a}),r(G,{1})}≤ 2/a+2.
	We then show that no cost configuration c̃ can motivate an occasionally unbiased agent for a reward less than 1/a^2, i.e., r(G,{a,1}^V) ≥ 1/a^2.
	As a result, the price of variability must be at least (1/a^2)/(2/a+2).
	Note that this term approaches 1/(2a) = τ/2 as a → 0, which establishes the theorem.
	
	To see that a reward of 2/a+2 is sufficiently motivating for an agent with a fixed present bias of a, assume such an agent is located at an arbitrary node v_i with 0 ≤ i ≤ 1/a^2+1/a+1.
	Her perceived cost for traversing (v_i,v_i+1) is at most d_a(v_i,v_i+1) ≤ 1 + a(2 + 1/a) = 2 + 2a if she plans to take the next shortcut at v_i+1.
	In the special case of i = 1/a^2, her perceived cost is d_a(v_1/a^2,v_1/a^2 + 1) = 1 as she can reach t directly via (v_1/a^2,v_1/a^2 + 1).
	Either way, a reward of r = 1/a(2 + 2a) = 2/a + 2 covers her perceived cost for staying on the main path.
	In contrast, taking the immediate shortcut at v_i has a perceived cost of d_a(v_i,w) = 2 + a(1/a) = 3.
	As we assume a < 1/2, the agent clearly perceives shortcuts as more expensive than the main path.
	Consequently, she follows the main path from s to t for a reward of 1/a(2 + 2a) = 2/a + 2.
	
	Next consider an unbiased agent, i.e., an agent with a fixed present bias of 1.
	Such an agent strictly follows a cheapest path P from s to t.
	Furthermore, her perceived cost along P never exceeds the total cost of P.
	Taking the first shortcut at s, we can bound the cost of a cheapest path from s to t from above by 2 + 1/a < 2/a + 2.
	This implies that the unbiased agent successfully reaches t for a reward of 2/a + 2.
	
	It remains to show that no cost configuration c̃ can be motivating for all present bias configurations β∈{1,a}^V if the reward is less than 1/a^2.
	For the sake of contradiction, assume such a c̃ exists.
	Note that the agent must not visit w.
	The reason is that a reward of less than 1/a^2 is not sufficient to make her traverse (w,t) should her present bias become β(w) = a.
	However, to prevent the agent from taking a shortcut, c̃ must assign a cost greater than 1/a^2 - i to all shortcuts i for 0≤ i ≤ 1/a^2.
	We proof this claim via an induction on i.
	For the base of the induction, let i=1/a^2.
	At v_1/a^2, exactly 2 + 1/a edges remain on the main path.
	Ignoring extra cost, there are two cheapest paths to t, one along the main path and one along the current shortcut.
	Consequently, if we assume that the agent is momentarily unbiased, i.e., β(v_1/a^2) = 1, and therefore takes a cheapest path from s to t, it becomes clear that c̃ must assign an extra cost greater than 0 = 1/a^2 - i to the current shortcut to prevent the agent from moving to w.
	
	For the induction step let i < 1/a^2 and assume that each shortcut j with i < j ≤ 1/a^2 has an extra cost greater than 1/a^2 - j.
	Our goal is to argue that the extra cost assigned to the shortcut i must be greater than 1/a^2 - j.
	When located at v_i, exactly 1/a^2 - i + 1/a + 2 edges of the main path remain to t.
	If the agent is currently unbiased, she perceives a cost of at least 1/a^2 - i + 1/a + 2 for taking the main path.
	Clearly she cannot reduce this cost by planning to take a shortcut j' with j' > 1/a^2.
	Should she consider a shortcut j with i < j ≤ 1/a^2 instead, she must first traverse (j-i) edges of the main path.
	Together with the induction hypothesis her total perceived cost for such a plan is at least (j-i) + 2 + 1/a + (1/a^2 - j) = 1/a^2 - i + 1/a + 2.
	Consequently, her perceived cost for staying on the main path is at least 1/a^2 - i + 1/a + 2.
	Since this exceeds the cost of shortcut i by at least 1/a^2 - i, we know that an extra cost greater than 1/a^2 - i must be assigned to the current shortcut to prevent the agent from walking onto w.
	This concludes the induction.
	
	We now know that all shortcuts i with 0≤ i ≤ 1/a^2 have an extra cost greater than 1/a^2 - i.
	By the same argument we have used in the inductive step it should be clear that each path from s to t has a cost of at least 1/a^2 + 1/a + 2.
	Therefore if the agent is unbiased at s, we need a reward of 1/a^2 + 1/a + 2 > 1/a to motivate her.
	However, this contradicts our initial assumption on c̃.


Although Proposition <ref> implies that the price of variability can become substantially larger than the price of uncertainty, it should be noted that the task graph constructed in the proof of this proposition is close to a worst case scenario.
In particular, we can show that the price of variability cannot exceed τ + 1, which is roughly twice the value obtained by Proposition <ref>.
To verify this upper bound, it is helpful to recall the proof of Theorem <ref>.
In the process of establishing the approximation ratio of VariablePresentBiasApprox we have argued that the cost configuration c̃ returned by the algorithm motivates any agent with a present bias configuration β∈ B^V for a reward of at most (τ + 1)r(G,{min B}).
Consequently, it holds true that r(G,B^V )≤ (τ + 1)r(G,{min B}), implying that the price of variability cannot exceed τ + 1. 


	The price of variability is at most τ + 1.






plainurl


