Present-Biased Optimization

Fedor V. Fomin, Pierre Fraigniaud, Petr A. GolovachAAAI 2021 · DOI

Abstract

Present-biased agents often make suboptimal decisions by overvaluing immediate costs or rewards relative to future ones. While previous models in behavioral economics focused on simple pathfinding, this work extends the framework to general combinatorial optimization problems like Set Cover and Knapsack. We analyze the "cost ratio" between biased and optimal solutions, proving that for many scenarios, the inefficiency is bounded and predictable, contrary to the infinite procrastination seen in simpler models.

The Challenge of Present Bias

We’ve all been there: deciding to read a short summary today because the full textbook seems too daunting, assuming we'll have more energy to tackle the hard chapters tomorrow. This is present bias: a tendency to undervalue future costs or gains relative to immediate ones.

In 2014, Kleinberg and Oren introduced a graph-theoretic model to study this, showing that a present-biased agent navigating a "task graph" could incur costs exponentially higher than the optimal path—a phenomenon known as the "procrastination" effect. However, their model was largely limited to simple pathfinding.

A task graph illustrating the pathfinding model where present bias can lead to inefficient routes.

This research addresses a major gap: How does present bias affect general optimization problems? If an agent is trying to solve a "Set Cover" problem (e.g., picking the fewest books to learn a set of concepts), does their bias lead to the same catastrophic failures seen in pathfinding?

Modeling Biased Agents

The authors extend the mathematical framework of present bias to two main scenarios:

  1. Minimization Tasks: The agent tries to minimize total cost (e.g., Set Cover). They perceive the immediate cost of the first step accurately but multiply all future costs by a factor $\beta$. If $\beta < 1$, they underestimate future work (procrastination); if $\beta > 1$, they overestimate it.
  2. Maximization Tasks: The agent tries to maximize total gain (e.g., Knapsack). Here, $\beta < 1$ means they underestimate future rewards.

By defining a biased cost function $c_\beta$, the authors analyze the cost ratio: the ratio between the solution found by the biased agent and the true optimal solution. As a theoretical study, the models were evaluated using synthetic problem instances (like Set Cover and Hitting Set) and classic constructions from behavioral economics, such as the Akerlof example.

Key Insights: Why Optimization is "Safer"

The study reveals several surprising properties of biased optimization:

  • Optimization is "Safer" than Pathfinding: In the original Kleinberg-Oren pathfinding model, the cost ratio can be infinite. Surprisingly, for general minimization tasks, the cost ratio is bounded by the number of steps $k$. You can't procrastinate forever if the task has a fixed set of requirements to "cover."
  • Overestimation is Surprisingly Stable: If an agent overestimates future costs ($\beta > 1$) in a minimization task, the damage is strictly limited. The cost ratio will never exceed $\beta$.
  • The "Inconsistency" Culprit: High costs usually stem from "inconsistent" choices—where an agent picks an element that wasn't even part of their own (biased) future plan. If an agent is forced to stay "consistent" with their previous plans, the cost ratio stays low ($1/\beta$).
  • Task Structure Matters: Different problems react differently to bias. For example, in the $d$-set cover problem, the cost ratio is linear relative to the set size, but in the $d$-hitting set problem, it can be exponential.

Summary of Results

The paper provides a complete global picture of biased optimization, establishing bounds for the cost ratio across different scenarios.

Summary of cost ratio bounds for different optimization scenarios and bias types.

Key theoretical results include:

  • Theorem 4: For any minimization problem with $\beta > 1$, the cost ratio is at most $\beta$.
  • Theorem 5: For any maximization problem with $\beta < 1$, the cost ratio is at most $1/\beta$.
  • Approximation Effects: If an agent uses an approximation algorithm (due to NP-hardness), the cost ratio generally scales linearly with the approximation factor $\alpha$.

Limitations and Future Directions

While this work provides a robust theoretical foundation, several avenues for future research remain:

  • Computational Complexity: The model assumes agents can calculate the "best" biased solution at each step. In reality, solving $c_\beta$ might be NP-hard, and the impact of "bounded rationality" (computational limits) is not yet fully understood.
  • Problem Scope: While Set Cover and Hitting Set are analyzed, other classic problems like the Traveling Salesman Problem (TSP) or Maximum Matching have yet to be explored under this framework.
  • Dynamic Bias: The current model assumes a constant $\beta$. Future work could explore "variable present bias," where the level of procrastination changes as the agent approaches their goal.

Summary updated

BibTeX
@inproceedings{fomin2021present,
  author = {Fedor V. Fomin and Pierre Fraigniaud and Petr A. Golovach},
  title = {{Present-Biased Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16682},
}
Figure