This paper introduces random versions of successive approximations and multigrid algorithms for computing approximate solutions to a class of finite and infinite horizon Markovian decision problems (MDPs). We prove that these algorithms succeed in breaking the curse of dimensionality for a subclass of MDPs known as discrete decision processes (DDPs).

This paper provides an empirical analysis of how the U.S. Social Security and Medicare insurance system affect the labor supply of older males in the presence of incomplete markets for loans, annuities, and insurance. We estimate a detailed dynamic programming (DP) model of the joint labor supply and Social Security acceptance decision, focusing on a sample of males in the low to middle income brackets whose only pension is Social Security. The DP model delivers a rich set of predictions about the dynamics of retirement behavior, and comparisons of actual vs. predicted behavior show that the DP model is able to account for wide variety of phenomena observed in the data, including the pronounced peaks in the distribution of retirement ages at 62 and 65 (the ages of early and normal eligibility for Social Security benefits, respectively). We identify a significant fraction of health insurance constrained individuals who have no form of retiree insurance other than Medicare, and who can only obtain fairly priced private insurance via their employer's group plan. The combination of significant individual risk aversion and a long tailed (Pareto) distribution of care expenditures implies that there is a significant security value for these individuals to remain employed until they are eligible for Medicare coverage at age 65. Overall, our model suggests that a number of heretofore puzzling aspects of retirement behavior can be viewed as artifacts of particular details of the Social Security rules, whose incentive effects are especially strong for lower income individuals and those who do not have access to fairly priced loans, annuities, and insurance.