Equilíbrio de Nash - Nash equilibrium

Na teoria dos jogos , o equilíbrio de Nash , em homenagem ao matemático John Forbes Nash Jr. , é a forma mais comum de definir a solução de um jogo não cooperativo envolvendo dois ou mais jogadores. Em um equilíbrio de Nash, presume-se que cada jogador conhece as estratégias de equilíbrio dos outros jogadores e nenhum jogador tem nada a ganhar mudando apenas sua própria estratégia. O princípio do equilíbrio de Nash remonta à época de Cournot , que o aplicou a empresas concorrentes que escolhiam produtos.

Se cada jogador escolheu uma estratégia - um plano de ação escolhendo suas próprias ações com base no que aconteceu até agora no jogo - e nenhum jogador pode aumentar seu próprio retorno esperado mudando sua estratégia enquanto os outros jogadores mantêm a sua inalterada, então o atual conjunto de escolhas de estratégia constitui um equilíbrio de Nash.

Se dois jogadores, Alice e Bob, escolherem as estratégias A e B, (A, B) será um equilíbrio de Nash se Alice não tiver outra estratégia disponível que se saia melhor do que A em maximizar seu retorno em resposta a Bob escolher B e Bob não tiver outra estratégia disponível que se sai melhor do que B em maximizar seu retorno em resposta a Alice escolher A. Em um jogo em que Carol e Dan também são jogadores, (A, B, C, D) é um equilíbrio de Nash se A for a melhor resposta de Alice a ( B, C, D), B é a melhor resposta de Bob para (A, C, D) e assim por diante.

Nash mostrou que existe um equilíbrio de Nash para cada jogo finito: veja mais adiante o artigo sobre estratégia .

Formulários

Os teóricos dos jogos usam o equilíbrio de Nash para analisar o resultado da interação estratégica de vários tomadores de decisão . Em uma interação estratégica, o resultado para cada tomador de decisão depende das decisões dos outros e também das suas. O simples insight subjacente à ideia de Nash é que não se pode prever as escolhas de múltiplos tomadores de decisão se analisarmos essas decisões isoladamente. Em vez disso, deve-se perguntar o que cada jogador faria levando em consideração o que espera que os outros façam. O equilíbrio de Nash requer que suas escolhas sejam consistentes: nenhum jogador deseja desfazer sua decisão dado o que os outros estão decidindo.

O conceito foi usado para analisar situações hostis, como guerras e corridas armamentistas (veja o dilema do prisioneiro ), e também como o conflito pode ser mitigado por interação repetida (veja tit-for-tat ). Também tem sido usado para estudar até que ponto as pessoas com preferências diferentes podem cooperar (veja a batalha dos sexos ) e se elas correrão riscos para alcançar um resultado cooperativo (veja a caça ao veado ). Tem sido utilizado para estudar a adoção de normas técnicas e também a ocorrência de corridas a bancos e crises cambiais (ver jogo de coordenação ). Outras aplicações incluem fluxo de tráfego (ver o princípio de Wardrop ), como organizar leilões (ver teoria do leilão ), o resultado de esforços exercidos por várias partes no processo de educação, legislação regulatória, como regulamentações ambientais (veja a tragédia dos comuns ), recursos naturais gerenciamento, analisando estratégias de marketing, até mesmo pênaltis no futebol (veja os centavos correspondentes ), sistemas de energia, sistemas de transporte, problemas de evacuação e comunicações sem fio.

História

Equilíbrio de Nash é nomeado após matemático americano John Forbes Nash Jr . A mesma ideia foi usada em uma aplicação particular em 1838 por Antoine Augustin Cournot em sua teoria do oligopólio . Na teoria de Cournot, cada uma das várias empresas escolhe quanto produto deve produzir para maximizar seu lucro. O melhor resultado para uma empresa depende dos resultados das outras. Um equilíbrio de Cournot ocorre quando o produto de cada empresa maximiza seus lucros, dado o produto das outras empresas, que é um equilíbrio de Nash de estratégia pura . Cournot também introduziu o conceito de melhor dinâmica de resposta em sua análise da estabilidade do equilíbrio. Cournot não usou a ideia em nenhuma outra aplicação, no entanto, nem a definiu de maneira geral.

O conceito moderno de equilíbrio de Nash é, em vez disso, definido em termos de estratégias mistas , onde os jogadores escolhem uma distribuição de probabilidade em vez de estratégias puras possíveis (o que pode colocar 100% da probabilidade em uma estratégia pura; tais estratégias puras são um subconjunto de estratégias mistas). O conceito de equilíbrio de estratégia mista foi introduzido por John von Neumann e Oskar Morgenstern em seu livro de 1944 The Theory of Games and Economic Behavior , mas sua análise se restringiu ao caso especial dos jogos de soma zero . Eles mostraram que um equilíbrio de Nash de estratégia mista existirá para qualquer jogo de soma zero com um conjunto finito de ações. A contribuição de Nash em seu artigo de 1951 "Jogos não cooperativos" foi definir um equilíbrio de Nash de estratégia mista para qualquer jogo com um conjunto finito de ações e provar que pelo menos um equilíbrio de Nash (de estratégia mista) deve existir em tal jogos. A chave para a capacidade de Nash de provar a existência de maneira muito mais geral do que von Neumann está em sua definição de equilíbrio. De acordo com Nash, "um ponto de equilíbrio é uma n-tupla de modo que a estratégia mista de cada jogador maximiza seu retorno se as estratégias dos outros forem mantidas fixas. Assim, a estratégia de cada jogador é ótima em relação às dos outros". Colocar o problema nesta estrutura permitiu que Nash empregasse o teorema do ponto fixo de Kakutani em seu artigo de 1950 para provar a existência de equilíbrios. Seu artigo de 1951 usou o teorema de ponto fixo de Brouwer mais simples para o mesmo propósito.

Os teóricos dos jogos descobriram que, em algumas circunstâncias, o equilíbrio de Nash faz previsões inválidas ou falha em fazer uma previsão única. Eles propuseram muitos conceitos de solução ('refinamentos' dos equilíbrios de Nash) projetados para descartar equilíbrios de Nash implausíveis. Uma questão particularmente importante é que alguns equilíbrios de Nash podem ser baseados em ameaças que não são ' credíveis '. Em 1965, Reinhard Selten propôs o equilíbrio perfeito do subjogo como um refinamento que elimina equilíbrios que dependem de ameaças não confiáveis . Outras extensões do conceito de equilíbrio de Nash abordaram o que acontece se um jogo for repetido ou o que acontece se um jogo for jogado na ausência de informações completas . No entanto, refinamentos e extensões subsequentes do equilíbrio de Nash compartilham o insight principal no qual o conceito de Nash se baseia: o equilíbrio é um conjunto de estratégias de modo que a estratégia de cada jogador seja ótima, dadas as escolhas dos outros.

Definições

Equilíbrio de Nash

Um perfil de estratégia é um conjunto de estratégias, uma para cada jogador. Informalmente, um perfil de estratégia é um equilíbrio de Nash se nenhum jogador puder fazer melhor mudando unilateralmente sua estratégia. Para ver o que isso significa, imagine que cada jogador conhece as estratégias dos outros. Suponha então que cada jogador se pergunte: "Conhecendo as estratégias dos outros jogadores e tratando as estratégias dos outros jogadores como gravadas na pedra, posso me beneficiar mudando minha estratégia?"

Se algum jogador pudesse responder "Sim", então esse conjunto de estratégias não é um equilíbrio de Nash. Mas se cada jogador prefere não trocar (ou é indiferente entre trocar ou não), então o perfil da estratégia é um equilíbrio de Nash. Assim, cada estratégia em um equilíbrio de Nash é a melhor resposta às estratégias dos outros jogadores nesse equilíbrio.

Formalmente, deixe ser o conjunto de todas as estratégias possíveis para o jogador , onde . Deixe ser um perfil de estratégia, um conjunto constituído por uma estratégia para cada jogador, onde denota as estratégias de todos os jogadores exceto . Seja o payoff do jogador i em função das estratégias. O perfil da estratégia é um equilíbrio de Nash se ${\ displaystyle S_ {i}}$${\ displaystyle i}$${\ displaystyle i = 1, \ ldots, N}$${\ displaystyle s ^ {*} = (s_ {i} ^ {*}, s _ {- i} ^ {*})}$${\ displaystyle s _ {- i} ^ {*}}$${\ displaystyle N-1}$${\ displaystyle i}$${\ displaystyle u_ {i} (s_ {i}, s _ {- i} ^ {*})}$${\ displaystyle s ^ {*}}$

${\ displaystyle u_ {i} (s_ {i} ^ {*}, s _ {- i} ^ {*}) \ geq u_ {i} (s_ {i}, s _ {- i} ^ {*}) \ ; \; {\ rm {para \; todos}} \; \; s_ {i} \ in S_ {i}}$

Um jogo pode ter mais de um equilíbrio de Nash. Mesmo que o equilíbrio seja único, pode ser fraco : um jogador pode ser indiferente entre várias estratégias dadas as escolhas dos outros jogadores. É único e denominado equilíbrio de Nash estrito se a desigualdade for estrita, de modo que uma estratégia é a melhor resposta única:

${\ displaystyle u_ {i} (s_ {i} ^ {*}, s _ {- i} ^ {*})> u_ {i} (s_ {i}, s _ {- i} ^ {*}) \; \; {\ rm {para \; todos}} \; \; s_ {i} \ in S_ {i}, s_ {i} \ neq s_ {i} ^ {*}}$

Observe que o conjunto de estratégias pode ser diferente para jogadores diferentes, e seus elementos podem ser uma variedade de objetos matemáticos. Mais simplesmente, um jogador pode escolher entre duas estratégias, por exemplo, Ou, o conjunto de estratégias pode ser um conjunto finito de estratégias condicionais respondendo a outros jogadores, por exemplo , Ou pode ser um conjunto infinito, um contínuo ou ilimitado, por exemplo, tal que é um número real não negativo. As provas de existência de Nash pressupõem um conjunto de estratégias finito, mas o conceito de equilíbrio de Nash não o exige. ${\ displaystyle S_ {i}}$${\ displaystyle S_ {i} = \ {{\ text {Sim}}, {\ text {Não}} \}.}$${\ displaystyle S_ {i} = \ {{\ text {Sim}} | p = {\ text {Baixo}}, {\ text {Não}} | p = {\ text {Alto}} \}.}$${\ displaystyle S_ {i} = \ {{\ text {Price}} \}}$${\ displaystyle {\ text {Preço}}}$

O equilíbrio de Nash pode às vezes parecer não racional em uma perspectiva de terceira pessoa. Isso ocorre porque um equilíbrio de Nash não é necessariamente o ideal de Pareto .

O equilíbrio de Nash também pode ter consequências não racionais em jogos sequenciais porque os jogadores podem "ameaçar" uns aos outros com ameaças que na verdade não executariam. Para tais jogos, o equilíbrio de Nash perfeito do subjogo pode ser mais significativo como uma ferramenta de análise.

Equilíbrio Estrito / Fraco

Suponha que no equilíbrio de Nash, cada jogador se pergunte: "Conhecendo as estratégias dos outros jogadores e tratando as estratégias dos outros jogadores como gravadas na pedra, eu sofreria uma perda mudando minha estratégia?"

Se a resposta de cada jogador for "Sim", então o equilíbrio é classificado como um equilíbrio de Nash estrito .

Se, em vez disso, para algum jogador, houver igualdade exata entre a estratégia no equilíbrio de Nash e alguma outra estratégia que dê exatamente o mesmo pagamento (ou seja, esse jogador é indiferente entre trocar e não), então o equilíbrio é classificado como um equilíbrio de Nash fraco .

Um jogo pode ter um equilíbrio de Nash de estratégia pura ou mista . (No último caso, uma estratégia pura é escolhida estocasticamente com uma probabilidade fixa ).

Teorema de existência de Nash

Nash provou que se estratégias mistas (onde um jogador escolhe probabilidades de usar várias estratégias puras) são permitidas, então todo jogo com um número finito de jogadores em que cada jogador pode escolher entre muitas estratégias puras finitas tem pelo menos um equilíbrio de Nash, que pode ser uma estratégia pura para cada jogador ou pode ser uma distribuição de probabilidade sobre estratégias para cada jogador.

O equilíbrio de Nash não precisa existir se o conjunto de escolhas for infinito e não compacto. Um exemplo é um jogo em que dois jogadores simultaneamente nomeiam um número e o jogador que atribui o maior número vence. Outro exemplo é onde cada um dos dois jogadores escolhe um número real estritamente menor que 5 e o vencedor é aquele que tiver o maior número; nenhum maior número estritamente inferior a 5 existe (se o número pudesse ser igual a 5, o equilíbrio de Nash teria ambos os jogadores escolhendo 5 e empatando o jogo). No entanto, existe um equilíbrio de Nash se o conjunto de escolhas for compacto com o payoff de cada jogador contínuo nas estratégias de todos os jogadores.

Exemplos

Jogo de coordenação

O jogo de coordenação é um jogo clássico de dois jogadores e duas estratégias , conforme mostrado na matriz de pagamento de exemplo à direita. Existem dois equilíbrios de estratégia pura, (A, A) com payoff 4 para cada jogador e (B, B) com payoff 2 para cada um. A combinação (B, B) é um equilíbrio de Nash porque se qualquer um dos jogadores mudar unilateralmente sua estratégia de B para A, seu payoff cairá de 2 para 1.

Um exemplo famoso de jogo de coordenação é a caça ao veado . Dois jogadores podem escolher caçar um veado ou coelho, o veado fornecendo mais carne (4 unidades utilitárias, 2 para cada jogador) do que o coelho (1 unidade utilitária). A ressalva é que o cervo deve ser caçado cooperativamente, então se um jogador tentar caçar o cervo, enquanto o outro caça o coelho, o caçador de cervos falhará totalmente, com uma recompensa de 0, enquanto o caçador de coelhos terá sucesso, pois uma recompensa de 1. O jogo tem dois equilíbrios, (veado, veado) e (coelho, coelho), porque a estratégia ótima de um jogador depende de sua expectativa sobre o que o outro jogador fará. Se um caçador confia que o outro caçará o cervo, ele deve caçar o cervo; entretanto, se ele achar que o outro caçará o coelho, ele também caçará o coelho. Esse jogo é usado como uma analogia para a cooperação social, uma vez que muito do benefício que as pessoas obtêm na sociedade depende da cooperação e da confiança implícita entre as pessoas para agirem de maneira correspondente à cooperação.

Dirigir em uma estrada contra um carro que se aproxima e ter que escolher entre desviar para a esquerda ou para a direita também é um jogo de coordenação. Por exemplo, com os payoffs 10 significando nenhuma falha e 0 significando uma falha, o jogo de coordenação pode ser definido com a seguinte matriz de payoffs:

Nesse caso, há dois equilíbrios de Nash de estratégia pura, quando ambos optam por dirigir à esquerda ou à direita. Se admitirmos estratégias mistas (onde uma estratégia pura é escolhida ao acaso, sujeita a alguma probabilidade fixa), então existem três equilíbrios de Nash para o mesmo caso: dois vimos da forma de estratégia pura, onde as probabilidades são (0 %, 100%) para o jogador um, (0%, 100%) para o jogador dois; e (100%, 0%) para o jogador um, (100%, 0%) para o jogador dois, respectivamente. Adicionamos outro onde as probabilidades de cada jogador são (50%, 50%).

Tráfego de rede

Gráfico de rede de amostra. Os valores nas bordas são o tempo de viagem experimentado por um 'carro' viajando por essa borda. x é o número de carros que passam por essa borda.

Uma aplicação do equilíbrio de Nash consiste em determinar o fluxo esperado de tráfego em uma rede. Considere o gráfico à direita. Se assumirmos que existem x "carros" viajando de A para D, qual é a distribuição de tráfego esperada na rede?

Esta situação pode ser modelada como um "jogo" onde cada viajante tem uma escolha de 3 estratégias, onde cada estratégia é uma rota de A a D (um de ABD , ABCD ou ACD ). A "recompensa" de cada estratégia é o tempo de viagem de cada rota. No gráfico à direita, um carro viajando via ABD experimenta um tempo de viagem de (1+ x / 100) +2 , onde x é o número de carros viajando na borda AB . Portanto, os payoffs de qualquer estratégia dependem das escolhas dos outros jogadores, como de costume. No entanto, o objetivo, neste caso, é minimizar o tempo de viagem, não maximizá-lo. O equilíbrio ocorrerá quando o tempo em todos os caminhos for exatamente o mesmo. Quando isso acontece, nenhum motorista sozinho tem qualquer incentivo para mudar de rota, uma vez que isso só pode aumentar seu tempo de viagem. Para o gráfico à direita, se, por exemplo, 100 carros estão viajando de A para D, então o equilíbrio ocorrerá quando 25 motoristas viajarem via ABD , 50 via ABCD e 25 via ACD . Cada motorista agora tem um tempo total de viagem de 3,75 (para ver isso, observe que um total de 75 carros levam a borda AB e, da mesma forma, 75 carros tomam a borda CD ).

Observe que essa distribuição não é, na verdade, socialmente ideal. Se os 100 carros concordassem que 50 viajam via ABD e os outros 50 via ACD , o tempo de viagem para qualquer carro seria 3,5, que é menos de 3,75. Esse também é o equilíbrio de Nash se o caminho entre B e C for removido, o que significa que adicionar outra rota possível pode diminuir a eficiência do sistema, um fenômeno conhecido como paradoxo de Braess .

Jogo de competição

Isso pode ser ilustrado por um jogo para dois jogadores em que ambos os jogadores escolhem simultaneamente um número inteiro de 0 a 3 e ambos ganham o menor dos dois números em pontos. Além disso, se um jogador escolher um número maior do que o outro, ele terá que ceder dois pontos para o outro.

Este jogo tem um equilíbrio de Nash de estratégia pura único: ambos os jogadores escolhem 0 (destacado em vermelho claro). Qualquer outra estratégia pode ser melhorada por um jogador trocando seu número para um a menos que o do outro jogador. Na mesa adjacente, se o jogo começar no quadrado verde, é do interesse do jogador 1 ir para o quadrado roxo e do jogador 2 ir para o quadrado azul. Embora não se encaixe na definição de um jogo de competição, se o jogo for modificado para que os dois jogadores ganhem a quantia indicada se ambos escolherem o mesmo número e, de outra forma, não ganharem nada, então existem 4 equilíbrios de Nash: (0,0 ), (1,1), (2,2) e (3,3).

Equilíbrio de Nash em uma matriz de payoff

Existe uma maneira numérica fácil de identificar os equilíbrios de Nash em uma matriz de payoff. É especialmente útil em jogos para duas pessoas, onde os jogadores têm mais de duas estratégias. Nesse caso, a análise formal pode se tornar muito longa. Esta regra não se aplica ao caso em que estratégias mistas (estocásticas) são de interesse. A regra é a seguinte: se o primeiro número de payoff, no par de payoff da célula, é o máximo da coluna da célula e se o segundo número é o máximo da linha da célula - então a célula representa um Nash equilíbrio.

Podemos aplicar esta regra a uma matriz 3 × 3:

Usando a regra, podemos muito rapidamente (muito mais rápido do que com a análise formal) ver que as células de equilíbrio de Nash são (B, A), (A, B) e (C, C). De fato, para a célula (B, A) 40 é o máximo da primeira coluna e 25 é o máximo da segunda linha. Para (A, B) 25 é o máximo da segunda coluna e 40 é o máximo da primeira linha. O mesmo para a célula (C, C). Para outras células, um ou ambos os membros do duplet não são o máximo das linhas e colunas correspondentes.

Dito isso, a mecânica real de encontrar células de equilíbrio é óbvia: encontre o máximo de uma coluna e verifique se o segundo membro do par é o máximo da linha. Se essas condições forem atendidas, a célula representa um equilíbrio de Nash. Verifique todas as colunas desta forma para encontrar todas as células NE. Uma matriz N × N pode ter entre 0 e N × N equilíbrios de Nash de estratégia pura .

Estabilidade

O conceito de estabilidade , útil na análise de muitos tipos de equilíbrios, também pode ser aplicado aos equilíbrios de Nash.

Um equilíbrio de Nash para um jogo de estratégia mista é estável se uma pequena mudança (especificamente, uma mudança infinitesimal) nas probabilidades de um jogador leva a uma situação em que duas condições se mantêm:

1. o jogador que não mudou não tem melhor estratégia na nova circunstância
2. o jogador que mudou agora está jogando com uma estratégia estritamente pior.

Se esses casos forem atendidos, um jogador com a pequena mudança em sua estratégia mista retornará imediatamente ao equilíbrio de Nash. O equilíbrio é considerado estável. Se a condição um não for válida, o equilíbrio é instável. Se apenas a condição um for mantida, é provável que haja um número infinito de estratégias ótimas para o jogador que mudou.

No exemplo do "jogo de direção" acima, existem equilíbrios estáveis ​​e instáveis. Os equilíbrios envolvendo estratégias mistas com 100% de probabilidade são estáveis. Se qualquer um dos jogadores mudar ligeiramente suas probabilidades, ambos ficarão em desvantagem e seu oponente não terá razão para mudar sua estratégia. O equilíbrio (50%, 50%) é instável. Se um dos jogadores mudar suas probabilidades (o que não beneficiaria ou prejudicaria a expectativa do jogador que fez a mudança, se a estratégia mista do outro jogador ainda for (50%, 50%)), então o outro jogador imediatamente tem uma estratégia melhor em (0%, 100%) ou (100%, 0%).

A estabilidade é crucial nas aplicações práticas do equilíbrio de Nash, uma vez que a estratégia mista de cada jogador não é perfeitamente conhecida, mas deve ser inferida a partir da distribuição estatística de suas ações no jogo. Nesse caso, é muito improvável que os equilíbrios instáveis ​​surjam na prática, uma vez que qualquer mudança minuciosa nas proporções de cada estratégia vista levará a uma mudança na estratégia e ao colapso do equilíbrio.

O equilíbrio de Nash define estabilidade apenas em termos de desvios unilaterais. Em jogos cooperativos, esse conceito não é convincente o suficiente. O equilíbrio de Nash forte permite desvios em todas as coalizões concebíveis. Formalmente, um equilíbrio de Nash forte é um equilíbrio de Nash em que nenhuma coalizão, tomando as ações de seus complementos como dadas, pode desviar-se cooperativamente de uma forma que beneficie todos os seus membros. No entanto, o forte conceito de Nash às vezes é percebido como muito "forte", pois o ambiente permite comunicação privada ilimitada. Na verdade, o equilíbrio de Nash forte deve ser eficiente de Pareto . Como resultado desses requisitos, o Nash forte é muito raro para ser útil em muitos ramos da teoria dos jogos. No entanto, em jogos como eleições com muito mais jogadores do que resultados possíveis, pode ser mais comum do que um equilíbrio estável.

Um equilíbrio de Nash refinado, conhecido como equilíbrio de Nash à prova de coalizão (CPNE), ocorre quando os jogadores não conseguem se sair melhor, mesmo que tenham permissão para se comunicar e fazer um acordo "auto-impositivo" para se desviar. Cada estratégia correlacionada suportada por dominância estrita iterada e na fronteira de Pareto é um CPNE. Além disso, é possível que um jogo tenha um equilíbrio de Nash resiliente contra coalizões menores que um tamanho especificado, k. CPNE está relacionado à teoria do núcleo .

Finalmente, na década de oitenta, construindo com grande profundidade sobre essas ideias , os equilíbrios estáveis ​​de Mertens foram introduzidos como um conceito de solução . Os equilíbrios estáveis ​​de Mertens satisfazem a indução direta e a indução retroativa . Em um contexto de teoria dos jogos, equilíbrios estáveis agora geralmente se referem aos equilíbrios estáveis ​​de Mertens.

Ocorrência

Se um jogo tem um equilíbrio de Nash único e é jogado entre jogadores sob certas condições, então o conjunto de estratégias NE será adotado. As condições suficientes para garantir que o equilíbrio de Nash seja executado são:

1. Todos os jogadores farão o possível para maximizar o retorno esperado conforme descrito pelo jogo.
2. Os jogadores são perfeitos na execução.
3. Os jogadores têm inteligência suficiente para deduzir a solução.
4. Os jogadores conhecem a estratégia de equilíbrio planejada de todos os outros jogadores.
5. Os jogadores acreditam que um desvio em sua própria estratégia não causará desvios por parte de outros jogadores.
6. É do conhecimento geral que todos os jogadores atendem a essas condições, incluindo este. Portanto, não apenas cada jogador deve saber que os outros jogadores cumprem as condições, mas também devem saber que todos sabem que as encontram, e saber que sabem que sabem que as cumprem, e assim por diante.

Onde as condições não são atendidas

Exemplos de problemas de teoria dos jogos em que essas condições não são atendidas:

1. A primeira condição não é atendida se o jogo não descreve corretamente as quantidades que um jogador deseja maximizar. Nesse caso, não há nenhuma razão particular para aquele jogador adotar uma estratégia de equilíbrio. Por exemplo, o dilema do prisioneiro não é um dilema se qualquer um dos jogadores ficar feliz em ficar preso indefinidamente.
2. Imperfeição intencional ou acidental na execução. Por exemplo, um computador capaz de jogar lógico sem falhas diante de um segundo computador sem falhas resultará em equilíbrio. A introdução da imperfeição levará ao seu rompimento, seja por derrota para o jogador que comete o erro, seja pela negação do critério de conhecimento comum que leva à possível vitória do jogador. (Um exemplo seria um jogador repentinamente colocando o carro em marcha à ré no jogo da galinha , garantindo um cenário sem perda e sem vitória).
3. Em muitos casos, a terceira condição não é atendida porque, embora o equilíbrio deva existir, ele é desconhecido devido à complexidade do jogo, por exemplo no xadrez chinês . Ou, se conhecido, pode não ser conhecido de todos os jogadores, como quando se joga jogo da velha com uma criança pequena que deseja desesperadamente vencer (atendendo aos outros critérios).
4. O critério do conhecimento comum pode não ser atendido mesmo que todos os jogadores, de fato, atendam a todos os outros critérios. Jogadores que desconfiam erroneamente da racionalidade uns dos outros podem adotar estratégias contrárias ao jogo irracional esperado em nome de seus oponentes. Esta é uma consideração importante em " galinhas " ou uma corrida armamentista , por exemplo.

Onde as condições são atendidas

Em seu Ph.D. dissertação, John Nash propôs duas interpretações de seu conceito de equilíbrio, com o objetivo de mostrar como os pontos de equilíbrio podem ser conectados com fenômenos observáveis.

(...) Uma interpretação é racionalista: se assumirmos que os jogadores são racionais, conhecem a estrutura completa do jogo, o jogo é jogado apenas uma vez e há apenas um equilíbrio de Nash, então os jogadores jogarão de acordo com esse equilíbrio .

Esta ideia foi formalizada por Aumann, R. e A. Brandenburger, 1995, Epistemic Conditions for Nash Equilibrium , Econometrica, 63, 1161-1180 que interpretou a estratégia mista de cada jogador como uma conjectura sobre o comportamento de outros jogadores e mostraram que se o jogo e a racionalidade dos jogadores são mutuamente conhecidos e essas conjecturas são comumente conhecidas, então as conjecturas devem ser um equilíbrio de Nash (uma suposição anterior comum é necessária para este resultado em geral, mas não no caso de dois jogadores. Neste caso, as conjecturas só precisam ser mutuamente conhecidas).

Uma segunda interpretação, que Nash se refere à interpretação da ação em massa, é menos exigente para os jogadores:

[i] Não é necessário assumir que os participantes têm pleno conhecimento da estrutura total do jogo, ou a habilidade e inclinação para passar por quaisquer processos complexos de raciocínio. O que se presume é que haja uma população de participantes para cada posição no jogo, que será jogada ao longo do tempo por participantes sorteados aleatoriamente nas diferentes populações. Se houver uma frequência média estável com a qual cada estratégia pura é empregada pelo membro médio da população apropriada, essa frequência média estável constitui um equilíbrio de Nash de estratégia mista.

Para obter um resultado formal ao longo dessas linhas, consulte Kuhn, H. e et al., 1996, "The Work of John Nash in Game Theory", Journal of Economic Theory , 69, 153-185.

Devido às condições limitadas em que NE pode realmente ser observado, eles raramente são tratados como um guia para o comportamento do dia-a-dia, ou observados na prática em negociações humanas. No entanto, como conceito teórico em economia e biologia evolutiva , o NE tem poder explicativo. A recompensa em economia é a utilidade (ou às vezes dinheiro), e em biologia evolutiva é a transmissão gênica; ambos são os resultados fundamentais da sobrevivência. Os pesquisadores que aplicam a teoria dos jogos nesses campos afirmam que as estratégias que não conseguem maximizá-los por qualquer motivo serão eliminadas do mercado ou do ambiente, aos quais é atribuída a capacidade de testar todas as estratégias. Esta conclusão é tirada da teoria da " estabilidade " acima. Nessas situações, a suposição de que a estratégia observada é na verdade uma EN tem sido frequentemente confirmada por pesquisas.

NE e ameaças não credíveis

Ilustrações extensas e de forma normal que mostram a diferença entre SPNE e outros NE. O equilíbrio azul não é um subjogo perfeito porque o jogador dois faz uma ameaça não crível em 2 (2) de ser cruel (U).

O equilíbrio de Nash é um superconjunto do equilíbrio de Nash perfeito do subjogo. O equilíbrio perfeito do subjogo, além do equilíbrio de Nash, requer que a estratégia também seja um equilíbrio de Nash em todos os subjogos desse jogo. Isso elimina todas as ameaças não credíveis , ou seja, estratégias que contêm movimentos não racionais para fazer o contra-jogador mudar sua estratégia.

A imagem à direita mostra um jogo sequencial simples que ilustra o problema com os equilíbrios de Nash imperfeitos do subjogo. Neste jogo, o jogador escolhe a esquerda (L) ou direita (R), o que é seguido pelo jogador dois sendo chamado a ser gentil (K) ou indelicado (U) com o jogador um. No entanto, o jogador dois só tem a ganhar por ser indelicado se o jogador um for para a esquerda. Se o jogador um der certo, o jogador racional dois seria de fato gentil com ele / ela naquele subjogo. No entanto, a ameaça não crível de ser cruel em 2 (2) ainda faz parte do equilíbrio de Nash azul (L, (U, U)). Portanto, se o comportamento racional pode ser esperado por ambas as partes, o equilíbrio de Nash perfeito do subjogo pode ser um conceito de solução mais significativo quando tais inconsistências dinâmicas surgem.

Prova de existência

Prova usando o teorema do ponto fixo de Kakutani

A prova original de Nash (em sua tese) usou o teorema do ponto fixo de Brouwer (por exemplo, veja abaixo uma variante). Fornecemos uma prova mais simples por meio do teorema do ponto fixo de Kakutani , seguindo o artigo de Nash de 1950 (ele credita a David Gale a observação de que tal simplificação é possível).

Para provar a existência de um equilíbrio de Nash, seja a melhor resposta do jogador i às estratégias de todos os outros jogadores. ${\ displaystyle r_ {i} (\ sigma _ {- i})}$

${\ displaystyle r_ {i} (\ sigma _ {- i}) = \ mathop {\ underset {\ sigma _ {i}} {\ operatorname {arg \, max}}} u_ {i} (\ sigma _ { i}, \ sigma _ {- i})}$

Aqui, onde , está um perfil de estratégia mista no conjunto de todas as estratégias combinadas e é a função de recompensa para o jogador i. Defina uma função com valor definido de forma que . A existência de um equilíbrio de Nash é equivalente a ter um ponto fixo. ${\ displaystyle \ sigma \ in \ Sigma}$${\ displaystyle \ Sigma = \ Sigma _ {i} \ times \ Sigma _ {- i}}$${\ displaystyle u_ {i}}$ ${\ displaystyle r \ colon \ Sigma \ rightarrow 2 ^ {\ Sigma}}$${\ displaystyle r = r_ {i} (\ sigma _ {- i}) \ times r _ {- i} (\ sigma _ {i})}$${\ displaystyle r}$

O teorema do ponto fixo de Kakutani garante a existência de um ponto fixo se as seguintes quatro condições forem satisfeitas.

1. ${\ displaystyle \ Sigma}$ é compacto, convexo e não vazio.
2. ${\ displaystyle r (\ sigma)}$ não está vazio.
3. ${\ displaystyle r (\ sigma)}$é hemicontínuo superior
4. ${\ displaystyle r (\ sigma)}$ é convexo.

A condição 1. é satisfeita pelo fato de ser um simplex e, portanto, compacto. A convexidade decorre da capacidade dos jogadores de misturar estratégias. não é vazio, desde que os jogadores tenham estratégias. ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$

As condições 2 e 3 são satisfeitas por meio do teorema do máximo de Berge . Por ser contínuo e compacto, é não vazio e hemicontínuo superior . ${\ displaystyle u_ {i}}$${\ displaystyle r (\ sigma _ {i})}$

A condição 4. é satisfeita como resultado de estratégias mistas. Suponha , então . ou seja, se duas estratégias maximizam os payoffs, então uma combinação entre as duas estratégias produzirá o mesmo payoff. ${\ displaystyle \ sigma _ {i}, \ sigma '_ {i} \ in r (\ sigma _ {- i})}$${\ displaystyle \ lambda \ sigma _ {i} + (1- \ lambda) \ sigma '_ {i} \ in r (\ sigma _ {- i})}$

Portanto, existe um ponto fixo e um equilíbrio de Nash. ${\ displaystyle r}$

Quando Nash apresentou esse ponto a John von Neumann em 1949, von Neumann o famoso descartou com as palavras: "Isso é trivial, você sabe. É apenas um teorema de ponto fixo ." (Veja Nasar, 1998, p. 94.)

Prova alternativa usando o teorema de ponto fixo de Brouwer

Temos um jogo onde está o número de jogadores e é a ação definida para os jogadores. Todos os conjuntos de ações são finitos. Vamos denotar o conjunto de estratégias mistas para os jogadores. A finitude do s garante a compactação de . ${\ displaystyle G = (N, A, u)}$${\ displaystyle N}$${\ displaystyle A = A_ {1} \ times \ cdots \ times A_ {N}}$${\ displaystyle A_ {i}}$${\ displaystyle \ Delta = \ Delta _ {1} \ times \ cdots \ times \ Delta _ {N}}$${\ displaystyle A_ {i}}$${\ displaystyle \ Delta}$

Agora podemos definir as funções de ganho. Para uma estratégia mista , deixamos o ganho para o jogador em ação ser ${\ displaystyle \ sigma \ in \ Delta}$${\ displaystyle i}$${\ displaystyle a \ in A_ {i}}$

${\ displaystyle {\ text {Ganho}} _ {i} (\ sigma, a) = \ max \ {0, u_ {i} (a, \ sigma _ {- i}) - u_ {i} (\ sigma _ {i}, \ sigma _ {- i}) \}.}$

A função de ganho representa o benefício que um jogador obtém ao mudar unilateralmente sua estratégia. Agora definimos onde ${\ displaystyle g = (g_ {1}, \ dotsc, g_ {N})}$

${\ displaystyle g_ {i} (\ sigma) (a) = \ sigma _ {i} (a) + {\ text {Ganho}} _ {i} (\ sigma, a)}$

para . Nós vemos que ${\ displaystyle \ sigma \ in \ Delta, a \ in A_ {i}}$

${\ displaystyle \ sum _ {a \ in A_ {i}} g_ {i} (\ sigma) (a) = \ sum _ {a \ in A_ {i}} \ sigma _ {i} (a) + { \ text {Ganho}} _ {i} (\ sigma, a) = 1 + \ sum _ {a \ in A_ {i}} {\ text {Ganho}} _ {i} (\ sigma, a)> 0 .}$

Em seguida, definimos:

${\ displaystyle {\ begin {cases} f = (f_ {1}, \ cdots, f_ {N}): \ Delta \ to \ Delta \\ f_ {i} (\ sigma) (a) = {\ frac { g_ {i} (\ sigma) (a)} {\ sum _ {b \ in A_ {i}} g_ {i} (\ sigma) (b)}} & a \ in A_ {i} \ end {cases} }}$

É fácil ver que cada uma é uma estratégia mista válida em . Também é fácil verificar se cada uma é uma função contínua de e, portanto, é uma função contínua. Como produto cruzado de um número finito de conjuntos convexos compactos, também é compacto e convexo. Aplicando o teorema do ponto fixo de Brouwer para e concluímos que tem um ponto fixo em , chame-o . Afirmamos que é um equilíbrio de Nash em . Para tanto, basta mostrar que ${\ displaystyle f_ {i}}$${\ displaystyle \ Delta _ {i}}$${\ displaystyle f_ {i}}$${\ displaystyle \ sigma}$${\ displaystyle f}$${\ displaystyle \ Delta}$${\ displaystyle f}$${\ displaystyle \ Delta}$${\ displaystyle f}$${\ displaystyle \ Delta}$${\ displaystyle \ sigma ^ {*}}$${\ displaystyle \ sigma ^ {*}}$${\ displaystyle G}$

${\ displaystyle \ forall i \ in \ {1, \ cdots, N \}, \ forall a \ in A_ {i}: \ quad {\ text {Ganho}} _ {i} (\ sigma ^ {*}, a) = 0.}$

Isso simplesmente afirma que cada jogador não ganha nenhum benefício ao mudar unilateralmente sua estratégia, que é exatamente a condição necessária para um equilíbrio de Nash.

Agora suponha que os ganhos não sejam todos zero. Portanto, e tal isso . Observe então que ${\ displaystyle \ exists i \ in \ {1, \ cdots, N \},}$${\ displaystyle a \ in A_ {i}}$${\ displaystyle {\ text {Ganho}} _ {i} (\ sigma ^ {*}, a)> 0}$

${\ displaystyle \ sum _ {a \ in A_ {i}} g_ {i} (\ sigma ^ {*}, a) = 1 + \ sum _ {a \ in A_ {i}} {\ text {Ganho} } _ {i} (\ sigma ^ {*}, a)> 1.}$

Então deixe

${\ displaystyle C = \ sum _ {a \ in A_ {i}} g_ {i} (\ sigma ^ {*}, a).}$

Também devemos denotar como o vetor de ganho indexado por ações em . Como é o ponto fixo, temos: ${\ displaystyle {\ text {Ganho}} (i, \ cdot)}$${\ displaystyle A_ {i}}$${\ displaystyle \ sigma ^ {*}}$

${\ displaystyle {\ begin {alinhado} \ sigma ^ {*} = f (\ sigma ^ {*}) & \ Rightarrow \ sigma _ {i} ^ {*} = f_ {i} (\ sigma ^ {*} ) \\ & \ Rightarrow \ sigma _ {i} ^ {*} = {\ frac {g_ {i} (\ sigma ^ {*})} {\ sum _ {a \ in A_ {i}} g_ {i } (\ sigma ^ {*}) (a)}} \\ [6pt] & \ Rightarrow \ sigma _ {i} ^ {*} = {\ frac {1} {C}} \ left (\ sigma _ { i} ^ {*} + {\ text {Ganho}} _ {i} (\ sigma ^ {*}, \ cdot) \ right) \\ [6pt] & \ Rightarrow C \ sigma _ {i} ^ {* } = \ sigma _ {i} ^ {*} + {\ text {Ganho}} _ {i} (\ sigma ^ {*}, \ cdot) \\ & \ Rightarrow \ left (C-1 \ right) \ sigma _ {i} ^ {*} = {\ text {Ganho}} _ {i} (\ sigma ^ {*}, \ cdot) \\ & \ Rightarrow \ sigma _ {i} ^ {*} = \ left ({\ frac {1} {C-1}} \ right) {\ text {Ganho}} _ {i} (\ sigma ^ {*}, \ cdot). \ end {alinhado}}}$

Uma vez que temos isso, é uma escala positiva do vetor . Agora afirmamos que ${\ displaystyle C> 1}$${\ displaystyle \ sigma _ {i} ^ {*}}$${\ displaystyle {\ text {Ganho}} _ {i} (\ sigma ^ {*}, \ cdot)}$

${\ displaystyle \ forall a \ in A_ {i}: \ quad \ sigma _ {i} ^ {*} (a) (u_ {i} (a_ {i}, \ sigma _ {- i} ^ {*} ) -u_ {i} (\ sigma _ {i} ^ {*}, \ sigma _ {- i} ^ {*})) = \ sigma _ {i} ^ {*} (a) {\ text {Ganho }} _ {i} (\ sigma ^ {*}, a)}$

Para ver isso, primeiro observamos que, se isso for verdade, por definição da função de ganho. Agora assuma isso . Por nossas declarações anteriores, temos que ${\ displaystyle {\ text {Ganho}} _ {i} (\ sigma ^ {*}, a)> 0}$${\ displaystyle {\ text {Ganho}} _ {i} (\ sigma ^ {*}, a) = 0}$

${\ displaystyle \ sigma _ {i} ^ {*} (a) = \ left ({\ frac {1} {C-1}} \ right) {\ text {Ganho}} _ {i} (\ sigma ^ {*}, a) = 0}$

e, portanto, o termo à esquerda é zero, o que nos dá que toda a expressão é conforme necessário. ${\ displaystyle 0}$

Então, finalmente temos isso

${\ displaystyle {\ begin {alinhados} 0 & = u_ {i} (\ sigma _ {i} ^ {*}, \ sigma _ {- i} ^ {*}) - u_ {i} (\ sigma _ {i } ^ {*}, \ sigma _ {- i} ^ {*}) \\ & = \ left (\ sum _ {a \ in A_ {i}} \ sigma _ {i} ^ {*} (a) u_ {i} (a_ {i}, \ sigma _ {- i} ^ {*}) \ right) -u_ {i} (\ sigma _ {i} ^ {*}, \ sigma _ {- i} ^ {*}) \\ & = \ sum _ {a \ in A_ {i}} \ sigma _ {i} ^ {*} (a) (u_ {i} (a_ {i}, \ sigma _ {- i } ^ {*}) - u_ {i} (\ sigma _ {i} ^ {*}, \ sigma _ {- i} ^ {*})) \\ & = \ sum _ {a \ in A_ {i }} \ sigma _ {i} ^ {*} (a) {\ text {Ganho}} _ {i} (\ sigma ^ {*}, a) && {\ text {pelas afirmações anteriores}} \\ & = \ sum _ {a \ in A_ {i}} \ left (C-1 \ right) \ sigma _ {i} ^ {*} (a) ^ {2}> 0 \ end {alinhado}}}$

onde a última desigualdade segue uma vez que é um vetor diferente de zero. Mas esta é uma contradição clara, portanto, todos os ganhos devem de fato ser zero. Portanto, é um equilíbrio de Nash para conforme necessário. ${\ displaystyle \ sigma _ {i} ^ {*}}$${\ displaystyle \ sigma ^ {*}}$${\ displaystyle G}$

Calculando equilíbrios de Nash

Se um jogador A tem uma estratégia dominante, então existe um equilíbrio de Nash no qual A joga . No caso de dois jogadores A e B, existe um equilíbrio de Nash em que A joga e B joga a melhor resposta . Se for uma estratégia estritamente dominante, A joga em todos os equilíbrios de Nash. Se A e B têm estratégias estritamente dominantes, existe um equilíbrio de Nash único em que cada um joga sua estratégia estritamente dominante. ${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$

Em jogos com equilíbrios de Nash de estratégia mista, a probabilidade de um jogador escolher qualquer estratégia particular (tão pura) pode ser calculada atribuindo uma variável a cada estratégia que representa uma probabilidade fixa para escolher essa estratégia. Para que um jogador esteja disposto a randomizar, seu retorno esperado para cada estratégia (pura) deve ser o mesmo. Além disso, a soma das probabilidades para cada estratégia de um determinado jogador deve ser 1. Isso cria um sistema de equações a partir do qual as probabilidades de escolha de cada estratégia podem ser derivadas.

Exemplos

No jogo de combinar centavos, o jogador A perde um ponto para B se A e B jogarem a mesma estratégia e ganha um ponto de B se eles jogarem estratégias diferentes. Para calcular o equilíbrio de Nash de estratégia mista, atribua a A a probabilidade p de jogar H e (1− p ) de jogar T e atribua a B a probabilidade q de jogar H e (1− q ) de jogar T.

E [recompensa para A jogando H] = (−1) q + (+1) (1− q ) = 1−2 q

E [recompensa para A jogando T] = (+1) q + (−1) (1− q ) = 2 q −1

E [recompensa para A jogando H] = E [recompensa para A jogando T] ⇒ 1−2 q = 2 q −1 ⇒ q = 1/2

E [ganho para B jogando H] = (+1) p + (−1) (1− p ) = 2 p −1

E [recompensa para B jogando T] = (−1) p + (+1) (1− p ) = 1−2 p

E [recompensa para B jogando H] = E [recompensa para B jogando T] ⇒ 2 p −1 = 1−2 p ⇒ p = 1/2

Assim, um equilíbrio de Nash de estratégia mista, neste jogo, é para cada jogador escolher aleatoriamente H ou T com p = 1/2 eq = 1/2.

Estranheza de pontos de equilíbrio

Em 1971, Robert Wilson propôs o Teorema da Estranheza, que afirma que "quase todos" os jogos finitos têm um número finito e um número ímpar de equilíbrios de Nash. Em 1993, Harsanyi publicou uma prova alternativa do resultado. "Quase todos" aqui significa que qualquer jogo com um número infinito ou par de equilíbrios é muito especial no sentido de que, se seus payoffs fossem perturbados de forma levemente aleatória, com probabilidade um, em vez disso, teria um número ímpar de equilíbrios.

O dilema do prisioneiro , por exemplo, tem um equilíbrio, enquanto a batalha dos sexos tem três - dois puros e um misto, e isso permanece verdadeiro mesmo que as recompensas mudem ligeiramente. O jogo de dinheiro grátis é um exemplo de jogo "especial" com um número par de equilíbrios. Nele, dois jogadores devem votar "sim" em vez de "não" para receber uma recompensa e os votos são simultâneos. Existem dois equilíbrios de Nash de estratégia pura, (sim, sim) e (não, não), e nenhum equilíbrio de estratégia mista, porque a estratégia "sim" domina fracamente "não". "Sim" é tão bom quanto "não" independentemente da ação do outro jogador, mas se houver alguma chance de o outro jogador escolher "sim", então "sim" é a melhor resposta. Sob uma pequena perturbação aleatória dos payoffs, entretanto, a probabilidade de que quaisquer dois payoffs permaneçam empatados, seja em 0 ou em algum outro número, é extremamente pequena, e o jogo teria um ou três equilíbrios.

Veja também

Notas

Referências

Livros didáticos de teoria dos jogos

Artigos originais de Nash

Outras referências

links externos

• "Teorema de Nash (na teoria dos jogos)" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Prova Completa de Existência de Equilíbrio de Nash
• Formulário Simplificado e Resultados Relacionados