Estratégia (teoria dos jogos)
# Estratégia (teoria dos jogos)

Na teoria dos jogos, em geral mais conhecida como "teoria da decisão interativa", a estratégia de um jogador é qualquer uma das opções que ele escolhe em um ambiente onde o resultado depende não apenas de suas próprias ações, mas das ações dos outros. A disciplina diz respeito principalmente à ação de um jogador em um jogo, afetando o comportamento, ou as ações, de outros jogadores. Alguns exemplos de "jogos" incluem xadrez, bridge, pôquer, monopoly, diplomacia ou batalha naval. A estratégia de um jogador determinará a ação que ele realizará em qualquer estágio do jogo. Ao estudar a teoria dos jogos, os economistas usam uma lente mais racional para analisar as decisões, em vez das perspectivas psicológicas ou sociológicas tomadas ao analisar as relações entre as decisões de duas ou mais partes em diferentes disciplinas.
O conceito de estratégia é às vezes (erroneamente) confundido com o de movimento. Um movimento é uma ação realizada por um jogador em algum ponto durante o jogo (por exemplo, no xadrez, mover o Bispo branco de a2 para b3). Uma estratégia, por outro lado, é um algoritmo completo para jogar o jogo, dizendo ao jogador o que fazer para cada situação possível durante o jogo. É útil pensar em uma "estratégia" como uma lista de direções e um "movimento" como uma única volta na própria lista de direções.
Um perfil de estratégia (às vezes chamado de combinação de estratégia) é um conjunto de estratégias para todos os jogadores que especifica totalmente todas as ações em um jogo. Um perfil de estratégia deve incluir uma e apenas uma estratégia para cada jogador, de forma a responder da maneira melhor e mais racional às decisões tomadas pelos outros jogadores.

## Conjunto de estratégias

O conjunto de estratégias de um jogador define quais estratégias estão disponíveis para eles jogarem. Um perfil de estratégia é uma lista de conjuntos de estratégias, ordenados do mais para o menos desejável.
Um jogador tem um conjunto de estratégias finito se ele tiver uma série de estratégias discretas disponíveis. Por exemplo, um jogo de pedra, papel e tesoura compreende um único movimento de cada jogador — e o movimento de cada jogador é feito sem o conhecimento do outro, não como uma resposta — então cada jogador tem o conjunto de estratégia finito.
Quando acontece o caso inverso, um conjunto de estratégias é infinito. Por exemplo, o jogo do corte do bolo tem um continuum limitado de estratégias no conjunto de estratégias {Corte em qualquer lugar entre 0% e 100% do bolo}.
Em um jogo dinâmico, a classe de jogos jogados ao longo de uma série de tempo, o conjunto de estratégias consiste nas regras possíveis que um jogador pode dar a um robô ou agente sobre como jogar o jogo. Por exemplo, no jogo do ultimato, a estratégia definida para o segundo jogador consistiria em todas as regras possíveis para que ofertas aceitar e quais rejeitar.
Em um jogo bayesiano, ou jogos em que os jogadores têm informações incompletas uns sobre os outros, o conjunto de estratégias é semelhante ao de um jogo dinâmico. Ele consiste em regras para as ações a serem tomadas em relação a qualquer possível informação privada.

### Escolhendo um conjunto de estratégias

Na teoria dos jogos aplicada, a definição dos conjuntos de estratégias é uma parte importante da arte de fazer um jogo tanto solucionável quanto significativo. O teórico do jogo pode usar o conhecimento do problema geral, ou seja, o atrito entre dois ou mais jogadores, para limitar os espaços de estratégia e facilitar a solução.
Por exemplo, estritamente falando no jogo do ultimato, um jogador pode ter estratégias como: Rejeitar ofertas de ($ 1, $ 3, $ 5, ..., $ 19), aceitar ofertas de ($ 0, $ 2, $ 4, ..., $ 20). Incluir todas essas estratégias cria um espaço de estratégia muito grande e um problema um tanto difícil. Em vez disso, um teórico do jogo pode acreditar que pode limitar o conjunto de estratégias para: {Rejeitar qualquer oferta ≤ x, aceitar qualquer oferta> x ; para x em ($ 0, $ 1, $ 2, ..., $ 20)}.

## Estratégias puras e mistas

Uma estratégia pura fornece uma definição completa de como um jogador irá jogar um jogo. A estratégia pura pode ser pensada como um plano sujeito às observações que ele faz no decorrer do jogo. Em particular, ela determina o movimento que um jogador fará para qualquer situação que possa enfrentar. O conjunto de estratégias de um jogador é o conjunto de estratégias puras disponíveis para aquele jogador.
Uma estratégia mista é a atribuição de uma probabilidade a cada estratégia pura. Quando alistando estratégia mista, geralmente é porque o jogo não permite uma descrição racional na especificação de uma estratégia pura para o jogo. Isso permite que um jogador selecione aleatoriamente uma estratégia pura. (Consulte a seção a seguir para obter uma ilustração de um exemplo). Uma vez que as probabilidades são contínuas, existem infinitas estratégias mistas disponíveis para um jogador. Uma vez que as probabilidades estão sendo atribuídas a estratégias para um jogador específico ao discutir os resultados de certos cenários, o resultado deve ser referido como "retorno esperado".
Claro, pode-se considerar uma estratégia pura um caso degenerado de uma estratégia mista, em que essa estratégia pura particular é selecionada com probabilidade 1 e todas as outras estratégias com probabilidade 0.
Uma estratégia totalmente mista é uma estratégia mista em que o jogador atribui uma probabilidade estritamente positiva a cada estratégia pura (estratégias totalmente mistas são importantes para o refinamento do equilíbrio, como o equilíbrio perfeito da mão trêmula).

## Estratégia mista
### Ilustração

Ao bater um pênalti quando joga futebol, o chutador deve escolher se chuta para o lado direito ou esquerdo do gol e, simultaneamente, o goleiro deve decidir como bloqueá-lo. Além disso, o chutador tem uma direção em que ele é melhor no chute, que é para a esquerda se ele for direito. A matriz do jogo de futebol ilustra essa situação, uma forma simplificada do jogo estudada por Chiappori, Levitt e Groseclose (2002). Ele supõe que, se o goleiro adivinhar corretamente, o chute é bloqueado, que é definido com o prêmio base de 0 para ambos os jogadores. Se o goleiro adivinhar errado, é mais provável que o chute ocorra se for para a esquerda (prêmios de +2 para o chutador e -2 para o goleiro) do que se for para a direita (o prêmio inferior de +1 para chutador e -1 para o goleiro).
| | | Goleiro | Goleiro |
| | | Jogar-se para a esquerda | Jogar-se para a direita |
| Chutador | Chute para a esquerda | 0, 0 | +2, -2 |
| Chutador | Chute para a direita | +1, -1 | 0, 0 |
| Resultado do jogo de futebol (chutador, goleiro) ||||
Este jogo não tem equilíbrio de estratégia pura, porque um jogador ou outro se desviaria de qualquer perfil de estratégias - por exemplo, (Esquerda, Esquerda) não é um equilíbrio porque o chutador se desviaria para a direita e aumentaria seu prêmio de 0 para 1.
O equilíbrio de estratégia mista do chutador é encontrado a partir do fato de que ele se desviará da randomização, a menos que seus prêmios de chute esquerdo e chute direito sejam exatamente iguais. Se o goleiro se inclinar para a esquerda com probabilidade g, o resultado esperado do chutador no chute para a esquerda é g (0) + (1-g) (2) e no chute para a direita é g (1) + (1-g) (0). Equacionando esses rendimentos, g = 2/3. Da mesma forma, o goleiro está disposto a randomizar apenas se o chutador escolher a probabilidade de estratégia mista k de modo que o prêmio jogar-se para a esquerda de k (0) + (1-k) (- 1) seja igual ao prêmio do jogar-se para a direita de k (-2) + (1) -k) (0), então k = 1/3. Assim, o equilíbrio de estratégia mista é (Prob (chute para a esquerda) = 1/3, (Prob (chute para a direita) = 2/3).
Observe que, em equilíbrio, o chutador chuta para o seu melhor lado apenas 1/3 das vezes. Isso porque o goleiro está protegendo mais esse lado. Observe também que, em equilíbrio, o chutador é indiferente para qual direção ele chuta, mas para que haja um equilíbrio ele deve escolher exatamente 1/3 de probabilidade.
Chiappori, Levitt e Groseclose tentam medir o quão importante é para o chutador chutar para seu lado favorito, adicionar chutes centrais, etc., e ver como os jogadores profissionais realmente se comportam. Eles descobrem que fazem escolhas aleatórias e que os chutadores chutam para seu lado favorito 45% das vezes e os goleiros tendem para esse lado 57% das vezes. O artigo deles é conhecido como um exemplo de como as pessoas na vida real usam estratégias mistas, apesar de não serem matematicamente sofisticadas.

### Significado

Em seu famoso artigo, John Forbes Nash provou que existe um equilíbrio para todo jogo finito. Pode-se dividir o equilíbrio de Nash em dois tipos. Equilíbrios de Nash de estratégia pura são equilíbrios de Nash onde todos os jogadores estão jogando estratégias puras. Equilíbrios de Nash de estratégia mista são equilíbrios em que pelo menos um jogador está jogando uma estratégia mista. Embora Nash tenha provado que todo jogo finito tem um equilíbrio de Nash, nem todos têm um equilíbrio de Nash de estratégia pura. Para obter um exemplo de um jogo que não possui um equilíbrio de Nash em estratégias puras, consulte Combinando centavos. No entanto, muitos jogos têm equilíbrios de Nash de estratégia pura (por exemplo, o jogo de coordenação, o dilema do prisioneiro, a caça ao veado). Além disso, os jogos podem ter equilíbrios de estratégia pura e estratégia mista. Um exemplo fácil é o jogo de coordenação puro, onde além das estratégias puras (A, A) e (B, B) existe um equilíbrio misto em que ambos os jogadores jogam qualquer uma das estratégias com probabilidade 1/2.

### Interpretações de estratégias mistas

Durante a década de 1980, o conceito de estratégias mistas foi alvo de críticas enormes por ser "intuitivamente problemático", uma vez que são equilíbrios de Nash fracos, e um jogador é indiferente sobre seguir sua probabilidade de estratégia de equilíbrio ou se desviar para alguma outra probabilidade. O teórico dos jogos Ariel Rubinstein descreve maneiras alternativas de entender o conceito. O primeiro, devido a Harsanyi (1973), é denominado purificação, e supõe que a interpretação das estratégias mistas reflete apenas o nosso desconhecimento das informações e do processo de tomada de decisão dos jogadores. As escolhas aparentemente aleatórias são então vistas como consequências de fatores exógenos não especificados e irrelevantes para o prêmio. Uma segunda interpretação imagina os jogadores representando uma grande população de agentes. Cada um dos agentes escolhe uma estratégia pura, e o retorno depende da fração de agentes que escolhem cada estratégia. A estratégia mista, portanto, representa a distribuição de estratégias puras escolhidas por cada população. No entanto, isso não fornece qualquer justificativa para o caso em que os jogadores são agentes individuais.
Mais tarde, Aumann e Brandenburger (1995) reinterpretaram o equilíbrio de Nash como um equilíbrio em crenças, ao invés de ações. Por exemplo, em pedra, papel e tesoura, um equilíbrio de crenças faria com que cada jogador acreditasse que o outro provavelmente jogaria cada estratégia. Esta interpretação enfraquece o poder descritivo do equilíbrio de Nash, entretanto, já que é possível em tal equilíbrio cada jogador realmente jogar uma estratégia pura de "pedra" em cada jogada do jogo — mesmo que, ao longo do tempo, as probabilidades sejam aquelas da estratégia mista.

### Estratégia de comportamento

Enquanto uma estratégia mista atribui uma distribuição de probabilidade sobre estratégias puras, uma estratégia de comportamento atribui a cada conjunto de informações uma distribuição de probabilidade sobre o conjunto de ações possíveis. Embora os dois conceitos estejam intimamente relacionados no contexto de jogos de forma normal, eles têm implicações muito diferentes para jogos de forma extensiva. Grosso modo, uma estratégia mista escolhe aleatoriamente um caminho determinístico na árvore do jogo, enquanto uma estratégia de comportamento pode ser vista como um caminho estocástico. A relação entre estratégias mistas e comportamentais é o tema do teorema de Kuhn, uma visão comportamental das hipóteses teóricas dos jogos tradicionais. O resultado estabelece que em qualquer jogo de forma extensiva finita com recordação perfeita, para qualquer jogador e qualquer estratégia mista, existe uma estratégia de comportamento que, contra todos os perfis de estratégias (de outros jogadores), induz a mesma distribuição naqueles nós terminais que a a estratégia mista sim. O contrário também é verdadeiro.
Um exemplo famoso de por que a memória perfeita é necessária para a equivalência é dado por Piccione e Rubinstein (1997) com seu jogo Absent-Minded Driver.

### Equivalência de Resultado

Equivalência de resultado combina a estratégia mista e comportamental do Jogador i em relação à estratégia pura do oponente do Jogador i. Equivalência de resultado é definida como a situação na qual, para qualquer estratégia mista e comportamental que o Jogador i adota, em resposta a qualquer estratégia pura que o oponente do Jogador I joga, a distribuição do resultado da estratégia mista e comportamental deve ser igual. Esta equivalência pode ser descrita pela seguinte fórmula: (Q ^ (U (i), S (-i))) (z) = (Q ^ (β (i), S (-i))) (z), onde U (i) descreve a estratégia mista do Jogador i, β (i) descreve a estratégia comportamental do Jogador i e S (-i) é a estratégia do oponente.

### Estratégia com memória perfeita

A memória perfeita é definida como a capacidade de cada jogador no jogo de lembrar e recordar todas as ações anteriores dentro do jogo. A memória perfeita é necessária para a equivalência, pois, em jogos finitos com recuperação imperfeita, haverá estratégias mistas existentes do Jogador I em que não há estratégia de comportamento equivalente. Isso está totalmente descrito no jogo Absent-Minded Driver formulado por Piccione e Rubinstein. Em suma, este jogo é baseado na tomada de decisão de um motorista com memória imperfeita, que precisa pegar a segunda saída da rodovia para chegar em casa, mas não lembra em qual cruzamento está ao chegar. A Figura [2] descreve este jogo.
Sem informações perfeitas (isto é, com informações imperfeitas), os jogadores fazem uma escolha em cada nó de decisão sem conhecimento das decisões que o precederam. Portanto, a estratégia mista de um jogador pode produzir resultados que sua estratégia comportamental não pode, e vice-versa. Isso é demonstrado no jogo Absent-minded Driver. Com a recuperação e as informações perfeitas, o motorista tem uma única estratégia pura, que é [continuar, sair], pois o motorista sabe em que interseção (ou nó de decisão) está quando chega a ela. Por outro lado, olhando apenas para o estágio de planejamento ideal, o retorno máximo é alcançado continuando em ambas as interseções, maximizado em p = 2/3 (referência). Este jogo simples para um jogador demonstra a importância da memória perfeita para a equivalência de resultados e seu impacto nos jogos de forma normal e estendida.

## Veja também

* Equilíbrio de Nash
* Haven (teoria dos grafos)
* Estratégia evolucionariamente estável