Procrastination with Variable Present Bias

on YouTube ↗34m

" summary

Introduces variable present bias: each day the bias B is drawn IID (example: 1/3 chance B=1, 2/3 chance B=3). Proves a main lemma that worst-case task graphs reduce to a worst-case two-level graph and uses an iterative construction plus a Myerson pricing reduction to show menu-like choices suffice. Gives bounds: with bounded-distance graphs the procrastination ratio is Theta(n) (tight via a marathon-training construction); with monotone distance and enough mass near B=1 the ratio is constant.

AI-written summary · about

" chapters (6)

1. 0:00Introduction
2. 1:30Task graphs and discounting
3. 10:06Procrastination ratios
4. 10:22Theoretical models and results
5. 27:41Conclusion and summary
6. 30:12Questions and answers

" related talks

• 01h 12mA Brief Introduction to Algorithms, Game Theory and Risk-Averse Decision MakingEvdokia Nikolova · Real-Time Decision Making Boot Camp, Spring 2018
• 48mA Simple Condition for Constant Regret in Online Decision-MakingDaniel Freund · Matching and Objectives
• 01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation IIJason Hartline · Economics and Computation Boot Camp 2015
• 40mApproximation Algorithms for Optimization under UncertaintyAnupam Gupta · Uncertainty in Computation 2016
• 31mBatch Value-function Approximation with Only RealizabilityNan Jiang · Reinforcement Learning from Batch Data and Simulation
• 43mLearning about AuctionsAvrim Blum · Uncertainty in Computation 2016
• 47mExploiting Combinatorial Structure in Constraint Programming: ...Gilles Pesant · Satisfiability: Theory, Practice, and Beyond 2023
• 33mA Few Connections Between Optimization and ProbabilitySasha Rakhlin · Optimization, Statistics and Uncertainty