CCT-UFCA/Ciência da Computação/Introdução à Teoria dos Jogos/Melhor resposta e equilíbrio de nash misto

Melhor resposta e equilíbrio de nash misto

Uma estratégia mista é considerada a melhor resposta de um jogo quando essa estratégia maximiza a utilidade de um jogador, dado que os demais sigam estratégias mistas específicas. Formalmente falando, dizemos que a melhor resposta do jogador $i$ para o perfil de estratégia $s_{-}i$ é a estratégia $s_{i}^{*}\in S_{i}$ tal que $u_{i}(s_{i}^{*},s_{-}i)\geq u_{i}(s_{i},s_{-}i)$ para todas as estratégias $si\in S_{i}$, ou seja, a estratégia $s_{i}^{*}$ gera a mesma ou maior utilidade que qualquer outra estratégia si.

Um equilíbrio de nash misto, por consequência, será um perfil de estratégia onde todos os jogadores escolhem suas melhores respostas, aquelas que maximizam suas utilidades dado o comportamento dos outros de forma que nenhum jogador consiga melhorar sua utilidade mudando sozinho sua estratégia.

Para encontrar o equilíbrio de nash misto precisamos encontrar probabilidades de cada jogador para com suas ações de modo que todos os jogadores fiquem indiferentes quanto as suas opções, ou seja, não possuam uma melhor resposta única visto que qualquer escolha resultaria em uma mesma utilidade esperada. Para isso precisamos:

• Definir as variáveis: para um jogo com duas ações teremos a 1° ação como $P$ e a 2° como $1-P$ por exemplo
• Calcular a utilidade do jogador que deseja tornar indiferente: por exemplo, se o jogador 1 pretende tornar o jogador 2 indiferente temos que calcular a utilidade de cada uma de suas ações, isso é feito somando o produto do payoff esperado da ação pela sua probabilidade de ocorrência para cada cenário de escolha do jogador 2. O mesmo vale para o jogador 2 que quer tornar o jogador 1 indiferente.
• Igualar os resultados obtidos e resolver a equação

Exemplo prático

$1/2$	$LW$	$WL$
$LW$	$2,1$	$0,0$
$WL$	$0,0$	$1,2$

Considere que o jogador 1 tem probabilidade $p$ de escolher $LW$, e $1-p$ de escolher $WL$, da mesma forma, o jogador 2 tem probabilidade $q$ de escolher $LW$, e $1-q$ de escolher $WL$. Vamos calcular a utilidade esperada de cada escolha para que o jogador 1 torne o jogador 2 indiferente:

${\begin{array}{lcl}U_{2}(LW)=U_{2}(WL)\\q+0(1-q)=0q+2(1-q)\\q={2 \over 3}\end{array}}$

Note que a utilidade esperada para cada ação ($LW$ e $WL$) do jogador 2 é soma dos produtos do payoff esperado pela sua probabilidade de ocorrência em cada cenário de escolha do jogador 1, por exemplo, temos que a utilidade $U_{2}(LW)$ é igual a $q+0(1-q)$ por que se o jogador 2 e 1 escolherem $LW$ o jogador 2 espera ganhar 1 com probabilidade $q$, caso contrário, jogador 2 escolhe $LW$ e jogador 1 $WL$, o jogador 2 espera ganhar 0 com probabilidade $1-q$.

Agora calcularemos a utilidade esperada para cada escolha para que o jogador 2 torne o jogador 1 indiferente:

${\begin{array}{lcl}U_{1}(LW)=U_{1}(WL)\\2p+0(1-p)=0p+1(1-p)\\p={1 \over 3}\end{array}}$

Logo temos que o jogador escolherá $LW$ com probabilidade de ${2 \over 3}$  e $WL$ com probabilidade restante de ${1 \over 3}$ , e o jogador 2 escolherá $LW$ com probabilidade de ${1 \over 3}$ e $WL$ com probabilidade restante de ${1 \over 3}$ , portanto, ${\biggr (}{2 \over 3}$, ${1 \over 3}{\biggr )}$ e ${\biggr (}{1 \over 3}$, ${2 \over 3}{\biggr )}$ são os equilíbrios de nash misto desse jogo.

Exemplo prático 2:

$1/2$	$Heads$	$Tails$
$Heads$	$1,-1$	$-1,1$
$Tails$	$-1,1$	$1,-1$

Considere que o jogador 1 tem probabilidade $p$ de escolher $Heads$, e $1-p$ de escolher $Tails$, e o jogador 2 tem probabilidade $q$ de escolher $Heads$, e $1-q$ de escolher $Tails$. Vamos calcular a utilidade esperada para cada jogada para que o jogador 1 torne o jogador 2 indiferente:

${\begin{array}{lcl}U_{2}(H)=U_{2}(T)\\-q+1-q=q-1(1-q)\\1-2q=q-1+q\\1-2q=-1+2q\\-2q-2q=-1-1\\-4q=-2\\4q=2\\q={2 \over 4}\\q={1 \over 2}\end{array}}$

Agora vamos calcular a utilidade esperada de cada jogada para que o jogador 2 torne o jogador 1 indiferente:

${\begin{array}{lcl}U_{1}(H)=U_{1}(T)\\p-1(1-p)=-p(1-p)\\p-1+p=-p+1-p\\-1+2p=1-2p\\2p+2p=1+1\\4p=2\\p={2 \over 4}\\p={1 \over 2}\end{array}}$

Logo, temos que o jogador 1 escolherá $Heads$ com probabilidade de ${1 \over 2}$ e $Tails$ com probabilidade de ${1 \over 2}$, enquanto o jogador 2 escolherá $Heads$ com probabilidade de ${1 \over 2}$ e $Tails$ com probabilidade de ${1 \over 2}$, o equilíbrio de nash misto desse jogo é, portanto, ${\Bigl (}{1 \over 2},{1 \over 2}{\Bigr )}$ e ${\Bigl (}{1 \over 2},{1 \over 2}{\Bigr )}$

Agora calcularemos a utilidade esperada para cada jogador:

para o jogador 1 temos:

${\begin{array}{lcl}U_{1}=p*q*1+(p*(q-1)*-1)+((1-p)*q)*-1)+((1-p)*(1-q)*1)\\U_{1}={1 \over 2}*{1 \over 2}*1+{1 \over 2}*{1 \over 2}*-1+{1 \over 2}*{1 \over 2}*-1+{1 \over 2}*{1 \over 2}*1\\U_{1}={1 \over 4}-{1 \over 4}-{1 \over 4}+{1 \over 4}=0\end{array}}$

para o jogador 2 temos:

${\begin{array}{lcl}U_{2}=p*q*-1+p*(1-q)*1+(1-p)*q*1+(1-p)*(1-q)*-1\\U_{2}={1 \over 2}*{1 \over 2}*-1+{1 \over 2}*{1 \over 2}*1+{1 \over 2}*{1 \over 2}*1+{1 \over 2}*{1 \over 2}*-1\\U_{2}=-{1 \over 4}+{1 \over 4}+{1 \over 4}-{1 \over 4}=0\end{array}}$

logo, a utilidade esperada do jogador 1 e 2 são ambas 0.