Inconsistent Planning: When in Doubt, Toss a Coin!

Yuriy Dementiev, Fedor V. Fomin, Artur IgnatievAAAI 2022 · DOI

This AAAI-22 paper, "Inconsistent Planning: When in Doubt, Toss a Coin!", explores the mathematical modeling of human procrastination and irrationality. By introducing randomization into a classic graph-theoretic model, the authors provide a more robust way to calculate the "cost of irrationality" and analyze the computational hurdles of predicting human behavior.

Introduction: The Cost of Procrastination

Why do we delay filing taxes or skip the gym despite knowing the long-term benefits? In behavioral economics, this is known as present bias—the tendency to overvalue immediate costs and undervalue future benefits. In 2014, Kleinberg and Oren introduced a graph-theoretic model to study this: an agent moves through a graph from a start node $s$ to a target $t$. At each node, the agent evaluates the remaining path cost but multiplies the immediate next step's cost by a bias factor $\beta \ge 1$.

Figure 1: A task graph representing a weekly schedule where an agent must decide when to perform reviews, illustrating potential procrastination paths.

However, the original model suffered from a "tie-breaking" problem. If two paths appeared equally costly to a biased agent, the model relied on arbitrary rules (like alphabetical order). This made the "cost of irrationality"—the ratio of the agent's actual path cost to the optimal cost—highly unstable. A tiny change in tie-breaking could lead to an exponential difference in the predicted outcome.

A Randomized Approach to Irrationality

To address this brittleness, the authors propose a randomized model. Instead of fixed rules, the agent "tosses a coin" to choose between equally attractive paths. This treats the task graph as a Markov Decision Process (MDP), smoothing out the instability of previous models and providing a more realistic representation of human indecision.

Computational Complexity: The Hardness of Prediction

A central question in this research is: how hard is it to predict the agent's behavior? The authors show that calculating the exact probability distribution of the agent's total cost is #P-hard.

To prove this, they utilize "diamond gadgets" to reduce the problem from COUNTING PARTITIONS. By mapping mathematical partitions of integers into specific paths within these gadgets, they demonstrate that counting paths of a certain cost is as difficult as solving fundamental hard counting problems.

Figure 2: Diamond gadgets used in the reduction from the counting partition problem to prove #P-hardness.

This hardness persists even on graphs with simple structures, such as those with low vertex cover. However, the complexity is sensitive to the "shape" of the graph. If a graph is "almost" a tree (having a small feedback edge set), the problem becomes fixed-parameter tractable.

Algorithmic Breakthroughs: Finding the Average

Despite the general hardness, the authors discovered a surprising efficiency in calculating "border" cases. While the exact distribution is hard to find, the expected (average) cost and the variance can be computed in polynomial time—specifically $O(n^3)$.

This is a significant result for practical applications. By knowing the mean and variance, researchers can use Chebyshev’s inequality to provide statistical guarantees. For instance, one can determine the minimum reward required at the target node to ensure an agent completes a task with at least a 75% success rate.

Conclusion and Future Work

This paper refines our understanding of inconsistent planning by replacing brittle tie-breaking rules with a robust randomized framework. It bridges the gap between theoretical complexity and practical behavioral modeling.

Future research directions include "nudging"—the strategic removal of certain edges (options) to lower the expected cost of irrationality. Additionally, extending the model to "sophisticated" agents—those who recognize their own bias and attempt to pre-commit to plans—remains an open and promising area of study.

Summary updated

BibTeX
@inproceedings{dementiev2022inconsistent,
  author = {Yuriy Dementiev and Fedor V. Fomin and Artur Ignatiev},
  title = {{Inconsistent Planning: When in Doubt, Toss a Coin!}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21207},
}
Figure