WIXLIB

NotesIntroduction to Game TheoryTyler MooreComputer Science & Engineering Department, SMU, Dallas, TXSlides are modified from version written by Benjamin Johnson, UC BerkeleyLecture 15–16Review: rational choice modelGame theoryNotesTopicsWe now discuss the final big idea in the course1Introduction2Security metrics and investment3Measuring cybercrime4Security gamesWe now consider strategic interaction between players2 / 40Review: rational choice modelGame theoryPreferences and outcomesUtilityExpected utility: modeling security threats as random actsRecall how we model rationalityNotesEconomics attempts to model the decisions we make, whenfaced with multiple choices and when interacting with otherstrategic agentsRational choice theory (RCT): model for decision-makingGame theory (GT): extends RCT to model strategicinteractions4 / 40Review: rational choice modelGame theoryPreferences and outcomesUtilityExpected utility: modeling security threats as random actsModel of preferencesAn agent is faced with a range of possible outcomeso1 , o2 O, the set of all possible outcomesNotationo1 o2 : the agent is strictly prefers o1 to o2 .o1 o2 : the agent weakly prefers o1 to o2 ;o1 o2 : the agent is indifferent between o1 and o2 ;Outcomes can be also viewed as tuples of different propertiesx̂, ŷ O, where x̂ (x1 , x2 , . . . , xn ) and ŷ (y1 , y2 , . . . , yn )5 / 40Notes

Preferences and outcomesUtilityExpected utility: modeling security threats as random actsReview: rational choice modelGame theoryRational choice axiomsNotesRational choice theory assumes consistency in how outcomes arepreferred.AxiomCompleteness. For each pair of outcomes o1 and o2 , exactly oneof the following holds: o1 o2 , o1 o2 , or o2 o1 . Outcomes can always be comparedAxiomTransitivity. For each triple of outcomes o1 , o2 , and o3 , if o1 o2and o2 o3 , then o1 o3 . People make choices among many different outcomes in aconsistent manner6 / 40Preferences and outcomesUtilityExpected utility: modeling security threats as random actsReview: rational choice modelGame theoryUtilityNotesRational choice theory defines utility as a way of quantifyingconsumer preferencesDefinition(Utility function) A utility function U maps a set of outcomes ontoreal-valued numbers, that is, U : O R. U is defined such thatU(o1 ) U(o2 ) o1 o2 .Agents make a rational decision by picking the outcome withhighest utility:o arg max U(o)o O(1)7 / 40Preferences and outcomesUtilityExpected utility: modeling security threats as random actsReview: rational choice modelGame theoryWhy isn’t utility theory enough?NotesOnly rarely do actions people take directly determine outcomesInstead there is uncertainty about which outcome will come topassMore realistic model: agent selects action a from set of allpossible actions A, and then outcomes O are associated withprobability distribution8 / 40Preferences and outcomesUtilityExpected utility: modeling security threats as random actsReview: rational choice modelGame theoryExpected utilityDefinition(Expected utility (discrete)) The expected utility of an actiona A is defined by adding up the utility for all outcomes weighedby their probability of occurrence:XE [U(a)] U(o) · P(o a)(2)o OAgents make a rational decision by maximizing expected utility:a arg max E [U(a)]a A(3)9 / 40Notes

Preferences and outcomesUtilityExpected utility: modeling security threats as random actsReview: rational choice modelGame theoryExample: process control system securityNotesSource: http://www.cl.cam.ac.uk/ fms27/papers/2011-Leverett-industrial.pdf10 / 40Preferences and outcomesUtilityExpected utility: modeling security threats as random actsReview: rational choice modelGame theoryExample: process control system securityNotesActions available: A {disconnect, connect}Outcomes available:O {successful attack, no successful attack}Probability of successful attack is 0.01(P(attack connect) 0.01)If systems are disconnected, then P(attack disconnect) 011 / 40Preferences and outcomesUtilityExpected utility: modeling security threats as random actsReview: rational choice modelGame theoryExample: process control system securitysuccessful attackP(attack action)ActionUconnectdisconnect-50-100.010Uno succ. attackP(no attack action)E [U(action)]10-100.9919.4-10Notes risk-neutral IT security manager chooses to connect sinceE [U(connect)] E [U(disconnect)].This model assumes fixed probabilities for attack. Is thisassumption realistic?12 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesGames vs. OptimizationOptimization: Player vs NatureGames: Player vs Player14 / 40

Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesStrategyBook of QiWarBusinessPolicy36 Stratagems (Examples)Befriend a distant state while attacking a neighborSacrifice the plum tree to preserve the peach treeFeign madness but keep your balanceSeehttp://en.wikipedia.org/wiki/Thirty-Six Stratagems15 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesRepresenting a game with a payoff matrixSuppose we have two players A and B.A’s actions AA {u, d}B’s actions AB {l, r }Possible outcomes O {(u, l), (u, r ), (d, l), (d, r )}We represent 2-player, 2-strategy games with a payoff matrixPlayer A chooses uPlayer A chooses dPlayer Bchooses lPlayer Bchooses r(UA (u, l), UB (u, l))(UA (d, l), UB (d, l))(UA (u, r ), UB (u, r ))(UA (d, r ), UB (d, r ))16 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesReturning to the process control system exampleSuppose we have two players: plant security manager and aterroristManager’s actions Amgr {disconnect, connect}Terrorist’s actions Aterr {attack, don’t attack}Possible outcomes O {(a1 , a3 ), (a1 , a4 ), (a2 , a3 ), (a2 , a4 )}We represent 2-player, 2-strategy games with a payoff �t attack( 50, 50)( 10, 10)(10, 0)( 10, 0)17 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesImportant NotionsZero-SumIn a zero-sum game, the sum of player utilities is zero.zero-sumheadstailsheadstails(1, 1)( 1, 1)( 1, 1)(1, 1)not zero-suminvest deferinvestdefer(1, 1)(2, 1)(1, 2)(0, 0)18 / 40

Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesHow can we determine which outcome will happen?We look for particular solution concepts12Dominant strategy equilibriumNash equilibriumPareto optimal outcomes19 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesDominant strategy equilibriumA player has a dominant strategy if that strategy achieves thehighest payoff regardless of what other players do.A dominant strategy equilibrium is one in which each playerhas and plays her dominant strategy.Example 1: Dominant Strategy Equilibria?leftAlicetopbottomBobright(1, 2)(2, 1)(0, 1)(1, 0)20 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesNash equilibriumNash equilibriumA Nash equilibrium is an assignment of strategies to players suchthat no player can improve her utility by changing strategies.A Nash equilibrium is called strong if every player strictlyprefers their strategy given the current configuration.It is called weak if at least one player is indifferent aboutchanging strategies.Nash equilibrium for 2-player gameFor a 2-person game between players A and B, a pair of strategies(ai , aj ) is a Nash equilibrium if UA (ai , aj ) UtilityA (ai 0 , aj ) forevery i 0 AA where i 0 6 i and UB (ai , aj ) UB (ai , aj 0 ) for everyj AB where j 0 6 j.21 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesFinding Nash equilibriaNash equilibrium for 2-player gameFor a 2-person game between players A and B, a pair of strategies(ai , aj ) is a Nash equilibrium if UA (ai , aj ) UA (ai 0 , aj ) for everyi 0 AA where i 0 6 i and UB (ai , aj ) UB (ai , aj 0 ) for every j ABwhere j 0 6 j.Example 1: Nash equilibria? (top,left) and (bottom, right)leftAlicetopbottomBobright(2, 1)(0, 0)(0, 0)(1, 2)(top,left)?:(top,right)?:UA (top, left) UA (bottom, left)?2 0 ? yes!UB (top, left) UB (top, right)?1 0 ? yes!UA (top, right) UA (bottom, right)?0 1 ? no!UB (top, right) UB (top, left)?0 1 ? no!22 / 40

Exercise: is there a dominant strategy or Nash equilibriumfor these games?topbottomleftright(1, 1)(2, 1)(1, 2)(0, 0)topbottomReview: rational choice modelGame theoryleftright(1, 1)( 1, 1)( 1, 1)(1, 1)NotesIntroduction and notationFinding equilibrium outcomesNotesPareto OptimalityDefinitionAn outcome of a game is Pareto optimal if no other outcomemakes at least one player strictly better off, while leaving everyplayer at least as well off.Example: Pareto-optimal outcome? everything exceptdefect/defectcooperatedefectcooperatedefect( 1, 1)(0, 5)( 5, 0)( 2, 2)24 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesPrisoners’ dilemmadenyconfessdenyconfess( 1, 1)(0, 5)( 5, 0)( 2, 2)25 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesThoughts on the Prisoners’ DilemmaCan you see why the equilibrium strategy is not always Paretoefficient?Exemplifies the difficulty of cooperation when players can’tcommit to a actions in advanceIn a repeated game, cooperation can emerge becauseanticipated future benefits shift rewardsBut we are studying one-shot games, where there is noanticipated future benefitHere’s one way to use psychology to commit to a nomics/comments/game-show-game-theory26 / 40

Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesSplit or StealNickIbrahimsplitstealsplitsteal(6 800, 6 800)(13 600, 0)(0, 13 600)(0, 0)27 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesPrisoners’ dilemma in infosec: sharing security datasharedon’t sharesharedon’t share( 1, 1)(0, 5)( 5, 0)( 2, 2)Note, this only applies when both parties are of the same type, and can benefit eachother from sharing. Doesn’t apply in the case of take-down companies due to theoutsourcing of security28 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesAssurance games: Cold war arms raceUSSRrefrain buildUSArefrainbuild(4,4)(3,1)(1,3)(2,2)Exercise: compute the equilibrium outcome (Nash or dominant strategy)29 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesAssurance games in infosec: Cyber arms raceRussiarefrain buildUSArefrainbuild(4,4)(3,1)(1,3)(2,2)30 / 40

Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesAssurance games in infosec: Upgrading protocolsMany security protocols (e.g., DNSSEC, BGPSEC) requirewidespread adoption to be usefulupgradedon’t upgradeupgradedon’t upgrade(4,4)(3,1)(1,3)(2,2)31 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesBattle of the sexespartyhomepartyhome(10, 5)(0, 0)(0, 0)(5, 10)32 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesStag-hunt games and infosec: joint cybercrime defenseStag huntstagharestaghare(10, 10)(7, 0)Coordinating malware responsejoin WG protect firm(0, 7)(7, 7)join WGprotect firm(10, 10)(7, 0)(0, 7)(7, 7)33 / 40Review: rational choice modelGame theoryIntroduction and notationFinding equilibrium outcomesNotesChickendarechickendarechicken(0, 0)(2, 7)(7, 2)(5, 5)34 / 40