Is convergence to a Nash Equilibrium dependent on turn order?

Question

Is convergence to a Nash Equilibrium dependent on turn order? Namely, if you change the turn order or switch between synchronous (all players move at once) and asynchronous turns can the outcome change even if all other factors are held to be the same?

Answer 1

The answer to you question is YES.

Formally a game is a tuple $(S,f)$ where:

• $S_i$ is the strategy set for player $i$ (the set of actions he can take), $S = S_1 \times S_2 \times \dots \times S_n$ where $n$ is the number of player.
• $f_i: S \rightarrow \mathbb{R}$ is the payoff function of player $i$ associating every strategy profile $s\in S$ with a real payoff, $f = f_1 \times f_2 \times \dots \times f_n$

Whatever the game, a Nash equilibrium is an element $x\in S$ such that no player could benefit from an unilateral move, given what others play in $x$. Formally

• $x\in S$ is a Nash equilibrium iff, $\forall x_i' \in S_i, f(x_i,x_{-i}) \geq f(x_i',x_{-i})$, where x_i is the strategy of $i$ in $x$ and $x_{-i}$ the strategy of every agent but $i$ in $x$.

What matters to your question is that $S$ varies with the order of the moves. Consider a two agents game.

• $S_1$ = (playing Up at the same time that player 2 choses between Left or Right, playing Bottom at the same time that player 2 choses between Left or Right)

is a different strategy set than

• $S_1'$ = (playing Up after player 2 chose between Left or Right, playing Bottom after player 2 chose between Left or Right)

So, your formulation "if all other factors are held to be the same" should be understood as

1) The actions in the set of strategies (playing Up, Bottom, Right or Left) remain the same

2) The payoff associated to a combination of action (e.g. (Up,Right) or (Bottom,Left)) are also unchanged

3) But the strategy set of an agent changes in a fashion similar to $S_1$ and $S_1'$

Then the answer is clearly yes. Consider the classical Battle of the sexes game

(from Wikipedia)

The only (pure strategy) Nash equilibria in the simultaneous game are (Opera, Opera) and (Football,Football). Now if the column player moves first (typically associated with the men in the sexist interpretation of the game), the only Nash equilibrium is (Football, Football). Indeed, the strategy set of the column player is

• (play Opera knowing that the line player will play after me, play Football knowing that the line player will play after me)

But this is equivalent to

• (play Opera knowing that is I play Opera the line player will play Opera too, playing Football knowing that if I play football the line player will play Football too)

So for a strategy profile to be an equilibrium, $x_{column}$ must be Football. But if $x_{column}$ needs to be Football (for $x$ to be a NE), then $x_{line}$ needs to be Football too and (Football,Football) is the only NE.

As you ask the question in terms of convergence, you see that in the simultaneous game, you have a convergence issue, and depending on how you model your convergence process, both of the equilibria could be attained. In the sequential game however convergence is instantaneous.

There are other examples in which instead of moving from a pair of equilibria to a single equilibrium, changing the turns affects the only possible equilibrium. This is the case for instance when one move from a Cournot-competition game to a Stackelberg competition game. Starting out of equilibrium, it takes some time to reach a Cournot equilibrium. Not only is the Stackelberg equilibrium instantaneous, but it is also different from the Cournot equilibrium.