6

Assume a two player symmetric game where the payoff for the row player is given by: $$ A = \left( \begin{array}{cc} a_{1,1} & a_{1,2} &\cdots & a_{1,n}\\ a_{2,1} & a_{2,2} &\cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots\\ a_{n,1}&a_{n,2}&\cdots &a_{n,n} \end{array} \right) $$

We denote by $\Delta$ all probability vectors over $[n]$.

A symmetric equilibrium for the game is a vector $a\in \Delta$ such that $$\forall x\in \Delta: x^tAa\leq a^tAa$$

Assume we increase the value of some specific coordinate $i,j$ by a variable $t$. Denote the new matrix by $A(t)$.

Assuming $A$ is non-singular, is the change in the symmetric equilibrium continuous in $t$?

I'm aware that the question might not be enough well-defined, as there could be more than a single equilibrium for $A$, but is there necessarily a symmetric equilibrium for $A(t)$ which converges to the symmetric equilibrium for $A$ as $t\to 0$?

R B
  • 620
  • 3
  • 13

1 Answers1

3

If I understand your question correctly then the answer is no. Consider

$$ A(h) = \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 2 & 0 \\ 2+2h & 0 & 3 \end{array} \right) $$ For the game defined by $A(0)$ the vector $a^t(0) = \left( \frac{1}{2}, \frac{1}{2}, 0\right)$ yields an equilibrium. For any $h>0$ however $$ A(h) \cdot a(0) = \left( \begin{array}{ccc} 1 \\ 1 \\ 1+h \end{array} \right), $$ so $a(0)$ is no longer an equilibrium. If play around with the probabilities you will see that nearby strategies do not constitute an equilibrium either. Hence if you have a positive sequence $h_1, h_2, ...$ such that $\lim_{n\to \infty} h_n = 0$ then you cannot select a sequence of vectors $a(h_1), a(h_2), ...$ such that they are equilibrium strategies of their respective games $A(h_1), A(h_2), ...$ and $$ \lim_{n\to \infty} a(h_n) = a(0). $$

In this counterexample I used that an action that was never played in $a(0)$ yielded the same payoff as actions with positive supports. If this is not the case then I think the answer to your question would be affirmative. Here is a proof for the case where $a>0$.

Since $a^t$ is a best response to $a$ we have $$ A\cdot a = \underline{1} \cdot c $$ where $\underline{1}$ is a vector with $1$ at all coordinates and $c \in \mathbb{R}$. If $A$ is non-singular then $$ a = A^{-1} \cdot \underline{1} \cdot c. $$ As $a$ is a probability vector, $c$ is uniquely determined by $A$: $$ 1 = \underline{1}^t \cdot a = \underline{1}^t \cdot A^{-1} \cdot \underline{1} \cdot c $$ I will use $A(h)$ to denote the perturbed matrix, and $a(h)$, $c(h)$ to denote the associated vectors. The original matrix and vectors occur at $h=0$. Since matrix inversion is continuous $$ \lim_{h \to 0} c(h) = \lim_{h \to 0} \frac{1}{\underline{1}^t \cdot A(h)^{-1} \cdot \underline{1}} = \frac{1}{\underline{1}^t \cdot A(0)^{-1} \cdot \underline{1}} = c(0). $$ Similarly $$ \lim_{h \to 0} a(h) = \lim_{h \to 0} A(h)^{-1} \cdot \underline{1} \cdot c(h) = A(0)^{-1} \cdot \underline{1} \cdot c(0) = a(0). $$ This is not an exact proof. To be exact you would have to specify the norm of a matrix, and then to prove that the above limits exist you would have to have a condition like $$ \lim_{h \to 0} ||A(h)|| = ||A(0)|| \neq 0. $$

Giskard
  • 29,387
  • 11
  • 45
  • 76