# How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

Consider a bimatrix game problem with matrix $$A$$ and $$B$$. The definition of the value $$v = [v_1, v_2]$$ of the Nash equilibrium $$(x, y)$$ are as follows, $$v_1 = x^TAy,$$ $$v_2 = x^TBy.$$

The situation is that we have an algorithm to give a prediction $$\hat{v}$$, which is expected to be as close as possible to the true value $$v$$.

My problem is how can I evaluate my algorithm performance, i.e., how can I measure the difference between the predicted value $$\hat{v}$$ and the true value $$v$$, without considering or knowing anything about strategy profiles $$(x, y)$$?

I have two following ideas,

1. The most simple and straightforward way is Using the mean square error(MSE), just like $$MSE(v, \hat{v})$$.
2. We find the strategy profiles $$(x, y)$$, which are probably more than one, corresponding to the predicted value $$\hat{v}$$. After having the strategy profiles $$(\hat{x}, \hat{y})$$, we can use the well-defined $$\epsilon$$ Nash equilibrium, see page 6 of this paper.
• What is a "prediction value" and how does it differ from a "true value"? Can't there be multiple Nash equilibrium values for a given game (in which case saying "the" value doesn't make sense)? Commented Sep 16, 2021 at 13:14
• @Neal Young, I am sorry for the confusion. Let me explain it in this way. By Nash equilibrium, I mean the mixed strategy profiles $(x, y)$, which can be more than one such profile for sure. By Nash equilibrium value $v$, I mean the value corresponding to those Nash equilibriums, which I think should be unique. By prediction value, I mean a value $\hat{v}$ is not the same as the Nash equilibrium value $v$. Commented Sep 16, 2021 at 19:59
• What's the role of $\hat v$ then? If it isn't an actual equilibrium value, then isn't determining "the difference between the predicted value and the true value" just the same as determining the true value? E.g., why not take $\hat v = 0$? I don't understand, formally, what problem you are hoping to find an algorithm for. Commented Sep 16, 2021 at 20:18
• The situation is that I already have an algorithm trying to find the Nash equilibrium value $v$, and I want to evaluate how well my algorithm is. For example, the true Nash equilibrium value is $v = 5$. My algorithm gives a prediction $\hat{v} = 4.3$. I just want to evaluate how well my algorithm is doing. The easiest way is to say the prediction have error $|v-\hat{v}|=|5-4.3|=0.7$, but I am trying to use a more game theory way, which I am not familiar with. Commented Sep 16, 2021 at 20:24
• Well, as far as I can tell to do that you need to compute the nearest true equilibrium value, or an approximation to it. At least as of a few years ago, I don't think there were poly-time algorithms to approximate any equilibrium value, much less the one nearest a given value. See e.g. cstheory.stackexchange.com/questions/17854/…, and cstheory.stackexchange.com/questions/12929/… Commented Sep 16, 2021 at 20:34

If you are satisfied with approximate equilibria, you should instead use the incentive players have to deviate from the strategy profile you have found. Here it helps you that a players always has a pure best response to any strategy profile. Thus, you'd be looking at: $$\left ( \max_{i \leq n} e_i^{\mathrm{T}}Ay - x^\mathrm{T}Ay \right ) + \left ( \max_{j \leq m} x^{\mathrm{T}}Be_j - x^\mathrm{T}By \right )$$