Last month, I had the pleasure of meeting Yakov Ben-Haim and talking with him at length about info-gap decision theory. He used an example of squirrels foraging for nuts to illustrate the types of problems for which info-gap decision theory models are useful.
A squirrel needs calories to survive, and nuts provide the perfect source of calories. The squirrel has a decision to make: where should the squirrel go to forage for nuts? Different foraging locations have different potentials for nut payoffs. They also have risks (not enough food). Foraging in a new location may carry highly uncertain risks that are impossible for the squirrel to estimate (being hit by a car, eaten by a wolf, etc.)
The squirrel has two options: the squirrel can hunt in the usual area where he can obtain n nuts with certainty or he can try a new location where he has a probability P of obtaining N nuts (with N > n) and a probability (1-P) of obtaining zero nuts. Let’s say that N and P are wild guesses.
Let’s say that the squirrel is an optimizer and decides to build a decision tree to maximize the number of nuts he can collect. Using basic decision analysis, he devices that he should choose the new location if PN>n.
The squirrel's decision tree. Squirrels don't really make decision trees, do they?
If the squirrel needs to collect n nuts to survive, then maximizing is nuts (pun intended. Sorry!) Staying with the status quo guarantees survival, even if P and N are large. The payoff for the new location may be greater, but there is a 1-P chance that the squirrel would starve. The traditional decision tree is not robust to the squirrel’s desire to survive (neither is darting in front of cars on the highway, but I digress).
On the other hand, if the squirrel needs to collect N nuts to survive, then staying with the status quo guarantees the squirrel’s demise. The new location is worth a look no matter how risky.
In both of these scenarios, the squirrel isn’t really maximizing the subjective expected nuts that he can collect–he really wants to maximize the probability of meeting his nut threshold (the one that guarantees survival). This is a satisficing strategy (although not dissimilar from an optimizing strategy with a moving threshold). The satisficing strategy is a better bet for the squirrel than the optimization strategy in this decision context. The squirrel doesn’t always need to know the exact probabilistic information to make a good decision, as illustrated above. In fact, he can have absolutely no idea what N and P would be to find an effective nut foraging strategy–even when there is severe uncertainty.
The idea of a squirrel building a decision tree is, of course, ludicrous. But it makes the point that what we should rethink our traditional optimization models so make sure they fit the real decision criteria on hand. Info-gap decision theory thus focuses on satisfying a given acceptable level of what is traditionally considered the objective function value and instead optimizing robustness. It also has philosophical implications for how one views certainty.
I’ve been looking more closely at robustness lately. I won’t abandon my optimization models, but I will acknowledge that including robustness in certain scenarios leads to decisions that more accurately reflect the criteria at hand and decisions that could be counter-intuitive.
Yakov Ben-Haim can explain this much better than I can, so I’ll refer you to his blog about info-gap decision theory and his article about foragers in the American Naturalist if you want to learn more.
Punk Rock Operations Research 
January 17th, 2012 at 8:44 am
I don’t know if squirrels make decision trees or not, but they are darned annoying little critters. At least around here.
January 17th, 2012 at 10:24 am
David – yeah, squirrels secretly run the UIUC campus. Once when I was running on the UIUC campus, I accidentally kicked a squirrel across the road when said squirrel ran in front of my foot.
January 17th, 2012 at 11:50 am
First off, shame on you for kicking a poor squirrel! Second, setting aside various questions about how many decision theory courses the typical squirrel audits (around here they seem to prefer finance courses, since all the theories taught there are clearly nuts), your arguments against optimizing neglect the fact that the criterion function should be expected utility and not just expected number of nuts. On the low end, as you note, a small haul is disproportionately bad (squirrel starves). At the high end, the marginal value of additional nuts is either zero or negative (squirrel washes them down with Big Gulps and suffers from obesity). Maximizing the probability of surviving seems a bit short-sighted. (Are squirrels near-sighted? Is that why they run into your foot?)
January 17th, 2012 at 12:08 pm
Shouldn’t the new location be (1-p) N n, N=n, and N<n? Thus the new location has a probability of being better the same or worse than the current location.
Or..you could look at it as the Time (t) to collect N nuts, thus optimizing the resource (time) to collect enough nuts in which case it should be a relatively straight forward optimization problem of either minimizing the time require to complete X # of tasks, or maximizing the # of tasks that can be completed in T time.
January 17th, 2012 at 12:20 pm
As a stochastic guy, it seems a risk management problem for me. Instead of maximizing the expected number of nuts, squirrels have to maximizing probability of surviving. Then the decision would be obvious. Alternatively, we can form a multiobjective optimization, maximizing number of nuts and minimizing the harshness of starving if squirrels can survive with less nuts. Then they will choose a solution among the efficient frontier. Only if they really do make analytical decisions.
The risk is well-considered in Finance or financial engineering, but not in operation management. This would be a good research area to explore.
January 17th, 2012 at 1:56 pm
Thanks for the comments, Paul, Todd, and Phil. It looks like we have a good group for working on a collaborative model of optimal squirrel foraging patterns (-:
I should not have left off a discussion about utility. That makes most of my discussion obsolete. Optimizing the time to collect an acceptable amount of nuts is an interesting spin on the problem. I wonder if multi-armed bandit models would work there. The squirrel could sample two regions to estimate the nut payoffs and then exploit. I am less familiar with financial engineering models of risk, but those seem relevant. I might have to work these suggestions into my courses this semester. VCU is not as squirrel-infested as other universities, but I think there would still be interest.
January 17th, 2012 at 2:00 pm
I want to reiterate that kicking the squirrel was not intentional.
I had a run-in with another squirrel in college who did perhaps solve decision trees. His optimal solution seems obvious in retrospect: wait until I opened a window and a jar of peanut butter, then chew through the screen to get the peanut butter sandwich. (He tried this approach when I didn’t open the window and got stuck between the screen and the window).
January 17th, 2012 at 2:25 pm
Another possibility: if the squirrel only forages when he’s down to his last few nuts, such that failure to find more nuts results in starvation, perhaps the squirrel should be using a Kelly strategy (http://en.wikipedia.org/wiki/Kelly_criterion). Note that I’m assuming the squirrel is male, and only forages (shops) when he absolutely has to. Female squirrels probably forage (shop) for fun.
January 18th, 2012 at 12:34 pm
This squirrel problem would definitely be made more interesting if there were inventory limits, such that Mr. Squirrel could only bury so many nuts per location. It would also be interesting if Mr. Squirrel knew his cognitive limits and would only bury so many nuts in so many different places – for the same reason I try to leave my keys in the same spot in my apartment every time I place them down 🙂
Thusly, foresting for more nuts equals more time and energy devoted to foraging them (and less time resting) and more energy either eating them or burying them somewhere, assuming these critters hibernate. (Apparently some squirrels hibernate, others don’t).
The tradeoff would be more rest and sleep, and more foraging.
January 18th, 2012 at 3:16 pm
G’day:
This reminds me of the famous quote
” … The behavior of Kropotkin’s cooperators is something like that of decision makers using the Jeffrey expected utility model in the Max and Moritz situation. Are ground squirrels and vampires using voodoo decision theory? …”
Brian Skyrms (1996, p. 51)
Evolution of the Social Contract
Cambridge University Press.
Indeed, info-gap decision theory is a voodoo decision theory par excellence. See
http://info-gap.moshe-online.com
http://vivalavoodoo.wordpress.com
Regarding the old counter-productive satisficing vs optimizing debate, consider this:
The Fundamental satisficing vs Optimizing Theorem:
Any satisficing problem can be formulated as an equivalent optimization problem.
Hence, the Satisficing vs Optimizing issue is a stylistic, rather than substantive, issue. What is important is what you optimize and what you satisfy.
Viva la Voodoo!
Moshe
January 18th, 2012 at 3:55 pm
Moshe, Thanks for your comments. Yes, any satisficing problem can be formulated as an equivalent optimization problem. In this post, I attempt to discuss the appropriateness of a modeling choice rather than delve into the “substantive” issues that you mention. I’m not as informed as you are, so I cannot offer too many comments there. “What is important is what you optimize and what you satisfy” is a great way of summarizing how to approach the modeling process, whether you are modeling squirrels or anything else. Thanks for the link to your papers and blog.
January 18th, 2012 at 4:45 pm
Laura, I appreciate your objectives and I can see why you are reluctant to consider “substantive” issues in this discussion. However, there is a real danger that by not clarifying the substantive issues first, the stylistic discussion could be easily misinterpreted and in fact be mistaken for a “substantive” analysis. The spread of info-gap decision theory is a good example of how quickly things can go wrong if the substantive issues are not clarified at the outset.
January 18th, 2012 at 5:08 pm
Moshe, The post meant to generate a discussion of modeling choice rather than an endorsement of any one choice. Certainly, other methods can be used to model the squirrel’s decision process, such as robust optimization, which I am more familiar with. Maybe I should have mentioned that there are other ways to address uncertainty in the modeling process.
One of the reasons I love blogging is that my readers add so much to the discussion. Thanks for offering your insight here and for providing links for more information.
January 18th, 2012 at 10:55 pm
News from the global ROBUSTNESS scene
This is in response to Laura’s apparent dilemma:
And since it looks like squirrels might also be interested in robust optimal solutions, I dedicate this short report to the international squirrels community.
OR Perspective
As we know, there are squirrels and there are OR-squirrels. And, as far as robustness is concerned, OR squirrels should know better! That is, OR-squirrels should know that they have at their disposal numerous modeling paradigms and that they can formulate their foraging problem in various ways. Furthermore, they should know that seemingly different models can actually be equivalent.
As far as I know, squirrels — including those of the OR variety — are primarily interested in optimizing (= maximizing in the Pareto sense) their quality of life in the face of adverse conditions. Although some squirrels regard their caloric intake as a major ingredient of their “quality of life” index, only very few use an unconstrained optimization model for this purpose. Therefore, as explained in my earlier comments, the “satisficing” vs “optimizing” issue is a non-issue.
The good news is that OR provides methodologies that seek optimal solutions that are robust to variations in the model’s parameters.
The bottom line is then that OR-squirrels should know that there is a striving area of OR called Robust Optimization that deals with situations where (optimal) solutions are required to be robust against variations in the values of the model’s parameters (objective function and/or constraints).
Non-OR Perspective
There are many ways to quantify/define the Robustness of decisions. It is therefore important to make sure that the robustness model used is suitable for the occasion. Experience has shown that in some disciplines there is lack of appreciation/awareness of the difference between local and global robustness.
Non-OR squirrels are therefore encouraged to consult their OR colleagues for advice/guidance regarding this matter.
On the other hand, OR-squirrels should be aware of the fact that OR does not have a monopoly in this area. Robustness is a major area of research and applications in other disciplines such as control, economics, statistics, engineering, and so on.
Info-gap perspective
Info-Gap squirrels should know that info-gap’s robustness model is a very simple robust optimization model that is known universally as radius of stability model (circa 1960), itself a very simple instance of Wald’s famous Maximin model (circa 1940). Since this is a model of local robustness, it is utterly unsuitable for the treatment of severe uncertainty of the type stipulated by info-gap decision theory. See extensive discussions on this issue at info-gap.moshe-online.com.
Summary
There is no conflict of interest between optimization and robustness. In situations where robustness is an issue, robust optimization methods can be used to seek decisions that are robust against variations in the values of the model’s parameters (objective function and/or constraints).
Robust decision making is a hot topic and OR has definitely a solid track-record in this area. However, OR has stiff competition in this arena. For instance, consider the brand new Cener for Robust Decision Making on Climate and Energy Policy (RDCEP). On the NSF page of the project we read:
No mention of OR!