How to find a solution of this equation system.

Question

Problem:

Given two real squre matrix $A, B$ with shape $(n,n)$ and two scalar values $v_1, v_2$, we consider finding two vectors $x, y$ which can satisfy the following equations, $$ \begin{array}{l} v_1 = x^T A y,\\ v_2 = x^T B y,\\ x\in X, y\in Y, \end{array} $$

where $X=\{x\in \mathbb{R}^n | \mathbf{1}_n^Tx=1, x\geq0\}$, $Y=\{y\in \mathbb{R}^n | \mathbf{1}_n^Ty=1, y\geq0\}$.

My question is when $A, B, v_1, v_2$ satisfy what conditions, the solution will exist? and how to solve it?

I randomly generate some $A, B, v_1, v_2$, and put it to Gurobi solver. Sometimes the solution can be found, sometimes doesn't. I haven't been able to see the pattern

---

Background: For people who are interested in the background of this problem.

Finding the Nash equilibrium of a bimatrix game can be defined as $$ \begin{array}{ll} v_{1}^*=\left(x^{*}\right)^{T} A y^{*} \geq x^{T} A y^{*} & \forall x \in X, \\ v_{2}^*=\left(x^{*}\right)^{T} B y^{*} \geq\left(x^{*}\right)^{T} B y & \forall y \in Y, \end{array} $$ where the bimatrix game can be represented by matrices $A, B$. The $(x^*,y^*)$ is a Nash equilibrium, and the $v_1^*, v_2^*$ is the corresponding value of Nash equilibrium.

My algorithm can somehow give a prediction $v_1, v_2$ to approximate the true value $v_1^*, v_2^*$.

However, after the prediction, I want to find the mixed strategy $x, y$ corresponding to the $v_1, v_2$. Then the problem is reduced to the equation system shown at the top.

(I apologize in advance if anything is not clear, feel free to edit it or make a comment.)

Answer 1

Let the matrices be $A_{n\times n}=(a_{i,j})_{i\leq n\\j\leq n}$ and $B_{n\times n}=(b_{i,j})_{i\leq n\\j\leq n}$. The decison variables $x=[x_1,\dots,x_n]$ and $y=[y_1,\dots,y_n]$ are in the $n-1$ probability simplex.

We flat the matrices $A$ and $B$ to vectors $a$ and $b$ with length $n*n$, where $a=[a_{11},\dots,a_{nn}]$, $b=[b_{11},\dots,b_{nn}]$.

We define a $n*n$ length vector $p=[p_{11}, \dots , p_{nn}]$, where $p_{i,j} = x_i *y_j, i\leq n, j\leq n.$

The existence of solution and soving are related to the following linear eqaution system, $$a^Tp = v_1$$ $$b^Tp = v_2$$ $$1^Tp = 1$$ $$0\leq p \leq 1$$

Answer 2

This is just some of my thought: Suppose $\gamma = v_1/v_2$ is finite, we have $ x^T(A-\gamma B)y = 0$. Since $x,y$ are nonnegative and nonzero, at least the matrix $A-\gamma B$ cannot be positive for every entry. We can consider

$$f(x,y) \equiv x^T(A-\gamma B)y $$

as real-valued function defined on the compact space $T^{n-1} \times T^{n-1}$, where $T^{n}$ is the $n-$dimensional unit simplex. Now, the problem will be reduced to finding zeros of $f$ in this compact space. If we view $f$ as quadratic polynomial in with factors of $x_jy_k$, then maybe there are zero-finding numerical methods for this type of function.