Interleaved Information Structures in Dynamic Games: A General Framework with Application to the Linear-Quadratic Case

Resumo Técnico: Estruturas de Informação Intercaladas em Jogos Dinâmicos

1. O Problema

A teoria de jogos dinâmicos não cooperativos enfrenta um desafio fundamental: o cálculo de Equilíbrios de Nash sob diferentes estruturas de informação. A literatura tradicional foca predominantemente em dois extremos canônicos:

• Estrutura de Malha Aberta (Open-loop): Os agentes observam apenas o estado inicial do jogo e não têm acesso a estados subsequentes durante a tomada de decisão.
• Estrutura de Feedback (Realimentação): Os agentes observam o estado completo do jogo (de todos os agentes) em cada passo de tempo.

No entanto, cenários reais de multiagentes frequentemente exibem estruturas de informação intercaladas (interleaved), onde cada agente observa apenas um subconjunto específico dos outros agentes em cada instante de tempo. Essas estruturas não são nem totalmente abertas nem totalmente fechadas. Até o momento, não existia uma estrutura sistemática para modelar e resolver jogos dinâmicos sob essas condições arbitrárias, especialmente para a classe fundamental de jogos Lineares-Quadráticos (LQ), onde a derivação de equações do tipo Riccati para equilíbrios de Nash permanece um problema aberto.

2. Metodologia

Os autores propõem uma abordagem baseada em Redes de Programas Matemáticos (Mathematical Program Networks - MPNs) para modelar a interdependência entre os problemas de otimização dos agentes.

• Modelagem como MPN:

  • Um jogo dinâmico é transformado em uma rede direcionada onde cada nó representa um programa matemático (problema de otimização) de um agente em um determinado passo de tempo.
  • Nós: Cada agente $i$ em cada passo de tempo $t$ possui um nó $N^i_t$ que representa a minimização do custo futuro (cost-to-go).
  • Arestas (Interdependências): As arestas da rede codificam as dependências informacionais:
    • Arestas Temporais: Conectam $N^i_t \to N^i_{t+1}$, representando a dependência das decisões futuras do próprio agente.
    • Arestas de Observação: Se o agente $i$ observa o agente $j$ no tempo $t$, cria-se uma aresta $N^j_t \to N^i_{t+1}$. Isso captura o fato de que a decisão futura de $i$ depende da decisão atual de $j$.
  • Variáveis de Decisão: As variáveis em cada nó são expandidas para incluir não apenas as próprias ações futuras, mas também as ações futuras dos agentes observados (ou inferidas), dependendo da estrutura de informação.

• Derivação de Equilíbrio para Jogos LQ:

  • Para jogos Lineares-Quadráticos, a estrutura afim das restrições e a convexidade das funções de custo garantem que as condições de otimalidade de primeira ordem (Condições de Karush-Kuhn-Tucker - KKT) sejam necessárias e suficientes.
  • O procedimento proposto envolve:
    1. Formular o jogo como uma MPN.
    2. Construir o gráfico de solução para cada nó (definindo o conjunto de soluções ótimas condicionadas às soluções dos nós filhos).
    3. Escrever as condições KKT para cada nó.
    4. Concatenar essas condições KKT de todos os nós para formar um sistema acoplado de equações do tipo Riccati.

3. Contribuições Principais

O artigo apresenta duas contribuições fundamentais:

1. Formulação Geral via MPNs: Introdução de um método sistemático para modelar jogos dinâmicos determinísticos com estruturas de informação intercaladas arbitrárias como Redes de Programas Matemáticos. A estrutura da rede captura explicitamente as dependências informacionais induzidas pelo fato de que os agentes observam subconjuntos diferentes de variáveis de estado.
2. Procedimento para Jogos Lineares-Quadráticos (LQ): Desenvolvimento de um procedimento sistemático para derivar equações do tipo Riccati que caracterizam os Equilíbrios de Nash em jogos LQ com $N$ agentes sob qualquer estrutura de informação intercalada. Isso preenche a lacuna teórica de como calcular equilíbrios quando a informação não é nem totalmente aberta nem totalmente fechada.

4. Resultados e Exemplo Ilustrativo

Os autores validam sua abordagem através de um exemplo numérico envolvendo três agentes com uma estrutura de informação cíclica:

• O Agente 1 observa o Agente 2.
• O Agente 2 observa o Agente 3.
• O Agente 3 observa o Agente 1.
• Nenhum agente observa a si mesmo diretamente (além do estado próprio) ou observa todos os outros simultaneamente.

Resultados do Exemplo:

• Foi construída a MPN correspondente, mostrando como as arestas de observação cruzada conectam os nós temporais dos diferentes agentes.
• As condições KKT foram derivadas para cada nó, introduzindo multiplicadores de Lagrange específicos para as dependências de informação (diferentes das dependências puramente dinâmicas).
• Demonstrou-se que, ao analisar as condições de estacionariedade retroativamente no tempo, é possível eliminar multiplicadores desnecessários e derivar um sistema de equações recursivas (tipo Riccati) que permite calcular os controles e estados de equilíbrio.
• O exemplo confirma que a estrutura cíclica de informação gera um sistema de equações acoplado que difere tanto do caso de malha aberta quanto do caso de feedback total.

5. Significado e Impacto

Este trabalho é significativo por várias razões:

• Generalidade: Move a teoria de jogos dinâmicos além dos extremos canônicos (malha aberta vs. feedback total), permitindo a análise de cenários mais realistas e complexos onde a informação é parcial e assimétrica.
• Ferramenta Computacional: A formulação via MPNs oferece uma estrutura unificada para modelar interdependências complexas, facilitando a implementação algorítmica.
• Fundação Teórica: A derivação de equações do tipo Riccati para estruturas intercaladas abre caminho para o controle ótimo e a análise de estabilidade em sistemas multiagentes distribuídos (como redes de sensores, veículos autônomos cooperativos e redes de energia), onde a comunicação é limitada ou seletiva.
• Futuro: O framework estabelece a base para investigar jogos não lineares e cenários onde a estrutura de informação evolui dinamicamente com as decisões dos agentes.

Em suma, o artigo fornece a primeira estrutura sistemática para modelar e resolver jogos dinâmicos com informações parciais e intercaladas, transformando um problema de otimização acoplado complexo em um sistema de equações tratável através da teoria de Redes de Programas Matemáticos.