Rust (1997b) discovered a class of dynamic programs that can be solved in polynomial time with a randomized algorithm. For these dynamic programs, the optimal values of a polynomially large sample of states are sufficient statistics for the (near) optimal values everywhere, and the values of this random sample can be bootstrapped from the sample itself. However, I show that this class is limited, as it requires all but a vanishingly small fraction of state variables to behave arbitrarily similarly to i.i.d. uniform random variables.

This paper integrates the classic theory of firm boundaries, through span of control or taste for variety, into a model of the labor market with random matching and on‐the‐job search. Firms choose when to enter and exit, whether to create vacancies or destroy jobs in response to shocks, and Bertrand‐compete to hire and retain workers. Tractability is obtained by proving that, under a parsimonious set of assumptions, all worker and firm decisions are characterized by their joint surplus, which in turn only depends on firm productivity and size. The job ladder in marginal surplus that emerges in equilibrium determines net poaching patterns by firm characteristics that are in line with the data. As frictions vanish, the model converges to a standard competitive model of firm dynamics. The combination of firm dynamics and search frictions allows the model to: (i) quantify the misallocation cost of frictions; (ii) replicate elusive life‐cycle growth profiles of superstar firms; and (iii) make sense of the failure of the job ladder around the Great Recession as a result of the collapse of firm entry.