Minimax·안장점·보장 하한과 상한

두 플레이어의 최적화 방향부터 고정하기

행 플레이어는 보수 F를 최대화하고 열 플레이어는 이를 최소화합니다. 각자의 효용이 F와 −F이므로 제로섬 게임입니다. 행 행동 0의 확률을 p, 열 행동 0의 확률을 q라 하면 다음과 같습니다.

$$F(p,q)=(p,1-p)A(q,1-q)^T,\qquad p,q\in[0,1].$$

A의 네 값은 양수·0·음수일 수 있습니다. 행 보수가 음수라는 것은 0에 비해 열 플레이어에게 유리하다는 뜻입니다. 실제 돈이 오가야 한다는 가정은 하지 않습니다.

두 사람은 독립적으로 혼합하고 상대가 이번에 뽑은 실제 행동을 보기 전에 결정합니다. 알려진 확률 분포에 대응하는 것과 표본 행동을 본 뒤 대응하는 것은 다릅니다. 상대에게 표본 관측 정보를 추가하면 게임이 달라지고 비공개 혼합의 이점이 사라질 수 있습니다.

순수 선택에서는 간극이 남을 수 있다

순수 행동만 허용하면 행은 행별 최솟값 중 가장 큰 것을 보장하고, 열은 열별 최댓값 중 가장 작은 것으로 보수를 제한합니다.

$$\underline v_{\rm pure}=\max_i\min_j A_{ij},\qquad \overline v_{\rm pure}=\min_j\max_i A_{ij}.$$

하한이 상한보다 클 수는 없지만 두 값이 같을 필요는 없습니다. A=(1,−1;−1,1)이면 각 행의 최솟값은 −1, 각 열의 최댓값은 1입니다. 순수 보장은 −1과 1이고 순수 안장점은 없습니다. 이것은 순수 선택의 등식이 실패한 예이지 유한 혼합전략 minimax 정리의 반례가 아닙니다.

혼합하면 가능한 전략 집합이 몇 개의 행동에서 확률 단체로 바뀝니다. 이산 행동을 물리적인 값의 평균으로 대신하는 것과 다릅니다. 전체 보수 행렬을 사용한 기대 보수가 확률에 선형이라는 점을 이용합니다.

선택한 혼합의 보장 곡선

행 혼합 p를 고정하면 상대가 고를 두 순수 열에 대해 기대 보수 두 개가 나옵니다. 작은 쪽이 보장 수준입니다. 열 혼합 q는 두 순수 행을 상대하므로 큰 쪽이 행 보수의 상한입니다.

$$L(p)=\min\{pA_{00}+(1-p)A_{10},\ pA_{01}+(1-p)A_{11}\},$$ $$U(q)=\max\{qA_{00}+(1-q)A_{01},\ qA_{10}+(1-q)A_{11}\}.$$

열을 섞어도 행 보수가 순수 열 보수의 최솟값 아래로 내려가지는 않습니다. 행을 섞어도 순수 행 보수의 최댓값을 넘지 않습니다. 따라서 어떤 가능한 전략 쌍에서도 다음을 얻습니다.

$$L(p)\le F(p,q)\le U(q).$$

하한 곡선은 p에 대해 오목한 조각별 아핀 함수이고 상한 곡선은 q에 대해 볼록한 조각별 아핀 함수입니다. 파랑과 주황은 같은 단위 구간에 그리지만 서로 다른 혼합 변수를 사용합니다. 두 사람의 보수를 하나의 공동 이동 경로에 그린 것이 아닙니다.

약한 부등식과 minimax 값

어떤 p,q에서도 L(p)는 U(q)를 넘을 수 없습니다. 각각 최적화하면 약한 minimax 부등식이 나옵니다. 유한 혼합 제로섬 정리는 최적값의 일치와 달성을 보장합니다.

$$\max_p L(p)=v=\min_q U(q).$$

따라서 현재 어떤 전략을 조회하더라도 실제 게임 값이 다음 범위에 있습니다.

$$L(p)\le v\le U(q).$$

두 문장을 구분하세요. 현재 보수 F와 최적 게임 값 v가 각각 하한과 상한 사이에 있다는 뜻이며, F와 v가 서로 같아야 하는 것은 아닙니다. 최적화한 두 값이 같다는 것과 임의의 최적이 아닌 조회에서 두 보장이 같다는 것은 다릅니다.

Goemans의 MIT 선형계획 강의노트 7절은 유한 제로섬 보장과 LP 쌍대성으로 얻는 minimax 정리를 설명합니다. 이 단원의 행렬과 두 직선 보장 곡선 구성은 실습을 위해 직접 만들었습니다.

선형계획 쌍대성이 적용되는 이유

일반 유한 보수 행렬과 확률 벡터 x,y에 대해 행 플레이어는 보장 수준 ℓ을 최대화합니다. 제약은 다음과 같습니다.

$$A^Tx\ge\ell\mathbf1,\quad \mathbf1^Tx=1,\quad x\ge0.$$

열 플레이어는 다음 조건에서 u를 최소화합니다.

$$Ay\le u\mathbf1,\quad \mathbf1^Ty=1,\quad y\ge0.$$

수준 변수의 부호는 자유입니다. 이 둘은 원문제·쌍대문제의 한 쌍입니다. 확률 단체는 비어 있지 않고 유한한 보수 값이 보장 수준을 유계로 만듭니다. LP 강한 쌍대성으로 최적값이 같습니다. 단순히 식에 min과 max를 썼기 때문이 아니라 실제 가능성·목적·쌍대 구조에 근거한 결론입니다.

안장점 부등식과 전체 해 집합

행 최대화와 열 최소화의 안장점은 다음을 만족합니다.

$$F(p,q^*)\le F(p^*,q^*)\le F(p^*,q) \quad\text{for all }p,q.$$

q를 고정하면 행이 바꿔도 F를 높일 수 없고, p를 고정하면 열이 바꿔도 F를 낮출 수 없습니다. 어떤 변수가 최소화하는지 바꾸면 부등식 방향도 바뀝니다. Bertsekas의 MIT 9강은 이런 역할을 명시해 안장점과 minimax 등식·최적값 달성을 연결합니다.

p가 L을, q가 U를 최적화하면 L(p*)≤F(p*,q*)≤U(q*)의 양 끝이 v라서 가운데도 v입니다. 같은 보장으로 두 안장 부등식을 얻습니다. 반대로 안장점은 최적 보장 전략을 줍니다. 전체 제로섬 안장 집합은 행 최적 집합과 열 최적 집합의 곱입니다. 두 행동 모형에서는 각각 점일 수도 있는 닫힌 구간입니다.

쌍대 간극으로 현재 전략의 유인 측정하기

현재 전략에서 행 플레이어의 최대 일방 이득은 U(q)−F(p,q)입니다. 열 플레이어의 효용은 −F이므로 개선량은 F(p,q)−L(p)입니다. 더하면 다음과 같습니다.

$$g_{\rm row}+g_{\rm column}=U(q)-L(p)\ge0.$$

간극이 0이면 두 개선량이 모두 0이므로 안장점이며 효용 (A,−A)의 Nash입니다. 양의 간극은 현재 전략의 문제를 말할 뿐 게임의 정확한 minimax 값이 없다는 뜻은 아닙니다. 현재 조회 확률은 n/12이고 이득은 공통 분모 144의 정수 분자로 계산합니다. 정확한 0 판정과 표시용 반올림 숫자는 구분합니다.

손계산: 혼합이 순수 간극을 닫는다

A=(1,−1;−1,1)의 순수 보장은 −1과 1입니다. p=q=1이면 F=1,L=−1,U=1이고 간극은 2입니다. 행은 고정된 q=1에 이미 최적인 보수를 받고, 열은 열을 바꿔 자신의 보수를 2 개선할 수 있습니다.

p=q=1/2에서는 두 보장 곡선이 모두 0입니다. 상대의 어떤 순수 선택도 기대 행 보수 0을 줍니다. 혼합 값은 0이고 간극도 사라집니다. 입력 분자를 6과 6으로 바꿔 정확히 확인하세요. 최적 구간의 곱은 (1/2,1/2) 한 점입니다.

손계산: 서로 다른 최적 확률

A=(3,0;1,2)의 행 보장 직선은 1+2p와 2−2p입니다. p=1/4에서 만나 값 3/2를 줍니다. 열 상한 직선은 3q와 2−q이고 q=1/2에서 같은 값으로 만납니다. 순수 하한과 상한은 1과 2입니다.

서로 다른 보장 곡선을 최적화하므로 p와 q가 같아야 할 이유는 없습니다. 두 번째 예제는 p=3/12,q=6/12를 사용합니다. 네 보장·보수·값 표식이 모두 1.5에 모이고 간극이 0입니다. 그래프의 꺾임점은 거친 수치 탐색의 결과가 아니라 정확한 유리수 경계입니다.

퇴화와 조회 격자 밖의 해

A=(2,2;0,0)에서 행은 p=1로 2를 보장하고 열은 어떤 q도 최적입니다. 안장 집합은 수직 선분이며 q 하나가 유일하다고 고르면 잘못입니다. 네 보수가 모두 같으면 두 최적 구간이 [0,1]이 되어 정사각형 전체가 안장점입니다.

A=(4,0;0,3)이면 두 최적 확률은 3/7이고 값은 12/7입니다. 어떤 n/12도 3/7과 같지 않습니다. 그래도 표와 곡선 꺾임점에는 정확한 분수를 남깁니다. p=q=5/12의 하한은 5/3, 상한은 7/4로 간극 1/12가 남습니다. 최적값을 조회 격자에 억지로 맞추면 이 차이를 가리게 됩니다.

계산기는 구간 끝점과 내부에 있을 때의 두 직선 교점을 평가합니다. 조각별 아핀 보장 곡선은 꺾임점에서 최적이 되거나 끝점이 꺾임점인 평평한 최적 구간을 가집니다. 모든 최적 끝점을 모아 전체 최적 구간을 얻습니다. 이 작은 정확 계산을 일반 대규모 LP 구현이라고 주장하지는 않습니다.

min과 max를 바꿀 수 없는 경우

유한 혼합 정리는 확률 단체 위의 연속 쌍선형 보수를 사용합니다. 더 일반적인 연속 minimax에서는 정의역·최적값 달성·볼록성과 오목성 조건을 확인해야 합니다. 단지 정의역이 콤팩트하고 볼록하다는 사실만으로는 충분하지 않습니다.

[−1,1]^2에서 F(x,y)=(x−y)^2를 x에 대해 최대화하고 y에 대해 최소화해 봅시다. 각 x의 최소화 선택은 y=x로 값이 0이어서 max_x min_y F=0입니다. y를 고정하면 가장 불리한 x 끝점의 보수는 (1+|y|)^2이고 그 최솟값은 y=0에서 1입니다. 따라서 min_y max_x F=1입니다. 최대화 변수에 대해 오목하지 않고 볼록하다는 점이 중요합니다. 이는 연속 값을 직접 선택하는 문제이며 그 선택을 무작위화하면 별도의 기대 보수 문제가 됩니다.

존재나 쌍대성 정리는 특정 상승·하강 알고리즘의 수렴도 증명하지 않습니다. 제로섬 학습에는 업데이트 규칙과 안정성 가정, 별도의 수렴 분석이 필요합니다.

연습 문제와 해설

문제 1: 상반 보수 행렬에서 p=3/4,q=1/4의 L,U,F와 두 일방 이득을 구하세요.

해설: L=−1/2,U=1/2이고 F=(2p−1)(2q−1)=−1/4입니다. 행 이득은 3/4, 열 이득은 1/4여서 합 1이 쌍대 간극과 같습니다. 게임 값 0과 그와 다른 현재 보수 −1/4가 둘 다 보장 사이에 있습니다.

문제 2: A=(2,2;0,0)에서 p=1일 때 q=0 대신 q=5/12를 쓰면 최적성이 깨지나요?

해설: 아닙니다. 두 열 모두 행 보수 2를 주므로 모든 q가 최적 구간에 있습니다. 한 q를 유일하다고 보고하면 틀립니다. 반면 p를 1보다 낮추면 행 보장이 줄고 간극이 양수가 됩니다.

문제 3: A=(4,0;0,3)에서 0에 가까운 반올림 표시만으로 조회 격자의 점을 정확한 안장점이라고 인증할 수 없는 이유는?

해설: 정확한 최적 확률은 격자 밖의 3/7입니다. 정수 간극 분자와 정확한 최적 구간을 확인해야 합니다. 최적점 가까이의 소수 표시는 근사이고, 유리수 해와 정확한 0 검사는 서로 다른 주장을 합니다.