Técnicas de Ponto Interior e Direções Viáveis para Problemas de Equilíbrio de Nash Generalizado com Restrições Compartilhadas

Abstract

Neste trabalho apresentamos dois métodos viáveis de ponto e direcção interiores para o cálculo computacional do equilíbrio normalizado do problema do equilíbrio generalizado de Nash, GNEP. O GNEP generaliza o problema clássico do equilíbrio de Nash, NEP, no sentido em que os conjuntos de estratégias de cada jogador dependem das estratégias dos jogadores rivais. Tal como no NEP, o GNEP envolve dois ou mais jogadores competindo sob o pressuposto de que não há colaboração entre eles e cada jogador, tem um problema de otimização associado. Através de uma reformulação que concatena as condições de otimização do problema de otimização de cada jogador, podemos obter a solução normalizada do GNEP. Os algoritmos apresentados neste trabalho são do tipo Newton e resolvem a concatenação das condições de otimização, utilizando também funções potenciais que decrescem em cada iteração. Assim, os algoritmos geram uma sequência de pontos viáveis que convergem para a solução normalizada do GNEP. A convergência global de ambos algoritmos é provada sob certas hipóteses e a sua aplicabilidade e eficiência são verificadas através de testes numéricos.

Se presenta el desarrollo e implementación de dos métodos de puntos interiores y direcciones viables para el cálculo computacional del equilibrio normalizado del problema de equilibrio generalizado de Nash, GNEP. El GNEP generaliza el problema de equilibrio clásico de Nash, NEP, en el sentido de que los conjuntos de estrategias de cada jugador dependen de las estrategias de los jugadores rivales. Al igual que NEP, GNEP involucra a dos o más jugadores que compiten bajo el supuesto de que no hay colaboración entre ellos y cada jugador, tiene un problema de optimización asociado. A través de una reformulación que concatena las condiciones de optimización del problema de optimización de cada jugador, podemos obtener la solución GNEP normalizada. Los algoritmos presentados en este trabajo son del tipo Newton y resuelven la concatenación de las condiciones de optimización, utilizando también funciones potenciales que decrecen en cada iteración. Así, los algoritmos generan una secuencia de puntos factibles que convergen a la solución GNEP normalizada. La convergencia global de ambos algoritmos se prueba bajo ciertas hipótesis y se verifica su aplicabilidad y eficiencia mediante pruebas numéricas.