블로토 대령 게임
1. 개요
Colonel Blotto game. 혹은 'divide a dollar'게임 등으로도 불린다. 죄수의 딜레마와 더불어 게임 이론에서의 주요 문제 중 하나이다.
1921년에 에밀 보렐에 의해 처음 제시되었으며 이 때 '경기자의 심리가 중요한 게임'의 예시로 나왔다. 1950년 Gross와 Wagner가 '블로토 대령 게임'[1]이라는 이름을 붙여 현재까지 이어져 오고 있다.
당시에는 주요 수학자들이 한번씩은 손대본 문제이지만 현재는 게임이론 초창기와 비교하면 더 적게 연구되고 있다. 그 이유 중 하나는 해답이 깔끔하게 제시되지 못한다는 점을 들 수 있을 것이다.[2]
2. 상세
여러 변형을 가할 수 있지만, 대표적인 게임의 형태는 다음과 같은 2인 제로섬 게임이다.
- 블로토 대령은 N명의 군대를 가지고 있으며, M개의 전장에 군대를 배치해야 한다.
- 적 또한 N명의 군대를 가지고 있으며 M개의 전장에 군대를 배치한다.
- 군대를 더 많이 투입한 측이 승리하며, 똑같은 숫자를 투입할 경우 비긴다.
- 최대한 많은 전장에서 승리를 거두는 것이 목표이다.
(4,4,4,4,4)를 배치한다면 (5,5,5,3,2)에 (패,패,패,승,승)으로 패배한다.
(5,5,5,3,2)는 (7,7,6,0,0)에 (패,패,패,승,승)으로 패배한다.
(7,7,6,0,0)은 (0,0,7,7,6)에 (승,승,패,패,패)로 패배한다.
(0,0,7,7,6)은 (1,1,9,9,0)에 (패,패,패,패,승)으로 패배한다.
(1,1,9,9,0)은 (4,4,4,4,4)에 (패,패,승,승,패)로 패배하면서 처음으로 돌아가게 된다.
이렇게 상대보다 단 한 명만 더 보내도 그 전장을 이길 수 있기 때문에, 순수 전략 내쉬균형이 존재하지 않는다. 참고로 만약 N=M일 경우, 각 전장에 1명씩의 군인을 배치하면 절대 지지 않는다. 이기거나 최소한 비기게 된다.
3. 기타
Arad와 Rubinstein의 논문 'Colonel Blotto’s Top Secret Files'에서 이들은 총 6500명에 달하는 다양한 두 집단을 대상으로 6개의 전장에 120명의 병사를 배치하는 (M=6,N=120) 방식의 게임을 가지고 실험을 했으며, 그 결과 (2,31,31,31,23,2)가 가장 성공적인 전략이었던 것으로 나타났다.
여기에서 이 전략을 세운 사람은 이렇게 배치한 이유를 다음과 같이 말했다.
"In the first stage, I decided that I would "surrender" on two fronts, but not so easily. I thought that other people would decide to assign a few battalions to some of the fronts and perhaps would not deploy any battalions to other fronts. So I could win on an "abandoned" front at the inexpensive price of one battalion. Eventually, I decided to deploy two battalions on the weak fronts in order to overpower anyone who thought like me and placed one battalion on the weak fronts. It seems logical to me that the weak fronts would be on the edges. I was left with 116 battalions to allocate to four fronts, which is an average of 29 battalions per front. I decided to reinforce three of the four remaining fronts with two battalions - that is, to deploy 31 battalions - in order to defeat those who allocated the remaining battalions equally. In this way, I would also defeat those who allocated 30 battalions to each of the four central fronts."
처음에 나는 두 곳에서 항복하지만, 쉽게 내주지 않으려 했다. 나와 같은 생각을 한 사람들이 있을 것이라 봤으며 그들에게 이기기 위해 2명씩을 배치했다. 내가 불리한 전장은 양쪽 끝 번호일 것으로 예상했다. 나머지 116명의 병력을 나머지 4개 전장에 배치하면 평균적으로 29명이 된다. 이 중 세개의 전장을 아까와 같이 2명씩 추가적으로 배치하면서 31명씩 배치하게 되었다. 이는 중앙의 전장에 똑같이 30명씩 배치한 사람들에 대해 이길 수 있을 것이다.