Game Theory: Strategy and Backward Induction

Let’s play a game. I’ll let you go first which I promise will let you win… if you play just right. The game is called 50 and the goal is to say the number 50 first. Before you shout it out like a smart ass, I should clarify that there are more rules:

You start by saying a whole number from 1 to 10 (inclusive), that is 1, 2,…, 9, or 10. Then it’s my turn and, whatever number you say, I have to say a whole number that’s bigger than yours, but no more than 10 bigger. So if you said 4 on your first turn, I’m free to say 5, 6,..., 13, or 14 on my first turn. We then take turns back and forth, where on her or his turn each player must say a number that’s bigger than the other player’s but no more than 10 bigger. The first person to say 50 wins.

Example Round:

You: 4
Me: 12
You: 22
Me: 27
You: 34
Me: 36
You: 42
Me: 50

That means I win and I’d probably parade triumphantly around the room and insist you buy me lunch for the next week. I shouldn’t be cocky though, because I just got lucky. We both played haphazardly and I happened to win. When you relay this game to other people, you can make yourself win.

As I said at the beginning, the first player has the power to win the game if he or she plays right. As with many games, there is exactly one winning strategy for the first player, that is to say a strategy that guarantees a win no matter what the other player does. So what is it?

Your instinct is probably to start with the first turn and work forwards. You think to yourself, I can start with anything from 1 to 10 and for each of my ten options he has ten options. You’re only two turns in and already we have 10 x 10 = 100 possible ways the turns could have unfolded! Maybe we should try a different approach.

The trick is a little counterintuitive but very simple: start from the last turn and work backwards. On the first turn there are ten options but on the last turn there’s only one: saying 50. Suppose we played a game and you won. Immediately we know you took the last turn and said 50. What could have possibly happened in the second-to-last turn, that is my last turn.

There are exactly ten possibilities. Keeping in mind the rules of the game, I could only have said 40, 41,..., 48, or 49 because otherwise 50 wouldn’t be a valid choice for you. In fact, as soon as I said any of those numbers, you were guaranteed to win because, whichever one I chose, 50 would be a valid choice for you in the next turn.

The upshot is that if you can force me to say a number between 40 and 49 (inclusive), you are guaranteed to win. But you can force me! If you say 39, my options are exactly the numbers 40, 41,..., 48, and 49. We may as well call the game 39 instead of 50 because whoever says 39 first automatically wins.

Then we can just keep moving backwards. If you say 28, I have to say 29, 30,..., 37, or 38 so no matter what you are allowed to say 39 the following turn. If you say 17 you will certainly be allowed to say 28 the following turn because I am forced to say 18, 19,..., 26, or 27. And if you start with 6, you will be able to say 17 on your next turn, 28 your third turn, 39 on your fourth, and on the fifth you’ll say 50 for the win.

This technique of starting from the end and working backwards is called backward induction. It takes advantage of the fact that, if we assume that you won, there is only one possible final state of the game, namely you took the last move and you said 50.

Notice that in some games like checkers or chess this is not such an effective technique because there are many final states of the game if you won. In chess for instance, the winning move had to be the capture of the king, but the board could have anything from 3 to 32 pieces on it when that happens. Then working backwards isn’t any easier than working forwards.

The last observation I want to make about the game 50 is that it is a first player win. That is, if both players use their best possible strategies, the first player will win no matter what. Impatience may lead you to think every turn-based game that has no luck involved is a first player win. This is definitely not so! Many games, Tic-Tac-Toe for instance, are draws where nobody can ever win if everybody uses their best possible strategy. Some games are second player wins, which you can probably guess the meaning of by now.

For instance, how about we play a game where one player says a number and then the other player says a number and whoever’s number is bigger wins? I’ll even let you go first…

Challenge: want to check out your understanding? Try out our short, fun quiz