In a $n$-player zero-sum game, one of the players, say $k$, unilaterally deviates from her Nash equilibrium strategy while all the other players stay on the equilibrium.

Now, we all know that $k$'s payoff cannot increase for her deviating move, but I wonder if we can say anything further about $k$'s payoff in this case. Must it always be nonpositive? Can we establish a lower-bound for $k$'s payoff? Or do all of these depend on the specific payoff function of the game?

  • $\begingroup$ Can you define "unilaterally deviates"? The answer to your question "Must it always be nonpositive?" definitely depends on this. As to your question "Can we establish a lower-bound for k's payoff?", I am almost sure that the answer is it depends on the specific payoff function even without knowing the definition of unilateral deviation. If I had to guess, I'd say the answer to the first is the same. $\endgroup$ Jan 4 '12 at 6:51
  • $\begingroup$ What is an n-player zero-sum game? If it is simply a normal-form game with a payoff-function that always sums to $0$, the answers are: No, no, and yes. You can construct the examples with two players and add $n-2$ dummy players with constant payoff zero. $\endgroup$ Jan 4 '12 at 6:53
  • $\begingroup$ @AlexBecker, by "unilaterally deviates", I mean player $k$ plays a strategy other than her equilibrium strategy, while all the other players play their respective equilibrium strategy. $\endgroup$
    – balllib
    Jan 4 '12 at 7:03
  • $\begingroup$ There may not be equilibrium strategies for $n \gt 2$. $\endgroup$
    – Henry
    Jan 4 '12 at 8:38
  • $\begingroup$ @MichaelGreinecker, could you please elaborate a bit more on the construction of the examples using two players plus $n-2$ dummy players. thanks. $\endgroup$
    – balllib
    Jan 4 '12 at 9:44

I will answer the questions for two-player zero-sum games and then show how to extend them to the general case.

  1. Let player Alice have two strategies, $L,R$ and player Bob two strategies $T,B$. Let the payoff of Alice and Bob be constant, for every strategy profile, Alice receives a payoff of $1$ and Bob a payoff of $-1$. The game is clearly zero-sum and every strategy profile is a Nash equilibrium. Moreover, when Alic deviates from any Nash equilibrium, she still gets the positive payoff $1$.

  2. Now lets consider a family of games parametrized by $\alpha>0$ with the same strategies, but the payoff of Alice is given by $u_A(L,T)=u(L,B)=\alpha$ and $u_A(R,T)=u_A(R,B)=-\alpha$. The payoff of Bob is given by $u_B=0-u_A$. This is clearly a zero-sum game for every $\alpha$ and a Nash equilibrium is any strategy profile in which Alice plays $L$. Her loss from switching to $R$ is $2\alpha$ and that can be made arbitrarily large by increasing $\alpha$.

So for two-player, zero-sum games, the answer to both questions is no. Now we can add any numbers of players with arbitrary finite strategy spaces by letting their payoff be constantly $0$ and their actions not affect the payoff Alice and Bob get. This allows us to extend the examples above to any number of players and show that the answer is no in both cases again.

It should be remarked that even though the examples are somewhat pathological and non-generic, one can construct more complicated generic examples. A special case that is natural for zero-sum games are games where all euilibria are completely mixed, that is where every strategy is played with positive probability. In such an equilibrium, the cost of deviating is always zero.

As a final remark, $n$-player zero sum games are rather pointless. We can always add a dummy player who doesn't effect anyone elses payoff and gets the sum of payoffs of all others times $-1$. So every $n$-player game can be interpreted as a $(n+1)$-player zero-sum game.

  • $\begingroup$ that's informative. Thanks Michael. $\endgroup$
    – balllib
    Jan 5 '12 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.