# Present-Biased Optimization††thanks: A preliminary version of this paper is
accepted for AAAI 2021. The research received funding from the Research
Council of Norway via the project “MULTIVAL” (grant no. 263317) and from the
French National Research Agency (ANR) via the project “DESCARTES”.

Fedor V. Fomin Department of Informatics, University of Bergen, Norway Pierre
Fraigniaud IRIF, Université de Paris and CNRS, France Petr A.
Golovach-1-1footnotemark: -1

###### Abstract

This paper explores the behavior of _present-biased_ agents, that is, agents
who erroneously anticipate the costs of future actions compared to their real
costs. Specifically, the paper extends the original framework proposed by
Akerlof (1991) for studying various aspects of human behavior related to time-
inconsistent planning, including procrastination, and abandonment, as well as
the elegant graph-theoretic model encapsulating this framework recently
proposed by Kleinberg and Oren (2014). The benefit of this extension is
twofold. First, it enables to perform fine grained analysis of the behavior of
present-biased agents depending on the _optimisation task_ they have to
perform. In particular, we study covering tasks vs. hitting tasks, and show
that the ratio between the cost of the solutions computed by present-biased
agents and the cost of the optimal solutions may differ significantly
depending on the problem constraints. Second, our extension enables to study
not only underestimation of future costs, coupled with minimization problems,
but also all combinations of minimization/maximization, and
underestimation/overestimation. We study the four scenarios, and we establish
upper bounds on the cost ratio for three of them (the cost ratio for the
original scenario was known to be unbounded), providing a complete global
picture of the behavior of present-biased agents, as far as optimisation tasks
are concerned.

##  1 Introduction

_Present bias_ is the term used in behavioral economics to describe the gap
between the anticipated costs of future actions and their real costs. A simple
mathematical model of present bias was suggested by Akerlof [1]. In this model
the cost of an action that will be perceived in the future is assumed to be
$\beta$ times smaller than its actual cost, for some constant $\beta<1$,
called the _degree of present bias_. The model was used for studying various
aspects of human behavior related to _time-inconsistent_ planning, including
_procrastination_ , and _abandonment_.

Kleinberg and Oren [10, 11] introduced an elegant graph-theoretic model
encapsulating Akerlof’s model. The approach of Kleinberg and Oren is based on
analyzing how an agent navigates from a source $s$ to a target $t$ in a
directed edge-weighted graph $G$, called _task graph_. At any step, the agent
chooses the next edge to traverse from the current vertex $v$ thanks to an
estimation of the length of the shortest path from $v$ to $t$ passing through
each edge outgoing from $v$. A crucial characteristic of the model is that the
estimation of the path lengths is _present-biased_. More specifically, the
model of Kleinberg and Oren includes a positive parameter $\beta<1$, the
degree of present bias, and the length of a path $x_{0},\dots,x_{k}$ from
$x_{0}=v$ to $x_{k}=t$ in $G$ is evaluated as
$\omega_{0}+\beta\,\sum_{i=1}^{k-1}\omega_{i}$ where $\omega_{i}$ denotes the
weight of edge $(x_{i},x_{i+1})$, for every $i\in\\{0,\dots,k-1\\}$. As a
result, the agent may choose an outgoing edge that is not on any shortest path
from $v$ to $t$, modeling _procrastination_ by underestimating the cost of
future actions to be performed whenever acting now in some given way. With
this effect cumulating along its way from $s$ to $t$, the agent may
significantly diverge from shortest $s$-$t$ paths, which demonstrates the
negative impact of procrastination. Moreover, the _cost ratio_ , which is the
ratio between the cost of the path traversed by an agent with present bias and
the cost of a shortest path, could be arbitrarily large. An illustrating
example is depicted on Fig. 1, borrowed from [11], and originally due to
Akerlof [1]. Among many results, Kleinberg and Oren showed that any graph in
which a present-biased agent incurs significantly more cost than an optimal
agent must contain a large specific structure as a minor. This structure,
called _procrastination structure_ , is specifically the one depicted on Fig.
1.

Figure 1: Procrastination structure as displayed in [11]; Assuming
$\mathsf{x}+\beta\mathsf{c}<\mathsf{c}$, the path followed by the agent is
$\mathsf{s},\mathsf{v}_{1},\dots,\mathsf{v}_{5},\mathsf{t}$; The ratio between
the length of the path followed by the agent and the shortest
$\mathsf{s}$-$\mathsf{t}$ path can be made arbitrarily large by adding more
nodes $\mathsf{v}_{k}$ with $k\geq 5$.

In this paper, we are interested in understanding what kind of _tasks_
performed by the agent result in large cost ratio. Let us take the concrete
example of an agent willing to acquire the knowledge of a set of scientific
concepts, by reading books. Each book covers a certain number of these
concepts, and the agent’s objective is to read as few books as possible. More
generally, each book could also be weighted according to, say, its
accessibility to a general reader, or its length. The agent’s objective is
then to read a collection of books with minimum total weight. Both the weight
and the collection of concepts covered by each book are known to the agent a
priori. This scenario is obviously an instance of the (weighted) _set-cover_
problem. Let us assume, for simplicity, that the agent has access to a _time-
biased_ oracle providing it with the following information. Given the subset
of concepts already acquired by the agent when it queries the oracle, the
latter returns to the agent a set $\\{b_{0},\dots,b_{k-1}\\}$ of books
minimizing $\omega_{0}+\beta\,\sum_{i=1}^{k-1}\omega_{i}$ among all sets of
books covering the concepts yet to be acquired by the agent, where
$\omega_{0}\leq\omega_{1}\leq\dots\leq\omega_{k-1}$ are the respective weights
of the books $b_{0},\dots,b_{k-1}$. This corresponds to the procrastination
scenario in which the agent picks the easiest book to read now, and
underestimates the cost of reading the remaining books later. Then the agent
moves on by reading $b_{0}$, and querying the oracle for figuring out the next
book to read for covering the remaining uncovered concepts after having read
book $b_{0}$.

The question is: by how much the agent eventually diverges from the optimal
set of books to be read? This set-cover example fits with the framework of
Kleinberg and Oren, by defining the vertex set of the task graph as the set of
all subsets of concepts, and placing an edge $(u,v)$ of weight $\omega$ from
$u$ to $v$ if there exists a book $b$ of weight $\omega$ such that $v$ is the
union of $u$ and the concepts covered by $b$. In this setting, the agent needs
to move from the source $s=\varnothing$ to the target $t$ corresponding to the
set of all the concepts to be acquired by the agent. Under this setting, the
question can be reformulated as: under which circumstances the set-cover
problem yields a large cost ratio?

More generally, let us consider a _minimization_ problem where, for every
feasible solution $S$ of every instance of the problem, the cost $c(S)$ of $S$
can be expressed as $c(S)=\sum_{x\in S}\omega(x)$ for some weight function
$\omega$. This includes, e.g., set-cover, min-cut, minimum dominating set,
feedback-vertex set, etc. We then define the biased cost $c_{\beta}$ as

$c_{\beta}(S)=\omega(x^{*})+\beta\,c(S\smallsetminus\\{x^{*}\\}),$ (1)

where $x^{*}=\operatorname*{arg\,min}_{x\in S}\omega(x)$. Given an instance
$I$ of the minimization problem at hand, the agent aims at finding a feasible
solution $S\in I$ minimizing $c(S)$. It does so using the following present-
biased planning, where $I_{0}=I$.

#### Minimization scenario:

For $k\geq 0$, given an instance $I_{k}$, the agent computes the feasible
solution $S_{k}$ with minimum cost $c_{\beta}(S_{k})$ among all feasible
solutions for $I_{k}$. Let $x^{*}_{k}=\operatorname*{arg\,min}_{x\in
S_{k}}w(x)$. The agent stops whenever
$\\{x^{*}_{0},x^{*}_{1},\dots,x^{*}_{k}\\}$ is a feasible solution for $I$.
Otherwise, the agent moves to $I_{k+1}=I_{k}\smallsetminus x^{*}_{k}$, that
is, the instance obtained from $I_{k}$ when one assumes $x^{*}_{k}$ selected
in the solution.

This general scenario is indeed captured by the Kleinberg and Oren model, by
defining the vertex set of the graph task graph as the set of all “sub-
instances” of the instance $I$ at hand, and placing an edge $(u,v)$ of weight
$w$ from $u$ to $v$ if there exists an element $x$ of weight $\omega$ such
that $v$ results from $u$ by adding $x$ to the current solution. The issue is
to analyze how far the solution computed by the present-biased agent is from
the optimal solution. The first question addressed in this paper is therefore
the following.

######  Question 1.

For which minimization tasks a large cost ratio may appear?

In the models of Akerlof [1] and Kleinberg and Oren [11] the degree $\beta$ of
present bias is assumed to be less than one. However, there are natural
situations where underestimating the future costs does not hold. For example,
in their influential paper, Loewenstein, O’Donoghue, and Rabin [14] gave a
number of examples from a variety of domains demonstrating the prevalence of
_projection bias_. In particular, they reported an experiment by Jepson,
Loewenstein, and Ubel [9] who “asked people waiting for a kidney transplant to
predict what their quality of life would be one year later if they did or did
not receive a transplant, and then asked those same people one year later to
report their quality of life. Patients who received transplants predicted a
higher quality of life than they ended up reporting, and those who did not
predicted a lower quality of life than they ended up reporting”. In other
words, there are situations in which people may also _overestimate_ the future
costs. In the model of Kleinberg and Oren [11] overestimation bias corresponds
to the situation of putting the degree of present bias $\beta>1$. This brings
us to the second question.

######  Question 2.

Could a large cost ratio appear for minimization problems when the degree of
present bias $\beta$ is more than $1$?

Reformulating the analysis of procrastination, as stated in Question 1,
provides inspiration for tackling related problems. As a matter of fact, under
the framework of Kleinberg and Oren, procrastination is a priori associated to
_minimization_ problems. We also investigate _maximization_ problems, in which
a present-biased agent aims at, say, maximizing its revenue by making a
sequence of actions, each providing some immediate gain that the agent
maximizes while underestimating the incomes resulting from future actions. As
a concrete example, let us consider an instance of Knapsack. The agent
constructs a solution gradually by picking the item $x_{0}$ of highest value
$\omega(x_{0})$ in a feasible set $\\{x_{0},\dots,x_{k-1}\\}$ of items that is
maximizing $\omega(x_{0})+\beta\,\sum_{i=1}^{k-1}\omega(x_{i})$ for the
current sub-instance of Knapsack. In general, given an instance $I$ of a
maximisation problem, we assume that the agent applies the following present-
biased planning, with $I_{0}=I$:

#### Maximization scenario:

Given an instance $I_{k}$ for $k\geq 0$, the agent computes the feasible
solution $S_{k}$ with maximum cost $c_{\beta}(S_{k})$ among all feasible
solutions for $I_{k}$ — where the definition of $x^{*}$ in Eq. (1) is replaced
by $x^{*}=\operatorname*{arg\,max}_{x\in S}w(x)$. With
$x^{*}_{k}=\operatorname*{arg\,max}_{x\in S_{k}}w(x)$, the agent stops
whenever $\\{x^{*}_{0}$, $x^{*}_{1}$, $\dots$, $x^{*}_{k}\\}$ is an inclusion-
wise maximal feasible solution for $I$, and moves to
$I_{k+1}=I_{k}\smallsetminus x^{*}_{k}$ otherwise.

We are interested in analyzing how far the solution computed by the present-
biased agent is from the optimal solution. More generally even, we aim at
revisiting time-inconsistent planning by considering both cases $\beta<1$ and
$\beta>1$, that is, not only scenarios in which the agent underestimates the
cost of future actions, but also scenarios in which the agent _overestimates_
the cost of future actions. The last, more general question addressed in this
paper is therefore the following.

######  Question 3.

For which optimization tasks, and for which time-inconsistency planning
(underestimation, or overestimation of the future actions), the solutions
computed by a present-biased agent are far from optimal, and for which they
are close?

For all these problems, we study the _cost ratio_
$\varrho=\frac{c(S)}{\textsc{opt}}$ (resp.,
$\varrho=\frac{\textsc{opt}}{c(S)}$) where $S$ is the solution returned by the
present-biased agent, and $\textsc{opt}=c(S_{\textsc{opt}})$ is the cost of an
optimal solution for the same instance of the considered minimization (resp.,
maximization) problem.

###  1.1 Our Results

Focussing on agents aiming at solving tasks, and not just on agents aiming at
reaching targets in abstract graphs, as in the generic model in [11], allows
us not only to refine the worst-case analysis of present-biased agents, but
also to extend this analysis to scenarios corresponding to overestimating the
future costs to be incurred by the agents (by setting the degree $\beta$ of
present bias larger than 1), and to maximisation problems.

#### Minimization & underestimation.

In the original setting of minimization problems, with underestimation of
future costs (i.e., $\beta<1$), we show that the cost ratio $\varrho$ of an
agent performing $k$ steps, that is, computes a feasible solution
$\\{x^{*}_{1},\dots,x^{*}_{k}\\}$, satisfies $\varrho\leq k$. This is in
contrast to the general model in [11], in which an agent can incur a cost
ratio exponential in $k$ when returning a $k$-edge path from the source to the
target. Hence, in particular, our minimization scenarios do not produce the
worst cases examples constructed in [11], i.e., obtained by considering
travels from sources to targets in arbitrary weighted graphs.

On the other hand, we also show that a “minor structure” bearing similarities
with the one identified in [11] can be identified. Namely, if an agent incurs
a large cost ratio, then the minimization problem addressed by the agent
includes a large instance of a specific form of minimization problem.

#### Min/maximization & under/overestimation.

Interestingly, the original setting of minimization problems, with
underestimation of future costs, is far from reflecting the whole nature of
the behavior of present-biased agents. Indeed, while minimization problems
with underestimation of future costs may result in unbounded cost ratios, the
worst-case cost ratios corresponding to the three other settings can be upper
bounded, some by a constant independent of the task at hand. Specifically, we
show that:

  * •

For any minimization problem with $\beta>1$, the cost ratio is at most
$\beta$;

  * •

For any maximization problem with $\beta<1$, the cost ratio is at most
$\frac{1}{\beta}$;

  * •

For any maximization problem with $\beta>1$, the cost ratio is at most
$\beta^{c}$, where $c\leq\textsc{opt}$ is the cost of a solution constructed
by the agent.

Our results are summarized in Table 1.

| minimization | maximization
---|---|---
$\beta<1$ |  $\infty$ [11] |  $1/\beta$ [Thm 5(i)]
$\beta>1$ |  $\beta$ [Thm 4] |  $\left(1+\log\beta\right)\frac{\textsc{opt}}{\log\textsc{opt}}$ [Cor 1]
Table 1: Upper bounds on the worst case ratio between the solution cost
returned by the present-biased agent and the optimal solution opt. The symbol
$\infty$ means that the cost ratio can be arbitrarily large, independently of
the values of $\beta$, and opt.

Let us remark that, for minimization problems with $\beta>1$, as well as for
maximization problems with $\beta<1$, we have that the cost ratio is bounded
by a constant. However, for maximization problems with $\beta>1$, the cost
ratio can be exponential in the cost of the computed solution. We show that
this exponential upper bound is essentially tight.

#### Approximated evaluations.

Actually, in many settings, discrete optimization problems are hard.
Therefore, for evaluating the best feasible solution according to the biased
cost function $c_{\beta}$, an agent may have to solve computationally
intractable problems. Thus, in a more realistic scenario, we assume that,
instead of computing an optimal solution for $c_{\beta}$ at every step, the
agent computes an $\alpha$-approximate solution.

#### Fine-grained analysis.

In contrast to the general model in [11], the refined model of this paper
enables fine-grain analysis of the agents’ strategies, that is, it enables
identifying different behaviors of the agents as a function of the considered
optimisation problems. Specifically, there are natural minimization problems
for which specific bounds on the cost ratio can be established.

To illustrate the interest of focusing on optimisation tasks, we study two
tasks in detail, namely _set-cover_ and _hitting set_ , and show that they
appear to behave quite differently. For set-cover, we show that the cost ratio
is at most $d\cdot\textsc{opt}$, where $d$ is the maximum size of the sets.
For hitting set, we show that the cost ratio is at most
$d!\,(\frac{1}{\beta}\textsc{opt})^{d}$, again for $d$ equal to the maximum
size of the sets. This latter result is using the sunflower lemma of Erdős and
Rado [6].

Finally, we identify a simple restriction of the agent’s strategy, which
guarantees that the cost of the solution computed by the agent is not more
than $\beta$ times the cost of an optimal solution.

###  1.2 Related Work

Our work is directly inspired by the aforementioned contribution of Kleinberg
and Oren [10], which was itself motivated by the earlier work by Akerlof [1].
We refer to [10, 11] for a survey of earlier work on time-inconsistent
planning, with connections to procrastination, abandonment, and choice
reduction. Hereafter, we discuss solely [10], and the subsequent work. Using
their graph-theoretic framework, Kleinberg and Oren reasoned about time-
inconsistency effects. In particular, they provided a characterization of the
graphs yielding the worst-case cost-ratio, and they showed that, despite the
fact that the degree $\beta$ of present bias can take all possible values in
$[0,1]$, it remains that, for any given digraph, the collection of distinct
$s$-$t$ paths computed by present-biased agents for all degrees of present
bias is of size at most polynomial in the number of nodes. They also showed
how to improve the behavior of present-biased agents by deleting edges and
nodes, and they provided a characterization of the subgraphs supporting
efficient agent’s behavior. Finally, they analyzed the case of a collection of
agents with different degrees of present bias, and showed how to divide the
global task to be performed by the agents into “easier” sub-tasks, so that
each agent performs efficiently her sub-tasks.

As far as we are aware of, all contributions subsequent to [10], and related
to our paper, essentially remain within the same graph theoretic framework as
[10], and focus on algorithmic problems related to this framework. In
particular, Albers and Kraft [4] studied the ability to place rewards at nodes
for motivating and guiding the agent. They show hardness and inaproximability
results, and provide an approximation algorithm whose performances match the
inaproximability bound. The same authors considered another approach in [2]
for overcoming these hardness issues, by allowing not to remove edges but to
increase their weight. They were able to design a 2-approximation algorithm in
this context. Tang et al. [15] also proved hardness results related to the
placement of rewards, and showed that finding a motivating subgraph is NP-
hard. Gravin et al. [7] (see [8] for the full paper) extended the model by
considering the case where the degree of present bias may vary over time,
drawn independently at each step from a fixed distribution. In particular,
they described the structure of the worst-case graph for any distribution, and
derived conditions on this distribution under which the worst-case cost ratio
is exponential or constant.

Kleinberg, Oren, and Raghavan [12, 13] revisited the model in [10]. In [12],
they were considering agents estimating erroneously the degree $\beta$ of
present bias, either underestimating or overestimating that degree, and
compared the behavior of such agents with the behavior of “sophisticated”
agents who are aware of their present-biased behavior in future and take this
into account in their strategies. In [13], they extended the model by
considering not only agents suffering from present-biases, but also from
_sunk-cost_ bias, i.e., the tendency to incorporate costs experienced in the
past into one’s plans for the future. Albers and Kraft [3] considered a model
with uncertainty, bearing similarities with [12], in which the agent is solely
aware that the degree of present bias belongs to some set $B\subseteq(0,1]$,
and may or may not vary over time.

##  2 Procrastination under minimization problems

This section includes a formal definition of inconsistent planning by present-
biased agents, and describes two extreme scenarios: one in which a present-
biased agent constructs worst case plannings, and one in which the plannings
generated by a present-biased agent are close to optimal.

###  2.1 Model and Definition

We consider minimization problems defined as triples $(\mathcal{I},F,c)$,
where $\mathcal{I}$ is the set of instances (e.g., the set of all graphs), $F$
is a function that returns the set $F(I)$ of feasible solutions for every
instance $I\in\mathcal{I}$ (e.g., the set of all edge-cuts of any given
graph), and $c$ is a non-negative function returning the cost $c(I,S)$ of
every feasible solution $S\in F(I)$ of every instance $I\in\mathcal{I}$ (e.g.,
the number of edges in a cut). We focus solely on optimization problems for
which

  * (i)

a finite ground set $\mathcal{S}_{I}\neq\varnothing$ is associated to every
instance $I$,

  * (ii)

every feasible solution for $I$ is a set $S\subseteq\mathcal{S}_{I}$, and

  * (iii)

$c(I,S)=\sum_{x\in S}\omega(x)$ where $\omega:\mathcal{S}_{I}\to\mathbb{N}$ is
a weight function.

Moreover, we enforce two properties that are satisfied by classical
minimization problems. Specifically we assume that:

  * •

All considered problems are closed downward, that is, for every considered
minimization problem $(\mathcal{I},F,c)$, every $I\in\mathcal{I}$, and every
$x\in\mathcal{S}_{I}$, the instance $I\smallsetminus\\{x\\}$ defined by the
feasible solutions $S\smallsetminus\\{x\\}$, for every $S\in F(I)$, is in
$\mathcal{I}$ with the same weight function $\omega$ as for $I$. This
guarantees that an agent cannot be stuck after having performed some task $x$,
as the sub-problem $I\smallsetminus\\{x\\}$ remains solvable for every $x$.

  * •

All considered feasible solutions are closed upward, that is, for every
minimization problem $(\mathcal{I},F,c)$, and every $I\in\mathcal{I}$,
$\mathcal{S}_{I}$ is a feasible solution, and, for every $S\in F(I)$, if
$S\subseteq S^{\prime}\subseteq\mathcal{S}_{I}$ then $S^{\prime}\in F(I)$.
This guarantees that an agent performing a sequence of tasks
$x_{0},x_{1},\dots$ eventually computes a feasible solution.

Inconsistent planning can be rephrased in this framework as follows.

#### Inconsistent Planning.

Let $\beta<1$ be a positive constant. Given a minimization problems
$(\mathcal{I},F,c)$, the biased cost $c_{\beta}$ satisfies
$c_{\beta}(S)=\omega(x)+\beta\,c(S\smallsetminus\\{x\\})$ for every feasible
solution $S$ of every instance $I\in\mathcal{I}$, where
$x=\operatorname*{arg\,min}_{y\in S}\omega(y)$. Given an instance $I$, the
agent aims at finding a feasible solution $S\in I$ by applying a present-based
planning defined inductively as follows. Let $I_{0}=I$. For every $k\geq 0$,
given the instance $I_{k}$, the agent computes a feasible solution $S_{k}$
with minimum cost $c_{\beta}(S_{k})$ among all feasible solutions for $I_{k}$.
Let $x_{k}=\operatorname*{arg\,min}_{y\in S_{k}}\omega(y)$. The agent stops
whenever $\\{x_{0},x_{1},\dots,x_{k}\\}$ is a feasible solution for $I$.
Otherwise, it carries on the construction of the solution by considering
$I_{k+1}=I_{k}\smallsetminus\\{x_{k}\\}$.

Observe that inconsistent planning terminates. Indeed, since the instances of
the considered problem $(\mathcal{I},F,c)$ are closed downwards,
$I_{k}=I\smallsetminus\\{x_{0},\dots,x_{k-1}\\}\in\mathcal{I}$ for every
$k\geq 0$, i.e., inconsistent planning is well defined. Moreover, since the
feasible solutions are closed upward, there exists $k\geq 0$ such that
$\\{x_{0},x_{1},\dots,x_{k}\\}$ is a feasible solution for $I$.

The _cost_ of inconsistent planning is defined as the ratio
$\varrho=\frac{c(S)}{\textsc{opt}}$ where $S=\\{x_{0},x_{1},\dots,x_{k}\\}$ is
the solution returned by the agent, and $\textsc{opt}=c(S_{\textsc{opt}})$ is
the cost of an optimal solution $S_{\textsc{opt}}$ for the same instance of
the considered minimization problem.

#### Approximated evaluation.

It can happen that the considered minimization problem is computationally
hard, say NP-hard, and the agent is unable to compute a feasible solution $S$
of minimum cost $c_{\beta}(S)$ exactly. Then the agent can pick an approximate
solution instead. For this situation, we modify the above strategy of the
agent as follows. Assume that the agent has access to an
$\alpha$-approximation algorithm $\mathcal{A}$ that, given an instance $I$,
computes a feasible solution $S^{*}$ to the instance such that
$c_{\beta}(S^{*})\leq\alpha\min c_{\beta}(S)$, where minimum is taken over all
feasible solution $S$ to $I$. For simplicity, we assume throughout the paper
that $\alpha\geq 1$ is a constant, but our results can be generalized for the
case, where $\alpha$ is a function of the input size or opt.

Again, the agent uses an inductive scheme to construct a solution. Initially,
$I_{0}=I$. For every $k\geq 0$, given the instance $I_{k}$, the agent computes
a feasible solution $S_{k}$ of cost at most $\alpha\min c_{\beta}(S)$, where
the minimum is taken over all feasible solutions $S$ of $I_{k}$. Then, exactly
as before, the agent finds $x_{k}=\operatorname*{arg\,min}_{y\in
S_{k}}\omega(y)$. If $\\{x_{0},x_{1},\dots,x_{k}\\}$ is a feasible solution
for $I$, then the agent stops. Otherwise, we set
$I_{k+1}=I_{k}\smallsetminus\\{x_{k}\\}$ and proceed. The _$\alpha$
-approximative cost_ of inconsistent planning is defined as the ratio
$\varrho_{\alpha}=\frac{c(S)}{\textsc{opt}}$ where
$S=\\{x_{0},x_{1},\dots,x_{k}\\}$. Clearly, the $1$-approximative cost
coincides with $\varrho$.

###  2.2 Worst-Case Present-Biased Planning

We start with a simple observation. Given a feasible solution $S$ for an
instance $I$ of a minimization problem, we say that $x\in S$ is _superfluous_
in $S$ if $S\smallsetminus\\{x\\}$ is also feasible for $I$. The ability for
the agent to make superfluous choices yields trivial scenarios in which the
cost ratio $\varrho$ can be arbitrarily large. This is for instance the case
of an instance of set-cover, defined as one set $y=\\{1,\dots,n\\}$ of weight
$c>1$ covering all elements, and $n$ sets $x_{i}=\\{i\\}$, each of weight 1,
for $i=1,\dots,n$. Every solution $S_{i}=\\{x_{i},y\\}$ is feasible, for
$i=1,\dots,n$, and satisfies $c_{\beta}(S_{i})=1+\beta c$. As a result,
whenever $1+\beta c<c$, the present-biased agent constructs the solution
$S=\\{x_{1},\dots,x_{n}\\}$, which yields a cost ratio $\varrho=n/c$, which
can be made arbitrarily large as $n$ grows. Instead, if the agent is bounded
to avoid superfluous choices, that is, to systematically choose _minimal_
feasible solutions, then only the feasible solutions $\\{y\\}$ and
$\\{x_{1},\dots,x_{n}\\}$ can be considered. As a result, the agent will
compute the optimal solution $S_{\textsc{opt}}=\\{y\\}$ if $c<1+\beta(n-1)$.

Unfortunately, bounding the agent to systematically choose _minimal_ feasible
solutions, i.e., solutions with no superfluous elements, is not sufficient to
avoid procrastination. That is, it does not prevent the agent from computing
solution with high cost ratio. This is for instance the case of another
instance of set-cover, that we denote by $I_{SC}^{(n)}$ for further
references.

#### Set-cover instance $I_{SC}^{(n)}$:

specified by $2n$ subsets of $\\{1,\dots,n\\}$ defined as $x_{i}=\\{i\\}$ with
weights $1$, and $y_{i}=\\{i,\dots,n\\}$ with weight $c>1$, for $i=1,\dots,n$.

The minimal feasible solutions of $I_{SC}^{(n)}$ are $\\{y_{1}\\}$ of weight
$c$, $\\{x_{1},\dots,x_{i},y_{i+1}\\}$ of weight $i+c$ for $i=1,\dots,n-1$,
and $\\{x_{1},\dots,x_{n}\\}$ of weight $n$. Whenever $1+\beta c<c$, a time-
biased agent bounded to make non-superfluous choices only yet constructs the
solution $\\{x_{1},\dots,x_{n}\\}$ which yields a cost ratio $\varrho=n/c$,
which can be made arbitrarily large as $n$ grows. We need the following lemma
about biased solutions for minimization problems.

######  Lemma 1.

Let $\alpha\geq 1$ and let $S^{*}$ be a feasible solution for minimization
problem, satisfying $c_{\beta}(S^{*})\leq\alpha\min c_{\beta}(S)$, where the
minimum is taken over all feasible solutions. Then

  * (i)

$\omega(x)\leq\alpha\cdot\textsc{opt}$ for $x=\operatorname*{arg\,min}_{y\in
S^{*}}\omega(y)$, and

  * (ii)

$c(S^{*})\leq\frac{\alpha}{\beta}\textsc{opt}$.

###### Proof.

Let $S$ be an optimum solution. As $\beta<1$, it follows that
$\omega(x)\leq\omega(x)+\beta\cdot\omega(S^{*}\setminus\\{x\\})=c_{\beta}(S^{*})\leq\alpha\cdot
c_{\beta}(S)\leq\alpha\cdot c(S)=\alpha\cdot\textsc{opt},$ and this proves
(i). To show (ii), note that
$c(S^{*})=\omega(x)+\omega(S^{*}\setminus\\{x\\})=\frac{1}{\beta}(\beta\omega(x)+\beta\omega(S^{*}\setminus\\{x\\})),$
from which it follows that
$c(S^{*})\leq\frac{1}{\beta}(\omega(x)+\beta\omega(S^{*}\setminus\\{x\\}))=\frac{1}{\beta}c_{\beta}(S^{*})\leq\frac{\alpha}{\beta}c_{\beta}(S)\leq\frac{\alpha}{\beta}c(S)=\frac{\alpha}{\beta}\textsc{opt},$
which completes the proof. ∎

Lemma 1 has a simple consequence that also can be derived from the results of
Gravin et al. [8, Claim 5.1], that we state as a theorem despite its
simplicity, as it illustrates one major difference between our model and the
model in [11].

######  Theorem 1.

For every $\alpha\geq 1$ and every minimization problem, the
$\alpha$-approximative cost ratio $\varrho_{\alpha}$ cannot exceed
$\alpha\cdot k$ where $k$ is the number of steps performed by the agents to
construct the feasible solution $\\{x_{1},\dots,x_{k}\\}$ by following the
time-biased strategy.

###### Proof.

By Lemma 1(i), at any step $i\geq 1$ of the construction, the agent adds an
element $x_{i}\in\mathcal{S}_{I}$ in the current partial solution, and this
element satisfies
$\omega(x_{i})\leq\alpha\,c_{\beta}(S_{\textsc{opt}})\leq\alpha\,c(S_{\textsc{opt}})=\alpha\cdot\textsc{opt}.$
Therefore, if the agent computes a solution $\\{x_{1},\dots,x_{k}\\}$, then
the $\alpha$-approximative cost ratio for this solution satisfies
$\varrho_{\alpha}=\sum_{i=1}^{k}\omega(x_{i})/\textsc{opt}\leq\alpha\,k,$ as
claimed. ∎

#### Remark.

The bound in Theorem 1 is in contrast to the general model in [11], in which
an agent performing $k$ steps can incur a cost ratio exponential in $k$. This
is because the model in [11] enables to construct graphs with arbitrary
weights. In particular, in a graph such as the one depicted on Fig. 1, one can
set up weights such that the weight of $(v_{1},t)$ is a constant time larger
than the weight of $(s,t)$, the weight of $(v_{2},t)$ is in turn a constant
time larger than the weight of $(v_{1},t)$, etc., and still a present-biased
agent starting from $s$ would travel via $v_{1},v_{2},\dots,v_{k}$ before
reaching $t$. In this way, the sum of the weights of the edges traversed by
the agent may become exponential in the number of traversed edges. This
phenomenon does not occur when focussing on minimization tasks. Indeed, given
a partial solution, the cost of completing this solution into a global
feasible solution cannot exceed the cost of constructing a global feasible
solution from scratch.

It follows from Theorem 1 that $I_{SC}^{(n)}$ is a worst-case instance.
Interestingly, this instance fits with realistic procrastination scenarios in
which the agent has to perform a task (e.g., learning a scientific topic $T$)
by either energetically embracing the task (e.g., by reading a single thick
book on topic $T$), or starting first by an easier subtask (e.g., by first
reading a digest of a subtopic of topic $T$), with the objective of working
harder later, but underestimating the cost of this postponed hard work. The
latter strategy may result in procrastination, by performing a very long
sequence of subtasks $x_{1},x_{2},\dots,x_{n}$.

In fact, $I_{SC}^{(n)}$ appears to be _the essence of procrastination_ in the
framework of minimization problems. Indeed, we show that if the cost ratio is
large, then the considered instance $I$ contains an instance of the form
$I_{SC}^{(n)}$ with large $n$. More precisely, we say that an instance $I$
contains an instance $J$ as a _minor_ if the ground set $\mathcal{S}_{J}$
associated to $J$ is a collection of subsets of the ground set
$\mathcal{S}_{I}$ associated to $I$, that is $\mathcal{S}_{J}\subseteq
2^{\mathcal{S}_{I}},$ and, for every $\bar{S}\subseteq\mathcal{S}_{J}$,
$\bar{S}$ is feasible for $J$ if and only if
$S=\bigcup_{\bar{x}\in\bar{S}}\bar{x}\;\;\mbox{is feasible for $I$.}$
Moreover, the weight function $\bar{\omega}$ for the elements of
$\mathcal{S}_{J}$ must be induced by the one for $\mathcal{S}_{I}$ as
$\bar{\omega}(\bar{x})=\sum_{x\in\bar{x}}\omega(x)$ for every
$\bar{x}\in\mathcal{S}_{J}$. Let $J^{(n)}$ be any instance of a minimization
problem such that its associated ground set is
$\mathcal{S}_{J^{(n)}}=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\},$
and the set of feasible solutions for $J^{(n)}$ is
$F(J^{(n)})=\big{\\{}\\{y_{1}\\},\\{x_{1},y_{2}\\},\\{x_{1},x_{2},y_{3}\\},\dots,\\{x_{1},\dots,x_{n-1},y_{n}\\},\\\
\\{x_{1},\dots,x_{n}\\}\big{\\}}.$ The following result sheds some light on
_why_ the procrastination structure of Fig. 1 pops up.

######  Theorem 2.

Let $I$ be an instance of a minimization problem for which the present-biased
agent with parameter $\beta\in(0,1)$ computes a solution for $I$ with cost
$\alpha\cdot\textsc{opt}(I)$ for some $\alpha>1$. Then $I$ contains $J^{(n)}$
as a minor for some $n\geq\alpha$, and the present-biased agent with parameter
$\beta$ computes a solution for $J^{(n)}$ with cost
$\alpha\cdot\textsc{opt}(J^{(n)})$.

###### Proof.

Let $S=\\{x_{1},\dots,x_{n}\\}$ be the final solution selected by the present-
biased agent for $I$, and let $\omega$ be the weight function on the set
$\mathcal{S}_{I}$ associated to $I$. We have
$\sum_{i=1}^{n}\omega(x_{i})=\alpha\,\textsc{opt}(I)$. For every
$i\in\\{1,\dots,n\\}$, let us denote by
$\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i}\\})$ the cost of an optimal
solution for the instance $I\smallsetminus\\{x_{1},\dots,x_{i}\\}$, and by
$S_{\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i}\\})}$ a corresponding
optimal solution. For $i=0$,
$S_{\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i}\\})}$ is an optimal
solution for $I$. For $i=1,\dots,n$, we define

$\bar{x}_{i}=\\{x_{i}\\},\;\mbox{and}\;\bar{y}_{i}=S_{\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i-1}\\})}.$

Let $J$ be the instance with ground set
$\\{\bar{x}_{1},\dots,\bar{x}_{n}\\}\cup\\{\bar{y}_{1},\dots,\bar{y}_{n}\\},$
and feasible solutions

$\\{\bar{y}_{1}\\},\\{\bar{x}_{1},\bar{y}_{2}\\},\dots,\\{\bar{x}_{1},\dots,\bar{x}_{n-1},\bar{y}_{n}\\},\\{\bar{x}_{1},\dots,\bar{x}_{n}\\}.$

Note that $\bar{x}_{i}\neq\bar{x}_{j}$ for every $i\neq j$, because $x_{i}\neq
x_{j}$ for every $i\neq j$. Also, for every $i\in\\{1,\dots,n-1\\}$ and
$j\in\\{1,\dots,n\\}$, $\bar{x}_{i}\neq\bar{y}_{j}$, because otherwise the
sequence constructed by the time-biased agent for $I$ would stop at $x_{k}$
with $k<n$. Therefore, we have $J=J^{(n)}$, and, since
$\omega(x_{i})\leq\textsc{opt}(I)$ for every $i=1,\dots,n$, $n\geq\alpha$
holds.

For analyzing the behavior of a present-biased agent with parameter $\beta$
acting on $J$, let us assume that $k$ steps were already performed by the
agent, with $0\leq k<n$, resulting in constructing the partial solution
$\\{\bar{x}_{1},\dots,\bar{x}_{k}\\}$. (For $k=0$, this partial solution is
empty). The feasible solutions for
$J_{k}=J\smallsetminus\\{\bar{x}_{1},\dots,\bar{x}_{k}\\}$ are

$\\{\bar{y}_{1}\\},\dots,\\{\bar{y}_{k+1}\\},\\{\bar{x}_{k+1},\bar{y}_{k+2}\\},\dots,\\{\bar{x}_{k+1},\dots,\bar{x}_{n-1},\bar{y}_{n}\\},\\{\bar{x}_{k+1},\dots,\bar{x}_{n}\\}.$

Note that, for every $i\in\\{1,\dots,n\\}$,
$\bar{\omega}(\bar{x}_{i})=\omega(x_{i})$, and
$\bar{\omega}(\bar{y}_{i})=\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i-1}\\})$.
We claim that $\bar{x}_{k+1}$ is the next element chosen by the agent. Indeed,
note first that $\bar{\omega}(\bar{x}_{k+1})\leq\bar{\omega}(\bar{y}_{k+2})$,
as, otherwise, we would get
$\omega(x_{k+1})>\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{k+1}\\})$,
contradicting the choice of $x_{k+1}$ by the agent performing on $I$. As a
consequence,

$c_{\beta}(\\{\bar{x}_{k+1},\bar{y}_{k+2}\\})=\bar{\omega}(\bar{x}_{k+1})+\beta\,\bar{\omega}(\bar{y}_{k+2}).$

It follows from the above that, for every $j=1,\dots,k+1$,
$c_{\beta}(\\{\bar{y}_{j}\\})\geq
c_{\beta}(\\{\bar{x}_{k+1},\bar{y}_{k+2}\\})$, as the reverse inequality would
contradict the choice of $x_{k+1}$ by the agent performing on $I$. For the
same reason, for every $\ell\in\\{k+1,\dots,n-1\\}$, and every
$i\in\\{k+1,\dots,\ell\\}$, we have

$c_{\beta}(\\{\bar{x}_{k+1},\bar{y}_{k+2}\\})\leq\bar{\omega}(\bar{x}_{i})+\beta\Big{(}\sum_{j\in\\{k+1,\dots,\ell\\}\smallsetminus\\{i\\}}\bar{\omega}(\bar{x}_{j})+\bar{\omega}(\bar{y}_{\ell+1})\Big{)}$

and

$c_{\beta}(\\{\bar{x}_{k+1},\bar{y}_{k+2}\\})\leq\bar{\omega}(\bar{y}_{\ell+1})+\beta\sum_{j\in\\{k+1,\dots,\ell\\}}\bar{\omega}(\bar{x}_{j}).$

As a consequence, the present-biased agent performing on $J$ picks
$\bar{x}_{k+1}$ at step $k+1$, as claimed. The cost of the solution computed
by the agent is
$\sum_{i=1}^{n}\bar{\omega}(\bar{x}_{i})=\sum_{i=1}^{n}w(x_{i})=\alpha\,\textsc{opt}(I)$.
On the other hand, by construction,
$\textsc{opt}(J)=\bar{\omega}(\bar{y}_{1})=\textsc{opt}(I)$. The cost ratio of
the solution computed by the agent for $J$ is thus $\alpha$, which completes
the proof. ∎

###  2.3 Quasi-Optimal Present-Biased Planning

In the previous section, we have observed that forcing the agent to avoid
superfluous choices, by picking minimal feasible solutions only, does not
prevent it from constructing solutions that are arbitrarily far from the
optimal. In this section, we show that, by enforcing consistency in the
sequence of partial solutions constructed by the agent, such bad behavior does
not occur. More specifically, given a feasible solution $S$ for $I$, we say
that $x$ is _inconsistent_ with $S$ if $x\notin S$. The following result shows
that inconsistent choices is what causes high cost ratio.

######  Theorem 3.

An agent using an $\alpha$-approximation algorithm bounded to avoid
inconsistent choices with respect to the feasible solutions used in the past
for constructing the current partial solution returns an
$\alpha/\beta$-approximation of the optimal solution. This holds independently
from whether the agent makes superfluous choices or not.

###### Proof.

Let $I$ be an instance of a minimization problem $(\mathcal{I},F,c)$. Let
$S=\\{x_{0},\dots,x_{k}\\}$ be the solution constructed by the agent for $I$,
where $x_{i}$ is the element computed by the agent at step $i$, for
$i=0,\dots,k$. Let $S_{i}$ be the feasible solution of
$I_{i}=I\smallsetminus\\{x_{0},\dots,x_{i-1}\\}$ considered by the agent at
step $i$. Since the agent is bounded to avoid any inconsistent choices with
respect to the past, we have $x_{i}\in\cap_{j=0}^{i}S_{j}$ for every
$i=0,\dots,k$ because $x_{i}\notin S_{j}$ for some $j<i$ would be an
inconsistent choice. It follows that $S\subseteq S_{0}$. Therefore, $c(S)\leq
c(S_{0})$. Since the agent uses an $\alpha$-approximation algorithm, by Lemma
1(ii), $c(S_{0})\leq\frac{\alpha}{\beta}\textsc{opt}$ and the claim follows. ∎

##  3 Min/maximization with under/overestimation

We first investigate the cost ratio for minimization problems for the case
when $\beta>1$. Similar bound was obtained by Kleinberg et al. (see [12,
Theorem 2.1]). However, their theorem is about sophisticated agents and cannot
be applied in our case directly.

######  Theorem 4.

Solutions computed by present-biased agents satisfy the following: For any
minimization problem with $\beta>1$, the cost ratio is at most $\beta$.

###### Proof.

For the proof of the theorem it is convenient to switch to the original graph-
theoretic model of Kleinberg and Oren [11]. Note that the task graphs
corresponding to optimization problems are, in fact, directed acyclic graphs.
Hence, we only consider task graphs of this type to avoid dealing with paths
of maximum length in the presence of cycles.

Let $G$ be a directed acyclic graph (DAG) with a source $s$. Let also
$\omega\colon E(G)\rightarrow\mathbb{N}$ be a weight function. The aim of the
agent is to go from the source $s$ to a sink $t$ of $G$ making present-biased
decisions on each step. We assume that $G$ has an $s$-$t$ path. Let $\beta$ be
a positive constant distinct from 1. Let $c^{\min}(x)$ be the minimum length
of an $x$-$t$ path.

We suppose that the agent is equipped with an algorithm $\mathcal{A}$ that,
given a vertex $v\in V(G)$, finds a vertex $x^{*}\in N_{G}^{+}(v)$ such that

$\omega(vx^{*})+\beta\cdot c^{\min}(x^{*})=\min_{x\in
N_{G}^{+}(v)}(\omega(vx)+\beta\cdot c^{\min}(x)).$

The agent constructs an $s$-$t$ path as follows: if the agent occupies a
vertex $v\neq t$, then he makes the present-biased $\alpha$-approximate
estimation of the length of a shortest $v$-$t$ path and moves to $x^{*}$. Note
that since $G$ is a DAG, the agent would eventually arrive to $t$.

We denote by $\textsc{cost}^{\min}(v)$ the length of a $v$-$t$ path
constructed by the agent from $v$. Notice that this value is not uniquely
defined as the agent may be able to choose distinct vertices that provide
$\alpha$-approximate present-biased evaluations but could give distinct
lengths for the constructed paths. Then the proof of the theorem is implied by
the following claim.

######  Claim 3.1.

Let $G$ be a weighted DAG with a weigh function $\omega\colon
E(G)\rightarrow\mathbb{N}$ and a sink $t$. Then for every $v\in V(G)$, if
$\beta>1$, then $\textsc{cost}^{\min}(v)\leq\beta\cdot c^{\min}(v)$.

The claim is trivial if $v=t$. Assume that $v\neq t$, and that the claim holds
for every out-neighbor $x$ of $v$. Assume that $x^{*}\in N_{G}^{+}(v)$ is
computed by $\mathcal{A}$, and let

$y=\operatorname*{arg\,min}_{x\in N_{G}^{+}(v)}(\omega(vx)+c^{\min}(x)).$

That is, there is a shortest $v$-$t$ path that goes through $y$.

By induction, we have that

$\textsc{cost}^{\min}(x^{*})\leq\beta\cdot c^{\min}(x^{*}).$

It follows that

$\displaystyle\textsc{cost}^{\min}(v)=$
$\displaystyle\;\omega(vx^{*})+\textsc{cost}^{\min}(x^{*})\leq\;\omega(vx^{*})+\beta\cdot
c^{\min}(x^{*})$ $\displaystyle\leq$ $\displaystyle\omega(vx^{*})+\beta\cdot
c^{\min}(x^{*})=\min_{x\in N_{G}^{+}(v)}(\omega(vx)+\beta\cdot c^{\min}(x))$
$\displaystyle\leq$ $\displaystyle\omega(vy)+\beta\cdot
c^{\min}(y)\leq\;\beta\cdot\omega(vy)+\beta\cdot c^{\min}(y)\leq\;\beta\cdot
c^{\min}(v).$

The last inequality completes the proof of the claim, and of the theorem. ∎

Next, we consider maximization problems. The formalism for these variants can
be set up in a straightforward manner by adapting the framework displayed in
Section 2.1. We establish the following worst-case bounds.

######  Theorem 5.

Solutions computed by present-biased agents satisfy the following:

  * (i)

For any maximization problem with $\beta<1$, the cost ratio is at most
$\frac{1}{\beta}$;

  * (ii)

For any maximization problem with $\beta>1$, the cost ratio is at most
$\beta^{c}$, where $c\leq\textsc{opt}$ is the cost of a solution constructed
by the agent.

###### Proof.

As in the proof of Theorem 4, we switch to the graph-theoretic model of
Kleinberg and Oren [11]. Let $G$ be a directed acyclic graph (DAG) with a
source $s$ and weight function $\omega\colon E(G)\rightarrow\mathbb{N}$. The
agent aims to go from the source $s$ to a sink $t$ of $G$ making present-
biased decisions on each step. We assume that $G$ has an $s$-$t$ path. Let
$\beta$ be a positive constant distinct from 1, and let $c^{\max}(x)$ be the
maximum length of an $x$-$t$ path.

Let $\alpha\in(0,1]$. As in Theorem 4, we assume that the agent is equipped
with an algorithm $\mathcal{A}$ that, given a vertex $v\in V(G)$, finds a
vertex $x^{*}\in N_{G}^{+}(v)$ such that

$\omega(vx^{*})+\beta\cdot c^{\max}(x^{*})=\max_{x\in
N_{G}^{+}(v)}(\omega(vx)+\beta\,c^{\max}(x)).$

Using $\mathcal{A}$, the agent located in vertex $v\neq t$ constructs an
$s$-$t$ path as follows: the agent computes the present-biased
$\alpha$-approximate estimation of the length of a longest $v$-$t$ and moves
to $x^{*}$. We denote by $\textsc{cost}^{\max}(v)$ the length of a $v$-$t$
path constructed by the agent from $v$.

######  Claim 3.2.

Let $G$ be a weighted DAG with a weigh function $\omega\colon
E(G)\rightarrow\mathbb{N}$ and a sink $t$. Then for every $v\in V(G)$,

  * (i)

if $\beta<1$, then $\textsc{cost}^{\max}(v)\geq\beta\,c^{\max}(v)$,

  * (ii)

if $\beta>1$, then
$c^{\max}(v)\leq\textsc{cost}^{\max}(v)\,{\beta}^{\textsc{cost}^{\max}(v)}$.

As in Theorem 4, we prove the claim by induction. The claim is trivial if
$v=t$. Assume that $v\neq t$, and that the claim holds for every out-neighbor
$x$ of $v$. Let $x^{*}$ be the vertex computed by $\mathcal{A}$ and let

$y=\operatorname*{arg\,max}_{x\in N_{G}^{+}(v)}(\omega(vx)+c^{\max}(x)).$

That is, there is a longest $v$-$t$ path that goes through $y$.

To show (i), we use the inductive assumption that

$\textsc{cost}^{\max}(x^{*})\geq\beta\,c^{\max}(x^{*}).$

We have

$\displaystyle\textsc{cost}^{\max}(v)=$
$\displaystyle\;\omega(vx^{*})+\textsc{cost}^{\max}(x^{*})\geq\;\omega(vx^{*})+\beta\,c^{\max}(x^{*})$
$\displaystyle=$ $\displaystyle\max_{x\in
N_{G}^{+}(v)}(\omega(vx)+\beta\,c^{\max}(x))\geq\;\omega(vy)+\beta\,c^{\max}(y)$
$\displaystyle\geq\;$
$\displaystyle\beta\,\omega(vy)+\beta\,c^{\max}(y)\geq\;\beta\,c^{\max}(v).$

To prove (ii), we assume that the following inductive assumption holds:

$c^{\max}(x^{*})\leq\textsc{cost}^{\max}(x^{*})\,\beta^{\textsc{cost}^{\max}(x^{*})}.$

It follows that

$\displaystyle c^{\max}(v)=$
$\displaystyle\;\omega(vy)+c^{\max}(y)\leq\;\omega(vy)+\beta\cdot c^{\max}(y)$
$\displaystyle\leq$ $\displaystyle\;\max_{x\in N_{G}(v)}(\omega(vx)+\beta\cdot
c^{\max}(x))\leq\;\omega(vx^{*})+\beta\cdot c^{\max}(x^{*})$
$\displaystyle\leq$
$\displaystyle\;\omega(vx^{*})+\beta\cdot\textsc{cost}^{\max}(x^{*})\,\beta^{\textsc{cost}^{\max}(x^{*})}$
$\displaystyle\leq$
$\displaystyle\;\beta^{\textsc{cost}^{\max}(x^{*})+1}(\omega(vx^{*})+\textsc{cost}^{\max}(x^{*}))=\;\textsc{cost}^{\max}(v)\,\beta^{\textsc{cost}^{\max}(x^{*})+1}$
$\displaystyle\leq$
$\displaystyle\;\textsc{cost}^{\max}(v)\,\beta^{\textsc{cost}^{\max}(v)}.$

This last inequality completes the proof of Claim 3.2, which immediately gives
the bounds for the $\alpha$-approximate cost ratio claimed in the statement of
the theorem. ∎

We also can write the bound for the cost ratio for $\beta>1$ in the following
form to obtain the upper bound that depends only on the value of opt.

######  Corollary 1.

For any maximization problem with $\beta>1$, the cost ratio is at most
$(1+\log\beta)\frac{\textsc{opt}}{\log\textsc{opt}}$.

###### Proof.

Let $c$ be the cost of a solution constructed by the agent. By Theorem 5,
$\textsc{opt}\leq c\beta^{c}$. Therefore, $\log\textsc{opt}\leq\log
c+c\log\beta\leq\big{(}1+\log\beta)c,$ and
$\frac{\textsc{opt}}{c}\leq(1+\log\beta)\frac{\textsc{opt}}{\log\textsc{opt}}.$
∎

For minimization problems with $\beta>1$, and maximization problems with
$\beta<1$, we have that the cost ratio is bounded by a constant. This differs
drastically with the case of maximization problems with $\beta>1$, when the
cost ratio is still bounded but the bound is exponential. This exponential
upper bound is however essentially tight, in the sense that the exponent
cannot be avoided.

######  Theorem 6.

There are maximization problems for which a present-biased agent with
$\beta>1$ returns a solution whose cost ratio is at least
$\frac{1}{c}\,\beta^{c-1}$, where $c$ is the cost of the solution constructed
by the agent.

###### Proof.

Let us consider the maximum independent set problem. In this problem, we are
given a weighted graph $G$, and the task is to find an independent set of
maximum weight. Let $k$ be a positive integer. We construct the graph $G_{k}$
as follows (see Fig. 2):

  * •

construct $k+1$ vertices $x_{0},\ldots,x_{k}$, and make them pairwise
adjacent,

  * •

construct $k$ vertices $y_{1},\ldots,y_{k}$,

  * •

for each $i\in\\{1,\ldots,k\\}$, make $y_{i}$ adjacent to
$x_{i},x_{i+1},\ldots,x_{k}$.

To define the weights, let $\beta\geq 2$. We set $\omega(y_{i})=1$ for every
$i\in\\{1,\ldots,k\\}$, and $\omega(x_{i})=\beta^{i}$ for every
$i\in\\{0,\ldots,k\\}$.

clique$y_{1}$$y_{2}$$y_{3}$$y_{4}$$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$\beta^{0}$$\beta^{1}$$\beta^{2}$$\beta^{3}$$\beta^{4}$$1$$1$$1$$1$

Figure 2: Construction of $G_{k}$ for $k=4$.

Since $X=\\{x_{0},\ldots,x_{k}\\}$ is a clique, any independent set has at
most one vertex in $X$. Therefore, the family of sets

$S_{i}=\\{x_{i}\\}\cup\\{y_{i+1},\ldots,y_{k}\\}$

for $i\in\\{0,\ldots,k\\}$ form the family of maximal independent sets.
Because $\beta\geq 2$, it is straightforward to verify that the single-vertex
set $S_{k}=\\{x_{k}\\}$ is an independent set of maximum weight $\beta^{k}$,
that is, $\textsc{opt}=\beta^{k}$. Observe that the biased cost of this set is
$\beta^{k}$ as well.

From the other side, the biased cost of $S_{k-1}$ is

$\omega(y_{k})+\beta\cdot\omega(x_{k-1})=1+\beta\cdot\beta^{k-1}=1+\beta^{k}>\beta^{k}.$

Hence, the agent would prefer to select $y_{k}$ at the first iteration. At the
next iteration, the agent considers the graph obtained from $G_{k}$ by the
deletion of $y_{k}$ and its neighborhood, that is, $G_{k-1}$. Applying the
same arguments inductively, we conclude that the agent will end up with the
set $S_{0}=\\{x_{0},y_{1},\ldots,y_{k}\\}$ with $\omega(S_{0})=k+1$. We obtain
that $\textsc{opt}=\beta^{c-1}$, where $c$ is the cost of a solution
constructed by the agent. ∎∎

#### Remark.

An example similar to the one in the proof of Theorem 6 can be constructed for
the knapsack problem. Recall that in this problem, we are given $n$ objects
with positive integer _values_ $v_{i}$, and _weights_ $w_{i}$, for
$i\in\\{1,\ldots,n\\}$, and $W\in\mathbb{N}$. the task is to find a set of
objects $S\subseteq\\{1,\ldots,n\\}$ of maximum value with the total weight at
most $W$. Let $k$ be a positive integer. We let $n=2k+1$, $W=n$ and $\beta\geq
2$. We define

$v_{i}=\beta^{k+1-i},$

and

$w_{i}=W-(i-1)$

for every $i\in\\{1,\ldots,k+1\\}$, and we set $v_{i}=1$ and $w_{i}=1$ for
$i\in\\{k+2,\ldots,n\\}$. Using the same arguments as for the maximum
independent set problem, we obtain that the optimum solution has cost
$\beta^{k}$ while a present-biased agent would select a solution of cost
$k+1$.

##  4 Covering and hitting problems

In Section 2.2, we have seen several instances of the set-cover problem whose
cost ratio cannot be bounded by any function of opt. The same obviously holds
for the hitting-set problem. Recall that an instance of hitting-set is defined
by a collection $\Sigma$ of subsets of a finite set $V$, and the objective is
to find the subset $S\subseteq V$ of minimum size, or minimum weight, which
intersects (hits) every set in $\Sigma$. However, set-cover problems, and
hitting set problems behave differently when the sizes of the sets are
bounded. First, we consider the $d$-set cover problem.

#### The $d$-set cover problem.

Let $d$ be a positive integer. The task of the $d$-set cover problem is, given
a collection $\Sigma$ of subsets with size at most $d$ of a finite set $V$,
and given a weight function $\omega\colon\Sigma\rightarrow\mathbb{N}$, find a
set $S\subseteq\Sigma$ of minimum weight that covers $V$, that is,
$\bigcup_{X\in S}X=V$.

######  Theorem 7.

Let $\alpha\geq 1$. For any instance of the $d$-set-cover problem, the
$\alpha$-approximative cost ratio is at most $\alpha\cdot d\cdot\textsc{opt}$.

###### Proof.

Let $I=(\Sigma,V,\omega)$ be an instance of the $d$-set cover problem. Let
$|V|=n$. Denote by $S_{1},\ldots,S_{p}$ a sequence of solutions computed by
the present-biased agent avoiding superfluous solutions, and let
$S=\\{X_{1},\ldots,X_{p}\\}$ be the obtained solution for $I$. That is, $S$ is
a set cover such that

$X_{i}=\operatorname*{arg\,min}_{Y\in S_{i}}\omega(Y)$

for $i\in\\{1,\ldots,p\\}$. Clearly, $p\leq n$. Note that for each iteration
$i\in\\{1,\ldots,p\\}$, the agent considers the instance
$I_{i}=(\Sigma_{i},V_{i},\omega_{i})$, where, as superfluous solutions are
avoided,

$\begin{array}[]{lcl}V_{i}&=&V\setminus(\bigcup_{j=1}^{i-1}X_{i}),\\\
\Sigma_{i}&=&\\{X\cap V_{i}\mid
X\in\Sigma\setminus\\{X_{1},\ldots,X_{i-1}\\}\\},\\\
\omega_{i}&=&\omega|_{\Sigma_{i}}.\end{array}$

We have that, for every $i\in\\{1,\ldots,p\\}$,

$\textsc{opt}=\textsc{opt}(I)=\textsc{opt}(I_{1})\geq\cdots\geq\textsc{opt}(I_{p}),$

and, by Lemma 1(ii),

$\omega(X_{i})\leq\alpha\,\textsc{opt}(I_{i}).$

Since each set of $\Sigma$ covers at most $d$ elements of $V$,
$\textsc{opt}(I)\geq n/d$. Therefore

$c(S)=\sum_{i=1}^{p}\omega(X_{i})\leq\alpha\,\textsc{opt}(I)n\leq\alpha
d\,\textsc{opt}(I)^{2}.$

It follows that the cost ratio is at most $\alpha d\,\textsc{opt}$. ∎

#### The $d$-hitting set problem.

Let $d$ be a positive integer. We are given a collection $\Sigma$ of subsets
with size $d$ of a finite set $V$, a weight function $\omega\colon
V\rightarrow\mathbb{N}$. The task is to find a set $S\subseteq V$ of minimum
weight that hits every set of $\Sigma$.

We are using the classical _sunflower lemma_ of Erdős and Rado [6]. We state
this result in the form given in [5]. A _sunflower_ with $k$ _petals_ and a
_core_ $X$ is a collection of pairwise distinct sets $S_{1},\ldots,S_{k}$ such
that $S_{i}\cap S_{j}=X$ for all distinct $i,j\in\\{1,\ldots,k\\}$. Note that
the core may be empty, that is, a collection of $k$ pairwise disjoint sets is
a sunflower.

######  Lemma 2 (Sunflower lemma [6]).

Let $\mathcal{A}$ be a family of pairwise distinct sets over a universe $U$
such that for every $A\in\mathcal{A}$, $|A|=d$. If
$|\mathcal{A}|>d!(k-1)^{d}$, then $\mathcal{A}$ contains a sunflower with $k$
petals.

######  Theorem 8.

Let $\alpha\geq 1$. For any instance of the $d$-hitting-set problem, the
$\alpha$-approximative cost ratio is at most $\alpha
d!\,(\frac{\alpha}{\beta}\textsc{opt})^{d}$.

###### Proof.

Let $I=(\Sigma,V,\omega)$ be an instance of the $d$-hitting set problem.
Denote by $S_{1},\ldots,S_{p}$ a sequence of solutions computed by the
present-biased agent avoiding superfluous solutions, and let
$S=\\{v_{1},\ldots,v_{p}\\}$ be the obtained solution for $I$, that is,
$S\subseteq V$ is a hitting set such that

$v_{i}=\operatorname*{arg\,min}_{v\in S_{i}}\omega(v)$

for every $i\in\\{1,\ldots,p\\}$. Since the agent avoids superfluous
solutions, the agent considers the instance
$I_{i}=(\Sigma_{i},V_{i},\omega_{i})$ at each iteration
$i\in\\{1,\ldots,p\\}$, where

$\begin{array}[]{lcl}V_{i}&=&V\setminus\\{v_{1},\ldots,v_{i-1}\\},\\\
\Sigma_{i}&=&\\{X\in\Sigma\mid
X\cap\\{v_{1},\ldots,v_{i-1}\\}=\emptyset\\},\\\
\omega_{i}&=&\omega|_{V_{i}}.\end{array}$

Let $i\in\\{1,\ldots,p\\}$. Since $S_{i}$ is a minimal hitting set for
$\Sigma_{i}$, there is $X_{i}\in\Sigma_{i}$ such that $v_{i}\in X_{i}$, and,
for every $v\in S_{i}\setminus\\{v_{i}\\}$, $v\notin X_{i}$. We say that
$X_{i}$ is a _private_ set for $v_{i}$. Observe that

$\textsc{opt}=\textsc{opt}(I)=\textsc{opt}(I_{1})\geq\cdots\geq\textsc{opt}(I_{p})$

by the construction of the instances. The following claim is crucial for the
prof of the theorem.

######  Claim 4.1.

$p\leq d!\,(\frac{\alpha}{\beta}\textsc{opt})^{d}$.

Let us assume, for the purpose of contradiction, that
$p>d!\,(\frac{\alpha}{\beta}\textsc{opt})^{d}$. Consider the private sets
$X_{1},\ldots,X_{p}\in\Sigma$ for $v_{1},\ldots,v_{p}$, respectively, and let
$\mathcal{A}=\\{X_{1},\ldots,X_{p}\\}$. Note that $X_{1},\ldots,X_{p}$ are
pairwise distinct, since $X_{h}\in\Sigma_{h}$ and $X_{h}\notin\Sigma_{h+1}$
for every $h\in\\{1,\ldots,p-1\\}$. Let

$k=\Big{\lfloor}\frac{\alpha}{\beta}\textsc{opt}\Big{\rfloor}+1\geq 2.$

We have that $|X_{h}|=d$ for every $X_{h}\in\mathcal{A}$, and
$|\mathcal{A}|>d!\,(k-1)^{d}$. Hence, $\mathcal{A}$ contains a sunflower with
$k$ petals by Lemma 2. Denote by $X_{h_{1}},\ldots,X_{h_{k}}$ the sets of the
sunflower, and let $Y$ be its core.

Suppose that $Y=\emptyset$. Then, $X_{h_{1}},\ldots,X_{h_{k}}$ are pairwise
disjoint. Therefore,

$\textsc{opt}(I)\geq
k=\Big{\lfloor}\frac{\alpha}{\beta}\textsc{opt}\Big{\rfloor}+1>\textsc{opt},$

which is a contradiction. Therefore, $Y\neq\emptyset$.

We show that, for every hitting set $R$ for $\Sigma_{h_{1}}$ of weight at most
$\frac{\alpha}{\beta}\textsc{opt}$, $R\cap Y\neq\emptyset$. Assume that this
is not the case, that is, $R\cap Y=\emptyset$. Since $R$ is a hitting set,
there exists

$u_{\ell}\in X_{h_{\ell}}\setminus Y$

such that $u_{\ell}\in R$ for every $\ell\in\\{1,\ldots,k\\}$. Because
$\\{X_{h_{1}},\ldots,X_{h_{k}}\\}$ is a sunflower, $u_{1},\ldots,u_{k}$ are
distinct. It follows that

$\omega(R)\geq\sum_{\ell=1}^{k}\omega(u_{\ell})\geq
k=\Big{\lfloor}\frac{\alpha}{\beta}\textsc{opt}\Big{\rfloor}+1>\frac{\alpha}{\beta}\textsc{opt}.$

The latter strict inequality is contradicting the fact that the weight of $R$
is at most $\frac{\alpha}{\beta}\textsc{opt}$. We conclude that $R\cap
Y\neq\emptyset$.

Recall that $S_{h_{1}}$ is a feasible solution for $I_{h_{1}}$, and, by Lemma
1 (ii),

$\omega(S_{h_{1}})\leq\frac{\alpha}{\beta}\textsc{opt}(I_{h_{1}})\leq\frac{\alpha}{\beta}\textsc{opt}.$

Then $S_{h_{1}}\cap Y\neq\emptyset$. The set $X_{h_{1}}$ was chosen to be a
private set for $v_{h_{1}}$, that is, $S_{h_{1}}\cap
X_{h_{1}}=\\{v_{h_{1}}\\}$. Note that $v_{h_{1}}\notin X_{h_{2}}$. Hence,
$v_{h_{1}}\notin Y$, and thus $S_{h_{1}}\cap Y=\emptyset$. This is a
contradiction, which completes the proof of the claim.

By Claim 4.1, $p\leq d!\,(\frac{\alpha}{\beta}\textsc{opt})^{d}$. By Lemma 1
(i),

$\omega(v_{i})\leq\alpha\,\textsc{opt}(I_{i})\leq\alpha\,\textsc{opt}$

for every $i\in\\{1,\ldots,p\\}$. Therefore,

$c(S)=\sum_{i=1}^{p}\omega(v_{i})\leq\alpha\,\textsc{opt}\,p\leq\alpha\,\textsc{opt}\,d!\,(\frac{\alpha}{\beta}\textsc{opt})^{d}.$

It follows that $\frac{c(S)}{\textsc{opt}}\leq\alpha
d!\,(\frac{\alpha}{\beta}\textsc{opt})^{d}$.

Let $S=\\{x_{1},\dots,x_{n}\\}$ be the final solution selected by the present-
biased agent for $I$, and let $\omega$ be the weight function on the set
$\mathcal{S}_{I}$ associated to $I$. We have
$\sum_{i=1}^{n}\omega(x_{i})=\alpha\,\textsc{opt}(I)$. For every
$i\in\\{1,\dots,n\\}$, let us denote by
$\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i}\\})$ the cost of an optimal
solution for the instance $I\smallsetminus\\{x_{1},\dots,x_{i}\\}$, and by
$S_{\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i}\\})}$ a corresponding
optimal solution. For $i=0$,
$S_{\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i}\\})}$ is an optimal
solution for $I$. For $i=1,\dots,n$, we define

$\bar{x}_{i}=\\{x_{i}\\},\;\mbox{and}\;\bar{y}_{i}=S_{\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i-1}\\})}.$

Let $J$ be the instance with ground set
$\\{\bar{x}_{1},\dots,\bar{x}_{n}\\}\cup\\{\bar{y}_{1},\dots,\bar{y}_{n}\\},$
and feasible solutions

$\\{\bar{y}_{1}\\},\\{\bar{x}_{1},\bar{y}_{2}\\},\dots,\\{\bar{x}_{1},\dots,\bar{x}_{n-1},\bar{y}_{n}\\},\\{\bar{x}_{1},\dots,\bar{x}_{n}\\}.$

Note that $\bar{x}_{i}\neq\bar{x}_{j}$ for every $i\neq j$, because $x_{i}\neq
x_{j}$ for every $i\neq j$. Also, for every $i\in\\{1,\dots,n-1\\}$ and
$j\in\\{1,\dots,n\\}$, $\bar{x}_{i}\neq\bar{y}_{j}$, because otherwise the
sequence constructed by the time-biased agent for $I$ would stop at $x_{k}$
with $k<n$. Therefore, we have $J=J^{(n)}$, and, since
$\omega(x_{i})\leq\textsc{opt}(I)$ for every $i=1,\dots,n$, $n\geq\alpha$
holds.

For analyzing the behavior of a present-biased agent with parameter $\beta$
acting on $J$, let us assume that $k$ steps were already performed by the
agent, with $0\leq k<n$, resulting in constructing the partial solution
$\\{\bar{x}_{1},\dots,\bar{x}_{k}\\}$. (For $k=0$, this partial solution is
empty). The feasible solutions for
$J_{k}=J\smallsetminus\\{\bar{x}_{1},\dots,\bar{x}_{k}\\}$ are

$\\{\bar{y}_{1}\\},\dots,\\{\bar{y}_{k+1}\\},\\{\bar{x}_{k+1},\bar{y}_{k+2}\\},\dots,\\{\bar{x}_{k+1},\dots,\bar{x}_{n-1},\bar{y}_{n}\\},\\{\bar{x}_{k+1},\dots,\bar{x}_{n}\\}.$

Note that, for every $i\in\\{1,\dots,n\\}$,
$\bar{\omega}(\bar{x}_{i})=\omega(x_{i})$, and
$\bar{\omega}(\bar{y}_{i})=\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{i-1}\\})$.
We claim that $\bar{x}_{k+1}$ is the next element chosen by the agent. Indeed,
note first that $\bar{\omega}(\bar{x}_{k+1})\leq\bar{\omega}(\bar{y}_{k+2})$,
as, otherwise, we would get
$\omega(x_{k+1})>\textsc{opt}(I\smallsetminus\\{x_{1},\dots,x_{k+1}\\})$,
contradicting the choice of $x_{k+1}$ by the agent performing on $I$. As a
consequence,

$c_{\beta}(\\{\bar{x}_{k+1},\bar{y}_{k+2}\\})=\bar{\omega}(\bar{x}_{k+1})+\beta\,\bar{\omega}(\bar{y}_{k+2}).$

It follows from the above that, for every $j=1,\dots,k+1$,
$c_{\beta}(\\{\bar{y}_{j}\\})\geq
c_{\beta}(\\{\bar{x}_{k+1},\bar{y}_{k+2}\\})$, as the reverse inequality would
contradict the choice of $x_{k+1}$ by the agent performing on $I$. For the
same reason, for every $\ell\in\\{k+1,\dots,n-1\\}$, and every
$i\in\\{k+1,\dots,\ell\\}$, we have

$c_{\beta}(\\{\bar{x}_{k+1},\bar{y}_{k+2}\\})\leq\bar{\omega}(\bar{x}_{i})+\beta\Big{(}\sum_{j\in\\{k+1,\dots,\ell\\}\smallsetminus\\{i\\}}\bar{\omega}(\bar{x}_{j})+\bar{\omega}(\bar{y}_{\ell+1})\Big{)}$

and

$c_{\beta}(\\{\bar{x}_{k+1},\bar{y}_{k+2}\\})\leq\bar{\omega}(\bar{y}_{\ell+1})+\beta\sum_{j\in\\{k+1,\dots,\ell\\}}\bar{\omega}(\bar{x}_{j}).$

As a consequence, the present-biased agent performing on $J$ picks
$\bar{x}_{k+1}$ at step $k+1$, as claimed. The cost of the solution computed
by the agent is
$\sum_{i=1}^{n}\bar{\omega}(\bar{x}_{i})=\sum_{i=1}^{n}w(x_{i})=\alpha\,\textsc{opt}(I)$.
On the other hand, by construction,
$\textsc{opt}(J)=\bar{\omega}(\bar{y}_{1})=\textsc{opt}(I)$. The cost ratio of
the solution computed by the agent for $J$ is thus $\alpha$, which completes
the proof. ∎

##  5 Conclusion

We demonstrated that, by focussing on present-biased agents solving tasks,
specific detailed analysis can be carried on for each considered task, which
enables to identify very different agent’s behavior depending on the tasks
(e.g., set cover vs. hitting set). Second, focussing on present-biased agents
solving tasks enables to generalize the study to overestimation, and to
maximization, providing a global picture of searching via present-biased
agents. Yet, lots remain to be done for understanding the details of this
picture.

In particular, efforts could be made for studying other specific classical
problems in the context of searching by a present-biased agent. This includes
classical optimization problems like traveling salesman (TSP), metric TSP,
maximum matching, feedback vertex set, etc. Such study may lead to a better
understanding of the class of problems for which present-biased agents are
efficient, and the class for which they act poorly. And, for problems for
which present-biased agents are acting poorly, it may be of high interest to
understand what kind of restrictions on the agent’s strategy may help the
agent finding better solutions.

Another direction of research is further investigation of the influence of
using approximation algorithms by agents, as it is natural to assume that the
agents are unable compute the cost exactly. We made some initial steps in this
direction, but it seems that this area is almost unexplored. For example, it
can be noted that the upper bound for the cost ratio in Theorem 4 can be
rewritten under the assumption that the agent uses an $\alpha$-approximation
algorithm. However, the bound gets blown-up by the factor $\alpha^{s}$, where
$s$ is the size of the solution obtained by the agent (informally, we pay the
factor $\alpha$ on each iteration). From the other side, the examples in
Section 4 show that this is not always so. Are there cases when this
exponential blow-up unavoidable? The same question can be asked about
maximization problems.

## References

  * [1] G. A. Akerlof, Procrastination and obedience, American Economic Review: Papers and Proceedings, 81 (1991), pp. 1–19.
  * [2] S. Albers and D. Kraft, On the value of penalties in time-inconsistent planning, in 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017, pp. 10:1–10:12.
  * [3] , The price of uncertainty in present-biased planning, in 13th Int. Conference on Web and Internet Economics (WINE), 2017, pp. 325–339.
  * [4] , Motivating time-inconsistent agents: A computational approach, Theory Comput. Syst., 63 (2019), pp. 466–487.
  * [5] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, Springer, 2015\.
  * [6] P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc., 35 (1960), pp. 85–90.
  * [7] N. Gravin, N. Immorlica, B. Lucier, and E. Pountourakis, Procrastination with variable present bias, in ACM Conference on Economics and Computation (EC), 2016, p. 361.
  * [8] , Procrastination with variable present bias, CoRR, abs/1606.03062 (2016).
  * [9] C. Jepson, G. Loewenstein, and P. Ubel, Actual versus estimated differences in quality of life before and after renal transplant.  Working Paper, Department of Social and Decision Sciences, Carnegie Mellon University, 2001.
  * [10] J. M. Kleinberg and S. Oren, Time-inconsistent planning: a computational problem in behavioral economics, in ACM Conference on Economics and Computation (EC), 2014, pp. 547–564.
  * [11] , Time-inconsistent planning: a computational problem in behavioral economics, Commun. ACM, 61 (2018), pp. 99–107.
  * [12] J. M. Kleinberg, S. Oren, and M. Raghavan, Planning problems for sophisticated agents with present bias, in ACM Conference on Economics and Computation (EC), 2016, pp. 343–360.
  * [13] , Planning with multiple biases, in ACM Conference on Economics and Computation (EC), 2017, pp. 567–584.
  * [14] G. Loewenstein, T. O’Donoghue, and M. Rabin, Projection bias in predicting future utility, The Quarterly Journal of economics, 118 (2003), pp. 1209–1248.
  * [15] P. Tang, Y. Teng, Z. Wang, S. Xiao, and Y. Xu, Computational issues in time-inconsistent planning, in Proceedings of the 31st Conference on Artificial Intelligence (AAAI), 2017.