I have been experimenting with three player games, which are almost never deterministic. Imagine it is your turn, you see that you can’t win, but you can move in such a way that either of the other two players wins. You have become a kingmaker! What do you do? Even though your choice has no impact on whether you win or lose, you still have to make a decision. There are three natural options:
- the Good strategy – if you can’t win, try to help the next player win
- the Evil strategy – if you can’t win, try to prevent the next player from winning
- the Neutral strategy – choose randomly from all moves which maximize your probability of winning
To analyze a three player game, I suggest that we start by analyzing what happens if all players follow the Good strategy, all players follow the Evil strategy, or all players follow the Neutral strategy.
Example: 1-2 Nim
Starting with three players and a pile of n stones, each player can remove either 1 or 2 stones on their turn. The player to remove the last stone wins.
- If all players agree to follow the Good strategy, then you will win if and only if n is 1 or 2 mod 5 when it is your turn.
- If all players agree to follow the Evil strategy, then you will win if and only if n is 1 or 2 mod 4 when it is your turn.
- If all players agree to follow the Neutral strategy, then for any fixed large value of n, the outcome is roughly random: Each player wins with probability approximately 1/3. (Can you prove it?)
Now of course, each player can only choose their own strategy, and each player wants their strategy to lead to first player wins as often as possible. So on average, the Evil strategy seems to be best of the three for everyone, since it leads to a first player win for 50% of values of n. But in practice, you could never get all three players to agree on following the Evil strategy, because then two players would be guaranteed to lose. To save themselves, they would surely break away from the strategy. So a three player game is always a problem in analyzing people’s behavior (economic game theory), not just mathematics. I will leave this kind of thinking to someone else, but I just point it out to illustrate that our simple mathematical model is not the whole story!
Example: Divisor Nim
Same setup. On your turn, if there are n stones, you can remove any number of stones which is a proper divisor of n. If 1 stone remains after your turn, you win. (After all, 1 has no proper divisors, so the game can’t continue.)
Since this game is more complicated, I don’t know any easy way to determine who wins under either the Good or Evil strategies. However, what about the Neutral strategy? In 1-2 Nim, when n was large, the outcome of following the Neutral strategy was roughly random. Each player won with probability about 1/3.
Is the same true in Divisor Nim? No!
Example: If n=1,000,000, then player 1 wins with probability exactly 50%, player 2 with probability ~36.5%, and player 3 with probability ~13.5%.
Theorem: In 3-player Divisor Nim, if all players follow the Neutral strategy, then for all n>15, at least one of the players has probability exactly 50% of winning.
This is a great toy example of a math research problem. As far as I can tell, proving it requires a little bit of computer programming and a little bit of mathematical ingenuity. Can you prove it? If you get stuck, contact me for the solution.
Problems
- Suppose you are playing three player 1-2 Nim, it is your turn, and there are 9 stones. Without knowing your opponents’ strategies, what should you do? Think about it, and then read the solution below.
- In three player 1-2 Nim, if all players agree to follow the Neutral strategy and n is large, prove that each player’s probability of winning is close to 1/3.
- In three player Divisor Nim, if all players agree to follow the Neutral strategy and n>15, prove that one of the players has exactly 50% probability of winning.
- What else can you learn about three player variants of Nim? If you discover anything, please let me know!
Solution to the first problem
Suppose you are playing three player 1-2 Nim, it is your turn, and there are 9 stones. Should you remove one stone or two? At first glance, it seems like each option is as good as the other. But let’s think recursively about what you would do if it were your turn and there were:
1 or 2 stones – You win! Congratulations!
3 stones – You lose. The player after you wins.
4 stones – You lose, but your move determines which of the other players wins. You are a kingmaker!
5 stones – You should always remove 1 stone, and then either you or the player before you will win. After all, if you remove 2 stones, then you are guaranteed to lose. So you remove 1 stone, and the player after you becomes kingmaker. Better hope they like you — maybe you should promise them some of your winnings…
6 stones – There is no mathematical answer here. If you remove 2 stones, the player after you will become kingmaker. If you remove 1 stone, the player before you will become kingmaker. Remove 2 if you have a better relationship with second player, 1 if you have a better relationship with third player.
7 stones – You should always remove 2 stones, and then either you or the player after you will win. Why? If you do remove 2, then second player will be looking at 5 stones, will remove 1, and third player will end up as kingmaker.
But what if you removed 1 stone? Then one of two things would happen:
- Second player removes 1 stone, and now third player is looking at 5 stones and removes 1. You are now looking at 4 stones and guaranteed to lose.
- Second player removes 2 stones, and now third player is kingmaker.
In other words, whether you remove 1 or 2 stones, your only path to victory involves the third player as kingmaker, but if you remove 1, then your path to victory also requires a certain decision from the second player. It is strictly better to just remove 2 stones.
8 stones – You should always remove 2 stones. If you removed 1, then the next player would be looking at 7 stones, and you would be guaranteed to lose if everyone played logically.
9 stones – You should always remove 1 stone. If you removed 2, then the next player would be looking at 7 stones, and you would be guaranteed to lose for the same reason.
There is some surprisingly rich structure to three player (1,2)-Nim. Every game involving at least 4 stones will eventually end up with one player (the “kingmaker”) looking at 4 stones and able to choose the winner. But less obvious, in perfect play, every game involving at least 8 stones will eventually end up with one player (the “heir-apparent”) looking at 6 stones and able to choose which of the other two players will be the kingmaker.
For an interesting puzzle in human behavior, try playing a few rounds starting from 10 stones!
References
I made these problems up and don’t know much about the literature on 3 player games, but if I wanted to dig deeper, I would start with articles like these:
- S.-Y.R. Li, “N-person Nim and N-person Moore’s games.” International Journal of Game Theory 7 (1978).
- James Propp, “Three player impartial games.” Theoretical Computer Science 233 (2000).
- Nowakowski, Santos, Silva. “Three player Nim with podium rule.” International Journal of Game Theory 50 (2021).
GeodeMath 