RANDOM NIM(5,1/2): Five stones lie on the desk. Again Black and White alternate to remove either one or two stones. Again the player who has to move but cannot (since there is no stone left) loses, and the payoffs are also identical to the preceding game. However between these moves of White and Black, randomly either 0 or 1 stones are also removed (with probability 0.5 and 0.5 respectively). What are the expected payoffs and the best strategies for the two players? Play the game against the computer in the random version. Now put in the values "5" and "0.5" into the textfield before you start.
We need a few modifications to the concept of the extensive form of a game as described here. In addition to the ordinary vertices, corresponding to positions of the game where one of the players is supposed to make a decision, there are random vertices in the digraph representing the game. At these vertices, randomness makes "decisions" in a random way. Therefore, there are arcs out of these random vertices to other vertices, positions that can be reached from the random position in question. These arcs are labeled by the appropriate probability to reach the other position from the random position. Of course, the probabilities attached to all outgoing arcs of such a random vertex must sum up to 1. It is also understood at the moment that all these probabilities are common knowledge. There can also be (and very often is) randomness at the beginning of the game. In this case, the start vertex would be a random vertex. Thus now we have three kind of vertices: random vertices, position vertices with labels of some player, and end vertices, and the start vertex is either a random or a position vertex.
Here is the digraph for the Random Nim game explained above. The probability labels are supressed. Also, in the two end positions only the payoff for White (1 and -1) is given. Since it is a zero-sum game, the payoff of Black is just the opposite of that of White.
Procedure for Backwards Induction with Randomness : Your goal is to have values for each player assigned at every vertex. As long as not all vertices have values attached, do the following:
|
(1) Find a vertex with no values attached yet, but with the property that all its successors in the digraph have values attached. Such a vertex can always been found (why?). Call this vertex "V". (2) At vertex V, either one player, say "X" has to move, or it is a random vertex. In the first case we proceed to step (P3), in the second case to step (R3). | |
|
(P3) If V is a player vertex belonging to player X, then we proceed as in sequential games without randomness. We identify the successor vertex of V for which the value for player X is highest. This is the vertex where player X want to move to (since the values will turn into payoffs eventually). Let's call this other vertex "W". Move to step (P4). (P4) Then we copy the values of vertex W to vertex V. Go back to step (1). |
(R3) If V is a random vertex, then all successors may occur with the given probabilities. Therefore the value at V for any given player is the expected value of the values of that player at the successor vertices, i.e. the sum of the products of probabilities to arrive there and the values. Compute this expected value for all player values. Go back to step (1) |
The tree we consider is no longer a probability tree, with situations and different experiments at the situations. Rather only in some situations random experiments are performed. At other situations the human player is supposed to make decisions, to choose between several options. Therefore we have two types of vertices in the tree or digraph---those where "Nature moves", where experiments are performed, and those where the human moves. For those where the human moves, edges are drawn towards the possible resulting situations.
|
1-CANDIDATE QUIZ SHOW: You play a quiz show with up to 6 questions.
The questions are worth $1, $1, $2, $4, $8, and $16. After each round,
you have the option to stop and take the money you have won so far, or hear the next
question. If you have heard the next question, there is no way out---you have to
answer it correctly, to go into the next round. If you give the wrong answer, all
your money is lost. You also know that in round n the probability of giving a
wrong answer is 2/(9-n). (Thus it increases from 2/8 over 2/7, 2/6, 2/5, 2/4 to 2/3
over the six rounds.) When do you stop?
|
Here you can play: |
Here is the tree. At each round you have the option to dare the next question or to stop. If you stop, an edge goes to a leaf, an end situation, and red number written at that leaf shows how much you have won. If you dare the next question, an edge goes to a green vertex, where a random experiment is performed. This random experiment has two outcomes---the answer can be correct or wrong. The probabilities for the two oucomes are written below the green edge. If the answer was wrong, we have again reached a leaf, a final situation, with payoff of 0. Otherwise, you are facing the decision whether to stop or to dare the next question of the next round.
What we want to do is to assign expected payoffs to all vertices of the tree, not just to the leaves. However, if we want to do this by beginning at the beginning we face some problems. What is the expected payoff for the game at the very beginning? Probably it is best to "dare" the first question. Then the payoff for the first decision vertex is the same as the expected payoff at the first green (random) vertex. But this expected payoff would be 2/8·0 + 6/8· the expected payoff of the second player vertex. But this is also unknown, and so on.
$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 decision tree of the original 5 Envelopes "game" can be seen here. Since it is so huge, and since the situations where you have drawn first $2000, and then $3000, or where you have drawn first $3000, and then $2000 are really identical situation for you, it is better to identify such situations and move to the digraph. This digraph can be seen in this Excel sheet,, where backwards induction is done automatically. There are five envelopes, containing amounts A, B, C, D, and 0. You can change the amounts A, B, C, D by typing in different numbers into cells B4 to B7. Actually the random vertices are omitted, all vertices are decision vertices, they are labeled by the bills received so far, and they are colored black if they are final situations (with nothing to decide), red if you rather stop, and green if you rather proceed. The expected value if proceeding is shown in the grey cell below the situation name, and the payoff if stopping, the accumulated payoff, is shown in the yellow cell. In each case, the payoff of that decision vertex is the maximum of both values. Therefore the expected payoff of the original version is $3200.
|
OH-NO
The player rolls a die repeatedly. After each roll, as much dollars as the die shows are added to a heap, which initially is empty. The game ends if either
Analysis:
These is obviously only one player, playing against Nature.
Unfortunately it is not a finite game---the extensive form is infinite.
For this reason, backward induction cannot be applied, but we can still solve the game
using a similar idea. Intuition may tell us that we want to roll the die again provided the heap is small, but
may want to stop if the heap has reached some size. The question is: From which heap size on would we stop?
The positions for the player are determined by the value of the heap obtained so far, so we denote these positions by integers. Each position n has an expected value v(n) for the player attached---the expected payoff the player would obtain when having reached that position and playing optimally from then on. Since in every position the player has the option to stop, obtaining the value of the heap as payoff, v(n) ≥ n for all natural numbers n. If the player is at position n and continues, he or she will expect (1/6)·0 + (1/6)·(v(n+2)) + (1/6)·(v(n+3)) + (1/6)·(v(n+4)) + (1/6)·(v(n+5)) + (1/6)·(v(n+6)). Since we started just at any position n, and don't use backward induction, we don't know the expected values at these positions n+2, ... n+6 yet, but we know that they are at least n+2, ... n+6. Therefore, the player at position n who continues to play expects at least (1/6)·(n+2) + (1/6)·(n+3) + (1/6)·(n+4) + (1/6)·(n+5) + (1/6)·(n+6) = (1/6)·(5n+20). That means that the player will continue playing if this value (1/6)·(5n+20) is larger than n, i.e. if 5n+20 > 6n, or 20 > n. We still don't know what to do when facing heap sizes of 20 or more, but using the assumption that the best strategy is to continue for heap sizes below some critical value m and stop after, we can easily obtain that 20 is this critical heap size. Thus the best strategy is to roll until you have 20 points. Then you stop. The expected value, however, is smaller than 20 if using this optimal strategy. How large is it? What changes in the "6"-version of the game, where a "6" loses? |
Here you can play ten plays of "OH-NO": |
