1
$\begingroup$

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.
$\endgroup$
6
  • $\begingroup$ 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)? $\endgroup$
    – Neal Young
    Commented Sep 16, 2021 at 13:14
  • $\begingroup$ @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$. $\endgroup$
    – dawen
    Commented Sep 16, 2021 at 19:59
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Sep 16, 2021 at 20:18
  • $\begingroup$ 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. $\endgroup$
    – dawen
    Commented Sep 16, 2021 at 20:24
  • $\begingroup$ 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/… $\endgroup$
    – Neal Young
    Commented Sep 16, 2021 at 20:34

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.