<p>It depends on what your usecase is. If you are interested in getting close to an actual Nash equilibrium, then the quality measure you want will be the distance to the nearest Nash equilibrium (which you probably can't compute efficiently).</p>
<p>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: <span class="math-container">$$\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 ) $$</span></p>

CC BY-SA 4.0
2021-09-19T17:54:40.687Z
2021-09-19T17:54:40.687Z
Arno
<p>Consider a bimatrix game problem with matrix <span class="math-container">$A$</span> and <span class="math-container">$B$</span>. The definition of the value <span class="math-container">$v = [v_1, v_2]$</span> of the Nash equilibrium <span class="math-container">$(x, y)$</span> are as follows,
<span class="math-container">$$v_1 = x^TAy,$$</span>
<span class="math-container">$$v_2 = x^TBy.$$</span></p>
<p>The situation is that we have an algorithm to give a prediction <span class="math-container">$\hat{v}$</span>, which is expected to be as close as possible to the true value <span class="math-container">$v$</span>.</p>
<p>My problem is how can I evaluate my algorithm performance, i.e., how can I measure the difference between the predicted value <span class="math-container">$\hat{v}$</span> and the true value <span class="math-container">$v$</span>, without considering or knowing anything about strategy profiles <span class="math-container">$(x, y)$</span>?</p>
<p>I have two following ideas,</p>
<ol>
<li>The most simple and straightforward way is Using the mean square error(MSE), just like <span class="math-container">$MSE(v, \hat{v})$</span>.</li>
<li>We find the strategy profiles <span class="math-container">$(x, y)$</span>, which are probably more than one, corresponding to the predicted value <span class="math-container">$\hat{v}$</span>. After having the strategy profiles <span class="math-container">$(\hat{x}, \hat{y})$</span>, we can use the well-defined <span class="math-container">$\epsilon$</span> Nash equilibrium, see page 6 of this <a href="https://link.springer.com/article/10.1007/s00453-018-0465-y#:%7E:text=An%20%5Cepsilon%20%2Dapproximate%20Nash%20equilibrium,deviating%20from%20their%20assigned%20strategy." rel="nofollow noreferrer">paper</a>.</li>
</ol>

CC BY-SA 4.0
2021-09-16T13:14:59.330Z
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)?
Neal Young
CC BY-SA 4.0
2021-09-16T19:59:15.393Z
@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$.
dawen
CC BY-SA 4.0
2021-09-16T20:18:10.367Z
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.
Neal Young
CC BY-SA 4.0
2021-09-16T20:24:57.680Z
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.
dawen
CC BY-SA 4.0
2021-09-16T20:34:30.710Z
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. https://cstheory.stackexchange.com/questions/17854/when-do-epsilon-nash-equilibrium-strategies-converge-to-nash-equilibrium-stra, and https://cstheory.stackexchange.com/questions/12929/compute-nash-equilibrium-for-2-player-games
Neal Young
CC BY-SA 4.0
2021-09-19T17:47:20.030Z
In general, different Nash equilibria can yield different outcomes. You get a unique value for zero-sum games though.
Arno
<gt.game-theory><approximation><nash-equilibrium>
How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$
dawen
# How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

(Asked by: username_0 on 2021-09-16)

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](https://link.springer.com/article/10.1007/s00453-018-0465-y#:%7E:text=An%20%5Cepsilon%20%2Dapproximate%20Nash%20equilibrium,deviating%20from%20their%20assigned%20strategy.).

**Tags:** gt.game-theory, approximation, nash-equilibrium
> **Comments:**
> **username_1**: 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)?  
> **username_0**: @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$.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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. https://cstheory.stackexchange.com/questions/17854/when-do-epsilon-nash-equilibrium-strategies-converge-to-nash-equilibrium-stra, and https://cstheory.stackexchange.com/questions/12929/compute-nash-equilibrium-for-2-player-games  
> **username_2**: In general, different Nash equilibria can yield different outcomes. You get a unique value for zero-sum games though.  

---

## 1 answers

### Answer by username_2 on 2021-09-19. Score: 1

It depends on what your usecase is. If you are interested in getting close to an actual Nash equilibrium, then the quality measure you want will be the distance to the nearest Nash equilibrium (which you probably can't compute efficiently).

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 ) $$


---

