I'm reading a paper on solving an optimization problem for a non-convex function. This paper is suggesting a method using a game theoretic approach:

Optimizing the Lagrangian can be interpreted as playing a two-player zero-sum game: the first player chooses $\theta$ to minimize $L(\theta, \lambda)$, and the second player chooses $\lambda$ to maximize it.

where $\theta$ is model parameter and $\lambda$ is Lagrangian multiplier. I was wondering if you could interpret the following for me:

Figure shows a case in which a pure Nash equilibrium of the Lagrangian game does not exist. The plotted rectangular region is the domain $\Theta$, the contours are those of the strictly concave minimization objective function $g_0$, and the shaded triangle is the feasible region determined by the three linear inequality constraints $g_1, > \dots, g_3$. The red dot is the optimal feasible point. The Lagrangian $L(\theta, \lambda)$ is strictly concave in $\theta$ for any choice of $\lambda$, so the optimal choice(s) for the $\theta$-player will always lie on the boundary of the plotted rectangle. However, these points are infeasible, and therefore suboptimal for the $\lambda$-player.

enter image description here

I attempted to decipher this starting with the Nash equilibrium, what it means in this context, and how is that different from pure Nash equilibrium.

A Nash Equilibrium is a stable pair of strategies (could be randomized). Stable means that neither player has incentive to deviate on their own.

How is this different from

A pure Nash equilibrium is a strategy profile in which no player would benefit by deviating, given that all other players don't deviate

  • $\begingroup$ I don't want to ask multiple questions, so I'm striking the last lines out in case it is deviating from the main question $\endgroup$ – Blade Jun 18 '20 at 2:18

Nash eqm allows players to use random strategies, so they can play each pure strategy with some probability. Pure Nash means that the players each use a single strategy with probability 1. Rock-paper-scissors is a game with a Nash eqm but no Pure-strategy Nash eqm.

The Lagrangian question is more complicated. The Lagrangian looks like $$ \mathcal{L}(\theta,\lambda) = f(\theta) + \lambda g(\theta) $$ with FONCs $$ \nabla f(\theta^*) + \lambda^* \nabla g(\theta^*) = 0 $$ $$ g(\theta^*) = 0. $$ You can think of the first condition as one player minimizing $\mathcal{L}(\theta,\lambda)$ over $\theta$, taking $\lambda$ as given; let's call $\theta$ that player's strategy. But what is going on with the second condition? It has the flavor of an optimization condition, since we are differentiating something and setting it equal to zero. But the problem is linear in $\lambda$, and the FONC does not identify whether we're talking about a maximum or a minimum.

It turns out that for a Lagrangian, $$ \mathcal{L}(\theta^*,\lambda) \le \mathcal{L}(\theta^*,\lambda^*) \le \mathcal{L}(\theta,\lambda^*), $$ at an optimum, which is often called the Saddle Point Theorem (e.g., "Nonlinear Programming", Bertsekas, p. 499). So if you think of it as a game where the $\theta$-player is taking $\lambda$ as given and minimizing $\mathcal{L}$, and the $\lambda$-player is taking $\theta$ as giving and maximizing $\mathcal{L}$, a critical point of the Lagrangian can be thought of as a pure-strategy eqm point of a zero-sum game, where neither player can gain by deviating to another $\theta$ or $\lambda$. The right-hand inequality says that faces with $\lambda^*$, the $\theta$-player can do no better than play $\theta^*$, and the left-hand inequality says that, faced with $\theta^*$, the $\lambda$-player can do no better than play $\lambda^*$. It is a pure-strategy Nash eqm.

This comes up endlessly in duality theory. See, for example, https://math.unice.fr/~auroux/EPU/Optim4.pdf . The game theory interpretation is actually how I teach Lagrangians to undergrads! If you want a good reference for duality and duality gaps, I'd look at the Bertsekas book for a start. That is a great book.


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.