On Discrete-Time Approximations to Infinite Horizon Differential Games

Resumo Técnico: Aproximações Discretas para Jogos Diferenciais de Horizonte Infinito

Enunciado do Problema
O artigo aborda a aproximação numérica de Equilíbrios de Nash Markovianos (ENM) em jogos diferenciais não cooperativos de horizonte infinito com $N$ jogadores. Em tais jogos, $N$ jogadores interagem estrategicamente ao longo do tempo, onde cada jogador $i$ busca maximizar um funcional objetivo $W_i$ sujeito a uma equação de dinâmica de estado $\dot{x} = g(x, u_i, u_{-i})$. Os autores focam em estratégias de feedback de estado (Markovianas), que são preferidas devido à sua perfeição em subjogos (consistência temporal) em comparação com equilíbrios em malha aberta.

O desafio central é que os ENMs são caracterizados por um sistema de $N$ equações de Hamilton-Jacobi-Bellman (HJB) acopladas. Devido à alta não linearidade e dimensionalidade dessas equações, soluções analíticas geralmente não estão disponíveis, exceto para modelos específicos lineares-quadráticos ou lineares em estado. Consequentemente, métodos numéricos são necessários. O artigo investiga se aproximações de tempo discreto e totalmente discretas (tempo e estado) desses jogos convergem para a solução de tempo contínuo e se os equilíbrios discretos resultantes servem como aproximações válidas (especificamente equilíbrios $\epsilon$-Nash) para o jogo contínuo original.

Metodologia
Os autores empregam uma abordagem de discretização semi-Lagrangiana, combinando a discretização temporal da dinâmica com uma discretização correspondente do funcional objetivo.

1. Aproximação de Tempo Discreto (Semi-discreta):

   • O horizonte de tempo contínuo é discretizado com tamanho de passo $h$.
   • A dinâmica de estado é aproximada usando um esquema de Euler explícito: $x_{n+1} = x_n + h g(x_n, u_{i,n}, u_{-i,n})$.
   • O funcional objetivo é aproximado usando a regra do retângulo com um fator de desconto discreto $\beta_h = 1 - \rho h$.
   • Os autores analisam a convergência da função valor discreta para a função valor contínua e estabelecem que um Equilíbrio de Nash Markoviano do jogo discreto constitui um equilíbrio $\epsilon$-Nash para o jogo contínuo.

2. Aproximação Totalmente Discreta (Tempo e Estado):

   • O espaço de estados é discretizado usando uma triangulação de um poliedro limitado $\Omega$ com tamanho de malha $k$.
   • Funções afins por partes são usadas para aproximar as funções valor e estratégias nos nós da malha.
   • Um jogo auxiliar é definido usando operadores de interpolação ($I_k$) no espaço de estados para lidar com a dinâmica de estado discreta.
   • A análise baseia-se na definição de um problema de tempo contínuo auxiliar com estratégias interpoladas para limitar o erro entre a solução totalmente discreta e a solução contínua.

Principais Contribuições e Resultados
O artigo fornece provas rigorosas de convergência e estimativas de erro para os esquemas de discretização propostos:

• Consistência das Funções Valor: Os autores provam que, à medida que o passo de tempo $h \to 0$ (e subsequentemente $k \to 0$ para o caso totalmente discreto), as funções valor dos jogos discretos convergem para a função valor do jogo diferencial contínuo.
• Propriedade de Equilíbrio $\epsilon$-Nash:
  • Teoremas 3 e 6: É provado que, para qualquer $\epsilon > 0$, existe um parâmetro de discretização suficientemente pequeno ($h$ ou $h, k$) tal que o Equilíbrio de Nash Markoviano do jogo discreto é um equilíbrio $\epsilon$-Nash para o jogo contínuo. Isso significa que nenhum jogador pode ganhar mais do que $\epsilon$ desviando-se unilateralmente da estratégia discreta no cenário contínuo.
  • Teoremas 4 e 7: Sob hipóteses mais fortes (especificamente regarding a taxa de desconto $\rho$ em relação às constantes de Lipschitz da dinâmica e das funções de custo), os autores derivam limites de erro explícitos. Eles mostram que o erro de aproximação é da ordem $O(h)$ para o caso de tempo discreto e $O(h+k)$ para o caso totalmente discreto.
• Experimentos Numéricos: Os resultados teóricos são validados usando dois exemplos:
  1. Um jogo de poluição transfronteiriça (estrutura linear-quadrática), onde os resultados numéricos confirmam a convergência de primeira ordem tanto para as funções valor quanto para as estratégias.
  2. Um jogo diferencial do tipo Lanchester (não linear, não quadrático), que também demonstra convergência da função valor e das estratégias à medida que os parâmetros de discretização diminuem.

Significado e Alegações
O artigo afirma estabelecer uma base teórica para o uso de métodos semi-Lagrangianos na resolução de jogos diferenciais não cooperativos complexos. O significado principal reside em provar que os equilíbrios discretos computacionalmente tratáveis não são meros artefatos numéricos, mas são matematicamente garantidos como aproximações dos verdadeiros equilíbrios de tempo contínuo com precisão arbitrária.

Os autores observam que, embora as hipóteses necessárias para os limites de erro explícitos (como a condição $\rho > L$) sejam restritivas, elas são frequentemente satisfeitas em aplicações práticas, particularmente quando a dinâmica permanece dentro de um domínio limitado e positivamente invariante. O trabalho estende resultados anteriores sobre controle ótimo de jogador único para o cenário de jogos com múltiplos jogadores, demonstrando que a abordagem semi-Lagrangiana permanece robusta quando interações estratégicas estão presentes. O artigo conclui que esses métodos fornecem um caminho viável para calcular equilíbrios de Nash Markovianos em modelos onde soluções analíticas são impossíveis.