# How to prove the existence of a pure Nash equilibrium?

I have a game as given by the table below. I would like to prove that the game has always at least one pure Nash equilibrium (NE). I used a computer program and in fact the game has a pure NE. So, I am claiming the existence of at least one pure NE.

I looked in the internet but most of the paper that I read are talking about general games.

I need to know what do I need to know and to do in order to prove my claim? I do not want to give me the whole answer (if you have any), just give the tools and some hints and that would be appreciated. Also, can you give, in general, situation, how to prove the existence of a pure NE? Thank you.

Here is the game:

$$\begin{array}{c|c|c|c|} P1\backslash P2 & \text{a_1} & \text{a_2} & \text{a_3} \\ \hline \text{a_1} & (-1, -1) & (p, q) & (r, 0) \\ \hline \text{a_2} & (s, t) & (-1, -1) & (x, 0) \\ \hline \text{a_3} & (0, y) & (0, z) & (0, 0) \\ \hline \end{array}$$

You can see that it is a 2 players ($P1$ is the row player and $P2$ is the column player) game where each player has the action space $\{a_1, a_2, a_3\}$. Here $p,q,r,s,t,x,y,z$ are integers in the set $\{-1, 1\}$ which are related to each others by:

If p == 1 then r = 1
If s == 1 then x = 1
If q == 1 then z = 1
If t == 1 then y = 1


My algorithm that I used is a brute force one that search for all possible values of $p,q,r,s,t,x,y,z$ and then see for each possible value if there is a pure NE or not.

• I don't understand what your question is. You found pure NE by computer search. A proof that a pure NE always exists is the list of strategy pairs for all values of the variables. Also I think the question is too localized if you are asking about this game. Asking for general methods is more appropriate. In that case potential games are a general class of games that have pure NE. – Sasho Nikolov Nov 26 '14 at 18:37
• Given the game above, I would like to prove that there is at least one pure Nash equilibrium. Of course, using my brute force algorithm, I have a proof but I want to give a mathematical proof. – Chiba Nov 26 '14 at 21:41
• Writing down the result of your brute force search for each valid setting of $p, q, r, s, t, x, y, z$ is a mathematical proof. Not a very concise one, but not every provable fact has a concise proof, and it's not clear why there should be anything better to do for your arbitrary-looking game. – Sasho Nikolov Nov 26 '14 at 21:49