Homework 2

Homework 2 2008, Sequential Games, Probability

Analyse the following game: TWO-ROUND BARGAINING(5,3): There is a fixed number, say 5, of dollar bills for both players. Ann makes an offer how to share them, which Beth can either accept or reject. If she accepts, the bills are divided as agreed upon. If the rejects, two dollar bills are taken away and only three remain on the desk. Then Beth makes an offer how to share these three dollars, which Ann can accept or reject. If Ann accepts, the bills are divided accordingly, if she rejects, nobody gets anything. Draw the extensive form of the game, and explain what will happen if both play optimally. Remember that you don't have to use the tree---you can also use the digraph to simplify matters.

Here is the digraph:

And here after doing backwards induction with neutral Ann and Beth, choosing the options with equal probability in case of several options leading to the same payoff. Interestingly enough Beth has a slight advantage in this game.

If both Ann and Beth are friendly to each other, or if both are hostile to each other, the payoffs are even 2 for Ann and 3 for Beth.

Analyse the 3·3 version of REC THE SQUARE game. Draw the extensive form of the game, and explain what will happen if both play optimal.
Black will win and White will lose. Note that you can describe the game using the following 18 states, where each symbol subsumes the cases obtained by rotation and reflection. State 0 is the Start, and states 12, 16, abd 17 are the terminal states. In State 12, White has won, and in states 16 and 17 Black has won. Working back from these states, using backwards induction, one obtains the result.
0:
1: 2:
3: 4: 5: 6:
7: 8: 9:
10: 11: 12: 13: 14: 15:
16: 17:

Here is the extensive form as digraph:

Analyse the 3·3 version of CREATING HOLES, a variant of REC THE SQUARE. Draw the extensive form of the game, and explain what will happen if both play optimal.
Of course this variant has the same 18 states as the main version, with again state 0 as start, and states 12, 16, abd 17 are the terminal states. The payoffs in state 12 are 2 for White and 1 for Black. The payoffs in state 16 are 0 for White and 1 for Black. The payoffs in state 17 are 1 for White and 0 for Black. Working back from these states, using backwards induction, one obtains that White will win a payoff of 2 and Black a payoff of 1.
0:
1: 2:
3: 4: 5: 6:
7: 8: 9:
10: 11: 12: 13: 14: 15:
16: 17:

a) Two cards are selected randomly from a shuffled 52-card deck. Someone tells you that the first card is black. What is the probability that the second card is black too?
b) Again two cards are selected randomly from a shuffled 52-card deck. Someone tells you that at least one of the two cards is black. What is the probability that both cards are black?
a) Since there are only 25 black cards left in the 51 card stack after the first card, a black one, has been taken, the probability is 25/51, slightly less than 1/2.
b) What are the simple events? All combinations of two cards where at least one of them is black. Thus, out of all the (52·51)/2 combinations of two cards, the (26·25)/2 red-red combinations are excluded. Therefore we have (52·51)/2 - (26·25)/2 simple events. How many of these simple events considered form the event "two black cards"? Obviously (26·25)/2 of them. Therefore the probability of two black cards if we know that at least one of the cards is black is ((26·25)/2)/((52·51)/2 - (26·25)/2) = (26·25)/(52·51 - 26·25) = 25/77, about 1/3, much less than in (a).

Assume you flip a coin and get $3 if the result is heads, and have to pay $2 if the result is tails. What is the expected value?
Heads and tails are equally likely with probability 1/2 each. Therefore the expected value equals (1/2)·3 + (1/2)·(-2) = 1/2.

You face 5 envelopes, containing $0, $1000, $2000, $3000, and $4000. You randomly choose one of them. What is the expected value?
All five outcomes are equally likely, and have therefore a probability of 1/5. Therefore the expected values for the money is (1/5)·0 + (1/5)·1000 + (1/5)·2000 + (1/5)·3000 + (1/5)·4000 = it is (0+1000+2000+3000+4000)/5 = 10000/5 = 2000.

You have five $1-bills, three $5-bills, and one $10 bills in your pocket. You randomly choose one of them to give the taxi driver a tip. What is the expected value?
Each of the nine bills is equally likely, a probability of 1/9. Since five bills are one-dollar bills, the probability to draw one of them is 5/9. In the same way, the probability of drawing a $5 bill is 3/9, whereas the probability of drawing the $10 bill is 1/9. Therefore the expected values is (5/9)·1 + (3/9)·5 + (1/9)·10 = 30/9 = 3.33 dollars.

5 Envelopes (a challenge)

$10000 is distributed into 5 envelopes. One envelope, the "bomb", remains empty. In the basic version the player knows how much is put into each envelope, let's say $1000, $2000, $3000, $4000, and 0. Then the envelopes are shuffled and in each round you, the player, can either choose to get one of the remaining envelopes or keep the money you have collected so far and quit. If you ask for a new envelope, randomly one of the remaining envelopes is selected and handed to the player. If this envelope contains nothing (the bomb), the player you lose all the money you collected in the previous envelopes, otherwise you add the money to the money taken so far.

How much would you "expect" to win when you were playing the game? Would you expect to win more or less if the $10000 were differently distributed on the envelopes, say as $2000, $2000, $2000, $2000, and 0? What if it were distributed as $100, $500, $2600, $7000, and 0? What about other distributions? Would you play different then? And what exactly does "expectation" mean?

Version b: In another version, you, the player can distribute the money into the envelopes (using the requirement that one of them, the bomb, has to remain empty) before starting to play. How would you distribute the money, and how would you play?

Version c: In still another version, the distribution of the money on the 5 envelopes is not known to the player. It is just known that exactly one envelope is empty and that the other four contain all the 10000 Dollar. How would expected value and strategy change? Would they change?

The expected value when playing it best is $3200, see this Excel sheet. The expected value when playing optimal would change if the money is distributed differently, see again the sheet. You can get as much as almost $5000, when distributing it as 9997, 1, 1, 1. Then the obvious strategy would be to play until you got the envelope containing the big money. This also answers the question for version b.

The question on version c I cannot answer here. It depends on your beliefs. The whole challenge would be a good research project. Anybody interested?