Nash Equilibrium with Constraints on Decision Variables

Question

I am trying to solve a two player game with constraints on decision variables. The general structure looks something like this: $$\max_{x_1} f(x_1, x_2)$$ $$\max_{x_2} g(x_1, x_2)$$ subject to $$x_1 + x_2 \leq x_0$$ What might be a solution approach? or any direction to a resource for solving such problems would be highly appreciated.

Answer 1

Usually in (non-coopeative) game theory, one assumes that players take their actions independently.

In this sense, a players' set of feasible actions should be independent of the action taken by the other player. In your setting this is not the case as $x_1$ can only take values in $[0, x_0 - x_2]$ and $x_2$ can only takes values in $[0, x_0 - x_1]$ (assuming both $x_1$ and $x_2$ to be greater or equal to zero).

How does player 1 know that a choice greater than $x_0 - x_2$ is not allowed if she does not know the action $x_2$ of player 2?

• One solution could be to define $f(x_1, x_2)$ and $g(x_1, x_2)$ on the entire set $[0,x_0]\times[0,x_0]$ but to define the payoff functions to be very negative, say, $-\infty$ when $x_1 + x_2 > x_0$. Defining: $$ \tilde f(x_1, x_2) = \begin{cases} f(x_1, x_2) &\text{ if } x_1 + x_2 \le x_0 \\ -\infty &\text{ if } x_1 + x_2 > x_0 \end{cases} $$ $$ \tilde g(x_1, x_2) = \begin{cases} f(x_1, x_2) &\text{ if } x_1 + x_2 \le x_0 \\ -\infty &\text{ if } x_1 + x_2 > x_0 \end{cases} $$ The problems of player 1 and player 2 then become: $$ \max_{x_1} \tilde f(x_1, x_2) \text{ s. t. } x_1 \in [0, x_0]\\ \max_{x_2} \tilde g(x_1, x_2) \text{ s.t. } x_2 \in [0, x_0]. $$ Notice that a Nash equilibrium $(x_1^\ast, x_2^\ast)$ for such game (if it exists) will always have $x_1^\ast + x_2^\ast \le x_0$ as otherwise every player could improve his or her payoff by satisfying the constraint.

• A second option is to simply define the optimization problem of both individuals conditional on the action taken by the other player: $$ \max_{x_1} f(x_1, x_2) \text{ s.t. } x_1 \le x_0 - x_2\\ \max_{x_2} g(x_1, x_2) \text{ s.t. } x_2 \le x_0 - x_1. $$ The "Nash equilibrium" of this game will be the same as for the previous case.

• Anyway, if the payoff functions $f$ and $g$ are continuous and concave in their own strategies one can use Kakutani's fixed point theorem to show that there will always be a Nash equilibrium, i.e. a strategy $(x_1^\ast, x_2^\ast)$ such that $x_1^\ast+ x_2^\ast \le x_0$ and: $$ f(x_1^\ast, x_2^\ast) \ge f(x_1, x_2^\ast) \text{ for all } x_1 \le x_0 - x_2^\ast\\ g(x_1^\ast, x_2^\ast) \ge f(x_1^\ast, x_2) \text{ for all } x_2 \le x_0 - x_1^\ast. $$