Skip to content
Voltar aos resultados

Equilíbrio de Nash

Proposto por
John Nash
Ano
1950
Tipo
algorithm
Família
Game-theoretic

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Equilíbrio de Nash é um conceito de solução em teoria dos jogos onde nenhum jogador pode desviar unilateralmente para melhorar seu payoff.

Formalizado por John Nash em 1950, o algoritmo de Lemke-Howson encontra computacionalmente equilíbrios em jogos bimatriciais identificando pares de vértices completamente rotulados nos politopos de estratégia.

A intuição por trás do método

Em um Equilíbrio de Nash, a estratégia de cada jogador é uma melhor resposta a cada estratégia dos outros jogadores. Imagine uma situação em que ambos os jogadores conhecem a estratégia do outro: nenhum deles desejaria mudar, pois fazê-lo apenas os prejudicaria. O algoritmo de Lemke-Howson explora a geometria dos poliedros de jogos, rastreando rótulos (restrições insatisfeitas) e pivotando através de vértices até que um par completamente rotulado seja encontrado — uma configuração onde ambos os jogadores não têm desvios lucrativos.

História

John Nash provou em sua tese de doutorado de 1950 que todo jogo finito possui pelo menos um Equilíbrio de Nash de estratégia mista. Em 1964, Lemke e Howson publicaram o primeiro algoritmo construtivo para encontrar esses equilíbrios, transformando a prova de existência de Nash em um método computacional prático. Seu trabalho tornou-se fundamental para a teoria dos jogos computacional e a economia algorítmica.

Quando usar

Usar a análise de Equilíbrio de Nash ao estudar jogos com dois jogadores e espaços de estratégia discretos, ou ao buscar equilíbrios totalmente mistos. Adequado para modelar problemas de competição, negociação e coordenação onde a interação estratégica é primordial. O método de Lemke-Howson funciona melhor para jogos bimatriciais não degenerados; casos degenerados podem exigir computação simbólica ou perturbação.

Limitações e considerações

  • Limitado a jogos bimatriciais (de dois jogadores); a extensão para jogos de n-jogadores é NP-difícil
  • Falha ou torna-se ineficiente em jogos degenerados onde múltiplos pivôs de entrada são possíveis
  • Pode encontrar apenas um equilíbrio; múltiplos equilíbrios frequentemente existem em jogos de soma não nula
  • Não lida diretamente com jogos dinâmicos ou de forma extensiva sem reformulação

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Computacionalmente eficiente para encontrar equilíbrios de Nash em jogos bimatriciais finitos
  • Garante a convergência para um par de vértices completamente rotulado para jogos não degenerados
  • Fornece fundação teórica conectando geometria combinatória à teoria dos jogos
  • Aplicável a equilíbrios de estratégia mista, que são frequentemente mais realistas do que resultados de estratégia pura

Aplicações

  • Economia: modelagem de competição oligopolista e comportamento de precificação em mercados
  • Leilões e design de mecanismos: análise de estratégias de lances em leilões de primeiro preço e fechados
  • Cibersegurança: previsão de equilíbrios atacante-defensor em jogos de segurança de rede
  • Biologia da vida selvagem: análise de estratégias evolutivamente estáveis em interações predador-presa

Como funciona

Como funciona

1

Converter o jogo bimatricial em dois problemas de complementaridade linear (LCP), um para cada jogador, representando suas condições de melhor resposta.

2

Atribuir rótulos às arestas e vértices dos politopos de estratégia com base em quais restrições de incentivo do jogador são violadas.

3

Partindo do vértice de todos os uns (completamente rotulado), realizar pivôs semelhantes ao simplex para navegar no politopo, removendo e adicionando rótulos até que um par completamente rotulado seja descoberto.

4

Confirmar que as estratégias de ambos os jogadores formam melhores respostas mútuas verificando que nenhum deles pode melhorar seu payoff dada a estratégia do outro.

Erros comuns

  • Assumindo que um equilíbrio único existe; muitos jogos têm múltiplos equilíbrios de Nash com diferentes implicações de payoff
  • Confundir equilíbrios de estratégia mista (jogabilidade probabilística) com equilíbrios de estratégia pura, levando a interpretações errôneas do comportamento do agente
  • Ignorar a distinção entre condições necessárias e suficientes para o equilíbrio; um par completamente rotulado satisfaz a otimalidade, mas pode não ser realizado se os jogadores não conseguirem coordenar

Perguntas frequentes

Um jogo pode ter nenhum Equilíbrio de Nash?

Equilíbrios de Nash de estratégia pura podem não existir (por exemplo, Pedra-Papel-Tesoura), mas todo jogo finito tem pelo menos um equilíbrio de estratégia mista onde os jogadores randomizam sobre ações com probabilidades específicas.

Como um equilíbrio de estratégia mista difere de um equilíbrio de estratégia pura?

Em um equilíbrio de estratégia pura, cada jogador se compromete com uma ação específica com certeza. Em um equilíbrio de estratégia mista, cada jogador usa uma distribuição de probabilidade sobre as ações. Equilíbrios mistos são frequentemente mais gerais e existem quando os puros não existem.

Por que o algoritmo de Lemke-Howson é preferido à busca por força bruta?

O algoritmo explora a estrutura politópica dos espaços de estratégia, reduzindo o espaço de busca exponencialmente e alcançando a convergência em tempo polinomial para jogos não degenerados, enquanto a enumeração por força bruta se torna inviável à medida que o espaço de estratégia cresce.

Métodos relacionados

Fontes

  1. Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.

    Abrir referência DOI
    Copiado.
  2. Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.

    Abrir referência DOI
    Copiado.