수학의 기초와 응용 VII
부산가톨릭대학교 컴퓨터공학과
변 상 선
N인 게임
• 실제 상황에서 게임에 참여하는 플레이어의 수는 4명 이상인 경우 가 다반사
• 하지만, 복잡도가 매우 증가
• 10명의 플레이어를 가정하고, 각 플레이어의 전략이 2가지라면 2 10
개의 전략 조합이 발생
줄서기 게임
• 6명의 탑승객이 탑승구 앞에서 체크인을 기다리고 있음
• 다들 의자에 앉아서 기다리다가, 갑자기 1명이 일어나서 아직 체크인 담당 직원이 오지도 않았는데, 탑승구 맨 앞에서 서서 기다리기 시작 했음
• 따라서, 다른 승객들도 뒤늦게 체크인 하기 싫어서 이 승객을 따라 불 필요하게 줄을 서게 됨
• 총이득 => 줄을 서지 않았을 때의 이득
• 순이득 => 총이득 - 2 => 줄을 서는 노력에 의해 2 차감
줄서기 게임
Order served Gross Payoff Net Payoff
First 20 18
Second 17 15
Third 14 12
Fourth 11 9
Fifth 8 6
Sixth 5 3
줄서기 게임
• 줄을 서지 않은 사람은 임의의 순서로 체크인 함
• 2명이 줄을 섰으면 나머지 4명은 1/4의 확률로 3~6번째에 위치함
• 아무도 줄을 서지 않으면, 모든 위치에 들어갈 확률이 동일하므로 기대이득은
• (1/6) * 20 + (1/6) * 17 + … + (1/6) * 5 = 12.5
• 총 이득은 12.5 * 6 = 75
• 이 게임에서 내시 균형은 무엇인가?
줄서기 게임
• 모두 앉아서 기다린다
• 첫 번째로 서서 기다리면 이득이 18이 되므로 기대이득 (12.5)보다 크다
• 따라서, 모두 앉아서 기다리는 것은 내시균형이 아님
• 독자적 전략 변경 (앉아서 기다린다 => 줄을 선다) 으로 자신의 이득을 증가 (12.5 => 18) 시킬 수 있다
• 1사람만 줄을 서고 나머지는 기다린다
• 나머지 승객들의 기대이득은
• (1/5)*17 + (1/5)*14 + … + (1/5)*5 = 11
• 두 번째로 서서 기다리면 이득이 15가 되므로 기대이득 (11) 보다 크다
• 따라서, 1사람만 줄을서서 기다린다도 내시균형이 아님
줄서기 게임
• 2사람이 줄을 서고 나머지는 기다린다
• 나머지 승객들의 기대이득은
• (1/4)*14 + (1/4)*11 + (1/4)*8 + (1/4)*5 = 9.5
• 세 번째로 서서 기다리는 것의 이득 (12)가 기대이득 (9.5) 보다 크다
• 따라서, 2사람만 줄을 서서 기다리는 것도 내시균형이 아님
• 3명이 줄을 선다
• 기대이득 = 8, 4번째로 줄을 서서 기다렸을 때 이득 = 9
• 따라서, 3명만 줄을 서는 것도 내시균형이 아님
• 4명이 줄을 선다
• 기대이득 = 6.5, 5번째로 줄을 서서 기다렸을 때 이득 = 6
• 5번째로 줄을 서서 기다리는 것이 손해 => 따라서, 내시균형
• 독자적으로 전략을 바꾸어도 (기다린다 => 줄을선다) 이득에 향상이 없음
줄서기 게임
•
내시균형 분석•
아무도 줄을 서지 않았을 때 (협조해)와 비교•
첫번째 사람의 이득 => 18 - 12.5•
두번째 사람의 이득 => 15 - 12.5•
세번째 사람의 이득 => 12 - 12.5•
네번째 사람의 이득 => 9 - 12.5•
나머지 => 6.5 - 12.5•
결국 줄서기를 함으로써, 처음 두 사람만 이득을보고 나머지는 이득을 보지 못한다N인 게임을 위한 단순화 가정
• 모든 참가자들이 동일하다고 가정 => 모든 참가자들이 대표자라고 가정
• 대표자 (representative agent)
• 모든 플레이어가 같은 전략과 각 전략에 대해 이득이 같다
• 상태변수
• 참가자들의 전략선택에 미치는 대표적인 변수만 주목한다
• 줄서기 게임에서는 현재 줄의 길이, 다른 변수 (누가 첫번째로 줄
을 섰는가? 등)는 주목하지 않음
참가자가 많은 게임: 비율게임
•
참가자가 많은 게임의 해석•
비율을 상태변수로•
통근 게임•
자가용 또는 대중교통을 이용한 통근•
자가용 이용자가 많을 수록 자가용 이용자, 대중교통 이용자의 이득이 모두 낮아짐•
대중교통 이용자가 많을 수록, 자가용 이용자 대중교통 이용자의 이득이 모두 높아 짐•
상태변수 => 자가용 통근자의 비율참가자가 많은 게임: 비율게임
Payoffs
-3 -2.25 -1.5 -0.75 0 0.75 1.5 2.25
Proportion
0 0.25 0.5 0.75 1
Payoff to bus commuters Payoff to car commuters
참가자가 많은 게임: 비율게임
•
자가용을 이용한 통근이 우월전략•
하지만, 모든 통근자가 자가용을 이용하면 -1.5의 이득•
모든 통근자가 대중교통을 이용하면 1의 이득 => 협조해•
즉, 모든 통근자가 -1.5의 손해를 감수하더라도 각 개개인에게는 자가용을 이용한 통근이 이득 => 우월전략 => 내시균형•
사회적 딜레마•
좀더 현실적인 게임•
자가용의 비율이 특정 값을 넘어서면 그 때부터는 대중교통이 오히려 유리참가자가 많은 게임: 비율게임
Payoffs
-3 -2.25 -1.5 -0.75 0 0.75 1.5 2.25
Proportion
0 0.25 0.5 0.75 1
Payoff to bus commuters Payoff to car commuters
자가용의 비율 = 2/3
참가자가 많은 게임: 비율게임
•
자가용 통근자의 비율이 2/3을 넘어서게 되면 대중교통을 이용한 통근이 이득이 더 커짐•
우월전략을 갖지는 않지만, 내시균형을 가짐•
통근자의 2/3가 자가용을 이용하는 것•
2/3인 지점에서 만약 한 사람이 대중교통 => 자가용으로 전략을 수정한다면?•
자가용 운전자 중에 한 사람은 대중교통으로 전략을 바꿈으로서 자신의 이득이 증가 함•
만약 한 사람이 자가용 => 대중교통으로 전략을 수정한다면?•
대중교통 운전자 중에 한 사람은 자가용으로 전략을 바꿈으로서 자신의 이득이 증가•
결과적으로 2/3인 지점에서 전략을 바꾸어도 이득의 증가가 없음공유자원의 비극
•
공유자원•
도로같은 것•
자가용 통근자는 자가용을 사용하는 것이 손해를 가져다 주지 않는한 더 많은 공유자원 (도로) 을 사용함으로써 사적인 이득을 극대화 하려 한다 => 사회적 경제의 필요성Payoffs
-3 -2.25 -1.5 -0.75 0 0.75 1.5 2.25
Proportion
0 0.25 0.5 0.75 1
Payoff to bus commuters Payoff to car commuters
2/3 지점에 도달하기 전까지는 자가용을 운전하 는 것이 유리하므로 공유자원의 과다 사용 유발
공유자원의 비극
•
해결책•
자가용 통근과 대중교통 통근의 이득 역전이 좀더 낮은 자가용 비율에서 나타나도록 조절•
버스전용차로 확대Payoffs
-3 -2.25 -1.5 -0.75 0 0.75 1.5 2.25
Proportion
0 0.25 0.5 0.75 1
Payoff to bus commuters Payoff to car commuters
매와 비둘기 게임의 제고
• 매와 비둘기가 먹이를 두고 경쟁하는 상황
• 게임이론의 생물학으로 적용 => 이득은 금전이나 효용이 아니라 생존 과 번식의 가능성
• 매와 비둘기의 개체군 성장 (번식력)이 이득으로 표현되어야 함
• 기존의 매와 비둘기 게임에서는 새 A, B가 매가 될 지 비둘기가 될지 결정할 수 있다 가정했지만, 실제 상황에서는 새 A, B가 매인지 비둘 기인지 이미 결정이 되어 있고, 무작위로 상대 새가 결정됨
• 즉, 자연을 상대로하는 게임의 형태로 표현
매와 비둘기 게임의 제고
• 자기자신이 대결하게 될 새가 무작위로 결정
• 자기자신이 매일 때 기대이득 => -25p+14(1-p) => -39p+14
• 자기자신이 비둘기일 때 기대이득 => -9p+5(1-p) => -14p+5
대결상대 새
매 비둘기 기대이득
자기 자신 매 -25 14 -25p+14(1-p)
비둘기 -9 5 -9p+5(1-p)
확률 p 1-p
매와 비둘기 게임의 제고
• x 축이 p
• 매와 비둘기의 기대이득을 p에 대한 함수로 표현
• 매의 비율이 35%를 넘어서게 되면 비둘기의 번식력이 더 좋아지고 (매보다) 35% 이하일 때는 매의 번식력이 더 좋음
• 매의 비율이 상태변수
