Now I'm wondering which is the best strategy you can follow if the other players follow an unknown non-optimal strategy (like selecting 1,2 or 3 with p=1/3). Maybe it's a good scenario to try some reinforcement learning
There is a nice strategy that is playing always 1, and claiming it.
Everyone else should not play 1 because otherwise they would not win. But if no one else plays 1, you win. So they must take turns to lose and make you lose. It's a good strategy to not meet them again ever :)
The other players then always pick 1 and 2, making the latter the winner, and you always the loser.
But in this case you lose no matter what strategy you use; you only get to decide which of the other players wins.
That's why the article analyses the case where the other players use the same strategy.
It's more fun with more players. They can discuss who is going to lose the round because of choosing 1 to block you. Someone can refuse to collude, so another must take the turn. Someone can decide to become a vigilante and choose always 1 to block you. Humans are very fun!
I wonder what would happen to the two player game if the rewards were set up so that win=1, lose=0, tie=-1? It would be interesting to see how the strategy changed as the penalty for tying is increased.
picking 1 would still dominate over any other strategy, in a head-to-head.
However, if you are trying to maximize your H2H score against a pool of contestants, a cooperation strategy, where you both alternated taking the lower number would be close to optimal.
For a short intuitive proof of that 1st sentence, imagine both players pick 1 every time. You both lose 1 point. If you're tied for score, you're still tied after the round.
Now imagine you change your number to stop ties. Well now you've picked a number bigger than 1, and you lose every time. If you were tied, now you're losing.
This is only true if your goal is to have a score higher than your opponent. It's not true if your goal is to have the highest possible score.
If ties are with 0, you always choose 1 in either situation. If ties are worth -1, choosing 1 always achieves a greater than or equal to score but the number will be much lower than if you some percentage of the time choose another number.
> In game theory, strategic dominance (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play.
All the other answers in the thread focus on maximizing head-to-head score. I'll try to answer the question for the goal of greedily maximizing your own score.
Using the same definitions from the article, we now have (for a 2 person game):
Q_i = -P_i + (1 - sum_{j=1..i}(P_j))
Where the first term is for the case of choosing the same number as your opponent, and the second when it's larger than your opponent.
Now solve the same set of equations, but with our new Q_i. Solving Q_1 = Q_2 analytically is easy, then Q_2 = Q_3 and so on... You get P = (1/2, 1/4, 1/8, ...)
So that's the result for this specific 2-player game. You could also ask about the 2-player game with tie=t for any negative t (the above is for t=-1). Now we get
Q_i = t*P_i + (1 - sum(P_j))
Again, solving Q_i=Q_{i+1} is easy and gives
P_{i+1} = (t / (t-1)) * P_i
For example, if t=-2 then (using the fact that all P_i's sum to 1): P = (1/3, 2/9, 3/27, ...)
I did not try to tackle the 3-player game with tie=t.
I think a triple tie means no one wins, which would explain why the probability of winning is less than 1/3. (If each of the three players is playing the same Nash equilibrium strategy, they should each win with the same frequency.)
This is used as a model for "reverse auctions" [1], which also then charges a fee for participation which essentially makes the whole thing a cross between a lottery and a scam.
There were loads advertised on TV with misleading claims about people winning ipods for 37p, etc, which while technically might be true for the winner ignores the overall cost.
I've not seen many advertised lately so either the practice itself or the advertising of it was cracked down on.
Interesting problem and I appreciate the author bringing it to our attention. That said, I have to admit I found the Math Overflow post he took the solution from much clearer: https://math.stackexchange.com/a/80743/
For one thing, the Math Overflow post is correct, whereas the blog post states a crucial inequality in the wrong direction. This confuses the whole argument, since the surrounding text isn't clear enough for the reader to easily self-correct the typo.
The other factor is the flow of the exposition. For example, the blog post attempts to define Q before using it, but the definition is too vague and ends up being less useful than the "define in the course of the argument" approach used in the Math Overflow post.
(Slightly off topic) -- I can't connect to this site from my mobile data or home connection. FF, Curl + mobile FF claim to not be able to resolve the host
The DNS records seem odd:
$ dig www.amolas.dev
[ ... ]
;; ANSWER SECTION:
www.amolas.dev. 66 IN CNAME https://alexmolas.github.io.
https://alexmolas.github.io. 66 IN A 185.199.111.153
https://alexmolas.github.io. 66 IN A 185.199.109.153
https://alexmolas.github.io. 66 IN A 185.199.108.153
https://alexmolas.github.io. 66 IN A 185.199.110.153
Why do you have links styled to look exactly like the other plain text?
At the bottom of the article, it says "This post has been heavily inspired by this question in SO ↩" and I could not for the life of me find the link to said question until I discovered that "question" was a hidden link.
That's weird, because on my computer it looks well. Some people already complained about that, but I don't know why it can happen. Do you have any suggestion?
This reminds me of an old article quote from a game developer on Steam bug reports from Linux vs Windows users:
>The report quality [from Linux users] is stellar. I mean we have all seen bug reports like: “it crashes for me after a few hours”. Do you know what a developer can do with such a report? Feel sorry at best. You can’t really fix any bug unless you can replicate it, see it with your own eyes, peek inside and finally see that it’s fixed. And with bug reports from Linux players is just something else. You get all the software/os versions, all the logs, you get core dumps and you get replication steps. Sometimes I got with the player over discord and we quickly iterated a few versions with progressive fixes to isolate the problem. You just don’t get that kind of engagement from anyone else.
What's super surprising if that I'm "dumb" and I play against two "smart" players then I can't have a bad strategy. Assuming that the "smart" players play the Nash-equilibrium mixed strategy then whatever strategy I execute, I have the same chance of winning.
It seems that it contradicts the principle of Nash equilibrium, since in Nash equilibrium you don't have any reason to change your strategy. However, if you change a "smart" strategy to a "dumb" strategy you're not increasing/decreasing your winning changes, so it still fulfills the Nash equilibrium principle.
This game seems to do weird things if you have a player able to disclose their choice in advance too. Stating that you will choose 42 is stronger than stating you will choose 1, assuming other players only maximize their own odds of winning. It's kind of like a convoluted game of chicken.
Choosing a bigger number makes it less likely that you will win by being smaller than the other two, but more likely that you will win by the other two knocking each other out, since there are now more numbers available for them to do so with.
but still (1) there's some probability of both players choosing a number bigger than one million billion trillion, and (2) there's some probability of both other players choosing the same number. Actually, the probability that the other both players choose 1 is pretty big (~0.21). So even if you choose a super-big number, there's a big probability of you still winning.
I read past four links in the text before it became clear that hyperlinks are visually indistinguishable from the rest of the text on this site. Who does this?
> if we follow this strategy we’ll win a little bit less than one-third of the time.
That is not possible. If N players use the same strategy then by symmetry each of them must win on average 1 time in N. So against two other players we should win exactly one third of the time, not "a little bit less" than one third of the time.
Also, if all players use the same strategy then it doesn't matter what the strategy actually is. The only requirement is that it have some probabilistic element, otherwise all players would choose the same number every time.
It seems like there are pathological counterexamples. If you're player three, and player one chooses 1 always, and player two chooses 2 always, then the player using this strategy can never win.
Player 2 wins with probability .45 (only wins when player 1 gets "knocked out"), and player 1 with probability 1-.45, and player 3 never wins.
> If N players use the same strategy then by symmetry each of them must win on average 1 time in N.
The point here is that there's an option of tying, if all players choose the same number. So P_1_win + P_2_win + P_3_win + P_tie = 1, means P_i_win < 1/3.
> Also, if all players use the same strategy then it doesn't matter what the strategy actually is. The only requirement is that it have some probabilistic element, otherwise all players would choose the same number every time.
A player choose its next move using some probabilities P, ie: it's going to choose randomly number 1 the 45% of times, 2 the 25% of times, etc. So there's a random element in the game, which makes players following the same strategy to not choose the same numbers every time.
> Also, if all players use the same strategy then it doesn't matter what the strategy actually is.
But it's not very interesting to add "all players use the same strategy" as an assumption, because yes, obviously, if every player randomly picks from the set {33, 247, 17855433344} each has a 29.6% chance of winning. But that's a different game.
In fact the author doesn't assume everyone will use the same strategy; rather, the author simply asks what optimal play is, when you don't know the others' strategies. The fact that all players choose the same strategy (if they're playing optimally) is a consequence of this. Optimal play has to work regardless of the strategy your opponents pick; assuming they'll play optimally too is just a shortcut to figuring out what optimal play is.
For example, let's say you knew the other two players' strategy is to pick from this distribution. If you simply always pick 1, you win any time neither of the others picked 1, which happens with probability (1-0.456)^2 ~ 0.296 -- the same probability of winning as the optimal strategy! So why bother with the distribution? Precisely because you don't know whether your opponents are playing optimally or not. If another player gets the same bright idea as you, you counteract each other and the 3rd player wins 54% of the time (the rest are ties). An optimal strategy has to be optimal even if opponents are not using it; otherwise it's not really optimal (one may not exist).
So all players using the same strategy is not an assumption, but a consequence, and therefore much more interesting.
The probability to win comes out as a^2 ~= 0.2955977425220847709809965928515386138989754484466083115379546015...
edit2:
To arrive to this solution I expressed the equations in terms of R_i = P(choosing a number larger than i), then substitute P_i = R_{i-1} - R_i . This gets rid of the sums when you evaluate Q_{j+1} - Q_j , and arrives at R_{j+1}^2 = R_{j-1}(2 R_j - R_{j-1}). We know that R_0 = 1, and lim R_i = 0. I just tried R_i = a^i, and it works, with the value of "a" calculated above.
edit3:
To name names: the solution is a geometric distribution [1]
What I ended up reducing the algebra problem to is a homogeneous recurrence relation, albeit non-linear. As it has constant coefficients, a^i is the obvious candidate to test it with.
I got successfully nerd-sniped, this is a fun problem. Next time with 4 players...
There was an online game in the 2000s where this game was played at scale (I think it was called limbo??). Lowest number I remembering seeing win was 4 but it would go up into the hundreds
> To start, assume that the other two players use the equilibrium probabilities P
If we can assign strategies (but no coordination) to other players, then how about having every player generate a uniform random 64-bit number.
Given the low chances of collision with this setup, this will result in a 1/3 chance of winning which is higher than the 0.296 chance given in the article.
> I fail to understand how this can be considered an optimal strategy.
Aye, I mean it doesn't even pass the sniff test to me.
If all actors are a) informed of the number of participants and b) are trying to win in earnest, I can not understand why a rational actor would ever pick a number larger than the number of participants. It seems an obviously bad strategy that's an artifact of infinite calculus.
Really though, I think using tools made for real numbers are a bad fit for a problem firmly bounded to natural numbers. I haven't formally studied game theory, but it's my impression this is the exact type of problem it's designed for, and discrete games are a significantly studied subject.
My intuition is there is no reason to ever pick a number greater than participants-1. I feel weird saying that, because everyone, you included, keeps bounding on 1-10 and not 1-n, and I don't have a lot of the formal math training that is fairly ubiquitous here, especially in this thread I would assume. I'd be interested to see the way the distributions play out when one of the Agents randomly select 1 or 2, might have to code this up, but I'm trying to resist the urge to jump down a rabbit hole. I definitely think that "everyone is using the same strategy" is a special case of the question, not a generalized solution.
My thinking is: in any case where you would pick 3+, why wouldn't you pick 1 or 2?
> I can not understand why a rational actor would ever pick a number larger than the number of participants.
If there are two of you and you're both always picking 1 or 2, you're going to both lose half the time when you collide. You'll win 1/4 of the time.
If you instead pick from 1-3 you're only going to collide 1/3 of the time, and you'll win 1/3 of the time.
1-4, 1/4 collision, 3/8 win rate.
(I think I've got the maths right, based on picking numbers uniformly.)
If you accept this is logical but decide to actually only ever pick 1 or 2, your logical opponent will surely decide the same and you'll both be worse off.
Indeed the Nash equilibrium is not always what we would like to call "optimal", especially in games with more than two players.
As you notice, it is possible the Nash equilibrium strategy will be crushed if more than one agent chooses a different strategy (i.e. a situation where players are deviating from a strategy in a non-unilateral fashion). If Agent 1 and Agent 2 work collude beforehand they can completely crush Agent 3. The Nash equilibrium only says the agent will lose more if they change while the others use the follow the same strategy (i.e. a unilateral deviation).
In defense of the Nash equilibrium, there are some reasons we can sort of assume that the two players will pick a strategy which happen work together to beat us by a lot. For example, one of the two other players could just play the Nash strategy along with us, in which case we know the other player will not be able to exceed the equilibrium value. There is no way the player can pick a strategy all by themselves which is guaranteed to win more than the equilibrium value. For the other players to actually have a guaranteed higher probability of winning, they must coordinate playing their strategy with the other player and trust that the other player will keep their word. This is known as forming a coalition.
There are some other notions of equilibrium which take this into account and do not permit coalitions to change the value (see: strong Nash equilibrium), but it won't exist for many games (like this one).
The Nash equilibrium strategy is optimal when the other players are also playing optimally.
If your opponents never choose 1, you can choose 1 and win 100% of the time. But if your opponents are very smart, know your strategy, and will exploit any weakness your strategy presents, it's best to play the Nash equilibrium strategy.
The nash equilibrium is defined by a strategy that cannot be improved by changing your own strategy, assuming the other players' strategies stay the same.
Agent 1 doesn't care if Agent 2 and 3 win less than him, he only feels a strategy is better than the Nash strategy if his expected score becomes higher than .296, which your simulation seems to show has not been achieved.
I don't believe cases where changing your strategy in a non-equilibrium state are considered, as the assumption that no other player will shift their own strategy will not hold.
Otherwise, you might as well consider the case P1 always chooses 1, P2 always chooses 1 and P3 always chooses 2.
There was a cool challenge in the Code Golf community in Stack Exchange, where participants wrote python scripts to compete in this problem over 1,000 rounds. The bots had access to previous rounds' results to inform their choice in each round.
The game is an interesting one. If an opponent declares an intention to always choose one, you’re more or less forced to collude with other players to beat him. With 3 players this is possible to execute without needing to trust the other person. They cannot fake it out to harm you. But you cannot do anything to avoid purposefully giving the win to another player.
I worked with a nationwide lottery game in Sweden called Limbo around 2005-2006 that used this concept. I believe the winner each day won around $1000 and had the ability to turn it into $10000 in a weekly final doing the same game in a tv-studio.
The game was completely shut down after people in a small little town won three times in a row and they started to suspect foul play. Turned out to be the local store asking people to join and the store distributed the numbers for the people to make sure they had an even distribution across a huge range.
It seemed to me by the description that being first, and picking 0 was sure win. But apparently ties mean nobody wins, or somebody not tied wins, or something. Doesn't say.
87 comments
[ 4.9 ms ] story [ 141 ms ] thread> To simplify the problem, let’s start with the simple scenario where you are competing against two other persons.
> P(wining)~=0.296
Where does the other 11.2% go? Is the probability of a triple tie? Perhaps you can add it to the article.
Now I'm wondering which is the best strategy you can follow if the other players follow an unknown non-optimal strategy (like selecting 1,2 or 3 with p=1/3). Maybe it's a good scenario to try some reinforcement learning
Everyone else should not play 1 because otherwise they would not win. But if no one else plays 1, you win. So they must take turns to lose and make you lose. It's a good strategy to not meet them again ever :)
But in this case you lose no matter what strategy you use; you only get to decide which of the other players wins. That's why the article analyses the case where the other players use the same strategy.
The hard part is to establish a prior for this "unknown". Otherwise you can't say anything.
Which is why the author skips the case of two players. Because then picking 1 always is a dominating strategy in which neither player wins.
However, if you are trying to maximize your H2H score against a pool of contestants, a cooperation strategy, where you both alternated taking the lower number would be close to optimal.
Now imagine you change your number to stop ties. Well now you've picked a number bigger than 1, and you lose every time. If you were tied, now you're losing.
If ties are with 0, you always choose 1 in either situation. If ties are worth -1, choosing 1 always achieves a greater than or equal to score but the number will be much lower than if you some percentage of the time choose another number.
That is what “dominant” in game theory means, which was the specific claim that’s being discussed.
> https://en.wikipedia.org/wiki/Strategic_dominance
> In game theory, strategic dominance (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play.
That is what is being described above.
Using the same definitions from the article, we now have (for a 2 person game):
Where the first term is for the case of choosing the same number as your opponent, and the second when it's larger than your opponent.Now solve the same set of equations, but with our new Q_i. Solving Q_1 = Q_2 analytically is easy, then Q_2 = Q_3 and so on... You get P = (1/2, 1/4, 1/8, ...)
So that's the result for this specific 2-player game. You could also ask about the 2-player game with tie=t for any negative t (the above is for t=-1). Now we get
Again, solving Q_i=Q_{i+1} is easy and gives For example, if t=-2 then (using the fact that all P_i's sum to 1): P = (1/3, 2/9, 3/27, ...)I did not try to tackle the 3-player game with tie=t.
I think a triple tie means no one wins, which would explain why the probability of winning is less than 1/3. (If each of the three players is playing the same Nash equilibrium strategy, they should each win with the same frequency.)
There were loads advertised on TV with misleading claims about people winning ipods for 37p, etc, which while technically might be true for the winner ignores the overall cost.
I've not seen many advertised lately so either the practice itself or the advertising of it was cracked down on.
[1] https://www.gamblingcommission.gov.uk/public-and-players/gui...
For one thing, the Math Overflow post is correct, whereas the blog post states a crucial inequality in the wrong direction. This confuses the whole argument, since the surrounding text isn't clear enough for the reader to easily self-correct the typo.
The other factor is the flow of the exposition. For example, the blog post attempts to define Q before using it, but the definition is too vague and ends up being less useful than the "define in the course of the argument" approach used in the Math Overflow post.
The DNS records seem odd:
I don't think you can put a scheme in a cname ...How can I solve the problem? What does it mean to put a scheme in a cname?
It means that https:// shouldn't be mentioned in the DSN records
> How can I solve the problem?
You should edit your DNS records and remove it
So a user who copy pasted from the URL bar into the DNS records (probably following some guide) ended up with the wrong thing in there.
Why do you have links styled to look exactly like the other plain text?
At the bottom of the article, it says "This post has been heavily inspired by this question in SO ↩" and I could not for the life of me find the link to said question until I discovered that "question" was a hidden link.
>The report quality [from Linux users] is stellar. I mean we have all seen bug reports like: “it crashes for me after a few hours”. Do you know what a developer can do with such a report? Feel sorry at best. You can’t really fix any bug unless you can replicate it, see it with your own eyes, peek inside and finally see that it’s fixed. And with bug reports from Linux players is just something else. You get all the software/os versions, all the logs, you get core dumps and you get replication steps. Sometimes I got with the player over discord and we quickly iterated a few versions with progressive fixes to isolate the problem. You just don’t get that kind of engagement from anyone else.
If they play thousands of times, what will the distribution of wins be?
It seems that it contradicts the principle of Nash equilibrium, since in Nash equilibrium you don't have any reason to change your strategy. However, if you change a "smart" strategy to a "dumb" strategy you're not increasing/decreasing your winning changes, so it still fulfills the Nash equilibrium principle.
Choosing a bigger number makes it less likely that you will win by being smaller than the other two, but more likely that you will win by the other two knocking each other out, since there are now more numbers available for them to do so with.
> if we follow this strategy we’ll win a little bit less than one-third of the time.
That is not possible. If N players use the same strategy then by symmetry each of them must win on average 1 time in N. So against two other players we should win exactly one third of the time, not "a little bit less" than one third of the time.
Also, if all players use the same strategy then it doesn't matter what the strategy actually is. The only requirement is that it have some probabilistic element, otherwise all players would choose the same number every time.
Player 2 wins with probability .45 (only wins when player 1 gets "knocked out"), and player 1 with probability 1-.45, and player 3 never wins.
The point here is that there's an option of tying, if all players choose the same number. So P_1_win + P_2_win + P_3_win + P_tie = 1, means P_i_win < 1/3.
> Also, if all players use the same strategy then it doesn't matter what the strategy actually is. The only requirement is that it have some probabilistic element, otherwise all players would choose the same number every time.
A player choose its next move using some probabilities P, ie: it's going to choose randomly number 1 the 45% of times, 2 the 25% of times, etc. So there's a random element in the game, which makes players following the same strategy to not choose the same numbers every time.
But it's not very interesting to add "all players use the same strategy" as an assumption, because yes, obviously, if every player randomly picks from the set {33, 247, 17855433344} each has a 29.6% chance of winning. But that's a different game.
In fact the author doesn't assume everyone will use the same strategy; rather, the author simply asks what optimal play is, when you don't know the others' strategies. The fact that all players choose the same strategy (if they're playing optimally) is a consequence of this. Optimal play has to work regardless of the strategy your opponents pick; assuming they'll play optimally too is just a shortcut to figuring out what optimal play is.
For example, let's say you knew the other two players' strategy is to pick from this distribution. If you simply always pick 1, you win any time neither of the others picked 1, which happens with probability (1-0.456)^2 ~ 0.296 -- the same probability of winning as the optimal strategy! So why bother with the distribution? Precisely because you don't know whether your opponents are playing optimally or not. If another player gets the same bright idea as you, you counteract each other and the 3rd player wins 54% of the time (the rest are ties). An optimal strategy has to be optimal even if opponents are not using it; otherwise it's not really optimal (one may not exist).
So all players using the same strategy is not an assumption, but a consequence, and therefore much more interesting.
P_i = a^i (1/a - 1)
where a is the real-valued solution of a^3 + a^2 + a - 1 = 0 .
a = 1/3 (-1 - 2/(17 + 3 sqrt(33))^(1/3) + (17 + 3 sqrt(33))^(1/3))
edit:
The probability to win comes out as a^2 ~= 0.2955977425220847709809965928515386138989754484466083115379546015...
edit2:
To arrive to this solution I expressed the equations in terms of R_i = P(choosing a number larger than i), then substitute P_i = R_{i-1} - R_i . This gets rid of the sums when you evaluate Q_{j+1} - Q_j , and arrives at R_{j+1}^2 = R_{j-1}(2 R_j - R_{j-1}). We know that R_0 = 1, and lim R_i = 0. I just tried R_i = a^i, and it works, with the value of "a" calculated above.
edit3:
To name names: the solution is a geometric distribution [1]
What I ended up reducing the algebra problem to is a homogeneous recurrence relation, albeit non-linear. As it has constant coefficients, a^i is the obvious candidate to test it with.
I got successfully nerd-sniped, this is a fun problem. Next time with 4 players...
[1] https://en.wikipedia.org/wiki/Geometric_distribution
If we can assign strategies (but no coordination) to other players, then how about having every player generate a uniform random 64-bit number.
Given the low chances of collision with this setup, this will result in a 1/3 chance of winning which is higher than the 0.296 chance given in the article.
The point of the equilibrium is that even if your respective strategies are public knowledge, nobody can benefit from changing theirs
I borrowed the author's choice probabilities and wrote a script to verify the probability of winning by simulating 10 million rounds of gameplay.
It seems it's true that when all three agents are following the same choice probability distribution the result is a win about 29.6% of the time.
However, when one of those three agents follows an alternative choice probability distribution, the percentages change significantly.
*Example:*
Agent 1 (nash distribution): .296
Agent 2 (nash distribution): .296
Agent 3 (nash distribution): .296
*However:*
Agent 1 (always chooses 1): .296
Agent 2 (nash distribution): .248
Agent 3 (nash distribution): .248
My results indicate that the nash strategy is not optimal in an environment where agents can choose their own strategy.
What did I miss?
Our baseline (once again):
Agent 1 (nash distribution): .296
Agent 2 (nash distribution): .296
Agent 3 (nash distribution): .296
Another case:
Agent 1 (always chooses 1): .489
Agent 2 (even distribution -- equal chance of any number 1-10 being chosen): .411
Agent 3 (nash distribution): .054
In this situation, the nash strategy comes out far far behind either of the other two strategies.
This makes sense intuitively:
Agent 3 chooses 1 nearly half (45.6%) of the time. It will lose with that choice every time because Agent 1 chooses 1 every time.
When Agent 3 chooses 2-10 (100 - 45.6 = ) 54.4% of the time, it will lose almost every time because Agent 1 already chose 1.
The only case where Agent 3 wins is when Agent 3 chooses a value 2-10 (54.4%) AND Agent 2 chooses 1 (10%), eliminating itself.
54.4% * 10% = 5.4%, which is exactly the value discovered above.
---
The specific strategies chosen by your competitors have a very large impact on your strategy's effectiveness.
I fail to understand how this can be considered an optimal strategy.
Aye, I mean it doesn't even pass the sniff test to me.
If all actors are a) informed of the number of participants and b) are trying to win in earnest, I can not understand why a rational actor would ever pick a number larger than the number of participants. It seems an obviously bad strategy that's an artifact of infinite calculus.
Really though, I think using tools made for real numbers are a bad fit for a problem firmly bounded to natural numbers. I haven't formally studied game theory, but it's my impression this is the exact type of problem it's designed for, and discrete games are a significantly studied subject.
My intuition is there is no reason to ever pick a number greater than participants-1. I feel weird saying that, because everyone, you included, keeps bounding on 1-10 and not 1-n, and I don't have a lot of the formal math training that is fairly ubiquitous here, especially in this thread I would assume. I'd be interested to see the way the distributions play out when one of the Agents randomly select 1 or 2, might have to code this up, but I'm trying to resist the urge to jump down a rabbit hole. I definitely think that "everyone is using the same strategy" is a special case of the question, not a generalized solution.
My thinking is: in any case where you would pick 3+, why wouldn't you pick 1 or 2?
If there are two of you and you're both always picking 1 or 2, you're going to both lose half the time when you collide. You'll win 1/4 of the time.
If you instead pick from 1-3 you're only going to collide 1/3 of the time, and you'll win 1/3 of the time.
1-4, 1/4 collision, 3/8 win rate.
(I think I've got the maths right, based on picking numbers uniformly.)
If you accept this is logical but decide to actually only ever pick 1 or 2, your logical opponent will surely decide the same and you'll both be worse off.
You either win, or tie, depending on your opponent's strategy. Your opponent can never win.
That seems extremely optimal.
As you notice, it is possible the Nash equilibrium strategy will be crushed if more than one agent chooses a different strategy (i.e. a situation where players are deviating from a strategy in a non-unilateral fashion). If Agent 1 and Agent 2 work collude beforehand they can completely crush Agent 3. The Nash equilibrium only says the agent will lose more if they change while the others use the follow the same strategy (i.e. a unilateral deviation).
In defense of the Nash equilibrium, there are some reasons we can sort of assume that the two players will pick a strategy which happen work together to beat us by a lot. For example, one of the two other players could just play the Nash strategy along with us, in which case we know the other player will not be able to exceed the equilibrium value. There is no way the player can pick a strategy all by themselves which is guaranteed to win more than the equilibrium value. For the other players to actually have a guaranteed higher probability of winning, they must coordinate playing their strategy with the other player and trust that the other player will keep their word. This is known as forming a coalition.
There are some other notions of equilibrium which take this into account and do not permit coalitions to change the value (see: strong Nash equilibrium), but it won't exist for many games (like this one).
If your opponents never choose 1, you can choose 1 and win 100% of the time. But if your opponents are very smart, know your strategy, and will exploit any weakness your strategy presents, it's best to play the Nash equilibrium strategy.
Agent 1 doesn't care if Agent 2 and 3 win less than him, he only feels a strategy is better than the Nash strategy if his expected score becomes higher than .296, which your simulation seems to show has not been achieved.
https://news.ycombinator.com/item?id=33025759
Otherwise, you might as well consider the case P1 always chooses 1, P2 always chooses 1 and P3 always chooses 2.
https://codegolf.stackexchange.com/questions/172178/smallest...
The game was completely shut down after people in a small little town won three times in a row and they started to suspect foul play. Turned out to be the local store asking people to join and the store distributed the numbers for the people to make sure they had an even distribution across a huge range.
Zero points for helpful exposition.