Question

Consider a game in which two players take turns moving a coin along a strip of wood (with borders to keep the coin from falling off). The strip of wood is divided into five equally sized regions, called (in order) \(A, B, C, D\), and E. Player l's objective is to get the coin into region E (player 2 's end zone), whereas player 2's objective is to get the coin into region A (player l's end zone). If the coin enters region \(A\), then the game ends and player 2 is the winner. If the coin enters region E, then the game ends and player 1 is the winner. At each stage in the game, the player with the move must decide between "Push" and "Slap." If she chooses Push, then the coin moves one cell down the wood strip in the direction of the other player's end zone. For example, if the coin is in cell B and player 1 selects Push, then the coin is moved to cell C. If a player selects Slap, then the movement of the coin is random. With probability \(1 / 3\), the coin advances two cells in the direction of the other player's end zone, and with probability \(2 / 3\) the coin remains where it is. For example, suppose it is player 2 's turn and the coin is in cell C. If player 2 chooses Slap, then with probability \(1 / 3\) the coin moves to cell \(\mathrm{A}\) and with probability \(2 / 3\) the coin stays in cell \(\mathrm{C}\). The coin cannot go beyond an end zone. Thus, if player 1 selects Slap when the coin is in cell \(\mathrm{D}\), then the coin moves to cell \(\mathrm{E}\) with probability \(1 / 3\) and it remains in cell \(\mathrm{D}\) with probability \(2 / 3 .\) If a player wins, then he gets a payoff of 1 and the other player obtains zero. If the players go on endlessly with neither player winning, then they both get a payoff of \(1 / 2\). There is no discounting. The game begins with the coin in region B and player 1 moves first. (a) Are there any contingencies in the game from which the player with the move obviously should select Push? (b) In this game, an equilibrium is called Markov if the players' strategies depend only on the current position of the coin rather than on any other aspects of the history of play. In other words, each player's strategy specifies how to behave (whether to pick Push or Slap) when the coin is in cell B, how to behave when the coin is in cell C, and so on. For the player who has the move, let \(v^{k}\) denote the equilibrium continuation payoff from a point at which the coin is \(k\) cells away from this player's goal. Likewise, for the player who does not have the move, let \(w^{k}\) denote the equilibrium continuation payoff from a point at which the coin is \(k\) cells away from this player's goal. Find a Markov equilibrium in this game and report the strategies and continuation values. You can appeal to the one-deviation property.

Short answer

Player 1 should push from D and slap otherwise; Player 2 should push from B and slap otherwise.

Step-by-step solution

Analyze Player Moves

First, identify when it might be optimal to "Push". Pushing the coin moves it closer to the player's goal with certainty, while a "Slap" introduces randomness. If the coin is on D for Player 1 or B for Player 2, pushing is optimal since it provides a certain win by reaching the end zone.

Calculate Payoffs for Pushing

Determine the payoff when the decision to push is made. If Player 1 pushes from D to E, they win and receive a payoff of 1. Similarly, if Player 2 pushes from B to A, they also win with a payoff of 1.

Evaluate Slap Outcomes and Payoffs

If a player decides to "Slap", the outcomes depend on probabilities. Evaluate the continuation payoffs by considering the probabilities of moving closer or staying in the same position. Calculate expected payoffs by blending these probabilities.

Determine Equilibrium with Markov Strategies

Markov strategies depend on the current position only. For cell B, Player 1 should slap because the probability of winning increases when closer to cell E. From cell C, Player 2 should slap to increase the chances of reaching cell A.

Calculate Continuation Values

Use the Markov equilibrium principles to establish continuation payoffs where each value reflects the expected winner from each position given optimal strategies. Calculate values such as \(v^0, v^1, v^2\) for Player 1 and \(w^0, w^1, w^2\) for Player 2.

Report Markov Strategies

For Player 1, push at D but slap otherwise. For Player 2, push at B but slap otherwise. Continuation payoffs mirror these strategies, optimizing each player's probability of winning at any given position of the coin.

Key concepts

Markov Equilibrium

In game theory, a Markov Equilibrium is a refinement of Nash Equilibrium where players' strategies rely only on the current state of the game, not on the history of how that state was reached. This is particularly useful in games where the environment can be neatly divided into distinct states or situations. For the coin-moving game on the wood strip, Markov strategies specify actions based on the coin's present location, disregarding past moves.
Each player evaluates the potential payoffs from making a specific move only by considering the current position of the coin. When a strategy depends solely on the present state, it simplifies decision-making and ensures consistency. A strategy that adheres to the principles of Markov Equilibrium is helpful in predicting outcomes and maximizing payoffs because it simplifies strategy formulation by compressing the decision process to only current conditions.

Payoff Calculation

Payoff calculation in this game requires determining the benefits or losses each player will achieve based on their decisions. This involves computing the immediate payoffs for decisive actions like "Push" or "Slap", as well as potential future payoffs based on the probability of various outcomes.
- **Push Move:** The payoff is straightforward. If Player 1 successfully pushes the coin into region E or Player 2 pushes it to region A, they win the game and receive a payoff of 1. The loser receives 0.
- **Slap Move:** Payoffs need to take into account probabilities. For instance, if Player 1 chooses to slap while the coin is at position D, then with a 1/3 probability, they win if the coin moves to E, and with a 2/3 probability, the coin stays in D, requiring further strategy.
By blending these probabilities, each player can compute their expected payoffs, weighing the risk and reward of the slap against the certainty of the push.

Player Strategies

In devising player strategies, one must choose between deterministic and probabilistic options based on the current position of the coin. The decision-making process involves determining what move optimizes the probability of a win. For both players: - **Pushing** ensures that the coin definitely moves toward the player's respective end zone. This is optimal when the coin is one move away from a winning position, like D for Player 1 and B for Player 2.
- **Slapping** may be beneficial when the reward of a random advance outweighs the risk of staying in position. Here, player strategy is often predicated on maximizing the expected value by considering past outcomes' probabilities. In summary, Player 1 should typically "slap" when further from victory (except right before winning), and Player 2 should also "slap" unless assured victory by pushing.

Randomized Decisions

Randomized decisions in our coin game arise mainly from the "Slap" move, where the outcome involves an element of chance. The essence of randomized decision-making is to incorporate uncertain elements into strategies to potentially yield better outcomes than deterministic ones. - **Probabilistic Impact:** A slap could either keep the coin in the same position or advance it two spaces forward with different probabilities. These chances are factors players must consider in their expected payoff calculations, blending risks with potential rewards. - **Strategic Elements:** Here, using a random choice can sometimes force an opponent into a less advantageous position, like slapping to potentially skip an opponent's sure win position.
Understanding the impact of randomized choices helps in manipulating the game flow and can introduce unpredictability, a strategic element that can effectively disrupt an opponent’s plans.