민속 정리(게임 이론)

게임 이론에서, 민속 이론은 반복된 게임에서 풍부한 내쉬 균형 잡힌 보상 프로필을 설명하는 이론의 한 종류다.^[1] (Friedman 1971) 원래의 민속정리는 무한 반복 놀이의 모든 나시 평형주의 보상에 관한 것이었다. 이 결과를 민속 정리라고 부른 것은 1950년대 게임 이론가들 사이에 널리 알려졌기 때문인데, 이는 아무도 이를 출판하지 않았음에도 불구하고 말이다. 프리드먼의 (1971) 정리는 무한히 반복되는 게임의 어떤 서브게임 퍼펙트 나시 평형(SPE)의 보상에 관한 것으로서, 그래서 나시 평형 개념인 서브게임 퍼펙트 나시 평형(subgame-perfect Nash 평형)을 내시 평형보다 더 강하게 사용함으로써 원래의 포크 정리를 강화한다.^[2]

민속 정리에서는 선수들이 충분히 인내하고 멀리 내다본다면( $\delta \to 1$ 즉, 할인율 $\delta \to 1$ → 1 ${\displaystyle \delta \to$ 1 $})$ 반복적인 상호작용을 통해 SPE 평형에서 사실상 평균적인 보수가 발생할 수 있다고 제안한다.^[3] "사실상 임의의 것"은 기술적으로 "실현 가능한 것"과 "개별적으로 이성적인 것"으로 정의된다.

예를 들어, 원샷 프리즈 딜레마에서 두 선수가 협력하는 것은 내시 평형이 아니다. 유일한 내시 평형은 두 선수 모두 탈주하는 것인데, 이것은 상호 미니맥스 프로필이기도 하다. 한 민간정리는 무한 반복된 게임 버전에서 플레이어가 충분히 인내심을 갖도록 제공하면 두 플레이어가 평형 경로에서 협력할 수 있는 내시 평형이 존재한다고 말한다. 그러나 알려진 한정된 횟수로 경기가 반복될 경우 역유도는 두 선수 모두 각 기간에 원샷 나시 평형을, 즉 매번 이탈한다는 것을 보여준다.

설정 및 정의

우리는 n플레이어 게임인 스테이지 게임으로도 알려진 기본 게임으로 시작한다. 이 게임에서 각 플레이어는 선택할 수 있는 행동이 아주 많고, 상대 플레이어의 선택을 모르는 상태에서 동시에 자신의 선택을 하게 된다. 선수들의 집단적 선택은 선수 개개인에 대한 보수 프로필, 즉 선수 개개인에 대한 보상으로 이어진다. 집단 선택에서 보상 프로파일에 이르는 매핑은 선수들에게 알려져 있으며, 각 참가자는 그들의 보상을 최대화하는 것을 목표로 한다. 집단 선택이 x로 표시되면 플레이어 i의 유틸리티라고도 알려진 내가 받는 보수는 $u_{i}(x)$ ( $u_{i}(x)$ ) $u_{i}(x)$ 에 의해 표시된다 $u_{i}(x)$

그리고 나서 우리는 이 스테이지 게임의 반복을, 정밀하게 또는 무한하게 여러 번 고려한다. 각각의 반복에서 각 플레이어는 스테이지 게임 옵션 중 하나를 선택하고, 그 선택을 할 때, 그들은 이전 반복에서 다른 플레이어의 선택을 고려할 수 있다. 이 반복된 게임에서, 선수들 중 한 명을 위한 전략은 사전 반복에서 다른 모든 플레이어의 선택을 바탕으로 스테이지 게임의 각 반복에서 플레이어의 선택을 명시하는 결정론적 규칙이다. 선수 개개인의 전략 선택은 전략 프로필로, 반복된 경기에 대한 성과급 프로필로 이어진다. 그러한 전략 프로파일이 아래에 요약된 지불 프로파일로 변환될 수 있는 여러 가지 다른 방법이 있다.

반복된 게임의 모든 내쉬 평형 지불 프로필은 다음 두 가지 특성을 만족시켜야 한다.

1. 개인의 합리성: 보상은 약하게 구성 스테이지 게임의 미니맥스 보상 프로필을 지배해야 한다. 즉, 각 플레이어의 평형 보수는 최소한 해당 플레이어의 최소 지급액만큼 커야 한다. 미니맥스보다 적은 보수를 달성하는 선수는 모든 역사에서 단순히 미니맥스 전략을 구사함으로써 항상 일탈할 동기를 부여받기 때문이다.

2. 실현 가능성: 보수는 스테이지 게임의 가능한 보상 프로파일의 볼록한 조합이어야 한다. 반복 경기에서의 보수는 기본 경기에서의 가중 평균에 불과하기 때문이다.

민속적 이론은 주장과 부분적으로 상충된다: 그들은 특정한 조건(각 민속 정리에서는 다른 것)에서는 개별적으로 합리적이고 실현 가능한 모든 보수 프로파일이 반복된 게임의 내시 평형 보수 프로파일로 실현될 수 있다고 말한다.

다양한 민속적 이론이 있다; 어떤 것은 미세하게 반복된 게임과 관련이 있는 반면 다른 것은 무한 반복된 게임과 관련이 있다.^[4]

할인 없이 무한 반복 게임

할인되지 않은 모델에서 선수들은 인내심이 강하다. 그들은 다른 시간대에 유틸리티를 구별하지 않는다. 따라서, 반복된 게임에서의 그들의 효용성은 기본 게임에서의 효용의 합으로 표현된다.

게임이 무한할 때 무한 반복 게임에서 유틸리티에 대한 공통 모델은 평균 효용보다 열등한 한계다. 게임이 결과 $x_{t}$ $x_{t}$ ${\$ 의 경로로 귀결되는 경우 $x_{t}$ 여기서 $x_{t}$ $x_{t}$ ${\$ 는 반복 t(t=0,1,2,...)에서 플레이어의 집합적 선택을 나타내는 $x_{t}$ 것으로, 플레이어 i의 효용은 다음과 같이 정의된다.

U_{i}=\liminf _{T\to \inflt}{\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t}),

여기서 ${\$ 는 플레이어 i의 기본 게임 유틸리티 기능이다 $u_{i}$ .

할인 없이 무한 반복하는 게임을 흔히 '슈퍼게임'이라고 부른다.

이 경우의 민속적 정리는 매우 간단하고 사전 조건이 없다: 기본 게임에서 개별적으로 합리적이고 실현 가능한 모든 지불 프로파일은 반복 게임에서 나시 평형 지불 프로파일이다.

그 증거는 암울하거나^[5] 암울한 방아쇠^[6] 전략이라고 불리는 것을 사용한다. 모든 플레이어는 규정된 동작을 하는 것으로 시작하고 누군가가 이탈할 때까지 계속한다. 내가 이탈하면 다른 모든 플레이어가 나를 영원히 괴롭히는 액션으로 바꾼다. 편차로 인한 1단계 이득은 선수 i의 총 효용성에 0을 기여한다. 이탈하는 선수의 효용은 그의 미니맥스보다 높을 수 없다. 따라서 모든 플레이어가 의도된 경로를 유지하며 이것은 실제로 내시 평형이다.

서브게임 완성도

위의 나시 평형은 항상 서브게임 완벽하지는 않다. 처벌에 비용이 많이 든다면 처벌 위협은 신빙성이 없다.

서브게임 퍼펙트 밸런스는 조금 더 복잡한 전략이 필요하다.^[5]^[7]^{: 146–149} 처벌은 영원히 지속되어서는 안 되며, 일탈로 얻은 이익을 없애기에 충분한 유한한 시간만 지속되어야 한다. 이후 다른 선수들은 평형대로 돌아가야 한다.

평균 제한 기준은 유한한 시간의 처벌이 최종 결과에 영향을 미치지 않음을 보장한다. 따라서, 제한시간 처벌은 게임에서 완벽한 평형이다.

연합 서브게임 퍼펙트 평형률:^[8] 어떤 연립도 일탈로부터 얻을 수 없다면 평형을 연립 나시 평형이라고 한다. 어떤 역사를 뒤엎는 것에서 어떤 연합도 얻을 수 없다면 그것은 연합 서브게임 퍼펙트 평형이라고 불린다.^[9] 평균 제한 기준의 경우, 지불 프로파일은 연립-내시-평형화 또는 연립-하위-완벽-평형화-평형화(Pareto 효율적이고 약한 연합-개별-합병)에서 달성할 수 있다.^[10]

추월

일부 저자들은 평균 제한 기준이 비현실적이라고 주장한다. 왜냐하면 그것은 유한한 시간 범위의 유틸리티가 총 효용성에 0을 기여한다는 것을 의미하기 때문이다. 그러나 유한한 시간 범위의 유틸리티가 양의 값을 기여하고 그 값이 할인되지 않는다면 유한한 숫자 효용을 무한의 결과 순서에 귀속시키는 것은 불가능하다. 이 문제에 대한 가능한 해결책은 각 무한 결과 시퀀스에 대해 숫자 유틸리티를 정의하는 대신 두 무한 시퀀스 사이의 선호 관계를 정의한다는 것이다. 에이전트 $i$ ${\displaystyle i}($ 강력하게)는 다음과 같은 경우 시퀀스 $x_{t}$ $x_{t}$ ${\$ 보다 $y_{t}$ $y_{t}$ y ${\$ 를 선호한다고 한다 $x_{t}$ ^[6]^[7]^{: 139}^[8]

\liminf _{T\to \infit }\sum _{t=0}^{T}(u_{i})(y_{t}-u_{i})(x_{t})>0

For example, consider the sequences $u_{i}(x)=(0,0,0,0,\ldots )$ and $u_{i}(y)=(-1,2,0,0,\ldots )$ . According to the limit-of-means criterion, they provide the same utility to player i, but according to the overtaking criterion, $y$ $y$ 이(가) 플레이어 i의 $x$ 경우 $x$ $x$ 보다 낫다 $y$ . 자세한 내용은 추월 기준을 참조하십시오.

추월 기준이 있는 민간 이론은 평균 한계 기준보다 약간 약하다. 엄격히 개별적으로 합리적인 결과만 내쉬 평형에서 얻을 수 있다. 대리인이 이탈하면 단기적으로 이득을 얻는데, 처벌이 합의 경로보다 엄격하게 효용성을 적게 부여해야 이 이득이 소멸될 수 있기 때문이다. 추월 기준으로는 다음과 같은 민간 이론이 알려져 있다.

엄격한 고정형 평형:^[6] 나시 평형은 각 플레이어가 자신이 벗어날 수 있는 다른 어떤 순서보다 평형 상태에서 달성되는 결과의 무한 순서를 엄격히 선호할 경우 엄격한 평형이라고 불린다. 나시 평형은 각 시간 주기마다 결과가 같으면 정지상태라고 한다. 모든 플레이어의 결과가 플레이어의 미니맥스 결과보다 엄격히 우수할 경우, 엄격한 스테이션 평형 상태에서 결과를 달성할 수 있다.^[11]
엄격한 고정식 서브게임 퍼펙트 평형도:^[6] 모든 플레이어가 플레이어의 미니맥스 결과보다 결과가 엄격히 우수할 경우, 엄격한 스테이션-하위 게임-완벽한 평형평형에서 결과를 달성할 수 있다(참고: "만약의 경우" 결과가 아님). 추월 기준과 함께 서브게임 퍼펙트 평형을 이루려면 합의 경로에서 이탈한 선수뿐 아니라 일탈자 처벌에 협조하지 않는 선수도 모두 처벌해야 한다.^[7]^{: 149–150}
- "정역 평형" 개념은 한정된 수의 결과가 주기적으로 반복되는 "주기적 평형"으로 일반화될 수 있으며, 한 기간의 보수는 결과에서 보상의 산술적 평균이다. 그 평균보수는 최소보상을 엄격히 초과해야 한다.^[6]
엄격한 고정식 연합:^[8] 추월 기준에서, 만약 결과가 연립-내시-균형화에서 달성될 수 있다면, 그것은 파레토 효율적이고 약하게-개별적인 연합이다. 반면에 파레토 효율적이고 강력한 연합인^[12] 경우-개별적으로 그것은 엄격한 역-연방 평형화에서 얻을 수 있다.

할인이 적용된 무한 반복 게임

무한정 반복된 게임에서 플레이어의 보수는 할인율 0 < Δ < 1:2>로 평균 할인된 기준에 의해 주어진다고 가정하자.

U_{i}=(1-\delta )\sum _{t\geq 0}\delta ^{t}u_{i}(x_{t}),

할인율은 선수들이 얼마나 인내심을 갖고 있는지를 나타낸다. $\delta \rightarrow 1$ → $\delta \rightarrow 1$ {\displaystyle \ $delta$ \rightarrow $1}$ 이(가) $(1-\delta )$ Δ → 1 ${\displaystyle \delta \rightarrow$ 1 $\delta \rightarrow 1$ 일 때 보수가 제한되도록 인자 $(1-\delta )$ (1 - $){\delta$ \delta \rigarrow 1 $}$

이 경우의 민속적 정리는 반복된 게임에서 지불 프로파일이 minmax 지불 프로파일(즉, 각 플레이어가 minmax 지불 프로파일보다 엄격히 더 많이 받는 것)을 엄격히 지배하도록 요구한다.

minmax payoff 프로필을 엄격하게 지배하는 payoff profile u와 함께 스테이지 게임의 전략 프로파일이 되자. u와의 게임의 나시 평형을 다음과 같이 결과적인 보상 프로파일로 정의할 수 있다.

1. 모든 플레이어는 a로 시작하고 일탈이 발생하지 않으면 a로 계속 플레이한다.

2. 만일 한 명의 선수, 즉 선수 i가 이탈했다면, minmax의 전략 프로파일 m을 영원히 실행한다.

3. 다자간 편차는 무시하라.

만약 선수가 1을 따라가면서 각 스테이지마다 그의 미니맥스보다 더 많은 돈을 받는다면, 처벌로 인한 잠재적 손실은 다음과 같다.

{\frac {1}{1-\flaim }}\varepsilon .

Δ가 1에 가까우면, 이것은 어떤 유한한 단단계 이득보다 크므로 전략이 내시 평형 상태가 된다.

이 민간 정리의^[4] 대안적인 진술은 평형적 지급 프로파일이 개별적으로 합리적일 수 있는 지급 프로파일이 될 수 있도록 허용한다; 그것은 오직 개별적으로 합리적으로 실현 가능한 지급 프로파일이 존재하도록 요구하며, 이는 최소 지급 프로파일을 엄격히 지배한다. 그러면 민속 정리는 원하는 정밀도로 평형적으로 u에 접근하는 것이 가능하다고 보장한다(각 for마다 지불 프로파일이 u로부터 ε 거리인 나시 평형이 존재한다).

서브게임 완성도

할인된 게임에서 완벽한 평형을 이루는 것은 할인되지 않은 게임보다 더 어렵다. 처벌 비용은 (평균한도 기준과 마찬가지로) 사라지지 않는다. 할인 요소가 앞으로 처벌을 현재와 무관하게 만들기 때문에 (추월 기준과 같이) 비징계자를 끝없이 처벌하는 것이 항상 가능한 것은 아니다. 그러므로, 다른 접근법이 필요하다: 처벌받는 사람들은 보상을 받아야 한다.

이를 위해서는 실현 가능한 성과급 프로파일의 집합이 전체 치수이고 최소-최대 프로파일이 내부에 있다는 추가적인 가정이 필요하다. 전략은 다음과 같다.

1. 모든 플레이어는 a로 시작하고 일탈이 발생하지 않으면 a로 계속 플레이한다.

2. 선수 i라고 하는 선수가 있다면, N 기간 동안 minmax한 전략 프로파일 m을 실행한다. (플레이어가 1단계에서 벗어날 동기가 없을 정도로 충분히 큰 N과 Δ를 선택하십시오.)

3. 2단계에서 이탈한 선수가 없을 경우, 모든 선수 j i i는 이후 영원히 j의 최소값보다 높은 보상을 받는 반면, 선수 i는 계속해서 최소값을 받는다. (이곳에서는 최대치 및 내부 가정이 필요하다.)

4. 선수가 2단계에서 이탈하면 모든 플레이어가 j를 대상으로 2단계를 재시작한다.

5. 다자간 편차는 무시하라.

선수 J ≠ 나는 이제 처벌 단계 2에서 벗어날 동기가 없다. 이것은 서브게임 퍼펙트 포크 정리를 증명한다.

할인 없이 반복된 게임

T 횟수가 반복되는 게임에서 선수 i의 보수는 다음과 같은 간단한 산술 평균에 의해 주어진다고 가정한다.

U_{i}={\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t})

이 경우에 대한 민속적 정리에는 다음과 같은 추가 요건이 있다.^[4]

기본 게임에서는 모든 플레이어 i에 대해 미니맥스보다 나시 평형

E_{i}

{\

가

E_{i}

엄격하게 더 좋다.

이 요건은 할인된 무한 게임 요건보다 강하며, 이는 할인되지 않은 무한 게임의 요건보다 강하다.

마지막 단계 때문에 이 요구사항이 필요하다. 마지막 단계에서 유일하게 안정된 결과는 기본 게임 내시 평형이다. 선수가 나시 평형으로부터 얻는 것이 아무것도 없다고 가정하자. (내시 평형에서 얻는 이익은 미니맥스밖에 없기 때문이다.) 그렇다면 그 선수를 처벌할 방법이 없다.

한편, 모든 플레이어에 대해 minmax보다 엄격히 나은 기본 평형이 있다면, 반복적인 경기 평형은 두 단계로 구성될 수 있다.

첫 번째 단계에서는 플레이어가 필요한 빈도로 전략을 바꾸어 원하는 성과급 프로파일에 근사하게 된다.
마지막 단계에서는 선수 개개인이 선호하는 평형을 차례대로 구사한다.

마지막 단계에서는 이미 기본 경기 평형이기 때문에 어느 선수도 이탈하지 않는다. 1단계에서 요원이 이탈하면 마지막 단계에서 미니맥스로 처벌할 수 있다. 게임이 충분히 길면 마지막 단계의 효과는 무시할 수 있기 때문에 평형 보수는 원하는 프로파일에 접근한다.

적용들

민속적 이론은 다양한 분야에 적용될 수 있다. 예를 들면 다음과 같다.

인류학: 모든 행동이 잘 알려져 있고, 공동체의 구성원들이 계속 서로 상대해야 한다는 것을 알고 있는 공동체에서, 공동체의 개인이 그들보다 공동체에 남아 있는 것이 더 나은 한, 어떤 행동의 패턴(전통, 금기 등)도 사회 규범에 의해 유지될 수 있다. 공동체를 떠나고 있다(최소 조건).
국제정치=국가 간 협정은 효과적으로 집행될 수 없다. 그러나 국가 간 관계는 장기적이고 국가 간에는 서로 "미니맥스 전략"을 사용할 수 있기 때문에 유지된다. 이러한 가능성은 종종 관련 국가의 할인율에 따라 달라진다. 한 나라가 매우 조급하면(향후 결과에 거의 관심을 두지 않는다) 처벌(또는 신뢰할 수 있는 방법으로 처벌)하기 어려울 수 있다.^[5]

반면, MIT 경제학자 프랭클린 피셔는 민속적 정리가 긍정적인 이론이 아니라고 지적했다.^[13] 예를 들어 과점행동을 고려할 때, 민속적 정리는 기업이 무엇을 할 것인가를 경제학자에게 말해주는 것이 아니라, 오히려 비용 및 수요 기능이 일반적인 과점 이론에 충분치 않으며, 경제학자들은 그들의 이론에 과점이 작용하는 맥락을 포함해야 한다.^[13]

2007년, 보그스 외 연구진은, 민속적 정리에도 불구하고, 일반적인 사례에서 반복적인 게임을 위한 내쉬 평형도를 계산하는 것이 PPAD 복잡성 등급에 있는 문제인 원샷 유한 게임을 위한 내시 평형도를 계산하는 것보다 쉽지 않다는 것을 증명했다.^[14] 이것의 실질적인 결과는 일반 사례에서 민속적 이론에 의해 요구되는 전략을 계산하는 효율적인 (폴리노멀 타임) 알고리즘이 알려져 있지 않다는 것이다.

민속 정리 요약

다음 표는 여러 측면에서 다양한 민속적 이론들을 비교한다.

Horizon – 스테이지 게임이 여러 번 반복되는지 무한정 반복되는지 여부
유틸리티 – 반복된 게임에서 플레이어의 유틸리티가 스테이지 게임 반복에서 플레이어의 유틸리티를 통해 결정되는 방식.
G(스테이지 게임)에 대한 조건 – 정리가 작동하기 위해 원샷 게임에서 보유해야 하는 기술적 조건이 있는지 여부.
x에 대한 조건(반복된 게임의 목표 지불 벡터) – 정리가 개별적으로 합리적이고 실현 가능한 지불 벡터 또는 이들 벡터의 하위 집합에서만 작동하는지 여부.
평형 유형 – 모든 조건이 충족되면, 정리(Nash) 또는 서브게임 퍼펙트(Subgame Perfect)에 의해 어떤 평형이 보장되는가?
벌칙 유형 – 선수가 이탈하지 않도록 하기 위해 어떤 벌칙 전략을 사용하는가?

게시자	지평선	유틸리티	G 조건	x에 대한 조건	보증	평형형형	벌칙형
베노이트&크리스나^[15]	유한( $T$ $T$ )	산술평균	모든 선수에게 있어 최소타스보다 훨씬 더 나은 평형적 보수가 있다.	없음	For all $\varepsilon >0$ there is $T_{0}\in \mathbb {N}$ such that, if $T\geq T_{0}$ , for every $x$ there is equilibrium with payoff $\varepsilon$ -close to $x$ .	나시
오만&샤플리^[5]	무한	수단의 한계	없음	없음	$정확히$ x ${\displaystyle$ x $x$	나시	그림
오만&샤플리와^[5] 루빈스타인^[8]^[16]	무한	수단의 한계	없음	없음	$정확히$ x ${\displaystyle$ x $x$	서브게임 퍼펙트	제한시간 벌칙.^[7]^{: 146–149}
루빈스타인^[6]	무한	추월	없음	미니맥스보다 훨씬 위다.	단일 결과 또는 주기적인 시퀀스.	서브게임 퍼펙트	비응징자를 처벌하고 있다.^[7]^{: 149–150}
루빈스타인^[8]	무한	수단의 한계	없음	파레토 효율성과 약체-개별^[10] 연합	없음	연합 서브게임 퍼펙트
루빈스타인^[8]	무한	추월	없음	파레토 효율적이고 강력한 연합-개별^[12] 연합	없음	연합-나시
푸덴버그&마신^[17]	무한	할인 합계 $\delta$ $\delta$	상관관계가 있는 혼합전략이 허용된다.	미니맥스보다 훨씬 위다.	When $\delta$ is sufficiently near 1, there is an equilibrium with payoff exactly $x$ .	Nash	Grim
Fudenberg& Maskin^[17]	Infinite	Sum with discount $\delta$	Only pure strategies are allowed.	Strictly above minimax.	For all $\varepsilon >0$ there is $\delta _{0}<1$ such that, if $\delta \geq \delta _{0}$ , for every $x$ there is an equilibrium with payoff $\varepsilon$ -close to $x$ .	Nash	Grim punishment.
Friedman (1971, 1977)	Infinite	Sum with discount $\delta$	Correlated mixed strategies are allowed.	Strictly above a Nash-equilibrium in G.	When $\delta$ is sufficiently near 1, there is equilibrium with payoff exactly $x$ .	Subgame-perfect	Grim punishment using the Nash-equilibrium.
Fudenberg& Maskin^[17]	Infinite	Sum with discount $\delta$	Two players	Strictly above minimax.	For all $x$ there is $\delta _{0}<1$ such that, if $\delta \geq \delta _{0}$ , there is equilibrium with payoff exactly $x$ .	Subgame-perfect	Limited-time punishment.
Fudenberg& Maskin^[17]	Infinite	Sum with discount $\delta$	The IR feasible space is full-dimensional.^[18]	Strictly above minimax.	For all $x$ there is $\delta _{0}<1$ such that, if $\delta \geq \delta _{0}$ , there is equilibrium with payoff exactly $x$ .	Subgame-perfect	Rewarding the punishers.^[7]^{: 150–153}

Notes

^ In mathematics, the term folk theorem refers generally to any theorem that is believed and discussed, but has not been published. Roger Myerson has recommended the more descriptive term "general feasibility theorem" for the game theory theorems discussed here. See Myerson, Roger B. Game Theory, Analysis of conflict, Cambridge, Harvard University Press (1991)
^ R. Gibbons (1992). A Primer in Game Theory. Harvester Wheatsheaf. p. 89. ISBN 0-7450-1160-8.CS1 maint: uses authors parameter (link)
^ Jonathan Levin (2002). "Bargaining and Repeated Games" (PDF).
^ ^a ^b ^c Michael Maschler, Eilon Solan & Shmuel Zamir (2013). Game Theory. Cambridge University Press. pp. 176–180. ISBN 978-1-107-00548-8.CS1 maint: uses authors parameter (link)
^ ^a ^b ^c ^d ^e Aumann, Robert J.; Shapley, Lloyd S. (1994). "Long-Term Competition—A Game-Theoretic Analysis". Essays in Game Theory. p. 1. doi:10.1007/978-1-4612-2648-2_1. ISBN 978-1-4612-7621-0.
^ ^a ^b ^c ^d ^e ^f Rubinstein, Ariel (1979). "Equilibrium in supergames with the overtaking criterion". Journal of Economic Theory. 21: 1. doi:10.1016/0022-0531(79)90002-4.
^ ^a ^b ^c ^d ^e ^f . ISBN 0-262-15041-7. LCCN 94008308. OL 1084491M. Missing or empty title= (help)
^ ^a ^b ^c ^d ^e ^f Rubinstein, A. (1980). "Strong perfect equilibrium in supergames". International Journal of Game Theory. 9: 1. doi:10.1007/BF01784792.
^ The paper uses the term "strong equilibrium". Here, to prevent ambiguity, the term "coalition equilibrium" is used instead.
^ ^a ^b For every nonempty coalition $B$ , there is a strategy of the other players ( $N\setminus B$ ) such that for any strategy played by $B$ , the payoff when $B$ plays $c^{B}$ is not [strictly better for all members of $B$ ].
^ In the 1979 paper, Rubinstein claims that an outcome is attainable in strict-stationary-equilibrium if-and-only-if for every player, the outcome is EITHER strictly better than the player's minimax outcome OR the outcome is weakly better than any other outcome the player can unilaterally deviate to. It is not clear how the second option is attainable in a strict equilibrium. In the 1994 book, this claim does not appear.
^ ^a ^b for every nonempty coalition $B$ , there is a strategy of the other players ( $N\setminus B$ ) such that for any strategy played by $B$ , the payoff is strictly worse for at least one member of $B$ .
^ ^a ^b Fisher, Franklin M. Games Economists Play: A Noncooperative View The RAND Journal of Economics, Vol. 20, No. 1. (Spring, 1989), pp. 113–124, this particular discussion is on page 118
^ Christian Borgs; Jennifer Chayes; Nicole Immorlica; Adam Tauman Kalai; Vahab Mirrokni; Christos Papadimitriou (2007). "The Myth of the Folk Theorem" (PDF).
^ Benoit, Jean-Pierre; Krishna, Vijay (1985). "Finitely Repeated Games". Econometrica. 53 (4): 905. doi:10.2307/1912660. JSTOR 1912660.
^ Rubinstein, Ariel (1994). "Equilibrium in Supergames". Essays in Game Theory. p. 17. doi:10.1007/978-1-4612-2648-2_2. ISBN 978-1-4612-7621-0.
^ ^a ^b ^c ^d Fudenberg, Drew; Maskin, Eric (1986). "The Folk Theorem in Repeated Games with Discounting or with Incomplete Information". Econometrica. 54 (3): 533. CiteSeerX 10.1.1.308.5775. doi:10.2307/1911307. JSTOR 1911307.
^ There is a collection of IR feasible outcomes $y_{1},\dots ,y_{n}$ , one per player, such that for every players $i,j$ , $x_{i}>y_{i,i}$ and $y_{j,i}>y_{i,i}$ .

References

Friedman, J. (1971). "A non-cooperative equilibrium for supergames". Review of Economic Studies. 38 (1): 1–12. doi:10.2307/2296617. JSTOR 2296617.
Ichiishi, Tatsuro (1997). Microeconomic Theory. Oxford: Blackwell. pp. 263–269. ISBN 1-57718-037-2.
Mas-Colell, A.; Whinston, M.; Green, J. (1995). Microeconomic Theory. New York: Oxford University Press. ISBN 0-19-507340-1.
Ratliff, J. (1996). "A Folk Theorem Sampler" (PDF). 민속 정리 입문서 세트.

[1] In mathematics, the term folk theorem refers generally to any theorem that is believed and discussed, but has not been published. Roger Myerson has recommended the more descriptive term "general feasibility theorem" for the game theory theorems discussed here. See Myerson, Roger B. Game Theory, Analysis of conflict, Cambridge, Harvard University Press (1991)

[2] R. Gibbons (1992). A Primer in Game Theory. Harvester Wheatsheaf. p. 89. ISBN 0-7450-1160-8.CS1 maint: uses authors parameter (link)

[3] Jonathan Levin (2002). "Bargaining and Repeated Games" (PDF).

[ZMS-4] Michael Maschler, Eilon Solan & Shmuel Zamir (2013). Game Theory. Cambridge University Press. pp. 176–180. ISBN 978-1-107-00548-8.CS1 maint: uses authors parameter (link)

[AumannShapley94-5] Aumann, Robert J.; Shapley, Lloyd S. (1994). "Long-Term Competition—A Game-Theoretic Analysis". Essays in Game Theory. p. 1. doi:10.1007/978-1-4612-2648-2_1. ISBN 978-1-4612-7621-0.

[Rubinstein79-6] ^ ^a ^b ^c ^d ^e ^f Rubinstein, Ariel (1979). "Equilibrium in supergames with the overtaking criterion". Journal of Economic Theory. 21: 1. doi:10.1016/0022-0531(79)90002-4.

[OR-7] ^ ^a ^b ^c ^d ^e ^f . ISBN 0-262-15041-7. LCCN 94008308. OL 1084491M. Missing or empty title= (help)

[Rubinstein80-8] ^ ^a ^b ^c ^d ^e ^f Rubinstein, A. (1980). "Strong perfect equilibrium in supergames". International Journal of Game Theory. 9: 1. doi:10.1007/BF01784792.

[9] The paper uses the term "strong equilibrium". Here, to prevent ambiguity, the term "coalition equilibrium" is used instead.

[weakly-coalition-individually-rational-10] For every nonempty coalition $B$ , there is a strategy of the other players ( $N\setminus B$ ) such that for any strategy played by $B$ , the payoff when $B$ plays $c^{B}$ is not [strictly better for all members of $B$ ].

[11] In the 1979 paper, Rubinstein claims that an outcome is attainable in strict-stationary-equilibrium if-and-only-if for every player, the outcome is EITHER strictly better than the player's minimax outcome OR the outcome is weakly better than any other outcome the player can unilaterally deviate to. It is not clear how the second option is attainable in a strict equilibrium. In the 1994 book, this claim does not appear.

[strongly-coalition-individually-rational-12] r every nonempty coalition $B$ , there is a strategy of the other players ( $N\setminus B$ ) such that for any strategy played by $B$ , the payoff is strictly worse for at least one member of $B$ .

[fisher-13] Fisher, Franklin M. Games Economists Play: A Noncooperative View The RAND Journal of Economics, Vol. 20, No. 1. (Spring, 1989), pp. 113–124, this particular discussion is on page 118

[14] Christian Borgs; Jennifer Chayes; Nicole Immorlica; Adam Tauman Kalai; Vahab Mirrokni; Christos Papadimitriou (2007). "The Myth of the Folk Theorem" (PDF).

[BenoitKrishna85-15] Benoit, Jean-Pierre; Krishna, Vijay (1985). "Finitely Repeated Games". Econometrica. 53 (4): 905. doi:10.2307/1912660. JSTOR 1912660.

[Rubinstein94-16] Rubinstein, Ariel (1994). "Equilibrium in Supergames". Essays in Game Theory. p. 17. doi:10.1007/978-1-4612-2648-2_2. ISBN 978-1-4612-7621-0.

[FudenbergMaskin86-17] Fudenberg, Drew; Maskin, Eric (1986). "The Folk Theorem in Repeated Games with Discounting or with Incomplete Information". Econometrica. 54 (3): 533. CiteSeerX 10.1.1.308.5775. doi:10.2307/1911307. JSTOR 1911307.

[18] There is a collection of IR feasible outcomes $y_{1},\dots ,y_{n}$ , one per player, such that for every players $i,j$ , $x_{i}>y_{i,i}$ and $y_{j,i}>y_{i,i}$ .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

v t 게임 이론의 주제
정의들	혼잡 게임 협동 게임 결정성 약속의 에스컬레이션 포브스폼 게임 1번과 2번 우승 게임 복잡성 게임 설명 언어 그래픽 게임 믿음의 위계 정보 세트 노멀 폼 게임 선호 순차 게임 동시 게임 동시 동작 선택 해결된 게임 간결한 게임
평형 개념	나시 평형 서브게임 완성도 메르텐스-안정성 평형 베이시안 나시 평형 완벽한 베이시안 평형 떨리는 손 적정 평형 엡실론 평형화 상관평형 순차 평형 준완벽 평형 진화적으로 안정된 전략 위험 우위 코어 샤플리 값 파레토 효율 깁스 평형 양자 반응 평형 자기 확인 평형 강한 나시 평형 마르코프 완전 평형
전략들	우세한 전략 순수전략 혼합 전략 전략-스틸링 인수 Tit for tat 그림 트리거 공모 후진 유도 전진 유도 마르코프 전략 입찰 셰이딩
반 사냥감의	협상문제 싸구려 말씨 글로벌 게임 자동 게임 평균 필드 게임 메커니즘 설계 n-플레이어 게임 완벽한 정보 대형 포아송 게임 포텐셜 게임 반복 게임 스크리닝 게임 신호 게임 엄격하게 결정된 게임 확률 게임 대칭 게임 제로섬 게임
게임.	가다 체스 무한 체스 체커스 틱택토 죄수의 딜레마 선물 교환 게임 선택형수의 딜레마 여행자의 딜레마 코디네이션 게임 치킨 지네 게임 루이스 시그널 게임 자원봉사자의 딜레마 달러 경매 성 전투 사슴 사냥 매칭 페니 얼티메이텀 게임 가위바위보 해적 게임 독재자 게임 공공재 게임 블로토 게임 소모전 엘 파롤 바 문제 공정분할 페어 케이크 커팅 쿠르노 게임 교착 상태 다이너의 딜레마 평균의 2/3을 추측하라. 쿤 포커 나시 흥정 게임 유도 퍼즐 트러스트 게임 공주와 괴물 게임 랑데부 문제
정리	화살의 불가능 정리 오만의 합의 정리 민속 정리 미니맥스 정리 내시의 정리 정화 정리 계시의 원리 제르멜로의 정리
키 수치	앨버트 W. 터커 아모스 트베르스키 앙투안 아우구스틴 쿠르노 아리엘 루빈스타인 클로드 섀넌 대니얼 카너 데이비드 K. 레빈 데이비드 M. 크렙스 도널드 B. 길리스 드루 푸덴베르크 에릭 마신 해럴드 쿤 허버트 사이먼 헤르베 물랭 존 콘웨이 장 티롤 장프랑수아 메르텐스 제니퍼 투어 체이스 존 하사니 존 메이너드 스미스 존 나시 존 폰 노이만 케네스 애로우 케네스 빈모어 레오니드 후르비츠 로이드 샤플리 멜빈 드레스허 메릴 M. 홍수 올가 본다레바 오스카르 모겐스턴 폴 밀그롬 페이턴 영 라인하르트 셀턴 로버트 액슬로드 로버트 아우만 로버트 B. 윌슨 로저 마이어슨 새뮤얼 보울스 수잔 스카치머 토머스 셸링 윌리엄 비크리
잡다한	올페이 경매 알파-베타 가지치기 베르트랑 역설 한정적 합리성 콤비네이터 게임 이론 대립분석 쿠페티션 진화 게임 이론 체스의 첫 동작의 이점 게임 설명 언어 게임 역학 게임 이론 용어집 게임 이론가 목록 게임 이론의 게임 목록 승리가 없는 상황 체스 풀기 위상 게임 공동체의 비극 작은 결정의 횡포

Search

민속 정리(게임 이론)

네임스페이스

더

목차

설정 및 정의

할인 없이 무한 반복 게임

서브게임 완성도

추월

할인이 적용된 무한 반복 게임

서브게임 완성도

할인 없이 반복된 게임

적용들

민속 정리 요약

Notes

References