1. nim with Two Piles of Coins



Download 37.82 Kb.
Date conversion21.03.2016
Size37.82 Kb.
1. NIM with Two Piles of Coins
Consider the following version of NIM. There are two piles of coins. Two players alternate moves. In each move, one player can remove 1, 2, or 3 coins from a single pile of coins. (If one pile has no more coins, then version of NIM is simplified to the version that we discussed in class on Monday, January 28). The player who removes the last coin wins the game.
We use the notation (n, m) to denote the position where there are n coins in pile 1 and m coins in pile 2. Assume throughout that n-3 < m < n+3, i.e. that the number of coins is each pile is within 3 of the number of coins in the other pile.
(a) Find all combinations (n, m) such that the next mover can win the game in one move. Define this set of combinations as set W1 (i.e. The “Win in One Move” set).


If only one pile has coins and it has 3 coins or less, then is possible to win in one move.

That is, W1 = { (0,1), (0, 2), (0, 3), (1, 0), (2, 0), (3, 0)}
(b) Now find all combinations (n, m) such that the next mover must make a choice that leaves a position in W1. Define this set of combinations as set L2 (i.e. The “Lose in One Move” set).
If a player is forced to eliminate one pile of coins and leave three or fewer coins in the second pile, then she must make a choice that leaves a combination in W1. But there is only one combination – (1, 1) – that falls into this category. For example, note that from position

(2, 1), it is possible to remove 1 coin from pile 1 and leave position (1, 1), which is not in W1.

That is, L1 = { (1,1) }


(c) Use backward induction to find sets W2 and L2 (“Win in Two Moves”, “Lose in Two Moves”).
W2 consists of all positions where it is possible to make a move that leaves a position in L1. So W2 consists of all positions where it is possible to remove coins from one pile to leave position (1, 1), so W2 = { (2,1), (3, 1), (4, 1), (1, 2), (1, 3), (1, 4)}
L2 consists of all positions where every possible move that leaves a position in W2 (or W1). Once again, there is only one such position and L2 = {(2, 2)}.
(d) Extend your analysis to find sets W3 and L3.
Following the logic of (c), W3 = { (3,2), (4, 2), (5, 2), (2, 3), (2, 4), (2, 5)}; L3 = {(3, 3)}.
(e) Suppose that the game starts with 23 coins in each pile and that Player 1 makes the first move. Should we expect Player 1 to win or lose? Describe the backward induction strategies in words.
Given the pattern of backward induction in (d), we expect to find that L23 = {(23, 23)}, so that Player 1 should lose the game in 23 moves.
In words, every position with an equal number of coins in the two piles is a losing position and every other position (where the piles differ by 3 coins or less) is a winning position. Therefore, the winning strategy for Player 2 is to match each one of Player 1’s moves – if Player 1 takes x coins from Pile 1 then Player 2 should take x coins from Pile 2. Then there will always be an equal number of coins in the two piles at each of Player 1’s moves.
If Player 1 wants to draw out the game as long as possible, he should remove 1 coin from a pile at each turn. Then after 22 moves, Player 1 will face position (1, 1) and so Player 2 will win the game in 23 moves. Any other strategy for Player 1 will simply shorten the game, but Player 2 will still win.

2. A Patent Race
Firms A and B are in an R&D race to develop a patent.
The firm that gets the patent first will make $10M. The other firm will make nothing.
In each period, each firm can progress either 0 steps, 1 step (with cost $1M), 2 steps (with cost $4M), or 3 steps (with cost $9M) towards the finishing line.
We assume that the firms move in sequence. We wish to determine the backward-induction strategies, depending on the starting position.
We use the notation (n, m) to denote the position where firm A is n steps and firm B is m steps from the finishing line.
In class, we showed that if both firms are within 3 steps of the finishing line, then the firm whose turn it is to move will move as many steps as is necessary to finish in one period.
(a) Suppose that the position is (4, 3) and it is A’s turn to move. What is the backward induction solution to the game?
If A takes a step towards the finish line with this move, then B will finish the work next period. So instead, A should avoid costs by not moving. In fact, by this reasoning, A should never take a further step. Recognizing this, B can achieve the patent at minimum cost by taking one step in each of the next three moves. The payoff in this backward induction solution is (0, 7).
(b) Now suppose that the position is (4, 4) and it is A’s turn to move. What is the backward induction solution to the game?
A can induce the desirable outcome in part (a) by taking one step at this move to get to

(3, 4), which yields payoff (7, 0). Including the cost of the current step for A, the payoff for the remainder of the game is then (6, 0).
(c) Now suppose that the position is (5, 4) and it is A’s turn to move. What is the backward induction solution to the game?
If A takes one step, then B will take one step to get to (4, 3), which is a winning position for B and a losing position for A. But if A takes two or more steps, A can achieve a winning position. So A should take two steps to get to (3, 4), which has payoff (7-4, 0) = (3, 0).
For parts (d) to (f), define the “trigger zone” as all the points where the firm moving first can ensure victory. (That is, it will get the patent and achieve a positive payoff.) and the “safety zone for A” as all the points where, regardless of which firm moves first, A can ensure victory. Define the safety zone for B similarly.
(d) Consider all the points where both firms are at a distance 5 or less from the finish line. Which points lie in the trigger zone, which lie in the safety zone for A, and which lie in the safety zone for B.
If one firm is 3 steps or less from the finish and the other is more than 3 steps from the finish, then the first firm will win the game. So (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5) are in the safety zone for A and similarly (4, 1), (5, 1), (4, 2), (5, 2), (4, 3), (5, 3) are in the safety zone for B.
If both firms are 4 or 5 steps from the finish, then the next firm to move can make a move that leaves a position in its safety zone (at cost at most 4). So (4, 4), (4, 5), (5, 4), (5, 5) are in the trigger zone.
(e) Now extend your analysis from (e) to all points at a distance 9 or less from the finish line.
6 units from the finish
A firm that is 6 units from the finish can move into the safety zone by moving 3 steps, but this requires an immediate cost of 9 and additional cost of at least 3 to achieve the patent, so it would be preferable for the firm not to move at all. That is, no firm would ever move 3 units if it starts at least 5 units from the finish.
Therefore, if firm A is 5 or less units from the finish while firm B is 6 or more units from the finish, the backward induction solution must produce a win for firm A. Using the terminology above, (5, 6), (5, 7), (5, 8), (5, 9) are in the safety zone for A, while (6, 5), (7, 5), (8, 5), (9, 5) are in the safety zone for B.
Once one firm is in its safety zone, the other firm will never take another step in the backward induction solution, so the first firm can simply take one step at a time to the finish. Thus, the payoff at (5, y) where y > 5 is (5, 0), while the payoff at (x, 5) where x > 5 is (0, 5).
So if A is to move at (6, y) where y > 5, A should move 1 step to (5, y) to achieve future payoff (5, 0) and net payoff (4, 0). Similarly, if B is to move at (x, 6) where x > 5, the backward induction solution is for B to move one step for net payoff (0, 4).
7 units from the finish
If A is to move at (7, 6), A’s best strategy is to move two steps to get to (5, 6), which is in A’s safety zone, and which yields net payoff of (1, 0).
Similarly if B is to move at (6, 7), B should move two steps to achieve net payoff (0, 1).
In sum, the first person to get to 5 units away from the finish and the first person to get to 7 units away from the finish must win the game. However, it is not the case that the first person to get to 6 units away from the finish must win the game.

8 units from the finish
From (8, 8), the next firm to move should go one step to get to a point in its safety zone.


But if it is A’s move at (9, 8), A should not incur costs. While A could get to its safety zone by moving two steps, it could never make a positive payoff by doing so since its costs for achieving the patent would be at least 11.

9 units from the finish
The prior analysis indicates that the first firm to move 1 step is in its safety zone. So the backward induction solution is to move 1 step, anticipating that it will be possible to gain the patent by moving one step at each future opportunity.
(f) What pattern emerges? What are the situations in which it pays to spend the money required to move fast?
A firm that is not ahead (the other firm is at least as close to the finish) should move more than one step if it is 2, 3, 5, 7 steps away from the finish if can get ahead of the other firm by doing so. In a tie at (4, 4), (6, 6), (8, 8), (9, 9), a move of one step get the firm into its safety zone. Otherwise, a firm that is behind should simply give up.

3. Bargaining with Pirates
A ship of 15 pirates has just claimed a treasure of 100 indivisible gold coins. Their traditional procedure for dividing the treasure is as follows. The pirates are ordered by age and then the oldest pirate has the honor of making the first proposal.
After any proposal, all the pirates vote "Yes" or "No". The proposer is allowed to vote as well. If at least 50% of the votes are in favor, the proposal is adopted and the game ends. If the proposal is voted down, then the pirate who made the proposal is thrown overboard to the sharks and then the next oldest pirate is asked to make a proposal.
Note that ties are broken in favor of the proposal. Coins cannot be divided in fractional units. Assume throughout that a pirate will never vote for a proposal that gives him 0 coins.
(a) Suppose we reach the point where only two pirates remain and thirteen have been thrown overboard. At that point, only one pirate needs to vote for the next proposal in order for it to be adopted. What will be the outcome in this contingency?
Throughout the problem, I denote the pirates by descending age. So Pirate 1 is the oldest, and Pirate 15 is the youngest. Note also that I assume the pirate making the offer votes in favor of his own proposal (this is weakly dominant, and does not change the analysis in any meaningful way). Without loss of generality, I assume that

u(# of coins = C, # of other pirates overboard = O) = C + ε*O, with ε arbitrarily small.
A pirate’s strategy includes whether he votes “yes” or “no” for each possible offer by older pirates, plus the offer he makes if it gets to be his turn.
The backward induction solution is: Pirate 14 offers (100,0) and keeps all the money. Pirate 15 can vote “yes” or “no” (or any mixture of the two)—he is indifferent.
(b) Now consider a situation where only three pirates remain. Use the answer to (a) to identify the backward induction outcome in this case.
If Pirate 13 is thrown overboard, Pirate 14 ends up with 100, and Pirate 15 gets 0 from the analysis in part a. P14 weakly prefers voting “no” regardless of the offer P13 makes (this is only a weak preference, because if both P13 and P15 vote yes, P14’s vote makes no difference; from here on out I will assume pirates vote according to their weak preference for simplicity’s sake). Meanwhile, P15 will vote yes to any offer which gives him at least 1 coin, since if P13 is thrown overboard, he will get 0.
Based on this logic, the backward induction solution is for P13 to offer (99, 0, 1), and P13 and P15 to vote in favor of that division.
(c) What will be the backward induction outcome in the game with all 15 pirates on board?
Iterating the logic from above, the backward induction outcome in a four-pirate game will be (99, 0, 1, 0), with P12 and P14 voting in favor, and P13 and P15 voting against (all of these are again weak preferences). With 5 pirates: (98, 0, 1, 0, 1).
This continues such that the oldest remaining pirate gives 0 to the second-oldest, 1 to the third-oldest, 0 to the fourth-oldest, 1 to the fifth-oldest, etc., taking the rest for himself. All pirates who get a positive number of coins vote in favor, and those getting 0 vote against.
This leads to the following outcome with 15 pirates: (93,0,1,0,1,0,1,0,1,0,1,0,1,0,1).

(d) How would the answers to parts (a) through (c) be different if the voting rule is adjusted slightly so that the proposal requires a majority of the votes (more than 50%) to be adopted?
Now the two-player game produces the opposite result: P15 will vote “no” to any proposal, since then he gets to throw P14 overboard and keep all the coins.
Three-player game: P13 now needs P14’s support, and can get it by offering (99, 1, 0)
Four-player game: P12 now needs support of two other pirates to get more than 50% of the vote. So P12 needs to offer (97,0,2,1).
5 players: (97,0,1,0,2)

6 players: (96,0,1,2,1,0)

7 players: (96,0,1,2,0,0,1)

8 players: (95,0,1,2,0,1,1,0)

etc.

15 players: (92,0,1,2,0,1,0,1,0,1,0,1,0,0,1)
Note that starting with 7 players, there is an arbitrary choice of which pirate to give 2 coins to, resulting in slightly different possible answers. As for part d, we would still get a range of Nash equilibria, but the division would be (x, 100-x, 0). The logic is the same in part d above, except we switch P14 and P15.

4. Efficient Investment in a Sequential Game
Suppose that a worker interacts with a firm as follows. The worker first decides how much to invest in developing his skills. Let x denote the worker’s investment and suppose that this entails a personal cost of x2, where x > 0.
If the worker decides to work at the firm, then his investment generates revenues of ax, while if he works on his own, his investment generates revenues bx, where a > b. The difference between the two options is that the worker keeps all of the revenues if he works on his own whereas he splits them with the firm if he works for the firm.
(a) Suppose that the worker chooses his level of investment, then the firm observes that level of investment and offers a wage w. The worker can accept the wage offer for payoff w - x2 for the worker and payoff ax – w for the firm, or reject and work on his own for payoff bx - x2 for the worker and 0 for the firm. What is the backward induction solution to this game?
The firm has to offer the worker a wage at least equal to the worker’s outside option for the worker to accept the offer. But if the firm observes x, it has no reason to offer the worker a higher wage than that, so the firm will offer a wage just greater than bx, or in approximation w = bx. (Note that since a > b, the firm makes a positive payoff if the worker accepts wage w = bx, so prefers making this wage offer to the worker to not offering the worker a job at all.)
Whether the worker accepts or rejects the offer, then the worker achieves total payoff bx - x2 , so the worker should choose x to maximize this value:

Max_x bx - x2
which has FOC b = 2x and optimal solution x* = b / 2.
So the SPE of this game calls for the worker to choose x* = b/2, the firm to offer wage w = bx / 2 (or a wage just greater than that) and the worker accepts the offer.
(b) Suppose instead that the firm makes an offer to the worker before the worker chooses his level of investment. Each offer consists of a base wage y and a percentage of revenues z. If the worker accepts, he then chooses x and receives a total payoff of y + zbx - x2, while the firm receives a total payoff of (1-z)bx. If the worker rejects the wage offer, then he chooses x and receives a total payoff of bx - x2 with payoff 0 for the firm. What is the backward induction solution to this game?
If the worker accepts the firm’s contingent offer, his expected payoff is then y + zax – x2, and then the worker will choose x to maximize this value. The FOC for the worker’s maximization problem gives the condition

za – 2x = 0,
with associated solution x* = az / 2. This produces total payoff for the worker of y + a2z2 / 4. If the worker rejects the firm’s offer, we know from (a) that the worker will chooses x = b / 2 with associated payoff b2 / 4. The worker will accept the firm’s offer if

y + a2z2 / 4 > b2 / 4
The firm maximizes profits by choosing the minimum value of y so that the worker will accept the offer, i.e. y = b2 / 4 - a2z2 / 4 = (b2 - a2z2) / 4. That is, from the perspective of the firm, both y and x can be viewed as functions of z: y = (b2 - a2z2) / 4; x* = az / 2

so that the firm can identify the optimal choice of contract in a single-dimensional maximization problem to identify the optimal choice of z.
Max_z ax – zax – y = (1-z) (ax) – y = (1-z) (a2z / 2) - (b2 - a2z2) / 4

This has FOC a2 / 2 – a2z + a2 z / 2 = (1/2) (a2 - a2z) = 0 with associated solution z = 1, y = -( a2 - b2) / 4.
In this contract, all proceeds of the firm go to the worker, who pays an upfront fee (a2 - b2) / 4. These kinds of contracts are sometimes described as “selling the firm to the worker”.
(c) Compare the outcomes of (a) and (b) to the efficient level of investment – the level of investment that maximizes the sum of payoffs to the worker and the firm. If neither of these outcomes yields the efficient level of investment, then suggest a change to the game that would yield an efficient outcome as the backward induction solution to the game.

Assuming the worker accepts an offer from the firm, the combined payoff for worker and firm is ax - x2, which is maximized by the choice xopt = a / 2.
Comparing the investment levels in SPE’s for (a) and (c) to xopt, first, note that the level of investment is inefficiently low in part (a) since a > b. This result arises because the worker’s investment produces a positive externality for the firm that is not incorporated into the firm’s wage offer – so this positive externality does not affect the worker’s choice of investment.
By contrast, the contract in (b) induces the optimal level of investment. This result arises because the firm can design a contingent contract to eliminate the externality. The optimal contract gives all of the revenues to the worker and gives a fixed payment to the firm. Therefore, any increase in profit due to a change in investment level x accrues to the worker, not the firm, and so the worker has every reason to choose the level of x that maximizes the combined payoff of firm and worker.
(d) Use the comparisons in part (c) to comment on the importance of first-mover advantage and/or commitment in this game.
The real advantage in this game is that the firm can make a take-it-or-leave-it offer to the worker. Regardless of the order of moves in the game, the firm has all of the bargaining power in negotiations, with the result that the worker can never do better than his outside option.


The database is protected by copyright ©essaydocs.org 2016
send message

    Main page