1Lecture 1Introduction to Game Theory,Extensive &Normal Form,Mixed Strategies and Beliefs 22Readings•Watson: Strategy_ An introduction to game theory–Ch 1‐5:1rd ed p.1-40; 3rd ed p.1‐46.•Introduction;The Extensive Form;Strategies &the Normal Form;Beliefs,Mixed Strategies and Expecte d Payoffs;General Assumptions and Methodology.•Appendix A:Review of Mathematics p.409‐420.32Outline•Introduction.•Extensive form representation.•Strategies.•Examples.•Normal form representation.•Mixed strategies.•Beliefs.•Expected payoffs.•General assumptions.42Game Theory•Mathematical models of strategic situations :–Each agent’s behavior affects the well-being of other agents.•Perfect competition and monopoly are not strategic situations.–In perfect competition no agent considers the specific action of any other individual agent.–In monopoly the monopolist doesn’t worry about specific consumer’s actions.(Chooses price/quantity based on overall demand.)•Duopoly (2firms producing)is strategic.–Each firm considers the other’s action when deciding on its own.5Ch2:The Extensive Form162Example 1•A family is on vacation is San Diego.Their young children decide whether to behave or misbehave duri ng breakfast.•After breakfast the parents decide whether the family goes to Legoland(乐高) or sits quietly in their hotel room for the rest of the day.•This is a strategic situation.–Each party considers what the other is likely to do (or has already done)when making their own decision.72Formal Definition of a Game •A game is (formally):–A list of players ;–Specification of all possible actions each player can take and when;–The players’knowledge •(what each player knows when he acts);–How actions lead to outcomes ;–A specification of preferences over outcomes.•A game can be non-cooperative or cooperative .–Non-cooperative:All decisions are made individually82Example 1•Players:–The children and their parents.•Actions:–Children –{Behave,Misbehave}–Parents –{Legoland after the kids behave, Hotel after the kids behave, Legoland after the kids misbehave, Hotel after the kids misbehave}•Knowledge:–We typically assume the players know the game and that each player is rational.–Children –Don’t know anything else.–Parents –Knows whether the children have behaved or misbehaved.•Outcomes &Preferences:–We still need to specify these.We’ll do so later.92Extensive Form Representation •One way to represent games is with the extensive form.–Nodes:Where players choose actions (or the game ends).–Branches:Specific actions.–Labels: •Player making a decision (for decision nodes);•or actions (for branches).–Payoffs:Represent preferences over outcomes.–Information sets:Reveal what a player knows when he or she makes a decision.10Example1:Extensive Form2,,112Information Sets•An information set of player i is a collection of player i ’s nodes among which i cannot distinguish.–Perfect information : all information sets in the tree have just one node.–Imperfect information : not perfect information.122Example 1:Information Sets •The children have one information set.–The initial node.•Their parents have two information sets.–When the parents make their decision they knows if the children behaved or misbehaved.•This is why their actions are labeled differently.•For this example each information set is a single node.•Each decision is associated with a single information set.132Example 1(b)•The children decide to behave or misbehave.•Their parents decide whether to take the family to Legoland or sit quietly in their hotel room.–But they don’t observe whether the children behaved or misbehaved.•This time the parents only have one information set.–Their decision cannot be contingent on anything.14Example1(b):Extensive Form2152Example 1(b):Information Sets •The children have one information set.–The initial node.•The parents also have one information set.–When the parents make their decision they don’t know if the children behaved or misbehaved.•They don’t know which node they’re at when they makes their decision.•This is why their actions are labeled the same at both nodes.•Each decision is still associated with a single information set.162Strategies•Strategy:A complete contingent plan for a player in a game.–Prescribes an action for each of this player’ information sets.•Example 1–strategy example:–Children:Behave.–Parents:Sit quietly in the hotel room if the children behave,and go to Legoland if the children misbehave.•Example 1(b)–strategy example:–Children: Behave–Parents: ?17Notation2182Example 1•S Children ={Behave,Misbehave},or for short {B ,M }•S Parents ={Legoland if behave and Legoland if misbehave,Legoland if behave and Hotel if misbehave,Hotel if behave and Legoland if misbehave,Hotel if behave and Hotel if misbeha ve}–We can simplify this notation to {LL ’, LH’, HL ’, HH ’}•One specific s is (B , LL ’)192Example 1(b)•S Children ={Behave,Misbehave}•S Parents ={Legoland,Hotel}•One specific s is (Behave,Legoland)202Example 2•A pedestrian and a car are approaching a crosswalk.–First the pedestrian decides to cross or wait.–The driver observes the decision and then decides to proceed through the crosswalk or delay.•Warning :This is a simplified example.When we eventually solve this problem do not use the results to determine how to proceed through crosswalks.21Example2:Extensive FormPedestrianDriverCrossWaitProceedProceed’DelayDelay’‐100, ‐7510, 55, 100, 0222Example 2:Strategy Sets •S Ped ={C ,W }•S Driver ={PP ’,PD ’,DP ’,DD ’}–Each specific strategy for the driver tells either to proceed or delay if the pedestrian crosses and either to proceed’ or delay’ if the pedestrian waits.232•It’s possible people can make a decision from a continuous action space.–Ie.,S1=[0,100]2's strategy needs to cover every contingency.ie., Yes for a ≥ 72.3 and no for a <72.30,012a Yes100–a,aNo242•We also can have information sets and incomplete information.–Ie.,S1=[0,100]0,012a Yes100–a,aNo2's strategy can be a single action.ie.,Yes.25The ultimatum game (最后通谍博弈)•Players：the two players；•Timing：player 1 proposes a division (x1,x2) of a pie, where x1+x2=1. If 2 accepts this division, she receives x2and player 1 receives x1; if she rejects it, neither player receives any pie.•Preferences：Each person’s preferences are represented by payoffs equal to the division of pie she receives.26Figure: The ultimatum game x 12,x x 120,0Y N 272Example 3•Centipede game:–Order of events is as follows:•Player 1can continue or quit.–If she quits she gets $1and player 2gets $0.•If she continues player 2can stay or go.–If he goes player 1gets $0and he gets $2.•If he stays player 1can agree or disagree –If she disagrees she gets $2and player 2gets $1.–If she agrees she gets $1and player 2gets $3–Graph this game in extensive form;describe each player’s information set and strategy set282Centipede Game Player 1has two information sets:The initial node,The node contingent on C ,S .Player 2has one information set:The node contingent on C .Strategies:S 1={CA ,CD ,QA ,QD }S 2={S ,G }112CQ G S D A 1, 00, 22,11, 329Ch3:Strategies and the Normal Form2302Normal Form Representation •Note that any specific strategy profile will result in a unique outcome.ie.,(CA,G)•(Sometimes)we can use this idea to express much of the essential information for the game in a more compact, matrix form called the normal form.312NormalForm32Back to Example2•A pedestrian and a car are approaching a crosswalk.–First the pedestrian decides to cross or wait.–The driver observes the decision and then decides toproceed through the crosswalk or delay.233Example2:Extensive Form234Example2:Normal Form2352Normal Form•For games with two players and a finite number of strategies,the normal form can be written as a table with appropriate labels.–Given any strategy profile the normal form tells us what the outcome is.u i :S –But we can’t determine the order of the decisions.–It’s possible to have games with different extensive forms that have identical normal forms.36237382Normal Form•There is some debate about whether the normal form contains all the relevant information about the game.•The normal form always contains all the relevant information when the players move simultaneously and independently.–Neither observes any actions chosen by the other player before making own decision.–There are several classic normal form games that fit this description.39Classic Normal Form Games240Classic Normal Form Games241Ch4:Beliefs,Mixed Strategies and Expected Payoffs2422•In strategic situations beliefs are important.•When one player chooses a strategy she will consider what strategies the other player is likely to choose.•Mathematically, a belief of player i is aprobability distribution over the strategies of the other players.432•Formally ΔS i is the set of probability distributions over S i .•In a two-player game, the belief of player i about the behavior of player j is a function θj ϵΔS j such that, for each strategy s j ϵS j of player j , θj (s j ) is interpreted as the probability that player i thinks player j will play s j .•θj has the property that θj (s j ) ≥ 0 for each s j ϵS j , and ()1j jj j s S s θ∈=∑442A specific belief of player 1 about player 2 is denoted by θ2ϵΔS2. ie.,θ2= (2/5, 3/5) over (St2, R2).452Players may choose their strategies by randomizing.ie., Player 1 may play St 1with probability ⅓ and R 1with ⅔.Formally ΔS i is the set of probability distributions over S i .A specific mixed strategy for player i is denoted by σi ϵΔS i .ie., ΔS 1= (p , 1-p ) where 0≤p ≤1, σ1= (⅓, ⅔).462•The strategies we looked at earlier are called pure strategies .–A player chooses one specific strategy with certainty.•A mixed strategy assigns probabilities on a player’s pu re strategies.–Technically a pure strategy is a mixed strategy with a probability of 1 on that pure strategy and a probability of 0 on all other pure strategies.•Beliefs look a lot like mixed strategies (for the other player)because both of them are chosen from the set of probability distributions over that player’s strategies.47Expected Payoffs•If a player uses a mixed strategy and/ or assigns positive probability to multiple strategies of the other player, the this player cannot expect to get a particular payoff for sure.2•We can extend the definition of a payoff function to mixed strategies and beliefs by using the concept of expected value.482When i uses mixed strategy, σi and the others play (pure) s -i When i uses pure strategy,s i and has a belief θ-i about the strategies of the others,When i uses mixed strategy, σi , and has a belief θ-i about the strategies of the others,()()(),,i ii i i i i i i i s S u s s u s s σσ--∈=∑()()(),,i i i i i i i i i is S u s s u s s θθ-----∈=∑()()()(),,,i i i i i i i i i i i i i i s S s S u s s u s s σθσθ-----∈∈=∑49250。
