Hope someone can help me with this one. The problem I am talking about can be found in the book titled "Game Theory Evolving: A Problem-Centered Introduction to Modeling Strategic Interaction" by Herbert Gintis. The problem is as follows:
Ollie and Stan decide to play the following game of poker. Each has a deck consisting of three cards, labeled H (high), M (medium), and L (low). Each puts 1 dollar in the pot, chooses a card randomly from his deck, and does not show the card to his friend. Ollie (player 1) either stays, leaving the pot unchanged, or raises, adding 1 dollar to the pot. Stan simultaneously makes the same decision. If both raise or both stay, the player with the higher card wins the pot (which contains 2 dollars if they stayed and 4 dollars if they raised), and if they tie, they just take their money back. If Ollie raises and Stan stays, then Ollie gets the 3 dollar pot. However, if Stan raise and Ollie stays, Ollie gets another chance. He can either drop, in which case Stan wins the 3 dollar pot (only 1 dollar of which is Ollie’s), or he can call, adding 1 dollar to the pot. Then, as before, the player with the higher card wins the pot, and with the same card, they take their money back. A game tree for poker with bluffing is depicted here:
(the “?” in the figure means that the payoff depends on who has the higher card).
The questions are:
a. Show that Ollie has 64 pure strategies and Stan has 8 pure strategies.
b. Find the normal form game. Note that although poker with bluffing is a lot simpler than real poker, the normal form is nevertheless a 64 × 8 matrix! If you know computer programming, solving this is not a hard task, however.
c. Show that when you eliminate dominated strategies there are only nine pure strategies for Ollie, and seven for Stan.
d. Show that Ollie always raises with H or M on the second round,and drops with L.
e. Suppose Stan sees Ollie’s first move before deciding to stay or raise (i.e., the two nodes where Stan moves are separate information sets). Now find the normal form game. Notice that this matrix is 64 x 64, so calculating this by hand is quite prohibitive.
f. Eliminate dominated strategies, and show that Ollie has only ten strategies left, while Stan has twelve.
g. Show that Ollie always calls with a high card on the second rounda nd Stan always raises with a high card.
The first is quite obvious, but the problem is the second question. So I am supposed to write a 64 x 8 matrix, which I would prefer to do it programatically (on the computer - this is not a problem). The problem is I do not know how to compute this matrix. What do I put in every matrix cell? How do I programatically calculate these values, so that I can then, in the third question, eliminate dominated strategies?
EDITED 28.6.:
Thanks every body for your answers, but I am still having problems. This is the way I wanted to solve this problem, but something isn't adding up. I wrote a JavaScript program that should solve this problem, but I dont know what I am missing. The program can be found here: http://rok.pnv.si/poker/en.html and it runs in your browser, so you dont have to install it or any thing. The only thing is, that every time you load the page, your computer calculates the steps in solving the game, so loading of the page can take some time, depending on your computer. The game can be found here, with all comments and the source code: http://rok.pnv.si/poker/en.html. Below I provide a description of what I am doing. The same description can be found at the above link.
The way I start is I write down all the possible pure strategies if I dont account for nature choice (which cards will be delt) (this is so that its more obvious). For Ollie these are (RC), (RD), (SC), (SD), for Stan these are (R) or (S). If I account for nature, than I get 64 pure strategies for Ollie and 8 for Stan. For Ollie they go something like this: (RC, RC, RC), (RC, RC, RD), (RC, RC, SC), (RC, RC, SD),... and for Stan something like this: (R, R, R), (R, R, S), (R, S, R),... For Ollie the first strategy (RC, RC, RC) would mean if he gets a low card: raise on first round, call on second, and the same for medium and high cards. For Stan it is the same (only difference is that Stan does not have a second move).
So with these pure strategies I know the play for every cell in the normal form game matrix, so I can calculate payoff values coresponding to these cells: for every cell in the normal form game matrix we calculate the payoff for Ollie and Stan. The algorithm for calculating the (i,j)-th element of the final normal form game matrix is as follows: First we construct two loops with which we loop through all the rows and all the columns, so that we get to (i,j)-th element of the final matrix. At this point Ollie is using strategy i and Stan strategy j in the game matrix. Then we look at the payoff for each player for (i,j)-th strategies relative to the cards they were delt (we go through every combination (9) of cards nature could have delt). We multiply each payoff by the probability that nature picked those particular cards (which is always 1/9) and sum together all of the payoffs that arise for different card combinations. This is the payoff that goes in each cell. We do this for Ollie and for Stan. The example can be seen on the above link.
Now I got the normal form game. So I continue with eliminating dominant strategies. First I try this by searching for saddle points with minimax method (I can do this because this is a zero-sum game) but I get strange saddle points (they are all in one column and there are too few to get 9 pure strategies for Ollie and 7 for Stan if I eliminate those strategies that don't have a saddle point). The example can be seen on the above link.
The second way I try to eliminate dominant strategies is by iterated elimination of strictly dominated strategies (if I include weakly dominated strategies I get a single cell for the end result - which is one of the saddle points found with the minimax method). The way I do this is: we go through every row and compare it with every other row. We compare the first values in each cell of the row with the first value from the coresponding cell of the second row. If we find that every value in the first row is bigger than the value in the second row, we declare the strategy in the second row strictly dominated and delete that row. After deletion we move on to the columns (we forget about comparing rows further in this round). We look at columns and repeat the previous comparison, this time with columns and second values in each cell. This constitutes one round. If there were any strategies that were eliminated, we repeat the whole process in round 2 and so on until in the final round when we can't eliminate any more strategies. That is then the matrix with strictly dominated strategies removed. The problem here is, that there remains 42 pure strategies for Ollie and 7 for Stan. That is way too much for Ollie as it should be only 9.
What am I doing wrong? Calculating the payoffs wrong? Eliminating the strategies wrong (does the order of elimination matter? - as far as I know it does not in zero-sum games)? I've been at this for quite some time now and I can't seem to figure it out. Any help would be appreciated.
