Mr. Pity was a very, very unlucky man. As a kid he had once accidentally stepped on a butterfly in the forest. But this was no ordinary butterfly! It was the most beautiful butterfly Nature had ever produced. Out of revenge, Nature cursed young Mr. Pity: “Whatever you do, I’ll try to make your life as miserable as possible!”

Now, Nature’s curse became evident every time Mr. Pity faces a decision in which uncertainty is involved. For Nature is the one that pulls the strings in all probabilistic situations. Thankfully, however, the Creator had been wise enough not to give Nature too much power. Nature does not have the power to decide the outcome of every probabilistic event, but it does have the power to influence probability distributions.

For instance, suppose Mr. Pity bets one dollar on the outcome of a coin. If he predicts the outcome correctly, he receives a dollar; if he is wrong he loses a dollar. Moreover, we know that the coin is at most 10% off from being fair (i.e., the probability of heads () is between 40% and 60%). Now, if Mr. Pity bets on heads, then Nature will make sure that the probability of heads is as small as possible ( in this case). On the other hand, if Mr. Pity bets on tails, then Nature will change the probability of heads to ). So whatever Mr. Pity chooses, his expected profit is negative: -$0.20.

After years of struggling and losing bets, Mr. Pity was fed up with the situation and turned to the Creator. “Dear Creator,” he said, ”I am grateful for most things you’ve created in this world, but I’m afraid you’ve overlooked one thing: You have given Nature too much power! You’ve allowed Nature to decide upon probability distributions after having observed my decisions,” he complained. “This second-mover advantage makes her extremely powerful. If you’re not careful, she’ll use these powers to threaten your position as the highest god!”

The latter comment convinced the Creator to revise his creation. He summoned Nature to his court and told her: “From now on, whenever you are trying to make someone’s life miserable by choosing unfortunate probability distributions, you have to go through the following process. You write down your probability distribution of choice, and your victim writes down their action of choice. You both hand these over to me and I show each of you what the other has decided. Then, you both have the option to revise your decision. This process repeats until both of you don’t want to revise anymore.” Nature laughed in reply and said: “well, be ready for some long sessions then!”

A few days later, Mr. Pity decided to try out his (revised) luck and make a coin flip bet again. He handed in his choice “heads”, and Nature handed in . Mr. Pity read Nature’s choice and laughed: “Ha, not this time, Nature!” and he changed his bet to “tails”. Smiling from ear to ear in expectation of his fortunate bet, the Creator came back to him with the message: “Nature’s changed her decision to ”. A little surprised, but still smiling, Mr. Pity just changed his bet to “heads” again. However, after 10 repetitions of this revision process, it was clear that Mr. Pity and Nature were never going to agree about their decisions.

Neither was going to give up though. Mr. Pity was determined not to be unlucky for the first time in his life, while Nature was angry with both Mr. Pity — for killing her butterfly — and the Creator — for taking away her second-mover advantage. The Creator was fed up with the situation, though, and he shouted: “This is insane! We need another rule change. I summon John Nash from the dead!”

John Nash, the mathematician, was taken from his resting place and taken to the Creator’s throne. The Creator spoke: “Mr. Nash, you’re famous for having invented this thing called game theory. I believe you might help me solve this situation I’ve got on my hand here.” The Creator explained the problem and Mr. Nash immediately started laughing. “Oh, you got yourself in an impossible situation, Mr. Creator, haha! Evidently, there is no pure-strategy Nash equilibrium in this zero-sum game. But of course, it is very clear that there does exist a mixed-strategy Nash equilibrium. Just give Mr. Pity the option to use a mixed strategy, and your problem will be solved!”

“Ah, of course!” the Creator replied. But, ehm, could you please elaborate a bit?” (For a supreme god, the Creator had never been really good at math.) Mr. Nash continued: “Just allow Mr. Pity to hand in his strategy in terms of probabilities. Something like `30% heads, 70% tails’. Then this whole game will work out smoothly. Well, that is, then at least there exists a possibility of this game coming to an end, hahaha!” Not completely understanding this last remark, the Creator nodded and said: “Of course! But what about Nature? Shouldn’t I give her the same option? She is already angry with me for taking away her second-mover advantage.” Mr. Nash laughed again and said: “Hahaha, sure, why not? If that makes her happy, hahahahaha!” This time, Mr. Nash didn’t stop laughing and he had to be dragged away from the court.

The next day, while still a bit confused about all this laughter, the Creator summoned Mr. Pity and Nature again and explained the new rules. Both were content with the new rules, it only seemed fair that they both got the same new possibility of using a mixed strategy.

In all his misfortune, Mr. Pity had learned that being clever was the only way to survive. So after thinking about his new possibilities, he said “eureka!” and he wrote down his strategy “50% heads, 50% tails”. Meanwhile, Nature didn’t really understand her new powers (thinking about probabilities was always a bit confusing to her), and she just went with her gut: “50% chance that ; 50% chance that ”.

Having handed in their decisions at the court of the Creator, they both received the other player’s decision. Nature first read Mr. Pity’s strategy and she soon realized that whatever probabilities she chose, Mr. Pity’s expected outcome would always be exactly $0.00. So she didn’t bother to revise her strategy. Meanwhile, Mr. Pity opened the note with Nature’s strategy and immediately burst out in laughter (it sounded surprisingly similar to Mr. Nash’s laughter the day before). “She really doesn’t understand probabilities!” he exclaimed. “She could just as well have written down !” He didn’t feel the need to revise his strategy, but he couldn’t resist writing down “ + ” on the back of the note.

The Creator, after receiving back the notes without any request for revision, sighed in relief. Finally, this whole probabilistic game-theory business was over and he could go back to his favorite activity: eating ambrosia and drinking nectar.

Returning home from the Creator’s court, Mr. Pity felt a great relief. Finally, his days of misfortune were over; at least when it came to his favorite activity: betting on coin flips. He lay down in bed and thought things over again. After a few minutes, he smiled and exclaimed: “Thanks to Mr. Nash, I went from being the most unfortunate man alive to the only man alive that knows that every coin he bets on will be a fair coin!”

Background and motivation

In stochastic optimization we consider decision-making problems under uncertainty. That is, we have to make a decision while the value of some of the parameters in the model is not known yet with certainty. To deal with this uncertainty, we usually assume that we know the probability distribution of the uncertain parameters. Then, we aim to find a solution that results in the best expected outcome (i.e., the lowest expected objective value). Mathematically, we solve the following problem:

where is the cost function, depending on the decision and the random vector .

In practice, however, we often don’t know . For instance, sometimes the only information we have to our disposal is a sample of historical data points, but we do not know from which distribution this sample came. In other words, we are dealing with distributional uncertainty.

One approach to deal with this issue would be to fit a distribution to this sample and then solve the resulting problem under this estimated distribution. However, we will inevitably make an estimation error and it is not immediately clear how this error propagates to the optimal solution/objective value. Hence, we have no guarantee that the resulting solution is any good!

Another, more conservative approach is that of distributionally robust optimization (DRO). Here we assume that the only knowledge we have about our distribution is that it is inside some collection of distributions, called the uncertainty set . We then search for a solution with the best objective under the worst possible distribution . That is, we solve the DRO problem

Now, if we know that the true distribution is an element of , then we know that the expected performance of our solution will be at least as good as the optimal value for our DRO problem. Or mathematically, . So this approach yields a performance guarantee.

A downside of this approach is that it is very conservative. One reason for this is that we let “Nature”, who picks , decide the distribution after we have decided on . So Nature has the power to pick a distribution that is particularly bad for the choice that we made. In game-theoretic terms, Nature has the second-mover advantage. In practice, we see that this issue leads to extremely conservative choices for , which is not always desirable.

Now, Dr. Ward Romeijnders and I were wondering what would happen if we take away the second-mover advantage from Nature and instead consider a simultaneous game. When choosing , we still need to take into account that Nature is trying to find the worst possible , so we are still hedging against distributional uncertainty. However, since Nature has lost some of its power, we expect to find a solution (i.e., a Nash equilibrium) that is less conservative than before.

The story above is a first attempt to answer our question what happens when we make this adjustment to a simultaneous game. The most interesting observation so far is that any mixed strategy for Nature reduces to a pure strategy (a distribution of distributions reduces to a single distribution). We are very interested to find out what this means for solutions to these problems.

Please note that this article is based on the research of Dr. Ward Romeijnders and Ruben van Beesten (PhD candidate).

This article is written by Ruben van Beesten