|
|
 |
 |
 |
 |
 |
|
December 2007 The calculus of cat and mousePaul J. Nahin Chases and Escapes: The Mathematics of Pursuit and Evasion, Princeton, N.J., Princeton University Press, 2007 (270 pp). ISBN 0-691-12514-7 (hard cover) RRP $41.95. What do submarine attacks, ant-trails, and dating have in common? Not much, except that they are all instances of pursuit and evasion problems and all submit to elegant mathematical treatments. The mathematics involved in such problems is varied and interesting in its own right, but the applications breathe life into the mathematics and invite wider engagement—as the intense interest of the military in such problems, especially during wartime, demonstrates. Consider the problem of a submarine commander about to fire on an enemy warship. The enemy warship, of course, refuses to co-operate, and the warship keeps up its course across the open sea. The submarine commander needs a strategy to ensure that the torpedoes arrive where the warship will be by the time the torpedoes arrive. How does the commander do this, without knowing the warship’s course? After all, there is no guarantee that the warship will travel in a straight line or at a constant speed. One way for the submarine commander to proceed is to keep the torpedo always aimed at the ship, instantaneously adjusting its direction to changes in the warship’s position. If this is done, the torpedo will (typically) trace out an arc and (typically) strike the ship from behind. This is called a pure pursuit strategy and is important in many military applications (such as Second World War air battles).
Not all pursuit problems have such a military flavour. Pursuit problems are also plentiful in biological applications. How is it that ants manage to forge such direct paths between their nests and food sources? One possibility is that each ant pursues the previous ant (via the latter’s marked trail) and the result is a straightening of the original rather tortuous trail between nest and food. To take another biological example, consider the problem of finding the best mate. The more desirable you are to your potential mates, the more desirable a mate you can secure. But how do you guarantee that you’ve done as well as you can? All but the most incorrigible romantics have wondered whether their current partner really is optimal, and again mathematics comes to the rescue; various techniques can be invoked to help with such dating dilemmas—more on this shortly. In Chases and Escapes: The Mathematics of Pursuit and Evasion, Paul Nahin surveys the mathematics of pursuit and escape problems. It's an odd mix of textbook and quirky general-interest book for a fairly sophisticated mathematical audience. To follow the discussion, the reader needs to be familiar with undergraduate calculus and at least ordinary differential equations (although there are occasional forays into more advanced topics). This, I suspect, puts the book beyond the reach of the average popular science reader, but those with the required mathematical credentials will find this an engaging book on a fascinating topic. The book has regular ‘challenge problems’ on the main topics covered, with solutions in the back. It is well written and clearly the result of an author with a passion for the subject matter. Nahin also discusses the history of the various pursuit and escape problems, but the main focus remains on the mathematical treatments.
For the most part, the problems Nahin discusses revolve around differential equations but towards the end of the book he introduces game theory, along with a couple of problems that submit to game-theoretic treatment. His focus on differential equations is fair enough, given the pursuit problems he chooses to discuss. But more on game theory would have been valuable, given the great contemporary interest in applications of game theory. (See von Neumann and Morgenstern (1947) and Luce and Raiffa (1957) for classic early treatises on game theory.) For the rest of this article I’ll discuss some of the topics Nahin did not cover, including examples involving game theory, number theory, and probability theory. In a nut shell, game theory is the study of decisions where one agent’s decision depends on the decisions of other agents. (Think of games like chess or tennis, or the cold-war arms race for ‘games’ with more serious consequences.) One of the most important examples in game theory is the stag hunt. This game originates in a story of co-operative hunting by the 18th century political philosopher Jean-Jacques Rousseau (1984). In its simplest form, the game consists of two hunters setting out to hunt a stag. For the hunt to succeed, both hunters will need to co-operate and the payoff for success is a feast. But each hunter will be tempted by lesser prey: a hare, for example. If one hunter defects from the stag hunt and opportunistically hunts a passing hare, the defector will be rewarded, but the non-defector will not. In decreasing order of preference, the rewards are: stag, hare, and nothing. So the co-operative outcome (both hunt stag) has the maximum payoff for each of them, but it is unstable in light of the ever-present temptation for each hunter to defect and hunt hare instead. Indeed, hunting hare is the safer option. In the jargon of game theory, the co-operative solution is a Pareto optimal Nash equilibrium, while the mutual defect solution is a risk dominant Nash equilibrium (though not Pareto optimal). That is, the co-operative solution is best for both hunters (it’s Pareto optimal), and given that the other party co-operates in the stag hunt, then you should too. But if the other party defects and hunts hare, then so should you. Most importantly, neither party will unilaterally change from co-operation to defection or from defection to co-operation (the mutual defect and co-operation solutions are Nash equilibria). So if you both play it safe and hunt hares, there seems no easy way to get to the mutually-preferable co-operative solution of stag hunting. Co-operation seems both hard to achieve and somewhat fragile. This game is important because it is a good model of many forms of co-operative behaviour: faithful marriage, and other forms of social contract. (See Skyrms (2003) for an excellent treatment of the stag hunt and its significance.)
Another kind of pursuit Nahin might have considered is evolutionary pursuits, where species are selected for certain life cycles because those lifecycles effectively hide them from predators. For example, it turns out that some species of cicadas have life cycles of thirteen and seventeen years. More specifically, the adult cicadas emerge from the soil-bound nymphal stage after thirteen or seventeen years (depending on the region) in a synchronised fashion, mate and then die after only a few weeks. Interestingly, the lengths of the life cycles are prime numbers (the numbers do not have integer divisors other than one and the number itself). A plausible explanation of these prime life cycles is that they are selected for: they minimise the chance of the cicadas having their life cycle coincide with that of a predator. After all, a predator with a periodic life cycle would need to have their life cycle coincide with the emergence of the adult cicada (the only time when the cicada is really vulnerable to predators), so predators with life cycles between one and thirteen (or seventeen, as the case may be) years will rarely coincide with the adult cicadas. (This follows from some elementary results in number theory, but the basic idea is clear enough: if the predator’s cycle is n years, where n is between one and thirteen, the predator can only ever coincide with the thirteen-year cicada once every 13n years.) In effect, prime life cycles such as these make for good evolutionary strategies for hiding (temporally) from predators. (See Baker (2005) for a discussion of this case and its philosophical significance.) One of the most interesting pursuit problems is that of finding a mate. Nahin mentions this problem in passing in his acknowledgements but does not take up the topic in the book. A classic mathematical treatment of finding a mate is the so-called secretary problem. Here the problem is that of finding the best secretary (read: mate) by interviewing (read: dating) a number of applicants. In the standard formulation, you have a finite and known number of applicants and you must interview these n candidates sequentially, and you must decide whether to accept or reject each applicant immediately after their interview; you cannot recall a previously-interviewed applicant. (Typically, boyfriends and girlfriends do not take kindly to being dumped for someone else and are not open to the possibility of recall!) The question is then: how many of the n possible candidates should you interview before making an appointment (read: how many people should you date before you marry)? It can be shown that the optimal strategy (for large n) is passing over the first n/e (where e is the transcendental number that is the base of the natural logarithm, approximately 2.718) applicants and accept the next applicant who is better than all those previously seen. This gives a probability of finding the best secretary (mate) at 1/e or approximately 0.37. So even if you do everything right, you still have only a 0.37 chance of finding your perfect mate. And then getting him or her to accept you as his or her perfect mate is a whole other story. As they say, it’s a jungle out there! (See Ferguson (1989) for more on the secretary problem and Todd (1997) for other treatments of mating games.)
Let me conclude with a question about the relationship between the various systems being modelled and the mathematics employed. Consider again the secretary problem. How useful is this as a model of actual dating? Sure, as a general rule, old flames are not recallable, but sometimes they are (or so I’ve been told!). And not everyone is serially monogamous, as the secretary problem assumes. The bottom line is that there are various assumptions of the idealised set-up that are false in the real world of dating. What use, then, is the secretary problem and its mathematical treatment as a means of investigating something as complicated as human dating practices? To give another example of a questionable idealisation: in the submarine and warship pursuit problems there are idealisations of various kinds such as that a torpedo can instantaneously change its direction so as to always be aimed at its target. Restating the question in its most general form then: how can models with false assumptions (especially those with known-to-be-false assumptions) tell us anything useful about the real-world systems they are supposed to model? This is a big topic and the reader can hardly blame Nahin for not entering this particular minefield. (See Batterman (2002) and Cartwright (1983) for philosophical discussions of this issue, and Ginzburg and Colyvan (2004) for a discussion of the issue in relation to ecological models.) But it is worth noting that leaving out detail in a model does not in itself invalidate all the conclusions derived from the model. For example, in the secretary problem, we assumed that every secretary (potential mate) would accept the job (marriage) if offered it. Clearly this is false, and adding this complication only makes the prospects of finding the perfect mate harder. So sometimes the idealisations can be used to show that even in the best/worst case, certain conclusions hold. Other times the idealisations are considered to be harmless: they are not thought to change the result in any significant way at all. Perhaps the assumptions of instantaneous change fall into this category. Often the idealisations are forced upon us by the difficulty of the problem. But still we hope that such highly-idealised models will help us gain insight into the problem and provide guidance on what a better, more sophisticated model would look like. On this view, models are essentially works in progress. All in all, pursuit problems are a fascinating topic and a very nice hook for the presentation of some important mathematics. As I’ve indicated, I think there are other topics that might have been included in Chases and Escapes, but this just serves to highlight how big and varied the topic is. In any case, this book provides an excellent vehicle to pursue the mathematics in question, and the mathematics in question is most certainly worth pursuing. REFERENCESBaker A. 2005, ‘Are there genuine mathematical explanations of physical phenomena?’, Mind, vol. 114, no. 454, pp. 223–238. Batterman, R.W. 2002, The Devil in the Details: Asymptotic Reasoning in Explanation Reduction and Emergence, Oxford University Press, New York. Cartwright, N. 1983, How the Laws of Physics Lie, Oxford University Press, New York. Ferguson, T.S. 1989, ‘Who solved the secretary problem?’, Statistical Science, vol. 4, no. 3, pp. 282–296. Ginzburg, L. & Colyvan, M. 2004, Ecological Orbits: How Planets Move and Populations Grow, Oxford University Press, New York. Luce, R.D. & Raiffa, H. 1957, Games and Decisions: Introduction and Critical Survey, John Wiley and Sons, New York. Rousseau, J.J. 1984, A Discourse on Inequality, trans. M. Cranston, Penguin Books, New York. Skyrms, B. 2003, The Stag Hunt and the Evolution of Social Structure, Cambridge University Press, Cambridge. Todd, P. 1997, ‘Searching for the next best mate’, in Simulating Social Phenomena, eds R. Conte, R. Hegselmann & P. Terna, Springer-Verlag, Berlin, pp. 419–436. von Neumann, J. & Morgenstern, O. 1947, Theory of Games and Economic Behavior, 2nd edn, Princeton University Press, Princeton. Mark Colyvan is Professor of Philosophy at The University of Sydney. His interests include logic, decision theory, and philosophy of science and mathematics. He is the author of The Indispensability of Mathematics (Oxford University Press, 2001) and (with Lev Ginzburg) Ecological Orbits: How Planets Move and Populations Grow (Oxford University Press, 2004). View other articles by Mark Colyvan:
|
|
||||||||||||
|
|
||||||||||||||
