Help with some game theory

[Magic_Man]

I've been checking out that www.moola.com (http://www.moola.com) website that a previous poster mentioned, and I really need to brush up on my game theory. Here's one of the games on the website, called "Goldrush:"

Both players start with 6 "gold nuggets", with values 1, 2, 3, 4, 5, and 6. 6 rounds are played, and on each round, another nugget is up for bid. All 6 values eventually appear for bidding, but they come up in random order. On each round, each player can bid one of their nuggets, and whoever bids higher wins all three nuggets (their bid, their opponent's bid, and the nugget up for grabs). If the bids are a tie, then the three nuggets stay in play, along with a new one for that round. After 6 rounds, whoever has more will win. There are 3*sum(1..6) = 3*21 = 63 points total, so whoever scores 32+ will win.

Example game:
Round 1: Nugget "2" is up for bid. PlayerA bids 1, PlayerB bids 2, PlayerB gets 5 points.

Round 2: Nugget "6" is up for bid. Both players bid 5, so it is a tie. Score is still 0-5.

Round 3: Nugget "1" is up for bid, along with 16 points from the last round. PlayerA bids 6, PlayerB bids 1, score is now 24-5.

Round 4: Nugget "4" is up, PlayerA bids 3, PlayerB bids 4, score is 24-16.

Round 5: Nugget "3" is up, PlayerA bids 2, PlayerB bids 3, score is 24-24.

Round 6: Nugget "5" is up, PlayerA bids 4, PlayerB bids 6, player B wins the game 24-39.


Does this game have a winning/nonexploitable strategy? Obviously it gets complicated once the scores are uneven, so I don't even know where to begin. It seems like in round 1, or whenever the positions are even (tie score, each player has the same nuggets left), there should be a strategy such that your opponent's EV = 0. If it was only one round, I think I could calculate some probabilities such that this was true, but the problem is you may give up some EV later by bidding too high in an early round.

Anyone know where to start?

~MagicMan

[Utah]

This is an insanely hard problem if you map out the entire tree. There are 216 possible positions after round 1 and 27,000 positions after round two and 1.7 million after round 3......

Theoretically, it can be solved. However, I dont know a computer that can calculate it. There may be some reduction methods that can solve it though. I havent thought hard but my intution says no.

btw - I did some checking on these large problems in the past and the max that the best tools commerically available today (eg., matlab) can calculate about a 1000x1000 sparse matrix (which this isnt).

Note: if you look at strategic options, there 36 in the first round and 150 in the second round. Thus, there are 5400 deployable strategies accounting for only the first 2 rounds.

[Magic_Man]

Suppose we play for one round only. My strategy will be to play nuggets 1-6 with probabilities a, b, ... f. The nugget up for bid is worth X. Then my opponent's EV, in point differential, is:

1: -(X+3)b - (X+4)c - (X+5)d - (X+6)e - (X+7)f
2: (X+3)a - (X+5)c - (X+6)d - (X+7)e - (X+8)f
3: (X+4)a + (X+5)b - (X+7)d - (X+8)e - (X+9)f
4: (X+5)a + (X+6)b + (X+7)c - (X+9)e - (X+10)f
5: (X+6)a + (X+7)b + (X+8)c + (X+9)d - (X+11)f
6: (X+7)a + (X+8)b + (X+9)c + (X+10)d + (X+11)e

I would then set each play to be equal, so that it doesn't matter what my opponent does. Is that correct? Do I care about the differential in points, or just the amount of points that he gains? To solve for 2 rounds only, could I just add some term to the above equations, some function f(a,b,c,d,e,f,N,X), where N is the nugget that he plays in round 1? I suppose I would have to have 6 such functions, one for each play I make in round 1. Ugh.

[Utah]

[ QUOTE ]
Suppose we play for one round only. My strategy will be to play nuggets 1-6 with probabilities a, b, ... f. The nugget up for bid is worth X. Then my opponent's EV, in point differential, is:

1: -(X+3)b - (X+4)c - (X+5)d - (X+6)e - (X+7)f
2: (X+3)a - (X+5)c - (X+6)d - (X+7)e - (X+8)f
3: (X+4)a + (X+5)b - (X+7)d - (X+8)e - (X+9)f
4: (X+5)a + (X+6)b + (X+7)c - (X+9)e - (X+10)f
5: (X+6)a + (X+7)b + (X+8)c + (X+9)d - (X+11)f
6: (X+7)a + (X+8)b + (X+9)c + (X+10)d + (X+11)e

I would then set each play to be equal, so that it doesn't matter what my opponent does. Is that correct? Do I care about the differential in points, or just the amount of points that he gains? To solve for 2 rounds only, could I just add some term to the above equations, some function f(a,b,c,d,e,f,N,X), where N is the nugget that he plays in round 1? I suppose I would have to have 6 such functions, one for each play I make in round 1. Ugh.

[/ QUOTE ]

You are thinking about the problem in the wrong direction. You can reduce the branches from right to left but not from left to right. So, your ultimate pregame strategy would be to include all possible plays in all rounds. So, you can include a term of terminal future round values in your round one strategy - ie, this path gives me X value in round one plus a terminal value of Y for all future rounds down this path. If you dont account for this at the start you end up with the possibility of going down a path that is +EV in the first round but has a very -EV in the later rounds for a net loss.

It all works in concert. Simply draw out some decision trees and you will see why you can't look at round one alone. Rather, you start with the farthest branches and keep reducing back to the start.

You can use a tool like http://econweb.tamu.edu/gambit/ to solve simpler problems. However, it will never solve something this complex. I tried before and crashed the software. I contacted the maker and he said not only could their software not do it but there was no software they were aware of that could.

Note: You are playing a game with perfect information. Thus, if you were playing only one round you would simply play your 6 /images/graemlins/smile.gif

[Utah]

I was wrong about this before. It hit me on the way home from picking up the kids. This is easily solvable.

There are only 3375 possible 2-round scenarios (combinations of my remaining chips, my opponents remaining chips, and the 2 remaining chips to bid on). Simply calculate the EV of all these branches. The 2-round game is simple as there are only 4 strategies possible.

Bid high chip if bidding on high. Bid high chip if bidding on low
Bid high chip if bidding on high. Bid low chip if bidding on low
Bid low chip if bidding on high. Bid high chip if bidding on low
Bid low chip if bidding on high. Bid low chip if bidding on low

simply: HH,HL,LH,LL

There are 8000 possible scenarios with 3 chips remaining. There are only 3 strategies in the game theory grid since you just reduced the next 2 rounds. Calculate all 8000 3 strategy games using the terminal values from prior step.

Now, you have the terminal value of all 3 round games (end branches).

there are 3375 possible scenarios for the prior round. This is now a 4 strategy game. Calculate all 3375 using the terminal values for the 3 round game.

There are 216 possible scenarios for the prior round. This is a 5 strategy game. Calculate all 216 using the terminal values from the 4 round game.

There is 1 possible scenarios for the prior (first) round. This is a 6 strategy game. Calculate all 6 using the terminal values of 5 round game.

This shouldn't be too hard if you have some programing cababilities and a sufficiently powerful computer.

There is the possibility too that I am missing something as I did this quick. But, I believe it works.

[Magic_Man]

This sounds promising, but how do you take into account ties from previous rounds? With 2 rounds left, it seems like there are more than those 3375 combinations, since there could be different combinations of ties that are riding on the current round.

[Utah]

You're right. Damnit.

You need a more powerful computer, but it is still doable.

2 round game = 189000 = 3375*56 (tie combinations)
3 round game = 328000 = 8000*41
4 round game = 70875 = 3375*21
5 round game = 1296 = 216*6

A lot of the tie combinations are not possible given certain scenarios (eg, I cant have a 6 tie going into it if I still have a 6 in my hand). However, I wouldn't bother programming that.

Also, the above takes into account all multiple tie combinations. eg., you can be carrying up to 4 consecutive ties in the 2 round game.

These calculations were quick so their may be something missing.

[Magic_Man]

[ QUOTE ]
You're right. Damnit.

You need a more powerful computer, but it is still doable.

2 round game = 189000 = 3375*56 (tie combinations)
3 round game = 328000 = 8000*41
4 round game = 70875 = 3375*21
5 round game = 1296 = 216*6

A lot of the tie combinations are not possible given certain scenarios (eg, I cant have a 6 tie going into it if I still have a 6 in my hand). However, I wouldn't bother programming that.

Also, the above takes into account all multiple tie combinations. eg., you can be carrying up to 4 consecutive ties in the 2 round game.

These calculations were quick so their may be something missing.

[/ QUOTE ]

I think we have to add one to each of those tie combinations to account for the times where there isn't a tie, right? Probably the actual number of possible games is still less than what you quoted, since some ties aren't possible.

~MagicMan

[Utah]

[ QUOTE ]
I think we have to add one to each of those tie combinations to account for the times where there isn't a tie, right?

[/ QUOTE ]Duh. Yes. I bet there are other little errors in there as I went quick. But, I believe the approach is correct.

[ QUOTE ]
Probably the actual number of possible games is still less than what you quoted, since some ties aren't possible.

[/ QUOTE ]There definitely is. However, it would be easier to simply avoid this complexity when programming since they would automatically get washed out in the calculations when the prior round is assigned.