Liar's Poker: a tricky problem, part 3
I've been working off and on to find the optimal strategy for the final round of a game of liar's poker. I've gotten a bit farther on it, and it now looks solveable. I've now solved the 12-card deck version (i.e. if the deck only contains aces, kings, and queens), and I suspect I've got an algorithm that will solve the whole problem in a reasonable amount of time.
I have already shown that if player 1 makes a bid that involves 2 cards, player 2 should always call BS. Consequently, if player 1 bids a pair, the only time he wins is when player 2's card is the same as player 1's. This occurs with probability 3/(n-1) (where n is the number of cards in the deck). If player 1 bids a high card with a kicker, he needs to find player 2 with the other of the two cards (player 1 should have one of those cards as well). Therefore, player 1 will win 4/(n-1) of the time in this case. Consequently, if you ever consider bidding a pair, you should change that to a high card with a kicker. Moreover, any high card and kicker bid is as likely as any other (assuming player 1 has one of those cards). Consequently, player 1 only needs to consider a few different bids: any of the "high card" bids (r different bids here, 1 for each of the r ranks in the deck), and some "high card and kicker" bid (they're all equivalent, so we can lump them all into one big group).
It's always a bad idea to bid the lowest rank as a high card: player 2 will always call BS and always win. If either of you have a higher card, your bid is not there and you lose, and if neither of you have a higher card, you've got a pair, and again you'll lose. Moreover, it's never a good idea to bid the second-lowest rank as a high card: that bid implies that the other card is a lower rank, so you might as well bid it as a kicker (that is to say, "3 high" implies "3 high with a 2 kicker"), and that two-card bid gives your opponent no choice in the matter, which can't hurt and might help (depending on whether that's an important choice for your opponent or not).
Therefore, there are r-1 possible bids to consider: "r high," "r-1 high," etc down to the third-lowest rank, and some high card with some kicker (where you have one of those two cards).
Last post, I suggested making a graph of planar regions in the objective function, and finding the largest connected component with no outbound edges. Unfortunately, it looks like that will always be the entire graph. However, there's a small problem here: if two nodes both have edges connecting to the other, both are sloping towards each other and the best solution in that local area is on the boundary between the two regions. This location is really in both regions, so you don't need to include both regions when finding the global optimum (including one of those regions is enough, since you'll still find the right optimum through linear programming). Therefore, the connected component we're really looking for is the largest one that, for every outbound edge, has a corresponding inbound edge as well (that is, if A is in the component and B is not, the edge (A,B) only exists if (B,A) does too). Using this notion, I managed to solve the 12-card deck by making the graph and finding the connected component.
The solution for the 12-card deck is as follows: if you are dealt an ace, bid "ace high." If you're not dealt an ace, 4/7 of the time bid "ace high" anyway, and 3/7 of the time bid "king high with a queen kicker." This allows you to win 16/33 of your games. This was the solution at the intersection of the regions in the connected component. However, one of those regions' derivatives was 0 with respect to a couple variables, and there is an entire subregion which will yield optimal results. Let x be the probability of bidding "ace high" given a King, and y be the probability of bidding "ace high" given a Queen. You will win 16/33 of your games with the following strategy
I've also come up with what I hope is an algorithm to find the optimal answer in larger decks reasonably quickly: a gradient descent-like system over the space of linear programming problems! Pick a region in the objective function, and solve the linear programming problem within that planar region (making the boundaries of the region constraints in the LP). The solution to this sub-problem will lie on the border of the current planar region and X others (for some integer X>=0). If X=0, this is the global optimum. Otherwise, for every neighboring region, solve its linear programming problem, choose the one whose solution has the best value of the objective function, and repeat until you can't find a better solution (in which case you've found the best one). Cache these solutions so you don't have to solve the same planar region more than once.
Each LP can be solved in polynomial time. Although there are an exponential number of planar regions, this gradient descent system will allow us to skip most of the regions. I have not yet proven that we only need to consider a polynomial number of regions, but the few examples I've looked at so far seem to require only looking at a few regions. I suspect I can make some sort of argument based on the convexity of the objective function and the convexity of each planar region to prove that you only need to consider a polynomial number of regions.
At this point, I've started coding up this algorithm, and I have high hopes that it will solve this problem in the full-sized deck in a reasonable amount of time.
I have already shown that if player 1 makes a bid that involves 2 cards, player 2 should always call BS. Consequently, if player 1 bids a pair, the only time he wins is when player 2's card is the same as player 1's. This occurs with probability 3/(n-1) (where n is the number of cards in the deck). If player 1 bids a high card with a kicker, he needs to find player 2 with the other of the two cards (player 1 should have one of those cards as well). Therefore, player 1 will win 4/(n-1) of the time in this case. Consequently, if you ever consider bidding a pair, you should change that to a high card with a kicker. Moreover, any high card and kicker bid is as likely as any other (assuming player 1 has one of those cards). Consequently, player 1 only needs to consider a few different bids: any of the "high card" bids (r different bids here, 1 for each of the r ranks in the deck), and some "high card and kicker" bid (they're all equivalent, so we can lump them all into one big group).
It's always a bad idea to bid the lowest rank as a high card: player 2 will always call BS and always win. If either of you have a higher card, your bid is not there and you lose, and if neither of you have a higher card, you've got a pair, and again you'll lose. Moreover, it's never a good idea to bid the second-lowest rank as a high card: that bid implies that the other card is a lower rank, so you might as well bid it as a kicker (that is to say, "3 high" implies "3 high with a 2 kicker"), and that two-card bid gives your opponent no choice in the matter, which can't hurt and might help (depending on whether that's an important choice for your opponent or not).
Therefore, there are r-1 possible bids to consider: "r high," "r-1 high," etc down to the third-lowest rank, and some high card with some kicker (where you have one of those two cards).
Last post, I suggested making a graph of planar regions in the objective function, and finding the largest connected component with no outbound edges. Unfortunately, it looks like that will always be the entire graph. However, there's a small problem here: if two nodes both have edges connecting to the other, both are sloping towards each other and the best solution in that local area is on the boundary between the two regions. This location is really in both regions, so you don't need to include both regions when finding the global optimum (including one of those regions is enough, since you'll still find the right optimum through linear programming). Therefore, the connected component we're really looking for is the largest one that, for every outbound edge, has a corresponding inbound edge as well (that is, if A is in the component and B is not, the edge (A,B) only exists if (B,A) does too). Using this notion, I managed to solve the 12-card deck by making the graph and finding the connected component.
The solution for the 12-card deck is as follows: if you are dealt an ace, bid "ace high." If you're not dealt an ace, 4/7 of the time bid "ace high" anyway, and 3/7 of the time bid "king high with a queen kicker." This allows you to win 16/33 of your games. This was the solution at the intersection of the regions in the connected component. However, one of those regions' derivatives was 0 with respect to a couple variables, and there is an entire subregion which will yield optimal results. Let x be the probability of bidding "ace high" given a King, and y be the probability of bidding "ace high" given a Queen. You will win 16/33 of your games with the following strategy
- If you have an ace, bid "ace high."
- If you have a king, bid "ace high" with probability x, and bid some high card with some kicker (one of which is a king) the rest of the time.
- If you have a queen, bid "ace high" with probability y, and bid some high card with a queen kicker the rest of the time.
- x <= 3/4
- y <= 3/4
- 3x + 4y >= 4
- 4x + 3y >= 4
I've also come up with what I hope is an algorithm to find the optimal answer in larger decks reasonably quickly: a gradient descent-like system over the space of linear programming problems! Pick a region in the objective function, and solve the linear programming problem within that planar region (making the boundaries of the region constraints in the LP). The solution to this sub-problem will lie on the border of the current planar region and X others (for some integer X>=0). If X=0, this is the global optimum. Otherwise, for every neighboring region, solve its linear programming problem, choose the one whose solution has the best value of the objective function, and repeat until you can't find a better solution (in which case you've found the best one). Cache these solutions so you don't have to solve the same planar region more than once.
Each LP can be solved in polynomial time. Although there are an exponential number of planar regions, this gradient descent system will allow us to skip most of the regions. I have not yet proven that we only need to consider a polynomial number of regions, but the few examples I've looked at so far seem to require only looking at a few regions. I suspect I can make some sort of argument based on the convexity of the objective function and the convexity of each planar region to prove that you only need to consider a polynomial number of regions.
At this point, I've started coding up this algorithm, and I have high hopes that it will solve this problem in the full-sized deck in a reasonable amount of time.