게임이론

게임이론이란 경쟁상대의 반응을 고려해 자신의 최적 행위를 결정해야 하는 상황에서 의사결정 형태를 연구하는 경제학 및 수학 이론이다. 게임이론은 1944년 수학자 폰 노이만(John von Neumann)과 경제학자 모르겐슈테른(Oskar Morgenstern)이 공저한 《게임이론과 경제행태》에서 등장했다. 이후 존 내시(John Nash)는 1950년 출간한 'Equilibrium points in n-person games'이라는 2페이지의 논문과 1951년 'Non-Cooperative Games'라는 짧은 논문을 통해 게임이론의 초석을 구축했다. 1994년 노벨경제학상을 공동 수상했으며 게임이론에 가장 큰 공헌을 하였다.

개요

게임이론은 의사 결정자들이 상호 의사결정을 했을 때 어떤 결정이 가장 합리적인 결정이 될 것인지를 다룬다. 게임이론의 전제는 의사결정자들은 합리적으로 선택을 하며 상대방의 반응을 충분히 고려하고 의사결정을 내린다. 게임이론은 경기자(Player), 전략(strategy), 보수(payoff)라는 요소로 구성되어있다. 경기자는 게임의 주최로 사람이거나, 기업, 국가일 수도 있다. 전략은 경기자가 행할 모든 가능한 행동이다. 보수는 각 경기자가 선택한 전략에 따라 이들에게 돌아갈 결과를 수치화한 것이다. 이는 실제 금전적인 보상일 수도 있고 수치로 나타난 효용일 수도 있다.

등장배경

게임이론은 수학자 폰 노이만과 경제학자 모르겐슈테른이 공저한 《게임이론과 경제행태》가 발간되면서 본격적으로 발전되었다. 이들은 제로섬 게임(zero-sum game)을 연구하였다. 제로섬 게임은 경제학과 군사학에 큰 영향을 주었다. 이후 경제학자와 수학자들은 게임이론에 대해 연구하였다. 많은 학자는 게임이론을 통해 사회과학적으로 대두된 문제들을 해결할 수 있을 것이라 기대했으며 제로섬 게임을 연장하면 해결책이 나오리라 생각했다. 1994년 게임이론으로 노벨경제학상을 공동 수상한 존 내시에 의해 게임이론이 발전하였다. 게임이론 자체는 응용 수학의 한 분야로 자리 잡았지만, 경제학에서의 여러 문제, 특히 과점시장을 분석하는 틀로 적용되었다. 이후 게임이론은 미시경제학에서 꼭 필요한 분석 도구가 되었다.

특징

게임의 정의

경제학에서 정의하는 게임은 크게 협조 게임(cooperative Game)과 비협조 게임(Non-cooperative)으로 나눌 수 있다, 협조게임은 경제 주체들 간에 구속력 있는 협정을 사전적으로 맺을 수 있다는 전제하에 다자간의 전략적 상호관계를 그 대상으로 한다. 비협조 게임은 경제 주체들 간의 사전적 합의가 가능하지 않은 경우를 말한다. 대부분의 경제학자는 경제, 경영, 정치, 등 각종 사회과학 현상을 설명하고 경제 주체들의 행동을 예측하는데 있어,비협조 게임이론이 더 우월한 것으로 보고 있다.

게임의 표현 방식

게임을 표현하는 방식은 전략형 게임(strategic form games)방식과 전개형 게임(extensive form games)방식이 있다. 전략형 게임은 각 경기자가 가자고 있는 전략 집합과 각 경기자가 선택한 전략의 조합에 따를 보수로 구성되며 이를 보수행렬(payoff matrix)이라 한다.

승부차기 게임을 예로 들어, 이 게임에서의 경기자는 공격수와 골키퍼이다. 경기자가 선택할 수 있는 전략은 왼쪽과 오른쪽이다. 경기자의 보수는 성공할 경우 1로, 실패할 경우 –1로 표시한다. 공격수가 골을 넣는다면 1, 넣지 못한다면 –1로 표시한다.

게임이 단 한 번이 아닌 계속해서 순차적으로 전개될 수도 있다. 전략형 게임 방식은 게임의 의사결정과 불확실성을 표현하기 어렵다. 전개형 게임 방식을 적용해 표현할 수 있다. 전개형 게임 방식은 게임트리(game tree)를 통해 과거의 의사결정이 현재의 의사결정에 어떻게 영향을 미치는가를 직관적으로 표현할 수 있다.

제로섬 게임

폰 노이만과 모르겐슈테른은 두 경기자 사이의 제로섬 게임(zero-sum game)을 연구했다. 제로섬 게임의 본질은 게임 참가자가 서로 경쟁하고 그 결과 한 사람의 이득이 다른 사람의 손실로 귀착되는 현상으로 적대적 게임이다. 대표적인 예로는 포커, 동전 던지기, 홀짝 게임 등이 있다. 탁구, 야구, 축구 등의 스포츠, 전쟁도 적대적 게임의 하나로 볼 수 있다.

승자의 이득이 패자의 손실보다 큰 경우는 양의 합 게임(positive-sum game)이라 하고 양측 모두 손실을 얻는 경우는 음의 합 게임(negative-sum game)이라 한다.

내시균형

내시균형(Nash equilibrium)은 게임이론의 한 형태로 1994년 노벨경제학상을 공동 수상한 수학자 존 내시(John Nash)가 개발했다. 이는 각 참여자가 상대방의 전략을 주어진 것으로 보고 자신에게 최적인 전략을 선택할 때 그 결과가 균형을 이루는 최적 전략의 집합을 말한다. 이러한 전략 구성이 두 참여자에 의해 모두 예측되었을 때 이 게임은 내시균형에 도달하게 된다. 내시균형에 이르게 되면 참여자는 전략을 수정할 필요가 없다. 오늘날 정치적 협상이나 경제 분야에서 전략으로 많이 활용되고 있다. 내시균형의 대표적인 적용 예시로는 죄수의 딜레마(Prisoner's Dilemma)가 있다.

죄수의 딜레마

죄수의 딜레마는 게임이론에 등장하는 고전적인 사례이다. 이 게임의 참여자는 공범으로 의심받는 두 용의자이다.

• 따로 심문을 받는 경우

-두 용의자 모두 자백을 한다면 징역 3년 구형
-한 사람은 자백, 다른 한 사람은 부인한다면 자백한 자는 방면, 부인한 자는 무기징역 구형
-두 용의자 모두 부인한다면 징역 3개월 구형

• 함께 심문을 받는 경우

두 용의자는 서로 대화를 나누거나 눈짓을 주고받아 둘 다 범행을 부인함으로써 가장 가벼운 형벌인 징역 3개월 구형만 받을 수 있다. 두 사람이 서로를 믿고 버틴다면 최선의 결과를 얻게 된다. 하지만 합리적인 개인이라면, 상대방이 부인을 하든 아니면 자백을 하든, 본인은 자백을 하는 것이 더 유리한 결과를 가져온다는 것을 알게 된다. 그에 따라 두 명이 서로 대화나 눈짓을 주고받을 수 있도록 허용을 하더라도 게임의 결과에 영향을 미치지 않는다. 용의자A는 용의자B를 믿었으나 B의 배신으로 자백을 하게 된다면 A는 무기징역을 구형받는 최악의 결과를 얻게 된다. 따라서 자신도 배신하고 싶은 생각이 들게 된다. 이것이 바로 이 두 용의자가 처해 있는 딜레마이다. 

각 용의자가 받게 될 처벌의 양을 일종의 점수로 환산해 보수행렬(payoff matrix)을 만들어 보면 다음과 같다.

방면되는 것을 가장 좋은 경우로 생각하여 10이란 수치로 환산하고, 무기징역 구형은 제일 나쁜 경우로 1의 수치로 부여한다.

3년 구형을 3, 3개월 구형을 7이란 수치로 환산한다.

이러한 보수행렬에서 두 용의자 모두 자백하는 경우는 우월전략(domination strategy) 균형이 되며 내시균형이 된다. 그러나 이 결과가 두 용의자에게는 바람직한 결과는 아니다. 둘이 입을 맞추어 범행을 부인한다면 구형량을 3년에서 3개월로 줄일 수 있었는데 그렇게 하지 못한 것을 뜻하기 때문이다. 이 사실을 잘 알면서도 실제로는 두 용의자 모두 범행을 자백하고 말 가능성이 크다는 것이 이 게임의 특징이다.

게임이론과 블록체인

블록체인과 게임이론은 큰 연결고리를 이루고 있다. 블록체인의 대표 특성인 탈중앙화에도 블록체인의 신뢰 네트워크가 유지되는 것은 그 암호학적 퍼즐이 게임이론으로 해결될 수 있기 때문이다. 블록체인 플랫폼의 컨센서스 알고리즘 작동원리는 게임이론에 기반하고 있다. 에코시스템에서 채굴업자, 스마트 계약 사용자, 토큰 보유자 등의 참여자들은 중앙의 통제받지 않는다. 게임 참여자들은 다른 참여자의 행동에 대한 예측을 기반으로 자신의 보수를 극대화하는 방향으로 행동하게 된다. 컨센서스 알고리즘은 이런 행동들이 블록체인 네트워크의 신뢰를 더 강화할 수 있도록 설계한다. 참여자의 바람직한 행동을 유도하기 위해서는 인센티브와 페널티 구조의 설계를 통해 게임의 내시균형이 유지될 수 있도록 해야 한다.

심버스

심버스(SymVerse)는 게임이론을 기반으로 설계한 차세대 블록체인 플랫폼을 위한 암호화폐이다. 기존 블록체인 플랫폼들은 작업증명(PoW)이나 지분증명(PoS)과 같은 방식을 도입한다. 그러나 작업증명은 확장성과 속도 문제가 있고, 지분증명은 지분 보유의 쏠림 현상 등의 문제가 있다. 심버스는 게임이론에서의 다양한 기법과 결론을 통해 해결책을 제시했다. 참가자들이 개별적인 이익을 추구하더라도 자발적인 공생으로 이어지도록 설계했다. 심버스는 거버넌스, 합의과정 참여유인, 상호협력, 블록체인의 생산·유통·소비 단계에 걸쳐 게임이론을 다음과 같이 적용했다.

• 전략적 투표 이론의 거부권을 적용한 블록생성 합의구조
• 코인의 집단 간 분배 비율 결정과 집단 내 분배방식에 단계적 내시균형 도입
• 메커니즘 디자인(Mechanism Design)으로 참여동기 부여와 유인합치적인 코인 분배
• 소비자의 거래처리를 위한 노드 선택방식에 경매 기법 도입

심센서스

심센서스(SymSensus)는 심버스의 합의 알고리즘이다. 심센서스의 설계는 게임이론에 기반하며, 특히 사회선택이론을 활용해 구조설계기법을 적용했다. 보증노드는 25개로 구성되며 그 중 9개는 A그룹이라 부르고 재단이 선발한다. 나머지 16개는 B그룹이라 부른다.

• A그룹 노드들은 블록생성권이 없고, 투표권만 행사한다. 또한 동일한 투표결과를 보여주는 집단적인 거부권을 행사한다. 전체 보증노드 중 2/3이상 찬성할 경우 합의과정은 종결된다. 거부권이 존재하여 어떠한 보증 노드들이라도 담합해 이득을 취할 수 없다.
• B그룹의 노드들은 후보 신청한 작업노드 중 탈중앙화되고 4단계의 자동 벤치마킹 테스트를 통해 선발된다. 블록생성의 합의과정을 주관하는 프라이머리 노드(1개), 프라이머리 노드에 대한 우선순위가 확정된 프런트 벤치 노드(3개), 미들 벤치 노드(8개), 백 벤치 노드(4개)를 포함해 총 16개로 구성된다. 충분한 거래명세를 처리하기 위해 프라이머리 노드가 생성하는 블록의 수는 정해지지 않는다. 블록의 크기는 종류에 따라 다를 수 있다. 프라이머리 노드는 거래기록을 모아 블록을 생성한 후 생성한 블록에 대한 검증을 요청한다. 이때 프라이머리 노드는 서명기반 비잔틴 장애 허용(BFT)방식으로 보증 노드 수의 2/3 이상으로부터 확인을 받으면 블록생성이 확정되어 다른 노드들에 전파한다.

참고자료

• 김철환, 〈게임이론〉, 《경제학 주요개념》
• 박은태, 〈죄수의 딜레마〉, 《경제학사전》
• KEEPIT, 〈블록체인의 컨센서스, 게임이론의 선구자들〉, 《brunch》, 2019-01-06
• 강의하는아디들 공식, 〈게임이론 궁금하다면 봐야 할 영화, 뷰티풀 마인드〉, 《네이버 블로그》, 2019-01-14
• 조중환 기자, 〈(컬럼)게임이론과 암호경제학〉, 《CCTV뉴스》, 2018-10-25
• 심버스 백서 -〈SymVerse : Better World〉, 《심버스 백서》, 2018-10
• 해시넷, 〈(암호화폐 제46탄) 심버스(SymVerse)란 무엇인가?〉, 《네이버 블로그》, 2019-02-11

같이 보기

• 심버스

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

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 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 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반