Game TheoryOutlineAdminSlide 4Utility TheoryExpected UtilityHow to evaluateSlide 8ExampleRationalityZero-sumNon-zero sumDegenerate StrategyNash EquilibriumClassic ExamplesPrisoner's DilemmaRock-Paper-ScissorsNo dominant strategyMixed StrategyMixed Strategy 2Mixed Strategy 3DegeneraciesSlide 23Lie or Not LieExpectationNoteSlide 27BUTRepeated InteractionsDecision TreeFuture CostReducing degeneracyWednesdayGame TheoryRobin BurkeGAM 224Spring 2004OutlineAdminGame TheoryUtility theoryZero-sum and non-zero sum gamesDecision TreesDegenerate strategiesAdminDue WedHomework #3Due Next WeekRule AnalysisReaction papersGrades availableGame TheoryA branch of economicsStudies rational choice in a adversarial environmentAssumptionsrational actorscomplete knowledge•in its classic formulationknown probabilities of outcomesknown utility functionsUtility TheoryUtility theorya single scalevalue with each outcomeDifferent actorsmay have different utility valuationsbut all have the same scaleExpected UtilityExpected utilitywhat is the likely outcomeof a set of outcomeseach with different utility valuesExampleBet•$5 if a player rolls 7 or 11, lose $2 otherwiseAny takers?How to evaluateExpected Utilityfor each outcome•reward * probability(1/6) * 5 + (1/18) * 5 + (7/9) (-2) = -2/9MeaningIf you made this bet 1000 times, you would probably end up $222 poorer.Doesn't say anything about how a given trial will end upProbability says nothing about the single caseGame TheoryExamine strategies based on expected utilityThe ideaa rational player will choose the strategy with the best expected utilityExampleNon-probabilisticCake slicingTwo playerscutterchooser Cutter'sUtilityChoose bigger pieceChoose smaller pieceCut cake evenly½ - a bit ½ + a bitCut unevenlySmall piece Big pieceRationalityRationalityeach player will take highest utility optiontaking into account the other player's likely behaviorIn exampleif cutter cuts unevenly•he might like to end up in the lower right•but the other player would never do that•-10if the current cuts evenly,•he will end up in the upper left•-1•this is a stable outcome•neither player has an incentive to deviate Cutter'sUtilityChoose bigger pieceChoose smaller pieceCut cake evenly(-1, +1) (+1, -1)Cut unevenly(-10, +10) (+10, -10)Zero-sumNotefor every outcome•the total utility for all players is zeroZero-sum gamesomething gained by one player is lost by anotherzero-sum games are guaranteed to have a winning strategy• a correct way to play the gameMakes the game not very interesting to playto study, maybeNon-zero sumA game in which there are non-symmetric outcomesbetter or worse for both playersClassic examplePrisoner's DilemmaHold Out ConfessHold Out [-1, -1] [-3, 0]Confess [0, -3] [-5, -5]Degenerate StrategyA winning strategy is also calleda degenerate strategyBecauseit means the player doesn't have to thinkthere is a "right" way to playProblemgame stops presenting a challengeplayers will find degenerate strategies if they existNash EquilibriumSometimes there is a "best" solutionEven when there is no dominant oneA Nash equilibrium is a strategyin which no player has an incentive to deviatebecause to do so gives the other an advantageCreatorJohn Nash Jr"A Beautiful Mind"Nobel Prize 1994Classic ExamplesCar DealersWhy are they always next to each other?Why aren't they spaced equally around town?•Optimal in the sense of not drawing customers to the competitionEquilibriumbecause to move away from the competitoris to cede some customers to itPrisoner's DilemmaNash EquilibriumConfessBecausein each situation, the prisoner can improve his outcome by confessingSolutioniterationcommunicationcommitmentRock-Paper-ScissorsPlayer 2Rock Paper ScissorsPlayer 1 Rock [0,0] [-1, +1] [+1, -1]Paper [+1, -1] [0,0] [-1, +1]Scissors [-1, +1] [+1, -1] [0,0]No dominant strategyMeaningthere is no single preferred option•for either playerBest strategy(single iteration)choose randomly"mixed strategy"Mixed StrategyImportant goal in game designPlayer should feelall of the options are worth usingnone are dominated by any othersRock-Paper-Scissors dynamicis often used to achieve thisExampleWarcraft II•Archers > Knights•Knights > Footmen•Footmen > Archers•must have a mixed armyMixed Strategy 2Other ways to achieve mixed strategyIgnoranceIf the player can't determine the dominance of a strategy•a mixed approach will be used•(but players will figure it out!)CostDominance is reduced•if the cost to exercise the option is increased•or cost to acquire itRarityMixture is required•if the dominant strategy can only be used periodically or occasionallyPayoff/Probability EnvironmentMixture is required•if the probabilities or payoffs change throughout the gameMixed Strategy 3In a competitive settingmixed strategy may be called foreven when there is a dominant strategyExampleFootballthird down / short yardagehighest utility option•running play•best chance of success•lowest cost of failureButif your opponent assumes this•defenses adjustincreasing the payoff of a long passDegeneraciesAre not always obviousMay be contingent on game stateExampleLiar's Diceroll the dice in a cupstate the "poker hand" you have rolledstated hand must be higher than the opponent's previous rollopponent can either•accept the roll, and take his turn, or•say "Liar", and look at the diceif the description is correct•opponent pays $1if the description is a lie•player pays $1Lie or Not LieMake outcome chartfor next playerassume the roll is not good enoughRollerlie or not lieNext playeraccept or doubtExpectationKnowledgethe opponent knows more than just thisthe opponent knows the previous roll that the player must beat•probability of lyingNoteThe opponent will never lie about a better rollOutcome cannot be improved by doing soThe opponent cannot tell the truth about a worse rollIllegal under the rulesExpected UtilityWhat is the expected utility of the doubting strategy?P(worse) - P(better) When P(worse) is greater than