Reshef, Moshe and Sam
(based on discussions with Reshef Meir, Moshe Tennenholtz, and Sam Payne)
Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking the empty squares in a 3 by 3 board – each player has a strategy that can guarantee a draw. Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.
What would you expect the minimal value of Y is so the X player has a winning strategy?
If the X player has more than this amount he can guarantee winning the game. If he has less than that the O player can guarantee that X does not win. The first commentator to answer correctly was Mohammad.
I myself did not get it right when I asked the question and thought the answer is around 104. (Because of the calculation mistake, the answers to the poll did not distinguish the correct answer from the incorrect intuition that any amount above 100 is enough for X to win.)
I found the answer (even the initial incorrect one) surprisingly low!
How to go about it
The picture on the top is the tree of the game of tic-tac-toe taken from the paper of Mike Develin and Sam Payne (the same simplifications that Mike and Sam aoolies apply to the tree apply in our case as well,) and where we computed the minimum ration of budgets required for X to win. Develin and Payne made the computation for the Richman game (where the players pays to each other for making the move,) and we just carried the computation to the version above (called Poorman game).
A very important reference with many beautiful (and at times humorous) concepts, questions, and results is:
A recent beautiful paper is:
Mike Develin and Sam Payne, Discrete bidding games, Electron. J. Combin. 17 (2010).
Jay Bhat and Sam Payne, Bidding chess, Math. Intelligencer 31 (2009), 37–39.
Sam Payne, Elina Robeva, Artificial intelligence for Bidding Hex.
For a study of turned based games, and Hex in particular, see
Richman game, Poorman game, and Spinner (random-turn) game
The paper by Lazarus, Loeb, Propp, Stromquist, and Ullman considers three types of games. The first called the “Richman game” (after Richman who first wrote about it), is an auction-based game where the players pay each others for the right to make the next turn. In this case, the amount of money they have together remains constant. The second version is the one we considered in our question and then the players pay for making the next move to a third party. Lazarus et al. called this version the “Poorman game.” A random-turn game, where in each round the player to play is decided by a coin toss, is referred in the paper as a “spinner game.”
Two Remarkable equivalences
Let me mention two remarkable equivalences:
Equivalence 1 (from Lazarus et al.): The fraction from the total budget needed for a player to win in Richman game is precisely the probability that the other player is winning in the Spinner (random-turn) game.
Equivalence 2 (from Peres et al.): For board games like HEX, the probability for one player winning in the spinner game is precisely the probability of winning when the board is filled at random.