<p>Consider the zero-sum game <span class="math-container">$A = \begin{bmatrix}5 &amp; 3 \\ 4 &amp; -3\end{bmatrix}$</span>.  The interpretation is that Row Player chooses a probability distribution over Top and Bottom <span class="math-container">$\vec x = \begin{bmatrix}\Pr(Top) \\ 1 - \Pr(Top)\end{bmatrix}$</span>, Column Player chooses a probability distribution over Left and Right <span class="math-container">$\vec y = \begin{bmatrix}\Pr(Left) \\ 1 - \Pr(Left)\end{bmatrix}$</span>, and then each distribution is realized and Column Player pays Row Player the payoff.</p>
<p>As I understand, <span class="math-container">$\vec x^T A \vec y$</span> is the Lagrangian of the game's Linear Programming formulation, which turns out to be <span class="math-container">$6\Pr(Top) - 5\Pr(Top)\Pr(Left) + 7\Pr(Left) - 3$</span>.  I graphed this surface (from <span class="math-container">$-1$</span> to <span class="math-container">$2$</span> for context despite the inputs being probabilities).</p>
<p><a href="https://i.imgur.com/TmEP2o9.png" rel="nofollow noreferrer"><img src="https://i.imgur.com/TmEP2o9.png" alt="a surface showing that the Nash Equilibrium is not at the saddle point" /></a></p>
<p>The Nash Equilibrium (the green point on the graph) occurs at <span class="math-container">$(1, 0)$</span> (assigning all of Row Player's weight to Top and all of Column Player's weight to Right).  I expected this to occur at a saddle point.  There <em>is</em> a saddle point (the blue point on the graph) at <span class="math-container">$(\frac{7}{5}, \frac{6}{5})$</span>, but the two points do not coincide.  In fact, the Nash Equilibrium is not even as close to the saddle point as possible within the valid probability region, which would be the point <span class="math-container">$(1, 1)$</span>.</p>
<p>I did not know until recently that the term saddle point (also?) refers to the geometry of the discrete surface above/below a zero-sum game matrix obtained by treating the payoffs as heights, and the Nash Equilibrium behaves like a saddle point in that geometry.  Is that the only interpretation, or are Nash Equilibria (given certain conditions?) saddle points in the Lagrangian surface as well (I thought the Lagrangian surface was related to swapping player order in the sequential version of the game giving rise to the Minimax Theorem)?  Are the discrete surface and the Lagrangian surface related?</p>
<p>EDIT:  I have been asked to provide a Linear Programming formulation of the game.  I believe there are several arbitrary choices involved, and I derived the Lagrangian from the above formula without going through a particular Linear Programming formulation, so I'm not sure if my Lagrangian and Linear Programming formulation will &quot;match,&quot; but I think a possible formulation would be...<span class="math-container">$$\max\limits_{\Pr(Top)}\{\min\{5\Pr(Top) + 4\Pr(Bottom),\ 3\Pr(Top) - 3\Pr(Bottom)\}\} \\ s.t.\ \ \ \Pr(Top) + \Pr(Bottom) = 1 \\ \min\{5\Pr(Top) + 4\Pr(Bottom),\ 3\Pr(Top) - 3\Pr(Bottom)\} \leq 5\Pr(Top) + 4\Pr(Bottom) \\ \min\{5\Pr(Top) + 4\Pr(Bottom),\ 3\Pr(Top) - 3\Pr(Bottom)\} \leq 3\Pr(Top) - 3\Pr(Bottom) \\ \Pr(Top) \geq 0 \\ \Pr(Bottom) \geq 0$$</span></p>

CC BY-SA 4.0
2024-10-30T12:43:38.353Z
What is the game's "linear programming formulation"?
Michael Greinecker
CC BY-SA 4.0
2024-10-30T19:32:57.173Z
@MichaelGreinecker I have edited my attempt to write one into the post!
user10478
CC BY-SA 4.0
2024-11-01T11:54:01.180Z
Is there any theoretical result connecting your "linear programming formulation" to equilibria? It seems you are asking why different questions have different answers. One can interpret saddle points of the Lagrangian of a linear programming problem as the equilibria/saddle points of a zero-sum game in which one player chooses the variable to be maximized and the other the multipliers. You seem to ask about some opposite direction but do not mention any theoretical connection.
Michael Greinecker
CC BY-SA 4.0
2024-11-01T17:06:25.887Z
@MichaelGreinecker Yes, I am focused on the opposite direction as you describe.  I think the Linear Program is basically the algebraic view of the geometric view of Nash Equilibria for two player games where a player has just two actions, which graphs that player's expected payoff as a function of the probability that player assigns to one action (one line per opponent's action), and computes the maximum point on the lower "envelope" of those lines.  Here is a video showing how to write the Linear Program:  https://www.youtube.com/watch?v=XNJLO_N-LYE&list=PLKR57ZbLAFd5O5QOkxHEDUb09xodttpwP
user10478
<game-theory><optimization><nash-equilibrium>
Nash Equilibrium as a Saddle Point
user10478
# Nash Equilibrium as a Saddle Point

(Asked by: username_0 on 2024-10-29)

Consider the zero-sum game $A = \begin{bmatrix}5 & 3 \\ 4 & -3\end{bmatrix}$. The interpretation is that Row Player chooses a probability distribution over Top and Bottom $\vec x = \begin{bmatrix}\Pr(Top) \\ 1 - \Pr(Top)\end{bmatrix}$, Column Player chooses a probability distribution over Left and Right $\vec y = \begin{bmatrix}\Pr(Left) \\ 1 - \Pr(Left)\end{bmatrix}$, and then each distribution is realized and Column Player pays Row Player the payoff.

As I understand, $\vec x^T A \vec y$ is the Lagrangian of the game's Linear Programming formulation, which turns out to be $6\Pr(Top) - 5\Pr(Top)\Pr(Left) + 7\Pr(Left) - 3$. I graphed this surface (from $-1$ to $2$ for context despite the inputs being probabilities).

[![a surface showing that the Nash Equilibrium is not at the saddle point](https://i.imgur.com/TmEP2o9.png)](https://i.imgur.com/TmEP2o9.png)

The Nash Equilibrium (the green point on the graph) occurs at $(1, 0)$ (assigning all of Row Player's weight to Top and all of Column Player's weight to Right). I expected this to occur at a saddle point. There *is* a saddle point (the blue point on the graph) at $(\frac{7}{5}, \frac{6}{5})$, but the two points do not coincide. In fact, the Nash Equilibrium is not even as close to the saddle point as possible within the valid probability region, which would be the point $(1, 1)$.

I did not know until recently that the term saddle point (also?) refers to the geometry of the discrete surface above/below a zero-sum game matrix obtained by treating the payoffs as heights, and the Nash Equilibrium behaves like a saddle point in that geometry. Is that the only interpretation, or are Nash Equilibria (given certain conditions?) saddle points in the Lagrangian surface as well (I thought the Lagrangian surface was related to swapping player order in the sequential version of the game giving rise to the Minimax Theorem)? Are the discrete surface and the Lagrangian surface related?

EDIT: I have been asked to provide a Linear Programming formulation of the game. I believe there are several arbitrary choices involved, and I derived the Lagrangian from the above formula without going through a particular Linear Programming formulation, so I'm not sure if my Lagrangian and Linear Programming formulation will "match," but I think a possible formulation would be...$$\max\limits\_{\Pr(Top)}\{\min\{5\Pr(Top) + 4\Pr(Bottom),\ 3\Pr(Top) - 3\Pr(Bottom)\}\} \\ s.t.\ \ \ \Pr(Top) + \Pr(Bottom) = 1 \\ \min\{5\Pr(Top) + 4\Pr(Bottom),\ 3\Pr(Top) - 3\Pr(Bottom)\} \leq 5\Pr(Top) + 4\Pr(Bottom) \\ \min\{5\Pr(Top) + 4\Pr(Bottom),\ 3\Pr(Top) - 3\Pr(Bottom)\} \leq 3\Pr(Top) - 3\Pr(Bottom) \\ \Pr(Top) \geq 0 \\ \Pr(Bottom) \geq 0$$

**Tags:** game-theory, optimization, nash-equilibrium
> **Comments:**
> **username_1**: What is the game's "linear programming formulation"?  
> **username_0**: @MichaelGreinecker I have edited my attempt to write one into the post!  
> **username_1**: Is there any theoretical result connecting your "linear programming formulation" to equilibria? It seems you are asking why different questions have different answers. One can interpret saddle points of the Lagrangian of a linear programming problem as the equilibria/saddle points of a zero-sum game in which one player chooses the variable to be maximized and the other the multipliers. You seem to ask about some opposite direction but do not mention any theoretical connection.  
> **username_0**: @MichaelGreinecker Yes, I am focused on the opposite direction as you describe.  I think the Linear Program is basically the algebraic view of the geometric view of Nash Equilibria for two player games where a player has just two actions, which graphs that player's expected payoff as a function of the probability that player assigns to one action (one line per opponent's action), and computes the maximum point on the lower "envelope" of those lines.  Here is a video showing how to write the Linear Program:  https://www.youtube.com/watch?v=XNJLO_N-LYE&list=PLKR57ZbLAFd5O5QOkxHEDUb09xodttpwP  

---

## 0 answers

