Estratégia (teoria do jogo) - Strategy (game theory)
Na teoria dos jogos , um jogador 's estratégia é uma das opções que escolher em um ambiente onde o resultado depende não só em suas próprias acções , mas sobre as 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, monopólio, diplomacia ou navio de guerra. 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 adotadas 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 a2 para b3). A 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.
Conjunto de estratégia
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 e tesoura de papel 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 {pedra de papel tesoura}.
Caso contrário, um conjunto de estratégias é infinito. Por exemplo, o jogo de corte de bolo tem um continuum limitado de estratégias no conjunto de estratégias {Corte em qualquer lugar entre zero por cento e 100 por cento do bolo}.
Em um jogo dinâmico , jogos que são 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 quais ofertas aceitar e quais rejeitar.
Em um jogo Bayesiano , ou jogos nos quais os jogadores têm informações incompletas uns sobre os outros, o conjunto de estratégias é semelhante ao de um jogo dinâmico. Consiste em regras para as ações a serem tomadas em relação a qualquer possível informação privada.
Escolha de 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 simultaneamente solucionável e 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 Ultimatum, 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 eles fazem no decorrer do jogo. Em particular, 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.) Como as probabilidades são contínuas, há uma infinidade de 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 "recompensa esperada".
Claro, pode-se considerar uma estratégia pura como 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 misturadas são importantes para o refinamento do equilíbrio , como equilíbrio perfeito da mão trêmula .)
Estratégia mista
Ilustração
Em um chute de pênalti de 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 na qual ele é melhor no chute, que é para a esquerda se ele for destro. A matriz para o jogo de futebol ilustra essa situação, uma forma simplificada do jogo estudada por Chiappori, Levitt e Groseclose (2002). Ele assume que, se o goleiro adivinhar corretamente, o chute é bloqueado, o que é definido como o payoff base de 0 para ambos os jogadores. Se o goleiro adivinhar errado, é mais provável que o chute ocorra se for para a esquerda (payoffs de +2 para o chutador e -2 para o goleiro) do que se for para a direita (o payoff menor de +1 para chutador e -1 para o goleiro).
| Goleiro | |||
| Inclinar-se para a esquerda | Lean Right | ||
| Kicker | Chute para a esquerda | 0, 0 | +2, -2 |
| 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 Kicker se desviaria para a direita e aumentaria seu payoff de 0 para 1 .
O equilíbrio de estratégia mista do chutador é encontrado a partir do fato de que eles se desviarão da randomização, a menos que seus payoffs 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 payoff do Lean Left de k (0) + (1-k) (- 1) seja igual ao payoff do Lean Right de k (-2) + (1 -k) (0), então k = 1/3. Assim, o equilíbrio de estratégia mista é (Prob (Kick Left) = 1/3, (Prob (Lean Left) = 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 a direção em que 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 uma escolha aleatória e que os chutadores chutam para seu lado favorito 45% das vezes e os goleiros tendem para esse lado 57% das vezes. Seu artigo é 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 os equilíbrios 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 cervo ). 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 fogo pesado 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 payoff. 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 uma tesoura de papel de pedra, 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, uma vez que é possível em tal equilíbrio para cada jogador realmente jogar uma estratégia pura de Rock em cada jogada do jogo, mesmo que com o tempo as probabilidades sejam as 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 dos 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 nos nós terminais que a a estratégia mista sim. O inverso 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 recordação perfeita
A recordação perfeita é definida como a capacidade de cada jogador no jogo de lembrar e recordar todas as ações anteriores dentro do jogo. A recuperação 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 se encontra ao chegar lá. A Figura [2] descreve este jogo.
Sem informações perfeitas (isto é, 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 recall e informações perfeitos, o motorista tem uma única estratégia pura, que é [continuar, sair], já que o motorista sabe em qual interseção (ou nó de decisão) se encontra quando chega a ela. Por outro lado, olhando apenas para o estágio de planejamento ideal, o ganho 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 recordação perfeita para a equivalência de resultados e seu impacto nos jogos de forma normal e estendida.