For the next several discussions, we're going to be talking about an area that I find fascinating, a domain called game theory. Game theory is a branch of mathematics. Like many of the things we've been talking about in this entire course, it's a much larger subject than we can do justice to in this kind of framework. What I'm going to try and do is give you some of the highlights, important ideas of game theory as they apply to cognitive science, as they apply to human behavior,and human decision-making, and to talk about some of the ways in which computational systems and simulations can be used to illuminate some of the situations of game theory. Game theory is not as you might suppose about board game, it can be about board games actually, but really it's about making decisions in the presence of other decision-making agents. That's really the main idea of game theory, is that you're looking at how intelligent agents, and by this I could mean animals, computers, people make decisions in the presence of and knowing that they are in the presence of other intelligent decision-making agents. It's a fascinating area. The origins of game theory are really in the 1950s. John von Neumann and Oskar Morgenstern wrote a book called Theory of Games and Economic Behavior. Games theory was then applied to some economic situations, but really during the 1950s and much of the '60s, the emphasis in game theory was on military situations, on nuclear deterrence and so forth, which put some people off from the subject because they didn't want to be studying a subject whose main applications were in predicting the results of nuclear war. But over the years and then the last 40 years or so, game theories really blossomed into a much broader field dealing with things like evolutionary biology, with things like multiple computational systems, demanding or sharing resources, with human decision-making, along with political science and with cognitive science. Now, why do I spend some time on this in this course? Game theory is not always a staple of cognitive science courses. I believe it should be, and in a way this reason is indicated by this graph that I'm showing. So what am I showing here? This is a graph I got off the web. It may not be completely up-to-date, but the basic idea you can see on the x, this is a graph of the expansion of cortical volume of brain volume in human evolution. So the x-axis goes back three and a half million years, and you see that at the far right there, the volume of the brain case was about 400 cubic centimeters. As evolution has taken place, as human evolution has taken place, brain volume has tripled essentially to the point where we have it now for Homo sapiens. Homo sapiens by the way is not in the fossil record the very largest brain volume, but the overall trend in the past three and a half million years has been a vast increase in brain volume. One of the challenges in explaining human evolution is to explain why this happened. It's an extraordinarily dramatic change in the evolutionary record. One of if not the most dramatic changes in all of evolution this is a relatively short time evolutionarily speaking for there to be a tripling of brain volume. Why is that occurring? Why did that occur and conceivably as human beings continue to evolve and over millions of years, it may continue to occur? But it came at a cost. I mean, we spend a lot of our caloric resources to maintain this large and expensive brain. We have extended childhood periods, human beings have an extended juvenile period which is spent in learning and being acclimated culturally, and that too is a result of our large brain but that long juvenile period is a period of relative dependence and helplessness. So these are stern costs that we pay for our large brain. What was the advantage? Why did we need? Why did this line of evolutionary descent? What was the cause, the driving force behind this increase in brain volume? Now, there are different suggestions for that, it's not a closed issue. But one rather compelling story is in essence that this graph is its own explanation. People got smarter because people were getting smarter. It's an arms race being shown here. In order to deal with smarter human beings, in order to make friends, take revenge on enemies, deal with rivals for resources or for mates, strike alliances, make deals, gain trust, in order to do those things with smarter colleagues, you need to be smarter yourself. So the arms race was not explained, it would not primarily be explained in this case by people had to get smarter to escape saber tooth tigers, it's people had to get smarter because they were making decisions in the presence of other decision-making people. This is why I find game theory so relevant to cognitive science. It's because much of our cognitive machinery goes into this social reasoning, into reasoning about social situations and reasoning about how to deal with other people. Now, game theory is one format, one mathematical tool for dealing with these situations. It's not the only one and it's an extremely interesting and powerful toolkit for describing and dealing with these situations. But in a way even though I'm fond of the subject and I'd like to talk about it in a cognitive science course, I think it's also important to remind those who are watching that this is not the end of the story as far as social reasoning is concerned, there's much more to be said on that story. But this is an interesting branch of mathematics applied to this social reasoning. So with that, I'm going to start with a fable, a classic game theory situation told as a fable. The fables that I'm going to tell it, I made it up, but it's based on a real imaginary story if that's not too much of a self-contradiction, a real story that goes behind one of the classic situations of game theory. It's called the prisoner's dilemma. So we're going to start out with the story of Bonnie and Clyde. That's not actually Bonnie and Clyde, that's Warren Beatty and Faye Dunaway Hollywood movie version of Bonnie and Clyde. They look a lot more glamorous than the real Bonnie and Clyde did but we'll let that pass. Anyway, so Bonnie and Clyde were bank robbers in the 1930s in this fable, so I'm just making up the whole rest of the story. The police track down Bonnie and Clyde and chase them, Bonnie and Clyde are driving in their car, the police are driving in their cars. They chased them through corn fields in the middle of Nebraska or whatever, and finally they capture Bonnie and Clyde, and they take them both back to police headquarters. Now the question is, can they actually convict Bonnie and Clyde of any of the crimes that they've committed? They don't have any of the bank loot on them. So can they actually convict Bonnie and Clyde of any of the crimes that they've committed? So here's what they do, here's what the police do. They take Bonnie and Clyde and they put them in separate rooms. Again, without loss of generality as the mathematicians say, we'll say what the police say to Bonnie in this case. Here's what they tell Bonnie, "Bonnie, we're giving you the very same deal that we're going to give Clyde, and he's going to get the same deal and you both know that. Here's the deal. It's a one-time-only deal and you got to decide while you're in this room. If you rat Clyde out and he remains faithful to you, he clams up. In other words, if you rat Clyde out but he clams up and doesn't tell us anything, then you're going to be in effect rewarded, you're going to go free and Clyde will get 20 years in prison." If he rats you out and you remain faithful to him, then the opposite will happen. He'll get rewarded. He goes free and you get 20 years in prison. So you rat him out, you go free, he gets 20. He rats you out, he goes free, and you get 20. If you both rat each other out, then you'll both get 10 years in prison. Finally, if you both remained faithful to each other and don't say anything, if you both clam up, then all we can get you on is reckless endangerment of corn and so a misdemeanor or something like that. Basically, you'll both get one year in prison. So Bonnie takes this. Now, you have this choice. Clyde has the identical choice, you make your choice now whether to clam up or whether to turn stool pigeon and rat him out. You make that choice. In the meantime he's making that choice. What are you going to do? So here's again, a summary of this situation and text. If you confess and Clyde doesn't, you'd go free and he gets 20. If you don't confess, if you clam up and if he does, that is he rats you out, then he goes free and you get 20 years. If you both confess you both get 10 years in prison. If you both clam up, you both get one year. So Bonnie draws out this matrix. Notice the structure of this matrix, it's a two-by-two matrix. Bonnie's choices are the two corresponds to the two rows, Clyde's choices correspond to the two columns. Bonnie and Clyde have identical situations and identical choices of strategy. The choices that they can make are essentially choices of strategy and what we're thinking of as a game here. They're making their choices secretly without the knowledge of the other party. But once their choices are made, those choices will be revealed to both parties and the result of the choice can be seen here in this matrix. The matrix itself, Clyde can draw out the exact same matrix. So the matrix is public. That is, this arrangement of rewards is known to both parties. However, the individual choices that Bonnie and Clyde are going to make, they make in secret simultaneously, and then they reveal their choices simultaneously and see what they've got. That may seem like a bit of an artificial constraint, but it actually captures many interesting social situations. Not all, but many. So Bonnie writes out this matrix. Her strategies are written in red and the results of playing her strategies are also written in red here. In other words, if I clam up and Clyde clamps up, then we both get one year. If we both remain faithful to each other, we both get one year. If I remain faithful and Clyde turned stool pigeon, I get 20 years and he goes free. If I turn stool pigeon and Clyde remains faithful to me, than he gets 20 years and I go free. If I rat Clyde out and he rats me out simultaneously, then we both get 10 years in prison. Now, here's one way of reasoning about this situation. This situation called the prisoner's dilemma, it's a common little test situation in games theory. But it's a really interesting one, and much has been written about it over the years. It's called the prisoner's dilemma after a situation like the one I'm describing. The classic descriptions don't employ Bonnie and Clyde, they just employ prisoners A and B. But think of Bonnie's reasoning. Look at it this way; suppose Clyde decides to be faithful. Suppose I trust Clyde and I think he's going to be a faithful guy, and he's not going to rat out, then I have two choices. Either to be faithful to him or to rap him out. If he's going to be faithful, then if I'm faithful, I get a year in prison. If I rat him out, I get no years in prison, I go free. So if Clyde is a faithful guy, I should turn stool pigeon, because I go free which is better than getting a year in prison. On the other hand, suppose Clyde's a rat. Suppose he's going to rat me out. In that case, if I remain faithful to him, I get 20 years in prison. If I rat him out, I only get 10 years in prison. So it seems to me, Bonnie, that no matter how I read Clyde's personality, I'm better off by ratting him out than by clamming up. I'm better off being a rat. What about Clyde's reasoning? Well, his matrix actually is in, from his point of view the exact same. It says, "If Bonnie clams up, I'm better off ratting her out. I get zero years instead of one. If Bonnie turns stool pigeon, I'm better off ratting her out. I get 10 years instead of 20." Using that reasoning, and it seems impeccably logical reasoning, using that reasoning, both Bonnie and Clyde rat each other out and they both get 10 years in prison. They've made the logical choice. In this case, being a stool pigeon is what in game theory is called a dominant choice. A dominant choice being a choice of strategy that does better for you no matter what the other player does. Regardless of the other players choices, you're better off making this choice. So being a stool pigeon is a dominant choice for both Bonnie and Clyde, and if they both make that dominant choice, they both get 10 years in prison. What's wrong? Well, yeah, all seems pretty logical. But if they both remain faithful, they both would have only had one year in prison. It seems like temptingly, there was a better solution for them both just by clamming up. Then the solution that they reached through impeccable logic. Impeccable logic led them to defect on one another instead of cooperate with one another. That impeccable logic led to 10 years in prison for them both instead of one year in prison for them both if they had both cooperated. This is what's called the prisoner's dilemma situation. The prisoner's dilemma is a generic term for situations like this. What I mean by situations like this, let me be specific, the formal conditions of a prisoner's dilemma are these. From the red player's standpoint, the best result is if I defect and the other player cooperates. The next best result for me is if we both cooperate, the next best result after that for me is if we both defect. The worst result for me is if I cooperate and the blue player defects. So just generalizing the players to read and blue, that ordering from the red player standpoint is what defines a prisoner's dilemma. The blue player also has the same reasoning, that is, you could write the same thing out from the standpoint of the blue player. There's one other condition on the prisoner's dilemma which is, we'll talk a little bit about it later. But the basic idea is just that we're both better off cooperating than trading defections. So that's an idea that will in fact come up later as we're discussing this. The prisoner's dilemma therefore, it's not just the matrix that I showed you, it's a generic situation in which two people can choose to cooperate or defect and logic seems to dictate that they both defect. But they're both better off if they cooperate. It's a little maddening actually. It does apply to in one way or another, in a loose way. I won't get too specific about this. But to many situations in life, one of the reasons that the prisoner's dilemma is so often studied in game theory, is because it doesn't seem to be this abstract irrelevant mathematical situation, you are living with a roommate who cleans the fridge. If your preference is that you lie on the couch and your roommate cleans the fridge, his or her preference is that he or she lies on the couch and you clean the fridge. You could also choose both not to clean the fridge in which case it gets pretty stinky, or you could both choose to clean the fridge which is not the most pleasant thing, but could be worse. In other words, you could both cooperate or one of you could cooperate or he could both defect. Your favorite choice, and this is that you defect while the other player cooperates, that's what you really want. I'll lie on the couch, you'll clean the fridge. That's what you really want, but you may decide both to cooperate because that's better than the result of both defecting or you might think so anyway. The Prisoner's Dilemma shows up in those kind of situations. It shows up in situations where it's in your interest to defect from others who are cooperating. It could be more than two people. One of my favorite examples of this and it's a life or death example is represented by the sign in case you see this in concert halls or in auditoriums. In case of fire, walk don't run to the nearest exit. That's a meaningful statement. We are all safer if we walk. However, there was a strong temptation to run hoping that everybody else will walk. In other words, what you'd really like maybe in your heart of hearts is that, you defect, you run while everybody else cooperates. But if everyone chooses to defect and everyone runs, then indeed we are all less safe. So the Prisoner's Dilemma is not some obscure idea. It represents some basic recurring situation in human affairs. We're going to talk more about the prisoner's dilemma as we go along, but before going on, I just want to point out, we've already seen, let me go back to this matrix. This matrix is representative of not the entire, but a large branch of game theory. The idea again is that you have two or perhaps more players, each of whom has two or perhaps more strategies, and they choose simultaneously. They choose privately among their strategies and then they reveal their choices simultaneously, and see what they got in the matrix. The matrix is known to all. So again as I said, that may seem like a fairly artificial set-up, but it adequately models many situations in human affairs and in game theory. Now, a few basic important ideas from game theory before we proceed further. Starting with the portrait that you've already seen, those games, a couple of things. First, there's an important division between what are called zero-sum and non-zero-sum games. In zero-sum games, every entry in a matrix like the one you just saw has to add up to zero. That is, if I gained three, you lose three, if I gain 10, you lose 10. So a zero-sum game in a two-person game is one in which we are really our interests are implacably opposed, we are enemies. Anything I gain, you lose, and vice versa. So our interests are really completely opposed. That's what a zero-sum game is. A non-zero-sum game is one in which our interests are not completely opposed or at least it is the case that the situation is more complex than anything that I get you lose. The Prisoner's Dilemma as you can quickly recognize is a non-zero-sum game and virtually, all the interesting games in the world are non-zero-sum games. Zero-sum games as it turns out, we're not going to go into this in depth. In a game theory course, you would see much more about zero-sum games, but zero-sum games turn out to be actually fairly easy to analyze. You can analyze zero-sum games and come up with strategies for the players to use that will be optimal for their purposes. I won't go into much detail about that, but suffice it to say that zero-sum games are easier than non-zero-sum games. Fortunately, they're not as common really. I mean, it is almost never the case that you and another party are implacably opposed. That's true even when modeling things like war. It's rarely the case that when two countries go to war, one of them wants to completely annihilate the other. They may have a mutual interest in finding a peaceful solution. So even war in virtually every case is not a zero-sum game. You really have very few enemies. Most zero-sum games are artificial, things like baseball, or chess, if I win, you lose, that's it. But in real life, non-zero-sum games are much more plentiful and they're much more interesting. Second interesting division is between two-person and n-person games. The Prisoner's Dilemma that you just saw is a two-person game, Bonnie and Clyde playing it. There could be three-person games in which somebody is trying to reason about what will happen as two other people make decisions, and in that case the matrix is not a flat matrix, it's a matrix in [inaudible] . That is you have to have entries for what Player 1 will do, Player 2 will do, and what Player 3 will do. Sometimes, people even look at four or five person games, but those get really complicated. More typically, what will happen is, instead of a two-person game, people look at n-person games where n is large, and it's something like you making a decision not just in the presence of one other person, but in the presence of a whole crowd. So n-person games are the way in which games are setting is often like two person games, some 3-person games, and then thousand person games. That's accounts for much of the literature in game theory. In the prisoner's dilemma, Bonnie and Clyde each had two choices they could choose between. In many situations there are more than two choices, there are 15 or 20 or 100 choices. There could also be games in which you have an infinite number of choices. For instance, your choice is to pick a real-valued number between zero and one. That's your strategy. In that case, there really are an infinite number of choices, that you could make of strategy. But many of the games that we'll talk about by enlarge are going to be games with finite number of choices. Finally, and this is a very important distinction. There are games that involve iterated versus non-iterated situations. In the prisoner's dilemma situation that I just showed you, Bonnie and Clyde are playing this game exactly once. Once the game is over, they'll know what the other one did, and they will never be able to play the game again. In many, many interesting situations, the game is not just played once, it's played repeatedly. So I might play this game, this prisoner's dilemma game with you and I might play it again knowing what you did last time. In other words, the second time that I play the prisoner's dilemma game with you, I know whether you cooperated or defected last time and that might influence my choice for my next decision. The roommate situation is a little bit like that. If I lie on the couch and make you clean the fridge today, you might decide, this is not such a good arrangement. Next time, the roommate is going to lie on the couch and you, Mike, are going to have to clean the fridge. So an iterated game can be a very different situation than a single-shot game and non-iterated game. Let me show you another prisoner's dilemma matrix and talk about. Notice that here the numbers are points, they're positive numbers. So this is indeed a prisoner's dilemma situation. The players are named red and blue. Red and blue both have strategies of cooperate and defect. If they both cooperate, they both get three. If red cooperates and blue defects, blue gets five and red gets zero. If red defects and blue cooperates, red gets five and blue gets zero. If they both defect, they both get one. This obeys the formal conditions of the prisoner's dilemma, that I showed you before and you should check that, thinking of these as dollars or points or something like that. Something that you want to get. Unlike the Bonnie and Clyde situation where the numbers represented years in prison. These are numbers that represent a reward, okay? Now, historically in psychological experiments, there were a number of experiments through the years like the 1960s when, for example, psychology researchers would get undergraduates to play an iterated prisoner's dilemma using this kind of matrix with each other. So in other words, you put two students across the table, you show them this matrix, and then you give them a choice. It's going to be an iterated game. So they're going to be able to repeatedly make choices about whether to cooperate or defect. Depending on their choices, they may alter their strategy for the next time through. But typically, what would happen in these psychological experiments is that the two parties would begin by cooperate and the rewards here might be tokens or something that could be traded in for prizes at the end. So they were actually offering rewards for this. Typically what would happen is the two parties would start by cooperating. They're getting three points each time through. Then maybe one player gets a little bored or just wants to shake things up a little bit, let's say that red decides to defect. So red gets five and blue gets zero. Then blue gets a little angry and blue defects and maybe blue gets five and red gets zero, and then they start defecting more and more. They end up really hating each other by the end of the laboratory situation and they end up both getting ones, defecting on each successive round. So this an iterated prisoner's dilemma situation and it's one that is used in a psychological experiment to see how people might actually behave in this iterated situation and the story doesn't seem positive. That is it looks as though people may begin by cooperating, but they end up defecting and not liking each other. That could be a pretty depressing story. But in the 1970s, a political scientist named Robert Axelrod decided to hold a computer tournament in which people would send in computer programs to play this very matrix with other entrance in the tournament. In other words, each party could send in a computer program that would play an iterated prisoner's dilemma game with or against, if you want to put it that way, another computer program and they would play perhaps 100 rounds of this particular matrix. The rules were each computer program could know what the other program and itself had done in all the previous rounds. So if I'm one of these computer programs, before I make my choice in the 50th surround, I can look at what I and you have done in the previous 49 rounds and maybe alter my decision accordingly, okay? So Axelrod called for people to submit computer programs, that would be used in a tournament of this kind. He wrote about the results in a truly fascinating book called, The Evolution of Cooperation and the results of that tournament and some of the insights gained from it will be the subject of our next discussion.
