Tic-Tac-Toyola is a variation of Tic-Tac-Toe with money. Instead of naughts and crosses (0s and Xs for Americans) being placed at the whim of alternating players, players vie for placement control at each turn by bidding some amount in a currency from an account under their control. The high bid decides the placement, with that bid amount being deducted from the corresponding player's account. Bids are in continuous units, so we can neglect the possibility of tie bids as unlikely.

There are two players: C(rosser) and N(aughty). X is placed first, and player C is declared winner if 3 Xs appear in a row before 3 Os appear in a row. If neither player achieves three in a row, N is declared winner. Thus, a game of Tic-Tac-Toyola will always have a winner.

C and N have been playing for some time and have reached the position:

(1) Assuming players are following optimal strategies, show that the outcome is independent of whether bidding is conducted secretly (by sealed bids) or openly (with players offered at each turn the possibility to outbid their opponent).

(2) Show that a player who is following an optimal strategy would not change his bid if he were to learn his opponent's account balance.

(3) Show that N can force a win if and only if he has in excess of twice as much money as C.

Note: Anyone interested in learning more about the Tic-Tac-Toyola family of games is invited to visit http://www.diplom.org/Zine/S2007R/Mayer/tictactoyola.htm

Dej Mar,

Let's see if I follow you..

Let us assume that a tie bid is won by Crosser.

This is at odds with the problem text, but we needn't let that derail us from considering your argument..

To insure Crosser does not win, Naughty bids c+1, winning the bid, and places his naught in the bottom left corner.

i'm not sure what you mean by c+1, but two possibilities come to mind:  a) you assume that naughty knows crosser's account balance and bids slightly more than his entire holdings on the upcoming move,   or b) you assume that there is open bidding, and that naughty will keep outbidding crosser until he takes control of the upcoming move by a small increment.

Either interpretation is reasonable, and both lead to the same results. Crosser should bid his entire account on the upcoming move, and so crosser would win if he has more money than naughty..

To insure Naughty does not win automatically with a "cat" win in the next placement, Crosser must bid [n - (c+1)] with placement of his cross in either remaining corner.

Again, I don't know what you mean by cat, but I will point out that crosser does not need to outbid naughty on the following turn in order to preserve his chances.

Assuming naughty's successful bid on the first turn put an X in a harmless square (one of the open edges), then crosser could also afford to allow naughty to outbid him on the next turn as well (presumably putting an O in the lower left hand corner to block the diagonal). Crosser could then still win by controlling all three of the remaining turns, thereby Xing out the remaining diagonal.

________________

Just to be sure there is no misunderstanding: you should take note that Xs and Os are placed alternately. Thus X is placed in the first turn regardless of which player has the highest bid.

In hindsight, it may have been better to state this explicitly in the problem text, instead of relying on the opening paragraph to suggest this important point.

Edited on April 27, 2008, 7:34 am

Posted by FrankM on 2008-04-27 07:22:14