죄수의 딜레마

죄수의 딜레마(prisoner's dilemma)

죄수의 딜레마(Prisoner's Dilemma)란 협동을 하면 모두에게 이익이 됨에도 불구하고 배반을 선택하게 되는 상황을 말한다. 흔히 '죄수의 딜레마'라고 부르며 용의자의 딜레마, 수인의 번민(囚人의 煩悶) 이라고도 한다. 1950년에 미국 랜드 연구소(RAND Corporation)에서 두 과학자 메릴 플러드(Merrill Flood)와 멜빈 드레셔(Melvin Dresher)가 사람들의 협력과 갈등에 관한 게임 이론에 대해 시행한 연구에서 시작되었다. 이후 랜드 연구소의 고문 앨버트 터커(Albert W. Tucker)가 이 게임이론에 ‘Prisoner's Dilemma’라는 이름을 붙였다.

개요

죄수의 딜레마는 게임 이론의 대표적인 예시 중 하나이다. 논 제로섬 게임(non zero-sum game)의 일종으로, 협력적인 선택이 최선의 선택임에도 불구하고 자신의 이익에 치중한 이기적인 선택을 하여 결국 서로에게 나쁜 결과를 야기하는 현상을 말한다. 경쟁자의 전략에 대응해 최선의 선택을 하면 서로 자신의 선택을 바꾸지 않는 균형 상태를 보이게 된다는 내시균형 이론이나, 어느 한쪽이 양보하지 않을 경우 양쪽 모두 파국으로 치닫게 되는 치킨게임 이론과 함께 다뤄지는 경우가 많다. 미시경제학에서 시작되어 심리학, 생물학, 정치학 등의 다양한 학문에 큰 영향을 끼쳤으며, 서로에게 더 좋은 결과가 있음에도 불구하고 서로에게 더 나쁜 결과로 귀착된다는 점에서 수많은 경제적, 사회적인 현상을 시사하는 대표적인 게임이론이다.

이론 및 예제

앨버트 터커의 예제

죄수의 딜레마(prisoner's dilemma) 예제

앨버트 터커(Albert W. Tucker)는 프린스턴 대학교(Princeton University)의 수학자 출신이다. 그는 랜드 연구소의 고문을 맡아 게임 이론을 설명하는 강연을 진행하면서 처음으로 해당 게임이론에 '죄수의 딜레마'(prisoner's dilemma)라는 이름을 붙였다. 다음은 앨버트 터커가 강연에서 제시한 예제이다.

두 명의 범죄 조직원 C, D가 체포되어 왔다. 이 범죄자들은 각각 독방에 수감되어 서로 교류할 수 없는 상황이다. 경찰은 두 명의 공범을 기소하기 위한 증거가 부족한 상황이다. 이러한 상황에서 경찰은 이들에게 자백을 받아 범죄를 입증할 방법을 세우고, 각 범죄자를 대상으로 신문을 한다. 이때 경찰은 두 공범에게 동일한 제안을 건넨다. 다른 한 명의 공범에 대해 자백을 하면 자백한 그 사람은 석방해주는 반면에, 다른 공범은 징역 3년을 선고받게 된다는 것이다. 이는 상대편 공범이 자백했을 경우에도 성립한다. 누구든 자백을 하면 자백을 한 사람은 석방되지만, 상대편 공범은 3년의 징역을 받는다. 그러나 두 공범이 모두 자백을 하면 각각 징역 2년을 받으며, 둘 다 자백하지 않고 묵비권을 행사하면 증거 불충분으로 각각 징역 1년을 받게 된다.

이는 '죄수의 딜레마'의 가장 대표적인 사례이다. 상대방이 배신하지 않고 자백하지 않을 것이라는 강한 믿음을 가지고 있다면 묵비권을 행사할 가능성이 크다. 또한, 상대편 공범도 동일한 선택을 한다면 서로에게 최선인 결과, 즉 1년의 징역을 선고받게 될 것이다. 그러나 상대방을 믿지 못한다면 상대방이 자백해서 자신이 구형을 받게 되는 일이 일어나는 것이 두려울 것이다. 결국, 두 사람은 서로를 믿지 못하고 자백을 하게 되어 두 사람 모두 징역 2년을 선고받을 가능성이 크다. 대부분의 사람은 자신의 이익을 고려해서 공공의 이익이 아닌 '자신'에게 최선인 선택을 한다. 그래서 서로를 배신하지 않고 협조했을 때의 결과보다 나쁜 결과를 맞게 된다. 이러한 상황에서 상대편 공범이 협조를 선택했을 때 또 다른 공범이 묵비권을 행사함으로써 협조를 선택하는 것보다 공범을 배신하는 것이 이득이 된다. 상대편 공범이 배신하는 상황을 고려해봐도 역시 자신이 묵비권을 행사하여 징역 3년을 받는 것보다는, 상대방을 배신하여 징역 2년을 받는 것이 이득이 된다. 모두가 배신하는 선택을 했을 때 이는 내시균형(Nash equilibrium)을 만족한다. 이는 개인에게 있어서 최선의 선택이 서로에게 최선의 결과를 가져오진 않는다는 것을 보여주는 예시이다.

냉전 시대

제2차 세계대전 이후 냉전 시대가 열렸다. 미국과 소련은 어느 한쪽이 무기를 만들어내면, 다른 한쪽은 더 나은 무기를 만들어 내는 식의 군비 경쟁을 펼쳤다. 그러나 무기 개발은 막대한 자원 소모 및 경제적 손실을 야기하고, 서로 만들어낸 핵무기를 사용하게 되면 거대한 핵전쟁이 발생하여 지구가 멸망에 가까운 위기를 맞을 수 있다는 문제 때문에 미국과 소련은 더는 무기를 개발하지 말자는 약속을 했다. 여기서 딜레마가 발생한다. 서로 약속은 했으나, 상대방이 핵무기를 개발할지 개발하지 않을지 알 수 없는 상황에서는 각자 핵무기를 개발하는 것이 최선의 선택이 되기 때문이다. 물론 양국에서 서로 무기를 만들어내지 않는다는 선택을 해서 평화를 맞을 수 있는 상황이 가장 최선이지만, 한 국가의 입장에선 타국의 핵무기 보유 여부를 알 수 없는 상황에 무기를 개발하지 않는다는 선택을 내린다면, 타국은 핵을 보유하여 자국의 군비를 압도하게 되는 최악의 상황에 놓이게 될 수 있다. 그러나 핵을 개발하는 선택을 한다면 최소한 타국과 핵 군비 균형을 이룰 수 있기 때문에 자국의 입장에서 합리적인 선택이라고 볼 수 있다. 결국 양국은 딜레마로 인해 군비 경쟁을 중단할 수 없었지만, 경쟁이 서로에게 큰 위협이 되어가는 것을 인지하고 있었기 때문에 딜레마를 해결하기 위해 핵확산금지조약을 맺는 등의 수많은 노력을 기울였다.

관용(Leniency) 제도

담합 자진신고자 감면 제도(leniency program)는 죄수의 딜레마를 활용한 제도로, 기업이 담합행위를 자진하여 신고하고 공정거래위원회의 조사에 협조할 경우 과징금을 감면해 주는 제도이다. 담합에 참여한 기업들이 담합행위에 대해 모두 침묵하고 있으면 증거가 충분하지 않아서 처벌에 어려움이 따르는데, 제일 먼저 자진하여 담합행위를 신고하면 과징금을 100% 면제해주는 제도이다. 이는 죄수의 딜레마로, 앞서 설명한 죄수 두 명이 서로를 믿을 수 없는 것처럼 기업 역시 상대 기업을 믿을 수 없기 때문에 생기는 딜레마이다. 제일 먼저 신고하면 과징금을 면제해 주는데, 만약 신고하지 않고 담합행위를 진행하다가 상대 기업이 먼저 자진하여 신고하면 담합행위에 따른 큰 과징금을 단독으로 부여받을 수 있기 때문에 서로 먼저 신고하는 것이 기업에 이득인 결과를 초래한다. 딜레마를 이용하여 고안한 관용 제도는 큰 성과를 거두었다. 관용 제도는 2011년 기준 40여 개국에서 시행되고 있으며, 대한민국의 2010년 기준 통계를 살펴보면 전체 담합 과징금 사건 중 관용 제도가 적용된 사건은 68%로 상당히 높은 수치를 기록하고 있다.

뻔뻔한 저녁 식사의 딜레마

뻔뻔한 저녁 식사의 딜레마(unscrupulous diner’s dilemma), 또는 저녁 식사의 딜레마(diner’s dilemma)는 글랜스(Glance)와 허버만(Huberman)이 고안한 딜레마로, 저녁 식사를 하는 일상생활에서 발견할 수 있다. 친구들과 저녁 식사를 할 때, 자기가 주문한 음식의 값은 자신이 내는 방법도 있고, 다 같이 먹는 음식이기 때문에 다양한 음식을 주문하고 1/n으로 계산하여 저렴하게 먹는 방법도 있다. 그러나, 여럿이 식사하는 상황에서 1/n으로 계산하기로 했는데 옆의 친구가 값비싼 스테이크를 주문한다면 자신은 비교적 저렴한 음식을 주문할 이유가 적다. 그래서 모든 사람이 상대적으로 비싼 메뉴를 주문하여, 주문한 음식의 값을 각자 지출하는 것보다 더 비싼 저녁 식사를 하게 되는 현상이다. 이는 죄수의 딜레마가 일상생활에 적용되는 간편한 예를 보여준다.

해결 방안

협력 및 전제

죄수의 딜레마는 기본적으로 대상자가 서로 교류가 없어야 하고, 어느 한 사람의 선택이 상대방의 결과에 영향을 미치는 상호 의존적이며 전략이 필요한 상황이 전제가 된다. 또한 이러한 상황에서 사람들은 합리적인 선택을 할 것이라는 가정을 바탕으로 하고 있다. 다음의 해결 방안들은 게임 이론의 특징인 전제들을 몇 가지 제외하고 생각하여 현실의 딜레마를 해결하는 방법을 제시한다.

• 당사자들 간의 지속적인 관계 전제 : 당사자들이 반복적인 상호작용을 함으로써 당사자들이 상대방의 전략, 기대, 한계 등에 대해 익숙해지도록 유도하며 시간이 지남에 따라 상대방의 가치에 대해 깨닫게 된다. 즉 선택의 순간에 상대방의 전략과 기대 및 한계를 고려하여 선택하게끔 한다.

• 미래의 가치화 : 죄수의 딜레마 상황에서 협동적인 산출물을 얻기 위해서는 참여자에게 미시적인 문제보다 미래에 관심을 둘 수 있게 해야 한다. 즉 현재보다 미래의 중요성을 강조하는 것이 협동을 증진시키는 것의 근본적인 조건이다. 근시안적인 이익보다 미래의 가치를 중요하게 생각하는 것이 중요하다.

• 규칙과 절차의 명확화 : 협상 과정에 대한 신뢰와 선택 대안에 대한 정확한 계산을 가능하게끔 하는 규칙과 절차를 명확하게 설정하여 신뢰 분위기를 조성한다.

• 일관적인 기준의 설정 : 협상을 협동적으로 이끌지 못하는 이유 중 하나로 일상화된 방법의 부재를 들 수 있다. 상호 간의 협조 정책이 내외부적으로 계속 변하고 일관적이지 못하기 때문에 협동 관계에 금이 가는 경우가 생긴다. 따라서 일관적인 기준을 설정하여 협상한다.

• 믿을 만한 정보의 이용 : 협동적인 산출물을 얻기 위해 참여자들이 그 상황을 정확히 이해하고 감시에 대한 확신이 있어야 하는데, 이를 위해서는 정확한 정보가 필수적이기 때문에 믿을만한 정보를 활용할 수 있도록 정보를 제공해야 한다.

• 배반에 대한 처벌 : 상호 간의 행태를 규율하고 합의된 협의를 어겼을 경우, 그 배반 행동에 대한 처벌이 가해지는 규범이 있어야 한다. 배반했을 때 줄어들 이익의 크기도 일종의 처벌이 될 수 있다.

팃포탯

팃포탯(Tit for tat)은 죄수의 딜레마가 반복될 경우에 효과적으로 성립할 수 있는 전략을 제시한다. 1979년 미국의 사회이론가 로버트 액설로드(Robert Axelroad)는 죄수의 딜레마 문제를 하나의 게임으로 생각하여, 문제를 해결하는 컴퓨터 프로그램을 제작해서 승부를 가리는 대회를 열었다. 참가자들이 죄수의 딜레마 문제에 대응할 수 있는 컴퓨터 프로그램을 제작하여 출품하면, 그 프로그램들을 각각 하나의 죄수로 간주하여 두 명씩 짝지어서 200번 게임을 시킨다. 한 쌍의 게임이 끝나면 다른 프로그램과 짝을 지어 다시 200번 게임을 하는 식으로 모든 프로그램들이 한 번씩 서로 겨루게 한다. 그리고 각각의 프로그램이 받은 점수를 합해서 가장 높은 점수를 얻어내는 프로그램이 승리하는 것으로 인정한다. 두 경쟁 프로그램이 모두 협력한다면 3점을 받고, 모두 배반한다면 1점을 받는다. 한쪽은 배반하고 다른 한쪽이 협력한다면, 배반한 쪽이 5점을 획득하게 된다. 이 게임은 큰 반향을 불러일으켰다. 전 세계에서 게임 이론가, 인공지능 전문가, 경제학자, 심리학자들이 참여해 여러 프로그램을 내놓았다. 1차 대회에는 15개의 프로그램들이 경합을 벌였고, 2차 대회에는 62개의 프로그램들이 경쟁했다. 다양한 전략을 가진 프로그램들이 참가했고, 그중에는 매우 복잡한 코드를 가진 프로그램도 있었지만 결국 최후의 승리자는 팃포탯이라는 짧고 간단한 프로그램이었다.

팃포탯(Tit for tat)의 전략은 '처음엔 항상 협력하고, 이후에는 상대방이 이전에 했던 판단을 똑같이 한다'이다. 팃포탯이 추구하는 전략의 특징은 다음과 같다.

• 상대가 협력하는 한 협력한다.
• 상대방의 얘기치 못한 배반에는 바로 응징한다.
• 상대의 도발 후에는 용서한다.
• 상대가 나의 패턴을 명확히 알 수 있도록 한다.

팃포탯은 기본적으로 상대의 협력을 유도하여 배반하지 않는 것을 원칙으로 하지만, 상대가 먼저 배반했을 경우에는 가감 없이 배반하여 보복한다. 그러나 배반 후에 상대방이 협력한다면 용서하고 다시 협력하는 자세를 취한다. 이는 당장은 조금 손해를 보더라도 로버트 액설로드 교수가 제안한 게임의 특징인 '반복'이라는 특성 때문에 결과적으로는 다른 전략에 비해 이득을 취할 수 있다는 논리를 가지고 있다. 다만 팃포탯이 유용하게 사용되기 위해서는 다음과 같은 전제가 필요하다.

• 반복 게임에 참여하는 유기체는 경제학적으로 합리적인 의사결정을 하며, 상대방 역시 그럴 것이라고 인지해야 한다.
• 자신이 과거에 상호작용했던 상대방이 누구인지 정확하게 변별할 수 있어야 한다.
• 과거에 상호작용했던 상대방과의 게임이 어떻게 진행되었는지 기억할 수 있어야 한다.
• 협력 혹은 배반의 선택지는 상대방에게 명료하게 확인되어야 하고, 상대방의 선택 역시 명료하게 확인되어야 한다.

이러한 팃포탯의 매커니즘은 최초의 접근에서 이득을 내는 방법 이외에는 자신을 추월하는 득점 전략을 허용하지 않기 때문에 프로그램 대회에서 승리할 수 있었다. 프로그램 대회 우승으로 증명된 팃포탯의 방법론은 반복되는 죄수의 딜레마에서 손해를 최소화하며 서로 이익을 취할 수 있는 가장 효과적인 방법으로 제시된다.

참고자료

• 이동귀, 〈상식으로 보는 세상의 법칙 : 심리편〉, 《21세기북스》, 2016-11-30
• 박은태, 〈경제학 사전〉, 《경연사》, 2010-11-10
• 김상원, 〈‘죄수의 딜레마’에 빠진 당신의 선택은?〉, 《한겨례》, 2019-02-01
• 김남희 , 〈죄수의 딜레마〉, 《네이버 지식백과》, 2014-04
• 에코타운, 〈게임이론과 죄수의 딜레마〉, 《브런치》, 2016-06-15
• Theodore L. Turocy , 〈Game Theory〉, 2001-10-08
• sandtimer, 〈게임이론 - 죄수의 딜레마〉, 《네이버 블로그》, 2018-11-13
• 김성환 기자, 〈'이기적 유전자’키워드 짚어보기〉, 《베리타스알파》, 2012-05-03
• Caseinate, 〈죄수의 딜레마 대응 전략〉, 《브런치》, 2017-07-14
• 이성연, 〈반복적 죄수 딜레마 게임, 협력이 최선〉, 《넥스트이코노미》, 2012-04-25
• 허니문차일드, 〈저녁 식사모임의 딜레마〉, 《티스토리》, 2015-05-10
• KEEPIT, 〈게임이론 속 죄수의 전략, 팃포탯 〉, 《브런치》, 2018-07-23

같이 보기

• 게임이론
• 치킨게임

이 죄수의 딜레마 문서는 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반