해의 존재·고정점·반복 수렴의 구분

서로 다른 근거가 필요한 세 주장

해가 존재해도 solver는 실패할 수 있습니다. 반복이 수렴해도 잘못 만든 사상의 고정점으로 갈 수 있습니다. 작은 이동은 평형이 아니라 반올림이나 약한 수축을 나타낼 수도 있습니다. 학습 곡선을 읽기 전에 세 질문을 나눠 보세요.

1. 명시한 수학 문제에 해가 존재하나요?
2. 그 해는 지금 사용하는 사상의 고정점과 같은가요?
3. 선택한 반복 알고리즘은 그 고정점으로 수렴하나요?

앞 단원은 안장점이 존재하는 이차 게임에서 여러 경사 업데이트가 회전·발산하는 경우를 살폈습니다. 여기서는 유한 게임과 콤팩트한 혼합 전략 정사각형으로 옮겨 옵니다. 연속 Nash 사상·순수 최적 반응 선택·두 보조 사상을 비교합니다. 콤팩트성이 확보되어도 존재와 수렴은 별개입니다.

다섯 게임을 명시한다

P1은 행, P2는 열을 고르며 각자의 행동은 0과 1입니다. p와 q는 각각 행동 0의 확률입니다. 두 혼합 선택은 독립입니다. 보수 목록의 순서는 00,01,10,11입니다.

게임	P1 보수 A	P2 보수 B
0 조정	2,0,0,1	2,0,0,1
1 대립	1,−1,−1,1	−1,1,1,−1
2 사회적 딜레마	3,0,5,1	3,5,0,1
3 P1 무차별	0,0,0,0	2,0,0,1
4 모두 무차별	0,0,0,0	0,0,0,0

P1의 기대 보수는 다음과 같습니다.

$$u_1(p,q)=pqA_{00}+p(1-q)A_{01}+(1-p)qA_{10}+(1-p)(1-q)A_{11}.$$

P2는 같은 결합 확률에 B를 사용합니다. P1의 기대 보수가 증가한다고 P2도 좋아지는 것은 아닙니다. 한 참가자의 일방 개선 가능량은 현재 상대에게 가장 좋은 순수 행동의 보수에서 현재 기대 보수를 뺀 값입니다. 임의의 혼합 일탈도 순수 행동 보수들의 평균이므로 순수 일탈만 검사해도 충분합니다.

전체 Nash 집합은 앞의 최적 반응 집합 단원과 같은 방식으로 구합니다. 그림은 점·선분·사각형의 합집합 전체를 보존합니다. ‘조각’은 집합 표현에 사용한 사각형 수이며 위상적 연결 성분 수나 연속 집합 안의 평형 개수가 아닙니다. 주황 집합은 선택한 사상의 고정점 집합으로 별도 계산합니다.

유한 혼합 게임에서 적절한 영역을 얻는다

각 참가자의 확률 벡터는 원소가 음이 아니고 합이 1인 단체를 이룹니다. 유한하고 비어 있지 않은 행동 집합들에 대해 이 단체들의 곱은 유한 차원에서 비어 있지 않고 콤팩트하며 볼록합니다. 기대 보수는 유한 개 확률 곱의 합이므로 연속이고 자기 혼합 전략에 관해서는 선형입니다.

Brouwer 고정점 정리는 이러한 집합의 연속 자기 사상에 고정점이 존재한다고 말합니다. 영역의 비어 있지 않음·콤팩트성·볼록성, 사상의 연속성, 모든 점을 다시 영역 안으로 보내는 성질이 필요합니다. 결론은 존재입니다. 반복 적용의 수렴이나 고정점의 유일성을 말하지는 않습니다.

게임에 맞는 사상도 따로 만들어야 합니다. 임의의 연속 자기 사상에 고정점이 있다고 그 점이 자동으로 게임 평형이 되는 것은 아닙니다.

양의 개선량을 정규화한 Nash 사상

s_i를 참가자 i의 혼합 전략 벡터, s를 전체 프로필이라고 합시다. 순수 행동 a마다 양의 개선량을 정의합니다.

$$g_{i,a}(s)=\max\{0,u_i(a,s_{-i})-u_i(s)\},\qquad G_i(s)=\sum_a g_{i,a}(s).$$

각 행동 확률에 양의 개선량을 더하고 다시 정규화합니다.

$$(T_N(s))_{i,a}=\frac{s_{i,a}+g_{i,a}(s)}{1+G_i(s)}.$$

분모는 적어도 1이고 각 원소는 음이 아니며 참가자별 합은 다시 1입니다. 양의 부분과 유한 기대 보수가 연속이므로 이 사상도 연속입니다. 따라서 콤팩트 볼록 전략 영역의 연속 자기 사상에 Brouwer를 적용할 수 있습니다.

여기까지는 T_N의 고정점 존재만 얻었습니다. 그 점이 Nash인지는 추가 논증이 필요합니다.

고정점과 Nash의 동치를 증명한다

고정점 식의 분모를 곱하면 모든 행동에서 g_{i,a}=s_{i,a}G_i입니다. G_i>0이라고 가정하면 양의 확률을 가진 모든 행동의 양의 개선량이 엄격히 양수입니다. 따라서 그 행동들의 실제 보수 차이도 양수입니다. 하지만

$$\sum_a s_{i,a}\bigl(u_i(a,s_{-i})-u_i(s)\bigr)=0$$

입니다. 혼합 기대 보수가 바로 순수 행동 보수들의 가중 평균이기 때문입니다. 지원 집합의 모든 항이 양수라는 가정과 모순입니다. 결국 모든 참가자의 G_i=0이고 이익이 되는 일방 일탈이 없습니다.

반대로 Nash에서는 양의 개선량이 모두 0이므로 T_N이 원래 전략을 돌려줍니다. 따라서 이 특정 사상의 고정점은 정확히 Nash입니다. 이 동치와 Brouwer를 결합하면 유한 혼합 게임의 존재 정리를 얻습니다. T_N을 반복했을 때의 수렴 속도는 증명하지 않았습니다.

표준 사상과 정리의 배경은 MIT 6.7980 강의 1, 콤팩트 영역의 고정점 논증은 강의 2를 참고하세요. 아래 보수·반복 비교는 명시한 유한 모형에서 직접 계산하는 예제입니다.

유용한 개선식에도 일방 변경이라는 범위가 있다

상대 전략은 고정하고 참가자 i만 Nash 사상의 전략으로 바꾸면 직접 대입하여 다음을 얻습니다.

$$u_i((T_N(s))_i,s_{-i})-u_i(s) =\frac{\sum_a g_{i,a}(s)^2}{1+G_i(s)}.$$

양의 개선량이 있으면 엄격한 효용 개선입니다. 모두 동시에 움직이면 상대가 더 이상 고정되지 않습니다. 모든 사람의 실제 보수가 증가한다고 해석하면 안 됩니다.

대립 게임의 (p,q)=(1,1)을 보세요. P1의 보수는 1이고 양의 개선량은 없습니다. P2의 보수는 −1이고 다른 행동으로 바꾸는 개선량은 2입니다. 전체 Nash 사상은 (1,1/3)을 만듭니다. P2는 4/3만큼 좋아지지만 P1의 실제 보수는 상대 변경 때문에 1에서 −1/3로 떨어집니다. 일방 개선식은 맞고 모두의 보수가 단조 증가한다는 해석은 틀립니다.

제어한 입력의 정확한 인증

p와 q 입력은 12분율입니다. 보수와 순수 일탈을 분모 144의 정수 분자로 구합니다. 초기 입력의 사상 출력·고정 여부·Nash 여부는 약분한 유리수와 정수 등식으로 판정하며 허용오차를 사용하지 않습니다.

조정 게임 p=q=1/3에서 각자의 두 순수 행동 보수는 모두 2/3입니다. 양의 개선량이 전부 0이고 Nash 사상은 정확히 (1/3,1/3)을 돌려줍니다. 전체 Nash 집합에는 (0,0),(1,1)도 있습니다. 존재가 유일성을 뜻하지 않는 사례입니다.

뒤의 반복은 별도입니다. Nash 사상을 정확한 유리수로 계속 반복하면 분모가 빠르게 커질 수 있어서 수치 궤적은 부동소수점을 사용합니다. 그림이 고정된 것처럼 보이거나 표시 잔차가 반올림되어 0처럼 보여도 정확한 Nash 인증으로 바꾸지 않습니다. 정확한 패널의 대상은 직접 제어한 초기 입력입니다.

연속 자기 사상도 영원히 순환할 수 있다

대립 게임과 보조 사분의 일 회전 사상을 고릅니다.

$$Q(p,q)=(q,1-p).$$

정사각형을 연속적으로 자기 자신에 보냅니다. 고정 조건 p=q, q=1−p를 풀면 유일한 고정점은 (1/2,1/2)입니다. 하지만 (1,1)에서 시작하면

$$(1,1)\to(1,0)\to(0,0)\to(0,1)\to(1,1)\to\cdots$$

의 4주기입니다. Brouwer의 가정을 모두 만족해도 이 반복은 수렴하지 않습니다. 고정점이 존재한다고 이 궤적을 끌어당기지는 않습니다. Q는 보조 사상이며 정규화 Nash 사상이 아닙니다. 이 대립 게임에서는 중심이 Nash와 일치하지만 게임을 바꾸면 그 관계가 깨질 수 있습니다.

0..3 상태의 평균은 (1/2,1/2)로 이 게임의 Nash이지만 마지막 꼭짓점은 아닙니다. 임의의 게임 궤적 평균이 일반적으로 Nash가 된다는 정리가 아닙니다.

최적 반응의 선택이 혼합 고정점을 버릴 수 있다

사상 1은 각자가 가장 좋은 순수 행동을 동시에 선택하며 동률에는 행동 0을 고릅니다. 대립 게임 (1/2,1/2)에서는 둘 다 무차별이므로 다음 선택은 (1,1)입니다. 진짜 혼합 Nash가 이 단일값 선택에서는 고정점이 아닙니다.

전체 최적 반응 대응에는 평형 혼합 전략이 그대로 들어 있습니다. 순수 반응 하나를 선택한 함수는 다른 대상입니다. 여러 게임에서 이 함수는 무차별 경계에서 불연속이므로 Brouwer를 바로 적용할 수 없습니다. 사회적 딜레마와 모두 무차별인 게임에서는 여기의 선택이 상수여서 연속입니다. 모든 최적 반응 선택이 반드시 불연속이라는 주장도 피해야 합니다.

이 순수 선택 사상의 고정점이면 순수 Nash이지만 임의의 혼합 Nash에 대한 역은 거짓입니다. 모형은 선택 사상의 전체 고정 집합을 따로 열거하며 전체 Nash 집합과 같다고 가정하지 않습니다.

수축해도 잘못된 목표로 갈 수 있다

보조 수축 사상을 다음처럼 정의합니다.

$$C_\lambda(z)=c+\lambda(z-c),\qquad c=(1/2,1/2),\quad0\le\lambda\le1.$$

닫힌 정사각형에서 Lipschitz 상수는 λ입니다. λ<1이면 완비 거리 공간과 엄격 수축 조건으로 유일한 고정점 c와 기하 수렴을 얻습니다.

$$\|z_T-c\|=\lambda^T\|z_0-c\|.$$

이것은 C_λ의 수렴 보장입니다. Nash에 대해서는 별도 논증이 필요합니다. 조정 게임의 중심에서 현재 보수는 각각 3/4, 가장 좋은 일방 보수는 1이어서 개선 가능량은 각각 1/4입니다. 보조 수축은 그 점을 정확히 고정하지만 Nash 사상은 (3/5,3/5)로 보냅니다. 상대를 고정한 Nash 사상의 일방 개선량은 각각 1/20입니다.

보조 수축을 꼭짓점에서 시작해도 같은 비평형 목표로 실제 수렴합니다. 게임을 대립형으로 바꾸면 같은 중심이 Nash가 됩니다. 기하 수렴 공식이 어느 게임을 올바르게 풀었는지 결정하지는 않습니다.

λ=1에서는 항등 사상이고 정사각형 전체가 고정됩니다. 엄격 수축이나 중심의 유일성을 주장할 수 없습니다. λ<1일 때는 다음 잔차 변환도 성립합니다.

$$\|z-c\|=\frac{\|C_\lambda(z)-z\|}{1-\lambda}.$$

λ가 1에 가까우면 작은 이동량과 상당한 거리가 공존할 수 있습니다. λ=1에서는 나눗셈 자체가 불가능합니다. c가 게임의 잘못된 해라면 c까지의 정확한 거리 보장도 그 오류를 고치지는 못합니다.

존재 가정이 빠지면 무엇이 달라지는가

다음은 유한 혼합 게임 정리를 반박하는 사례가 아니라 별도의 수학 문제입니다.

• 콤팩트성을 빼고 열린 구간 (0,1)에서 한 참가자가 u(x)=x를 최대화하게 합시다. 모든 가능한 x에 대해 (1+x)/2가 구간 안에서 더 좋습니다. 1에 접근하는 수열이 있어도 상한을 달성하지 못해 최대점이 없습니다.
• 볼록성을 빼면 콤팩트 집합 {0,1}의 T(x)=1−x는 상대 위상에서 연속인 자기 사상이지만 고정점이 없습니다. 혼합 확장 [0,1]에는 1/2가 있습니다. 대립 게임도 순수 프로필에는 Nash가 없지만 혼합 영역에는 존재합니다.
• 연속성을 빼고 [0,1]에서 x<1이면 T(x)=1, x=1이면 T(x)=0으로 정의합시다. 두 경우 모두 출력이 입력과 달라 고정점이 없습니다. 콤팩트 볼록 영역과 자기 사상 성질만으로는 충분하지 않습니다.
• 자기 사상을 빼고 T(x)=x+δ, δ>0으로 두면 끝점 1이 [0,1] 밖으로 갑니다. Brouwer의 가정을 만족하지 않습니다.

수치 표본은 이 사례들을 보여 줄 수 있습니다. 그러나 보편적인 비존재 결론은 유한 격자에서 못 찾았다는 사실이 아니라 위의 경우별 논증에서 나옵니다.

잔차와 평균의 단위를 읽는다

아래 그림은 현재 전략과 접두 평균의 최대 일방 개선량을 비교하며 둘 다 게임의 보수 단위입니다. 사상 이동 잔차는 확률 단위의 다른 양이므로 표와 사상 패널에 별도로 표시합니다.

모든 일방 개선량이 ε 이하이면 ε-Nash입니다. 초기 입력의 정수 계산으로 이 정의를 직접 확인할 수 있습니다. 작은 Nash 사상 이동 잔차를 ε-Nash 인증으로 쓰려면 정량적 변환을 먼저 증명해야 합니다. 두 값을 모두 ‘작다’고 부른다고 변환이 성립하지는 않습니다.

T>0 평균은 0..T−1 상태를 사용하고 마지막 T 상태를 제외합니다. T=0에는 평균이나 조회 전이가 없고 초기 상태는 남습니다. 조회는 T−1로 제한되며 관찰만 바꿉니다. λ는 보조 수축에만 영향을 줍니다. 다른 사상의 동역학을 표시용 입력이 바꾸지 않습니다.

연습 문제와 해설

1. 조정 게임의 Nash를 모두 쓰세요. 두 순수 조정 꼭짓점 (0,0),(1,1)과 혼합점 (1/3,1/3)입니다. 존재 정리가 하나를 골라 주거나 유일성을 뜻하지 않습니다.
2. 조정 게임 (1/2,1/2)의 Nash 사상을 구하세요. 행동 0의 양의 개선량은 1/4, 행동 1의 양의 개선량은 0이므로 새 확률은 (1/2+1/4)/(1+1/4)=3/5입니다. 중심을 고정하는 보조 사상은 다른 사상입니다.
3. λ=1/2, 초기 (1,1)에서 여덟 번 보조 수축을 적용하면 어디로 가나요? 각 좌표는 1/2+(1/2)^9=257/512입니다. 같은 점이 한 게임에서는 올바른 중심에 가깝고 다른 게임에서는 잘못된 중심에 가까울 수 있습니다.
4. 순수 선택이 혼합 Nash에서 떠나면 존재 정리가 틀렸나요? 아닙니다. 그 선택에서의 고정성이 틀렸을 뿐입니다. 정규화 양의 이득 사상은 정확한 혼합 고정점을 보존하고 필요한 연속성도 갖습니다.

AI 연구에서 구분을 사용한다

먼저 해의 개념과 가정을 명시하세요. 이어서 알고리즘의 목표가 그 문제를 푸는지 증명하고, 반복 생성 방식과 정지 지표를 설명해야 합니다. 존재·유일성·근사 정확도·수렴 속도·계산 비용에는 서로 다른 근거가 필요합니다.

이 실습은 작은 명시적 집합을 완전히 표현하고 제어한 유리수 프로필을 검사합니다. 일반 대규모 Nash solver나 Sperner 알고리즘을 구현한 것도, 모든 학습 규칙의 수렴을 증명한 것도 아닙니다. 다음 영역에서는 같은 구분을 프라이버시·공정성·강건성과 물리 모델링에 적용합니다.