Reshef, Moshe and Sam

## The question:

### (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?

We asked this question in our test your intuition series (#17) in this post. Here is a recent new nice version of tic-tac-toe.

## The poll:

## The answer:

### 101.84

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

## Related papers

James Propp

A very important reference with many beautiful (and at times humorous) concepts, questions, and results is:

A. Lazarus, D. Loeb, J. Propp, W. Stromquist, and D. Ullman, Combinatorial

games under auction play, Games Econom. Behav. 27 (1999), 229-264

A recent beautiful paper is:

Mike Develin and Sam Payne, Discrete bidding games, *Electron. J. Combin. *17 (2010).

See also

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

Y. Peres, O. Schramm, S. Sheffield, and D. Wilson, Random-turn hex and

other selection games, Amer. Math. Monthly 114 (2007), no. 5, 373{387

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

James ProppHi Gil. Nice article! One slight correction: David Richman never actually wrote about his idea (as far as I know). He communicated it to me orally at a conference we both attended back in the 80s, but he died before he could publish anything.

Gil KalaiPost authorDear James, thanks for the comment! indeed it is a fascinating direction with mysterious connections. The decisive advantage from a slight budget edge is something that we still don’t understand. San Payne told me that he was playing auction-based chess as a graduate student so it is interesting to where the origins of such variation could be traced.

ReshefIt should be noted that what makes the result of Lazarus et al. remarkable, is that it also applies to games that contain cycles (i.e. not in a tree form). In such games it is not a-priori clear why there is a well-defined winning probability at all.

Gil KalaiPost authorDear Reshef, this is an excellent point. In fact, I don’t know if the second equivalence between random-turn game and random assignment extends to more general frameworks.

Pingback: Bi-weekly links for July 15 | God plays dice

lkafleReblogged this on lava kafle kathmandu nepal <a href="https://plus.google.com/102726194262702292606" rel="publisher">Google+</a>.