Time-Inconsistent Planning: Simple Motivation Is Hard to Find

Fedor V. Fomin, Torstein J. F. StrømmeAAAI 2020 · DOI

Abstract

This paper investigates the computational complexity of designing task structures for "present-biased" agents who disproportionately weight immediate costs. While finding a single motivating path is computationally efficient, the authors demonstrate that finding a "simple" task structure with even one branching choice is NP-complete. This reveals a sharp complexity dichotomy and suggests that structural simplicity does not necessarily imply ease of design.

Introduction: The Challenge of Present Bias

Human behavior often deviates from long-term goals due to time-inconsistency. A common manifestation is present bias, where immediate costs are perceived as significantly more burdensome than future costs. This phenomenon explains why individuals may abandon gym memberships or online courses midway through.

Researchers Kleinberg and Oren modeled this behavior using weighted directed acyclic graphs (DAGs). In this model, an agent moves toward a reward $r$ at a destination vertex $t$. At each step, the agent re-evaluates their plan, multiplying the cost of the immediate next edge by a "salience factor" $b \ge 1$. If the perceived cost of the path exceeds the reward, the agent abandons the task.

Figure 1: A time-inconsistent planning model where an agent (salience $b=3$) evaluates paths toward a reward $r=59$.

Defining the Simple Motivating Subgraph Problem

A "task designer" can influence an agent's behavior through choice reduction—pruning edges or vertices from the graph to ensure the agent remains motivated to reach the goal. The authors focus on finding "simple" motivating subgraphs, where simplicity is defined by the number of branching vertices ($k$), which are points where the agent has more than one outgoing edge to choose from.

Figure 3: Formal definition of the Simple Motivating Subgraph problem.

Complexity Dichotomy: From Linear to NP-Complete

The core contribution of this work is identifying a sharp jump in computational complexity based on the parameter $k$:

  1. The $k=0$ Case (Single Path): Finding the cheapest single path that keeps an agent motivated is solvable in linear time, $O(|V| + |E|)$, using a modified shortest-path algorithm.
  2. The $k \ge 1$ Case (Branching): Surprisingly, allowing even a single branching vertex ($k=1$) makes the problem NP-complete. The authors prove this via a reduction from the Subset Sum problem, showing that the difficulty arises from the precise balancing of costs required to keep the agent on track across different decision points.

Algorithmic Solutions for Bounded Costs

While the general problem is hard, the authors provide a path forward for practical scenarios. They developed a pseudo-polynomial algorithm that runs in $(|V| \cdot W)^{O(k)}$ time, where $W$ is the total sum of edge weights. This indicates that if the number of decision points is small and the costs are manageable integers, the problem becomes tractable. However, the problem remains "W[1]-hard" with respect to $k$ alone, meaning that without bounding the costs, increasing the number of choices quickly leads to computational intractability.

Conclusion and Future Directions

The study proves that "simple" task structures are deceptively difficult to design. The transition from a single path to a single choice introduces significant computational hurdles. Future research may explore models with fluctuating salience factors or the strategic placement of intermediate rewards (milestones) to mitigate the effects of present bias in more complex environments.

Summary updated

BibTeX
@inproceedings{fomin2020time,
  author = {Fedor V. Fomin and Torstein J. F. Strømme},
  title = {{Time-Inconsistent Planning: Simple Motivation Is Hard to Find}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6537},
}
Figure