4
$\begingroup$

I'm trying to figure out a Nash Equilibrium for a 3x3 zero-sum game, and it's not following normal patterns (or I'm making a huge oversight, in which case I'll feel stupid!). Can anyone help me?

The payoff matrix for P1 is (additive inverses for P2):

0.0 0.0 1.0

1.5 3.0 -0.5

-1.5 -2.0 1.5

As far as I can tell, nothing is dominated for either player. Doing the usual calculations where you find probabilities each player makes each play such that the other player is then indifferent to his plays yields negative probabilities though...not sure what's wrong with what I'm doing.

Thanks in advance!

Edit: Some more thinking has led me to believe that I don't think I'm doing this wrong, and that there's a reason I wasn't explicitly taught to do this. It seems to be equivalent to a LP problem in the 3x3 case (and in the general nxn case) where no strategy is strictly dominated, and where there's no pure strategy equilibrium. My confusion arose from the fact that I know a Nash equilibrium is guaranteed to exist -- I guess I was taking that to mean that I should be able to calculate one easily. :)

$\endgroup$
  • $\begingroup$ There is no pure strategy equilibrium, if with additive inverse you mean that any positive payoff for P1 is a negative payoff for P2. That makes sense, since every cell that P1 likes would then be disliked by P2. But there should exist a mixed strategy equilibrium. Keep looking. $\endgroup$ – Nameless Oct 31 '13 at 10:58
  • $\begingroup$ I'd also be curious about what the mixed strategy NE is. I tried to do the same calculations, and also got nonsensical probabilities. I would think that the equations that work for the 2x2 case work here too, because they are based on a general principle. But they seem not to... $\endgroup$ – Balazs Rau Apr 7 '14 at 6:34
2
+50
$\begingroup$

The Nash equilibrium I got was:

p[1] == 1/2 && p[2] == 1/2 && p[3] == 0 && q[1] == 3/4 && q[2] == 0 && q[3] == 1/4

where p is the vector of probabilities of player 1 and q is of player 2.

As the previous answer pointed some strategies have zero probabilities. You equate payoffs only of strategies that are played with positive probability.

If you want an automatic way of computing equilibria of games like this, you may want to check this link (the code is in Mathematica):

http://www.mathematica-journal.com/2014/03/using-reduce-to-compute-nash-equilibria/

If you want to use pencil and paper. First guess what strategies have positive prob and which have zero prob. Second compute the expected payoff of all strategies. Check all strategies that have positive prob. have the same payoff and that this payoff is no less than the payoff of a strategy with zero prob. If no results, try another guess. It is a force brute method. For each player you have lots of cases to consider: $2^n-n-1$ where $n$ is the number of strategies.

$\endgroup$
  • $\begingroup$ I don't know Mathematica unfortunately. Is that algorithm the same as described here: youtube.com/watch?v=aa8USttcDoE It is based on calculating what probabilities a player should have for all his options so that her opponents expected return does not depend on what of her options she chooses. $\endgroup$ – Balazs Rau Apr 7 '14 at 22:27
  • $\begingroup$ So it is possible to have 0 probability in a NE even if that strategy in not dominated, either weekly or strongly. $\endgroup$ – Balazs Rau Apr 7 '14 at 22:30
  • $\begingroup$ @BalazsRau: yes off course: if it is strictly dominated it must have zero prob. but you can have zero prob. even if it is not strictly or weakly dom. $\endgroup$ – Sergio Parreiras Apr 7 '14 at 22:31
  • $\begingroup$ The hard part of finding mixed strategy Nash is to discover which strategies have positive prob. and those that have zero prob. $\endgroup$ – Sergio Parreiras Apr 7 '14 at 22:32
  • $\begingroup$ 2 x 2 cases are easy because any strategy that is not pure (i.e. any mixed) must put positive prob in all strategies $\endgroup$ – Sergio Parreiras Apr 7 '14 at 22:33
1
$\begingroup$

There exists a mixed-strategy Nash equilibrium, but some strategies have $0$ weight in that equilibrium.

$\endgroup$

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.