Bidding Tic Tac Toe

Question

In regular tic tac toe, both the players get alternate chances. This is a variant of that.

Player $A$ has $\$x$ amount and player $B$ has $\$y$ amount as initial balance. Assume that $y>x$.

Both the players bid some amount from the available amount to them. whichever bids higher will get the turn to put a mark on the board and the winner for that bid has to subtract the bidding amount from his/her available balance.

Player $A$ does not know the bidding amount of player $B$ and vice versa but a referee is there who will announce the remaining balance amount of each player after each move. Both the players know initial amount of each other.

Bidding can be done in fractions also.

For example:

Player $A$ is having $\$100$ and player $B$ is having $\$300.99$.

Player $A$ bids $\$40$ and player $B$ bids $\$100.33$. Player $B$ wins and puts a mark on the board. Player $A$ is left with $\$100$ and player $B$ is left with $\$200.66$ after this move.

Both the players are playing the same bidding amount in next two rounds and ultimately player $B$ wins.

The question: It is clear that if Player $B$ has $y>3x$ amount then he/she can surely win. What is the minimum amount of player $B$ (minimum $y$) such that he/she can develop a strategy where he/she always wins. Can we model this problem to any knows techniques of optimization?

I have tried the problem and pulled down the ratio of $y:x$ from $3 + \epsilon:1$ to $\frac{33}{28} + \epsilon :1$.

I don't know under which tag should I ask this questions so I am putting multiple tags.

Edit: If both the players tie in bidding then they re-bid until they come up with different bidding amounts. Ans since bidding amount is a real number, it is unlikely that will bid same amount in consecutive moves.

Answer 1

The paper by Develin and Payne referenced in the comments gives a very thorough treatment of this type of game, and in particular addresses the complicated nuances of breaking ties that arise during the bidding. However, in the Richman games they treat, the winning bid is given to the other player... this problem is slightly different. Glossing over the nuances of tied bids, we can see the following. (Assume that $B$ has one unit to bid with, and that both players will bid and play optimally.)

• Every game state $G$ has a critical ratio $x(G)$ such that player $A$ can win if he has more than $x(G)$ to bid, and cannot win if he has less than $x(G)$ to bid.
• A game state that is already won by player $A$ has $x(G)=0$; a game state already drawn or lost by player $A$ has $x(G)=\infty$.
• Player $A$ can win with $x$ to bid when he has a winning bid, i.e., an amount $0 \le y \le x$ such that player $B$ loses if he bids more than $y$ (because $x(G_B) \le x/(1-y)$ for any state $G_B$ that player $B$ can move to; this applies only for $y<1$), and also loses if he bids less than $y$ (because $x(G_A) \le x - y$ for some state $G_A$ that player $A$ can move to).

We see two constraints on a winning bid for player $A$. First, $y \le x - x(G_A)$ for some state $G_A$ that player $A$ can move to; i.e., $y \le x - \min_{G_A} x(G_A)$. Second, either $y \ge 1$ (so player $B$ can't outbid it), or else $y\ge 1 - x / x(G_B)$ for all states $G_B$ that player $B$ can move to; i.e., $y \ge 1 - x / \max_{G_B} x(G_B)$. The latter constraint is never stronger than the former, so we have: $$ 1-x/\max_{G_B}x(G_B) \le y \le x-\min_{G_A}x(G_A). $$ This interval of winning bids shrinks as $x$ decreases, and vanishes (by definition) when $x=x(G)$. So setting the two endpoints equal to one another lets us solve for $x(G)$: $$ 1-x(G)/\max_{G_B}x(G_B) = x(G)-\min_{G_A}x(G_A) \implies x(G)=\frac{1+\min_{G_A}x(G_A)}{1+1/\max_{G_B}x(G_B)}. $$

At this point we can calculate. I'm pasting Python code to evaluate this recursion below. The result that I get for Tic-Tac-Toe is $x(G_0)\approx 1.018375$. I have modified the code to give an exact (rational) result (code not shown here, as it's not worth the extra space): it is $$x(G_0)=\frac{396925}{389763}=1+\frac{7162}{389763}.$$

g0 = '---|---|---'
NO = '-'
DRAW = 'x'

def legalMoves(g, player):
  ret = []
  for i in xrange(0, len(g)):
    if g[i]==NO: ret.append(g[:i] + player + g[(i+1):])
  return ret

def winner(g):
  for i in xrange(3):
    if g[i]==g[i+4] and g[i+4]==g[i+8] and g[i]!=NO: return g[i]
    if g[4*i]==g[4*i+1] and g[4*i+1]==g[4*i+2] and g[4*i]!=NO: return g[4*i]
  if g[0]==g[5] and g[5]==g[10] and g[0]!=NO: return g[0]
  if g[2]==g[5] and g[5]==g[8] and g[2]!=NO: return g[2]
  if NO in g: return NO
  return DRAW

def value(g, infty=10**12, cache={}):
  if cache.has_key(g): return cache[g]
  w = winner(g)
  if w == NO:
    amin = min(map(lambda(gg):value(gg, infty, cache), legalMoves(g, 'A')))
    bmax = max(map(lambda(gg):value(gg, infty, cache), legalMoves(g, 'B')))
    val = (1.0 + amin) / (1.0 + 1.0 / bmax)
  elif w=='A': val = 0
  else: val = infty
  cache[g] = val
  return val