이 단원 목차
어떤 변경에 대해 안정적인 선택인가?
Nash equilibrium은 다른 사람의 전략을 그대로 둘 때 혼자 전략을 바꿔 보수를 높일 수 없는 전략 조합입니다. 한 사람이 상대의 행동까지 새로 정하는 변경은 허용하지 않습니다. 두 사람이 공동 점수를 최대화해야 한다는 조건도 아닙니다. 두 플레이어가 각각 두 행동을 갖는 작은 게임에서도 이 구분이 중요합니다.
P1이 행동 0을 고를 확률을 p, P2의 확률을 q라고 놓습니다. 두 사람은 독립적으로 혼합합니다. A와 B는 각자의 보수 행렬이고 P1의 행동이 행, P2의 행동이 열입니다. 현재 보수는 앞 단원에서 계산한 쌍선형 기대값입니다.
MIT Nash Equilibrium 강의노트 6.1·6.3절은 상호 최적 반응과 혼합 균형의 지원 집합 조건을 설명합니다. 아래 예제와 정확한 집합 구성, 이탈 조작은 교재의 유한 교육 모형을 위해 구성했습니다.
먼저 최적 반응을 정의하기
상대의 q를 고정하면 P1의 두 순수 행동 보수는 다음과 같습니다.
상대의 p를 고정하면 P2는 다음 두 값을 비교합니다.
r0이 더 크면 P1의 최적 반응은 p=1, r1이 더 크면 p=0입니다. 두 값이 같으면 모든 혼합이 최적 반응입니다. P2도 같은 방식으로 q를 정합니다. 특정 상대 전략에 대한 최적 반응과 모든 상대 전략에서 최적인 우월전략은 다릅니다.
첫 그림의 가로축은 p, 세로축은 q입니다. 파란 실선은 P1의 최적 반응 대응, 주황 점선은 P2의 최적 반응 대응입니다. 동률에서 임의의 행동 하나를 고르지 않고 가능한 전체 집합을 남깁니다. 굵은 검정 점·선·테두리 영역은 두 조건의 교집합인 전체 Nash 집합입니다. 마름모는 현재 조회점입니다.
왜 두 순수 이탈만 확인해도 충분할까?
q를 고정하고 P1의 혼합을 p'로 바꾸면 자신의 보수는 다음과 같습니다.
두 숫자의 볼록 조합이므로 그 최댓값은 두 숫자 중 큰 값입니다. 어떤 혼합도 더 좋은 순수 이탈보다 높은 보수를 주지 못합니다. P2에게도 같고, 순수 행동이 유한하게 여러 개여도 자신의 분포에 대한 기대 보수가 아핀이라는 논리를 쓸 수 있습니다.
전략 공간은 연속이지만 이 성질 때문에 유한한 검사가 가능합니다. 상대를 고정한 독립 혼합의 기대 효용이라는 가정이 중요합니다. 상관 장치의 개인 추천을 받은 뒤 유인을 검사하는 문제를 그대로 대신하는 것은 아닙니다.
최대 일방 이득은 현재 전략의 인증이다
각자의 최대 개선량을 정의합니다.
현재 전략도 가능한 선택이므로 이득은 음수가 아닙니다. 두 값이 모두 0일 때 정확히 Nash입니다. 조작 영역에서 제안한 변경은 가능한 변경 하나에 불과합니다. 그 제안이 손해라고 해서 다른 개선도 없다고 결론 내릴 수는 없습니다. 최대 이득은 모든 순수 행동을 비교하므로 모든 혼합 이탈까지 포함합니다.
조회 확률은 n/12입니다. 보수가 정수여서 현재 기대 보수와 이득을 공통 분모 144의 정수 분자로 계산합니다. 이득이 0인지는 분자가 0인지 정확히 확인합니다. 부동소수점 허용오차를 등식의 증명으로 대체하지 않습니다. 읽기용 숫자는 반올림하지만 분자도 따로 제공합니다.
지원하는 행동은 모두 최적이어야 한다
균형에서는 양의 확률을 주는 모든 순수 행동이 최적 반응이어야 합니다. 더 나쁜 행동에 양의 질량이 있다면 그 일부를 더 좋은 행동으로 옮겨 기대 보수를 높일 수 있어 균형에 모순입니다. 반대로 최적 행동들 사이에서만 혼합하면 보수는 같은 최댓값이므로 최적 반응입니다.
두 행동을 모두 양의 확률로 사용하면 두 순수 행동 보수가 같아야 합니다. 이것은 무차별 조건이며 두 확률이 반드시 0.5라는 뜻은 아닙니다. 한 사람의 혼합이 상대를 무차별하게 만드는 경우가 많습니다. 올바른 보수 행렬의 방정식을 풀고 확률 범위와 지원 조건을 함께 검사해야 합니다.
손계산: 조정 게임의 세 균형
조정 게임의 A=B는 행 우선 순서로 (2,0,0,1)입니다. P1의 순수 보수 2q와 1−q가 같아지는 지점은 q=1/3입니다. P2도 p=1/3에서 무차별입니다. 따라서 완전 혼합 균형은 다음과 같습니다.
각자의 보수는 2/3입니다. 상대를 1/3 혼합에 고정하면 자신만 혼합을 바꿔도 보수가 그대로 2/3입니다. 첫 예제의 입력 분자는 4와 4이므로 4/12를 사용해 정확히 이 점을 조회합니다.
순수 균형 (0,0),(1,1)도 있으며 보수는 각각 (1,1),(2,2)입니다. 그림은 세 점을 모두 표시합니다. 낮은 보수의 순수 균형도 Nash입니다. 혼자만 행동을 바꿔 상대의 행동까지 함께 좋은 대각으로 옮길 수 없기 때문입니다. 균형이 여러 개면 조건을 푸는 것만으로 하나의 예측이 선택되는 것도 아닙니다.
손계산: 공동 효율과 다른 균형
사회적 딜레마의 보수 쌍은 (3,3),(0,5),(5,0),(1,1)입니다. p=q=0이면 둘 다 행동 1을 선택해 1을 받습니다. 한 사람만 행동 0으로 바꾸면 0을 받으므로 두 최대 이득이 0입니다.
둘이 함께 행동 0으로 바꾸면 보수는 (3,3)입니다. 이런 공동 개선이 원래 Nash를 무효로 만들지는 않습니다. 반면 p=q=1에서는 한 사람만 행동 1로 바꿔 3 대신 5를 받을 수 있습니다. 일방 이득이 2이므로 이 공동 협력점은 Nash가 아닙니다. 균형, 공동 효율, 한 사람의 변경 유인은 다른 질문입니다.
두 번째 그림의 제안 네모는 선택한 한 사람만 바꿉니다. 현재 점과 두 순수 이탈 표식은 같은 보수 축척으로 비교합니다. 아래 두 곡선도 각자 자신의 혼합만 따로 바꾸며, 두 사람이 동시에 움직이는 공동 변경 경로가 아닙니다.
손계산: 순수 균형이 없는 상반 보수 게임
상반 보수 게임에서 행동이 같으면 P1은 1, 다르면 −1을 받고 P2는 그 음수를 받습니다. 모든 순수 전략 쌍에서 한 사람은 바꾸고 싶어 합니다. 순수 균형은 없지만 p=q=1/2이면 두 사람이 모두 무차별입니다. 혼합 균형은 (1/2,1/2) 한 점입니다.
순수 균형이 없다는 것과 균형이 없다는 것은 다릅니다. 모든 유한 정규형 게임에는 혼합전략 Nash equilibrium이 존재합니다. 이는 선택한 학습 알고리즘이 거기에 도달한다거나 해가 유일하다거나 계산이 언제나 쉽다는 뜻이 아닙니다. 이 실습은 구분을 보여주는 유한 예제이며 일반 존재 정리의 증명 자체는 아닙니다.
퇴화: 균형이 선분 전체가 될 때
게임 3에서는 P1의 보수가 언제나 0이고 P2는 조정 게임 보수를 갖습니다. P1은 모든 곳에서 무차별입니다. P2는 p<1/3이면 q=0, p>1/3이면 q=1, p=1/3이면 모든 q를 최적 반응으로 가집니다. 전체 Nash 집합은 다음 합집합입니다.
세 번째 예제는 수직 선분 위의 p=4/12, q=7/12를 조회합니다. (1/3,1/3)만 반환하면 무한히 많은 다른 균형을 누락합니다. 게임 4에서는 두 플레이어가 어디서나 무차별이어서 단위 정사각형 전체가 균형입니다. 임의로 한 해를 특별 취급하지 않고 영역을 표시합니다.
연속적인 전체 균형 집합을 정확히 구성하기
두 행동의 순수 보수 차이는 상대 확률의 아핀 함수입니다. 유리수 영점을 구해 해당 축을 경계의 단일점과 열린 구간으로 나눕니다. P2의 무차별 영점으로 p축을, P1의 무차별 영점으로 q축을 나눕니다. 각 곱 구간에서는 보수 차이의 부호가 일정하고 자신의 혼합이 경계인지 내부인지도 일정하므로 최적 반응 조건의 참·거짓이 일정합니다.
두 조건을 만족하는 부분을 남깁니다. 두 최대 일방 이득 함수가 연속이므로 남긴 부분의 폐포도 조건을 만족합니다. 더 큰 반환 사각형에 포함된 중복 부분을 제거하면 점·선분·사각형의 합집합으로 나타낼 수 있습니다. n/12 격자만 뒤져 찾은 점들이 아니라 연속 집합이며, 표에는 정확한 유리수 끝점을 남깁니다.
이 구성은 정수 보수가 유계인 두 플레이어·두 행동 게임의 구조를 사용합니다. 모든 큰 다중 플레이어 게임을 푼다는 주장은 아닙니다. 독립 검사에서는 퇴화 게임과 조회 격자 밖 유리수 점도 포함해 반환 영역의 소속과 순수 이탈 부등식을 직접 비교합니다.
연습 문제와 해설
문제 1: 조정 게임에서 p=q=1/2는 균형인가요? 유리한 순수 이탈과 최대 이득을 구하세요.
해설: 각 현재 보수는 0.75입니다. 상대 q=1/2에 대해 행동 0은 1, 행동 1은 0.5를 줍니다. P1이 행동 0을 확실히 고르면 0.25를 개선하고 P2도 같습니다. 두 사람이 같은 확률로 혼합한다는 사실이 균형 검사는 아닙니다.
문제 2: 사회적 딜레마에서 상대를 행동 1에 고정하고 행동 0을 제안했습니다. 제안의 보수 변화가 음수면 어떤 현재 전략에서도 균형이라고 결론 내릴 수 있나요?
해설: 아닙니다. 특정 제안 하나가 나쁘다는 사실만 알 수 있습니다. 균형을 인증하려면 현재 보수를 두 순수 보수의 최댓값과 비교해야 합니다. 더 나쁜 행동에 양의 질량을 준 현재 혼합은 다른 제안이 더 나쁘더라도 최적이 아닙니다.
문제 3: P1이 항상 무차별인 게임에서 p=1/3인 균형들을 적어 보세요. 두 사람이 모두 항상 무차별이면 균형은 몇 개인가요?
해설: 게임 3에서 p=1/3이면 [0,1]의 모든 q가 균형입니다. 게임 4에서는 단위 정사각형의 모든 (p,q)가 균형이며 비가산 연속체입니다. 화면의 사각형 개수는 집합 표현의 기하학적 구성요소 수이고 균형 전략 쌍의 개수가 아닙니다.
설명할 수 있나요?
실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.
선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.