2
$\begingroup$

I run into this problem in my attempt to answer another question on math.stackexchange

We have a 2-player zero-sum game with an infinite set of strategies.

Imagine that we have one class of infinite strategies, let's call them $H_b$, where $b \in [0,1]$. You can view $b$ as the parameter that tweaks the general class to a specific strategy. Imagine also that we have another class of infinite strategies, call them $R_a$ with $a \in [0,1]$. $R_a$ strategies are "inferior" to $H_b$ strategies. More specifically, if we denote as $G(x,y)$ the gain of strategy $x$ over strategy $y$, then strategies $R$ are inferior to $H$ in the sense that $G(H_b, R_a) > 0, \space \forall a \in [0,1], \forall b < \frac{2}{3}$. In other words, any strategy in the first two thirds of strategy class $H$, wins all of the strategies in strategy class $R$.

My question is: Should I include strategies $R$ when I am looking for a mixed-strategy equilibrium, or can I safely ignore them?

EDIT: I know that if a strategy is strictly dominated we can safely ignore it when looking for a mixed strategy equilibrium. But strategies $R$ are not strictly dominated (if I understand the term correctly). Strictly dominated would mean that some strategy Y provides higher gains than $R_a$ for all possible opponents. This does not happen in our case. Let's choose any strategy $H_b, b \le 2/3$ to be our potential strictly dominant strategy over all strategies $R$. We can always find strategies $H_c, c> 2/3$ and $R_a$ such that $G(H_b,H_c)<0$ but $G(R_a,H_c)>0$. In other words, there exists an opponent, namely strategy $H_c$, that $R_a$ can perform better than $H_b$. For example, let's examine if strategy $H_{0.5}$ is strictly dominant over $R$. We can find that strategy $H_{0.8}$ wins over $H_{0.5}$, but $H_{0.8}$ loses over $R_{0.4}$. So, for opponent $H_{0.8}$, $R_{0.4}$ is better than $H_{0.5}$, and thus (by definition) not strictly dominated by $H_{0.5}$.

To complete the proof that no strategy in $H$ can dominate over all of $R$, let's consider strategies $H_b, b > 2/3$ to be our potential strictly dominant strategy. We can easily show that this cannot be, as we can find strategy $R_a$ such that $G(H_b, R_a) < 0$ and we know that $G(R_a, R_a) = 0$.

Even if strategies $R$ are not strictly dominated, can we use/exploit the "inferiority" of strategies $R$ when looking for a mixed strategy equilibrium?

I think there is a way out of having to consider strategies $R$ (even if theory says we should include them). If we find the mixed strategy equilibrium including only strategies $H$ then we can check if the found mixed strategy is better than every $R$ strategy. If it is, then we are clear. Is my reasoning correct?

EDIT 2: I found something that slightly simplifies the problem, but does not change my crux of my question. I found that strategy $R_1$ strictly dominates over all other strategies $R$. First I noted that $G(R_b, R_a) = \frac{b-a}{2}$, so $b=1$ gives you the best possible result if we restrict our choices in $R$ strategies. Furthermore, if we also consider $H$ strategies we can show that: $$G(R_1, H_b) > G(R_a, H_b), \forall b \in [0,1], \forall a \in [0,1)$$ So we can discard all other $R$ strategies and only keep $R_1$. The main question remains though, because $R_1$ is not dominated by any strategy $H$.

Assume I find a mixed strategy considering only strategies $H$ and then find the mixed strategy's gain against $R_1$. If this gain is positive, can I now ignore $R_1$?

$\endgroup$
5
  • $\begingroup$ If I told you that strictly dominated actions were never played with positive probability in mixed nash equilibria (which is true), would that answer your question? $\endgroup$ – Shane Sep 28 '16 at 20:42
  • 2
    $\begingroup$ @Shane, this is the crux of my question and confusion. As far as I understand, strategies $R_a$ are not strictly dominated. Strictly dominated would mean that some $H_b$ strategy would provide higher gains than $R_a$ for all possible opponents. This does not happen in my case. For example, strategy $H_{0.8}$ wins over $H_{0.5}$, and strategy $H_{0.5}$ wins over $R_{0.1}$ but $R_{0.1}$ wins over $H_{0.8}$. I'll edit my question to make this part clearer. $\endgroup$ – Thanassis Sep 29 '16 at 2:53
  • $\begingroup$ You are comparing strategies of two different players. I understand that in your original question the game is symmetric, but here it seems that the question implicitly assumes the game is symmetric (and zero sum) without stating it. $\endgroup$ – Sergio Parreiras Sep 29 '16 at 18:35
  • 1
    $\begingroup$ For infinite games, I do not know if it works, but my guess is what you are looking for is elimination of never best responses. See, Theorem 11 in homepages.cwi.nl/~apt/stra/ch4.pdf $\endgroup$ – Sergio Parreiras Sep 29 '16 at 18:38
  • 1
    $\begingroup$ @SergioParreiras, thanks for the suggestions. I edited the question to make it clearer, and in the process I also discovered a fact the simplifies the problem a little. But my main question stands. Thank you for the reference. Yes, I think that $R_1$ can be named as "never best response", but I am not sure the theorem holds because the game is not finite. How about the other proposal I make (to exclude and then test)? Does it make sense? $\endgroup$ – Thanassis Sep 30 '16 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.