Introduction to Game Theory

1、Introduction to Game TheoryIntroduction to Game TheoryYale BraunsteinJune 2003General approachBrief History of Game Theory Payoff MatrixTypes of Games Basic StrategiesEvolutionary ConceptsLimitations and ProblemsBrief History of Game Theory1913 - E1. Zermelo provides the first theorem of game theory

2、; asserts that chess is strictly determined1928 - John von Neumann proves the minimax theorem 1944 - John von Neumann & Oskar Morgenstern write ;Theory of Games and Economic Behavior”1950-1953 - John Nash describes Nash equilibriumRationalityAssumptions: humans are rational beingshumans always s

3、eek the best alternative in a set of possible choicesWhy assume rationality?narrow down the range of possibilitiespredictabilityUtility TheoryUtility Theory based on:rationalitymaximization of utilitymay not be a linear function of income or wealthIt is a quantification of a persons preferences with

4、 respect to certain objects.What is Game Theory? Game theory is a study of how to mathematically determine the best strategy for given conditions in order to optimize the outcomeGame TheoryFinding acceptable, if not optimal, strategies in conflict situations.Abstraction of real complex situationGame

5、 theory is highly mathematicalGame theory assumes all human interactions can be understood and navigated by presumptions.Why is game theory important?All intelligent beings make decisions all the time.AI needs to perform these tasks as a result.Helps us to analyze situations more rationally and form

6、ulate an acceptable alternative with respect to circumstance.Useful in modeling strategic decision-makingGames against opponentsGames against ;nature;Types of GamesSequential vs. Simultaneous movesSingle Play vs. Iterated Zero vs. non-zero sum Perfect vs. Imperfect information Cooperative vs. confli

7、ct Zero-Sum GamesThe sum of the payoffs remains constant during the course of the game.Two sides in conflictBeing well informed always helps a playerNon-zero Sum GameThe sum of payoffs is not constant during the course of game play.Players may co-operate or competeBeing well informed may harm a play

8、er.Games of Perfect InformationThe information concerning an opponents move is well known in advance.All sequential move games are of this type.Imperfect InformationPartial or no information concerning the opponent is given in advance to the players decision.Imperfect information may be diminished o

9、ver time if the same game with the same opponent is to be repeated.Key Area of InterestchancestrategyMatrix NotationNotes:Player Is strategy A may be different from Player IIs.P2 can be omitted if zero-sum gamePrisoners Dilemma & Other famous gamesA sample of other games:MarriageDisarmament (my

10、generals are more irrational than yours)Prisoners DilemmaNotes: Higher payoffs (longer sentences) are bad.Non-cooperative equilibrium ? Joint maximumNCEJt. max.Games of ConflictTwo sides competing against each otherUsually caused by complete lack of information about the opponent or the gameCharacte

11、ristic of zero-sum gamesGames of Co-operationPlayers may improve payoff throughcommunicatingforming binding coalitions & agreements do not apply to zero-sum games Prisoners Dilemma with CooperationPrisoners Dilemma with IterationInfinite number of iterationsFear of retaliationFixed number of ite

12、rationDomino effectBasic Strategies1. Plan ahead and look back 2. Use a dominating strategy if possible3. Eliminate any dominated strategies4. Look for any equilibrium5. Mix up the strategiesPlan ahead and look backIf you have a dominating strategy, use itUse strategy 1Eliminate any dominated strate

13、gyEliminate strategy 2 as its dominated by strategy 1Look for any equilibriumDominating EquilibriumMinimax EquilibriumNash EquilibriumMaximin & Minimax EquilibriumMinimax - to minimize the maximum loss (defensive)Maximin - to maximize the minimum gain (offensive)Minimax = MaximinMaximin & Mi

14、nimax Equilibrium StrategiesDefinition: Nash Equilibrium“If there is a set of strategies with the property that no player can benefit by changing her strategy while the other players keep their strategies unchanged, then that set of strategies and the corresponding payoffs constitute the Nash Equili

15、brium. “Source: /./economics/mccain/game/game.htmlIs this a Nash Equilibrium?Cost to press button = 2 unitsWhen button is pressed, food given = 10 unitsBoxed Pigs ExampleDecisions, decisions.Time for ;real-life; decision makingHolmes & Moriarity in ;The Final Problem;What would y

16、ou doIf you were Holmes?If you were Moriarity?Possibly interesting digressions?Why was Moriarity so evil?What really happened?What do we mean by reality?What changed the reality?Mixed StrategyMixed Strategy SolutionThe Payoff Matrix for Holmes & MoriarityPlayer #1Player #2Strategy #1Strategy #2S

17、trategy #1Strategy #2Payoff (1,1)Payoff (1,2)Payoff (2,1)Payoff (2,2)Evolutionary Game TheoryNatural selection replaces rational behaviorSurvival of the fittestWhy use evolution to determine a strategy?Hawk / Dove GameEvolutionary Stable StrategyIntroduced by Maynard Smith and Price (1973)Strategy b

18、ecomes stable throughout the populationMutations becoming ineffectiveWhere is game theory currently used? EcologyNetworksEconomics Limitations & ProblemsAssumes players always maximize their outcomesSome outcomes are difficult to provide a utility forNot all of the payoffs can be quantifiedNot a

19、pplicable to all problems SummaryWhat is game theory?Abstraction modeling multi-person interactionsHow is game theory applied?Payoff matrix contains each persons utilities for various strategies Who uses game theory?Economists, Ecologists, Network people,.How is this related to AI?Provides a method

20、to simulate a thinking agentKM Lecture 4 - Game TheoryYale M. BraunsteinKM Lecture 4 - Game Theory//top/class/histf.htmlYale M. BraunsteinKM Lecture 4 - Game TheoryBased on the assumption that human beings are absolutely rational in their economic choices. Specifically, the as

21、sumption is that each person maximizes her or his rewards - profits, incomes, or subjective benefits - in the circumstances that she or he faces. This hypothesis serves a double purpose in the study of the allocation of resources. First, it narrows the range of possibilities somewhat. Absolutely rat

22、ional behavior is more predictable than irrational behavior. Second, it provides a criterion for evaluation of the efficiency of an economic system. If the system leads to a reduction in the rewards coming to some people, without producing more than compensating rewards to others (costs greater than

23、 benefits, broadly) then something is wrong. Pollution, the overexploitation of fisheries, and inadequate resources committed to research can all be examples of this.Source:/./economics/mccain/game/game.htmlYale M. BraunsteinKM Lecture 4 - Game TheoryFew people would risk a sure gain

24、 of $1,000,000 for an even chance of gaining $10,000,000, for example. In fact, many decisions people make, such as buying insurance policies, playing lottery games, and gambling in a casino, indicate that they are not maximizing their average profits. Game theory does not attempt to indicate what a

25、 players goal should be; instead, it shows the player how to attain his goal, whatever it may be. Von Neumann and Morgenstern understood this distinction, and so to accommodate all players, whatever their goals, they constructed a theory of utility. They began by listing certain axioms that they fel

26、t all ;rational; decision makers would follow (for example, if a person likes tea better than milk, and milk better than coffee, then that person should like tea better than coffee). They then proved that for such rational decision makers it was possible to define a utility function that would refle

27、ct an individuals preferences; basically, a utility function assigns to each of a players alternatives a number that conveys the relative attractiveness of that alternative. Maximizing someones utility automatically determines his most preferred option. In recent years, however, some doubt has been

28、raised about whether people actually behave in accordance with these rational rules.Source: /search.britannica4/bcom/eb/article/5/0,5716,117275+6,00.htmlValues assigned to alternatives is based on the relative attractiveness to an individual.Yale M. BraunsteinKM Lecture 4 - Game Theorygame theory fo

29、cuses on how groups of people interact. Game theory focuses on how “players” in economic “games” behave when, to reach their goals, they have to predict how their opponents will react to their moves. CONCLUSION: As a conclusion Game theory is the study of competitive interaction; it analyzes possibl

30、e outcomes in situations where people are trying to score points off each other, whether in bridge, politics of war. You do this by trying to anticipate the reaction of your competitor to your next move and then factoring that reaction into your actual decision. It teaches people to think several mo

31、ves ahead. From now on , Whoever it was who said it doesnt matter if you win or lose but how you play the game, missed the point. It matters very much. According to game theory, its how you play the game that usually determines whether you win or lose. Source:/..tr/zyilmaz/proposal

32、.htmlYale M. BraunsteinKM Lecture 4 - Game TheoryIt is highly mathematical in order to emulated human value judgement (mental rules, fuzzy input of good or bad)ex. Chess playYale M. BraunsteinKM Lecture 4 - Game TheoryWHY GAME THEORY IS IMPORTANT? Game theory is both easy and excruciatingly difficul

33、t. People use it all the time, average people, in their daily lives. It comes into play in mundane deals likebuying a car, where a certain skill in haggling is required. The buyers offer is usually formulated on the basis of what he or she presumes the seller will take. The seller is guided by a pre

34、sumption about how high the buyer will go. The outcome of this negotiation could be totally positive (if the deal satisfies both parties), totally negative (if it falls through), or positive for one party and less so for the other (depending on how much is paid.) It is used to describe any relations

35、hip and interaction, economic, social or political. And its useful in creating strategies for negotiators. It can help you win, and that is why companies and governments hire game theorists to write strategies against other players in whatever game theyre in. Mathematics and statistics are the tools

36、 they use. For example, during the Cold War the Pentagon became interested in game theory to help develop its nuclear strategy, and with some success. You dont make a move in chess without first trying to figure out how your opponent will react to it. Game theory assumes that all-human interactions,

37、 personal, institutional, economic, can be understood and navigated by presumptions similar to those of the chess player. Source:/..tr/zyilmaz/proposal.htmlYale M. BraunsteinKM Lecture 4 - Game TheoryYale M. BraunsteinKM Lecture 4 - Game TheoryIn zero-sum games it never helps a pla

38、yer to give an adversary information, and it never harms a player to learn an opponents strategy in advance. These rules do not necessarily hold true for nonzero-sum games, however.Source: /search.britannica/bcom/eb/article/5/0,5716,117275+6,00.htmlYale M. BraunsteinKM Lecture 4 - Game TheoryNonzero

39、-sum game includes all games which are not constant-sum. In non-zero-sum game, the sum of the payoffs are not the same for all outcomes. Nonzero-sum games are mixed motive games. The interests of the players are neither strictly coincident nor strictly opposed. They generate intrapersonal and interp

40、ersonal conflicts. They are not always completely soluble but they provide insights into important areas of interdependent choice. In these games, one players losses do not always equal another players gains. Some nonzero-sum games are positive sum and some are negative sum: Negative sum games are c

41、ompetitive, but nobody really wins, rather, everybody loses. For example, a war or a strike. Positive sum games are cooperative, all players have one goal that they contribute together as in an educational game. For example, school newspapers or plays, building blocks, or a science exhibit.One major

42、 example of a two-person nonzero-sum game is the prisoners dilemma. It is a non cooperative game because the players can not communicate their intentions. (See topic Automata & Games Theory) Source: /artsci-ccwin.concordia.ca/edtech/ETEC606/conceptprinciples.htmlA player may want his opponent to

43、 be well-informed. In a labour-management dispute, for example, if the labour union is prepared for a strike, it behooves it to inform management and thereby possibly achieve its goal without a long, costly conflict. In this example, management is not harmed by the advance information (it, too, bene

44、fits by avoiding the costly strike), but in other nonzero-sum games a player can be at a disadvantage if he knows his opponents strategy. A blackmailer, for example, benefits only if he informs his victim that he will harm the victim unless his terms are met. If he does not give this information to

45、the intended victim, the blackmailer can still do damage but he has no reason to. Thus, knowledge of the blackmailers strategy works to the victims disadvantage.Source: /search.britannica/bcom/eb/article/5/0,5716,117275+6,00.htmlYale M. BraunsteinKM Lecture 4 - Game TheoryA class of Game in which pl

46、ayers move alternately and each player is completely informed of previous moves. Finite, Zero-Sum, two-player Games with perfect information (including checkers and chess) have a Saddle Point, and therefore one or more optimal strategies. However, the optimal strategy may be so difficult to compute

47、as to be effectively impossible to determine (as in the game of Chess). Source:/mathworld.wolfram/PerfectInformation.htmlYale M. BraunsteinKM Lecture 4 - Game TheoryYale M. BraunsteinKM Lecture 4 - Game TheoryYale M. BraunsteinKM Lecture 4 - Game TheoryIt might seem that the paradox inherent in the

48、prisoners dilemma could be resolved if the game were played repeatedly. Players would learn that they do best when both act unselfishly and cooperate; if one player failed to cooperate in one game, the other player could retaliate by not cooperating in the next game and both would lose until they be

49、gan to cooperate again. When the game is repeated a fixed number of times, however, this argument fails. According to the argument, when the two shopkeepers described above set up their stores at a 10-day county fair, each should maintain a high price, knowing that if he does not, his competitor wil

50、l retaliate the next day. On the 10th day, however, each shopkeeper realizes that his competitor can no longer retaliate (the fair will be closed so there is no next day); therefore each shopkeeper should lower his price on the last day. But if each shopkeeper knows that his rival will lower the pri

51、ce on the 10th day, he has no incentive to maintain the high price on the ninth day. Continuing this reasoning, one concludes that ;rational; shopkeepers will have a price war every day. It is only when the game is played repeatedly and neither player knows when the sequence will end that the cooperative strategy succeeds.Source:/search.britannica/bcom/eb/article/5/0,5716,117275+6,00.htmlLead to ESS.Yale M. BraunsteinKM Lecture 4 - Game Theory1. Each player need to figure out the other players future responses and