Game-theoretic analysis toolsTerminologyGame representationsDominant strategy “equilibrium”Nash equilibrium [Nash50]Criticisms of Nash equilibriumExistence of (pure strategy) Nash equilibriaRock-scissors-paper gameSlide 9Mixed strategy Nash equilibriumExistence & complexity of mixed strategy Nash equilibriaUltimatum gameSubgame perfect equilibrium & credible threatsUltimatum game, againThoughts on credible threatsConclusions on game-theoretic analysis toolsGame-theoretic analysis toolsTuomas SandholmProfessorComputer Science Department Carnegie Mellon UniversityTerminology•In a 1-agent setting, agent’s expected utility maximizing strategy is well-defined•But in a multiagent system, the outcome may depend on others’ strategies also•Game theory analyzes stable points in the space of strategy profiles => allows one to build robust, nonmanipulable multiagent systems•Agent = player•Action = move = choice that agent can make at a point in the game•Strategy si = mapping from history (to the extent that the agent i can distinguish) to actions•Strategy set Si = strategies available to the agent•Strategy profile (s1, s2, ..., s|A|) = one strategy for each agent•Agent’s utility is determined after each agent (including nature that is used to model uncertainty) has chosen its strategy, and game has been played: ui = ui(s1, s2, ..., s|A|)Game representationsExtensive formplayer 11, 23, 4player 2UpDownLeftRight5, 67, 8player 2LeftRightMatrix form (aka normal formaka strategic form)player 1’sstrategyplayer 2’s strategy1, 2UpDownLeft,LeftLeft,Right3, 45, 6 7, 8Right,LeftRight,Right3, 41, 25, 6 7, 8Potential combinatorial explosionDominant strategy “equilibrium”•Best response si*: for all si’, ui(si*,s-i) ≥ ui(si’,s-i)•Dominant strategy si*: si* is a best response for all s-i–Does not always exist–Inferior strategies are called dominated•Dominant strategy equilibrium is a strategy profile where each agent has picked its dominant strategy–Does not always exist–Requires no counterspeculationcooperatecooperatedefectdefect3, 3 0, 55, 01, 1Pareto optimal? Social welfare maximizing?Prisoners’ DilemmaNash equilibrium [Nash50]•Sometimes an agent’s best response depends on others’ strategies: a dominant strategy does not exist•A strategy profile is a Nash equilibrium if no player has incentive to deviate from his strategy given that others do not deviate: for every agent i, ui(si*,s-i) ≥ ui(si’,s-i) for all si’–Dominant strategy equilibria are Nash equilibria but not vice versa–Defect-defect is the only Nash eq. in Prisoner’s Dilemma–Battle of the Sexes (has no dominant strategy equilibria):ballet0, 0boxingboxingballet0, 02, 1WomanMan1, 2Criticisms of Nash equilibrium•Not unique in all games, e.g. Battle of the Sexes–Approaches for addressing this problem•Refinements (= strengthenings) of the equilibrium concept–Eliminate weakly dominated strategies first–Choose the Nash equilibrium with highest welfare–Subgame perfection–…•Focal points•Mediation•Communication•Convention•Learning•Does not exist in all games1, 00, 11, 00, 1Existence of (pure strategy) Nash equilibria•Thrm. –Any finite game, –where each action node is alone in its information set •(i.e. at every point in the game, the agent whose turn it is to move knows what moves have been played so far) –is dominance solvable by backward induction (at least as long as ties are ruled out)•Constructive proof: Multi-player minimax searchRock-scissors-paper gameSequential movesRock-scissors-paper gameSimultan eous movesMixed strategy Nash equilibriummove of agent 1move of agent 2rockrockrockrockscissorsscissorsscissorsscissorspaperpaperpaperpaper0, 00, 00, 01, -11, -11, -1-1, 1-1, 1-1, 1Symmetric mixed strategy Nash eq: Each player plays each pure strategy with probability 1/3Mixed strategy = agent’s chosen probability distribution over pure strategies from its strategy setEach agent has a best response strategy and beliefs(consistent with each other)In mixed strategy equilibrium, each strategy that occurs in the mix of agent i has equal expected utility to iInformation set(the mover does not know which node of the set she is in)Existence & complexity of mixed strategy Nash equilibria•Every finite player, finite strategy game has at least one Nash equilibrium if we admit mixed strategy equilibria as well as pure [Nash 50]–(Proof is based on Kakutani’s fix point theorem)•May be hard to compute–Even in 2-agent matrix games•Finding one is PPAD-complete (even with 0/1 payoffs) [Cheng&Deng FOCS-06; Abbott, Kane & Valiant FOCS-05]•Finding an approximately good one is NP-hard [Conitzer&Sandholm]Ultimatum game (for distributional bargaining)Subgame perfect equilibrium & credible threats•Proper subgame = subtree (of the game tree) whose root is alone in its information set•Subgame perfect equilibrium = strategy profile that is in Nash equilibrium in every proper subgame (including the root), whether or not that subgame is reached along the equilibrium path of play•E.g. Cuban missile crisis•Pure strategy Nash equilibria: (Arm,Fold), (Retract,Nuke)•Pure strategy subgame perfect equilibria: (Arm,Fold)•Conclusion: Kennedy’s Nuke threat was not credib leKhrushchevKennedyArmRetractFoldNuke-1, 1- 100, - 10010, -10Ultimatum game, againThoughts on credible threats•Could use software as a commitment device–If one can credibly convince others that one cannot change one’s software agent, then revealing the agent’s code acts as a credible commitment to one’s strategy–E.g. nuke in the missile crisis–E.g. accept no less than 60% as the second mover in the ultimatum game•Restricting one’s strategy set can increase one’s utility–This cannot occur in single agent settings•Social welfare can increase or decreaseConclusions on game-theoretic analysis tools•Tools for building robust, nonmanipulable systems for self-interested agents•Different solution concepts–For existence, use strongest equilibrium concept–For uniqueness, use weakest equilibrium conceptNash eq Dominant strategy eqStrengthStrength against collusionSubgame perfect eq Perfect Bayesian eqBayes-Nash eqSequential eqStrong Nash eqCoalition-Proof Nash eqEx post equilibrium Nash equilibrium for all
View Full Document