Auction-based Tic Tac Toe: Solution

reshefmoshepayne

Reshef, Moshe and Sam

poorman

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:

pollttt

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

propp

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 gamesElectron. J. Combin. 17 (2010).

See also

Jay Bhat and Sam Payne, Bidding chessMath. 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.

About these ads
This entry was posted in Games, Test your intuition and tagged . Bookmark the permalink.

6 Responses to Auction-based Tic Tac Toe: Solution

  1. James Propp says:

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

  2. Gil Kalai says:

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

  3. Reshef says:

    It 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 Kalai says:

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s