You are currently browsing the monthly archive for August 2012.
In a previous post I described an infinite-horizon perfect-information game without a subgame-perfect equilibrium. Does there exist another refinement of Nash equilibrium that keeps the spirit of subgame perfection and is nonempty in every infinite-horizon perfect-information game?
One refinement of the concept of Nash equilibrium is that of trembling-hand equilibrium for extensive-form games, also called extensive-form perfect equilibrium. Call a strategy profile σ an extensive-form perfect equilibrium if there exists a sequence (σn) that satisfies the following properties:
- The sequence (σn) converges to σ.
- Under σn, each player in each of his decision nodes plays each action with probability at least 1/n.
- σn is a Nash equilibrium in the game Γn in which every player must play in each of his decision nodes each action with probability at least 1/n. (Note that the third requirement implies the second requirement).
Does every game admit such an extensive-form perfect equilibrium? The following example, to appear in a new paper of János Flesch, Jeroen Kuipers, Ayala Mashiah-Yaakovi, Gijs Schoenmakers, Eran Shmaya, your humble servant, and Koos Vrieze, is a variant of the example I provided here, and it shows that this is not the case. The conclusion is that at present we do not have any refinement of the concept of Nash equilibrium for infinite-horizon games that keeps the spirit of subgame perfection and is always nonempty.
I first met Jean-Francois Mertens while I was a graduate student at the Hebrew University of Jerusalem . He often visited the Center for Rationality at the Hebrew University and in one of those visits Abraham Neyman, my Ph.D. adviser, asked Mertens to sit with me and listen to my research.
Mertens has contributed to several areas in game theory.
His study of the min-max value and max-min value in general repeated games had a huge influence on the research in this area. The Mertens conjecture on repeated games with signals, stating that in zero-sum repeated games with signals, whenever player 1 knows everything that player 2 knows (that is, the signal of player 1 contains the signal of player 2), then the limit of the n-stage game converges to the max-min value, has been the starting point of many works in this topic, and is still open, though recently some advances has been made to solve it.
His contribution to the Shapley value in games with continuum of players includes the extension of the diagonal formula, that historically applied to smooth nonatomic games, to a larger class of games that includes nondifferentiable and also discontinuous games.
For me, his most significant contribution is to the area of stochastic games, where he proved, together with Abraham Neyman, that every two-player zero-sum stochastic game has a uniform value. When Mertens and Neyman proved this result I was still in elementary school. The story I heard about the inception of this result is that in a workshop at CORE on repeated games in the Winter of 1978–1979, Sylvain Sorin was giving a talk on the Big Match, which was the first nontrivial two-player zero-sum undiscounted stochastic game that was solved. For Abraham Neyman, who was sitting in the audience, this was the first encounter with repeated games and stochastic games, and so he asked many questions, ranging from basic to ideas of extending the result to general stochastic games. Jean-Francois Mertens, who was sitting in the audience as well, patiently answered Neyman’s questions and explained why each route that Neyman suggested to extend the result is bound to fail. Like two swordmen, Neyman made another suggestion and Mertens fended it off. The result of this match was one of the most beautiful papers in game theory.
I met Jean-Francois Mertens at Toulouse in September last year, during the conference that Jerôme Renault organized. We had a dinner together. During the conference Mertens was very tired, and when he was back to Belgium he was diagnosed with a lung cancer in an advanced stage. He passed away on the night of July 17, 2012. We will all miss him. יהי זכרו ברוך