1. 개요
Colonel Blotto game. 혹은 'divide a dollar'게임 등으로도 불린다. 죄수의 딜레마와 더불어 게임 이론에서의 주요 문제 중 하나이다.1921년에 에밀 보렐에 의해 처음 제시되었으며 이 때 '경기자의 심리가 중요한 게임'의 예시로 나왔다. 1950년 Gross와 Wagner가 '블로토 대령 게임'[1]이라는 이름을 붙여 현재까지 이어져 오고 있다.
당시에는 주요 수학자들이 한번씩은 손대본 문제이지만 현재는 게임이론 초창기와 비교하면 더 적게 연구되고 있다. 그 이유 중 하나는 해답이 깔끔하게 제시되지 못한다는 점을 들 수 있을 것이다.[2][3]
2. 상세
여러 변형을 가할 수 있지만, 대표적인 게임의 형태는 다음과 같은 2인 제로섬 게임이다.- 블로토 대령은 N명의 군대를 가지고 있으며, M개의 전장에 군대를 배치해야 한다.
- 적 또한 N명의 군대를 가지고 있으며 M개의 전장에 군대를 배치한다.
- 군대를 더 많이 투입한 측이 승리하며, 똑같은 숫자를 투입할 경우 비긴다.
- 최대한 많은 전장에서 승리를 거두는 것이 목표이다.
구체적 수치를 들어보자. 두 경기자는 5개의 전장에 20명의 병사를 배치한다고 했을때, 한쪽이
(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)은 (9,8,1,1,1)에 (패,패,승,패,패)로 패배한다.
(9,8,1,1,1)은 (4,4,4,4,4)에 (승,승,패,패,패)로 패배하면서 처음으로 돌아가게 된다.
이 다섯을 모두 대결시켜보자면 (0,0,7,7,6)은 (1,1,9,9,0)을 제외한 나머지를 다 이기므로 최강, (4,4,4,4,4)는 (1,1,9,9,0)을 제외한 나머지에게 모두 지므로 최약체다. (7,7,6,0,0)은 (0,0,7,7,6)에게 지고 (1,1,9,9,0)과 비기며 나머지를 모두 이기므로 2승 1무 1패, (1,1,9,9,0)은 (0,0,7,7,6)을 이기고 (7,7,6,0,0)과 비기며 나머지에게 모두 지므로 1승 1무 2패이다. (5,5,5,3,2)는 (1,1,9,9,0)을 이기고 (0,0,7,7,6)에게 져서 2승 2패를 달성했다.
이렇게 상대보다 단 한 명만 더 보내도 그 전장을 이길 수 있기 때문에, 순수 전략 내시균형이 존재하지 않는다. 참고로 만약 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명씩 배치한 사람들에 대해 이길 수 있을 것이다.
처음에 나는 두 곳에서 항복하지만, 쉽게 내주지 않으려 했다. 나와 같은 생각을 한 사람들이 있을 것이라 봤으며 그들에게 이기기 위해 2명씩을 배치했다. 내가 불리한 전장은 양쪽 끝 번호일 것으로 예상했다. 나머지 116명의 병력을 나머지 4개 전장에 배치하면 평균적으로 29명이 된다. 이 중 세개의 전장을 아까와 같이 2명씩 추가적으로 배치하면서 31명씩 배치하게 되었다. 이는 중앙의 전장에 똑같이 30명씩 배치한 사람들에 대해 이길 수 있을 것이다.
4. 관련 문서
- 게임 이론
- 삼사법 -. 손빈이 전차 경주에서 제안한 삼사법을 블로토 대령 게임으로 치환하면 M=3, N=6인 상황에서 모든 플레이어는 전장에 반드시 (1 -> 하등 수레, 2 -> 중등 수레, 3 -> 상등 수레)을 배치하는 제한이 걸려있다고 볼 수 있다.
[1] Colonel은 대령, Lt. Colonel은 중령이다.[2] 특정 형태의 게임, 예를 들어 상대와 나의 병력 수가 같다거나 전장의 숫자가 정해져 있거나 단 한번의 게임 결과에 모든 것이 달리지 않는 등의 게임들에 대해서는 여러 해답들이 제시되어 있다. 그러나 일반화된, 즉 이런 제약이 최소화된 형태의 게임에 대해서는 2015년 현재까지도 아직 큰 발전이 없다.[3] 당장 아래 논문에서 가장 좋은 전략이라 생각된 (2, 31, 31, 31, 23, 2)의 경우도 당연히 100% 이기는 건 아니다. 만약 상대가 양 끝과 하나의 전장에 논개를 이길 만한 전력만 배치하고 3개의 전장에 나머지 전력을 균등하게 몰아넣은 (5, 35, 5, 35, 35, 5)와 같이 나와버린다면 1승 5패로 처참하게 패배한다. 왜냐하면 (2, 31, 31, 31, 23, 2)을 생각한 사람은 대부분의 사람들이 많아봐야 2개의 전장에서만 패배를 감수할 것으로 예상했을 뿐, 설마 미쳤다고 3개 전장의 패배를 감수할 것이라고 생각하지 않았기 때문.[4] 상술된 논문에서 제시된 M=6, N=120 게임의 (2,31,31,31,23,2) 작전은 양 끝을 버리되, 상대가 0이나 1로 완전히 버리는 경우에는 잡아먹을 수 있는 2를 배치하여 상대의 논개작전을 받아치는 것을 고려했고, 유력한 전장인 3곳은 남은 116의 평균인 29보다 2 높은 31을 배치하였다. 수열 조합으로도 120의 평균인 20보다 4개의 수가 높으므로 고르게 균등한 전력을 배치할 경우 3개의 전장에선 확실히 이기고 23에서도 무승부가 날 확률이 높다.