Métodos numéricos para equilíbrio de Nash com critério de descenso

Resumo

Este trabalho tem como objetivo desenvolver um algoritmo baseado em Lagrangeano aumentado para encontrar um ponto de equilíbrio para o problema de equilíbrio de Nash de dois jogadores. Os métodos da literatura para este tipo de problema usam da teoria de condições de otimalidade para encontrar pontos estacionários via condições de Karush-Kuhn-Tucker (KKT) fazendo uso de alguma condição de qualificação. Embora estas condições sejam necessárias para que um ponto limite da sequência gerado pelos algoritmos seja um ponto de equilíbrio, ela não é suficiente, conforme ilustra Haeser et. al. em trabalhos anteriores. Por conta disso, métodos baseados em KKT para problemas de equilíbrio de Nash encontram pontos de sela ou máximos locais com frequência, ao invés de determinar soluções do problema. O método aqui proposto fará o uso da estrutura de minimização dos subproblemas de otimização gerados pela abordagem de Lagrangeano aumentado para encontrar um critério de parada do algoritmo que seja baseado em descenso, e não levando em conta as condições de KKT. Visamos também estudar a possibilidade de uso de condições de otimalidade sequenciais, similares a estudos realizados por Haeser et. al., em trabalhos recentes para outros tipos de problemas. Neste projeto visa-se estabelecer as propriedades de convergência deste algoritmo, bem como demonstrar a boa performance prática em relação aos demais métodos para este tipo de problema do estado da arte. (AU)