위키원
"내시균형"의 두 판 사이의 차이
(새 문서: '''내쉬 균형'''이란 상대 플레이어의 전략이 예상 가능할 때, 자신의 최선택을 선택했을 때 그 결과로 형성된 균형 상태를 말한다. 내쉬 균...) |
(→죄수의 딜레마) |
||
| (사용자 2명의 중간 판 5개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
| − | ''' | + | '''내시균형'''<!--내시 균형, 내쉬균형, 내쉬 균형-->(Nash equilibrium)이란 상대 플레이어의 전략이 예상 가능할 때, 자신의 최선택을 선택했을 때 그 결과로 형성된 균형 상태를 말한다. 내시균형이 아니라는 것은 [[순수 전략]](pure strategy)에서 존재하지 않음을 의미한다. 이때 순수 전략이란 가위바위보 게임처럼 100% 확률로 선택하게 되는 전략을 말하는데 [[죄수의 딜레마]]와 달리 확률을 따지지 않으며 타 플레이어들이 이 전략을 선택하고 있는 상황 하에서 자신의 전략을 바꾸는 것이 득인 플레이어가 한 명 이상 존재한다는 뜻이다. |
| − | |||
==개요== | ==개요== | ||
| − | ''' | + | '''내시균형'''(Nash equilibrium)은 게임이론의 한 형태로 1994년 노벨경제학상을 공동 수상한 수학자 [[존 내시]]((John Forbes Nash. Jr)가 개발했다. 이는 각 참여자가 상대방의 전략을 주어진 것으로 보고 자신에게 최적인 전략을 선택할 때 그 결과가 균형을 이루는 최적 전략의 집합을 말한다. 이러한 전략 구성이 두 참여자에 의해 모두 예측되었을 때 이 게임은 내시균형에 도달하게 된다. 내시균형에 이르게 된다면 참여자는 전략을 수정할 필요가 없다. 오늘날 정치적 협상이나 경제 분야에서 전략으로 많이 활용되고 있다. 내시균형의 대표적인 적용 예시로는 '''죄수의 딜레마'''(Prisoner’s Dilemma)가 있다. <ref>박은태,〈[https://terms.naver.com/entry.nhn?docId=779583&cid=42085&categoryId=42085 죄수의 딜레마]〉, 《경제학사전》, 2011-03-09</ref> |
| + | 플레이어가 타 플레이어의 전략을 알고 있고 그들이 전략을 바꾸지 않는다고 할 때, 자신의 전략을 바꾸는 게 이득인지에 대한 질문의 답으로 그렇다고 한다면 그 전략은 내시균형이 아니고 그렇지 않다고 한다면 그 전략은 내시균형이다. | ||
| + | |||
| + | ==역사== | ||
| + | 내시균형은 1938년 [[쿠르노]](Antoine Augustin Cournot)의 [[과점이론]]에서 처음으로 사용됐다. 과점이론에서 기업은 이익 극대화를 위해 산출물의 생산량을 고민한다. 이때 타 기업들의 산출량을 크게 고려한다. 쿠르노 균형에서 각 기업들의 산출물 극대화는 [[순수 전략]]인 내시균형에 속한다. | ||
| + | |||
| + | [[폰 노이만]](John von Veumann)과 모르겐슈타른(Oskar Morgenstern)이 1944년 발표한 [[게임이론과 경제행동]](The Theory of Games and Economic Behavior)에서 [[내시균형 혼합전략]]이 소개되었다. 그러나 유한한 행동에서의 [[제로섬 게임]]에서만 존재한다고 한정했다. 이를 1951년 내시가 글 '[[비협조게임]]'(Non-Cooperative Games)에서 유한한 행동의 묶음에서 적어도 하나 이상의 내시균형이 반드시 존재함을 증명하며 확장했다. 내시의 단서는, "n개의 경기자들의 균형점은 타 경기자들이 그들의 전략을 고수한 채 혼합전략을 이용해 수익을 극대화하는 점에서 이루어진다. 이는 연속 전략함수를 타 전략에 생산하며 불필요한 옵션들의 확장은 궁극적으로 균형점이나 고정점에 존재한다."로 폰 노이만의 [[균형정의]]보다 더 일반적이다. | ||
| + | |||
| + | [[라인하드 젤텐]](Reinhard Selten)은 1965년 [[신빙성 없는 위험]]에 근거를 둔 균형을 제거한 [[부분게임완전균형]](Sub Game Perfect Equilibrium)에서 게임이 반복되거나 완전정보를 갖지 않을 때의 상황에서의 개선책을 발표했다.<ref>〈[https://ko.wikipedia.org/wiki/%EB%82%B4%EC%8B%9C_%EA%B7%A0%ED%98%95 내시 균형]〉, 《위키피디아》, 2018-07-30</ref> | ||
==특징== | ==특징== | ||
| − | * | + | * 내시균형은 1개 이상일 수 있다. |
| − | * | + | * 내시균형과 파레토최적은 다를 수 있다. |
| − | [[파레토최적]]이란 타인의 이익을 감소시키지 않고서는 어느 한 사람의 이익을 증가시키는 것이 불가능할 정도로 자원이 효율적으로 배분된 상태를 의미한다. | + | |
| − | * [[순수전략]] | + | [[파레토최적]]이란 타인의 이익을 감소시키지 않고서는 어느 한 사람의 이익을 증가시키는 것이 불가능할 정도로 자원이 효율적으로 배분된 상태를 의미한다. 내시균형이 파레토최적이 아니라는 것은 '개인적인 합리성'이 늘 '집단적 합리성'은 아님을 의미한다.<ref>히키신,〈[https://hichy.tistory.com/entry/%EA%B2%8C%EC%9E%84-%EC%9D%B4%EB%A1%A0-%EB%82%B4%EC%89%AC-%EA%B7%A0%ED%98%95-%ED%8C%8C%EB%A0%88%ED%86%A0-%ED%9A%A8%EC%9C%A8%EC%84%B1-%EC%82%AC%EC%8A%B4%EC%82%AC%EB%83%A5-%EA%B2%8C%EC%9E%84 파레토최적 ]〉, 《티스토리》, 2017-02-15</ref> |
| + | * [[순수전략]] 내시균형은 존재하지 않을 수 있다. | ||
순수 전략이란 가위바위보 게임처럼 100% 확률로 선택하게 되는 전략을 말하는데 죄수의 딜레마와 달리 확률을 따지지 않으며 타 플레이어들이 이 전략을 선택하고 있는 상황 하에서 자신의 전략을 바꾸는 것이 득인 플레이어가 한 명 이상 존재한다는 뜻이다. | 순수 전략이란 가위바위보 게임처럼 100% 확률로 선택하게 되는 전략을 말하는데 죄수의 딜레마와 달리 확률을 따지지 않으며 타 플레이어들이 이 전략을 선택하고 있는 상황 하에서 자신의 전략을 바꾸는 것이 득인 플레이어가 한 명 이상 존재한다는 뜻이다. | ||
| − | * [[혼합전략]] | + | * [[혼합전략]] 내시균형은 항상 존재한다. |
혼합 전략이란 여러 개의 전략을 미리 선택된 확률에 따라 무작위로 선택하는 것을 의미한다. | 혼합 전략이란 여러 개의 전략을 미리 선택된 확률에 따라 무작위로 선택하는 것을 의미한다. | ||
| 17번째 줄: | 25번째 줄: | ||
===죄수의 딜레마=== | ===죄수의 딜레마=== | ||
| − | 죄수의 | + | [[죄수의 딜레마]]란 용의자 두 명을 격리해 따로 심문하며 둘 다 자백하지 않을 경우엔 제일 적은 형량을, 둘 다 자백할 경우는 그보다 높은 형량을, 한 명만 자백할 경우 그 한 명만 높은 형량을 제안했을 때 그들이 겪는 딜레마를 말한다. 두 명의 용의자가 최선의 선택을 한다면 둘 다 자백하지 않고 제일 적은 형량을 받겠지만, 상대를 신뢰하지 못하고 차선을 선택한다. 자백을 하기로 결정했다면, 그때부턴 상대방의 선택에 상관없이 달라질 것이 없어지며 이 균형을 내시균형이라고 한다. |
| − | 존 | + | |
| − | 죄수의 딜레마에서 각자가 자신의 이익을 추구함으로써 도달하게 되는 균형점은 [[파레토최적]]이 아닌 비효율적인 상태이다. | + | 존 내시는 정보가 차단되고 여러 상황이 동시다발적으로 발생할 때, 사람들은 자신에게 이익이 되는 최선이 아니라 타인의 행동과 전략을 예상하고 그에 대응하는 차선택을 택한다고 주장했다. |
| + | 죄수의 딜레마에서 각자가 자신의 이익을 추구함으로써 도달하게 되는 균형점은 [[파레토최적]]이 아닌 비효율적인 상태이다. 내시는 내시균형을 통해 [[애덤 스미스]]의 [[보이지 않은 손]]이 실패할 수도 있다고 증명했다. | ||
===미니맥스 정리=== | ===미니맥스 정리=== | ||
| − | + | 내시는 [[폰 노이먼]]의 [[미니맥스 정리]]를 확장하기 위해 폰 노이먼을 찾아갔으나 부정당했다. 미니맥스 정리는 플레이어가 2명이고 서로의 이득의 합이 0이 되는 [[제로섬]] 규칙이기에 한정적이나 내시균형은 3명 이상의 플레이어가 게임에 참가하고 그들의 이득의 합이 0이 아닌 비제로섬 규칙이기에 미니맥스 정리에 비해 더 일반적인 경우로 확장되어 있다. | |
| − | 미니맥스 정리는 플레이어가 2명이고 서로의 이득의 합이 0이 되는 [[제로섬]] 규칙이기에 한정적이나 | ||
===크루노 균형=== | ===크루노 균형=== | ||
| − | [[크루노]]는 최적반응의 개념을 균형 안정의 분석에서 도입한다. | + | [[크루노]]는 최적반응의 개념을 균형 안정의 분석에서 도입한다. 내시균형의 정의는 크루노의 정의보다 넓은 개념이다. |
| + | |||
| + | ==예시== | ||
| + | ===비둘기 - 매 게임 (hawk-dove game)=== | ||
| + | * '매'가 되는 생존전략 | ||
| + | 상대를 만나면 전력을 다해 싸우며, 한쪽이 심각한 상처를 입으면 끝난다. (-100의 성과) | ||
| + | |||
| + | * '비둘기'가 되는 생존전략 | ||
| + | 매를 만나면 즉시 피하며 진다. 같은 비둘기를 만나면 싸우는데, 극단적인 폭력을 피하는 방식이다. (이기든 지든 모두 -10의 성과) | ||
| + | |||
| + | * 비둘기 혹은 매끼리 싸울 때 승률은 50%이며 싸움 자체에서 발생하는 성과와는 별도로, 싸움에서 이기면 50, 지면 0의 성과를 얻는다. | ||
| + | |||
| + | ===라우팅 게임=== | ||
| + | * 교통 네트워크의 각 출발-목적지 쌍 (s, t)의 복수개의 s-t 경로가 존재한다. | ||
| + | |||
| + | * 각 경로마다 통행 비용이 존재하고, 통행자들은 각자 비용이 최소가 되는 경로를 선택한다. 이를 ‘selfish routing,’ 즉, 개별적 라우팅이라고 한다. 통행자들의 개별적 라우팅이 전체 네트워크의 통행 흐름을 결정한다. | ||
| + | |||
| + | * 역으로, 통행량은 경로의 비용을 결정하는 요인 중에 하나다. 비용 요인 중에는 통행시간, 환승의 편의성, 요금 등도 존재한다. 통행량이 특별한 점은, 이를통해 통행자들의 경로선택이 상호영향을 준다는 것이다. 경로선택 문제는 통행자들간의 게임이 된다. 따라서, 각 경로의 통행량은 라우팅 게임의 균형이 된다. | ||
{{각주}} | {{각주}} | ||
| 32번째 줄: | 57번째 줄: | ||
==참고자료== | ==참고자료== | ||
* 박은태, 〈[https://terms.naver.com/entry.nhn?docId=779583&cid=42085&categoryId=42085 죄수의 딜레마]〉, 《경제학사전》 | * 박은태, 〈[https://terms.naver.com/entry.nhn?docId=779583&cid=42085&categoryId=42085 죄수의 딜레마]〉, 《경제학사전》 | ||
| − | * 히키신,〈[https://hichy.tistory.com/entry/%EA%B2%8C%EC%9E%84-%EC%9D%B4%EB%A1%A0-%EB%82%B4%EC%89%AC-%EA%B7%A0%ED%98%95-%ED%8C%8C%EB%A0%88%ED%86%A0-%ED%9A%A8%EC%9C%A8%EC%84%B1-%EC%82%AC%EC%8A%B4%EC%82%AC%EB%83%A5-%EA%B2%8C%EC%9E%84 파레토최적 ]〉, | + | *〈[https://ko.wikipedia.org/wiki/%EB%82%B4%EC%8B%9C_%EA%B7%A0%ED%98%95 내시 균형]〉, 《위키피디아 |
| − | == | + | * 히키신,〈[https://hichy.tistory.com/entry/%EA%B2%8C%EC%9E%84-%EC%9D%B4%EB%A1%A0-%EB%82%B4%EC%89%AC-%EA%B7%A0%ED%98%95-%ED%8C%8C%EB%A0%88%ED%86%A0-%ED%9A%A8%EC%9C%A8%EC%84%B1-%EC%82%AC%EC%8A%B4%EC%82%AC%EB%83%A5-%EA%B2%8C%EC%9E%84 파레토최적 ]〉, 《티스토리》 |
| + | |||
| + | ==같이 보기== | ||
* [[게임이론]] | * [[게임이론]] | ||
| + | |||
| + | {{알고리즘|검토 필요}} | ||
2019년 7월 18일 (목) 14:06 기준 최신판
내시균형(Nash equilibrium)이란 상대 플레이어의 전략이 예상 가능할 때, 자신의 최선택을 선택했을 때 그 결과로 형성된 균형 상태를 말한다. 내시균형이 아니라는 것은 순수 전략(pure strategy)에서 존재하지 않음을 의미한다. 이때 순수 전략이란 가위바위보 게임처럼 100% 확률로 선택하게 되는 전략을 말하는데 죄수의 딜레마와 달리 확률을 따지지 않으며 타 플레이어들이 이 전략을 선택하고 있는 상황 하에서 자신의 전략을 바꾸는 것이 득인 플레이어가 한 명 이상 존재한다는 뜻이다.
목차
개요[편집]
내시균형(Nash equilibrium)은 게임이론의 한 형태로 1994년 노벨경제학상을 공동 수상한 수학자 존 내시((John Forbes Nash. Jr)가 개발했다. 이는 각 참여자가 상대방의 전략을 주어진 것으로 보고 자신에게 최적인 전략을 선택할 때 그 결과가 균형을 이루는 최적 전략의 집합을 말한다. 이러한 전략 구성이 두 참여자에 의해 모두 예측되었을 때 이 게임은 내시균형에 도달하게 된다. 내시균형에 이르게 된다면 참여자는 전략을 수정할 필요가 없다. 오늘날 정치적 협상이나 경제 분야에서 전략으로 많이 활용되고 있다. 내시균형의 대표적인 적용 예시로는 죄수의 딜레마(Prisoner’s Dilemma)가 있다. [1] 플레이어가 타 플레이어의 전략을 알고 있고 그들이 전략을 바꾸지 않는다고 할 때, 자신의 전략을 바꾸는 게 이득인지에 대한 질문의 답으로 그렇다고 한다면 그 전략은 내시균형이 아니고 그렇지 않다고 한다면 그 전략은 내시균형이다.
역사[편집]
내시균형은 1938년 쿠르노(Antoine Augustin Cournot)의 과점이론에서 처음으로 사용됐다. 과점이론에서 기업은 이익 극대화를 위해 산출물의 생산량을 고민한다. 이때 타 기업들의 산출량을 크게 고려한다. 쿠르노 균형에서 각 기업들의 산출물 극대화는 순수 전략인 내시균형에 속한다.
폰 노이만(John von Veumann)과 모르겐슈타른(Oskar Morgenstern)이 1944년 발표한 게임이론과 경제행동(The Theory of Games and Economic Behavior)에서 내시균형 혼합전략이 소개되었다. 그러나 유한한 행동에서의 제로섬 게임에서만 존재한다고 한정했다. 이를 1951년 내시가 글 '비협조게임'(Non-Cooperative Games)에서 유한한 행동의 묶음에서 적어도 하나 이상의 내시균형이 반드시 존재함을 증명하며 확장했다. 내시의 단서는, "n개의 경기자들의 균형점은 타 경기자들이 그들의 전략을 고수한 채 혼합전략을 이용해 수익을 극대화하는 점에서 이루어진다. 이는 연속 전략함수를 타 전략에 생산하며 불필요한 옵션들의 확장은 궁극적으로 균형점이나 고정점에 존재한다."로 폰 노이만의 균형정의보다 더 일반적이다.
라인하드 젤텐(Reinhard Selten)은 1965년 신빙성 없는 위험에 근거를 둔 균형을 제거한 부분게임완전균형(Sub Game Perfect Equilibrium)에서 게임이 반복되거나 완전정보를 갖지 않을 때의 상황에서의 개선책을 발표했다.[2]
특징[편집]
- 내시균형은 1개 이상일 수 있다.
- 내시균형과 파레토최적은 다를 수 있다.
파레토최적이란 타인의 이익을 감소시키지 않고서는 어느 한 사람의 이익을 증가시키는 것이 불가능할 정도로 자원이 효율적으로 배분된 상태를 의미한다. 내시균형이 파레토최적이 아니라는 것은 '개인적인 합리성'이 늘 '집단적 합리성'은 아님을 의미한다.[3]
- 순수전략 내시균형은 존재하지 않을 수 있다.
순수 전략이란 가위바위보 게임처럼 100% 확률로 선택하게 되는 전략을 말하는데 죄수의 딜레마와 달리 확률을 따지지 않으며 타 플레이어들이 이 전략을 선택하고 있는 상황 하에서 자신의 전략을 바꾸는 것이 득인 플레이어가 한 명 이상 존재한다는 뜻이다.
- 혼합전략 내시균형은 항상 존재한다.
혼합 전략이란 여러 개의 전략을 미리 선택된 확률에 따라 무작위로 선택하는 것을 의미한다.
비교[편집]
죄수의 딜레마[편집]
죄수의 딜레마란 용의자 두 명을 격리해 따로 심문하며 둘 다 자백하지 않을 경우엔 제일 적은 형량을, 둘 다 자백할 경우는 그보다 높은 형량을, 한 명만 자백할 경우 그 한 명만 높은 형량을 제안했을 때 그들이 겪는 딜레마를 말한다. 두 명의 용의자가 최선의 선택을 한다면 둘 다 자백하지 않고 제일 적은 형량을 받겠지만, 상대를 신뢰하지 못하고 차선을 선택한다. 자백을 하기로 결정했다면, 그때부턴 상대방의 선택에 상관없이 달라질 것이 없어지며 이 균형을 내시균형이라고 한다.
존 내시는 정보가 차단되고 여러 상황이 동시다발적으로 발생할 때, 사람들은 자신에게 이익이 되는 최선이 아니라 타인의 행동과 전략을 예상하고 그에 대응하는 차선택을 택한다고 주장했다. 죄수의 딜레마에서 각자가 자신의 이익을 추구함으로써 도달하게 되는 균형점은 파레토최적이 아닌 비효율적인 상태이다. 내시는 내시균형을 통해 애덤 스미스의 보이지 않은 손이 실패할 수도 있다고 증명했다.
미니맥스 정리[편집]
내시는 폰 노이먼의 미니맥스 정리를 확장하기 위해 폰 노이먼을 찾아갔으나 부정당했다. 미니맥스 정리는 플레이어가 2명이고 서로의 이득의 합이 0이 되는 제로섬 규칙이기에 한정적이나 내시균형은 3명 이상의 플레이어가 게임에 참가하고 그들의 이득의 합이 0이 아닌 비제로섬 규칙이기에 미니맥스 정리에 비해 더 일반적인 경우로 확장되어 있다.
크루노 균형[편집]
크루노는 최적반응의 개념을 균형 안정의 분석에서 도입한다. 내시균형의 정의는 크루노의 정의보다 넓은 개념이다.
예시[편집]
비둘기 - 매 게임 (hawk-dove game)[편집]
- '매'가 되는 생존전략
상대를 만나면 전력을 다해 싸우며, 한쪽이 심각한 상처를 입으면 끝난다. (-100의 성과)
- '비둘기'가 되는 생존전략
매를 만나면 즉시 피하며 진다. 같은 비둘기를 만나면 싸우는데, 극단적인 폭력을 피하는 방식이다. (이기든 지든 모두 -10의 성과)
- 비둘기 혹은 매끼리 싸울 때 승률은 50%이며 싸움 자체에서 발생하는 성과와는 별도로, 싸움에서 이기면 50, 지면 0의 성과를 얻는다.
라우팅 게임[편집]
- 교통 네트워크의 각 출발-목적지 쌍 (s, t)의 복수개의 s-t 경로가 존재한다.
- 각 경로마다 통행 비용이 존재하고, 통행자들은 각자 비용이 최소가 되는 경로를 선택한다. 이를 ‘selfish routing,’ 즉, 개별적 라우팅이라고 한다. 통행자들의 개별적 라우팅이 전체 네트워크의 통행 흐름을 결정한다.
- 역으로, 통행량은 경로의 비용을 결정하는 요인 중에 하나다. 비용 요인 중에는 통행시간, 환승의 편의성, 요금 등도 존재한다. 통행량이 특별한 점은, 이를통해 통행자들의 경로선택이 상호영향을 준다는 것이다. 경로선택 문제는 통행자들간의 게임이 된다. 따라서, 각 경로의 통행량은 라우팅 게임의 균형이 된다.
각주[편집]
참고자료[편집]
같이 보기[편집]
| ||||||||||||||||||||||||||||||||||
