Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

While working on a hobby project I encountered a difficult math problem. Or at least, difficult for me. Here is the problem:

Given an $a > 0$, find all pairs of a value $λ \in [0,1]$ and a function $f \colon [0,1] \to [0,1]$ such that $z$ is minimal.

$ b(v) = \int_0^v f(x)\ \mathrm{d}x \\ z=\int_0^1{ \max \left( \begin{array}{l} (1 + 2a)λ, \\ (2 + 2a)x - λ, \\ 2 a b(x) + 1, \\ (2 + 2a)x + b(1) - 2b(x) \\ \end{array} \right) } \mathrm{d}x $

That is the complete problem, but a partial solution would already help me a lot, for example:

  • A solution only for certain values of $a$
  • Finding values of $z$ without knowing $λ$ and $f$
  • Only one pair $(λ, f)$ for an $a$ instead of all the pairs
  • Are there even multiple pairs for one $a$? (considering different $f$'s that yield the same $b$ as equal)
  • Is it possible that all values of $a$ have at least one pair in which the $f$ has $\{0, 1\}$ as its range?

I'll give you some info on what this formula is about. The goal of the project I'm working on is to have a better understanding of poker by finding Nash equilibria of very simplified versions of poker. The game I'm now trying to find equilibria for is a two player game that goes as follows: In the beginning both players are required to bet a certain amount, the ante, variable $a$ in the formula. Both players get a 'card', which is a uniformly distributed number between 0 and 1. Then the one and only betting round follows. Both players have only one coin with a value of 1 that they can use. Player 1 starts. There are five different ways the betting round can go:

  • Check > Check
  • Check > Bet > Fold
  • Check > Bet > Call
  • Bet > Fold
  • Bet > Call

After the betting round the payout is done. If the betting round ends with check or call, there will be checked who of the players has the highest card. The winner will get the ante, or the ante plus one if a bet followed by a call occurred. The goal for each player is to have as much expected profit as possible.

When player 1 uses the best response to the strategy of player 2, the expected value of the game will be $z - 1 - a$. A positive value indicates profit for player 1, a negative value profit for player 2. If player 1 checks, then player 2 will check with probability $f(c)$ and bet otherwise, where $c$ is the card player 2 has. If player 1 bets, then player 2 will call if his card is at least $λ$.

If I have the solution to this problem and didn't make any mistakes in making the formula, then I have the optimal strategy for player 2 and the expected value in the Nash equilibrium. And then I only have to do something similar for player 1.

Any ideas on minimizing $z$?

share|improve this question
    
When I have time, I may turn this comment into an answer. This game and many related $0-1$ games were studied by Bill Chen and Jerrod Ankenman, with many results posted to the newsgroup rec.gambling.poker in 2003, and some examples written up in their book The Mathematics of Poker, not to be confused with my book The Math of Hold'em which does not contain analyses of $0-1$ games. Chen and Ankenman solved more complicated games than this one, but you may want to start with the simpler example in which only one player may bet. –  Douglas Zare Jun 18 '12 at 14:42
    
Also, the first money into the pot after the ante should be called a bet not a raise, and the formulas you get are a bit simpler if you assume that the winner of a showdown is the player with the lower number, not the higher number. –  Douglas Zare Jun 18 '12 at 14:43
add comment

1 Answer

up vote 5 down vote accepted

$0-1$ poker games have been studied by Borel, Von Neumann and Morgenstern, and others. The most detailed treatment I know is by Bill Chen and Jerod Ankenman, who wrote a series of posts in rec.gambling.poker in 2003, "The [0,1] game: Part 1-14." Some of this was included in their 2006 book, The Mathematics of Poker.

The game you mention is "[0,1] Game #9" on pages 198-203.

Before going into the solution, note that it is a common misconception that mixed strategies are ubiquitous. In fact, for games with finitely many options, mixed strategies are typically required for finitely many boundary cases. In a game with finitely many states like rock-paper-scissors that may be everything, but in a game like this with no atoms in the distribution of cards, mixed strategies are not required at all. Because of the hidden information, when you bet, your opponent still will not know whether you are betting for value (with a strong hand which is ahead on average when called) or with a bluffing hand (which is behind your entire calling range). At the Nash equilibrium, you may be indifferent between betting or checking with a range of hands, when checking will never win and betting as a bluff gives the same value as giving up. So, instead of choosing a function which gives you a probability of betting when dealt that card, you might as well partition the possibilities into sets for each action.

The following excerpts show the Nash equilibrium:


X's strategy consists of the following thresholds:

  • $x_0$ between check-folding and bluffing.
  • $x_1^*$ between check-folding and check-calling.
  • $x_1$ between value betting and check-calling.

Y's strategy likewise consists of three thresholds:

  • $y_0$ between checking and bluffing if X checks.
  • $y_1^*$ between calling X's bet and folding to X's bet (if X bets)
  • $y_1$ between value-betting and checking if $X$ checks.

...

$0 \lt x_1 \lt y_1 \lt x_1^*, y_1^* \lt y_0 \lt x_0 \lt 1$

[This follows the convention that lower cards are stronger, and corrects a typo.]

...

Solution:

$y_1 = (1-\alpha)/(1+\alpha)$

$ x_1 = (1-\alpha)^2/(1+\alpha)$

$y_0 = (1+\alpha^2)/(1+\alpha)$

$x_0 = 1 - \alpha(1-\alpha)^2/(1+\alpha)$

$y_1^* = 1 - \alpha$

$x_1^*= 1-\alpha$


where $\alpha$ is the probability with which you fold a bluff-catcher with a bet of that size relative to the pot to make someone indifferent to bluffing. Since you have a bet of $1$ into a pot of size $2a$, $\alpha = 2a / (1+2a)$.

share|improve this answer
    
Allright, thanks. It looks like I've been taking the hard road with minimizing an integral. –  Paul Jun 19 '12 at 2:30
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.