내시 균형은 하나가 아니다, 풀이 알고리즘이 해를 고르는 숨은 편향

두 사람이 겨루는 제로섬 게임에서 내시 균형을 구한다는 것은 흔히 "정답을 찾는다"는 말로 이해된다. 미니맥스 값이 정해져 있고, 그 값을 보장하는 전략이 존재하니, 어떤 풀이 알고리즘을 쓰든 결국 같은 곳에 도달하리라는 직관이다. 게임 솔버들이 서로 교체 가능한 도구처럼 취급되어 온 것도 이 때문이다. 그러나 루이스 레알의 이 연구는 그 직관이 미묘하지만 중요한 지점에서 무너진다는 것을 분석적으로 풀어낸다. 많은 제로섬 게임의 내시 균형은 점 하나가 아니라, 동일한 게임 값을 공유하면서도 서로 다른 행동을 지시하는 균형들의 볼록 집합, 즉 다면체(polytope)를 이룬다. 이때 어떤 알고리즘을 쓰느냐가 이 집합 안에서 어느 점을 고를지를 체계적으로 결정한다는 것이 핵심 주장이다.

시드가 아니라 알고리즘이 답을 고른다

연구의 설계는 단정하다. 내시 집합을 해석적으로 정확히 알 수 있는 여섯 개의 작은 게임을 테스트베드로 삼았다. 2차원 내시 다면체를 가진 인공 게임부터, 불완전 정보 게임의 고전인 쿤 포커(Kuhn poker)까지 포함된다. 정답의 형태를 수학적으로 알고 있으니, 각 솔버가 실제로 어디에 안착하는지를 진짜 기준선과 직접 대조할 수 있다. 가장 먼저 확인된 사실은, 솔버가 고르는 균형이 난수 시드 같은 우연이 아니라 알고리즘 자체에 의해 결정된다는 점이다. 다만 이 차이는 균형 집합이 비대칭일 때만 드러난다. 대칭적인 내시 집합에서는 모든 방법이 같은 점으로 수렴하므로 차이가 보이지 않는다. 솔버를 교체 가능하다고 믿어온 통념이 오랫동안 들키지 않은 이유가 여기에 있다.

흥미로운 것은 알고리즘 계열에 따라 선택이 뚜렷하게 갈린다는 점이다. 정규화된 마지막 반복(last-iterate) 계열인 R-NaD와 자기장 거울하강법은 균형 집합 안에서 최대 엔트로피를 가진 점을 고른다. 이는 균일한 기준 분포를 내시 집합 위로 정보 사영(I-projection)한 결과와 정확히 일치한다. 2차원 다면체에서는 정확히, 쿤 포커에서는 최대 엔트로피의 99.7%에 도달한다. 반면 후회 평균화(regret-averaging) 계열인 CFR, CFR+, 가상 플레이는 엔트로피가 더 낮은 면으로 흘러간다. 무작위로 생성한 180개 게임 앙상블에서도 R-NaD는 수렴한 모든 게임에서 최대 엔트로피 균형에 도달한 반면, CFR+는 94%의 게임에서 그보다 엄밀히 낮은 곳에 머물렀다. 짝지은 윌콕슨 검정에서 p값이 10의 마이너스 27제곱 아래로 나온다는 것은, 이것이 우연이 아니라 알고리즘에 새겨진 구조적 편향임을 말해준다.

어떤 균형을 고르느냐가 실전에서 갈리는 지점

같은 게임 값을 보장한다면 어느 균형을 고르든 상관없지 않을까. 상대가 완벽하게 합리적이라면 그렇다. 그러나 상대가 최적이 아닌 수를 둘 때, 선택된 균형의 차이가 실제 성과로 이어진다. 이 효과는 게임의 순차적·은닉 정보 구조가 풍부할수록 커지되, 무한히 벌어지지는 않고 유계로 머문다. 쿤 포커에서는 최대 엔트로피 균형이 엄밀하게 더 나은 헤지가 된다. 상대의 실수를 더 폭넓게 흡수하기 때문이다. 반면 단순 행렬 게임에서는 균형들이 서로 다르긴 해도 어느 한쪽이 지배하지는 않는다. 최대 엔트로피 선택이 만능 우위는 아니지만, 정보가 숨겨진 게임일수록 보수적이고 강건한 선택이 된다는 결론이다.

저자는 흔한 직관을 교정하는 두 가지 음성 결과도 함께 보고한다. CFR의 양의 직교 사영(음수 후회를 0으로 자르는 처리)을 제거해도 경계로의 쏠림은 사라지지 않으며, R-NaD의 선택 역시 초기화와 무관한 것이 아니라 기준점을 따라가는 성질(anchor-following)을 가진다. 즉 R-NaD가 최대 엔트로피를 고르는 것은 균일 기준 분포를 닻으로 삼았기 때문이며, 그 닻을 바꾸면 선택도 따라 움직인다. 최대 엔트로피 또는 정보 사영이라는 특성화는 아직 정리로 증명된 것이 아니라, 해석적 정답과 끊임없이 대조해 검증한 강하게 데이터로 뒷받침된 추측으로 제시된다.

이 연구가 던지는 메시지는 실용적이다. 멀티에이전트 강화학습과 게임 풀이가 점점 더 큰 시스템에 들어가는 지금, "균형에 수렴했다"는 보고만으로는 충분하지 않다. 어떤 솔버를 골랐느냐가 곧 어떤 행동을 배포하느냐를 결정하며, 그 선택은 재현성과 강건성, 그리고 비합리적 상대에 대한 대응 능력에까지 영향을 미친다. 솔버는 더 이상 투명한 도구가 아니라, 그 자체로 정책을 고르는 행위자다.