[=] 내쉬 균형(game thoery)에 대하여..

... [참고] ...
######  내쉬 균형  ######

영화 <뷰티풀 마인드>(A Beautiful Mind, 2001년 작)는 《뉴욕 타임즈》 경제부 기자    실비아 네이사가 쓴 같은 제목의 책(한국어판: 신현용 외 옮김, 《뷰티풀 마인드》, 승산)을 영화화한 것으로, 게임 이론의 업적으로 1994년 노벨 경제학상을 수상한 수학자 존 내쉬(John Forbes Nash Jr., 1928-)의 삶을 다루고 있다.

1900년대 초까지 경제학자들은 시장에 대한 추상적인 이론을 마련해 놓았지만, 시장 참가자와 전략의 영향은 고려하지 않고 단순히 "수요와 공급은 일치한다."고 가정하였다. 그 탓에 수요와 공급이 일치하지 않는 가격의 문제에 답을 내줄 새로운 이론이 필요했다.

1920년대 들어 ‘존 폰 노이만’(John von Neumann), ‘오스카 모르겐스테른’(Oscar Morgenstern)이 체스와 같은 ‘2인 영합 게임’(zero-sum game: 참여자의 이득과 손실의 총합이 0이 되는 게임)에 대해 연구했으나, 현실의 경제적 거래 대부분은 영합 게임이 아니라 협상과 마찬가지로 모든 참여자가 뭔가 소득을 얻고 싶어 하는(반드시 참여자의 이해가   엇갈린다고는 볼 수 없는) 상황이다. 이는 게임 이론 용어로 표현하면 ‘비영합 게임’(non-zero-sum game)에 해당한다.

내쉬 이론은 이러한 ‘비영합 게임’에 관한 이론으로서, 다른 참가자의 전략이 주어져 있다는 가정 아래 각 참가자가 최선의 전략을 세울 때 얻어지는 결과가 내시 이론의 핵심 개념인 ‘내쉬 균형’(Nash equilibrium)이다. 즉 ‘내시 균형’은 다른 참가자들이 최적전략을 세울 때를 가정하고 각자가 최적전략을 내세운 결과이다.

영화에서는 내쉬가 1948년 프린스턴 대학 근처 술집에서 친구들과 여자를 꼬시려 하면서 ‘내시 균형’이라는 발상을 떠올리는 것처럼 묘사하고 있다. 친구들이 매력적인 금발 여인을 꼬셔 보라고 하자 그는 "만약 모두가 금발 여성에게 접근하면 그녀는 그들을 가까이 하지 않을 것이다. 그렇다고 그녀의 친구들에게 가면 '꿩 대신 닭'을 원하는 상황이므로 친구들 역시 그들을 피할 것이다. 하지만 만약 처음부터 금발 여성에게 아무도 접근하지 않는다면 서로 싸울 필요도 없고, 다른 여성들이 기분을 상할 일도 없을 것이다. 그게 유일한 성공 전략이다."고 한다.

즉 각자가 가장 아름다운 여성이 아닌 그보다 덜 매력적인 여성에게 데이트를 신청하면 전체 성공 확률이 높아진다는 것이고, 이는 '모두'가 다르게 행동하면 '모두'가 좋은 결과를 얻게 된다는 말과 같은데 ‘내쉬 균형’의 분석과는 무관한 것이다. '모두'를 전제로 한다는 것은 상호간 협동이나 정보 교류가 행해짐을 뜻하는 것인데 ‘내쉬 균형’은 그런 것이 없다고 가정하는, 게임 이론 용어로는 ‘비협조(non-cooperative) 비영합 게임’에서 생각하는 것이다.

즉, '모두'가 아닌 '개인'을 전제로 하면 어떻게 자원 고갈, 환경 파괴 같은 나쁜 결과가 나오는지 설명이 된다. 개인적으로 자기 행동을 바꾸려는 이는 없으나 전체의 행동을 통해서는 해로운 결과가 나타나고, 행동을 서로 조절할 수 있으면 모두에게 좋은 결과가 생기나 개인으로서 행동하는 한 그럴 수 없다.

내쉬 균형은 각자가 최적의 결과를 예상하고 행한 행동의 종합이지만, 이로부터 반드시 최적의 결과가 나옴을 보장하는 것은 아니다. 아니, 오히려 나쁜 결과를 포함하는 것이야말로 내시 균형이라고 부를 수 있다. 상대방의 최적전략을 예상하고 수립한 최적전략이지만 상대방이 그 최적전략을 내놓지 않으면 자신의 전략도 최적이 아니게 된다는 뜻이다. 그 좋은 예가 ‘2인 비협조 비영합 게임’에서 나오는 유명한 '죄수의 딜레마'이다.

현실 세계에서 ‘내쉬 균형’을 적용할 수 있는 예로는 다음과 같은 것이 있다.

(1) 경매에서 각각의 입찰자가 얼마에 입찰할지는 타인의 입찰 예상액에 따른다. 이때 모든 입찰자가 합리적으로 생각해서 자신의 입찰가를 결정한 결과가 내시 균형이다.

(2) 두 남녀가 데이트를 하는데 발레 공연과 권투 경기가 겹쳤다. 남자는 권투를, 여자는 발레를 더 좋아하지만 각자 좋아하는 것을 혼자 보는 것보다는 같이 보는 것을 좋아한다. 이때 상대방의 행동을 예상해서 각자가 무엇을 볼지 결정한 결과가 내시 균형이다.

(출처 : '대중 매체 속 수학' - 네이버 지식iN)

1950년에는 내쉬(Nash)가 협상(bargaining)이론에 관한 협조적 모형을 발표하였는데, 이는 사전에 선수들이 구속력 있는 협약을 맺고 하는 게임이다. 이는 몇 개의 공리를 이용하여 다수의 결과 중 관심 있는 결과를 하나만 가려냈다 하여 공리적(axiomatic) 모형이라고도 한다. 이어 내쉬는 비협조적 게임을 위한 균형이론을 발전시켰는데, 이것이 유명한 ‘내쉬균형이론’이다. ‘내쉬균형’은 각 선수들의 전략이 상대가 사용할 것이라고 예측한 전략에 대하여 최선의 전략이 되어야 하며, 또한 상대방에 대한 예측이 들어맞아야 한다는 두 가지   특성을 지니고 있다. 따라서 ‘내쉬균형’ 상태에서는 어느 한 쪽도 독자적으로 균형전략으로부터 이탈한 유인이 없게 된다.

(출처 : '게임이론(Game Theory)' - 네이버 지식iN)

######  완전정보하의 정적 게임  ######

1. 게임의 균형

1.1 우월전략(Dominant Strategy)

상대방이 어떤 전략을 선택하는지에 관계없이 자신의 보수를 더 크게 만드는 전략.

1.2 내쉬균형(Nash Equilibrium)

각 경기자가 상대방의 전략을 주어진 것으로 보고 자센이게 최적전략을 선택할 때 이 최적 전략의 짝을 내쉬균형이라고 한다.

1) 내쉬균형의 특성

ㄱ. 선수들은 주어진 상황에서 최선의 대응전략을 택한다고 특성은 지닌다.

ㄴ. 자기예상실현의 특성을 지니고 있다. 즉, 상대방이 택할 전략을 예측할 수 있으며, 이 예측대로 상대가 선택한다는 것이다.

* 정리

(1) 열등전략은 결코 내쉬균형 전략이 될 수 없다.

(2) 반복적 열등전략 삭제에 의해 구한 균형은 내쉬균형이다.

EXAMPLE : prisoners' Dilemma

 두 명의 공범자 1, 2를 형사가 검거했다. 그러나 그 형사는 심증만 있는 상태라서 범인들의 자백이 없이는 기소가 불가능하다. 그러자 이 형사는 다음과 같은 방법을 생각해 냈다. 각각 피의자를 독방에 격리시켜 놓고 다음과 같은 사항을 알려 주었다. "만약 당신이 자백을 하지 않았는데 다른 한 명이 자백을 하면 자백한 사람은 특전으로 풀려나나 당신은 10년의 징역을 살게 됩니다. 반대로 당신만이 자백을 하게 되면 당신이 특전의 혜택을 받게 됩니다. 만약 둘이 다 자백하는 경우에는 각각 5년형을 언도 받을 것이며, 둘 다 자백을 하지 않으면 각각 1년 형을 언도 받게 될 것입니다." 

이를 normal form으로 표현하면 다음과 같다.

위 상황에서 1과 2는 각각 confess하는 것이 Dominant Strategy이다. 따라서 (C,C)는 Dominant Strategy Equilibrium이 된다. 그 결과 두 용의자는 모두 5년씩 징역을 살게 된다.

이 결과를 살펴보면, 서로에게 불만족한 해를 얻는다는 문제를 발견할 수 있는데, 그것은 둘이 다 not confess하면 1년씩만 징역을 살면 되는데 두 사람에게 서로 좋은 결과를 마다하고 5년 징역을 살게 되는 것이 최선의 대응이라는 결과가 나오는 까닭에 딜레마이다.

그러나 믿는다는 것이 말로만 형성되는 것이 아니고 확실한 보장이 있어야만 가능하다. 이러한 딜레마는 개인의 합리성(individual rationality)과 집단의 합리성(collective rationality) 차이에 의해 생긴다. 즉 ‘파레토 효율’이 아닌 것이다.

1.3 내쉬 혼합전략균형

1) 순수전략과 혼합전략

순수전략(pure strategy) : 일어날 개연성이 있는 모든 경우에 대해서 해당 경기자가 취할 행동의 완전한 계획(complete contingent plan)으로 정의 된다.

혼합전략(mixed strategy) : 경기자가 여러 개의 행동 가운데 하나를 선택하되 주어진 확률분포에 따라 임의로 택하는 것을 뜻한다.

2) 혼합전략으로서의 균형개념

 위에서 언급한 것처럼 혼합전략의 정의는 여러 가지 순수전략을 확률로써 혼합하여 사용하는 전략이다. 그러면 왜 혼합전략을 사용하는가, 혼합전략을 사용할 조건은 무엇인가 하는 질문에 어느 정도 이해가 있어야만 혼합전략을 찾을 수 있게 된다.

 먼저 어떤 선수가 혼합전략을 사용할 경우에는 몇 가지 순수전략을 선택하여 그 순수전략을 각각 확률로써 선택하게 된다. 이 경우 열등전략은 아무리 작은 확률이라도 선택되어서는 안 된다. 왜냐 하면, 만약 확률로써 그 열등전략이 나오게 되면 그 선수는 최선의 전략을 택한 것이 아니기 때문이다. 따라서 혼합전략의 대상이 되는 순수전략 각각은 열등전략이 아니어야 한다.

둘째로는 각각의 순수전략이 선수의 입장에서는 동등한 보상을 주어야 한다. 만약 어떤 순수전략이 선수에게 보상(기대보상)을 더 준다면 혼합전략이나 다른 순수전략을 택하는 대신 바로 그 순수전략을 택하는 것이 최선이기 때문이다. 따라서 혼합전략을 선수가 택한다는 것은 동일한 보상을 주는 순수전략들의 확률을 결정하는 것이라고 볼 수 있다.

 그러면 왜 동일한 보상을 주는 데 꼭 혼합전략을 사용하여야 하느냐 하는 문제가 생기게 된다. 동일한 보상이므로 아무 전략이나 사용하여도 문제가 되지 않는가 하고 반문할 수 있다. 그 해답이 바로 이 균형의 묘미다. 동일한 보상 하에서 적절한 확률로 전략을 택하여야 균형을 얻을 수 있기 때문이다.

 만약 동일하다고 아무 전략이나 택한다면(동일한 보상을 주는 전략 중) 상대방은 이에 대한 최선의 전략을 택하기 때문에 이 경우 자신이 택한 전략이 이제는 최선이 되지 않는 경우가 발생한다. 따라서 균형이 되기 위해서는 동일한 보상 중 적절한 것을 택하여야 상대가 그에 대한 최선의 선택을 하더라도 자신의 전략을 바꾸지 않아도 되 그런 확률이 있게 된다.

이것이 혼합전략으로서의 균형개념이다. 오로지 균형 상태에서만 보상이 동일해지기 때문에 그 균형을 유지하지 않는 다른 상태가 되면 순수전략의 보상이 동일해지지 않는다. 따라서 혼합전략으로서 균형이 깨져 버린다.

3) 혼합전략 찾는 방법

ㄱ. 열등 전략을 계속 반복하여 삭제

ㄴ. 서로 상대방이 어느 순수전략을 택하든 보상이 동일해지도록 확률을 설정

2. 내쉬균형의 존재, 다중성 및 파레토 효율성

2.1 내쉬균형의 존재정리

1) 정리 1 : 모든 유한한 전략형 게임은 내쉬균형을 가진다.(Nash. 1951)

2) 정리 2 : 모든 선수들의 순수전략집합이 밀집(compact)되어 있고, 선수들의 보상함수가 순수전략에 대해 연속적일 경우 내쉬균형은 존재한다. (Dasgupta and Maskin, 1986)

2.2 내쉬균형의 약점

1)균형의 다중성 문제 -내쉬균형이 유일한 경우가 아닌 여러 개 있는 경우로서 이를 균형의 다중성 문제라고 한다.

2) 내쉬균형이 파레토효율적이 아닐 수도 있다는 점이다. 먼저 파레토 효율의 정의를 간략하게 살펴보면 어느 일방을 해치지 않고 서로가 좋아질 수 없는 상태에 있을 때 이를 파레토 효율이라고 한다.

위 example 죄수 딜레마의 그림에서 보면 내쉬균형은 (C,C)로서 (-5,-5)를 얻는다. 그러나 이러한 결과는 (NC,NC)의 경우보다 서로에게 나쁘며, 따라서 파레토 비효율적인 것이 되는 경우이다. 그러나 일반적으로 균형이 여러 개 있는 경우에 파레토 효율적인 균형이 선택될 가능성이 높으며 이것도 일종의 관심의 초점으로 해석될 수 있다.

* 정리

1) 내쉬균형은 반드시 파레토 효율이 아니다.

2) 우월전략균형은 내쉬균형이다. (역도 성립)

3) 우월전략균형은 반드시 파레토 효율이 아니다.

[~]  게임이론(game thoery)에 대하여..
[=]  Posted by 서재민