News :: story cache

Game theory in the popular press.

Mathematics: The big match

(News & Views)
Ivar Ekeland
June 4, 1998
text is a cache of

One of the oldest problems in game theory, known as the big match, has just been solved by the French mathematician Nicolas Vieille. Let me tell it as a story.

Once upon a time there was a king, powerful and wise. He called in his trusted minister and told him: "Today I will leave, and in my absence, I put you in charge of my kingdom. You will not hear from me again until the day of my return, if I ever come back. On that day, if I find you hard at work at my desk, you will become king in my place, and you will live in this palace for ever and ever. If, on the other hand, I find you idling, enjoying the perks of office, you will be put in chains and imprisoned in a dungeon where you will be tormented for ever and ever. Be aware that every night I will be informed of how you spent the past day, and I can always come back the next day."

What should the minister do, assuming that the king will use the system to his own advantage? If he spends the whole time working, then the king, being informed that he is at his desk every day, will expect him to go on showing up every morning for work, and will not come back, so the minister can only look forward to a lifetime of work. If he spends every day enjoying the good life, he can be assured that the king, being duly informed of his misdemeanour, will come back to chastise him and will indeed find him idling, so that he can look forward to the bottomless pit. In neither case will he have any chance of catching the king out by being at work on his return, and so become king himself.

Somewhere in between the two extremes of 'always work' and 'always shirk', there must be a compromise that blends working and shirking in an optimal manner. But this compromise is hard to find. Every day, as he wakes up, the minister has to balance the pleasure of shirking against the risk of the king coming back today, based on his information yesterday. He must also bear in mind that by shirking today, he is increasing the likelihood that the king will come back tomorrow. As he wakes up tomorrow, he may judge the new risk unacceptable, and find himself forced to go to work; in other words, by shirking today, he may be committing himself to work tomorrow.

His difficulties, as always in game theory, are compounded by the fact that the king is perfectly able to put himself in his minister's shoes. So if, for instance, there were a way for the minister to reach a definite conclusion as to whether he should work or shirk today, the king, having precisely the same information (namely, what the minister did yesterday and the days before), would reach the same conclusion, and take advantage of it — returning if the minister planned to shirk, and staying away if he planned to work. The way out is to resort to probabilistic strategies: as he wakes up, the minister decides on certain probabilities with which to work or shirk, and then casts lots to find out what he will actually do. Similarly, the king will throw dice every morning to find out whether to return or to stay away, only needing to decide the odds for returning or staying away.

This problem was first stated by Gillette in 1957. Its solution depends on the values the minister and the king attach to the different outcomes, and also on the way they value the future, compared with the present. In 1968, Blackwell and Ferguson found the solution to the particular case when the king and the minister have exactly opposite interests (say, for instance, that if the minister is caught, he can stay out of jail by paying every day a large amount of money M to the king, and that if the king is caught out, he can keep his kingdom by paying the minister this same amount M every day). They proved that, if everyone holds a long-range view, the best strategy for the king is to choose at the outset some large number N, and then to compute every morning the number D = N + A - B, where A is the number of days the minister has worked since the game began and B the number of days he has shirked. The king then assigns a probability p = 1/D2 to coming back and throws dice to that effect. As for the minister, his best policy is to flip a fair coin every morning and to work if it comes up tails. Note that, as long as A is close to B, the probability of the king returning today is close to the constant 1/N2.

After this solution, things stalled for ten more years, until Mertens and Neyman extended the result to games with more than two possible outcomes, and where chance comes in more complicated ways. But they were still restricted to zero-sum games, that is, where one player's loss is exactly the other's gain. Non-zero-sum games have more general payoffs, allowing both players to win in some outcomes, and thereby encouraging some degree of cooperation. But the question of whether such games also could be solved eluded researchers for 20 more years.

Finally, Vieille has proved that they can all be solved. It is an extremely long proof, which spans a series of four difficult papers. It is not a constructive proof, in the sense that in most cases one would not be able to actually give the solution, as I did in the preceding story: one would just know that it exists. However, it is an outstanding achievement, requiring extremely sophisticated tools from all sides of mathematics, from ergodic theory to algebraic geometry. It gives us a new class of models with which to study conflict and cooperation — models that will certainly find their way into the study of social interactions and economics.

Nature Macmillan Publishers Ltd 1998 Registered No. 785998 England.