Resumen Técnico: Selección Dependiente del Solucionador en Polítopos de Nash de Suma Cero

Planteamiento del Problema

En la teoría de juegos computacional, los juegos de dos jugadores de suma cero (2p0s) suelen tratarse como si tuvieran un equilibrio de Nash (EN) único. Si bien el teorema de minimax garantiza un valor de juego único $V^\star$, muchos juegos —particularmente aquellos con degeneraciones o simetrías estructurales— poseen un conjunto convexo de equilibrios (un polítopo de Nash). Dentro de este conjunto, todos los perfiles producen $V^\star$ contra un oponente que responde de forma óptima, pero pueden prescribir comportamientos materialmente diferentes fuera de la trayectoria del equilibrio, utilizar diferentes soportes y exhibir una mayor o menor robustez ante oponentes subóptimos.

Los solucionadores estándar garantizan la convergencia a algún equilibrio, pero frecuentemente se tratan como intercambiables. Este trabajo investiga si diferentes familias de solucionadores seleccionan sistemáticamente distintos miembros del conjunto de Nash en función de su estructura algorítmica, en lugar de debido a semillas aleatorias o presupuestos de iteración. Además, busca caracterizar los criterios de selección específicos (por ejemplo, la máxima entropía) empleados por estos algoritmos.

Metodología

Los autores emplean un banco de pruebas tabular, mínimo y totalmente transparente para eliminar la varianza proveniente del muestreo o la aproximación de funciones. El estudio utiliza valores contrafácticos exactos para asegurar que la verdad fundamental sea analíticamente conocida.

Banco de Pruebas:

• Seis Juegos Construidos a Mano: Incluyendo controles simétricos (ej. "pennies safe"), juegos asimétricos (ej. "asym safe"), un juego con un polítopo de Nash genuinamente bidimensional ("polytope4") y Kuhn poker.
• Ensamble Aleatorizado: Una población de 180 juegos de matrices asimétricos aleatorios con caras de Nash analíticamente conocidas para probar la generalización.

Familias de Solucionadores Comparadas:

1. Métodos de Promedio de Arrepentimiento (Regret-Averaging): Despliegan un promedio temporal de estrategias.
   • Minimización de Arrepentimiento Contrafáctico (CFR)
   • CFR+ (promedio ponderado linealmente)
   • Juego Ficticio (Fictitious Play - FP)
   • Hedge (utilizado como ablación para probar mecanismos de proyección)
2. Métodos de Última Iteración Regularizados: Despliegan la última iteración de una dinámica anclada a una política de referencia.
   • Dinámica de Nash Regularizada (R-NaD): Utiliza una referencia móvil (reiniciada periódicamente a la política actual).
   • Descenso de Espejo Magnético (MMD): Utiliza una referencia fija.
   • Actualización de Pesos Multiplicativos (MWU/NeuRD): Última iteración no regularizada.

Métricas:

• Coordenada de selección (posición dentro del polítopo de Nash).
• Entropía de política media (entropía de Shannon).
• Explotabilidad (NashConv) para verificar la convergencia.
• Divergencia de Jensen–Shannon entre las selecciones de los solucionadores.

Resultados Clave

1. Selección Algorítmica vs. Aleatoriedad

La selección es determinista y dependiente del algoritmo. En solucionadores tabulares con valores exactos, la variación entre semillas aleatorias es cero. Las diferencias emergen estrictamente entre familias de algoritmos, particularmente en conjuntos de Nash geométricamente asimétricos. En conjuntos simétricos, la mayoría de los solucionadores que convergen coinciden; en conjuntos asimétricos, las familias divergen significamente.

2. Los Métodos Regularizados Seleccionan la Máxima Entropía (Proyección I)

Con una referencia inicial uniforme, los métodos de última iteración regularizados (específicamente R-NaD) seleccionan el miembro de máxima entropía del conjunto de Nash.

• Exactitud: En el polítopo 2-D y en todos los juegos de matrices, R-NaD selecciona el punto de máxima entropía analítica (dentro de la precisión numérica).
• Kuhn Poker: R-NaD selecciona una frecuencia de farol (bluff) que produce el 99.7% de la máxima entropía. La pequeña brecha residual se atribuye a la planitud del paisaje de entropía cerca del máximo, no a un fallo del algoritmo.
• Generalización: En un ensamble de 180 juegos asimétricos, R-NaD alcanza el miembro de máxima entropía analítica en el 100% de los juegos convergidos.
• Mecanismo: Este comportamiento se caracteriza como la Proyección de Información (I-proyección) de la referencia uniforme sobre el polítopo de Nash. La selección es de "seguimiento de ancla": si la referencia está sesgada, el equilibrio seleccionado se desplaza hacia la I-proyección de esa referencia sesgada.

3. Los Métodos de Promedio de Arrepentimiento Derivan hacia una Menor Entropía

Los métodos de promedio de arrepentimiento (CFR, CFR+, FP) derivan consistentemente hacia caras de menor entropía o hacia los límites del polítopo de Nash en juegos asimétricos.

• CFR+ se sitúa estrictamente por debajo del miembro de máxima entropía en el 94% del ensamble aleatorizado (brecha de entropía media de +0.121).
• El Juego Ficticio (Fictitious Play) deriva hacia el límite incluso en juegos simétricos, igualando la máxima entropía solo en Kuhn (tratado como una anomalía).
• La deriva no es falta de convergencia: Aumentar el presupuesto de iteraciones mueve a los métodos de promedio de arrepentimiento aún más lejos del miembro de máxima entropía, confirmando que la deriva es una propiedad de la regla de actualización, no de la falta de cómputo.

4. Refutación de Mecanismos Comunes

El documento presenta dos resultados negativos que corrigen intuiciones comunes:

• La Hipótesis de la Proyección: La deriva hacia el límite de CFR se atribuye ampliamente a la proyección de ortante positivo max(R, 0). Al reemplazar esto con un softmax (Hedge) manteniendo los arrepentimientos fijos, los autores muestran que la deriva aumenta. Por lo tanto, la proyección no es la causa de la deriva al límite.
• Independencia de la Inicialización: La selección de R-NaD no es incondicional; depende de la referencia inicial (seguimiento de ancla).

5. Consecuencias Derivadas

La robustez del equilibrio seleccionado contra oponentes subóptimos varía:

• Kuhn Poker: El miembro de máxima entropía (R-NA) es un escudo estrictamente mejor contra oponentes defectuosos (que pasan demasiado o que llaman demasiado) que el miembro de CFR+, sin costo contra oponentes óptimos.
• Juegos de Matrices: Los miembros difieren, pero ninguno domina estrictamente al otro a través de todas las desviaciones del oponente.
• Magnitud: Aunque la ventaja relativa escala con la estructura secuencial/de información oculta (aproximadamente 5.6 veces mayor en Kuhn que en juegos de matrices), la magnitud absoluta del efecto es limitada (< 0.02 en explotabilidad).

Significancia y Reivindicaciones

El artículo establece que "resolver" un juego con múltiples equilibrios no es un proceso neutral; la elección del solucionador determina sistemáticamente el perfil de estrategia resultante.

• Caracterización: Los autores proponen una conjetura fuertemente respaldada por datos de que los métodos de última iteración regularizados (como R-NaD) computan la I-proyección de su política de referencia sobre el polítopo de Nash. Con una referencia uniforme, esto produce el equilibrio de máxima entropía.
• Distinción: El documento distingue cuidadosamente entre los fenómenos demostrados (las familias de solucionadores seleccionan puntos diferentes; R-NaD selecciona la máxima entropía con inicialización uniforme) y los mecanismos conjeturados (la caracterización de la I-proyección).
• Corrección: Corrige la idea errónea de que la deriva al límite de CFR es causada por la proyección max(R, 0) y que la selección del solucionador es meramente una función de las semillas aleatorias o de la insuficiencia de iteraciones.
• Alcance: Los hallazgos son específicos para juegos 2p0s. El documento señala que, en entornos de suma cero, la selección afecta la robustez fuera de la trayectoria (off-path), pero no el valor del juego (debido al teorema de minimax); los equilibrios con valores distintos requieren entornos de suma general, que están fuera del alcance de este trabajo.

El trabajo enfatiza que, si bien los solucionadores son intercambiables para encontrar un equilibrio de Nash, no lo son para encontrar un tipo de equilibrio específico (por ejemplo, el más robusto o entrópico), y esta elección es una propiedad inherente de la regla de actualización del algoritmo.