<p>If <i>p</i>=<i>q</i>=<i>s</i>=<i>t</i>=−1, then it is easy to see that a pure NE can be reached by local search starting from (<i>a</i><sub>3</sub>, <i>a</i><sub>3</sub>).  So in the rest of the proof, assume that at least one of <i>p</i>, <i>q</i>, <i>s</i>, and <i>t</i> is equal to 1.</p>

<p>If <i>p</i>=<i>q</i>=1, then (<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>) is a pure NE.  Similarly, if <i>s</i>=<i>t</i>=1, then (<i>a</i><sub>2</sub>, <i>a</i><sub>1</sub>) is a pure NE.</p>

<p>In the remaining cases, at least one of the pairs (<i>p</i>, <i>q</i>), (<i>q</i>, <i>p</i>), (<i>s</i>, <i>t</i>), and (<i>t</i>, <i>s</i>) is equal to (1, −1).  By symmetry, we may assume without loss of generality that <i>p</i>=1 and <i>q</i>=−1.  By assumption, <i>r</i>=1.  Then (<i>a</i><sub>1</sub>, <i>a</i><sub>3</sub>) is a pure NE.</p>

CC BY-SA 3.0
2014-11-28T17:04:33.123Z
2014-11-28T17:04:33.123Z
Tsuyoshi Ito
<p>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.</p>

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

<p>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.</p>

<p>Here is the game:</p>

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

<p>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: </p>

<pre><code>If p == 1 then r = 1
If s == 1 then x = 1
If q == 1 then z = 1
If t == 1 then y = 1
</code></pre>

<p>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.</p>

CC BY-SA 3.0
2014-11-26T18:37:50.210Z
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
CC BY-SA 3.0
2014-11-26T21:41:32.847Z
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
CC BY-SA 3.0
2014-11-26T21:49:24.417Z
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
<gt.game-theory>
How to prove the existence of a pure Nash equilibrium?
Chiba
# How to prove the existence of a pure Nash equilibrium?

(Asked by: username_0 on 2014-11-26)

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.

**Tags:** gt.game-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-11-28. Score: 5 | Accepted answer

If *p*=*q*=*s*=*t*=−1, then it is easy to see that a pure NE can be reached by local search starting from (*a*3, *a*3). So in the rest of the proof, assume that at least one of *p*, *q*, *s*, and *t* is equal to 1.

If *p*=*q*=1, then (*a*1, *a*2) is a pure NE. Similarly, if *s*=*t*=1, then (*a*2, *a*1) is a pure NE.

In the remaining cases, at least one of the pairs (*p*, *q*), (*q*, *p*), (*s*, *t*), and (*t*, *s*) is equal to (1, −1). By symmetry, we may assume without loss of generality that *p*=1 and *q*=−1. By assumption, *r*=1. Then (*a*1, *a*3) is a pure NE.


---

