Game Theory - Research Paper Example

? Game Theory Word Count: 3,300 (13 pages) TABLE OF CONTENTS I. Introduction…………….…………….…………….…………….………………..3 II. Game Theory…………….…………….…………….…………….……………....5 III. Decision Theory: One-Person Games………………………………………..….9 IV. Zero-Sum Games………………………………………………………………...11 V. Two-Person Games…………….…………….…………….…………….………13 VI. N-Person Games…………….…………….…………….…………….…………14 VII. Conclusion…………….…………….…………….…………….……………14 I. INTRODUCTION Here, we are going to analyze what is known as game theory. Different types of theory are going to be explained at length in this paper, which include: game theory itself (the normal version); decision theory (one-person games); zero-sum games; two-person games; and n-person games. Game theory is useful for many purposes. First, one must ask, what is game theory? “Game theory uses mathematical tools to study situations, called games, involving both conflict and cooperation. Its study was greatly stimulated by the publication in 1944 of the monumental Theory of Games and Economic Behavior by John von Neumann and Oskar Morgenstern…”1 Before we get into the details of game theory, it is first important to make clear a few definitions. A “game” consists of a competition between two or more parties, although in decision theory, it is possible to have a one-person game. A “player” is a party competing in said game. The state is the information known by a player at a certain point during the game. A strategy is a rule which defines how the player will play the game. The payoff is the value assigned to the result of play, i.e., the outcome—the results of which might be distinct for every player. The main concept behind game theory is that, in a game, each player is trying to maximize their resultant payoff. “The game theoretician is concerned with the mathematical model and with conclusions he can draw from assumptions (in particular about utilities represented by payoffs) that stay put, not with assumptions that capture the entire spectrum of human conflict behavior.”2 At each stage of a game, a wide array of moves is presented to each player. Then, they each decide the move that would be the best choice, to the best of their knowledge, in order to achieve the highest payoff. There are always rules for selecting the proper moves at any point in a game which can be figured out before a game is played—which is called a strategy. Subsequently, it also follows that a game which is very complex, involving many decisions at varying stages can be represented by the strategy of each player. But, the result of any particular strategy really depends on the other players’ moves. Someone on the defensive might be able to calculate the lowest payoff or end result for each strategy (presuming that the particular strategy is somewhat of a secret), selecting the strategy that would result in the best (or highest) payoff. Basically, it is worth noting that one should account for the fact that many players will try to act as rationally as possible, hopefully making corollary decisions which would be deemed ration. To such an end, the main goal is to find a certain set of strategies (one per player) that maximizes each player’s payoff. However, such a selection of strategies should probably be rejected if it is not equilibrium. Equilibrium is basically reached when none of the players can attain a higher payoff by way of utilizing a different strategy, given the decisive actions of the other players. The model which has thus far been described is pretty abstract, although, technically speaking, this theory can be applied to a quite huge range of scenarios—and could be thusly applied to warfare, business, sports, or even politics. Truly, the possible uses of game theory boggle the mind. II. GAME THEORY Game theory in its strategic form is an expression of an extensive game—which is different than the normal game. For all practical purposes, game theory will first be analyzed in its normal form. “This model specifies for each player a set of possible actions and a preference ordering over the set of possible action profiles.”3 The strategic or normal form is a brief way to express an extended game that is manipulatable by various mathematical tools to figure out the most rational way to play the game. The extensive game can be, and will be, in this example, “reduced” to the strategic form in the following way as described by van Neumann and Morgenstern. Each player, before play begins, can and will define how they will play, utilizing a set of rules, which take into account all possible states of information. In one particular game, the second player has exactly two strategies in a game of Risk: 1) the player can ‘win’ by conquering a country or multiple countries with armies; or 2) ‘lose’ his own country’s or countries’ control due to the fact that the other opponents’ armies are taking over the loser’s country/countries with the opponent’s armies. Despite the fact that his decision can be on one of a few branches, this player really has only one viable decision. Since when a single strategy is selected for each player, the probabilistic expected value can be calculated, the relative rationality for each pair of strategies can be weighed. This is not the only way to simplify an extensive game, as there are other models designed to deal with various issues that come up in the standard strategic representation. The issues include the problems of communication, imperfect information, and imperfect recall. Furthermore, the breakdown described above leads to redundant strategies in which for a given player, a certain strategy results in identical payoffs as some other strategy. Such strategies do not enhance analysis and will not be evaluated as part of the solution. This phenomenon is the result of a decision in which one move results in a terminating node while another leads to an eventual second move by the same player. An example of the game of Risk has strategies as broken down into probability, which would look like the following: The strategic form as a standalone game is a novel concept. Now, while some games are simply consisting of one sole decision, made by both players at the same time—here the strategies are the available moves for each player and the payoffs are the results of having played the game. There are at least two fundamental examples of such games which are rather simple to understand. The significance of each of these is demonstrated below. 1) The Political Game of “Chicken” Two players are heading directly towards each other on a collision course. If only one political party turns aside (relenting doing a political deal or “chickens” out), the one who went straight by sticking to his political ideals (the politician who “drives”) wins. If both turn aside from the issue at hand, it’s a tie. However, if neither politician backs down, the catastrophic result is worse than both turning. It is modeled by the following table. This is meant to be somewhat humorous, but it shows that when Democrats don’t back down (aka “drive”), most of the time Republicans “chicken out.” 2) Prisoners’ Dilemma Both players can be prosecuted for a minor crime without any additional information. However, if one informs on the other, the other player can be prosecuted for a more severe crime and he will be pardoned from the minor crime. If both inform on each other, they will both be prosecuted for the more severe crime. The following table illustrates the point: III. DECISION THEORY—ONE-PERSON GAMES Decision theory forms the basis of any kind of rational decision-making. In fact, decision theory is indeed the underlying basis of game theory, as well. When one is presented with a dilemma between several choices, the first thing that he has to do is first evaluate the utility, or relative value, of each possibility. At this point he can then select the best possible choice, which has the highest utility. Major difficulty arises when ambiguity is introduced. This comes from the fact that the person making the decision—for whatever reason—does not know the state of the environment variable which is ultimately going to affect the relative utility (or feasibility) of each choice. For instance, let’s pretend that a woman is going to go shopping. Even this simple example can be categorized into a matrix which describes the behaviors of the individual. So, let’s say this person has low involvement, and she’s not concerned about the differences between brands. This ultimately results in the fact that she is going to have habitual buying behavior—because she just doesn’t care about the brand. But let’s say she is picky about the brand, but is still not necessarily interested in the differences between brands. This would result in her not wanting to buy the product at all. Then, take a few other scenarios. Let’s say this woman’s interest is not specifically interested in buying the product—let’s say, toilet paper. But—there are tons of significant differences between brands. There’s 1-ply, 2-ply, 3-ply, some are cheaper in price, some are greater in price, there’s a sale going on—and she’s totally confused as to which decision to make. Chances are that if the buyer’s involvement is low, but there are a lot of choices, she is just going to pick a random choice out of the variety of toilet paper brands. On the other hand, if this woman’s involvement is high, and there is a significant difference between brands—then she might exhibit complex buying behavior—which would probably include doing price-checks at the end of the aisle, comparing levels of thickness and comfort, and maybe even researching the best brands for the price. This choice of level of activity on her part might also include cutting coupons in order to save on her favorite brand, or some other activity such as reading the newspaper ads—which would in effect, demonstrate the mathematical concept that her buying behaviors were complex and only the result of some extensive mental calculation as to where, when, and how to buy the most cost-efficient but still good quality toilet paper. Of course, it is possible for any decision which is made to be randomly chosen between one or the others. The goal of such a decision is that over several repetitions, there would be a higher net result than constantly choosing a single side. In this case, it is logical to weigh both Single Brand and Other Possible Brands respectively with a probability of . Such a strategy is known as a mixed strategy or a randomized strategy (as opposed to a pure strategy). It only makes sense that, in order for the buyer to strategize wisely, it will depend on two things: a) the buyer’s level of focus; and b) the customer’s brand. To prove this mathematically, if X is the set of decision choices and ,  is  such that . The expected utility is limited by the probability of each result.  where T ? s is the set of possible states,  is the probability of a given state and }. However, it is possible for the decision to be to randomly choose between one brand of toilet paper over another. Here, the decision set X is expanded to  such that  iff  and  and . The utility function is now  where . The goal of such a decision is that over several repetitions, there would be a higher net result than constantly choosing a single side. There should exist  such that . If , , then and . Ex. For example, if B = 35, what is the range of  for which ? is optimal? ?? ?? Plug in variables into the equation: Since the sum of p is 1: Plug in values and solve for p: ;  One then repeats the above steps for the second part of the question. ;  Then one repeats the steps for the third part. ;  Therefore, the overall utility function for a strategy is a collection of individual utility functions for each state which are defined as the probability of that result given that event’s causation. IV. ZERO-SUM GAMES Zero-sum games are two-player games in which a gain for one player represents a loss for the other. This is a special type of game (known either as ‘zero-sum’ or a ‘strictly competitive’ game). The utility function can be described strictly in terms of player 1. All references to player 2’s utility function can be replaced with the negative of player 1’s utility function. The mixed extension of zero-sum games will always have an equilibrium. Several different types of zero-sum games include card games such as War, where two players will throw down cards in an attempt to see who has the higher card (the higher card wins). In the case that the cards the players down are both the same, there can only be one outcome—but the parties have to go to War to find out who won the opponents’ cards. This is called a two-person zero-sum game. An example of the two-person zero-sum game is shown in the table below. A mathematical table which follows definitely shows the difference between player 1 and player 2 in a zero-sum game: In zero-sum games, the reason why these games are called zero-sum is because losing means sudden death. There’s no real ability to “take back” one’s decisions; all decisions made are final, and it’s at the discretion of the winner to regard or disregard pleas for a redo. Of course, everything depends on what player 2 would say. Zero-sum games, since they mean sudden death upon losing—can be very high-stakes games. Consider professional tennis. For example, a professional tennis player, a ‘pro,’ could easily command millions of dollars competing in all four title games—the Australian Open, the French Open, the U.S. Open, and of course, Wimbledon. What are the odds, one could calculate, of winning the Grand Slam (all four of the championships)? First, let’s break it down game by game, set by set. Usually, there are three sets in tennis. In each set, there is best out of seven (7) games, and the winner has to win by two (2). This means that the score cannot be 5-4, for example, because in order to be the winner, the winner would have to win by two, thus meaning that the tennis player would have to get a score of 6-4 to beat the other opponent. The way scoring goes in tennis is, “Love (which means zero), 15, 30, 40, game.” In order to win the game, the person who will win must also win by two points. Therefore, let’s say that two women are playing tennis and their scores are 40-40. When the server gets the point, she would say “ad in” (short for ‘advantage in,’ or “I’ve got the advantage, 40 plus one”). When the server does not get the point, she would say, “ad out” (short for ‘advantage out,’ or, “My opponent has the advantage, 40 plus one”). Whoever won the advantage point plus the extra point would essentially win the game. Here is a mathematical proof proving zero-sum game theory. The mixed extension of zero-sum games will always have an equilibrium. Therefore, it can be prove that: (1)  is an equilibrium iff and (2) If  is an equilibrium then The solution of the mixed equilibrium is found by solving the system of equations. The method is closely linked to the dual problem of linear programming. The idea is to maximize given that  is the system of linear equations. This is equivalent to where , , , , , , . The  are vectors of the expected utility for each player for each pure strategy. Keeping score of tennis games during matches is really not as complicated once one begins to play—as it becomes second nature to the tennis players how to keep score, and they barely even think about it. We will use this example again in the next section. V. TWO-PERSON GAMES Now, as mentioned before, professional tennis is a zero-sum game. Our last example was with two players, but there can be up to four players on one court, thus increasing the amount of probabilities that something unusual could happen in a game. For example, let’s say one partner in a doubles match (of 2 and 2) had to switch quadrants on the court. Here is the mathematical proof of outcome for players (this equation can be used for up to four people, using j1 and j2 as variables for players, although more will be discussed about n-person games in the next section): Basically speaking, two-person games can be easier to predict in terms of outcomes. Normally, the partner who has a stronger strategy has a much better chance of winning. For example, let’s say two people were playing SuperScrabble. One opponent’s strategy is to make a word every turn which will garner at least 20 points apiece. The other opponent’s strategy is to try to get rid of letters that aren’t part of the word “STARLINE,” makes an effort to put high-value letters on a quadruple tile in line with a double-word score (effectively giving her 8 times the points of a normal word), and also tries to get double-double’s, which is when a word lies across two double-word spots (in essence doubling the value of the word two times over, similar to a quadruple word score). Other tricks the second opponent might be using include: saving up letters she does like in order to get a “bingo” (using all 7 letters to spell a word, which adds an extra 50 points to one’s final score for the word); trying to make as many points with the least letters possible, ensuring that the game is longer; and capitalizing on good spaces that can increase the capacity for earning more points. Ensuring that one has a beneficial strategy in place can definitely enhance or improve one’s score. Obviously the second opponent in this game will have the edge because she is trying very hard to strategize and economize in various ways in order to win the game. VI. N-PERSON GAMES This is a table showing the possible outcomes of an n-person game: In this example, we certainly have an n-person game where we have general oppressor(s) versus the people (including the possibility of revolt): VII. CONCLUSION Several distinct types of theory were explained with some reasonable length in this paper, which included: game theory itself (the normal version); decision theory (one-person games); zero-sum games; two-person games; and n-person games. It is hoped that, with the development of game theory, and a good understanding of it—people will not only see the mathematical value of game theory—but also that they will have a type of mastery which helps them to analyze different kinds of situations in which one might think that math would not be traditionally involved, but it actually is. For example, one may be able to use game theory—from anything as simple as winning a card game to as complicated as winning a political election. The point is, it is very important to be able to use practical applications of game theory in real life, because this is what math was ultimately created for—in order that people might be able to live their lives with more efficacy, smoothness, and ease than before these principles were applied to everyday situations. It is the logic of game theory which continues—and hopefully will continue—to inspire people to think “outside the box,” and ultimately help them make rational decisions about the real world. These ‘practical applications’ include being able to deduce from a matrix what the most mathematically sound choice would be, using game theory—in order to make the best decisions. Without game theory, many of the world’s most complex decisions—including those made in politics—would not be acted upon. Because of game theory, the world can be a better place—and a more statistically sound environment in which to live. WORKS CITED Malkevitch, Joseph, et al. “Game Theory: The Mathematics of Competition.” In For All Practical Purposes: Mathematical Literacy in Today’s World. US: Macmillan, 2008. Pp. 467. Osborne, Martin J., et al. A Course in Game Theory. Cambridge: The MIT Press, 1994. Pp. 9. Rapoport, Anatol. Game Theory as a Theory of Conflict Resolution. U.S.: Springer, 1974. Pp. 9. Read More