Auction-based Tic Tac Toe: Solution


Originally posted on Combinatorics and more:

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.

View original 507 more words

About these ads

Leave a Reply

Please log in using one of these methods to post your comment:

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