Resumo Técnico: Seleção Dependente de Solver em Polítopos de Nash de Soma Zero

Declaração do Problema

Em teoria dos jogos computacional, jogos de soma zero entre dois jogadores (2p0s) são frequentemente tratados como possuindo um equilíbrio de Nash (EN) único. Embora o teorema minimax garanta um valor de jogo único $V^\star$, muitos jogos — particularmente aqueles com degenerações ou simetrias estruturais — possuem um conjunto convexo de equilíbrios (um politopo de Nash). Dentro deste conjunto, todos os perfis produzem $V^\star$ contra um oponente que responde de forma ótima, mas podem prescrever comportamentos materialmente diferentes fora do caminho de equilíbrio, utilizar suportes diferentes e exibir variadas robustez contra oponentes subótimos.

Solvers padrão têm a garantia de convergir para algum equilíbrio, mas são frequentemente tratados como intercambiáveis. Este artigo investiga se diferentes famílias de solvers selecionam sistematicamente membros diferentes do conjunto de Nash como uma função de sua estrutura algorítmica, em vez de sementes aleatórias ou orçamentos de iteração. Além disso, busca caracterizar os critérios de seleção específicos (ex: entropia máxima) empregados por esses algoritmos.

Metodologia

Os autores empregam um ambiente de teste tabular mínimo e totalmente transparente para eliminar a variância de amostragem ou aproximação de função. O estudo utiliza valores contrafatuais exatos para garantir que a verdade fundamental seja analiticamente conhecida.

Ambiente de Teste:

• Seis Jogos Construídos à Mão: Incluindo controles simétricos (ex: "pennies safe"), jogos assimétricos (ex: "asym safe"), um jogo com um politopo de Nash genuinamente bidimensional ("polytope4") e Kuhn poker.
• Ensemble Aleatorizado: Uma população de 180 jogos de matriz aleatórios assimétricos com faces de Nash analiticamente conhecidas para testar a generalização.

Famílias de Solvers Comparadas:

1. Métodos de Média de Arrependimento (Regret-Averaging): Empregam uma média temporal de estratégias.
   • Counterfactual Regret Minimization (CFR)
   • CFR+ (média ponderada linearmente)
   • Fictitious Play (FP)
   • Hedge (usado como um ablação para testar mecanismos de projeção)
2. Métodos de Última Iteração Regularizados: Empregam a última iteração de uma dinâmica ancorada a uma política de referência.
   • Regularized Nash Dynamics (R-NaD): Usa uma referência móvel (periodicamente resetada para a política atual).
   • Magnetic Mirror Descent (MMD): Usa uma referência fixa.
   • Multiplicative Weights Update (MWU/NeuRD): Última iteração não regularizada.

Métricas:

• Coordenada de seleção (posição dentro do politopo de Nash).
• Entropia média da política (entropia de Shannon).
• Exploitabilidade (NashConv) para verificar a convergência.
• Divergência de Jensen–Shannon entre as seleções dos solvers.

Resultados Principais

1. Seleção Algorítmica vs. Aleatoriedade

A seleção é determinística e dependente do algoritmo. Em solvers tabulares com valores exatos, a variação entre sementes aleatórias é zero. As diferenças emergem estritamente entre famílias de algoritmos, particularmente em conjuntos de Nash geometricamente assimétricos. Em conjuntos simétricos, a maioria dos solvers convergentes concorda; em conjuntos assimétricos, as famílias divergem significativamente.

2. Métodos Regularizados Selecionam Entropia Máxima (I-Projeção)

Com uma referência inicial uniforme, métodos de última iteração regularizados (especificamente R-NaD) selecionam o membro de entropia máxima do conjunto de Nash.

• Exatidão: No politopo 2-D e em todos os jogos de matriz, o R-NaD seleciona o ponto de entropia máxima analítica (dentro da precisão numérica).
• Kuhn Poker: O R-NaD seleciona uma frequência de blefe que atinge 99,7% da entropia máxima. A pequena lacuna residual é atribuída à planicidade do relevo de entropia próximo ao máximo, não a uma falha do algoritmo.
• Generalização: Em um ensemble de 180 jogos assimétricos, o R-NaD atinge o membro de entropia máxima analítica em 100% dos jogos convergidos.
• Mecanismo: Este comportamento é caracterizado como a Projeção de Informação (I-projeção) da referência uniforme sobre o politopo de Nash. A seleção é "seguidora de âncora": se a referência é enviesada, o equilíbrio selecionado desloca-se em direção à I-projeção dessa referência enviesada.

3. Métodos de Média de Arrependimento Derivam para Menor Entropia

Métodos de média de arrependimento (CFR, CFR+, FP) derivam consistentemente para faces de menor entropia ou fronteiras do politopo de Nash em jogos assimétricos.

• CFR+ situa-se estritamente abaixo do membro de entropia máxima em 94% do ensemble aleatorizado (lacuna média de entropia de +0,121).
• Fictitious Play deriva para a fronteira mesmo em jogos simétricos, igualando a entropia máxima apenas em Kuhn (tratado como uma anomalia).
• O desvio não é convergência incompleta: Aumentar o orçamento de iterações move os métodos de média de arrependimento ainda mais longe do membro de entropia máxima, confirmando que o desvio é uma propriedade da regra de atualização, não de falta de computação.

4. Refutação de Mecanismos Comuns

O artigo apresenta dois resultados negativos corrigindo intuições comuns:

• A Hipótese da Projeção: O desvio para a fronteira do CFR é amplamente atribuído à projeção no ortante positivo max(R, 0). Ao substituir isso por um softmax (Hedge) mantendo os arrependimentos fixos, os autores mostram que o desvio aumenta. Assim, a projeção não é a causa do desvio para a fronteira.
• Independência de Inicialização: A seleção do R-NaD não é incondicional; ela depende da referência inicial (âncora-seguidora).

5. Consequências a Jusante

A robustez do equilíbrio selecionado contra oponentes subótimos varia:

• Kuhn Poker: O membro de entropia máxima (R-NaD) é um hedge estritamente melhor contra oponentes falhos (over-folding/over-calling) do que o membro do CFR+, sem custo contra oponentes ótimos.
• Jogos de Matriz: Os membros diferem, mas nenhum domina estritamente o outro através de todas as desvios do oponente.
• Magnitude: Enquanto a vantagem relativa escala com a estrutura sequencial/informação oculta (aproximadamente 5,6× maior em Kuhn do que em jogos de matriz), a magnitude absoluta do efeito é limitada (< 0,02 em exploitabilidade).

Significância e Alegações

O artigo estabelece que "resolver" um jogo com múltiplos equilíbrios não é um processo neutro; a escolha do solver determina sistematicamente o perfil de estratégia resultante.

• Caracterização: Os autores propõem uma conjectura fortemente sustentada por dados de que métodos de última iteração regularizados (como R-NaD) computam a I-projeção da política de referência sobre o politopo de Nash. Com uma referência uniforme, isso resulta no equilíbrio de entropia máxima.
• Distinção: O artigo distingue cuidadosamente fenômenos demonstrados (famílias de solvers selecionam pontos diferentes; R-NaD seleciona max-entropia com inicial uniforme) de mecanismos conjecturados (a caracterização da I-projeção).
• Correção: Corrige o equívoco de que o desvio de fronteira do CFR é causado pela projeção max(R, 0) e que a seleção de solver é meramente uma função de sementes aleatórias ou de iterações insuficientes.
• Escopo: Os achados são específicos para jogos 2p0s. O artigo observa que, em configurações de soma zero, a seleção afeta a robustez fora do caminho, mas não o valor do jogo (devido ao teorema minimax); equilíbrios com valores distintos exigem jogos de soma geral, que estão fora do escopo deste trabalho.

O trabalho enfatiza que, embora os solvers sejam intercambiáveis para encontrar um equilíbrio de Nash, eles não são intercambiáveis para encontrar um tipo específico de equilíbrio (ex: o mais robusto ou entrópico), e essa escolha é uma propriedade inerente da regra de atualização do algoritmo.