9월 Monthly Seminar : 게임이론

9월 Monthly Seminar : 게임이론

발표자 : 김성훈

 

      일반적으로 하나의 에이전트가 환경에서 활동할 때, 각 스텝은 오로지 한 에이전트의 폴리시와, 환경의 트렌지언트로 결정되어 다른 스테이트로 이동한다. 그러나 서로 다른 폴리시를 가진 에이전트 들이 하나의 환경 위에서 상호작용한다면 우리는 더 많은 것들을 고려해주어야한다. 기본적으로 우리가 강화학습에서 다루는 점은 에이전트가 환경에서 가장 리워드를 많이 받도록 하는 것이다. 그러나 여러 에이전트들이 각자 리워드를 많이 받기위해 학습해 나간다면, 상황을 어떻게 바뀔까? 이런 점들을 고려하는 이론을 게임이론이라고 부른다.

    게임이론의 이론적 기초를 제시한 사람은 폰 노이만이다. 2인 제로섬 게임은 게임에서 발생하는 리워드의 총량이 0인 경우로, 한명이 손해보는 만큼 다른 한쪽이 이득을 보는 게임이다. 이 때 나는 리워드가 가장 큰 행동을 선택하고, 상대는 내가 리워드를 가장 적게 받는 행동을 선택할 것이다. 그럼 가장 처음은 리워드가 max인 행동이며, 다음 상대는 내 리워드가 min인 행동을 선택한다. 이런 형태로 모든 행동에 대해 전개해 나가면 optimal policy, 즉 서로가 가장 만족할 만한 형태의 폴리시를 결정할 수있다.   

     다음으로 게임이론 중 가장 쉽게 이해할 수 있는 가위바위보에 대해 이야기해보자. 만약 한명의 플레이어가 패를 내는 정책을 수정하지 않고 게임에 임한다고 고려해보자. 그때 다른 한명은 이길 확률이 가장 쪽으로 정책을 바꿔갈 것이다. 만약 플레이어 B 가 가위를 50%의 확률로 내는 정책을 고수한다면, 플레이어 A는 100%로 바위를 내는 정책으로 바꿔갈것이고, 50%의 승률을 가지게 될것이다. 그리고 나머지 50%는 무승부와 패에 해당하여 플레이어 A는 많은 리워드를 얻을 수 있다. 그러나 플레이어 B도 자신의 정책을 수정한다면 상황이 달라진다. 플레이어 A가 100%로 바위를 내는 정책을 가지고 있으니, B는 가위에서 보를 많이 내는 쪽으로 정책을 바꿀 것이며, 이에 맞추어 A도 바위에서 가위를 많이 내는 쪽으로 정책을 바꿔간다. 이런 상호작용이 계속 반복된다면, 가위바위보 게임은 결국 uniform random policy로 수렴하게 된다. 이때 어떤 한명이 독단적으로 자신의 정책을 수정하여, 가위를 조금 많이 내려한다고 가정해보자. 그럼 상대는 상대가 가위를 많이 내니 주먹을 많이 내는 정책을 취하여, 좀 더 큰 승률을 기록할 것이다. 즉 무작위정책에서 전략을 수정하는 것은 결코 좋은 학습방향이 아니다. 이런 입장은 양 쪽 플레이어 모두에게 해당하며, 결국 위 표와 같은 정책으로 수렴하고, 더 이상 수정하지 않는다. 이와 같은 상황을 내쉬균형이라고 말한다. 원론적으로 말하려면 더 많은 개념이 등장하지만, 우선 이 정도 수준에서 이해해도 괜찮을 것이라 생각한다.

     이 내쉬 균형은 영화 '뷰티플 마인드'의 실제 주인공인 존 내쉬에 의해 제시되었다. 내쉬균형은 게임이론을 모를지라도, 많이 접하게 되는 단어이다. 내쉬는 비협조적게임에서 n개 이상의 내쉬균형이 존재함을 증명함으로써 1994년 노벨경제학상을 수상하였다. 그가 리만 가설에 도전하던 도중 조현병이 발병한 또 다른 이야기도 존재한다. 마치 아인슈타인이 뉴턴의 고전역학에 물음을 던지듯, 내쉬는 애덤 스미스의 국부론에 반증을 남기며 경제학에서 주목받게 된다. 애덤 스미스가 말했던 경제 원리 중 하나는 다음과 같다.  '모든 구성원이 자신의 자리에서 최선의 선택을 할때 국가는 성장한다.'  존 내쉬는 게임이론을 통해 위 명제에 정면으로 반박하였다. 이 상황을 명확하게 설명해줄 한 문제를 소개하도록 하겠다.

     죄수의 딜레마. 어디선가 들어봄직한 흥미로운 문제이다. 두 죄수가 협력과 배신의 패 중 무엇을 선택하는지에 따라 결과가 달라져 버린다. 위 표를 바탕으로 설명하면, 죄수는 어떤 선택을 해야할 까? 죄수A의 입장에서 문제를 바라보겠다. 만약 죄수B가 협력을 선택한다면, 우리는 협력과 배신중에 선택해야한다. 협력을 한다면 둘 다 좋은 결과를 가지겠지만, 큰 보상이 주어지는 배신의 유혹이 존재한다. 따라서 죄수B가 협력한다면 죄수A는 배신할 때 더 큰 이득을 얻을 수 있다. 반대로 죄수B가 배신했을 때, 내가 협력을 한다면 가장 큰 패널티를 받게 된다. 따라서 이 경우에도 마찬가지고 배신을 선택해야한다. 결과적으로 어떠한 상황에서도 죄수는 배신하는 쪽이 자신에게 이롭다고 생각할 수 있다. 기존 애덤덤 스미스의 이론에 따르면 두 죄수가 각자의 위치에서 최선의 선택을 해야만 공동체에게 이롭다고 말할 수 있다. 그래서 두 죄수 모두 배신한다면 어떤 결과가 따르는가? 두 개의 배신은 두 개의 협력에 비해 안좋은 결과를 야기한다. 이런 아이러니는 현실 세계의 문제에도 직접적으로 이어진다. 단적으로 보면 배신하는게 좋다고 생각했을지라, 그 선택은 상황을 불리하게 만든다. 

     죄수의 딜레마의 아이러니함은 위 책을 통해 명쾌하게 해결할 수있다. 실제 세계는 단 한번의 '죄수의 딜레마'로만 이루어 지지않는다. 사람을 포함한 동물은 생애 중 이전에 만난 상대를 계속 만나게 된다. 이처럼 반복되는 죄수의 딜레마를 도입함으로서 전혀 반대의 결과를 얻을 수 있다. 그 중 어떤 전략이 가장 우세했을까? 앞선 한번의 죄수의 딜레마에서 도출된 배신을 선호하는 전략의 결과는 어떻게 되었을까? 이 질문들은 사람은 왜 협력하는지, 왜 동물들은 공생관계를 형성하는지, 왜 혈연관계에서 희생을 하는지 더욱 많은 질문들로 나아간다.  자세한 내용은 위 책을 통해 확인하는 편을 추천한다. 필자가 아무리 잘 설명하더라도, 책의 설명에 분명 미치지 못할 것이다. 또는 '반복된 죄수의 딜레마'에 대해 자세한 정보를 찾아보는 것도 도움이 될 것이다.