Last, more interesting game theory problem

[Magic_Man]

A private investing company recently held a programming/psychology/game theory contest at our school. I'll link to the full text at the bottom of this message, but in brief, the problem is as follows:

Consider a variaton in tic-tac-toe. Each of the 2 players will start with $100. In round 1, each player submits silent bids for the squares. Whoever bidds higher on a square pays the amount of their bid and owns the square. In a tie, the square remains unowned. In each round the players bid again for the unowned squares, and so on until either all the squares are won or if the board remains the same for 3 rounds. At that time, whoever has more 3-in-a-rows (including diagonals) wins. You can only make integer bids.

The first thing I notice is that if you win any diagonal, you automatically win. However, it seems to me there is no dominant strategy. How would I begin to select an opening strategy for this game?

full text:www.ellington.com/challenge/ (http://www.ellington.com/challenge/)

~MagicMan

[Utah]

I think the challenge is a bit silly given the parameters. Game theory is incredibly difficult here (although I would use it to model likely opponent scenarios). Sadly, given the parameters you cannot exploit the play of other players because you have no information about them. It would be a far more interesting problem if you had to play the same player 20 times or if your program could learn the results of each battle against all opponents to know if it was winning or losing.

My loose thoughts on round 1:
a) you need to spend all your money. Holding anything back is a mistake
b) you need to protect against the most obvious opponent strategy, which is grabbing a game ending diagonal.

I think I would start with:

6 1 6
5 71 6
2 1 2

You have an excellent block against the diagonal and you give yourself a heck of a lot of options. You worry about a diagonal play of your opponent of 7, 80, 7 or such. However, you have to give something up. I would possibly go even lower on the corners. It seems to me that you either go for them or you dont. However, I like 6 because it is just above the obvious pricepoint 5.

I don't like this problem unless I am missing something in the rules.

[Magic_Man]

You articulated well many of my thoughts. I was excited about the problem at first, but after thinking about it for a long time, I decided not to submit a solution. Unfortunately I missed the awards ceremony, so I don't know what the winning strategy actually was. One of my problem was with the round 2 wagers. There were just too many situations to account for, and it seemed like a tedious programming problem.

I thought about going about this like an all-in preflop problem; that is, try to put my opponents on a "range," and find the best strategy against that range. For example, one of the most common strategies is probably:

Y 0 Y
0 X 0
Y 0 Y

Where X is some sufficiently large number, probably 50+. There is a similar strategy that puts X in the middle and Y on the four edges, sort of the counterattack against the 4 corners strategy. And of course the range would include some opening bids involving all 9 squares also, perhaps one gaussian distribution for the corners, and another for the edges. My plan was to make a complete list of these most-likely strategies, then find the best winning strategy against the set. All in all it seemed like a tedious problem, and other graduate work got in the way. Alas.

~MagicMan

[Utah]

I like this:

1,1,31
1,1,13
3,8,41

You are strong against diagonal strategy. if pure diag. strat. down 1,1,41 you win unless they play greater than 41 in lower right, which is highly unlikely because a hard diag. strat. with a 42+ in lower right is suicide. If they go diag in other direction then you are in bad shape, but you may catch a break with an opponent 30,40,30

You are strong against an X strategy as you take the far right column and put a blocker in the second column. Thus, you get a tie and maybe a win if you get lucky in the first.

You are okay against a + strategy because an opponent using it must protect the center or they are in ruins. Hopefully, your 13 is enough to take the space and your 3 on the corner blocks giving you a tie.

You get killed by an even distribution strategy, but I have a very hard time seeing opponents playing it because such a strategy does not protect the diagonal and it thus a loser.