Problem 3. (Capture the flag) There are two players and 21 flags, of which 20 are...

Transcribed Image Text:

Problem 3. (Capture the flag) There are two players and 21 flags, of which 20 are orange and one is blue. The winner of the game is the player that captures the blue flag. At each step, a player can take 1, 2, or 3 flags. They must take orange flags first; i.e., the blue flag must be the last flag to be taken. The winner is the last player to move, i.e., the player who captures the blue flag (regardless of how many other orange flags they take on the last turn). Suppose that player 1 moves first, and subsequently players alternate turns until the game ends. Use backward induction to find an SPNE: Give equilibrium strategies, the equilibrium path of play, and the outcome. (Remember that strategies must be complete contingent plans: they must say what each player would do after any history of the game.) (NOTE: We've asked you to solve this problem mainly to get practice translating the solution we derived in class into the formalism of SPNE. For an added challenge (not to turn in), generalize your solution to the case where there are n flags, and on each turn a player must take a number of flags between 1 and k, where k is a positive integer less than n.) Problem 3. (Capture the flag) There are two players and 21 flags, of which 20 are orange and one is blue. The winner of the game is the player that captures the blue flag. At each step, a player can take 1, 2, or 3 flags. They must take orange flags first; i.e., the blue flag must be the last flag to be taken. The winner is the last player to move, i.e., the player who captures the blue flag (regardless of how many other orange flags they take on the last turn). Suppose that player 1 moves first, and subsequently players alternate turns until the game ends. Use backward induction to find an SPNE: Give equilibrium strategies, the equilibrium path of play, and the outcome. (Remember that strategies must be complete contingent plans: they must say what each player would do after any history of the game.) (NOTE: We've asked you to solve this problem mainly to get practice translating the solution we derived in class into the formalism of SPNE. For an added challenge (not to turn in), generalize your solution to the case where there are n flags, and on each turn a player must take a number of flags between 1 and k, where k is a positive integer less than n.)