Game representations, game-theoretic solution concepts, and complexity Tuomas Sandholm Computer Science Department Carnegie Mellon University The heart of the problem In a 1-agent setting, agents expected utility maximizing strategy is well-defined But in a multiagent system, the outcome may depend on others strategies also Terminology 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 Agents 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 representations Matrix form (aka normal form aka strategic form) Extensive form player 2s strategy Up 1, 2 Right

3, 4 Left 5, 6 Right 7, 8 Left, Left player 2 player 1 Down Left Up

player 1s strategy Down Left, Right, Right, Right Left Right 1, 2 1, 2 3, 4 3, 4 5, 6 7, 8 5, 6

7, 8 player 2 Potential combinatorial explosion Dominant 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 counterspeculation cooperate defect Pareto optimal? cooperate

defect 3, 3 5, 0 0, 5 1, 1 Social welfare maximizing? Nash equilibrium [Nash50] Sometimes an agents 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 Prisoners Dilemma Battle of the Sexes game Has no dominant strategy equilibria

boxing boxing Man ballet Woman ballet 2, 1 0, 0 0, 0 1, 2 Criticisms 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 1, 0 0, 1 Learning Does not exist in all games 0, 1 1, 0

Existence 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 search Rock-scissors-paper game Sequential moves Rock-scissors-paper game Simultaneous moves Mixed strategy Nash equilibrium Mixed strategy = agents chosen probability distribution over pure strategies from its strategy set

move of agent 2 rock scissors paper rock scissors paper 1, -1 -1, 1 rock move of agent 1 0, 0

scissors paper -1, 1 0, 0 1, -1 rock Information set (the mover does not know which node of the set she is in) scissors paper 1, -1 -1, 1 0, 0

Each agent has a best response strategy and beliefs (consistent with each other) Symmetric mixed strategy Nash eq: Each player plays each pure strategy with probability 1/3 In mixed strategy equilibrium, each strategy that occurs in the mix of agent i has equal expected utility to i 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 Kakutanis fix point theorem) May be hard to compute Complexity of finding a Nash equilibrium in a normal form game: 2-player 0-sum games can be solved in polytime with LP 2-player games are PPAD-complete (even with 0/1 payoffs) [Chen, Deng & Teng JACM-09; Abbott, Kane & Valiant FOCS-05; Daskalakis, Goldberg & Papadimitriou STOC-06], NP-complete to find an even approximately good Nash equilibrium [Conitzer & Sandholm GEB-08] 3-player games are FIXP-complete [Etessami & Yannakakis FOCS-07] Ultimatum game (for distributional bargaining) Subgame perfect equilibrium [Selten 72] & 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 Nuke Arm Kennedy Fold Pure strategy Nash equilibria: (Arm,Fold), (Retract,Nuke) Pure strategyKhrushchev subgame perfect equilibria: (Arm,Fold) Conclusion: Kennedys Nuke threat was not credible Retract - 100, - 100 -1, 1 10, -10

Ultimatum game, again Thoughts on credible threats Could use software as a commitment device If one can credibly convince others that one cannot change ones software agent, then revealing the agents code acts as a credible commitment to ones strategy E.g. nuke in the missile crisis E.g. accept no less than 60% as the second mover in the ultimatum game Restricting ones strategy set can increase ones utility This cannot occur in single-agent settings Social welfare can increase or decrease Solution concepts Strength against collusion

Strong Nash eq Coalition-Proof Nash eq Nash eq Subgame perfect Perfect Bayesian Bayes-Nash eq equilibrium equilibrium Sequential equilibrium Dominant strategy eq Strength Ex post equilibrium = Nash equilibrium for all priors There are other equilibrium refinements too (see, e.g., following slides & wikipedia) Example from the Brains vs AI HeadsUp No-Limit Texas Holdem poker

competition that I organized in April and May 2015 Claudico made a bad move (not in the beginning of a hand) How can that mistake be part of a GTO strategy? Solution concepts for Bayesian games A (Bayesian) Nash equilibrium is a strategy profile and beliefs specified for each player about the types of the other players that maximizes the expected utility for each player given their beliefs about the other players' types and given the strategies played by the other players Perfect Bayesian equilibrium (PBE) More refined

Players place beliefs on nodes occurring in their information sets A belief system is consistent for a given strategy profile if the probability assigned by the system to every node is computed as the probability of that node being reached given the strategy profile, i.e., by Bayes rule A strategy profile is sequentially rational at a particular information set for a particular belief system if the expected utility of the player whose information set it is is maximal given the strategies played by the other players A PBE is a strategy profile and a belief system such that the strategies are sequentially rational given the belief system and the belief system is consistent, wherever possible, given the strategy profile A strategy profile is sequentially rational for a particular belief system if it satisfies the above for every information set

'wherever possible' clause is necessary: some information sets might be reached with zero probability given the strategy profile; hence Bayes' rule cannot be employed to calculate the probability of nodes in those sets. Such information sets are said to be off the equilibrium path and any beliefs can be assigned to them Sequential equilibrium [Kreps and Wilson 82]. Refinement of PBE that specifies constraints on beliefs in such zero-probability information sets. Strategies and beliefs must be a limit point of a sequence of totally mixed strategy profiles and associated sensible (in PBE sense) beliefs Extensive-form trembling hand perfect equilibrium [Selten 75]. Require every move at every information set to be taken with non-zero probability. Take limit as tremble probability 0 Extensive-form proper equilibrium [Myerson 78]. Idea: Costly trembles much less likely. At any information set, for any two actions A and B, if the movers utility from B is less than from A, then prob(B) prob(A). Take limit as 0 More detail about sequential equilibrium (slide content from Yiling Chens course) Solution concepts for Bayesian games Extensive-form perfect / proper equilibrium can involve playing

weakly dominated strategies => argument for other solution concepts: Normal-form perfect equilibrium More refined Normal- and extensive-form perfect equilibria are incomparable A normal-form perfect equilibrium of an extensive-form game may or may not be sequential (and might not even be subgame perfect) Quasi-perfect equilibrium [van Damme 84] Informally, a player takes observed as well as potential future mistakes of his opponents into account but assumes that he himself will not make a mistake in the future, even if he observes that he has done so in the past Incomparable to extensive-form perfect / proper Normal-form proper equilibrium Always sequential

For 0-sum games, provides a strategy that maximizes the conditional utility (among minmax strategies), conditioned on the opponent making a mistake. (Here a mistake is defined as a pure strategy that doesnt achieve the value of the game against all minmax strategies.)