Introduction to Game TheoryGeneral approachBrief History of Game TheoryRationalityUtility TheoryWhat is Game Theory?Game TheoryWhy is game theory important?Types of GamesZero-Sum GamesNon-zero Sum GameGames of Perfect InformationImperfect InformationKey Area of InterestMatrix NotationSlide 16Slide 17Games of ConflictGames of Co-operationPrisoner’s Dilemma with IterationBasic StrategiesPlan ahead and look backIf you have a dominating strategy, use itEliminate any dominated strategyLook for any equilibriumMaximin & Minimax EquilibriumMaximin & Minimax Equilibrium StrategiesDefinition: Nash EquilibriumIs this a Nash Equilibrium?Slide 30Slide 31Time for "real-life" decision makingMixed StrategyMixed Strategy SolutionThe Payoff Matrix for Holmes & MoriarityWhere is game theory currently used?Limitations & ProblemsSummarySourcesIntroduction to Game TheoryYale BraunsteinSpring 2007General approachBrief History of Game Theory Payoff MatrixTypes of Games Basic StrategiesEvolutionary ConceptsLimitations and ProblemsBrief History of Game Theory1913 - E. Zermelo provides the first theorem of game theory; 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 seek 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 person's preferences with 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 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 formulate an acceptable alternative with respect to circumstance.Useful in modeling strategic decision-makingGames against opponentsGames against "nature„Provides structured insight into the value of informationTypes of GamesSequential vs. Simultaneous movesSingle Play vs. Iterated Zero vs. non-zero sum Perfect vs. Imperfect information Cooperative vs. conflictZero-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 player.Games of Perfect InformationThe information concerning an opponent’s 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 player’s decision.Imperfect information may be diminished over time if the same game with the same opponent is to be repeated.Key Area of InterestchancestrategyMatrix Notation (Column) Player II Strategy A Strategy B (Row) Player I Strategy A (P1, P2) (P1, P2) Strategy B (P1, P2) (P1, P2) Notes: Player I's strategy A may be different from Player II's.P2 can be omitted if zero-sum gamePrisoner’s Dilemma & Other famous gamesA sample of other games:MarriageDisarmament (my generals are more irrational than yours)Prisoner’s DilemmaNotes: Higher payoffs (longer sentences) are bad.Non-cooperative equilibrium Joint maximumInstitutionalized “solutions” (a la criminal organizations, KSM)NCEJt. max.Games of ConflictTwo sides competing against each otherUsually caused by complete lack of information about the opponent or the gameCharacteristic of zero-sum gamesGames of Co-operationPlayers may improve payoff throughcommunicatingforming binding coalitions & agreements do not apply to zero-sum games Prisoner’s Dilemma with CooperationPrisoner’s Dilemma with IterationInfinite number of iterationsFear of retaliationFixed number of iterationDomino 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 strategyEliminate strategy 2 as it’s 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 & Minimax 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 Equilibrium. “Source: http://www.lebow.drexel.edu/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 you do…If 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 SolutionValue in SafeProbability of being GuardedExpected LossSafe 1 10,000$ 1 / 11 9,091$ Safe 2 100,000$ 10 / 11 9,091$ Both 110,000$The Payoff Matrix for Holmes & MoriarityPlayer #1Player #2Strategy #1Strategy #2Strategy #1Strategy #2Payoff (1,1)Payoff (1,2)Payoff (2,1) Payoff (2,2)Where is game theory currently used? –Ecology–Networks–EconomicsLimitations & ProblemsAssumes players always maximize their outcomesSome
View Full Document