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.
There are two players, Alice and Bob. Alice is the active player at the beginning of the game, at stage 1. The play proceeds in blocks, the length of block k is k stages. The identity of the active player is determined at the beginning of the block, and that player remains active until the block ends. In each decision node the active player has two actions, A and B. If the active player chose A in at least 50% of the stages of the block, then Alice is the active player in the next block. Otherwise, Bob is the active player in the next block. Note that when a player has to choose each action with probability at least 1/n, then even if the active player chooses Alice with probability (n-1)/n, there is a positive probability that Bob will be the next active player.
Payoffs are as follows:
- If there is some stage t such that Alice is the active player in all stages after t, then the payoff is (-1,2).
- If there is some stage t such that Bob is the active player in all stages after t, then the payoff is (-2,1).
- Otherwise the payoff is (0,0).
Call this game Γ. This game is in fact the same game as the one I gave in the previous post: every stage in that game translates into one block in the present game.
Let Γn be the version of the game in which each action has to be chosen with probability at least 1/n. It turns out that for every n, the game Γn has no Nash equilibrium. In particular, an extensive-form perfect equilibrium does not exist.
How can we prove that? Standard approximations of the normal distribution show that if Alice plays the stationary strategy [(1-1/n)(A), (1/n)(B)] in which she chooses A with probability 1-1/n and B with probability 1/n, then for every positive ε there is T such that with probability at least 1-ε Alice will be the active player after stage T. This property holds because the size of the blocks increase, so that the probability that Alice chooses B more than 50% of the time when she plays [(1-1/n)(A), (1/n)(B)] shrinks to 0 at a rate which is faster then geometric. Arguments similar to those given here show that the game Γn has no subgame-perfect equilibrium, hence no Nash equilibrium.