해적 게임

Pirate game
기타 용도는 해적(동음이의) § 게임 및 장난감을 참조하십시오.

해적 게임은 간단한 수학 게임이다. 최후통첩 게임의 멀티 플레이어 버전이다.

게임

금화 100개를 발견한 이성적 해적 5명(연령 A, B, C, D, E)이 있다. 그들은 그것들을 어떻게 분배할지 결정해야 한다.

해적세계의 유통규칙은 가장 선배 해적이 먼저 유통계획을 제안한다고 한다. 그런 다음 제안자를 포함한 해적들은 이 배포를 받아들일지 여부를 투표한다. 대다수가 이 계획을 받아들이면 동전이 분산되고 게임은 끝난다. 동수일 경우 제안자가 캐스팅보트를 쥐고 있다. 대다수가 이 계획을 거부하면 제안자는 해적선에서 배 밖으로 던져져 죽게 되고, 다음으로 선임된 해적이 다시 제도를 시작하자는 새로운 제안을 하게 된다. 계획이 받아들여지거나 해적이 한 명 남아 있을 때까지 그 과정이 반복된다.[1]

해적들은 네 가지 요인에 근거하여 결정을 내린다. 우선, 각각의 해적들은 살아남기를 원한다. 둘째, 생존을 고려해 볼 때, 각 해적들은 그가 받는 금화의 수를 최대화하기를 원한다. 셋째, 만약 다른 모든 결과가 같다면, 각 해적들은 또 다른 배 밖으로 던지는 것을 선호할 것이다.[2] 그리고 마지막으로 해적들은 서로를 신뢰하지 않으며, 각 해적에게 금화를 전량 주는 제안된 유통 계획 외에 해적들 사이의 어떤 약속도 지키지 않을 것이다.

결과

그의 계획이 받아들여질 가능성을 높이기 위해서, 사람들은 해적 A가 다른 해적들에게 대부분의 금을 제공해야만 할 것이라고 예상할 수 있다. 그러나 이는 이론적 결과와 거리가 멀다. 해적들이 투표를 할 때, 그들은 현재 제안만을 생각하는 것이 아니라 다른 결과들도 생각할 것이다. 또한, 연공서열 순서는 미리 알려져 있으므로 각자가 어떤 시나리오에서든 다른 사람들이 어떻게 투표할 수 있는지를 정확하게 예측할 수 있다. 만약 우리가 거꾸로 일한다면 이것은 명백해진다.

마지막 가능한 시나리오는 D와 E를 제외한 모든 해적들을 배 밖으로 던지게 할 것이다. D는 E보다 나이가 많으므로 캐스팅보트를 쥔다. 그래서 D는 자신을 위해 100을, E를 위해 0을 유지하자고 제안할 것이다.

3개(C, D, E)가 남으면 다음 라운드에서 D가 E 0을 제시할 것을 알고 있기 때문에, E의 표를 얻기 위해서는 이번 라운드에서 C가 E에게 1개의 동전을 제시해야 한다. 따라서 3개만 남았을 때 할당은 C:99, D:0, E:1이다.

B, C, D, E가 남으면 B가 1 대 D를 제안할 수 있는데, B가 캐스팅보트를 쥐고 있기 때문에 D의 투표만 하면 된다. 따라서 B는 B:99, C:0, D:1, E:0을 제안한다.

(이전 라운드에서는 B:99, C:0, D:0, E:1을 제안하는 것을 고려할 수 있는데, E가 B를 너무 많이 던지면 더 많은 동전을 구할 수 없을 것이라는 것을 E가 알고 있기 때문이다. 그러나, 각각의 해적들은 다른 해적들을 배 밖으로 던지려고 열심이기 때문에, E는 C로부터 같은 양의 금을 얻기 위해 B를 죽이는 것을 선호한다.)

이러한 지식으로 A는 C와 E의 지원으로 최종 해결책인 다음과 같은 할당을 기대할 수 있다.

  • A: 98개의 동전
  • B: 동전 0개
  • C: 동전 1개
  • D: 동전 0개
  • E: 1코인[2] 1개

(참고: A:98, B:0, C:0, D:1, E:1 또는 다른 변종들은 D가 B로부터 동일한 양의 금을 얻기 위해 A를 배 밖으로 던질 것이기 때문에 충분하지 않다.)

확장

해법은 다른 해적 및/또는 동전의 숫자에 대해서도 동일한 일반적인 패턴을 따른다. 하지만 게임은 동전이 있는 것보다 해적 수가 두 배나 더 많은 것을 넘어 연장될 때 성격이 변한다. 이언 스튜어트는 1999년 5월 사이언티픽 아메리칸 판에서 스티브 오모훈드로의 임의적인 해적 수 확장에 대해 썼으며, 해결책에서 나타나는 다소 복잡한 패턴에 대해 설명했다.[2]

100개의 금 조각이 있다고 가정할 때:

  • 해적 #201 선장으로서 가장 낮은 홀수 해적에게 금 한 자루씩을 모두 바쳐야만 생존이 가능하다.
  • #202 해적 #202 선장은 금을 가져가지 않고 #201로부터 금화를 받지 못하는 100명의 해적에게 각각 금을 하나씩 바쳐야 생존이 가능하다. 따라서, 이 금화 뇌물 한 건에 대해 최고 200명, 최고 201명의 짝수 해적 100명이 받을 수 있는 101명이 있다. 이 101개 중 어떤 100개를 선택할 것인지에 대한 제약이 없기 때문에, 어떤 선택이든 똑같이 좋고 그는 무작위로 선택하는 것으로 생각할 수 있다. 이렇게 해서 숫자가 더 많은 해적들에게 기회가 고려되기 시작한다.
  • Pirate #203 as captain will not have enough gold available to bribe a majority, and so will die.
  • Pirate #204 as captain has #203's vote secured without bribes: #203 will only survive if #204 also survives. So #204 can remain safe by reaching 102 votes by bribing 100 pirates with one gold coin each. This seems most likely to work by bribing odd-numbered pirates optionally including #202, who will get nothing from #203. However, it may also be possible to bribe others instead as they only have a 100/101 chance of being offered a gold coin by pirate #202.
  • With 205 pirates, all pirates bar #205 prefer to kill #205 unless given gold, so #205 is doomed as captain.
  • Similarly with 206 or 207 pirates, only votes of #205 to #206/7 are secured without gold which is insufficient votes, so #206 and #207 are also doomed.
  • For 208 pirates, the votes of self-preservation from #205, #206, and #207 without any gold are enough to allow #208 to reach 104 votes and survive.

In general, if G is the number of gold pieces and N (> 2G) is the number of pirates, then

  • All pirates whose number is less than or equal to 2G + M will survive, where M is the highest power of 2 that does not exceed N – 2G.
  • Any pirates whose number exceeds 2G + M will die.
  • Any pirate whose number is greater than 2G + M/2 will receive no gold.
  • There is no unique solution as to who gets one gold coin and who does not if the number of pirates is 2G+2 or greater. A simple solution dishes out one gold to the odd or even pirates up to 2G depending whether M is an even or odd power of 2.

Another way to see this is to realize that every pirate M will have the vote of all the pirates from M/2 + 1 to M out of self preservation since their survival is secured only with the survival of the pirate M. Because the highest ranking pirate can break the tie, the captain only needs the votes of half of the pirates over 2G, which only happens each time (2G + a Power of 2) is reached. For instance, with 100 gold pieces and 500 pirates, pirates #500 through #457 die, and then #456 survives (as 456 = 200 + 28) as he has the 128 guaranteed self-preservation votes of pirates #329 through #456, plus 100 votes from the pirates he bribes, making up the 228 votes that he needs. The numbers of pirates past #200 who can guarantee their survival as captain with 100 gold pieces are #201, #202, #204, #208, #216, #232, #264, #328, #456, #712, etc.: they are separated by longer and longer strings of pirates who are doomed no matter what division they propose.

참고 항목

메모들

  1. ^ Bruce Talbot Coram (1998). Robert E. Goodin (ed.). The Theory of Institutional Design (Paperback ed.). Cambridge University Press. pp. 99–100. ISBN 978-0-521-63643-8.
  2. ^ a b c Stewart, Ian (May 1999), "A Puzzle for Pirates" (PDF), Scientific American, pp. 98–99

참조

  • Robert E. Goodin, ed. (1998). "Chapter 3: Second best theories". The Theory of Institutional Design. Cambridge University Press. pp. 90–102. ISBN 978-0-521-63643-8.