Equilíbrio de Nash

Na teoria dos jogos, o Nash Equilibrium é o conceito de solução mais comumente usado para jogos não cooperativos. Um equilíbrio de Nash é uma situação em que nenhum jogador poderia ganhar mudando sua própria estratégia (mantendo todos os outros jogadores - estratégias fixa). A idéia de Nash Equilibrium remonta à época de Cournot, que em 1838 a aplicou ao seu modelo de competição em um oligopólio.

Se cada jogador escolheu uma estratégia - um plano de ação com base no que aconteceu até agora no jogo - e ninguém pode aumentar o próprio retorno esperado, alterando a estratégia de uma delas enquanto os outros jogadores Mantenha o deles inalterado, então o conjunto atual de opções de estratégia constitui um equilíbrio de Nash.

Se dois jogadores Alice e Bob escolhem as estratégias A e B, (a, b) é um equilíbrio de Nash se Alice não tiver outra estratégia disponível que se sai melhor do que A em maximizar sua recompensa em resposta a Bob escolhendo B, e Bob tem Nenhuma outra estratégia disponível que se sai melhor do que B em maximizar sua recompensa em resposta à escolha de Alice 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 Alice &# 39; a melhor resposta a (b, c, d), b é a melhor resposta de Bob ' a (a, c, d) e assim por diante.

Nash mostrou que há um equilíbrio de Nash, possivelmente em estratégias mistas, para todos os jogos finitos.

Os teóricos do jogo 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 da sua. A insight simples subjacente à idéia de Nash é que não se pode prever as escolhas de vários tomadores de decisão se analisar essas decisões isoladamente. Em vez disso, é preciso perguntar o que cada jogador faria levando em consideração o que o jogador espera que os outros façam. O Equilíbrio de Nash exige que as opções 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 o dilema de guerras e armas (consulte o dilema do prisioneiro) e também como o conflito pode ser mitigado pela interação repetida (ver tit-for-tat). Também tem sido usado para estudar até que ponto as pessoas com preferências diferentes podem cooperar (ver Batalha dos Sexos) e se elas correrão riscos para alcançar um resultado cooperativo (ver Stag Hunt). Foi usado para estudar a adoção de padrões técnicos e também a ocorrência de corridas bancárias e crises de moeda (consulte o jogo de coordenação). Outras aplicações incluem fluxo de tráfego (consulte o princípio do Wardrop), como organizar leilões (ver teoria do leilão), o resultado dos esforços exercidos por várias partes no processo educacional, legislação regulatória, como regulamentos ambientais (ver tragédia do Commons ), Gerenciamento de Recursos Naturais, Analisando Estratégias de Marketing, Penalidade Chega no Futebol (consulte Pennies correspondentes), navegação por robôs em multidões, sistemas de energia, sistemas de transporte, problemas de evacuação e comunicações sem fio.

O equilíbrio de Nash recebeu o nome do matemático americano John Forbes Nash Jr. A mesma idéia foi usada em uma aplicação específica em 1838 por Antoine Augustin Cournot em sua teoria do oligopólio. Na teoria de Cournot, cada uma das várias empresas escolhem quanta produção produzir para maximizar seu lucro. A melhor saída para uma empresa depende das saídas dos outros. Um equilíbrio de Cournot ocorre quando a saída de cada empresa maximiza seus lucros, dada a saída 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 idéia em nenhum outro aplicativo, no entanto, nem a definiu em geral.

O conceito moderno de equilíbrio de Nash é definido em termos de estratégias mistas, onde os jogadores escolhem uma distribuição de probabilidade sobre possíveis estratégias puras (que podem colocar 100% da probabilidade em uma estratégia pura; essas estratégias puras são um subconjunto de misto estratégias). O conceito de equilíbrio de estratégia misto foi introduzido por John von Neumann e Oskar Morgenstern em seu livro de 1944 A teoria dos jogos e comportamento econômico , mas a análise deles foi restrita ao caso especial de jogos zero de soma . Eles mostraram que um equilíbrio de Nash de estratégia mista existirá para qualquer jogo de soma zero com um conjunto de ações finitas. 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 de ações finitas e provar que pelo menos um (estratégia mista) Nash Equilibrium deve existir nesse jogo. A chave da capacidade de Nash de provar a existência muito mais de maneira mais geral do que Von Neumann estava em sua definição de equilíbrio. De acordo com Nash, um ponto de equilíbrio é uma tupla n, de modo que a estratégia mista de cada jogador maximize [seu] retorno se as estratégias dos outros forem mantidas. Assim, a estratégia de cada jogador é ideal contra os dos outros. " Colocar o problema nessa 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 mais simples de Brouwer, para o mesmo objetivo.

Os teóricos do jogo descobriram que, em algumas circunstâncias, o Nash Equilibrium faz previsões inválidas ou falha em fazer uma previsão única. Eles propuseram muitos conceitos de solução (' refinamentos ' de Nash Equilibria) 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 subgame como um refinamento que elimina os equilíbrios que dependem de ameaças não crédicas. 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, os refinamentos e extensões subsequentes do equilíbrio de Nash compartilham o principal insight sobre o qual repousa o conceito de Nash: o equilíbrio é um conjunto de estratégias para que a estratégia de cada jogador seja ideal, dadas as escolhas dos outros.

Um perfil de estratégia é um conjunto de estratégias, um para cada jogador. Informalmente, um perfil de estratégia é um equilíbrio de Nash se nenhum jogador puder se sair melhor mudando unilateralmente sua estratégia. Para ver o que isso significa, imagine que cada jogador seja informado das estratégias dos outros. Suponha então que cada jogador se pergunte: "Conhecendo as estratégias dos outros jogadores e tratar as estratégias dos outros jogadores como estabelecidos em pedra, posso me beneficiar alterando minha estratégia? "

Por exemplo, se um jogador preferir - sim ", então esse conjunto de estratégias não é um equilíbrio de Nash. Mas se todo jogador prefere não alternar (ou for indiferente entre a comutação e não), o perfil de estratégia é um equilíbrio de Nash. Assim, cada estratégia em um equilíbrio de Nash é a melhor resposta para os outros jogadores ' Estratégias nesse equilíbrio.

Formalmente, deixe $Não. S_{i}}$ ser o conjunto de todas as estratégias possíveis para o jogador $Não.$, onde $- Sim.$. Vamos. ${\displaystyle s^{*}=(s_{i}^{*},s_{-i}^{*}) ?$ ser um perfil de estratégia, um conjunto que consiste em uma estratégia para cada jogador, onde $Não. s_{-i}^{*}}$ denota o $Não.$ estratégias de todos os jogadores, exceto $Não.$. Vamos. ${\displaystyle u_{i}(s_{i},s_{-i}^{*}) ?$ ser jogador i's payoff como uma função das estratégias. O perfil de estratégia ${\displaystyle s^{*}}$ é um equilíbrio de Nash se

${\displaystyle u_{i}(s_{i}^{*},s_{-i}^{*}) O que é? u_{i}(s_{i},s_{-i}^{*})\;\;{\rm {for\;all}}\;\;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, considerando os outros jogadores ' escolhas. É único e chamado de Equilíbrio de Nash rigoroso se a desigualdade for estrita, portanto, uma estratégia é a melhor resposta única:

${\displaystyle u_{i}(s_{i}^{*},s_{-i}^{*})>u_{i}(s_{i},s_{-i}^{*})\;\;{\rm {for\;all}}\;\;s_{i}\in S_{i},s_{i}\neq s_{i}^{*}}$

O conjunto de estratégia $Não. S_{i}}$ pode ser diferente para diferentes jogadores, e seus elementos podem ser uma variedade de objetos matemáticos. Mais simplesmente, um jogador pode escolher entre duas estratégias, por exemplo. $Não. S_{i}=\{{\text{Yes}},{\text{No}}\}.}$ Ou, o conjunto de estratégia pode ser um conjunto finito de estratégias condicionais respondendo a outros jogadores, por exemplo. $Não. S_{i}=\{{\text{Yes}}|p={\text{Low}},{\text{No}}|p={\text{High}}\}.}$ Ou, pode ser um conjunto infinito, um continuum ou unbounded, por exemplo. $Não. S_{i}=\{{\text{Price}}\}}}}$ tal que ${\displaystyle {\text{Price}}}$ é um número real não negativo. As provas existentes de Nash assumem um conjunto de estratégia finito, mas o conceito de equilíbrio de Nash não o exige.

Um jogo pode ter uma estratégia pura ou um equilíbrio de Nash de estratégia mista. Neste último, uma estratégia pura é escolhida estocástica com uma probabilidade fixa.

Suponha que no equilíbrio de Nash, cada jogador se pergunta: "Conhecendo as estratégias dos outros jogadores e tratando as estratégias dos outros jogadores como ambientado, eu sofreria uma perda ao mudar minha estratégia? "

Se a resposta de todo jogador for é classificada como um equilíbrio de Nash rigoroso.

Se, em vez disso, para algum jogador, existe uma igualdade exata entre a estratégia no equilíbrio de Nash e alguma outra estratégia que fornece exatamente o mesmo pagamento (ou seja, o jogador é indiferente entre a comutação e não), então o equilíbrio é classificado como A < I> FRACO ou Equilíbrio de Nash não estrito .

O equilíbrio de Nash define estabilidade apenas em termos de desvios individuais do jogador. Nos jogos cooperativos, esse conceito não é convincente o suficiente. O forte equilíbrio de Nash permite desvios por todas as coalizões concebíveis. Formalmente, um forte equilíbrio de Nash é um equilíbrio de Nash, no qual nenhuma coalizão, tomando as ações de seus complementos conforme dada, pode se desviar de uma maneira que beneficie todos os seus membros. No entanto, o forte conceito de Nash às vezes é percebido como também " forte " Nisso, o ambiente permite comunicação privada ilimitada. De fato, o forte equilíbrio de Nash deve ser eficiente em relação ao Pareto. Como resultado desses requisitos, o forte Nash é raro demais para ser útil em muitos ramos da teoria dos jogos. No entanto, em jogos como eleições com muito mais jogadores do que possíveis resultados, pode ser mais comum do que um equilíbrio estável.

Um equilíbrio refinado de Nash conhecido como equilíbrio de Nash à prova de coalizão (CPNE) ocorre quando os jogadores não podem se sair melhor, mesmo que possam se comunicar e fazer com que se auto-reforçam " acordo para desviar. Toda estratégia correlacionada apoiada pela dominância rigorosa iterada e na fronteira de Pareto é uma CPNE. Além disso, é possível que um jogo tenha um equilíbrio de Nash que seja resiliente contra coalizões menos que um tamanho especificado, k. O CPNE está relacionado à teoria do núcleo.

Nash provou que, se estratégias mistas (onde um jogador escolher probabilidades de usar várias estratégias puras) forem permitidas, todos os jogos com um número finito de jogadores nos quais cada jogador pode escolher entre muitas estratégias puras têm pelo menos um equilíbrio de Nash (NE), que pode ser uma estratégia pura para cada jogador ou pode ser uma distribuição de probabilidade sobre estratégias para cada jogador.

Os

equilíbrios Nash não precisam existir se o conjunto de opções for infinito e não compacto. Por exemplo:

• Um jogo onde dois jogadores simultaneamente nomeiam um número e o jogador nomeando o número maior ganha não tem um NE, já que o conjunto de escolhas não é compacto porque ele é unbounded.
• Cada um de dois jogadores escolhe um número real estritamente menos de 5 e o vencedor é quem tem o maior número; nenhum número maior estritamente menos de 5 existe (se o número poderia igual 5, o equilíbrio Nash teria ambos os jogadores escolhendo 5 e amarrando o jogo). Aqui, o conjunto de escolhas não é compacto porque não está fechado.

No entanto, existe um equilíbrio de Nash se o conjunto de opções for compacto com a recompensa de cada jogador nas estratégias de todos os jogadores.

Rosen estendeu o teorema da existência de Nash de várias maneiras. Ele considera um jogo N-Player, no qual a estratégia de cada jogador i é um vetor s i no espaço euclidiano r mi . .+ M n ; Portanto, uma tupla de estratégia é um vetor em r m . Parte da definição de um jogo é um subconjunto s de r m , de modo que a tupla de estratégia deve estar em s . Isso significa que as ações dos jogadores podem ser potencialmente restringidas com base em ações de outros jogadores. Um caso especial comum do modelo é quando s é um produto cartesiano de conjuntos convexos s 1 , ..., s < Sub> n , de modo que a estratégia do jogador i deve estar em s i . Isso representa o caso de que as ações de cada jogador i são restringidas independentemente de outros jogadores ' ações. Se as seguintes condições mantiverem:

• T é convexo, fechado e limitado;
• Cada função de pagamento u_Eu... é contínuo nas estratégias de todos os jogadores, e côncavo em S_Eu... para cada valor fixo de S_{- Não.Eu...}.

então existe um equilíbrio de Nash. A prova usa o teorema de ponto fixo de Kakutani. Rosen também prova que, sob certas condições técnicas que incluem concavidade estrita, o equilíbrio é único.

O resultado

de Nash se refere ao caso especial em que cada um s I De todos os jogadores são funções bilineares das estratégias.

O equilíbrio de Nash às vezes pode 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 seqüenciais porque os jogadores podem ameaçar " com ameaças que eles realmente não realizariam. Para esses jogos, o equilíbrio de Nash Perfect Subgame pode ser mais significativo como uma ferramenta de análise.

Um jogo de coordenação mostrando pagamentos para o jogador 1 (row) \ jogador 2 (coluna)

Estratégia do Jogador 1	Estratégia do Jogador 2
	Jogador 2 adota estratégia A	Jogador 2 adota estratégia B
Jogador 1 adota estratégia A	4 4	3 1
Jogador 1 adota estratégia B	1 3	2 2

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

The Stag Hunt

Estratégia do Jogador 1	Estratégia do Jogador 2
	Escada de caça	Caça coelho
Escada de caça	2 2	1 0
Caça coelho	0 1	1 1

Um exemplo famoso de um jogo de coordenação é a caça ao veado. Dois jogadores podem optar por caçar um veado ou um coelho, o veado fornecendo mais carne (4 unidades de utilidade, 2 para cada jogador) do que o coelho (1 unidade de utilidade). A ressalva é que o veado deve ser caçado cooperativamente; portanto, se um jogador tentar caçar o veado, enquanto o outro caça o coelho, o caçador de veados falhará totalmente, por uma recompensa de 0, enquanto o caçador de coelhos terá sucesso, para um Pagão de 1. O jogo tem dois equilíbrios (Stag, Stag) e (Rabbit, Rabbit), porque a estratégia ideal de um jogador depende de sua expectativa do que o outro jogador fará. Se um caçador confia que o outro caçará o veado, deve caçar o veado; No entanto, se eles acharem que o outro caçará o coelho, eles também caçarão o coelho. Este jogo é usado como uma analogia para a cooperação social, uma vez que grande parte do benefício que as pessoas ganham na sociedade depende das pessoas que cooperam e confiam implicitamente para agir de uma maneira correspondente à cooperação.

Dirigindo em uma estrada contra um carro que se aproxima e ter que optar por desviar à esquerda ou desviar à direita da estrada, também é um jogo de coordenação. Por exemplo, com payoffs 10, significando nenhum acidente e 0 significando um acidente, o jogo de coordenação pode ser definido com a seguinte matriz de pagamento:

O jogo de condução

Estratégia do Jogador 1	Estratégia do Jogador 2
	Dirigir à esquerda	Conduzir à direita
Dirigir à esquerda	10. 10.	0 0
Conduzir à direita	0 0	10. 10.

Nesse caso, existem dois equilíbrios de Nash de estratégia pura, quando ambos optam por dirigir à esquerda ou à direita. Se admitirmos estratégias contraditórias (onde uma estratégia pura é escolhida aleatoriamente, sujeita a alguma probabilidade fixa), existem três equilíbrios de Nash para o mesmo caso: dois que vimos na 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 para cada jogador são (50%, 50%).

Uma aplicação de equilibria Nash está na determinação do fluxo esperado de tráfego em uma rede. Considere o gráfico à direita. Se assumirmos que há $Não.$ "carros" viajando de A para D, qual é a distribuição esperada do tráfego na rede?

Esta situação pode ser modelada como um "jogo", onde cada viajante tem uma escolha de 3 estratégias e onde cada estratégia é uma rota de A para D (um de ABD, ABCDou ACD). O "payoff" de cada estratégia é o tempo de viagem de cada rota. No gráfico à direita, um carro viajando via ABD tempo de viagem de experiências ${\displaystyle 1+{\frac {x}{100}}+2}$, onde $Não.$ é o número de carros que viajam na borda AB. Assim, os pagamentos para qualquer estratégia dada dependem das escolhas dos outros jogadores, como é habitual. No entanto, o objetivo, neste caso, é minimizar o tempo de viagem, não o maximizar. Equilíbrio ocorrerá quando o tempo em todos os caminhos for exatamente o mesmo. Quando isso acontece, nenhum único motorista tem qualquer incentivo para mudar rotas, uma vez que só pode adicionar ao 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 ABD, 50 via ABCD, e 25 via ACD. Cada motorista agora tem um tempo total de viagem de 3.75 (para ver isso, um total de 75 carros tomar o AB borda, e também, 75 carros tomar o CD-ROM borda).

Observe que essa distribuição não é, na verdade, socialmente ideal. Se os 100 carros concordaram que 50 viagens via abd e os outros 50 através de acd , o tempo de viagem para qualquer carro único seria realmente ser 3,5, que é inferior a 3,75. Este também é o equilíbrio de Nash se o caminho entre b e c for removido, o que significa que a adição de outra rota possível pode diminuir a Eficiência do sistema, um fenômeno conhecido como paradoxo de Braess.

Um jogo de competição

Estratégia do Jogador 1	Estratégia do Jogador 2
	Escolha "0"	Escolha "1"	Escolha "2"	Escolha "3"
Escolha "0"	0, 0	2, -2	2, -2	2, -2
Escolha "1"	-2, 2	1, 1	3, - Sim.	3, - Sim.
Escolha "2"	-2, 2	- Sim., 3	2, 2	4, 0
Escolha "3"	-2, 2	- Sim., 3	0, 4	3, 3

Isso pode ser ilustrado por um jogo de dois jogadores, no qual 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 que o outro, terá que desistir de dois pontos para o outro.

Este jogo tem um equilíbrio exclusivo de Nash de estratégia pura: os dois jogadores escolhendo 0 (destacados em vermelho claro). Qualquer outra estratégia pode ser aprimorada por um jogador alternando seu número para um menos que o do outro jogador. Na tabela adjacente, se o jogo começar na Praça Verde, é do interesse do jogador 1 de se mudar para a praça roxa e é do interesse do jogador 2 de se mudar para a praça azul. Embora não se encaixasse na definição de um jogo de competição, se o jogo for modificado para que os dois jogadores ganhem o valor nomeado se ambos escolherem o mesmo número e, de outra forma, não ganharem nada, então existem 4 Equilibria de Nash: (0,0 ), (1,1), (2,2) e (3,3).

Existe uma maneira numérica fácil de identificar os equilíbrios de Nash em uma matriz de pagamento. É especialmente útil em jogos de 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 as estratégias mistas (estocásticas) são de interesse. A regra é da seguinte representa um equilíbrio de Nash.

Uma matriz de pagamento – Nash equilibria em negrito

Estratégia do Jogador 1	Estratégia do Jogador 2
	Opção A	Opção B	Opção C
Opção A	0, 0	25, 40	5, 10
Opção B	40, 25	0, 0	5, 15
Opção C	10, 5	15, 5	10, 10

Podemos aplicar esta regra a uma matriz 3 × 3:

Usando a regra, podemos muito rapidamente (muito mais rápido do que com 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 se aplica à célula (C, C). Para outras células, um ou ambos os membros do Duplo não são o máximo das linhas e colunas correspondentes.

Dito isto, 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 dessa maneira para encontrar todas as células NE. Uma matriz n × n pode ter entre 0 e n × n equilíbrios NASH de estratégia pura.

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 levar a uma situação em que duas condições 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. Diz -se que o equilíbrio é estável. Se a condição não se mantém, o equilíbrio será instável. Se apenas condicionar que se mantém, provavelmente haverá um número infinito de estratégias ideais para o jogador que mudou.

no jogo de direção " Exemplo acima, existem equilíbrios estáveis e instáveis. Os equilíbrios envolvendo estratégias mistas com 100% de probabilidades são estáveis. Se um dos jogadores mudarem um pouco suas probabilidades, elas estarão em desvantagem, e seu oponente não terá motivos para mudar sua estratégia por sua vez. O equilíbrio (50%, 50%) é instável. Se um dos jogadores mudar suas probabilidades (o que não beneficiaria ou danificariam a expectativa do jogador que fez a mudança, se a estratégia mista do outro jogador ainda for (50%, 50%)), o outro jogador imediatamente o fez Uma estratégia melhor em (0%, 100%) ou (100%, 0%).

A estabilidade é crucial em aplicações práticas do Equilíbrios 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, é improvável que os equilíbrios instáveis surjam na prática, uma vez que qualquer minuto alteração nas proporções de cada estratégia observada levará a uma mudança na estratégia e à quebra do equilíbrio.

Finalmente, nos anos 80, construindo com grande profundidade em tais idéias, os equilíbrios estáveis para Mertens foram introduzidos como um conceito de solução. Os equilíbrios estáveis de Mertens satisfazem a indução para a frente e a indução para trás. Em um contexto de teoria dos jogos, os equilíbrios estáveis agora geralmente se referem a equilíbrios estáveis de Mertens.

Ocorrência

Se um jogo tiver um equilíbrio exclusivo de Nash e for jogado entre os jogadores sob determinadas condições, o conjunto de estratégia NE será adotado. Condições suficientes para garantir que o equilíbrio de Nash seja reproduzido são:

1. Todos os jogadores farão o máximo para maximizar seu pagamento esperado, conforme descrito pelo jogo.
2. Os jogadores são impecáveis 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 outros jogadores.
6. Há conhecimento comum de que todos os jogadores cumprem essas condições, incluindo esta. Então, não só cada jogador deve saber que os outros jogadores cumprem as condições, mas também eles devem saber que todos eles sabem que eles os encontram, e sabem que eles sabem que eles conhecem e assim por diante.

Quando as condições não forem cumpridas

Exemplos de problemas da teoria dos jogos nos quais essas condições não são atendidas:

1. A primeira condição não é satisfeita se o jogo não descrever corretamente as quantidades que um jogador deseja maximizar. Neste caso, não há nenhuma razão particular para que o jogador adote uma estratégia de equilíbrio. Por exemplo, o dilema do prisioneiro não é um dilema se qualquer jogador está feliz por ser preso indefinidamente.
2. imperfeição intencional ou acidental na execução. Por exemplo, um computador capaz de jogo lógico impecável enfrentando um segundo computador impecável resultará em equilíbrio. A introdução da imperfeição levará à sua ruptura, seja através da perda para o jogador que comete o erro, ou através da negação do critério de conhecimento comum levando à possível vitória para o jogador. (Um exemplo seria um jogador de repente colocando o carro em reverso no jogo de frango, garantindo um cenário sem perder nenhum-ganho).
3. Em muitos casos, a terceira condição não é satisfeita porque, embora o equilíbrio deve existir, é desconhecido devido à complexidade do jogo, por exemplo no xadrez chinês. Ou, se conhecido, pode não ser conhecido por todos os jogadores, como ao jogar tic-tac-toe com uma criança pequena que desesperadamente quer ganhar (metendo os outros critérios).
4. O critério do conhecimento comum pode não ser cumprido mesmo que todos os jogadores, de fato, atendam a todos os outros critérios. Os jogadores erroneamente desconfiando da racionalidade uns dos outros podem adotar contra-estratégias para o jogo irracional esperado em nome de seus oponentes. Esta é uma grande consideração em "frango" ou uma corrida de armas, por exemplo.

Quando as condições são cumpridas

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 ao fenômeno observável.

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

Essa idéia foi formalizada por R. Aumann e A. Brandenburger, 1995, Condições epistêmicas para Nash Equilibrium , Econometrica, 63, 1161-1180 que interpretaram a estratégia mista de cada jogador; Conjectura sobre o comportamento de outros jogadores e demonstraram que, se o jogo e a racionalidade dos jogadores são conhecidos mutuamente e essas conjecturas forem conhecidas, as conjecturas devem ser um equilíbrio de Nash (uma suposição anterior comum é necessária para esse resultado em geral, Mas não no caso de dois jogadores.

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

[i]t é desnecessário assumir que os participantes têm pleno conhecimento da estrutura total do jogo, ou a capacidade e inclinação para passar por qualquer processo de raciocínio complexo. O que é assumido é que há uma população de participantes para cada posição no jogo, que será jogado ao longo do tempo pelos participantes sorteados aleatoriamente das diferentes populações. Se houver uma frequência média estável com a qual cada estratégia pura é empregada por Membro médio da população adequada, então esta frequência média estável constitui uma estratégia mista equilíbrio de Nash.

Para um resultado formal nesse sentido, consulte Kuhn, H. e et al., 1996, " O trabalho de John Nash na teoria dos jogos ", Journal of Economic Theory , 69, 153-185.

Devido às condições limitadas em que o NE pode realmente ser observado, elas raramente são tratadas como um guia para o comportamento do dia-a-dia ou observadas na prática nas negociações humanas. No entanto, como um conceito teórico em economia e biologia evolutiva, o NE tem poder explicativo. A recompensa na economia é a utilidade (ou às vezes dinheiro), e na biologia evolutiva é a transmissão de genes; Ambos são os fundamentos fundamentais de sobrevivência. Os pesquisadores que aplicam a teoria dos jogos nesses campos afirmam que as estratégias que não conseguem maximizá -las por qualquer motivo serão competidas fora do mercado ou ambiente, que são atribuídas a capacidade de testar todas as estratégias. Esta conclusão é tirada da estabilidade " teoria acima. Nessas situações, a suposição de que a estratégia observada é na verdade uma NE muitas vezes foi confirmada por pesquisas.

O equilíbrio de Nash é um superconjunto do equilíbrio de Nash Perfect Subgame. O equilíbrio perfeito do subgame, além do equilíbrio de Nash, exige que a estratégia também seja um equilíbrio de Nash em todos os sub -jogos desse jogo. Isso elimina todas as ameaças não crédicas, ou seja, estratégias que contêm movimentos não racionais, a fim de fazer com que o contra-jogador mude sua estratégia.

A imagem à direita mostra um jogo seqüencial simples que ilustra o problema com os equilíbrios de Nash imperfeitos do subgame. Neste jogo, o jogador um escolhe esquerda (L) ou direita (R), que é seguido pelo jogador dois sendo chamado a ser gentil (k) ou cruel (U) para o jogador um, no entanto, o jogador dois só ganha por ser Desarranjo se o jogador um for para a esquerda. Se o jogador um for certo, o jogador racional dois seria gentil com ela nesse sub -jogo. No entanto, a ameaça não crédulo de ser cruel em 2 (2) ainda faz parte do equilíbrio azul (L, (U, U)). Portanto, se o comportamento racional puder ser esperado por ambas as partes, o equilíbrio perfeito de Nash no subgame pode ser um conceito de solução mais significativo quando essas inconsistências dinâmicas surgirem.

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

Para provar a existência de um equilíbrio de Nash, deixe $(\sigma _{-i}) ?$ ser a melhor resposta do jogador i para as estratégias de todos os outros jogadores.

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

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

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

1. $Não. "Sigma"$ é compacto, convexo, e nenhummpty.
2. ${\displaystyle r(\sigma)}$ Não é nada.
3. ${\displaystyle r(\sigma)}$ é superior hemicontinuous
4. ${\displaystyle r(\sigma)}$ É convexo.

Condição 1. está satisfeito com o fato de que $Não. "Sigma"$ é um simples e, portanto, compacto. Convexidade segue da capacidade dos jogadores de misturar estratégias. $Não. "Sigma"$ não é nenhummpty enquanto os jogadores têm estratégias.

A condição 2. e 3. estão satisfeitos por meio do teorema máximo de Berge. Porque... $Não. u_{i}}$ é contínuo e compacto, ${\displaystyle r(\sigma _{i})}$ é não vazio e hemicontinuous superior.

Condição 4. está satisfeito como resultado de estratégias mistas. Suponha ${\displaystyle \sigma _{i},\sigma '_{i}\in r(\sigma _{-i})) ?$, então ${\displaystyle \lambda \sigma _{i}+(1-\lambda)\sigma '_{i}\in r(\sigma _{-i})) ?$. ou seja, se duas estratégias maximizar os pagamentos, então uma mistura entre as duas estratégias irá render o mesmo pagamento.

Portanto, existe um ponto fixo em $Não.$ e um equilíbrio de Nash.

Quando Nash fez esse ponto para John von Neumann em 1949, Von Neumann o descartou com as palavras, isso é trivial, você sabe. Isso é apenas um teorema de ponto fixo. " (Ver Nasar, 1998, p. 94.)

Temos um jogo. $(N,A,u)}$ Onde? $Não.$ é o número de jogadores e $Não. A=A_{1}\times \cdots \times A_{N}}$ é o jogo de ação para os jogadores. Todos os conjuntos de ação $Não. A_{i}}$ são finitas. Vamos. ${\displaystyle \Delta =\Delta _{1}\times \cdots \times \Delta _{N}}$ denota o conjunto de estratégias mistas para os jogadores. A finitude do $Não. A_{i}}$s garante a compactação de $- Sim.$.

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

${\displaystyle {\text{Gain}}_{i}(\sigmaa)=\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 recebe alterando unilateralmente sua estratégia. Definimos agora $(g_{1},\dotscg_{N})}$ Onde?

$(a)=\sigma _{i}(a)+{\text{Gain}}_{i}(\sigmaa)}$

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

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

Em seguida, definimos:

$(f_{1},\cdotsf_{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 um $Não. f_{i}}$ é uma estratégia mista válida em ${\displaystyle \Delta _{i}}$. Também é fácil verificar se cada um $Não. f_{i}}$ é uma função contínua de $- Sim.$e daí $Não.$ é uma função contínua. Como produto transversal de um número finito de conjuntos de convexos compactos, $- Sim.$ também é compacto e convexo. Aplicando o teorema de ponto fixo Brouwer para $Não.$ e $- Sim.$ nós concluímos que $Não.$ tem um ponto fixo em $- Sim.$Chama-o. ${\displaystyle \sigma ^{*}}$. Nós reivindicamos que ${\displaystyle \sigma ^{*}}$ é um equilíbrio de Nash em $Não. G.$. Com esta finalidade, basta mostrar que

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

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

Agora assuma que os ganhos não são todos zero. Portanto, ${\displaystyle \exists i\in \{1,\cdotsN\},}$ e ${\displaystyle a\in A_{i}}$ tal que ${\displaystyle {\text{Gain}}_{i}(\sigma ^{*},a)>0}$. Então...

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

Então vamos

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

Também denotaremos $(i,\cdot)}$ como o vetor de ganho indexado por ações em $Não. A_{i}}$. Desde então. ${\displaystyle \sigma ^{*}}$ é o ponto fixo que temos:

${\displaystyle {\begin{aligned}\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}^{* {1}{C}}\left(\sigma _{i}^{*}+{\text{Gain}}_{i}(\sigma ^{*},\cdot)\right)\\[6pt]&\Rightarrow C\sigma _{i}^{*}=\sigma _{i}^{*}+{\text{Gain}}_{i}(\sigma ^{*},\cdot)\&\Rightarrow \left(C-1\right)\sigma _{i}^{*}={\text{Gain}}_{i}(\sigma ^{*},\cdot)\&\ Direita: _{i}^{*}=\left({\frac {1}{C-1}}\right){\text{Gain}}_{i}(\sigma ^{*},\cdot).\end{aligned}}}$

Desde então. $- Sim.$ nós temos ${\displaystyle \sigma _{i}^{*}}$ é algum escalonamento positivo do vetor ${\displaystyle {\text{Gain}}_{i}(\sigma ^{*},\cdot)}$. Agora dizemos que

${\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{Gain}}_{i}(\sigma ^{*},a)}$

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

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

e assim o termo esquerdo é zero, dando-nos que toda a expressão é $Não. 0$ como necessário.

Então, finalmente temos isso

${\displaystyle {\begin{aligned}0&=u_{i}(\sigma _{i}^{*}, \sigma _{-i}^{*})-u_{i}(\sigma _{i}^{*}, - Sim. _{-i}^{*})\\&=\left(\sum _{a\in A_{i}}\sigma _{i}^{*}(a)u_{i}(a_{i},\sigma _{-i}^{*})\right)-u_{i}(\sigma _{i}^{*}, - Sim. _{-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{Gain}}_{i}(\sigma ^{*},a)&&&{\text{ pelas declarações anteriores }}\\&=\sum _{a\in A_{i}}\left(C-1\right)\sigma _{i}^{*}(a)^{2}>0\end{aligned}}}$

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

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

Em jogos com os equilíbrios de Nash de estratégia mista, a probabilidade de um jogador escolher qualquer estratégia (tão pura) pode ser calculada atribuindo uma variável a cada estratégia que represente 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 a mesma. 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 da qual as probabilidades de escolher cada estratégia podem ser derivadas.

Combinando centavos

Estratégia	Jogador B joga H	Jogador B joga T
Jogador A joga H	-1, +1	+1, -1
Jogador A joga T	+1, -1	-1, +1

No jogo de moedas correspondentes, o jogador A perde um ponto para B se A e B jogar a mesma estratégia e ganha um ponto de B se eles jogam diferentes estratégias. Para calcular o equilíbrio de Nash de estratégia mista, atribuir A a probabilidade $Não.$ de jogar H e $(em inglês)}$ de jogar T, e atribuir B a probabilidade $Não.$ de jogar H e $(I-q)}$ de jogar T.

$${\displaystyle {\begin{aligned}&\mathbb [E] A playing H}}]=(-1)q+(+1)(1-q)=1-2q\&\mathbb {E} [text{payoff para A playing T}}]=(+1)q+(-1)(1-q)=2q-1\&\mathbb {E} [text{payoff para Um jogo H}}=\mathbb [E] Um jogo T}} implies 1-2q=2q-1\implies q={\frac {1}{2}}\\&\mathbb Não. [Observação] B playing H}}]=(+1)p+(-1)(1-p)=2p-1\\&\mathbb {E} [text{payoff para B playing T}}]=(-1)p+(+1)(1-p)=1-2p\\&\mathbb {E} [text{payoff] B jogando H}} =\mathbb {E} [{\text{payoff para B jogando T}} implies 2p-1=1-2p\implies p={\frac {1}{2}}\\\end{aligned}}}$$

Assim, um equilíbrio de Nash de estratégia mista neste jogo é para cada jogador escolher aleatoriamente H ou T com $- Sim. Não.$ e $- Sim. Não.$.

Jogo de Dinheiro Livre

Estratégia	Jogador B votos Sim.	Jogador B votos Não
Jogador Um voto Sim	1, 1	0, 0
Jogador Um voto Não	0, 0	0, 0

Em 1971, Robert Wilson criou o teorema da estranheza, que diz que "quase todos" 34; Jogos finitos têm um número finito e ímpar de equilíbrio de Nash. Em 1993, Harsanyi publicou uma prova alternativa do resultado. " quase todos " Aqui significa que qualquer jogo com um número infinito ou uniforme de equilíbrios é muito especial no sentido de que, se seus recompensas fossem um pouco perturbados aleatoriamente, com probabilidade de um, 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 misturado, e isso permanece verdadeiro mesmo que os pagamentos mudem um pouco. O jogo de dinheiro gratuito é um exemplo de A " especial " Jogo com um número uniforme de equilíbrio. Nele, dois jogadores precisam votar "sim"; em vez de " no " Para obter 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 " no ". " sim " é tão bom quanto " no " Independentemente da ação do outro jogador, mas se houver alguma chance, o outro jogador escolhe "sim"; Então, sim, sim " é a melhor resposta. Sob uma pequena perturbação aleatória dos pagamentos, no entanto, a probabilidade de que dois pagamentos permanecessem amarrados, seja em 0 ou algum outro número, é muito pequeno, e o jogo teria um ou três equilíbrios.

Vamos. ${\displaystyle {\mathcal {A}}=\{A_{1},\ldotsA_{m}\}}}}$ e ${\displaystyle {\mathcal {B}}=\{B_{1},\ldotsB_{n}\}}}}$ ser um par de multi-hipergramas duplos no conjunto de terra comum $Não. \Omega =\{\omega _{1},\ldots\omega _{k}\}}$. Note que ${\displaystyle {\mathcal {A}}}$ ou ${\displaystyle {\mathcal {B}}}$ pode ter bordas embutidas ou iguais.

Uma borda é mínima se não for um superconjunto rigoroso de outra borda. No entanto, as bordas mínimas iguais podem existir.

Um par ${\displaystyle ({\mathcal {A}},{\mathcal {B}})}$ é chamado $(intersecto)}$ se $(i)}}}$ $Não. A\cap B\neq \emptyset }$ para cada par $Não. A\in {\mathcal {A}}}$ e $Não. B\in {\mathcal {B}}}$.

Um conjunto $Não. T\subseteq \Omega }$ é chamado $(transversal)$ para ${\displaystyle {\mathcal {A}}}$ se $Não. T\cap A\neq \emptyset }$ para todos $Não. A\in {\mathcal {A}}}$.

Por definição, cada $Não. B\in {\mathcal {B}}}$ é transversal a ${\displaystyle {\mathcal {A}}}$.

Nós dizemos que ${\displaystyle {\mathcal {B}}}$ é duplo para ${\displaystyle {\mathcal {A}}}$ se $(i)}}}$ e cada transversal a ${\displaystyle {\mathcal {A}}}$ contém uma borda $Não. B\in {\mathcal {B}}}$.

Da mesma forma, definimos transversais para ${\displaystyle {\mathcal {B}}}$ e quando ${\displaystyle {\mathcal {A}}}$ é duplo para ${\displaystyle {\mathcal {B}}}$.

É óbvio e bem conhecido que ${\displaystyle {\mathcal {B}}}$ é duplo para ${\displaystyle {\mathcal {A}}}$se e somente se ${\displaystyle {\mathcal {A}}}$ é duplo para ${\displaystyle {\mathcal {B}}}$. Neste caso multi-hipergrafias ${\displaystyle {\mathcal {A}}}$ e ${\displaystyle {\mathcal {B}}}$ são chamados ${\displaystyle {\textbf {dual}}}$.

Dualidade de ${\displaystyle {\mathcal {A}}}$ e ${\displaystyle {\mathcal {B}}}$ implica $(i)}}}$ por definição. Obviamente, também implica

$(ii)}$ Para cada mínimo $Não. A\in {\mathcal {A}}}$ e cada ${\displaystyle \omega \in A}$ existe uma borda (minimal) $Não. B\in {\mathcal {B}}}$ tal que $Não. A\cap B=\{\omega Sim.$.

De facto, caso contrário $Não. A.$ não seria mínimo em ${\displaystyle {\mathcal {A}}}$.

Reivindicação $(ii)}$ pode ser estendido da seguinte forma. Uma ordem linear $- Sim.$ sobre $Não. - Sim.$ define uma ordem lexicográfico única $_{L}}$ sobre o Boolean ${\displaystyle 2^{\Omega }}$. Vamos. $Não. A.$ ser a borda lexicograficamente máxima de ${\displaystyle {\mathcal {A}}}$. Então,

$(iii)}$ $Não. A.$ é mínimo em ${\displaystyle {\mathcal {A}}}$ e para cada ${\displaystyle \omega \in A}$ existe um (minimal) $Não. B\in {\mathcal {B}}}$ tal que $Não. A\cap B=\{\omega Sim.$ e ${\displaystyle \omega \succeq \omega \ '$ para cada ${\displaystyle \omega\in B}$.

Esta propriedade possui aplicações imediatas na teoria dos jogos, implicando a solvabilidade de Nash de formas e correspondências de jogo apertadas. Primeiro, foi demonstrado por V. Gurvich in.

No caso de soma zero, este resultado foi obtido anteriormente por J. Edmonds e D.R. Fulkerson.

Deixe as estratégias de Alice e Bob ser as bordas de multi-hipergramas ${\displaystyle {\mathcal {A}}}$ e ${\displaystyle {\mathcal {B}}}$, respectivamente. Cada par de bordas $(A,B)}$com $Não. A\in {\mathcal {A}},B\in {\mathcal {B}}}$, define o conjunto de resultados $Não. A\cap B}$. Assim, par ${\displaystyle ({\mathcal {A}},{\mathcal {B}})}$ define uma correspondência de jogo ${\displaystyle C({\mathcal {A}},{\mathcal {B}})}$. Além disso, escolher um (arbitrário) resultado de cada interseção resulta em uma forma de jogo ${\displaystyle g=g({\mathcal {A}},{\mathcal {B}})}$.

Uma forma de jogo $Não.$ é chamado $- Sim.$ se suas multi-hipergrafias ${\displaystyle {\mathcal {A}}}$ e ${\displaystyle {\mathcal {B}}}$ são duplos.

Uma forma de jogo $Não.$ é chamado ${\displaystyle {\textbf {Nash-solvable}}}$ se por quaisquer pagamentos $Não.$ e $Não.$ de Alice e Bob o jogo obtido $(g,u,w)}$ tem pelo menos um NE (em estratégias puras).

$(Theorem)$ Uma forma de jogo é Nash-solvable se e somente se for apertado.

Observe que esse resultado é mantido apenas para o caso de duas pessoas. Para 3 jogadores, o aperto se torna não necessário nem suficiente para a solvabilidade de Nash; Veja exemplos em.

Além disso, a estratégia NE de Alice é sua estratégia lexmax. Curiosamente, não depende da preferência de Bob. A Alice pode não estar ciente disso. Dada essa estratégia, Bob maximiza seu pagamento. Por favor. $(iii)}$, ele tem uma estratégia percebendo um Equilíbrio de Nash.

É claro, trocando Alice e Bob também obtemos um equilíbrio de Nash. Esses dois tipos de NE podem coincidir. Acontece, por exemplo, no caso de soma zero ou se existe um NE exclusivo.

No entanto, se tanto Alice quanto Bob aplicarem suas estratégias lexmax, o par obtido $(A,B)}$ pode não ser um NE; veja um exemplo em.

Bordas $Não. A.$ e $Não.$ satisfazendo $(iii)}$ e o NE correspondente pode ser encontrado em tempo polinomial. Isto é trivial se ambos os multi-hipergramas duplos ${\displaystyle {\mathcal {A}}}$ e ${\displaystyle {\mathcal {B}}}$ são dados explicitamente. No entanto, é verdade se apenas um deles é dado, e não explicitamente, mas por um oráculo polinomial $Não. O.$ cujo tamanho $|O|}$ pode ser logarítmica no tamanho de ${\displaystyle {\mathcal {A}}}$ e ${\displaystyle {\mathcal {B}}}$. V. Gurvich e M. Naumova forneceram quatro exemplos de tais oráculos polinomiais.

• "Nash theorem (em teoria do jogo)", Enciclopédia da Matemática, EMS Press, 2001 [1994]
• Prova completa da existência de Nash Equilibria
• Formulário simplificado e resultados relacionados Arquivado 2021-07-31 no Wayback Machine