Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

game tree

(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.

share|improve this question
1  
Note that Ollie only has $3^3=27$ truly distinct pure strategies instead of $4^3=64$, since if he decides to raise he will never play a second round. –  Generic Human Jun 25 '12 at 14:38
    
Yes, that is true I think, but the problem should be solvable even if I don't take this into accound, right? –  Rok Dominko Jun 28 '12 at 2:26
    
Yes, should be solvable even in this case, but you must remove strategy with the same payoff. For example "RC,RC,RC" dominates "RC,RC,RD" (and the opposite too), because you can always play the one of them instead of the other and get a greater or equal pay-off. Note that you can have some rounding errors in the code that lead to a fail of equality check, I suggest multiplying each payoff by 9, so you can work with integer. –  carlop Dec 3 '12 at 8:23
add comment

1 Answer

Stan's 8 pure strategies consist of an action (stay or raise) for each of the 3 cards. One of them is raise on H, stay on M or L. One of Ollie's is raise on all cards. In the cell of the matrix at the intersection of these goes the average payoff if both players follow this strategy. So you go over the 9 possible distributions of cards, calculate the payoff to Stan, average them, and put it in the matrix.

For c, you look for a pair of Stan's strategies where Stan comes out better regardless of what Ollie does. You are told that there will be exactly one pair. You can then eliminate the poorer strategy from the matrix. You are also told that you will be able to eliminate 55 of Ollie's strategies. For d, you note that the remaining strategies for Ollie all satisfy this.

share|improve this answer
    
Hi and thank you for your answer, but I am still having problems. At the begining you are writing about entering a value in the cell where Stan's and Stan's (not Ollie's) strategies intersect. I assume this is a typo. The answer for c is where I really get lost. Actually what I get told is, that I can eliminate only one strategy that is dominated, not one pair. I have written an online script for calculating every aspect of this game. I will go into it more in the EDIT part of the question abowe, because I don't have enough room here. –  Rok Dominko Jun 28 '12 at 1:43
    
@RokDominko: you are right, I fixed Ollie's name in the first sentence. From your edit, it sounds to me you are doing things right. –  Ross Millikan Jun 28 '12 at 4:03
    
What about the answer to c? I dont understand what you meant by this. –  Rok Dominko Jun 28 '12 at 13:11
    
@RokDominko: you have the right approach in your edit. If Stan's strategies are across the top of your matrix, look for a column where each cell is greater than or equal to some other column. The one that is less can be eliminated. I didn't do the problem, so can't say why you don't find as many dominated ones as they do. –  Ross Millikan Jun 28 '12 at 13:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.