CCT-UFCA/Ciência da Computação/Introdução à Teoria dos Jogos/Melhor resposta, estratégias dominantes e equilíbrio de nash puro

Analisando jogos

No contexto de análise de um jogo, objetiva-se sempre a busca de uma estratégia ótima, ou seja, que maximize a função de utilidade de um agente, isso é consideravelmente aplicado em um cenário onde existe apenas um agente com preferências entre estados do mundo, contudo, em um contexto onde há múltiplos agentes essa noção de estratégia ótima se perde, uma vez  que todos os agentes buscam a maximização de sua utilidade que é influenciada diretamente pela sua própria escolha e dos demais, nesse contexto a teoria dos jogos foca-se no encontro de conceitos de solução, que são subconjuntos de resultados com características únicas e interessantes.

Melhor resposta

Formalmente falando, temos que para $a-i=(a_{1},a_{2},...,a_{i}-1,a_{i}+1)$, um perfil de ações sem a ação do jogador $a_{i}$, tem que sua melhor resposta é a ação $a_{i}*$ pertencente ao conjunto de ações disponíveis do jogador $A_{i}$, tal que $(a_{i}*,a-i)>=(a_{i},a-i)$, ou seja, o perfil de ações contendo $a_{i}*$ e as ações dos demais jogadores, é maior ou igual a todas as possíveis ações restantes disponíveis para o jogador $a_{i}$, e as ações jogadas pelos demais jogadores.

Intuitivamente falando temos que a melhor resposta é a escolha de uma ação que maximize o ganho de um jogador dado que ele saiba o que os outros jogadores escolheram. Considerando novamente a instância do jogo do dilema do prisioneiro apresentado abaixo:

$1/2$	$C$	$D$
$C$	$-1,1$	$-4,0$
$D$	$0,-4$	$-3,-3$

Temos que, caso o jogador 2 escolha $C$, a melhor resposta para o jogador 1 será $D$, pois $0>-1$. Caso o jogador 2 escolha $D$, a melhor resposta para o jogador 1 também será $D$ pois $-3>-4$.

Da mesma forma, caso o jogador 1 escolha $C$, a melhor resposta para o jogador 2 será $D$, pois $0>-1$. Caso o jogador 1 escolha D, a melhor resposta para o jogador 2 ainda será D, pois -3>-4.

Estratégias dominantes

Estratégias dominantes são ações que são sempre a melhor resposta para um jogador independente da escolha dos outros, ou seja, ações que o jogador pode escolher sempre sem preocupações.

Dizemos que uma estratégia $Si$ estritamente domina outra estratégia $Si'$, se para qualquer escolha dos oponentes o payoff de $Si$ é sempre maior que o de $Si'$, ou seja, o jogador sempre a escolherá pois é a melhor entre todas as outras opções para qualquer um dos cenários possíveis.

Dizemos que uma estratégia $Si$ fracamente domina outra estratégia $Si'$, se para qualquer escolha dos oponentes o payoff de $Si$ é sempre igual ou em pelo menos em um caso melhor ao payoff de $Si'$, ou seja, o jogador irá preferir escolher a mesma mas há situações em que o seu payoff será igual caso tivesse adotado outra estratégia.

Considere o jogo abaixo onde analisaremos o contexto de estratégias dominantes de ambos os jogadores:

$1/2$	$X$	$Y$
$A$	$3,2$	$2,1$
$B$	$4,3$	$2,2$

analisando o jogador 1:

• se o jogador 2 escolher $X$, o jogador 1 irá ganhar 3 caso escolha $A$, ou 4 caso escolha $B$; ($B>A$)
• se o jogador 2 escolher $Y$, o jogador 1 irá ganhar 2 caso escolha $A$, ou 2 caso escolha $B$; ($B=A)$

Portanto, temos que a escolha $B$ fracamente domina $A$, pois garante que independente da escolha do oponente o jogador 1 tenha payoff igual ou uma vez maior que sua outra estratégia disponível.

analisando o jogador 2:

• se o jogador 1 escolher $A$, o jogador 2 irá ganhar 2 caso escolha $X$, ou 1 caso escolha $Y$; ($X>Y)$
• se o jogador 1 escolher $B$, o jogador 2 irá ganhar 3 caso escolha $X$, ou 2 caso escolha $Y$; ($X>Y)$

Portanto, temos que a escolha $X$ estritamente domina $Y$, pois independente da escolha do oponente essa estratégia sempre garantirá payoff maior.

Equilíbrio de nash puro

Um equilíbrio de nash puro se dá quando para dado perfil de ações $a=(a_{1},a_{2},...,a_{n})$, todos os jogadores têm que suas ações $a_{i}$ são a melhor resposta para o perfil de ação $a$.

Intuitivamente falando o equilíbrio de nash se baseia no conceito de melhor resposta, ou seja, consiste em um perfil de ações onde todos os jogadores, cientes das escolhas de todos, escolhem suas melhores ações simultaneamente, de modo que nenhum jogador consiga melhorar sua utilidade mudando de ação sozinho.

Exemplo 1: considere a instância do dilema do prisioneiro abaixo:

$1/2$	$C$	$D$
$C$	$-1,1$	$-4,0$
$D$	$0,-4$	$-3,-3$

Note que independente do cenário de escolha dos jogadores, a melhor resposta dos mesmos será sempre $D$, analisando o perfil de ação onde ambos escolhem $D$, $a=\{(D,D)\}$, com utilidade $u(a)=\{(-3,-3)\}$ , temos que $a$ será o equilíbrio de nash puro, pois nenhum jogador consegue melhorar sua utilidade mudando de ação sozinho, uma vez que se o jogador 1 mudar para $C$ ganhará -4 que é menor que -3, e se o jogador 2 mudar para $C$ganhará -4 que é menor que -3.

Exemplo 2: considere a seguinte instância do jogo abaixo:

$1/2$	$Left$	$Right$
$Left$	$1,1$	$0,0$
$Right$	$0,0$	$1,1$

Analisando os cenários em busca da melhor resposta, temos que:

para o jogador 1:

• caso o jogador 2 escolha $Left$, sua melhor resposta será $Left$, pois 1>0;

• caso o jogador 2 escolha $Right$, sua melhor resposta será $Right$, pois 1>0.

Para o jogador 2:

• caso o jogador 1 escolha $Left$, sua melhor resposta será $Left$, pois 1>0;

• caso o jogador 1 escolha $Right$, sua melhor resposta será $Right$, pois 1>0.

Note que independente da escolha de um dos jogadores o outro sempre escolherá o mesmo, portanto, temos dois perfis de ações que são equilíbrios de nash puros, são eles o caso em que ambos os jogadores escolhem $Left$, e o caso em que ambos escolhem $Right$, isso se deve ao fato de que nenhum jogador conseguirá melhorar sua utilidade modificando unicamente sua resposta sozinho, uma vez que para os dois perfis de ações, independente da resposta do adversário e da mudança de resposta de um dos jogadores, o mesmo sempre passará a ganhar 0 que é menor que sua utilidade atual.