  The Bimatrix Nash Equilibrium (NE) for $m \times n$ real matrices $R$ and
$C$, denoted as the {\it Row} and {\it Column} players, is characterized as
follows: Let $\Delta =S_m \times S_n$, where $S_k$ denotes the unit simplex in
$\mathbb{R}^k$. For a given point $p=(x,y) \in \Delta$, define $R[p]=x^TRy$ and
$C[p]=x^TCy$. Consequently, there exists a subset $\Delta_* \subset \Delta$
such that for any $p_*=(x_*,y_*) \in \Delta_*$, $\max_{p \in \Delta,
y=y_*}R[p]=R[p_*]$ and $\max_{p \in \Delta, x=x_* } C[p]=C[p_*]$.
  The computational complexity of bimatrix NE falls within the class of {\it
PPAD-complete}. Although the von Neumann Minimax Theorem is a special case of
bimatrix NE, we introduce a novel extension termed {\it Trilinear Minimax
Relaxation} (TMR) with the following implications: Let $\lambda^*=\min_{\alpha
\in S_{2}} \max_{p \in \Delta} (\alpha_1 R[p]+ \alpha_2C[p])$ and
$\lambda_*=\max_{p \in \Delta} \min_{\alpha \in S_{2}} (\alpha_1 R[p]+
\alpha_2C[p])$.
  $\lambda^* \geq \lambda_*$.
  $\lambda^*$ is computable as a linear programming in $O(mn)$ time, ensuring
$\max_{p_* \in \Delta_*}\min \{R[p_*], C[p_*]\} \leq \lambda^*$, meaning that
in any Nash Equilibrium it is not possible to have both players' payoffs to
exceed $\lambda^*$.
  $\lambda^*=\lambda_*$ if and only if there exists $p^* \in \Delta$ such that
$\lambda^*= \min\{R[p^*], C[p^*]\}$. Such a $p^*$ serves as an approximate Nash
Equilibrium. We analyze the cases where such $p^*$ exists and is computable.
  Even when $\lambda^* > \lambda_*$, we derive approximate Nash Equilibria.
  In summary, the aforementioned properties of TMR and its efficient
computational aspects underscore its significance and relevance for Nash
Equilibrium, irrespective of the computational complexity associated with
bimatrix Nash Equilibrium. Finally, we extend TMR to scenarios involving three
or more players.

Computer Science and Game Theory