ABCs of the bomber problem and its relatives

In a classic Markov decision problem of Derman et al. (Oper. Res. 23(6):1120–1130, 1975 ) an investor has an initial capital x from which to make investments, the opportunities for which occur randomly over time. An investment of size y results in profit P(y), and the aim is maximize the sum of the profits obtained within a given time t. The problem is similar to a groundwater management problem of Burt (Manag. Sci. 11(1):80–93, 1964 ), the notorious bomber problem of Klinger and Brown (Stochastic Optimization and Control, pp. 173–209, 1968 ), and types of fighter problems addressed by Weber (Stochastic Dynamic Optimization and Applications in Scheduling and Related Fields, p. 148, 1985 ), Shepp et al. (Adv. Appl. Probab. 23:624–641, 1991 ) and Bartroff et al. (Adv. Appl. Probab. 42(3):795–815, 2010a ). In all these problems, one is allocating successive portions of a limited resource, optimally allocating y(x,t), as a function of remaining resource x and remaining time t. For their investment problem, Derman et al. (Oper. Res. 23(6):1120–1130, 1975 ) proved that an optimal policy has three monotonicity properties: (A) y(x,t) is nonincreasing in t, (B) y(x,t) is nondecreasing in x, and (C) x−y(x,t) is nondecreasing in x. Theirs is the only problem of its type for which all three properties are known to be true. In the bomber problem the status of (B) is unresolved. For the general fighter problem the status of (A) is unresolved. We survey what is known about these exceedingly difficult problems. We show that (A) and (C) remain true in the bomber problem, but that (B) is false if we very slightly relax the assumptions of the usual model. We give other new results, counterexamples and conjectures for these problems. Copyright Springer Science+Business Media, LLC 2013