Academic Paper attributes
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 =Sm times Sn, where Sk denotes the unit simplex in Rk. For a given point p=(x,y) in Delta, define R[p]=xTRy and C[p]=xTCy. Consequently, there exists a subset Delta* subset Delta such that for any p*=(x*,y*) in Delta*, maxp in Delta, y=y*R[p]=R[p*] and maxp 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*=minalpha in S2 maxp in Delta (alpha1 R[p]+ alpha2C[p]) and lambda*=maxp in Delta minalpha in S2 (alpha1 R[p]+ alpha2C[p]). lambda* geq lambda*. lambda* is computable as a linear programming in O(mn) time, ensuring maxp* 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*= minR[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.
