Hacker News Reader

Comment by seanw265 | Hacker News Reader

There must be something I'm missing.

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?

View on HN

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.

Please see my follow-up comment with another simulation that shows how the expected score can rise well above .296.

https://news.ycombinator.com/item?id=33025759

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.

Diving into this further, I've found another situation that appears to interfere even more.

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.

> 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.

If there's two of you then you are even better off just always picking 1.

You either win, or tie, depending on your opponent's strategy. Your opponent can never win.

That seems extremely optimal.

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).

This was very helpful. Thank you!

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.

Reply on news.ycombinator.com