This Segment: Computational game theory Lecture 1: Game

This Segment: Computational game theory Lecture 1: Game

This Segment: Computational game theory Lecture 1: Game representations, 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 of the equilibrium concept 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

May be hard to compute 0, 1 1, 0 Existence of (pure strategy) Nash equilibria IF a game is finite and at every point in the game, the agent whose turn it is to move knows what moves have been played so far THEN the game has a (pure strategy) Nash equilibrium (solvable by minimax search at least as long as ties are ruled out) 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 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)

Subgame perfect equilibrium & credible threats [Selten 72] 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 Different solution concepts Strength against collusion Strong Nash eq Coalition-Proof Nash eq Nash eq Bayes-Nash eq Subgame perfect eq Perfect Bayesian eq Sequential eq Dominant strategy eq

Strength There are other equilibrium refinements too (see, e.g., wikipedia). Definition of a Bayesian game N is the set of players. is the set of the states of nature. For instance, in a card game, it can be any order of the cards. Ai is the set of actions for player i. A = A1 A2 An Ti is the type set of player i. For each state of nature, the game will have different types of players (one type per player). For instance, in a car selling game, it will be how much the player values the car Ci Ai Ti defines the available actions for player i of some type in Ti.

u: A R is the payoff function for player i. pi is the probability distribution over for each player i, that is to say, each player has different views of the probability distribution over the states of the nature. In the game, they never know the exact state of the nature. 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) 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 strategy profile is sequentially rational for a particular belief system if it satisfies the above for every information set. 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. '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 is a refinement of PBE that specifies constraints on the beliefs in such zeroprobability information sets. Strategies and beliefs should be a limit point of a sequence of totally mixed strategy profiles and associated sensible (in PBE sense) beliefs.

Recently Viewed Presentations

  • Medical Gas Administration 1 Oxygen Therapy  Medical gases

    Medical Gas Administration 1 Oxygen Therapy Medical gases

    Fire triangle. O 2, heat, and fuelIncrease risk of fire . High concentration of O. 2 High pressures of O. 2 Reduce O 2. buildup in enclosed environmentsUnder drapes. Operating rooms, etc. Be cautious when using electronic equipment. Scalpels, cardioversion,...
  • Title of Presentation Myriad Pro, Bold, Shadow, 28pt

    Title of Presentation Myriad Pro, Bold, Shadow, 28pt

    1980, it may have been built with materials that contain asbestos, mercury, or lead. Asbestos could be found in insulation, wiring, and roof or siding shingles. Mercury is frequently found in old thermostats and old light switches. Lead is sometimes...
  • Multiplication


    Multiplication LI: To be able to write number sentences to describe an array Multiplication I have 12 counters. How could I arrange them into equal rows? What number sentences could you write to go with this array? 2 x 6...
  • Ecology 1: Ecosystems

    Ecology 1: Ecosystems

    Ecology is the scientific study of interactions among organisms and between the organisms and their environments. ... Using the Pictures given to you label the water cycle and carbon cycle on separate papers with all processes labeled and arrows showing...
  • Sample heading text

    Sample heading text

    AUQA Performance Portfolio Chapter 3 International Activities
  • Basic Observation Buoys Introduction to Hard Substrate Epifaunal

    Basic Observation Buoys Introduction to Hard Substrate Epifaunal

    Lecithotrophic - they obtain energy from internal sources. Examples: colonial tunicates (Botrylloides, Botryllus). Larvae that . do. feed in the water column are. Planktotrophic. Examples: solitary tunicates, some bryozoans. Benthic Invertebrate Life Cycle. Text-heavy slide. Blue bottom image and GSO...
  • Factors, Multiples, Primes: - Variation Theory

    Factors, Multiples, Primes: - Variation Theory

    10 product of prime factors = 20 product of prime factors = 60 product of prime factors = 30 product of prime factors = 6 product of prime factors = 36 product of prime factors = 9 product of prime...
  • Symbolism in chapter 2 - Ms. Do's Classroom

    Symbolism in chapter 2 - Ms. Do's Classroom

    The eyes of tjeckleburg. A billboard with the eyes of Dr. T. J. Eckleburg is also an important symbol in this chapter. Reread p. 23. Describe the billboard. Then, respond in a short analytical paragraph (you only need one piece...