I consider a game with two players in incomplete information with perfect recall and I would like to prove Kuhn’s theorem stating that for every mixed strategy $\sigma$ there exists a behavior strategy $\mu$ that is equivalent in the following sense : for all pure strategy $t$ of the other player we have that

$$ \mathbb{P}_{\sigma,t} = \mathbb{P}_{\mu,t} $$ Which means that they induce the same probability distribution on the terminal nodes.

Here is my attempt :

We fix $\sigma$ a mixed strategy of player $1$, $(I^{1}_j)$ and $(I^{2}_k)$ to be respectively the information set of player $1$ and $2$ and $t$ the pure strategy of player $2$.

Let $T$ be a terminal node. First, the candidate we will consider is the following, which holds for any information set :

$$\mu(I^{1}_{n-1})(j) =\mathbb{P}_{\sigma,t}(j| a_1,..,a_{n-1}) $$

For all $j$ in the action set following the node $a_{n-1}$ where $a_{n-1}\in I^{1}_{n-1}$.

This leads to consider

$$ \mathbb{P}_{\mu,t}(T)= \Pi_{l=1}^{n}\mu(I^{1}_{l-1})(a_l) $$

Where $(a_1,…, a_n)$ is the play leading to the terminal node $T$. Thus $a_n=T$.

My first idea is to show that this probability does not depend on player $2$ :

Indeed we have

$$ \mathbb{P}_{\mu,t}(T | a_1,..,a_{n-1}) = \frac{\mathbb{P}_{\sigma,t}(s(I^{1}_1) = a_1,.., t(I^{2}_v) = a_k,..,s(I^{1}_{n-1}) = T)}{\mathbb{P}_{\sigma,t}(s(I^{1}_1) = a_1,..,t(I^{2}_v) = a_k,..,t(I^{2}_m) = a_{n-1})} $$

By independence of actions between player $1$ and $2$ we have that this is equal to

$$ \mathbb{P}_{\mu,t}(T | a_1,..,a_{n-1}) = \frac{\mathbb{P}_{\sigma,t}(s(I^{1}_1) = a_1,..,s(I^{1}_{n-1}) = T)}{\mathbb{P}_{\sigma,t}(s(I^{1}_1) = a_1,..,s(I^{1}_j) = a_{n-2})} $$

This probability in fact depends only on the mixed strategy $\sigma$, by the perfect recall assumption it does not depend on particular sequence $(a_i)_{i=1}^{n}$ leading to $T$ and $\mathbb{P}_{\mu,t}$ is well defined.

The second task is to show that it induces the same probability distribution on terminal nodes.

Using the fact that we have independence between behavior strategies, we get that in fact the product is a telescopic product, and taking the probability of the terminal node $T$ yields

$$ \mathbb{P}_{\mu,t}(T)= \Pi_{l=1}^{n}\mu(I^{1}_{l-1})(a_l) = \mathbb{P}_{\sigma,t}(T) $$

Please, I would like to know if this proof seems correct to you. The idea I have is somewhat intuitive, but I realized that much of the difficulty appears when trying to write it properly.

Thank you a lot

In fact it is not exactly $\mathbb{P}_{\sigma,t}(T)$ that we get in the last equation but

$$ \mathbb{P}_{\sigma,t}(a_1,…,a_{n-1},T) $$

If I am not wrong



Your Answer

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