Game Theory Cindy ChengHicksville High SchoolLong Island Math Fair 2018Abstract The main idea and purpose of this paper is to discuss game theory and its numerous applications. There is a brief history of how game theory emerged as a mathematical concept. Fundamentals and basic terms are then explained in order to increase the understanding of the specific examples listed in this paper. Various factors, such as number of players, motives of players, and benefits of payoffs affect the outcome of each game. In addition, zero sum games and non-zero sum games are later discussed and related to Nash’s equilibrium, an essential concept of game theory. Game Theory Game theory allows us to make smart decisions that can lead to the best outcomes. For numerous years, biologists and economists have been using game theory to determine specific strategies that may result in a specific consequence. From winning a game of chess to deciding the next move in an intense war, learning game theory can help us to understand the impacts of our choices. Game theory was “established as a field after the publication of Theory of Games and Economic Behavior in 1944 by John von Neumann and Oskar Morgenstern” (Turocy & Stengel). It took situations where there were “players”, or multiple decision makers, whose choices led to a variety of possible outcomes. In today’s world, knowing different strategies can help people achieve their professional goals, whether it is someone winning a gambling game, or a neuroscientist discovering how emotions and behavior affect a patient’s decision-making skills. A popular example in game theory is the Prisoner’s Dilemma. It is a game which involves two players. Each player has two different choices: “cooperate” and “defect”. “Prisoner’s Dilemma” got its name because two people were suspects of a crime and there was no evidence pointing to who the actual criminal was. The rule was that if one of them accused the other, the accuser would be let free and be sentenced to zero years in prison, while the person being accused would be sentenced to three years in prison. It would be the same if the other person was the accuser. However, if they both stayed silent, they would both only be sentenced to one year in prison each. If they both accused each other, they would both go to prison for two years each. “Cooperating” would be staying silent and not accusing the other person, while “defecting” would be accusing the other person of the crime. The following table shows the different possible outcomes of this game: Player 2: Player 1: Note that the numbers in the table that are on the upper right of each box represents player one’s number of years in jail and the numbers on the bottom left represents players two’s number of years in jail. For instance, the upper right box in the table shows that if player one “cooperated” while player two “defected”, player one would have sentencing of three years and player two would have a sentencing of zero years. If player one chose to betray the other and “defect”, player two would serve time in jail while player one is free. This would result in a total of three years in prison. However, if both chose to “cooperate”, the total would be two years. Cooperating is more beneficial to the pair, while defecting is more beneficial to one person. When both people “defect”, the total number of years the pair has to serve is four, which is essentially the worst outcome in the game. The outcomes of this game are changed when it is played several times. “In such a repeated game, patterns of cooperation can be established as rational behavior when players’ fear of punishment in the future outweighs their gain from defecting today.” (Turocy & Stengel) Another popular example in game theory is the Monty Hall problem. Monty Hall was a famous host of a game show where a contestant picked one out of three doors in hopes of picking the one with a nice expensive car behind it (Binmore 172). The other two doors have goats, or “zonk” prizes. Let’s suppose you are a contestant on the game show and you are asked to pick a door. You choose door #1. Monty Hall then opens door #2, revealing to you a door with a goat behind it. He then asks if you would like to keep your choice of door #1, or switch to the other door, which in this case would be door #3. Since Monty Hall is the host, he knows whatever is behind each door. Should you switch doors, changing your decision and ultimately risking the chance to win a car if you had picked right the first time? Is Monty Hall trying to trick you and make you paranoid by showing you a “zonk” prize behind a door you hadn’t chosen? Suppose door #1 had a goat behind it, and since the host revealed that door #2 had a goat, if you switched to the other door, you would win the car. This is similar to if you picked door #2, the host reveals a goat behind door #1, if you switched your answer, you would win the car. However, if you picked the door with the car originally, and the host revealed a door that had a goat, if you switched doors, you would get the goat and lose the game. Therefore, by always switching doors, you will win 2/3 or 66.7% of the time, rather than only having a 1/3 or 33.3% chance of winning if you don’t switch doors (Binmore 173). The strategy to have a higher chance of winning the car is to always switch doors. Some may still argue that, regardless of whether you switch your answer after one of the doors revealed a goat, you would still have a 50/50 chance of winning the the car. This is not true due to proven statistics and probability. An easier way to understand the Monty Hall problem is to imagine if there were fifty cards. One of the cards is red and the rest are blue. When they are faced down, you are unable to see the color. The goal is to choose the red card. Initially, there is a 1/50, or 2% chance in choosing a red card. Let’s say you choose card #1. I then reveal all the other cards except for card #39, giving you the choice to either keep your original choice or change it to card #39. The more probable card to be red would be card #39 because after revealing cards #2-38 and #40-50, showing that they are blue, the probability of choosing the red card becomes “concentrated” in card #39. At first, it had a 2% chance of being red, but now, it has a 98% chance. Therefore, switching your choice would statistically give you a higher chance of picking the red card. In contrast to the previous shown simple models of games, another mathematical model of a game, known as the extensive form, “is built on the basic notions of position andmove, concepts not apparent in the strategic form of a game” (Ferguson 49). Several examples of the extensive form of a specific game include chance moves, information sets, and the game tree. Chance moves can be vital in determining the outcomes of a game. Rolling die, the dealing of cards, or the decision of who has the first turn can all influence who wins the game. Information sets are pieces of information available to different players throughout the game. For example, in the card game “Cheat”, cards are placed sequentially and face-down in a pile. Players are allowed to lie about the cards they have placed down, but if caught lying by another player, that player lying must take the entire pile. The goal of the game is to deceive your opponents by bluffing and ultimately get rid of all of your cards. The information set in this game is that individual players know their own cards, the cards that others have claimed to put down, and the number of each type of cards there are in the deck. In a standard deck of cards, there are four of each number/face cards. If you have all four jacks, for instance, you know there cannot possibly be other jacks in the deck. Therefore, if an opponent plays a card and claims it is a jack, you can call them out on their lie, and make that player take the entire pile of cards, which gives you the advantage in the game. The game tree “is a directed graph, (T,F) in which there is a special vertex, t0, called the root or the initial vertex, such that for every other vertex t ? T, there is a unique path beginning at t0 and ending at t” (Ferguson 49). This basically means that each pathway in the tree is unique, and there are no loops that may lead to a different outcome. The following is an example of a game tree for the Ultimatum Game: In the Ultimatum Game, “there is a fixed number, such as 5, of dollar bills for both players. Player One (Ann) makes an offer how to share it, which Player Two (Beth) can either accept or reject. If Beth accepts, the bills are divided as agreed upon. However, if Beth rejects, nobody gets anything” (“Sequential Games I”). The game tree above shows each possible unique pathway and the payoffs of each decision. When this game is played with various pairs of people, the outcomes can vary depending on the relationship between the two people in the pairs. Player One is usually more lenient and giving to Player Two if the people in the pair know each other and are close. If they don’t know each other, Player Two is assumed to be more likely to accept any offer, because gaining a low amount of money is better than gaining nothing at all. However, one sided offers, where Player One offers Player Two a very low amount of money, are usually rejected. This is due to the reason that human behavior is generally shaped by fairness, revenge, empathy/sympathy, and equality. Interestingly, when a person is offered ten dollars, they would gladly accept. However, when that person is told that his/her acceptance of the offer would result in someone else receiving twenty dollars, their decision may change to rejecting the offer. People may feel that they would rather get nothing than to get a low amount relative to the other person. They may get revenge on the other person, by preventing that person from getting a high amount of money, for being placed in a lower position of reward relative to the other person. Although humans have an individual preference for equality, they may sacrifice a reward to penalize someone else for their inequality. Games that are zero-sum mean that “whatever one player wins comes at the expense of other players” (Bennet & Miles 46). The other person loses something as a result of one person winning, or gaining something. For example, tennis is a zero-sum game because there is no such thing as a draw. If one player wins, it definitely means his/her opponent has lost. On the other hand, non-zero sum games are games in which one person’s win does not necessarily mean another person’s loss. They could both win the game. For example, in economics, trading goods is beneficial to both countries. If one country had an abundance of corn and a scarcity of coffee beans, then trading with a country that had an abundance of coffee beans and a scarcity of corn would benefit both. “In 1950, John Nash, as a 21-year-old grad student at Princeton, solved the problem of finding equilibria in nonzero sum games” (Rosenthal 55). In zero-sum games, equilibrium is a list of strategies that will cause no improvements in the payoffs, or the desirability of outcomes, of a player changing his/her own strategy. Equilibrium exists when players realize that changing their strategies could lead to a worse outcome than if they kept their original strategy. This relates to both players “defecting” in the Prisoner’s Dilemma. If the other person accused you, your best option would be also to accuse that person. It is necessary to keep in mind that equilibrium does not always mean the best outcome for all of the players. Let’s suppose two different companies, Apple and Samsung, wanted to agree to adopt a common face-recognition technology. They will choose to adopt either “Face Recognition Software #1”, which we’ll call FRS-1 or “Face Recognition Software #2”, which we’ll call FRS-2. If the companies disagree to choose the same software, they will go their separate ways with incompatible formats. Let’s also suppose that choosing FRS-1 is more advantageous for Apple and choosing FRS-2 is more advantageous for Samsung. This causes a unique shift in the payoffs for each situation. The following table demonstrates the various results with scaled outcomes: Samsung’s ChoicesApple’s ChoicesFRS-1 FRS-2FRS-1(7,3)(0,0)FRS-2(0,0)(3,7) Based off of the table above, if Apple chose FRS-1 and Samsung decided to also choose FRS-1, the outcome would be much more beneficial to Apple than it would be for Samsung. However, if Samsung didn’t choose FRS-1 and instead went with FRS-2, the outcome for Apple would be worse. By not cooperating, there would be a payoff of (0,0) rather than cooperating and getting a payoff of (7,3). Consequently, (FRS-1, FRS-1) is a pure strategy equilibrium. Suppose Samsung reconsiders and thinks about choosing FRS-2. Since Samsung’s choices have been restricted to the first row of the matrix (due to Apple’s choice of FRS-1), if the company were to carry through with that choice, they would end with a payoff of (0,0), so sticking with the original choice would be better (Rosenthal 55). Likewise, (FRS-2, FRS-2) is another pure strategy equilibrium. These various strategies refer to Nash equilibria. The Nash equilibrium strategy has both Apple and Samsung go for their preferred choices, 7/10, or 70% of the time and give in the other 3/10 or 30% of the time. Nash proved that there is at least one equilibrium in every non-zero sum game. The psychological aspect of game theory cause social dilemmas which influence the outcomes of numerous games. For instance, in the stag hunt game, two people are hunting. There are two rabbits and one stag in the area they are hunting. They could either choose to hunt the stag, which has a total of six “units” of meat, or hunt the two rabbits, which have one unit of meat each. Two people are required to hunt the stag, whereas only one person is required to hunt a rabbit. Player 2Player 1 Stag Rabbit Stag (3,3) (0,2)Rabbit (2,0)(1,1) The matrix above represents the situation. If both people decided to work together to hunt the stag, each would receive three units of meat. However, if one person decided to attempt to hunt the stag and couldn’t, the other person would end up hunting the two rabbits and receiving two units of meat. If both decided not to hunt the stag, each would hunt a rabbit and receive one unit of meat each. Suppose that the current convention is to hunt the rabbits, but player 1 persuades player 2 to hunt the stag in the future (Binmore 69). No matter what player 1 decides to do, it is in his/her best interest to convince the other person to hunt the stag. If player one succeeds he will get 3 rather than 0 if he was planning to hunt stag and 2 rather than 1 if he was planning to hunt rabbits. Likewise, player 2 may use the same strategy in attempting to convince player 1 to hunt the stag. This leads to a social dilemma and a questioning of trust between the two players. Are there strategies that support the rational cooperation between two players? The Folk Theorem can be described as “any strictly individually rational and feasible payoff vector of the stage game that can be supported as a subgame-perfect equilibrium average payoff of the repeated game” (Ratliff 3). In addition, behavior of the different players can be aligned with game theory. The Dictator game, which is similar to the Ultimatum Game, is a game of trust where there are two players and a sum of $10 is divided between them. Player 1, or the “dictator”, is the person who decides how much of the money to keep and how much to give to Player 2 (Rosenthal 276). This is different from the Ultimatum Game because Player 2 does not have the option to accept or reject the offer; they must accept it. In one study, there were two choices, split the money evenly, or keep $8 while giving the other player $2. Interestingly, the majority of people who participated in the study chose to split the sum of money evenly. Over a series of other studies, results have shown that with the increase of communication and identification between the two players, the higher the probability of Player 1 splitting the sum evenly rather than keeping most of it for him/herself. The results are fascinating because when compared to the results of the Ultimatum Game, more people offered to split the money evenly, even though they knew that if they chose to keep the majority, the other player would have to accept the offer, whereas in the Ultimatum Game, they knew the other person had a choice to accept or reject, but they still wanted to take the majority of the sum of money. In conclusion, game theory can be applied to multiple aspects in life, from the economy of countries, to the behaviors of individuals. For further research, one can study game theory in work environments, and how groups of people come to one decision. Using decision matrices and game trees can help to solve workplace conflicts, for instance, how to divide up the bonus pay amongst the employees (depending on how long the employee has worked there, or what they specifically have achieved for the company. In addition, one can also study game theory in a healthcare environment, finding the payoffs for choosing different kinds of health insurance. Overall, game theory is a unique field that can help with real world problems. Bibliography Bennett, Nathan, and Stephen A. Miles. Your career game: how game theory can help you achieve your professional goals. Stanford University Press, 2011.Binmore, Ken. Game theory: a very short introduction. Oxford University Press, 2007.Ferguson, Thomas S. “Game Theory.” Two-Person Zero-Sum Games, www.math.ucla.edu/~tom/Game_Theory/mat.pdf.Ratliff, Jim. “A Folk Theorem Sampler.” 1996, www.virtualperfection.com/gametheory/5.3.FolkTheoremSampler.1.0.pdf.Rosenthal, Edward C. Game Theory: The Fascinating Math Behind Decision-Making. Penguin Group, 2011.”Theory Chapter 3: Sequential Games I: Perfect Information and no Randomness.” Game Theory through Examples, www.eprisner.de/MAT109/Sequential.html#1. Turocy, Theodore L. , and Bernhard von Stengel. “Game Theory.” CDAM Research Report, Encyclopedia of Information Systems, 8 Oct. 2001, www.cdam.lse.ac.uk/Reports/Files/cdam-2001-09.pdf.