내시 균형

내시 균형(Nash equilibrium)은 게임 이론에서 경쟁자 대응에 따라 최선의 선택을 하면 서로가 자신의 선택을 바꾸지 않는 균형상태를 말한다. 상대방이 현재 전략을 유지한다는 전제 하에 나 자신도 현재 전략을 바꿀 유인이 없는 상태를 말하는 것으로 죄수의 딜레마(prisoner's dilemma)와 밀접한 관계가 있다.

게임이론에서 내시균형이란 두 명이나 그 이상의 경기자들의 비협조적인 게임에서 각 경기자들이 다른 경기자들의 균형전략을 알고 있다고 가정할 때 어떠한 경기자들도 자신의 전략을 바꾸지 않게 되는 비협조적인 게임에 관한 해결방식이다. 만약 각 경기자들이 자신의 전략을 고수하고 아무도 전략을 바꾸지 않는다면 현재의 전략선택은 내시균형에 부합하는 결과를 갖게 된다. 간단히 말하면 Amy는 Phil의 결정이 변함이 없는 동안 Phil의 결정을 고려하여 그녀가 할 수 있는 최적의 선택을 하고, Phil 역시 Amy의 결정이 변함이 없는 동안 Amy의 전략을 고려하여 결정한다면 Amy와 Phil은 내시균형을 갖는다. 이와 같이 한 그룹의 경기자들은 그들이 다른 경기자들의 결정을 참고하여 내린 최적결정은 내시균형에 있다는 뜻이다.

존 포브스 내시가 만든 개념이며, 그의 이름을 따서 명명되었다. 존 내시는 이 공로를 인정받아 1994년 노벨 경제학상을 수상했다.

적용

게임이론자들은 내시균형이론을 몇 가지 정책결정자들의 전략적인 상호작용의 결과를 분석하는데 사용한다. 다시 말해 내시균형은 사람들이나 기업들이 서로간의 선택에 의지하여 동시에 결정해야 하는 상황일 때 그들에게 일어나는 행동변화를 예측할 수 있는 방법을 제공한다. 존 내시 (John Nash)의 발상에 깔려있는 간단한 통찰력은 의사 결정들을 개별적으로 분석할 경우 여러 의사 결정자들의 선택들에 의한 결과를 예측할 수 없다는 것이다. 대신, 다른 의사결정자들의 의사 결정을 고려 할 때 무엇을 할 것인지를 각 의사결정자에게 질문해야한다. 내시균형은 적대적인 상황에서 전쟁이나 군비확장경쟁(죄수의딜레마 참고)을 분석하는 틀이 되어왔고, 반복적인 상호작용으로 갈등을 완화시키는 방안을 제공한다. 다른 선호를 가진 사람(성대결;battle of the sexes)끼리의 균형, 협력으로 인한 이점을 시사하는 결과(사슴 사냥 게임; stag hunt)추론을 설명하는 데에도 사용된다. 이는 기술표준을 채택하는 연구에도 사용되고 예금인출사태(bank run), 통화위기 등의 발생을 연구하는 곳에도 사용된다. 교통류(워드롭이론 ; Wardrop’s principle), 경매의 구성(auction theory), 환경규제 같은 규제법의 제정 (공유지의비극 ; tragedy of the Commons), 축구에서 페널티킥(matching pennies) 등에도 적용가능하다.

역사

내시균형은 존 내시(John Forbes Nash. Jr)에 의해 명명되었다. 내시균형의 개념은 1838년 쿠르노(Antoine Augustin Cournot)의 과점이론에서 처음 사용되어 알려졌다. 크루노의 이론에서 기업은 그들의 이익을 극대화하기 위해 산출물을 얼마나 생산해야할지 선택한다. 그러나 이때 최적화된 산출량은 다른 기업들의 산출량에 영향받는다. 크루노균형에서 각 기업들의 산출물 극대화는 순수 전략으로 불리는 내시균형이다. 크루노는 최적반응(best response)의 개념을 균형 안정의 분석에서 도입하였다. 그러나 내시의 균형 정의는 크루노의 정의보다 넓은 개념이다. 물론 파레토효율의 균형에서 내시균형은 최적균형이 생성됨에 있어 아무런 판단을 제공해 주지 않는다.

현대 게임이론의 내시균형의 개념은 경기자들이 취할 행동을 여러 가능한 행동중에서 확률적으로 선택하여 사용하는 혼합전략의 개념을 대신한다. 내시균형 혼합전략의 개념은 폰노이만(John von Neumann)과 모르겐슈테른(Oskar Morgenstern)의 1944년 발표된 공저 ‘게임이론과 경제행동(The Theory of Games and Economic Behavior)’에서 소개되었다. 그러나 그들의 분석은 제로섬 게임(zero-sum games)같은 특별한 상황에서만 제한되었다. 그들은 내시균형혼합전략이 단지 유한한 행동에서의 제로섬게임에서만 존재함을 보였다. 1951년 내시의 글 ‘비협조 게임(Non-Cooperative Games)’에서 혼합전략내시균형은 어떠한 게임의 유한한 행동의 묶음에서 이 같은 게임에는 적어도 하나 이상의 내시균형이 반드시 존재함을 증명하였다. 내시의 존재능력을 증명하기 위한 단서는 노이만의 균형정의보다 훨씬 더 일반적이다. 내시에 따르면 “n개의 경기자들의 균형점은 다른 경기자들이 그들의 전략을 고수한 채 혼합전략을 이용하여 수익을 극대화하는 점에서 이루어진다.

이것은 연속 전략함수를 다른 전략에 생산하고 불필요한 옵션들의 확장은 궁극적으로 균형점이나 고정점에 존재한다”

내시균형 개념이 발전해 오면서 게임이론가들은 확실한 상황에서 잘못된 예측(혹은 특별한 예측을 실패)을 이끌 수 있다는 것을 발견했다. 그러므로 그들은 내시개념의 단점을 극복하기 위해 관련된 많은 대안개념(개량 내시균형)을 제시하였다. 특히 중요한 점은 몇몇 내시균형은 신빙성 없는 위협에 근거를 두고 있다는 것이다. 그후 1965년 젤텐(Reinhard Selten)은 ‘신빙성 없는 위협'에 근거를 둔 균형’을 제거한 부분게임완전균형(sub game perfect equilibrium)을 개선책을 제시하였다. 다른 내시균형의 확장에는 게임이 반복되거나 게임이 완전정보를 갖지 않았을 때의 상황에서의 개선책들이 있다. 그러나 이러한 내시균형의 개선책과 확장의 개념의 주요 관점은 ‘모든 균형개념은 다른 경기자들의 선택을 각 경기자들이 계산하여 선택한다’는 것이다.

정의

비공식 정의

비공식적으로 전략묶음은 경기자들이 일방적으로 전략을 바꿈으로써 이득을 얻을 수 없을 때의 내시균형이다. 이 의미를 확인하자면, 각 경기자들이 다른 경기자들의 전략을 들었을 때를 상상해보자. 각 경기자들이 자신에게 “다른 경기자들의 전략을 알고, 각 경기자들이 전략을 바꾸지 않는다고 했을 때 나는 전략을 바꿈으로써 이득을 얻을 수 있는가?”라고 묻는다고 가정하자.
만약 누군가가 “그렇다” 라고 한다면 그 전략집합은 내시균형이 아니다. 하지만 만약 모든경기자들이 자신들의 전략을 변경하지 않는다면 그 전략집합은 내시균형이다. 그러므로 내시균형을 이루는 각각의 전략들은 다른 전략에 근거한 최적반응이다.
내시균형은 때때로 제3자의 눈에는 비이성적으로 보이기도 한다. 그 이유는 내시균형이 파레토최적에서 나오지 않기 때문이다.
내시균형은 비이성적인 결과가 나오긴 하는데 경기자들이 비이성적 이동을 동반한 위협을 가하기 때문이다. 이러한 ‘부분게임내 완전내시균형’ 게임에서는 분석의 틀이 중요한 의미를 가지고 있다.

공식적인 정의

$(S,f)$ 를 경기자 $n$ 명의 게임이라 두고, $S_{i}$ 는 경기자 $i$ 가 취할 전략, $S=S_{1}\times S_{2}\times \dotsb \times S_{n}$ 는 전략프로필의 집합일 때

$f=(f_{1}(x),\dotsc ,f_{n}(x))$ 는 $x\in S$ 의 이익함수이다.
$x_{i}$ 가 경기자 $i$ 가 취할 전략이라고 두고 $x_{-i}$ 는 경기자 $i$ 를 제외한 모든 경기자들의 전략프로필이라고 하자.
각 경기당 $i\in \{1,\dotsc ,n\}$ 들이 전략 $x_{i}$ 를 선택하고 전략프로필 $x=(x_{1},\dotsc ,x_{n})$ 의 결과를 냈을 때 경기자 $i$ 가 얻게되는 이익은 $f_{i}(x)$ 이다.
이때 각 이익은 다른 경기자들이 전략을 선택했을 때 경기자 $i$ 가 선택한 전략에 따라 달려있다.
전략프로필 $x^{*}\in S$ 은 다른 경기자들이 일방적으로 전략을 바꾸지 않았을 때의 내시균형이고 이때의 식은 다음과 같다;

$\forall i,x_{i}\in S_{i}:f_{i}(x_{i}^{*},x_{-i}^{*})\geq f_{i}(x_{i},x_{-i}^{*})$ .

만약 불평등이 위의 조건들이 모든 경기자들과 모든 가능한 대안전략들에게 엄격하게 유지되었을때(≥대신 >을 사용했을때) 그 균형점은 강한내시균형(a strict Nash equilibrium)으로 분류된다. 만약 대신에 몇 경기자들에 있어서 균등이 $x_{i}^{*}$ 에 존재하고 다른 전략들이 $S$ 집합에 있을 때 이 균형은 약한내시균형(a weak Nash equilibrium으로 분류된다.

게임은 순수전략 및 혼합전략을 가질 수 있다. (후자의 순수전략은 고정확률을 가지고 확률적으로 선택한다.)

참고 자료

Game theory textbooks

Dixit, Avinash and Susan Skeath. Games of Strategy. W.W. Norton & Company. (Second edition in 2004)
Dutta, Prajit K. (1999), 《Strategies and games: theory and practice》, MIT Press, ISBN 978-0-262-04169-0 . Suitable for undergraduate and business students.
Fudenberg, Drew and Jean Tirole (1991) Game Theory MIT Press.
Leyton-Brown, Kevin; Shoham, Yoav (2008), 《Essentials of Game Theory: A Concise, Multidisciplinary Introduction》, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1 . An 88-page mathematical introduction; see Chapter 2. Free online Archived 2000년 8월 15일 - 웨이백 머신 at many universities.
Morgenstern, Oskar and John von Neumann (1947) The Theory of Games and Economic Behavior Princeton University Press
Myerson, Roger B. (1997), 《Game theory: analysis of conflict》, Harvard University Press, ISBN 978-0-674-34116-6
Rubinstein, Ariel; Osborne, Martin J. (1994), 《A course in game theory》, MIT Press, ISBN 978-0-262-65040-3 . A modern introduction at the graduate level.
Shoham, Yoav; Leyton-Brown, Kevin (2009), 《Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations》, New York: Cambridge University Press, ISBN 978-0-521-89943-7 . A comprehensive reference from a computational perspective; see Chapter 3. Downloadable free online.
Gibbons, Robert (1992), 《Game Theory for Applied Economists》, Princeton University Press (July 13, 1992), ISBN 978-0-691-00395-5 . Lucid and detailed introduction to game theory in an explicitly economic context.
Osborne, Martin (2004), 《An introduction to game theory》, Oxford University, ISBN 978-0-19-512895-6 . Introduction to Nash equilibrium.

Original Nash papers

Nash, John (1950) "Equilibrium points in n-person games" Proceedings of the National Academy of Sciences 36(1):48-49.
Nash, John (1951) "Non-Cooperative Games" The Annals of Mathematics 54(2):286-295.

기타 인용

Mehlmann, A. The Game's Afoot! Game Theory in Myth and Paradox, American Mathematical Society (2000).
Nasar, Sylvia (1998), "A Beautiful Mind", Simon and Schuster, Inc.