어떤 내쉬 균형(Nash Equilibrium)인가? 제로섬 내쉬 다면체(Zero-Sum Nash Polytopes)에서의 솔버 의존적 선택

많은 2인 제로섬 게임(two-player zero-sum games)은 유일한 내쉬 균형(Nash equilibrium)이 아니라, 볼록 집합(convex set)을 허용합니다. 즉, 모두 동일한 미니맥스 값(minimax value) V*를 공유하면서도 서로 다른 행동을 규정하는 프로필들의 다면체(polytope)가 존재합니다. 표준 솔버(Standard solvers)들은 각각 특정 균형으로 수렴하며 서로 교체 가능한 것으로 취급됩니다. 우리는 이들이 시드(seed)가 아닌 알고리즘의 함수로서 체계적으로 내쉬 집합(Nash set)의 서로 다른 구성원을 선택하는지 질문합니다. 분석적으로 알려진 내쉬 집합을 가진 6개 게임(2차원 내쉬 다면체와 Kuhn poker 포함)의 테이블형(tabular) 정밀 해결 가능 테스트베드를 사용하여, 우리는 다음을 발견했습니다: (i) 선택은 시드가 아닌 알고리즘에 의해 결정되지만, 알고리즘 군(families)은 비대칭 내쉬 집합(asymmetric Nash sets)에서만 차이를 보입니다; (ii) 정규화된 마지막 반복 방법(regularized last-iterate methods; R-NaD, magnetic mirror descent)은 최대 엔트로피(maximum-entropy) 구성원을 선택하며, 이는 균등 참조(uniform reference)를 내쉬 집합으로 정보 투영(information projection)한 결과입니다. 이는 2차원 다면체에서 정확히 일치하며 Kuhn poker에서는 최대 엔트로피의 99.7%에 달합니다. 반면 후회 평균 방법(regret-averaging methods; CFR, CFR+, fictitious play)은 더 낮은 엔트로피의 면(face)으로 표류(drift)합니다. 우리는 180개 게임의 무작위 앙상블(ensemble)을 통해 이를 확인했으며, 여기서 R-NaD는 수렴한 게임의 100%에서 최대 엔트로피 구성원을 달성한 반면, CFR+는 94%에서 그보다 엄격히 낮은 위치에 있었습니다 (paired Wilcoxon p < 10^-27); (iii) 선택된 구성원은 순차적/숨겨진 정보 구조(sequential/hidden-information structure)에 따라 규모가 달라지지만 유계(bounded)를 유지하는, 하위 최적(sub-optimal) 상대에 대한 다운스트림 결과(downstream consequences)를 가집니다. Kuhn poker에서 최대 엔로피 구성원은 엄격하게 더 나은 헤지(hedge)인 반면, 행렬 게임(matrix games)에서는 구성원들이 어느 하나가 지배하지 않는 방식으로 서로 다릅니다. 우리는 또한 일반적인 직관을 교정하는 두 가지 부정적인 결과도 보고합니다: CFR의 양의 직교 영역(positive-orthant; max(R,0)) 투영을 제거해도 경계 표류(boundary drift)가 사라지지 않으며, R-NaD의 선택은 초기화와 독립적인 것이 아니라 앵커 추종(anchor-following) 방식입니다. 우리는 최대 엔트로피 / I-투영(I-projection) 특성화를 분석적 실측값(analytic ground truth)을 통해 지속적으로 검증한, 강력한 데이터 지원을 받는 추측(conjecture)으로 제시합니다.