OK, so committing 2-2-96 is a perfect strategy, then? Because that’s quite easily beaten.
You guys are asking me to prove something that I already said doesn’t exist.
2-2-96 is a perfectly fine strategy for someone who decides to commit 1 in the first two rounds. The odds of that are pretty slim but it’s not impossible. But I’d say that in general it’s probably a bad strategy.
Yes, you are agreeing with me and proving my point.
And I’m saying that’s BS. There is no “optimal unbeatable one”.
There definitely is a strategy which if even if your opponent knows your exact weightings he cannot do better than tie you long term.
Up til that point though any other strategy will probably lose long-term against the optimal strategy.
Well, let’s just as an example say you pick a random number between 31-36 for round 1. Roll a 6-sided die covertly, and add the result to the number 30. Then your exact value is unpredictable but you are only committing around a third of your forces, leaving plenty for the second and third rounds while having a reasonable chance of winning the first round. I mean, this seems reasonable for a first round strategy.
Then what you pick for the second round depends on what they picked for the first round. Let’s say you did 35 and they did 25. You win round 1, and they have 75 left and you have 65 left. At this point you can then commit 64 in the second round and hope they don’t commit more than 64; if they do then you lose because then in the third round you only have 1 warrior left and as long as they didn’t commit their maximum of 74 (which they know they didn’t have to, they are guaranteed to win by just committing 65 which they know you can’t match). Or you can commit 1 in the second round, and hope they commit at least 12, in which case they’d have 63 or fewer and you have 64 and win the third round.
But you see how much depends on what they pick. It’s situational and not particularly complex. That’s why I don’t put a lot of stock in a grand master strategy, and I don’t think there is any kind of optimal, unbeatable strategy outside of being able to somehow predict your opponent.
Oh, I’m also assuming that nobody is choosing to commit a total number of warriors less than 100. Nothing in this thread has said that you can’t commit less than 100 by the end of the game, just that you can’t do more than 100 in total and have to do at least 1 each round.
If I know your first attempt is 31-36 I can bid 37 or 0 and gain an advantage. I can’t then guarantee victory but my range of options and the scenarios where I win are much greater and I will beat you more times than you beat me. That is of course a very basic strategy, but refine it enough, and add in some better randomisation eventually you will reach a strategy that cannot be beaten long-term, and will win longterm against suboptimal strategies.
In the interests of nit-picking I feel compelled to point out that picking 0 is illegal and picking 1 is a losing strategy unless your opponent picks at least 34 and only a drawing strategy unless your opponent picks at least 51. Picking 37 in this case works fine, though.
I think there’s a misunderstanding here. No-one is claiming that there’s an unbeatable strategy that will win every game. What we’re claiming is there must be an optimal strategy that guarantees a minimum 50% win rate against any opposing strategy (even if your opponent knows your strategy and can specifically tailor one to beat it) - and that the game is sufficiently complicated that it’s not at all clear what that strategy is.
The problem is nobody can define what an “optimal” strategy is. There “must” be such a thing and yet there’s no indication of what you even mean by that. Which makes such a statement useless.
I also find these confident statements that there must be such a strategy to be nothing more than hubris, especially with such a simple game. And especially when nobody can give an actual example. You need to back up those claims or it’s nothing but informed speculation based on nothing.
Here’s a discussion of this game - complete with the optimal strategies for particular numbers of allocatable warriors.
For larger S the game becomes progressively more difficult to analyze. For S = 12, it can be shown that (2, 4, 6) represents the optimal strategy, while for S > 12, deterministic strategies fail to be optimal. For S = 13, choosing (3, 5, 5), (3, 3, 7) and (1, 5, 7) with probability 1/3 each can be shown to be the optimal probabilistic strategy.
Since 100 is greater than 12, the 100 warrior case is one for which there is no deterministic strategy. By Nash’s theorem, there is still an optimal mixed strategy
Nash proved that if mixed strategies (where a player chooses probabilities of using various pure strategies) are allowed, then every game with a finite number of players in which each player can choose from finitely many pure strategies has at least one Nash equilibrium, which might be a pure strategy for each player or might be a probability distribution over strategies for each player.
It’s still hard work to figure out what that optimal strategy is - but we know a) that it exists, and b) that it’s a mixed strategy (a random choice with specific probabilities for specific “pure” strategies)
If someone wants to test strategies they could potentially do it on the SDMB (maybe in Thread Games)? It would take 3 people… Two players and a “helper”.
Each player separately messages a number to the helper who then reveals both choices in a post in the first round. Then it repeats through the last two rounds. It’s kind of awkward but doable, if someone really wanted to test things here.
I do not see that your link takes into account adjusting the allocation after the results of each round; it seems to pick them in advance (also the payoff value is slightly different, but that is not really a problem). For the game described there calculating the optimal (mixed) strategy is a straightforward computation (albeit that might take a while for a 5000x5000 payoff matrix).
I think adjusting after each round is a way to get to the stable solution where changing does no good for either player, but I could be wrong.
And yet, previously you said that
Now you’re saying that you shouldn’t commit only 1 warrior in two rounds, and also shouldn’t commit only 2 warriors in two rounds.
It’s not hubris; it’s math.
No, I said if someone was foolish enough to commit 1 warrior in the first two rounds that committing 2 in each of those rounds works fine. You’d obviously win in that scenario.
Of course, again odds are slim but a game like this is unpredictable.
1-1-98 makes it literally impossible to win, although you could tie. 2-2-96 is bad, but at least it beats 1-1-98, so it isn’t quite as bad.
Yes, that was the point I was making.
But a strategy that only wins against the worst possible strategy is still a terrible strategy. And once you admit that some strategies are worse than others, you have to admit that some strategies are better than others. And if some strategies are better than others, then there has to be some strategy that’s best, or at least a set of strategies that are tied for best.
Meanwhile, for the (simpler) version where all three allocations are made at once, I’ve determined that, at least, the optimal strategy can’t take the form of “use these three numbers, shuffled randomly”: For any strategy with fixed allocations a, b, and c such that a > b > c, a strategy of a+1, b-2, c+1 will win against it 2/3 of the time.
That counter-strategy doesn’t work for initial strategies where b = c+1 or c+2.
For example, if I pick 35-33-32, your formula gives 36-33-31, which only draws.
A more complete proof that there’s no optimal pure strategy in the simpler version:
- If a strategy contains no number >48, it loses to 50,49,1
- If a strategy contains only one number >33,it loses to 34,33,33
- The remaining strategies have the form a,b,c, where a > 48, b > 33 and c must be < 18. These lose to @Chronos’s a+1, b-2, c+1, or to something like 98-2c, c+1, c+1 (b is at least c+17, so a, which is 100-(b+c) cannot be greater than 83-2c)
Regarding Nash equilibrium: does it follow that if the game were deciding real number percentages of an (infinitely dividable) army, then no optimal strategy exists because you’re not choosing from some finite set of strategies?
You are never going to use (a, b, c) in your optimal mix, though, without also including all its permutations.