Problem 1
Consider the following game between two players. The players take turns moving a rock among cells of an \(m \times n\) matrix. At the beginning of the game (before the first move), the rock is placed in the bottom-right cell of the matrix [cell \((m, n)\) ]. Player 1 goes first. At each turn, the player with the move must push the rock into one of the three cells above or to the left (or both) of the cell where the rock currently sits. That is, the player may move the rock to the cell above the current position, to the cell to the left of the current position, or to the cell diagonal to the current position in the up-left direction, as pictured below. A player may not move the rock outside of the matrix. The player who is forced to move the rock into the top-left cell of the matrix [cell \((1,1)\) ] loses the game. (a) Suppose the dimensions of the matrix are \(5 \times 7\). Does either player have a strategy that guarantees a victory? If so, which of the two players has such a strategy? (b) In general, under what conditions on \(m\) and \(n\) does player 1 have a winning strategy and under what conditions does player 2 have a winning strategy?
Problem 2
The game Cliff runs as follows. There are two players, each of whom has a pocketful of pennies, and there is an empty jar. The players take turns tossing pennies into the jar, with player 1 moving first. There are two rules: (a) When a player is on the move, he must put between one and four pennies in the jar (that is, he must toss at least one penny in the jar, but he cannot toss more than four pennies in the jar), and (b) the game ends as soon as there are sixteen or more pennies in the jar. The player who moved last (the one who caused the number of pennies to exceed fifteen) wins the game. Determine which of the players has a strategy that guarantees victory, and describe the winning strategy.
Problem 5
Chomp is a game in which two players take turns choosing cells of an \(m \times n\) matrix, with the rule that if a cell has been selected, then it and all cells below and/or to the right of it are removed from consideration (graphically, filled in) and cannot be selected in the remainder of the game. That is, if cell \((j, k)\) is selected, then one fills in all cells of the form \(\left(j^{\prime}, k^{\prime}\right)\) with \(j^{\prime} \geq j\) and \(k^{\prime} \geq k\). The player who is forced to pick the top-left corner cell [cell \((1,1)\) ] loses; the other player wins. Player 1 moves first. Analyze this game and determine which player has a strategy guaranteeing victory. Explain how the identity of the player with the winning strategy depends on \(m\) and \(n\). Can you calculate the winning strategy, for at least some cases of \(m\) and \(\mathrm{n} ?^{4}\)
Problem 6
Consider a three-player version of Chomp. Play rotates between the three players, starting with player 1 . That is, player 1 moves first, followed by player 2 , then player 3 , then back to player 1 , and so on. The player who is forced to select cell \((1,1)\) loses the game and gets a payoff of 0 . The player who moved immediately before the losing player obtains 1 , whereas the other player wins with a payoff of 2 . (a) Does this game have a subgame perfect Nash equilibrium? (b) Do you think any one of the players has a strategy that guarantees him a win (a payoff of 2)? (c) Can you prove that player 1 can guarantee himself any particular payoff? Sketch your idea.
Problem 7
Consider a board game played on an \(m \times n\) matrix. Player 1 has an unlimited supply of white chips, and player 2 has an unlimited supply of black chips. Starting with player 1 , the players take turns claiming cells of the matrix. A player claims a cell by placing one of her chips in this cell. Once a cell is claimed, it cannot be altered. Players must claim exactly one cell in each round. The game ends after \(\mathrm{mn}\) rounds, when all of the cells are claimed. At the end of the game, each cell is evaluated as either a "victory cell" or a "loss cell." A cell is classified as a victory if it shares sides with at least two cells of the same color. That is, there are at least two cells of the same color that are immediately left, right, up, or down from (not diagonal to) the cell being evaluated. A player gets one point for each of the victory cells that she claimed and for each of the loss cells that her opponent claimed. The player with the most points wins the game; if the players have the same number of points, then a tie is declared. (a) Under what conditions on \(m\) and \(n\) do you know that one of the players has a strategy that guarantees a win? Can you determine which player can guarantee a win? If so, provide some logic or a proof. (b) Repeat the analysis for a version of this game in which a victory cell must share sides with at least three cells of the same color.
