Should both young men have decided to kiss the princess, no matter at what time she comes, then their chance of being the second one and escape the curse would have been 5/11 at any time, except at the first possible time, when this probability is obviously zero, and the last possible time, when this probability is one. To see this, note that if the princess arrives to one of them at five, say, then there are two possibe events: 1. She has chosen the times five to five and five, so he is second, or 2. She has chosen five and five past five, so he is first. The first event requires her to throw something else than a six in one more throw and hence is a factor 5/6 less likely than the second event, which makes the probability to be second equal to (5/6)/((5/6)+1)=5/(5+6)=5/11.

In reality, this probability is lower because of the probability that the young man she visits first does not kiss her, in which case she never visits the second one in that night. Mathematically, we can try to use game theory to decide which strategy is best for the competitors. To do this, we must first assign values to various outcomes. If the first young man decides to quit the game, then we assing to him a gain of -1, because of the shame of having given up, while the gain for the other one is 0. If the first young man decides to kiss and is duly turned into a frog, then his gain is -2, i.e., this is worse than being shamed. But the gain of marrying the princess is +20, so that our young adventurers are willing to take even a 10% chance of success, notwithstanding the risk, as in such a situation their expected gain is 0.1*20-0.9*2=0.2, which is still positive. (Admittedly, this is an old-fashioned fairy tale. They don't make many heros like that anymore.)

Mathematically speaking a strategy is a sequence of probabilities, that indicate for each time that the princess can arrive the probability that our adventurers at that time choose to kiss the princess. These probabilities can all be zeros or ones, in which case we speak of a deterministic strategy. For many games, there exists deterministic optimal strategies, but in some games, such as rock–paper–scissors, it is better to keep your opponent unsure of what you will do.

An optimal strategy corresponds to what mathematically is called a Nash equilibrium. This is a strategy with the property that if one player plays this strategy, then the other player cannot do better than to play the same strategy. It can be shown that such a Nash equilibrium always exists (although there may not always exist a deterministic one), but it need not be unique. For the game our princess has invented, it is easy to show that the only Nash equilibria are those strategies, where the players choose not to kiss the princess at any time before six in the morning. What they do if she arrives precisely at six is then irrelevant. In particular, this means that odd as that may sound, the strategy played by our prince Know-it-all is mathematically speaking optimal.

To see this, imagine that one of the competitors plays a strategy where he never kisses the princess before a certain time x, but does kiss the princess (at least with some positive probability) at time x. Then the other competitor can improve his expected gain by not kissing the princess at time x and doing at all other times exactly the same (with the same probabilities) as the first competitor. Indeed, in this way his chances of success are the same as for the first competitor at all times except for time x, when he makes a net gain, since at this time he can be sure not to be the second one to be visited.

Even though this proof is mathematically watertight, it is worth noting that the difference in expected gain between two nonoptimal strategies can be very small. Take, for example, the case that the first competitor kisses the princess at all times. In this case, the second competitor can maximize his expected gain by kissing her at all times except 8 pm sharp. A little calculation shows that in this case, the expected gain of the first competitor is about 8.999965 while the expected gain of the second competitor is about 9.0000018. On the other hand, if both competitors play an "optimal" strategy corresponding to a Nash equilibrium, then the expected gain for each of them is -0.5, since one of them will have to live with the shame of having given up.

This shows that according to the rules of game theory, our adventurers should never have entered the game in the first place. Also, while a Nash equilibrium is the best possible strategy if the strategy of your opponent is also a Nash equilibrium, it actually does pretty bad in terms of expected gain if your opponent plays something else. Nevertheless, it seems very hard to say what is the best strategy for adventurers who want to take the risk and can assume the same of their opponents. Kissing at 8 pm seems to make no sense in any scenario. But then neither does kissing at five past eight, and so on... (The game is in some ways similar to the Chainstore paradox, where the owner of a chain store can play agressive strategies that are not Nash equilibria but nevertheless seem to be good in practice, although it is impossible to say which is optimal. There is also considerable similarity to the Unexpected hanging paradox, Centipede game, and the Traveler's dilemma.)

If the princess is really clever, she can resolve the dilemma of the competitors as follows. She secretly instructs her jester, who is performing during the banquet, to spread the rumour that the whole competition is really just a great joke. In reality, he claims, she has long been relieved of her curse and only wants to put the man of her choice to the test, by knocking at his door already at eight. Only if he kisses her in this seemingly hopeless situation, he will be allowed to marry her. Initially, the two young men will probably not attach much belief to this story. This would change radically, however, if she should really arrive at eight. In this case, according to Bayes' rule, the competitors update the prior probabilities they attached to the truth or falseness of the rumour, by weighting them with the conditional probability of the evidence given each hypothesis. Since the probability of the princess arriving at eight is extremely small under the assumption that the rumour is false (about 1 : 563,465), but quite high under the assumption that the rumour is true (namely, 1 : 2), this means that if initially they gave the rumour just a chance of 1 : 10,000 to be true, after updating their information in the light of the new evidence, they give the rumour a 97% of being true. On other words, in such a situation, they will surely go for the kiss.

In reality, of course, the princess arrives with high probability only towards the end of the night, but nevertheless a minimal belief in the rumour, that moreover only has direct consequences in a very unlikely situation, is able to completely change the game in the sense that a new optimal strategy arises that has a higher expected gain for both competitors. (Nevertheless, in the new situation, the old optimal strategy of never kissing also remains a Nash equilibrium, so that the new game now has two Nash equilibria, similar to the well-known coordination game.)

Continue: read the fairy-tale epilogue or return to the fairy tale.