Exercises and Projects for Chapter 5: Sequential Games II: Perfect Information and Randomness

Exercises

1. What are the expected payoffs and best strategies in Random Nim(5,1)?
2. What are the expected payoffs and best strategies in Random Nim(5,0.8)?
3. What are the expected payoffs and best strategies in Random Nim(5,0.6)?
4. What are the expected payoffs and best strategies in Random Nim(5,0.4)?
5. What are the expected payoffs and best strategies in Random Nim(5,0.2)?
6. For which p is Random Nim(5,p) fair, i.e. giving the same expected payoff to White and Black?
7. What happens to the expected payoffs for White in Random Nim(n,0.5) if n is taken larger and larger? What about Random Nim(n,0)? Explain.
8. What are the expected payoffs and best strategies in Random Nim(5,0)?
9. What are the expected payoffs in this game, if both players Ann and Beth would play optimally? At the beginning, will Ann choose "up" or "down"? When Ann would have to decide between "hot" and "cold", which one would she choose? When she would have to decide between "north" and "south", how would she decide? How would Beth decide between the options "left" and "right", between the options "west" and "east", and between the options "fast" and "slow" if she would have to?
   
10. What are the expected payoffs in this game, if both players Ann and Beth would play optimally? At the beginning, will Ann choose "up" or "down"? When Ann would have to decide between "hot" and "cold", which one would she choose? When she would have to decide between "north" and "south", how would she decide? How would Beth decide between the options "left" and "right", between the options "west" and "east", and between the options "fast" and "slow" if she would have to?
    
11. Analyze the 3 × 3 version of Polynomial REC THE SQUARE with randomness game. Explain what will happen if both play optimally. How much will each of the players expect, if a win counts as +1 and a loss as -1?
    Note that you can describe the game using the following 27 states, where each symbol subsumes the cases obtained by rotation and reflection.
    
12. The following sequential game with randomness but perfect information is given in extensive form. There are two players, Ann and Beth. Vertices are labeled by the player whose turn is it. Vertices without such a label are random moves, the probabilities for the two options are 50% and 50% in each case. The payoffs of the end vertices are given, always first Ann's payoff, then Beth's.
    • Analyze the game using backwards induction.
    • What first move would Ann make when playing optimally?
    • What is the expected payoff for Ann in the game when Ann plays optimally?
13. 5 PIRATES with random selection: Five pirates have to decide how to distribute 20 gold coins they have found. They do it according to the following rules. In each round they sit in a circle and rotate a bottle of rum. The one to which the bottle points has to propose a distribution of the coins. This proposal is voted on, with the proposer voting too, and even deciding in case of a tie. That implies that in case of only two pirates, the proposal will always win, and in case of four pirates, the proposer needs only one of the others voting for the proposal. If the proposal wins, everything is settled. If not, the proposer is thrown into the water and dies, and the next round starts. Assume that the pirates value their life worth 40 gold coins, and prefer throwing somebody overboard if everything else is equal (are playing the "hostile" variant).
    What would you propose if the bottle points on you and there are 2, 3, 4, or 5 pirates left?
14. ** Consider the following variant of draw poker. Each player gets a hand of three cards out of a 32 card deck. The ordering of the hands is straight flush (5 points), triple (4 points), flush (3 points), straight (2 points), one pair (1 point), and nothing of the above (0 point). Each player is allowed to exchange one card from her hand against an unknown card from the deck. What is the optimal way to proceed if the goal is to maximize the expected points of the hand, provided you hold ...
    • a) heart 7, spade 8, spade 10
    • b) heart 10, spade 10, spade K
15. ** We face the same situation as in the previous exercise, but a more realistic goal (if the game is played in the usual way that the highest hand wins) is to maximize the expected value of the percentile of the hand, where one pair has a percentile of 67.9 (which is the probability in percent to have nothing), straight has percentile 67.9 + 19 = 87, flush has percentile of 67.9 + 19 + 7.7 = 94.7, triple has percentile of 67.9 + 19 + 7.7 + 4.5 = 99.2 and straight flush finally has a percentile of 67.9 + 19 + 7.7 + 4.5 + 0.6 = 99.879 = 100 - 0.121. Would the perfect strategy change? (For simplicity we assume that two hands of the same type, say two straights, have equal weight, although this is not the case in reality.) What is the optimal way to proceed provided you hold ...
    • a) heart 7, spade 8, spade 10
    • b) heart 10, spade 10, spade K

1. Project: JOB INTERVIEWS: You are offered four job interviews in four different companies, companies A, B, C, and D. Company A would offer 125,000 Euros, but you know that you only have a small chance to get the job, which you estimate to be 1/5. Company B would offer 100,000 Euros, and you estimate the chance to be accepted to be a little higher, around 1/4. Company C would offer 75,000 Euros, and the chance to get the job is estimated as 1/3. Finally, Company D offers only 50,000 Euros but you seem to have a decent chance of 1/2 there. These job interviews are scheduled sequentially, in different weeks. In each case, if you are offered the job, you have to decide immediately whether you accept it or not. In case you accept you have to cancel the remaining job interviews. In case you decline, you cannot come back later.

   • Assume company B interviews the first week, company D the second week, company A the third week, and company C in the last week. How would you play? Would you accept or decline an offer company B made? What about company D? How much is the expected salary for your chosen strategy?
   • Answer the same questions provided company D interviews the first week, company A the second week, company C the third week, and company B in the last week.
   • Assume you can decide which company to visit in the first week, which one in the second week, and so on. How would you order them? Give some explanation.

2. Project: 5 ENVELOPES: 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?

   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?

   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 10000 Dollars. How would expected value and strategy change? Would they change?

3. Projects: OH-NO or OH-NO 6: Write a paper on "OH-NO" discussed above in the text, or about "OH-NO 6" which works in the same way, except that now the appearance of a "6" would end the game and delete all accumulated money. You can play the games here and here.
   Among others, you could address the following items:

   • What is the best strategy for playing each of the two games. Remember that for "OH-NO" the best strategy was given already above.
   • What is the expected payoff when playing the optimal strategy?
   • Now consider other strategies, like for instance stopping whenever the heap has reached 12 points. What is the expected payoff when playing this strategy?
   • Can you find the expected payoff of a more creative strategy, like stopping whenever the heap number is even, and proceeding otherwise?
   • You could also perform experiments in the applets and compare the theoretical values for expected payoffs with the empirical results. For this, play 100 plays for one or several of the strategies mentioned.


4. Project: 3 × 4 version of Polynomial REC THE SQUARE with randomness, play it here, Analyze the game. Can the 4 × 4 version be analyzed too? If not, describe the difficulty you encounter.