미니맥스 정리 (Minimax Theorem)

수학

한 줄 정의: 두 사람이 서로 반대되는 이익을 두고 겨루는 상황(제로섬 게임)에서, "내가 최악을 가정했을 때 얻을 수 있는 최선의 값"과 "상대가 최악을 가정했을 때 얻을 수 있는 최선의 값"이 결국 하나의 값으로 일치한다는 정리입니다.

쉽게 풀면

가위바위보를 생각해보면, 내가 어떤 전략을 쓰든 상대가 내 패턴을 안다면 나는 지게 됩니다. 그래서 최선의 전략은 "가위, 바위, 보를 각각 1/3 확률로 무작위로 낸다"는 확률 전략입니다. 이때 나는 "최악의 상황(상대가 내 전략을 완전히 안다)에서도 확보할 수 있는 가장 좋은 결과"를 계산하고, 상대도 똑같이 "최악의 상황에서 확보할 수 있는 가장 좋은 결과"를 계산합니다. 미니맥스 정리는 이렇게 서로 반대 입장에서 계산한 두 값이, 양쪽 모두 확률을 섞어 쓰는 전략(혼합전략)을 허용하면 정확히 같은 값으로 만난다는 것을 증명한 정리입니다. 이 값을 "게임의 값(value of the game)"이라고 부릅니다.

왜 중요한가

미니맥스 정리는 대립하는 두 주체의 최적 전략이 하나의 값으로 수렴한다는 것을 보장하기 때문에, 게임이론뿐 아니라 최적화·통계적 의사결정·기계학습 전반에서 목적 함수를 설계하는 이론적 토대로 쓰입니다. 특히 최악의 경우를 가정하고도 안정적인 해를 찾아야 하는 강건 최적화나 적대적 학습 분야에서, 두 값이 일치한다는 성질은 알고리즘의 수렴성과 최적성을 증명하는 데 직접 활용됩니다.

논문에서는 이렇게 쓰입니다

"적대적 생성 신경망(GAN)의 학습 목표는 생성자와 판별자 사이의 미니맥스 게임(minimax game)으로 정식화되며, 이는 미니맥스 정리(minimax theorem)와 밀접하게 연관되어 있다."

이 문장은 "생성자는 판별자를 속이려 하고 판별자는 속지 않으려 하는 두 신경망의 경쟁 구조를, 한쪽은 최소화하고 다른 쪽은 최대화하려는 하나의 수식으로 표현했다"는 뜻입니다. 게임이론뿐 아니라 적대적 학습(adversarial learning), 강건 최적화(robust optimization) 논문에서 목적 함수의 구조를 설명할 때 자주 인용됩니다.

"본 연구는 통계적 의사결정 이론의 관점에서, 미니맥스 정리를 이용해 최악의 사전분포 하에서도 위험을 최소화하는 미니맥스 추정량(minimax estimator)의 존재를 보였다."

베이즈 통계나 결정이론 분야에서, 미지의 모수나 사전분포가 어떤 값을 가지더라도 손실을 일정 수준 이하로 억제하는 추정 전략을 구성할 때 미니맥스 정리가 근거로 쓰인다는 뜻입니다.

"강건 최적화 문제를 원문제와 쌍대문제 사이의 미니맥스 구조로 재정식화하고, 이 둘 사이에 강쌍대성(strong duality)이 성립함을 미니맥스 정리를 통해 확인하였다."

운용과학이나 제어이론 논문에서, 불확실성이 존재하는 상황의 최적화 문제를 원문제-쌍대문제 관계로 바꾸어 풀 때 미니맥스 정리가 이론적 정당성을 제공한다는 의미입니다.

조금 더 깊게 보면

미니맥스 정리가 성립하려면 전략 공간이 볼록집합이고 목적 함수가 오목-볼록 구조를 가지는 등 일정한 조건이 필요하며, 이 일반화된 형태는 폰 노이만의 원래 정리를 확장한 시온(Sion)의 미니맥스 정리로 알려져 있습니다. 또한 선형계획법에서 원문제의 최적값과 쌍대문제의 최적값이 일치하는 강쌍대성은 미니맥스 정리와 수학적으로 동치 관계에 있어, 최적화 이론을 다루는 논문에서는 두 개념이 함께 언급되는 경우가 많습니다.

주의할 점

미니맥스 정리는 참가자가 순수하게 한 가지 전략만 고집할 경우에는 성립하지 않을 수 있으며, 확률을 섞어 쓰는 혼합전략을 허용해야 최솟값과 최댓값이 일치합니다. 또한 이 정리는 선형계획법의 쌍대성(duality) 이론과 수학적으로 동치인 것으로 알려져 있어, 선형계획법과 함께 이해하면 도움이 됩니다.