Information Processing

Nash and Milnor were involved in experimental tests of n-person game theory at RAND in 1952. Even then it was clear that game theory had little direct applicability in the real world. See also What Use Is Game Theory? , Iterated Prisoner's Dilemma is an Ultimatum Game, and, e.g., The Econ Con or Venn Diagram for Economics.

A Beautiful Mind: ... For the designers of the experiment[s], however, the results merely cast doubt on the predictive power of game theory and undermined whatever confidence they still had in the subject. Milnor was particularly disillusioned. Though he continued at RAND as a consultant for another decade, he lost interest in mathematical models of social interaction, concluding that they were not likely to evolve to a useful or intellectually satisfying stage in the foreseeable future. The strong assumptions of rationality on which both the work of von Neumann and Nash were constructed struck him as particularly fatal. After Nash won the Nobel Prize in 1994, Milnor wrote an essay on Nash's mathematical work in which he essentially adopted the widespread view among pure mathematicians that Nash's work on game theory was trivial compared with his subsequent work in pure mathematics.

In the essay, Milnor writes:

As with any theory which constructs a mathematical model for some real-life problem, we must ask how realistic the model is. Does it help us to understand the real world? Does it make predictions which can be tested?...

First let us ask about the realism of the underlying model. The hypothesis is that all of the players are rational, that they understand the precise rules of the game, and that they have complete information about the objectives of all of the other players. Clearly, this is seldom completely true.

One point which should particularly be noticed is the linearity hypothesis in Nash's theorem. This is a direct application of the von Neumann-Morgenstern theory of numerical utility; the claim that it is possible to measure the relative desirability of different possible outcomes by a real-valued function which is linear with respect to probabilities .... My own belief is that this is quite reasonable as a normative theory, but that it may not be realistic as a descriptive theory.

Evidently, Nash's theory was not a finished answer to the problem of understanding competitive situations. In fact, it should be emphasized that no simple mathematical theory can provide a complete answer, since the psychology of the players and the mechanism of their interaction may be crucial to a more precise understanding.

For more discussion, including specific experimental results, see Machine Dreams, chapter 6.2: It's a world eat world dog: game theory at RAND.

The original title of this post was For this you won a Nobel (Memorial) Prize? But see sad news at bottom.

A Beautiful Mind: Nash went to see von Neumann a few days after he passed his generals? He wanted, he had told the secretary cockily, to discuss an idea that might be of interest to Professor von Neumann. It was a rather audacious thing for a graduate student to do. Von Neumann was a public figure, had very little contact with Princeton graduate students outside of occasional lectures, and generally discouraged them from seeking him out with their research problems. But it was typical of Nash, who had gone to see Einstein the year before with the germ of an idea.

Von Neumann was sitting at an enormous desk, looking more like a prosperous bank president than an academic in his expensive three-piece suit, silk tie, and jaunty pocket handkerchief.  He had the preoccupied air of a busy executive. At the time, he was holding a dozen consultancies, "arguing the ear off Robert Oppenheimer" over the development of the H-bomb, and overseeing the construction and programming of two prototype computers. He gestured Nash to sit down. He knew who Nash was, of course, but seemed a bit puzzled by his visit.

He listened carefully, with his head cocked slightly to one side and his fingers tapping. Nash started to describe the proof he had in mind for an equilibrium in games of more than two players. But before he had gotten out more than a few disjointed sentences, von Neumann interrupted, jumped ahead to the yet unstated conclusion of Nash's argument, and said abruptly, "That's trivial, you know. That's just a fixed point theorem." 

See also What use is game theory? Compare the excerpt below about Nash's Embedding Theorem (also of interest: Theorem proving machines).

A Beautiful Mind: Nash's theorem stated that any kind of surface that embodied a special notion of smoothness can actually be embedded in Euclidean space. He showed that you could fold the manifold like a silk handkerchief, without distorting it. Nobody would have expected Nash's theorem to be true. In fact, everyone would have expected it to be false. "It showed incredible originality," said Mikhail Gromov, the geometer whose book Partial Differential Relations builds on Nash's work. He went on:

Many of us have the power to develop existing ideas. We follow paths prepared by others. But most of us could never produce anything comparable to what Nash produced. It's like lightning striking. Psychologically the barrier he broke is absolutely fantastic. He has completely changed the perspective on partial differential equations. There has been some tendency in recent decades to move from harmony to chaos. Nash says chaos is just around the corner. 

John Conway, the Princeton mathematician who discovered surreal numbers and invented the game of Life, called Nash's result "one of the most important pieces of mathematical analysis in this century."

In writing this post, I googled "a beautiful mind" to find a link to the Amazon page. I was shocked to find a news article about the death of John Nash and his wife Alicia (both are in the photo above) yesterday in a car accident! May they rest in peace.

War is a simple card game played by children. The most common version does not require decisions, so it's totally deterministic (outcome is determined) once the card order in each deck is fixed. Nevertheless it can be entertaining to watch/play: there are enough fluctuations to engage observers, mainly due to the treatment of ties. The question of how to determine the winner from the two deck orderings (without actually playing the entire game, which can take a long time) was one of the first aspects of computability / predictive modeling / chaotic behavior I thought about as a kid. This direction leads to things like classification of cellular automata and the halting problem.

My children came home with a version designed to teach multiplication -- each "hand" is two cards, rather than the usual single card, and the winner of the "battle" is the one with the higher product value of the two cards (face cards are removed). I thought this was still too boring: no strategy (my kids understood this right away, along with the meaning of deterministic; this puts them ahead of some philosophers), so I came up with a variant that has been quite fun to play.

Split the deck into red and black halves, removing face cards. Each hand (battle) is played with two cards, but they are chosen by each player. One card is placed face down simultaneously by each player, and the second cards played are chosen after the first cards have been revealed (flipped over). Winner of most hands is the victor.

This game ("strategic war") is simple to learn, but complex enough that it involves bluffing, calculation, and card counting (keeping track of which cards have been played). A speed version, with, say, 10 seconds allowed per card choice, goes very fast.

Has anyone seen heard of this game before? It's a bit like repeated two card poker (heads up), drawing from a fixed deck. Note the overall strength of hands for each player (combined multiplicative value of all cards) is fixed and equal. Playing strong hands early means weaker hands later in the game. The goal is to win each hand by as small a margin as possible.

Are there strategies which dominate random play (= select first card at random, second card from range not exceeding highest card required to guarantee a win)?


Don't forget to respond to the reader survey.

Amazing new results on iterated prisoner's dilemma (IPD) by Bill Press (Numerical Recipes) and Freeman Dyson. There is something new under the sun. Once again, physicists invade adjacent field and add value.

Extortion and cooperation in the Prisoner’s Dilemma (June 18, 2012) 

The two-player Iterated Prisoner’s Dilemma game is a model for both sentient and evolutionary behaviors, especially including the emergence of cooperation. It is generally assumed that there exists no simple ultimatum strategy whereby one player can enforce a unilateral claim to an unfair share of rewards. Here, we show that such strategies unexpectedly do exist. In particular, a player X who is witting of these strategies can (i) deterministically set her opponent Y’s score, independently of his strategy or response, or (ii) enforce an extortionate linear relation between her and his scores. Against such a player, an evolutionary player’s best response is to accede to the extortion. Only a player with a theory of mind about his opponent can do better, in which case Iterated Prisoner’s Dilemma is an Ultimatum Game.

Accompanying commentary in PNAS. See these comments by Press and Dyson.

[[Press]] I was originally wondering about a much more modest question that, annoyingly, I couldn’t find already answered in the Prisoner’s Dilemma literature. ... The story now becomes one of symbiosis between computer and human intelligence: The computer could find instances, but not generalize them. I knew that the exact complement of computer intelligence, as yin to yang, is Freeman-Dyson-intelligence. So I showed what I had to Freeman. A day later, he sent me an email with the general result, equations 1-7 in our paper, all worked out. These equations immediately expose all the ZD strategies, including the successful extortionate ones. 

... The successful extortionate strategies have been mathematically present in IPD from the moment that Axelrod defined the game; they just went, seemingly, unnoticed. On a planet in another galaxy, seven million years ago, Axelrod-Prime independently invented the same IPD game. He (it?) was of a species several times more intelligent than Homo sapiens [[i.e., like Dyson!]] and so recognized immediately that, between sentient players, the IPD game is dominated by an obvious extortionate strategy. Hence, for Axelrod-Prime, IPD was just another instantiation of the well-studied Ultimatum Game. He (it?) thus never bothered to publish it.

The history of IPD shows that bounded cognition prevented the dominant strategies from being discovered for over 60 years, despite significant attention from game theorists, computer scientists, economists, evolutionary biologists, etc. Press and Dyson have shown that IPD is effectively an ultimatum game, which is very different from the Tit for Tat stories told by generations of people who worked on IPD (Axelrod, Dawkins, etc., etc.).

How can we expect markets populated by apes to find optimal solutions in finite time under realistic conditions, when the underlying parameters of the game (unlike in IPD) are constantly changing? You cannot think of a simpler quasi-realistic game of cooperation and defection than IPD, yet the game was not understood properly until Dyson investigated it! Economists should think deeply about the history of the academic study of IPD, and what it implies about rationality, heuristics, "efficient" markets (i.e., everyone can be wrong for a long, long time). 

For evolutionary biologists: Dyson clearly thinks this result has implications for multilevel (group vs individual selection):

... Cooperation loses and defection wins. The ZD strategies confirm this conclusion and make it sharper. ... The system evolved to give cooperative tribes an advantage over non-cooperative tribes, using punishment to give cooperation an evolutionary advantage within the tribe. This double selection of tribes and individuals goes way beyond the Prisoners' Dilemma model.

See also What use is game theory? and Plenty of room at the top. Zero-Determinant Strategies in the Iterated Prisoner’s Dilemma provides a pedagogical summary of the new results.

Fantastic interview with game theorist Ariel Rubinstein on Econtalk. I agree with Rubinstein that game theory has little predictive power in the real world, despite the pretty mathematics. Experiments at RAND (see, e.g., Mirowski's Machine Dreams) showed early game theorists, including Nash, that people don't conform to the idealizations in their models. But this wasn't emphasized (Mirowski would claim it was deliberately hushed up) until more and more experiments showed similar results. (Who woulda thought -- people are "irrational"! :-)

Perhaps the most useful thing about game theory is that it requires you to think carefully about decision problems. The discipline of this kind of analysis is valuable, even if the models have limited applicability to real situations.

Rubinstein discusses a number of topics, including raw intelligence vs psychological insight and its importance in economics (see also here). He has, in my opinion, a very developed and mature view of what social scientists actually do, as opposed to what they claim to do.

Rubinstein reminds me strongly (in intellectual style, manner of speaking) of other great Israeli academics I have known. Such people are a treasure.

Ariel Rubinstein of Tel Aviv University and New York University talks with EconTalk host Russ Roberts about the state of game theory and behavioral economics, two of the most influential areas of economics in recent years. Drawing on his Afterword for the 60th anniversary edition of Von Neumann and Morgenstern's Theory of Games and Economic Behavior, Rubinstein argues that game theory's successes have been quite limited. Rubinstein, himself a game theorist, argues that game theory is unable to yield testable predictions or solutions to public policy problems. He argues that game theorists have a natural incentive to exaggerate its usefulness. In the area of behavioral economics, Rubinstein argues that the experimental results (which often draw on game theory) are too often done in ways that are not rigorous. The conversation concludes with a plea for honesty about what economics can and cannot do.

Here is Rubinstein's Afterward to the 60th anniversary edition of Theory of Games. It is only a few pages and definitely worth reading if you have any interest in game theory, or if you are pressed for time and can't listen to the podcast. See p. 634:

So is game theory useful in any way? The popular literature is full of nonsensical claims to that effect [Remember the FCC bandwidth auctions?] ... Most situations can be analyzed in a number of ways, which usually yield contradictory "predictions" ...

See also Venn diagram for economics :-)

Note Added: Ariel Rubinstein found this post and sent me a nice email with a link to this photo album of cafes around the world where he likes to work. Below is one of the places I've actually been to (Brewed Awakening in Berkeley). I guess academics should not complain about our lot in life :-)

While visiting Vanderbilt over spring break, I discovered that astrophysicist Bob Scherrer and I share a couple of boyhood interests: science fiction and strategic games. Bob actually writes science fiction, and still plays board games with his kids, whereas I switched long ago to "serious" literature and don't play or design games anymore.

But from age 11 to 14 or so (basically until I hit puberty and discovered girls), I spent every Saturday at the local university simulation gaming club, playing games like Panzergruppe Guderian, Starship Troopers or Dungeons and Dragons with college students and other adults. Bob tells me that I should have saved my collection of these games -- that they'd be very valuable today! Actually, the design of games and rule systems interested me even more than play.

Although I admire the elegance of classical games like Chess and Go, I prefer simulation games. More specifically, I enjoy thinking about the design and structure of these games. A good analogy is the distinction between natural science and mathematics. The former attempts to distill truths about the workings (dynamics) of the natural world, whereas the latter can be admired solely for its abstract beauty and elegance. To me Chess sometimes feels too finite and crystalline. The challenge of formulating a system of rules that captures the key strategic or tactical issues facing, e.g., Stalin, or an infantry platoon, or the ruler of a city state, or even a science postdoc, is just messy enough to be more interesting to me than the study of a finite abstract system. To some extent, every theoretical scientist, economist and financial modeler is participating in a kind of game design -- building a simplified model without throwing away the essential details.

I think role playing games are overly maligned, even among the community of gamers. Under ideal circumstances, role playing games are highly educational, and combine components like story telling, negotiation, diplomacy and team building. At the club I attended one of the "game masters" (I know, it sounds silly!) was a portly older man named Bill Dawkins, who preferred to be called Standing Bear (his Native American name). Standing Bear, though possessed of limited formal education, was widely read and had lived a vast life. He was the most creative story teller and world creator I have known. His ideas were easily as original and interesting as those I had encountered in science fiction and fantasy writing. Each of the role playing campaigns he created, taking place over years, was a masterpiece of imagination and myth building. He attracted scores of players from around the region. I often found myself playing alongside or against people I barely knew, although some came to be close friends.

Economist's View notes the passing of Anatol Rapoport, a mathematician turned game theorist and political theorist. I first discovered Rapoport from his introduction to an edition of von Clausewitz's On War. I found the introduction far more lucid and useful than von Clauswitz's own presentation. You can often detect a first rate thinker from a relatively short piece of work, and this brief introduction piqued my interest in Rapoport many years ago. As noted here,

I read some of his 1984 book "Mathematical Methods in the Social and Behavioral Sciences" and it's a great book. There are not many people who have a strong and original mathematical mind and yet know how to apply it with wisdom, but Rapoport's reach and depth in the book is hugely impressive.

Rapoport was the author of Tit for Tat, the benevolent strategy for prisoner's dilemma that won the earliest tournaments conducted by Axelrod at Michigan.

Globe&Mail: That year also saw publication of political scientist Robert Axelrod's seminal book, The Evolution of Co-operation, which asked a simple, yet age-old, question: If living things evolve through competition, how can co-operation ever emerge? A computer tournament was organized to study the relationship of game theory to evolution -- a variation on the Prisoner's Dilemma. Entries came from the world's top theorists.

Dr. Rapoport entered a program he wrote called Tit-For-Tat, consisting of four lines of code. It was by far the simplest entry, and it won. Betraying the retributive implications of its name, the program opened by co-operating with its opponent. Thereafter, it played exactly as the other side had played in the preceding game. If the other side had defected, Tit-For-Tat also defected for that one game. If the other side had co-operated, it co-operated on the next round.

"In effect, Tit-For-Tat punished the other player for selfish behaviour and rewarded her for co-operative behaviour -- but the punishment lasted only as long as the selfish behaviour lasted," observed Metta Spencer, editor of Peace Magazine, on the occasion of Dr. Rapoport's 90th birthday. "This proved to be an exceptionally effective sanction, quickly showing the other side the advantages of co-operating. . . . It also set moral philosophers to proposing this as a workable principle to use in real life interactions."