(A few more quantum posts are coming. But let’s have a quick break for games.)

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.

For example, if, to start with, the X player have 120 dollars, and if for the first move X bids 40 dollars and O bids 30 dollars, then X will make the first move and will be left with 80 dollars while O will be left with his 100 dollars.

What would you expect the minimal value of Y is so the X player has a winning strategy? Of course if Y>300, X can make 3 uninterrupted moves and win, but perhaps much less is enough?

(Thanks to Reshef Meir and Moshe Tennenholtz)

Update: Another variant of this game is when the player winning the turn pays his bid to the other player. (This version is called “Richman game,” while the variant above is called “Poorman game”. In this case if Y> 800 the X player can play three moves and win. And again the question is what is the infimum value of Y for which the X player can force a win…

If the bids are made simultaneously, we might have to consider mixed strategies. By “winning strategy”, do you mean a strategy that wins with probability 1? There might be other interesting thresholds: when does X have a strategy that wins with positive probability? When does X have a strategy that wins with positive probability and loses with probability 0?

Then the term “winning strategy” makes no sense anymore, because you made the game nondeterministic.

Anonymous Rex

Re tom (@goiken): Gil’s response to James indicates that the condition is “winning with certainty”. In terms of the coin flip, this means you must win regardless of how the coin flips.

If you’re okay with making the game assymetric, then an alternative interpretation is the following: before each move, X makes a bid. Since we’re in the worst case, we may as well assume O’s bid is the exact same amount. Again since we’re in the worst case, we may as well let O choose whose bid is successful.

In other words, X bids an amount, and O decides whether or not he or X will pay that amount for the privilege of moving. (If X bids more money than O has, then of course X moves.)

You can set the tie breaking any way you want, it does not change the infimum value of Y. For convenience you can assume that X plays in case of a tie, in which case the infimum becomes minimum.

Dear Phiippe, lets assume that X gets to see O’s bid, but as you said it is not important. Actually, I should have said infimum Y and not minimum Y in the post…

Interesting problem!
The second simplest bound (the first being 303, with the coin flipping rule and if they bid integers) seems to be 228 (and X should bet 25 or 26 the first time), since X can afford to give away the first move if he can move three times in a row after that.

Hi Gil, Doe player O know how much money player X has to start? I’m not sure if it’s relevant, but assuming yes, I think I can also show that X can win with $150+\epsilon.

If the currency is infinitely divisible, then I believe X can guarantee a win iff their ratio of money strictly exceeds 396925/389763. Multiplied by $100, this is around $101.84 (confirming Mohammad’s answer).

I haven’t fully automated my computation, so I may be fouling things up with transcription errors, but I am getting closer to 1.0169. As a point of reference, if we win the first two bids, my strategy suggests placing a bid of 7/15*$100 on the final bid.

My actual answer is 296273/1066185 + 527/1935 + 7/15 = 120467/118465, where essentially I am making every possible route through the game tree equally expensive, and so these would be the first three bids if we win all of them.

If the currency is divisible down to the dollar, (I believe) X wins with at least $104. If we correctly model US currency as divisible down to the cent, X wins with at least $101.86. In both cases, you only lose one unit of money due to the discretization!

I’d have to say the answer for the infimum is 12,600/121 or about 104.13 Not sure how others are guaranteeing a win for less. But I stand to be corrected.

It’s a hard to answer question because of vagueness. Mainly the fact that you don’t state that Y has to overbid X each time in order to win. Because if he doesn’t, the first move instantly becomes irrelevant. If you do (Or if you’re allowed to see their bid first), then it’s (Y+1), mainly because there’s no way you could lose if you have to bid higher.

There are a bunch of other vague rules I’m not sure on, but I’ll just leave that up to you. I am worn out, have been working on this for almost 1 hour now, and I still haven’t gotten very far without the aid of a simulation. Maybe later. Maybe.

Cool question! Reshef’s comment implies that we should not require bids to be integral, so let me assume we win ties. (If not, just bid epsilon higher.) I think a rough lower bound on the answer is that if your budget is less than (9/7)*100 = 128.57…, then there is an opponent against whom you do not win — in fact, you do not even make three moves.

To see this, suppose all possible games you’re playing end in at most “k” rounds. Suppose that you make at least three moves against every possibly strategy; so every possible strategy makes at most k-3 moves. Then for every subset of k-2 rounds, you bid at least $100 total (else some opponent matches your bids plus epsilon and wins all k-2 of them). The lowest-cost way to achieve this is to spend 100/(k-2) in each of the k rounds, so you have to spend at least k/(k-2)*100 total to guarantee that you make a move in 3 rounds out of k. The smallest this value can be is when k is maximal, and all tic-tac-toe games end in at most 9 rounds, so 9/(9-7) * 100 should be a lower bound.

I think by being somewhat vague about what constitutes a “strategy” you are enforcing stronger conditions than need exist. In particular, when you mention “every subset of k-2 rounds” it seems like you are assuming a fixed bid amount based on the number of moves alone. In particular, our response against a strategy that outbids us every turn as long as it can need not have anything to do with our response to a strategy that, say, only bids a nonzero amount when it would lose otherwise.

Thus your justification, that some opponent could bid in such a way as to block us out, doesn’t really apply. That will have to be true of our bids in the case that we keep losing, but needn’t be if we have already made a move. This is still a useful condition for finding a solution, but has narrower scope than you are suggesting.

For Richman Game, I’ve done the math. The maximum X player will need to beat O, while O has a starting fund of $100, is $707. Here’s each round, with both parties bids for said round

X $101 <—Round Winner, loses $101
O $100 <—Round loser, gains $101

X $202 <—Round Winner, loses $202
O $201 <—Rounder loser, gains $202

X $404 <—Game Victory, loses $404
O $403 <—Game lost, gains $404

JamesIf the bids are made simultaneously, we might have to consider mixed strategies. By “winning strategy”, do you mean a strategy that wins with probability 1? There might be other interesting thresholds: when does X have a strategy that wins with positive probability? When does X have a strategy that wins with positive probability and loses with probability 0?

Gil KalaiPost authorDear James, yes, by winning strategy I mean winning with certainty.

oriWhat happens if there are equal bids?

Gil KalaiPost authorDear Ori, lets assume that in this case we flip a coin on who will move.

tom (@goiken)Then the term “winning strategy” makes no sense anymore, because you made the game nondeterministic.

Anonymous RexRe tom (@goiken): Gil’s response to James indicates that the condition is “winning with certainty”. In terms of the coin flip, this means you must win regardless of how the coin flips.

If you’re okay with making the game assymetric, then an alternative interpretation is the following: before each move, X makes a bid. Since we’re in the worst case, we may as well assume O’s bid is the exact same amount. Again since we’re in the worst case, we may as well let O choose whose bid is successful.

In other words, X bids an amount, and O decides whether or not he or X will pay that amount for the privilege of moving. (If X bids more money than O has, then of course X moves.)

Reshef MeirYou can set the tie breaking any way you want, it does not change the infimum value of Y. For convenience you can assume that X plays in case of a tie, in which case the infimum becomes minimum.

phiippeDoes the X player get to see the O player’s bid after each round or only who has lost or won?

phiippenevermind! It’s worst case.

Gil KalaiPost authorDear Phiippe, lets assume that X gets to see O’s bid, but as you said it is not important. Actually, I should have said infimum Y and not minimum Y in the post…

BenoitInteresting problem!

The second simplest bound (the first being 303, with the coin flipping rule and if they bid integers) seems to be 228 (and X should bet 25 or 26 the first time), since X can afford to give away the first move if he can move three times in a row after that.

NGot a bound of 161, assuming they never make equal bids and the bids are integral.

NHi, I think now I have a solution that shows 150 suffices.

Mohammad~101.84 ?

Greg FriedmanHi Gil, Doe player O know how much money player X has to start? I’m not sure if it’s relevant, but assuming yes, I think I can also show that X can win with $150+\epsilon.

BorisIf the currency is infinitely divisible, then I believe X can guarantee a win iff their ratio of money strictly exceeds 396925/389763. Multiplied by $100, this is around $101.84 (confirming Mohammad’s answer).

BorisIn the Richman game, I get 133/123 * $100 ~ $108.13.

PeterI haven’t fully automated my computation, so I may be fouling things up with transcription errors, but I am getting closer to 1.0169. As a point of reference, if we win the first two bids, my strategy suggests placing a bid of 7/15*$100 on the final bid.

My actual answer is 296273/1066185 + 527/1935 + 7/15 = 120467/118465, where essentially I am making every possible route through the game tree equally expensive, and so these would be the first three bids if we win all of them.

BorisIf the currency is divisible down to the dollar, (I believe) X wins with at least $104. If we correctly model US currency as divisible down to the cent, X wins with at least $101.86. In both cases, you only lose one unit of money due to the discretization!

Boris(Err, TWO units of money.)

GuaraldiWith reasonable confidence I can say the answer for guaranteed victory is $136

LucianI’d have to say the answer for the infimum is 12,600/121 or about 104.13 Not sure how others are guaranteeing a win for less. But I stand to be corrected.

LucianMy previous calculation was off, I believe it is 15,050 / 121 or about 124.38

I’m curious to see how some people managed lower.

LucianNevermind, my other calculation was excluding a case, while 124.38 works it looks like it could be done for lower

Pingback: An Actuary plays Tic-Tac-Toe « Actuaries Rule

informatimagoIt seems to me the Y value to ensure three moves is not 300 but 101+202+404 = 707. Once you’ve paid the first move, the other player has 201.

LucianAccording to the example given, the winning bid doesn’t go to the other player, it is just spent.

David JoergIt is cruel to post a problem like this without the solution. I have things to do!

keithgIt’s a hard to answer question because of vagueness. Mainly the fact that you don’t state that Y has to overbid X each time in order to win. Because if he doesn’t, the first move instantly becomes irrelevant. If you do (Or if you’re allowed to see their bid first), then it’s (Y+1), mainly because there’s no way you could lose if you have to bid higher.

There are a bunch of other vague rules I’m not sure on, but I’ll just leave that up to you. I am worn out, have been working on this for almost 1 hour now, and I still haven’t gotten very far without the aid of a simulation. Maybe later. Maybe.

LucianBecause he’s looking for the infimum it doesn’t really matter and we can assume that one outbids the other by some small epsilon > 0 to make a win.

sp2hariNice question, do you know this question is available at https://www.hackerrank.com/challenges/biddingtictactoe. Programmers who want to try their intuition can give it a try ;)

bowaggonerCool question! Reshef’s comment implies that we should not require bids to be integral, so let me assume we win ties. (If not, just bid epsilon higher.) I think a rough lower bound on the answer is that if your budget is less than (9/7)*100 = 128.57…, then there is an opponent against whom you do not win — in fact, you do not even make three moves.

To see this, suppose all possible games you’re playing end in at most “k” rounds. Suppose that you make at least three moves against every possibly strategy; so every possible strategy makes at most k-3 moves. Then for every subset of k-2 rounds, you bid at least $100 total (else some opponent matches your bids plus epsilon and wins all k-2 of them). The lowest-cost way to achieve this is to spend 100/(k-2) in each of the k rounds, so you have to spend at least k/(k-2)*100 total to guarantee that you make a move in 3 rounds out of k. The smallest this value can be is when k is maximal, and all tic-tac-toe games end in at most 9 rounds, so 9/(9-7) * 100 should be a lower bound.

Am I misunderstanding anything?

bowaggoner(That line should of course be 9/(9-2) * 100.)

PeterI think by being somewhat vague about what constitutes a “strategy” you are enforcing stronger conditions than need exist. In particular, when you mention “every subset of k-2 rounds” it seems like you are assuming a fixed bid amount based on the number of moves alone. In particular, our response against a strategy that outbids us every turn as long as it can need not have anything to do with our response to a strategy that, say, only bids a nonzero amount when it would lose otherwise.

Thus your justification, that some opponent could bid in such a way as to block us out, doesn’t really apply. That will have to be true of our bids in the case that we keep losing, but needn’t be if we have already made a move. This is still a useful condition for finding a solution, but has narrower scope than you are suggesting.

LJ133. Any less and O can at the very least force a draw

LJbut that is under the premise that when it is a draw, both parties pays the sum, but neither makes a move.

Pingback: Test Your Intuition (21): Auctions | Combinatorics and more

Deaths HeirFor Richman Game, I’ve done the math. The maximum X player will need to beat O, while O has a starting fund of $100, is $707. Here’s each round, with both parties bids for said round

X $101 <—Round Winner, loses $101

O $100 <—Round loser, gains $101

X $202 <—Round Winner, loses $202

O $201 <—Rounder loser, gains $202

X $404 <—Game Victory, loses $404

O $403 <—Game lost, gains $404

Total of X's money spent to win the game: $707

Deaths Heirand that’s a guaranteed victory, with O not being able to make a single move.

Pingback: Auction-based Tic Tac Toe: Solution | Combinatorics and more