Repeated games can last a long time, and it turns out they also take a long time to write about. But the wait is over for the definitive book that Bob Aumann, in his foreword, notes was fifty years in the making.
Repeated Games, by Jean-François Mertens, Sylvain Sorin, Shmuel Zamir
Aumann has written a five page, fascinating historical foreword that is well worth reading. Here are a few paragraphs:
"The theory born in the mid to late sixties under the Mathematica-ACDA project started to grow and develop soon thereafter. For many years, I was a frequent visitor at CORE – the Center for Operations Research and Econometrics – founded in the late sixties by Jacques Dreze as a unit of the ancient university of Leuven-Louvain in Belgium. Probably my first visit was in 1968 or ’69, at which time I met the brilliant, flamboyant young mathematician Jean-Francois Mertens (a little reminiscent of John Nash at MIT in the early fifties). One Friday afternoon, Jean-Francois took me in his Alfa-Romeo from Leuven to Brussels, driving at 215 km/hour, never slowing down, never sounding the horn, just blinking his lights – and indeed, the cars in front of him moved out of his way with alacrity. I told him about the formula, in terms of the concavification operator, for the value of an infinitely repeated two-person zero-sum game with one-sided incomplete information – which is the same as the limit of values of the n-times repeated games. He caught on immediately; the whole conversation, including the proof, took something like five or ten minutes. Those conversations – especially the vast array of fascinating, challenging open problems – hooked him; it was like taking a mountain climber to a peak in the foothills of a great mountain range, from where he could see all the beautiful unclimbed peaks. The area became a lifelong obsession with him; he reached the most challenging peaks.
"At about the same time, Shmuel Zamir, a physics student at the Hebrew University, asked to do a math doctorate with me. Though a little skeptical, I was impressed by the young man, and decided to give it a try. I have never regretted that decision; Shmuel became a pillar of modern game theory, responsible for some of the most important results, not to speak of the tasks he has undertaken for the community. One problem treated in his thesis is estimating the error term in the above-mentioned limit of values; his seminal work in that area remains remarkable to this day. When Maschler and I published our Mathematica-ACDA reports in the early nineties, we included postscripts with notes on subsequent developments. The day that our typist came to the description of Zamir’s work, a Jerusalem bus was bombed by a terrorist, resulting in many dead and wounded civilians. By a slip of the pen – no doubt Freudian – she typed “terror term” instead of “error term.” Mike did not catch the slip, but I did, and to put the work in its historical context, purposely refrained from correcting it; it remains in the book to this day.
"After finishing his doctorate, Shmuel – like many of my students – did a postdoctoral stint at CORE. While there, he naturally met up with JeanFrancois, and an immensely fruitful lifelong collaboration ensued. Together they attacked and solved many of the central unsolved problems of Repeated Game theory.
"One of their beautiful results concerns the limit of values of n-times repeated two-person zero-sum games with incomplete information on both sides – like the original repeated Geneva negotiations, where neither the US nor the SU knew how many nuclear weapons the other side held. In the Mathematica-ACDA work, Maschler, Stearns, and I had shown that the infinite repetition of such games need not have a value: the minmax may be strictly greater than the maxmin. Very roughly, that is because, as mentioned above, using information involves revealing it. The minmax is attained when the maximizing player uses his information, thereby revealing it; but the minimizing player refrains from using her information until she has learned the maximizing player’s information, and so can use it, in addition to her own. The maxmin is attained in the opposite situation, when he waits for her. In the infinitely repeated game, no initial segment affects the payoff, so each side waits for the other to use its information; the upshot is that there is no value – no way of playing a “long” repetition optimally, if you don’t know how long it is.
"But in the n-times repeated game, you can’t afford waiting to use your information; the repetition will eventually end, rendering your information useless. Each side must use its information gradually, right from the start, thereby gradually revealing it; simultaneously, each side gradually learns the information revealed by the other, and so can – and does – use it. So it is natural to ask whether the values converge – whether one can speak of the value of a “long” repetition, without saying how long. Mike, Dick, and I did not succeed in answering this question. Mertens and Zamir did: they showed that the values indeed converge. Thus one can speak of the value of a “long” repetition without saying how long, even though one cannot speak of optimal play in such a setting. This result was published in the first issue – Vol. 1, No. 1 – of the International Journal of Game Theory, of which Zamir is now, over forty years later, the editor.
"The Mertens–Zamir team made many other seminal contributions. Perhaps best known is their construction of the complete type space. This is not directly related to repeated games, but rather to all incomplete information situations – it fully justifies John Harsanyi’s ingenious concept of “type” to represent multi-agent incomplete information.
"I vividly remember my first meeting with Sylvain Sorin. It was after giving a seminar on repeated games (of complete information, to the best of my recall) in Paris, sometime in the late seventies, perhaps around 1978 or ’79. There is a picture in my head of standing in front of a grand Paris building, built in the classical style with a row of Greek columns in front, and discussing repeated games with a lanky young French mathematician who actually understood everything I was saying – and more. I don’t remember the contents of the conversation; but the picture is there, in my mind, vividly.
"There followed years and decades of close cooperation between Sylvain, Jean-Francois, Shmuel, and other top Israeli mathematical game theorists...
******************
(The book seems to be available online for free to members of the Econometric Society, and here is some other information:
Cambridge Books Online http://ebooks.cambridge.org/
Book DOI: http://dx.doi.org/10.1017/CBO9781139343275 )
Repeated Games, by Jean-François Mertens, Sylvain Sorin, Shmuel Zamir
Aumann has written a five page, fascinating historical foreword that is well worth reading. Here are a few paragraphs:
"The theory born in the mid to late sixties under the Mathematica-ACDA project started to grow and develop soon thereafter. For many years, I was a frequent visitor at CORE – the Center for Operations Research and Econometrics – founded in the late sixties by Jacques Dreze as a unit of the ancient university of Leuven-Louvain in Belgium. Probably my first visit was in 1968 or ’69, at which time I met the brilliant, flamboyant young mathematician Jean-Francois Mertens (a little reminiscent of John Nash at MIT in the early fifties). One Friday afternoon, Jean-Francois took me in his Alfa-Romeo from Leuven to Brussels, driving at 215 km/hour, never slowing down, never sounding the horn, just blinking his lights – and indeed, the cars in front of him moved out of his way with alacrity. I told him about the formula, in terms of the concavification operator, for the value of an infinitely repeated two-person zero-sum game with one-sided incomplete information – which is the same as the limit of values of the n-times repeated games. He caught on immediately; the whole conversation, including the proof, took something like five or ten minutes. Those conversations – especially the vast array of fascinating, challenging open problems – hooked him; it was like taking a mountain climber to a peak in the foothills of a great mountain range, from where he could see all the beautiful unclimbed peaks. The area became a lifelong obsession with him; he reached the most challenging peaks.
"At about the same time, Shmuel Zamir, a physics student at the Hebrew University, asked to do a math doctorate with me. Though a little skeptical, I was impressed by the young man, and decided to give it a try. I have never regretted that decision; Shmuel became a pillar of modern game theory, responsible for some of the most important results, not to speak of the tasks he has undertaken for the community. One problem treated in his thesis is estimating the error term in the above-mentioned limit of values; his seminal work in that area remains remarkable to this day. When Maschler and I published our Mathematica-ACDA reports in the early nineties, we included postscripts with notes on subsequent developments. The day that our typist came to the description of Zamir’s work, a Jerusalem bus was bombed by a terrorist, resulting in many dead and wounded civilians. By a slip of the pen – no doubt Freudian – she typed “terror term” instead of “error term.” Mike did not catch the slip, but I did, and to put the work in its historical context, purposely refrained from correcting it; it remains in the book to this day.
"After finishing his doctorate, Shmuel – like many of my students – did a postdoctoral stint at CORE. While there, he naturally met up with JeanFrancois, and an immensely fruitful lifelong collaboration ensued. Together they attacked and solved many of the central unsolved problems of Repeated Game theory.
"One of their beautiful results concerns the limit of values of n-times repeated two-person zero-sum games with incomplete information on both sides – like the original repeated Geneva negotiations, where neither the US nor the SU knew how many nuclear weapons the other side held. In the Mathematica-ACDA work, Maschler, Stearns, and I had shown that the infinite repetition of such games need not have a value: the minmax may be strictly greater than the maxmin. Very roughly, that is because, as mentioned above, using information involves revealing it. The minmax is attained when the maximizing player uses his information, thereby revealing it; but the minimizing player refrains from using her information until she has learned the maximizing player’s information, and so can use it, in addition to her own. The maxmin is attained in the opposite situation, when he waits for her. In the infinitely repeated game, no initial segment affects the payoff, so each side waits for the other to use its information; the upshot is that there is no value – no way of playing a “long” repetition optimally, if you don’t know how long it is.
"But in the n-times repeated game, you can’t afford waiting to use your information; the repetition will eventually end, rendering your information useless. Each side must use its information gradually, right from the start, thereby gradually revealing it; simultaneously, each side gradually learns the information revealed by the other, and so can – and does – use it. So it is natural to ask whether the values converge – whether one can speak of the value of a “long” repetition, without saying how long. Mike, Dick, and I did not succeed in answering this question. Mertens and Zamir did: they showed that the values indeed converge. Thus one can speak of the value of a “long” repetition without saying how long, even though one cannot speak of optimal play in such a setting. This result was published in the first issue – Vol. 1, No. 1 – of the International Journal of Game Theory, of which Zamir is now, over forty years later, the editor.
"The Mertens–Zamir team made many other seminal contributions. Perhaps best known is their construction of the complete type space. This is not directly related to repeated games, but rather to all incomplete information situations – it fully justifies John Harsanyi’s ingenious concept of “type” to represent multi-agent incomplete information.
"I vividly remember my first meeting with Sylvain Sorin. It was after giving a seminar on repeated games (of complete information, to the best of my recall) in Paris, sometime in the late seventies, perhaps around 1978 or ’79. There is a picture in my head of standing in front of a grand Paris building, built in the classical style with a row of Greek columns in front, and discussing repeated games with a lanky young French mathematician who actually understood everything I was saying – and more. I don’t remember the contents of the conversation; but the picture is there, in my mind, vividly.
"There followed years and decades of close cooperation between Sylvain, Jean-Francois, Shmuel, and other top Israeli mathematical game theorists...
******************
(The book seems to be available online for free to members of the Econometric Society, and here is some other information:
Cambridge Books Online http://ebooks.cambridge.org/
Book DOI: http://dx.doi.org/10.1017/CBO9781139343275 )
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.