Backward Induction: Rationality or Inappropriate Reductionism? – Part 2

by Mark R. Waser (originally appeared Dec. 23, 2012 at Transhumanity.Net)

Contains three hints (one given previously) before the puzzle solution from Part 1 is revealed.

Before I lose my mathematical/logical audience, let me clearly state that backward induction is a logical operation that *always* functions correctly.  Unfortunately, however, like so many similar operations, correct functioning upon garbage input most often includes outputting garbage (GIGO).  This is clearly the case when using backward induction on the centipede game.

One of the standard assumptions in the centipede game is the following (from Part 1):

On the last turn, player two has a choice between stopping and getting $128 and passing and getting only $64. “Obviously”, s/he will choose to stop.

The puzzle from Part 1 was specifically designed to disprove this assumption.  If this is your strategy when you are player two, the game show host will, by the rules, be forced to stop before you have this choice.  If you make a similar choice when you are player one, you will never succeed in getting to the next round.  Of course, if you choose to always pass, you won’t make enough money to get to the next round via that method either.

Hint 1: The optimal strategy does not guarantee that you get to the next round — but it *does* give you a greater than 95% chance of doing so.

The “trick” is to offer the “self-interested” game show host “an offer he can’t refuse”.  If you were player one first, you could offer a strategy of always passing UNLESS the game show host stopped in the first game, in which case you stop immediately in game two.  Given a choice between 128 + 4 = 132 if he stops and 64 + 256 = 320 if he passes, the game show host must always pass as well.  But, alas, you are not going first (so as to prevent this strategy and the complaint that the two games are being tied together “inappropriately”).

Hint 2: The games should be considered separately and succeeding in stopping on your last turn in either game (both are possible) will move you on to the next round.

So how do you make it so that the game show host can’t prevent you from stopping?

According to the rules, the only way is to make it more worthwhile for him to let you reach that stopping point (remember his rules don’t care about how much you are making or whether you make it to the next round, they only care about how much money he gets to burn).

Hint 3: How do you “force” your opponent’s “optimal strategy” in a Nash Equilibrium?

WARNING!  SOLUTION IMMEDIATELY FOLLOWS!

 

WARNING!  SOLUTION IMMEDIATELY FOLLOWS!

 

WARNING!  SOLUTION IMMEDIATELY FOLLOWS!

 

centipede

WARNING!  SOLUTION IMMEDIATELY FOLLOWS!

 

WARNING!  SOLUTION IMMEDIATELY FOLLOWS!

 

WARNING!  SOLUTION IMMEDIATELY FOLLOWS!

 

The “trick” is to have your last turn strategies rely on the results of a future random event (like a coin-flip) that will give him an expected average outcome that is better than the outcome of his stopping before the event.  For example, assume that your strategy is to pass on your first two turns of each game and then flip a coin on the last.  In the first game, the game show host’s choices are to either stop at 64 or have a 50% chance of 32 and a 50% chance of 256 – for an expected average of (32 + 256) / 2 = 144.  Given a choice between 64 and 144, he can’t refuse the offer of 144.

Similarly, in the second game, he has a choice between stopping at 32 or having a 50% chance of 16 and a 50% chance of 128 and must choose the average of 72 over 32.

With this strategy, only being unlucky with both coin-flips (50% x 50% = 25%) prevents you from moving onto the next round.  But you can do *much* better.  The equilibrium point, where the odds must be for the expected outcome to equal that of stopping, is actually at a probability of one-seventh.  Any odds

better than one in seven, for example a die roll, will still force the game show host to allow the random event.  Now only a roll of “snake-eyes” (1/6 x 1/6 = 1/36 < 95%) will prevent you from moving on.

Of course, with your typical luck, that is exactly what you roll – winning only $96 of the needed $100.  Fortunately for you, that makes for bad television and you are moved on to the next round by the “statistical outlier” rule while the host cheerfully burns the maximum possible $384.


Backward induction is performed exactly like forward induction.  First, you prove that a single case is true.

Then, you prove that if a given case it true, then the neighboring case is true.  All cases of induction most often simply produce garbage if either of the two proofs is invalid.

The centipede game case errs by claiming to have proved the case of the last turn *in isolation* and then claiming that it is still solved identically in the context of a neighboring case.  But, realistically, once the previous turn is considered, there never exists a case of 64 vs. 128 which is a slam-dunk *unless* either the previous player is willing to accept 32 rather than 64 – OR – s/he believes that there is some probability that the answer to 64 vs. 128 is not a foregone conclusion in favor of the 128.  If neither is true, the previous player will stop and create the paradox of a choice which operates backwards in time to cause its own non-existence (like an evil AI black-mailing you from a possible future in order to ensure its creation).

Seeming paradoxes in logic *always* mean that either you don’t understand the problem or you’ve got faulty assumptions or both.  The most egregious “sins of game theory” aren’t where game theory is incorrect but where results derived under (and depending upon) very specific circumstances are inappropriately generalized and expected to hold when critical assumptions are invalidated under the generalization.  Another example of bad assumptions ruining backward induction is the so-called “hanged man paradox”.

As_HangedManAn arrogant reductionist was brought before the king who believed all reductionists to be a danger to his realm.  The reductionist knew that the king was good to his word and would not break it even if it meant releasing him so he quickly constructed a logical trap.  After being informed that he was going to be hanged in the current month and asked his last wishes, reductionist claimed that he loved surprises and asked that the date of his execution be a surprise and that he not realize it until he was told at 7:00 AM on the day of his hanging – or that the king relent and pardon him at the end of the month.

The king, being a great deal wiser and having seen this all before, acted confused but agreeable.  The reductionist immediately leapt on the chance and started “Well then, I can’t be executed on the last day of the month because then I would know the date and couldn’t be surprised.”  The king pondered and pondered and eventually doubtfully said “It would certainly seem so.”  So the reductionist continued “And I can’t be executed on the day before that because I know that I can’t be executed in the last day and therefore the next to last day is the only day possible, so I will know that it is then and won’t be surprised and can’t be executed.  The king looked even more doubtful and said “Are you sure?”  The reductionist excitedly claimed “Yes, absolutely” and went on to argue that he couldn’t be executed on any day of the month.

Now, the king really could have killed the reductionist at any time – since he would have been tremendously surprised to see his logic fail – but he had a lamentable fondness for baiting reductionists and wanted to make the most of the opportunity.  He amused himself during the month by periodically showing up at 7:00 AM and seemingly allowing himself to be talked out of the execution as unsurprising – as the reductionist started looking forward to his reprieve and going home.  And on the last day of the month, he sent the hangman in at 7:00 and the reductionist was executed after his last words of “But I knew that it had to be today so I couldn’t possibly be surprised and hanged.”

Comments are closed.