집 › 변속기(기어박스) › 선형 프로그래밍의 이중성. 평형의 종류 : 내쉬균형, 스테켈베르그, 파레토최적균형, 지배전략균형 평형해를 찾는 최적의 메커니즘은 무엇인가

선형 프로그래밍의 이중성. 평형의 종류 : 내쉬균형, 스테켈베르그, 파레토최적균형, 지배전략균형 평형해를 찾는 최적의 메커니즘은 무엇인가

이중성 이론의 기본 정의.

각 선형 계획법 문제는 다른 선형 계획법 문제와 연관될 수 있습니다. 그 중 하나가 해결되면 다른 문제는 자동으로 해결됩니다. 이러한 작업을 상호 이중이라고 합니다. 주어진 문제(우리는 그것을 원래 문제라고 부를 것입니다)가 주어졌을 때 어떻게 쌍대를 구성할 수 있는지 보여드리겠습니다.

계획된 출력의 문제를 고려하십시오.

에프=3 엑스 1 + 5엑스 2 + 4엑스 3 + 5엑스 4 → 최대
5x 1 +0.4x 2 +2x 3 +0.5x 4 ≤400
5x2 +x3 +x4 ≤300
x1 + x3 + x4 ≤100
x 1 ≥0, x 2 ≥0, x 3 ≥0, x 4 ≥0

이중 문제 컴파일을 위한 일반 규칙:

똑바로	이중
목표 기능(최대)	제약 조건의 오른쪽
제약 조건의 오른쪽	대상 기능(분)
A - 제약 조건 행렬	A T - 제약 조건 행렬
i 번째 제약: ≤ 0, (≥ 0)	변수 y i ≥ 0, (≤ 0)
i 번째 제약: = 0	변수 y i ≠ 0
변수 xj ≥ 0(≤ 0)
변수 xj ≠ 0	j번째 제약: = 0

최대 → 최소

똑바로	이중
대상 기능(분)	제약 조건의 오른쪽
제약 조건의 오른쪽	목표 기능(최대)
A - 제약 조건 행렬	A T - 제약 조건 행렬
i 번째 제약: ≥ 0, (≤ 0)	변수 y i ≥ 0, (≤ 0)
i 번째 제약: = 0	변수 y i ≠ 0
변수 xj ≥ 0(≤ 0)	j 번째 제약: ≤ 0(≥ 0)
변수 xj ≠ 0	j번째 제약: = 0

다음 규칙에 따라 이중 문제를 구성해 보겠습니다.

이중 문제의 변수 수는 원래 문제의 부등식 수와 같습니다.
이중 문제의 계수 행렬은 원래 문제의 계수 행렬로 바뀝니다.
원래 문제의 자유 항의 열은 이중 목적 함수에 대한 계수의 행입니다. 목적 함수는 한 문제에서 최대화되고 다른 문제에서는 최소화됩니다.
원래 문제의 변수가 음수가 아닌 조건은 다른 방향으로 향하는 이중 문제의 부등식 제한에 해당합니다. 그리고 그 반대의 경우에도 원본의 불평등-제한은 이중의 비음성 조건에 해당합니다.

작업 I 행렬의 행은 작업 II 행렬의 열입니다. 따라서 문제 II의 변수 y i에 대한 계수는 각각 문제 I의 i번째 부등식의 계수입니다.
결과 모델은 직접적인 문제에 대한 이중 문제의 경제적 및 수학적 모델입니다.

화살표로 연결된 불평등은 켤레 호출.
이중 문제의 의미 있는 공식화: 자원 Y = (y 1 , y 2 ..., y m)의 가격 세트를 찾으십시오. 각 유형의 생산 자원 비용이 제공되는 경우 총 자원 비용이 최소화됩니다. 제품의 수익은 이 제품의 판매 수익금 이상입니다.
자원 가격 y 1 , y 2 ..., y m 받은 경제 문헌 다양한 타이틀: 회계, 암묵적, 그림자. 이러한 이름의 의미는 이것이 조건부 "가짜" 가격이라는 것입니다. 1의 "외부"가격과 달리 2 ..., 제품에 대한 n부터 일반적으로 생산 시작 전에 알려진 자원 가격 y 1 , y 2 ..., y m은 내부적입니다. , 외부에서 설정하는 것이 아니라 문제를 해결한 결과 직접적으로 결정되기 때문에 자원 추정치라고도 합니다.
직접 문제와 이중 문제 사이의 연결은 특히 그 중 하나의 솔루션이 다른 솔루션에서 직접 얻을 수 있다는 사실에 있습니다.

이중성 정리

이중성은 선형 프로그래밍 이론의 기본 개념입니다. 이중성 이론의 주요 결과는 이중성 정리라는 두 가지 정리에 포함되어 있습니다.

첫 번째 이중성 정리.

쌍대 문제 I과 II의 쌍 중 하나가 풀릴 수 있다면 다른 하나도 풀 수 있고 최적의 계획에 대한 목적 함수의 값은 동일하며, 에프(엑스*) = G(와이*) 여기서 x *, y * - 문제 I 및 II의 최적 솔루션

두 번째 이중성 정리.

계획 x * 및 y *는 각각 문제 I 및 II의 제약 시스템으로 대체될 때 켤레 부등식 쌍 중 적어도 하나가 등식이 되는 경우에만 문제 I 및 II에서 최적입니다.
이것 근본적인 이중성 정리. 즉, x * 및 y *가 원문제 및 쌍대 문제에 대한 실행 가능한 솔루션이고 c T x*=b T y*인 경우 x * 및 y *는 한 쌍의 쌍대 문제에 대한 최적 솔루션입니다.

세 번째 이중성 정리. 이중 문제의 최적 솔루션에서 변수 y i의 값은 제약 조건 시스템의 자유 구성원 b i의 영향에 대한 추정치입니다. 이 문제의 목적 함수 값에 대한 직접 문제의 불평등입니다.
Δf(x) = b i y i

심플 렉스 방법으로 LLP를 풀면 이중 LLP도 동시에 풀 수 있습니다. 최적의 계획에서 이중 문제 y i의 변수 값을 객관적으로 결정된 값 또는 이중 추정치라고 합니다. 응용 문제에서 이중 추정치 y i는 종종 숨겨진 그림자 가격 또는 한계 자원 추정치라고 합니다.

상호 이중 문제의 속성

한 문제에서는 선형 함수의 최대값을 구하고 다른 문제에서는 최소값을 구합니다.
한 문제의 선형 함수에서 변수에 대한 계수는 다른 제약 조건 시스템의 자유 구성원입니다.
각 문제는 표준 형식으로, 최대화 문제에서는 ≤ 형식의 모든 부등식, 최소화 문제에서는 ≥ 형식의 모든 부등식으로 제공됩니다.
두 문제의 제약 조건 시스템에서 변수에 대한 계수 행렬은 서로 전치됩니다.
한 문제의 제약 시스템에서 부등식의 수는 다른 문제의 변수 수와 같습니다.
변수의 음수가 아닌 조건은 두 문제 모두에 존재합니다.

평형 정리

작업 2
문제 1에 대한 이중 문제를 작성하십시오. 찾기 평형 정리에 의한 해.
3x1 +x2 ≥12
x1 +2x2 ≥14
4x1 +11x2 ≥68

평형 정리 . X*=(x 1 *,...,x n *) 및 Y*=(y 1 *,...,y n *)를 대칭 형태의 쌍대 문제 쌍의 허용 가능한 설계라고 합니다. 이러한 계획은 다음과 같은 보완적인 느슨함 조건이 충족되는 경우에만 최적입니다.

정리 4를 사용하면 한 쌍의 이중 문제 중 하나를 해결하여 다른 문제에 대한 최적의 솔루션을 결정할 수 있습니다. 최적해를 대입했을 때 한 문제의 제약 조건이 엄격한 부등식으로 바뀌면 이중 문제의 최적해에서 해당하는 이중 변수는 0이 된다. 한 문제의 최적 계획에서 양수인 변수가 있으면 이중 문제의 해당 제약 조건은 방정식입니다.
보완적 느슨함의 조건을 경제적으로 해석해 보겠습니다. 최적의 솔루션에서 일부 원자재의 추정치가 0이 아닌 경우 완전히 소모됩니다(자원이 부족함). 원자재가 완전히 소비되지 않은 경우(초과) 평가는 0입니다. 따라서 이중 평가는 원자재 부족의 척도임을 알 수 있습니다. 추정치는 해당 원자재의 재고가 1 단위 증가함에 따라 목적 함수 값이 얼마나 증가하는지 보여줍니다. 특정 유형의 제품이 생산 계획에 포함되어 있으면 생산 비용이 생산 제품 비용과 일치합니다. 제품 생산 비용이 제품 비용보다 크면 제품이 생산되지 않습니다.
쌍대 문제 쌍 중 하나에 두 개의 변수가 포함되어 있으면 그래픽으로 풀 수 있으며 정리 3과 4를 사용하여 쌍 대 문제에 대한 솔루션을 찾을 수 있습니다. 이 경우 세 가지 경우가 발생할 수 있습니다. 두 문제 모두 실행 가능한 솔루션이 있습니다. 하나는 실행 가능한 솔루션 문제가 있고 두 문제 모두 실행 가능한 솔루션이 없습니다.

예 2
이중 문제를 구성하고 평형 정리를 사용하여 솔루션을 찾습니다.
x 2 -2x 3 +2x 4 -2x 5 ≤4
-2x 1 -2x 2 +2x 3 +2x 4 +x 5 ≥2
x i≥0, i=1.5
Z=10x 1 -9x 2 -19x 3 -13x 4 -11x 5 → 최대, 원래 문제에 대한 솔루션을 알고 있는 경우: Zmax=(3;4;0;0;0).
이중 문제를 구성해 봅시다. 우리는 원래 문제의 목표와 불평등의 징후에 동의합니다.

Z=10x 1 -9x 2 -19x 3 -13x 4 -11x 5 → 최대
이중 작업:

W=4y 1 -2y 2 → 분
평형 정리를 이용하여 쌍대문제의 최적해를 찾아보자. 보완적인 느슨함의 조건을 적어 봅시다.
y 1 (4-(x 2 -2x 3 +2x 4 -2x 5))=0
y 2 (-2-(2x 1 -2x 2 -2x 3 -2x 4 -x 5))=0
x 1 (-2y 2 -10)=0
x 2 (y 1 -2y 2 +9)=0
x 3 (-2y 1 -2y 2 +19)=0
x 4 (2y 1 -2y 2 +13)=0
x 5 (-2y 1 -y 2 +11)=0
원래 문제의 최적 솔루션을 컴파일된 시스템으로 대체해 보겠습니다. x 1 =3, x 2 =4, x 3 =0, x 4 =0, x 5 =0.
y 1 (4-(4-2 0+2 0-2 0))=0
y 2 (-2-(2 3-2 4-2 0-2 0-0))=0 W(y 1 , y 2 , y 3)=12y 1 +31y 2 +18y 3 → 최대 . 정리 3에 의해 Zmax=Wmin=100000.
마지막으로 Wmin=W(0; 4000/7; 32000/21) = 100000

적대적인 게임에서 최적의 결과는 어떤 플레이어도 그것에서 벗어나는 것이 이익이 되지 않는 것이라고 생각하는 것이 당연합니다. 이러한 결과(x*,y*)를 평형상태라 하고, 평형상태를 찾는 것에 기초한 최적성의 원리를 평형원리라 한다.

정의. 차원 행렬이 있는 행렬 게임에서 결과는 다음과 같습니다. 균형 상황또는 안장 지점인 경우

안장 지점에서 행렬 요소는 행의 최소값과 열의 최대값입니다. 예제의 게임에서 요소 2 33안장점이다. 이 게임에서 최적은 두 플레이어 모두에게 세 번째 전략입니다. 첫 번째 플레이어가 세 번째 전략에서 벗어나면 다음보다 적게 이기기 시작합니다. 33. 두 번째 플레이어가 세 번째 전략에서 벗어나면 그는 다음보다 더 많은 것을 잃기 시작합니다. 33. 따라서 두 플레이어 모두에게 세 번째 전략을 꾸준히 고수하는 것보다 더 좋은 것은 없습니다.

최적 행동의 원칙: 매트릭스 게임에 안장점이 있다면 최적의 전략은 안장점에 해당하는 선택입니다. 게임에 안장 지점이 두 개 이상 있으면 어떻게 됩니까?

정리. 허락하다 매트릭스 게임에서 두 개의 임의 안장 지점. 그 다음에:

증거. 평형 상황의 정의로부터 우리는 다음을 얻습니다.

부등식의 왼쪽 (2.8) , 오른쪽 - , 부등식의 왼쪽 (2.9) - , 오른쪽 - 에 대입합시다. 그런 다음 다음을 얻습니다.

평등은 어디에서 오는가:

보수 함수는 모든 평형 상황에서 동일한 값을 취한다는 정리에 따릅니다. 그래서 그 번호를 불렀다. 게임 비용으로. 그리고 임의의 안장 지점에 해당하는 전략을 최적의 전략각각 플레이어 1과 2. (2.7) 덕분에 모든 플레이어의 최적 전략은 상호 교환 가능합니다.

게임의 전략 세트가 동일하게 유지되고 보수 함수에 양의 상수가 곱해지거나 상수가 추가되는 경우 플레이어 행동의 최적성은 변경되지 않습니다.

정리. 안장점(i*,j*)이 매트릭스 게임에 존재하려면 최대값이 최소값과 같아야 합니다.

(2.10)

증거. 필요성.(i*,j*)가 안장점이면 (2.6)에 따라:

(2.11)

그러나 다음이 있습니다.

(2.12)

(2.11)과 (2.12)에서 다음을 얻습니다.

(2.13)

비슷하게 논쟁하면서 우리는 평등에 도달합니다.

따라서,

반면 역부등식(2.5)은 항상 만족하므로 (2.10)은 참이다.

적절. (2.10)이 참이라고 하자. 안장점의 존재를 증명해 보자. 우리는:

평등(2.10)에 따라 불평등(2.15)과 (2.16)은 평등으로 바뀝니다. 그 후 우리는:

정리가 입증되었습니다. 또한 입증되었습니다 일반적인 의미 maximin과 minimax는 게임 가격과 같습니다.

혼합 게임 확장

매트릭스 게임 G를 고려하십시오. 그 안에 평형 상황이 있으면 최소값은 최대값과 같습니다. 또한 각 플레이어는 상대방에게 자신의 최적 전략에 대한 정보를 알려줄 수 있습니다. 그의 상대는 이 정보로부터 어떠한 추가적인 이익도 얻을 수 없을 것입니다. 이제 게임 G에서 균형 상황이 없다고 가정합니다. 그 다음에:

이 경우 minimax 및 maximin 전략이 안정적이지 않습니다. 플레이어는 더 많은 보상을 받을 수 있는 가능성과 관련된 신중한 전략에서 벗어날 인센티브가 있을 수 있지만 손실 위험, 즉 신중한 전략을 사용하는 것보다 적은 보상을 받을 수 있습니다. 위험한 전략을 사용할 때 상대방에게 정보를 전송하면 해로운 결과가 발생합니다. 플레이어는 신중한 전략을 사용할 때보다 자동으로 더 적은 보상을 받습니다.

예 3. 게임 매트릭스는 다음과 같습니다.

그러한 행렬의 경우, 즉 평형이 존재하지 않습니다. 플레이어의 신중한 전략은 i*=1, j*=2입니다. 플레이어 2는 전략 j*=2를 따르고 플레이어 1은 전략 i=2를 선택하도록 합니다. 그런 다음 후자는 3의 보수를 받게 되며 이는 최대값보다 2단위 더 큽니다. 그러나 플레이어 2가 플레이어 1의 계획에 대해 추측하면 전략을 j=1로 변경하고 첫 번째 플레이어는 최대값보다 적은 0의 보수를 받게 됩니다. 두 번째 플레이어에 대해서도 유사한 추론을 수행할 수 있습니다. 일반적으로 게임의 별도 게임에서 모험적인 전략을 사용하면 보장된 것보다 더 큰 결과를 가져올 수 있지만 그 사용은 위험과 관련이 있다고 결론을 내릴 수 있습니다. 문제는 신뢰할 수 있는 신중한 전략과 모험적인 전략을 결합하여 평균 보수를 높이는 것이 가능한가 하는 것입니다. 본질적으로 문제는 참가자들 사이에 보수(2.17)를 어떻게 나누는가입니다.

합리적인 해결책은 혼합 전략, 즉 순수 전략을 무작위로 선택하는 것입니다. 기억해 플레이어 1의 전략을 혼합이라고 합니다., i 번째 행의 선택이 어떤 확률로 그에 의해 이루어진 경우 파이 .이러한 전략은 확률 분포로 식별할 수 있습니다. 여러 줄에. 첫 번째 플레이어가 m개의 순수 전략을 가지고 있고 두 번째 플레이어가 n개의 순수 전략을 가지고 있다고 가정합니다. 그런 다음 혼합 전략은 확률 벡터입니다.

(2.18)

예제 3의 첫 번째 플레이어에 대한 두 가지 가능한 혼합 전략을 고려하십시오. . 이러한 전략은 순수 전략 간의 확률 분포가 다릅니다. 첫 번째 경우에 행렬의 행이 동일한 확률로 플레이어에 의해 선택되면 두 번째 경우에는 다른 것으로 선택됩니다. 혼합 전략에 대해 이야기할 때 의미하는 것은 무작위 선택"무작위" 선택이 아니라 필요한 확률 분포를 제공하는 무작위 메커니즘의 작업을 기반으로 한 선택입니다. 따라서 첫 번째 혼합 전략을 구현하려면 동전 던지기가 적합합니다. 플레이어는 동전이 떨어지는 방식에 따라 첫 번째 줄 또는 두 번째 줄을 선택합니다. 평균적으로 플레이어는 첫 번째 행과 두 번째 행을 똑같이 자주 선택하지만 게임의 특정 반복에서의 선택은 고정된 규칙의 적용을 받지 않으며 최대 비밀 수준을 갖습니다. , 첫 번째 플레이어에게도 알려지지 않았습니다. 두 번째 혼합 전략을 구현하려면 그리기 메커니즘이 적합합니다. 플레이어는 7개의 동일한 종이를 가져다가 그 중 3개에 십자 표시를 하고 모자에 넣습니다. 그런 다음 무작위로 그 중 하나를 추출합니다. 고전적인 확률 이론에 따르면 그는 3/7의 확률로 십자가가 있는 종이 한 장을, 4/7의 확률로 깨끗한 종이 한 장을 꺼낼 것입니다. 이러한 그리기 메커니즘은 합리적인 확률을 실현할 수 있습니다.

플레이어가 혼합 전략을 고수하도록 합니다(2.18). 그런 다음 게임의 단일 반복에서 첫 번째 플레이어의 보상은 임의의 변수입니다. v(X,Y). 플레이어는 서로 독립적으로 전략을 선택하기 때문에 확률 곱셈 정리에 따라 승리로 결과(i, j)를 선택할 확률은 확률의 곱과 같습니다. 그런 다음 확률 변수의 분포 법칙 v(X,Y)다음 표에 의해 주어진

이제 게임을 무한정 플레이하도록 하십시오. 그런 다음 그러한 게임의 평균 보수는 가치에 대한 수학적 기대치와 같습니다. v(X,Y).

(2.19)

마지막이지만 충분할 때 큰 숫자게임의 반복, 평균 보수는 값(2.19)과 약간 다를 것입니다.

예 4. 플레이어가 다음 전략을 사용할 때 예제 3의 게임에 대한 평균 보수(2.19)를 계산합니다. . 보수 행렬과 확률 행렬은 다음과 같습니다.

평균을 구해봅시다:

따라서 평균 보수(2.20)는 최대값과 최소값 사이의 중간입니다.

혼합 전략 X와 Y의 모든 쌍에 대해 게임의 평균값을 계산할 수 있으므로 최적의 전략을 찾는 문제가 발생합니다. 신중한 전략을 모색하는 것부터 시작하는 것은 당연합니다. 첫 번째 플레이어의 신중한 전략은 그에게 맥시민을 제공합니다. 두 번째 플레이어의 신중한 전략은 첫 번째 플레이어가 미니맥스보다 더 많이 이기도록 허용하지 않습니다. 관심사가 반대인 게임 이론에서 가장 중요한 결과는 다음과 같습니다.

정리. 모든 매트릭스 게임은 혼합 전략에서 균형 상황을 갖습니다.. 이 정리의 증명은 쉽지 않다. 본 강좌에서는 생략합니다.

결과: 평형 상황의 존재는 최대값이 최소값과 같다는 것을 의미하므로 모든 매트릭스 게임에는 가격이 있습니다. 첫 번째 플레이어를 위한 최적의 전략은 최대화 전략입니다. 두 번째의 최적 전략은 minimax입니다. 최적의 전략을 찾는 문제가 해결되었으므로 모든 매트릭스 게임을 말합니다. 풀 수 있는혼합 전략 세트에 대해.

게임 2x2 솔루션

예 5. 게임을 해결합니다. 안장점이 없는지 확인하는 것은 어렵지 않습니다. 첫 번째 플레이어의 최적 전략을 나타냅니다. (엑스, 1-엑스)열 벡터이지만 편의상 문자열로 작성합니다. 두 번째 플레이어의 최적 전략을 나타냅니다. (y,1-y).

첫 번째 플레이어의 보수는 다음과 같은 분포를 갖는 무작위 변수입니다.

v(x,y)	2	-1	-4	7
피	XY	x(1-y)	(1x)년	(1-x)(1-y)

우리는 첫 번째 플레이어의 반복에 대한 평균 보수를 찾습니다. 즉, 무작위 변수의 수학적 기대값입니다. v(x,y):

이 표현식을 변환해 보겠습니다.

이 수학적 기대값은 상수(5/7)와 변수 부분으로 구성됩니다. 14(x-11/14)(y-8/14). 값이 와이 8/14와 달리 첫 번째 플레이어는 항상 선택할 수 있습니다. 엑스변수 부분을 긍정적으로 만들어 상금을 늘리는 방식으로. 값이 엑스 11/14와 다르면 두 번째 플레이어가 항상 선택할 수 있습니다. 와이변수 부분을 음수로 만들어 첫 번째 플레이어의 보수를 줄입니다. 따라서 안장점은 x*=11/14, y*=8/14 등식으로 정의됩니다.

2.5 게임 해결

예를 들어 이러한 게임을 해결하는 방법을 보여줍니다.

예 6. 게임을 해결 . 안장 지점이 없는지 확인합니다. 첫 번째 플레이어의 혼합 전략을 나타냅니다. 엑스=(엑스, 1-엑스)열 벡터이지만 편의상 문자열로 작성합니다.

첫 번째 플레이어가 전략 X를 적용하게 하고 두 번째 플레이어는 자신의 j번째 청소전략. 이 상황에서 첫 번째 플레이어의 평균 보수를 로 표시하겠습니다. 우리는:

세그먼트에 함수(2.21)의 그래프를 그려봅시다.

임의의 선분에 위치한 점의 세로 좌표는 혼합 전략을 사용하는 상황에서 첫 번째 플레이어의 보수에 해당합니다. (엑스,(1-엑스)), 두 번째 플레이어는 해당하는 순수 전략입니다. 첫 번째 플레이어의 보장된 결과는 라인 계열의 하위 엔벨로프입니다(Broken ABC). 최고점이 파선(B 지점)은 플레이어 1의 최대 보장 결과입니다. B 지점의 가로 좌표는 첫 번째 플레이어의 최적 전략에 해당합니다.

원하는 점 B는 선의 교차점이므로 가로 좌표는 방정식의 솔루션으로 찾을 수 있습니다.

따라서 첫 번째 플레이어의 최적 혼합 전략은 (5/9, 4/9)입니다. 포인트 B의 세로 좌표는 게임 가격입니다. 다음과 같습니다.

(2.22)

두 번째 플레이어의 두 번째 전략에 해당하는 라인이 B 지점 위를 통과합니다. 즉, 첫 번째 플레이어가 최적의 전략을 적용하고 플레이어 2가 두 번째 전략을 사용하면 전략을 적용하는 것보다 두 번째 플레이어의 손실이 증가합니다. 1 또는 3. 따라서 두 번째 전략은 두 번째 플레이어의 최적 전략에 참여하지 않아야 합니다. 플레이어 2의 최적 전략은 다음과 같아야 합니다. . 최적 전략에서 0이 아닌 구성 요소를 갖는 두 번째 플레이어의 순수 전략 1과 3을 일반적으로 호출합니다. 중요한. 전략 2가 호출됩니다. 의미 없는. 위의 그림과 평등(2.22)에서 첫 번째 플레이어가 최적의 전략을 적용할 때 두 번째 플레이어의 보수는 그가 사용하는 필수 전략에 의존하지 않는다는 것을 알 수 있습니다. 그는 또한 필수(특히 최적)로 구성된 혼합 전략을 적용할 수 있으며 이 경우에도 보수는 변경되지 않습니다. 반대의 경우에도 완전히 유사한 진술이 적용됩니다. 두 번째 플레이어가 최적의 전략을 사용하면 첫 번째 플레이어의 보수는 그가 사용하는 필수 전략에 의존하지 않고 게임 비용과 동일합니다. 이 문장을 사용하여 두 번째 플레이어를 위한 최적의 전략을 찾습니다.

갈등 이론에서 최적의 전략은 플레이어를 안정적인 평형 상태로 이끄는 전략입니다. 모든 플레이어를 만족시키는 몇 가지 상황.

게임 이론에서 솔루션의 최적성은 개념을 기반으로 합니다. 균형 상황:

1) 다른 모든 플레이어가 균형 상태에 남아 있는 경우 어느 플레이어도 평형 상태에서 벗어나는 것은 이익이 되지 않습니다.

2) 균형의 의미 - 게임을 반복적으로 반복하면 플레이어는 균형 상황에 도달하여 모든 전략적 상황에서 게임을 시작합니다.

각 상호작용에서 다음 유형의 평형이 존재할 수 있습니다.

1. 평형 신중한 전략으로 . 플레이어에게 제공하는 전략에 따라 결정 보장된 결과;

2. 평형 지배적 전략에서 .

지배 전략다른 참가자의 행동에 관계없이 참가자에게 최대 이익을 제공하는 행동 계획입니다. 따라서 우월 전략의 균형은 게임에 참여하는 두 참가자의 우월 전략의 교차점이 될 것입니다.

플레이어의 최적 전략이 다른 모든 전략을 지배한다면 게임은 우월 전략에 균형을 이룹니다. 죄수의 딜레마 게임에서 전략의 내쉬 균형 세트는 ("인정 - 인정")이 될 것입니다. 더욱이, 플레이어 A와 플레이어 B 모두 "인식"이 우세한 전략인 반면 "인식하지 않음"이 우세하다는 점에 유의하는 것이 중요합니다.

3. 평형 내쉬 . 내쉬균형 2명 이상의 플레이어가 참여하는 게임의 결정 유형으로, 다른 참가자가 결정을 바꾸지 않는 경우 참가자가 일방적으로 결정을 변경하여 보상을 높일 수 없습니다.

게임이라고 하자 N는 순수 전략 집합이고 는 보수 집합입니다.

각 플레이어가 전략 프로필에서 전략을 선택하면 플레이어는 보상을 받습니다. 더욱이 결과는 전략의 전체 프로필에 따라 달라집니다. 플레이어 자신이 선택한 전략뿐만 아니라 다른 사람의 전략에도 영향을 받습니다. 전략 프로필은 전략의 변경이 어떤 플레이어에게도, 즉 어떤 플레이어에게도 유익하지 않다면 내쉬 균형입니다.

게임은 순수 전략과 혼합 전략 모두에서 내쉬 균형을 가질 수 있습니다.

Nash는 허용되는 경우 혼합 전략, 각 게임에서 N플레이어는 적어도 하나의 내쉬 균형을 갖게 됩니다.

내쉬 균형 상황에서 각 플레이어의 전략은 다른 플레이어의 전략에 대한 최상의 대응을 제공합니다.

4. 균형 스타켈버그. 스타켈버그 모델– 정보 비대칭이 존재하는 과점 시장의 게임 이론 모델. 이 모델에서 기업의 행동은 완전한 완벽한 정보를 가진 역동적인 게임으로 설명되며, 여기서 기업의 행동은 다음을 사용하여 모델링됩니다. 공전와 게임 완전한 정보. 주요 특징게임은 상품의 생산량을 처음으로 설정하는 선도 기업의 존재이며 나머지 기업은 그에 따라 계산됩니다. 게임의 기본 전제 조건:

산업은 동종 제품을 생산합니다. 다른 회사의 제품 차이는 무시할 수 있습니다. 즉, 구매자는 구매할 회사를 선택할 때 가격에만 집중합니다.

산업에는 소수의 회사가 있습니다.

기업은 생산되는 제품의 수량을 설정하고 가격은 수요에 따라 결정됩니다.

다른 회사가 안내하는 생산량에 소위 리더 회사가 있습니다.

따라서 Stackelberg 모델은 동적 게임에서 최적의 솔루션을 찾는 데 사용되며 한 명 이상의 플레이어가 이미 선택한 후 발전한 조건을 기반으로 플레이어의 최대 보상에 해당합니다. 스탁켈베르그 평형.- 어느 플레이어도 일방적으로 승률을 높일 수 없고, 한 플레이어가 먼저 결정을 내리고 승자가 되는 상황 두 번째로 알려진플레이어. 죄수의 딜레마 게임에서 Stackelberg 균형은 사각형 (1; 1)에서 도달합니다-두 범죄자 모두 "죄를 인정"합니다.

5. 파레토 최적성- 시스템 상태를 설명하는 각 특정 기준의 값이 다른 플레이어의 위치를 악화시키지 않고는 개선될 수 없는 시스템 상태.

파레토 원칙은 다음과 같이 말합니다. 따라서 누구에게도 추가적인 해를 끼치지 않는 모든 변경에 대한 권리가 인정됩니다.

파레토 최적인 시스템 상태 집합을 "파레토 집합", "파레토의 의미에서 최적 대안 집합" 또는 "최적 대안 집합"이라고 합니다.

파레토 효율이 달성된 상황은 교환의 모든 이점이 소진된 상황입니다.

파레토 효율성은 현대 경제학의 핵심 개념 중 하나입니다. 이 개념을 바탕으로 첫 번째와 두 번째 기본 복지 정리를 구성한다.

파레토 최적성의 적용 중 하나는 국제 경제 통합에서 자원(노동 및 자본)의 파레토 분포입니다. 둘 이상의 국가의 경제 연합. 흥미롭게도 국제 경제 통합 이전과 이후의 파레토 분포는 수학적으로 적절하게 설명되었습니다(Dalimov R.T., 2008). 분석결과 산업의 부가가치와 노동자원의 소득은 잘 알려진 열전도 방정식에 따라 우주의 기체나 액체와 같이 반대 방향으로 이동하는 것으로 나타나 사용된 분석기법을 적용할 수 있다. 경제적 매개변수 이동의 경제적 문제와 관련하여 물리학에서.

파레토 최적사회의 후생이 최대치에 도달하고, 이 분배의 변화가 경제 체제의 적어도 한 주체의 후생을 악화시키면 자원 분배가 최적이 된다고 말합니다.

시장의 파레토 최적 상태- 다른 사람 중 적어도 한 사람의 복지를 동시에 감소시키지 않고 경제 과정에서 참가자의 지위를 향상시키는 것이 불가능한 상황.

파레토 기준(사회복지의 성장 기준)에 따르면 최적을 향한 움직임은 다른 사람에게 해를 끼치지 않고 최소한 한 사람의 복지를 증가시키는 자원 분배가 있어야만 가능합니다.

상황 S*는 다음과 같은 경우 파레토 우세 상황 S라고 합니다.

모든 플레이어에 대해 그의 보수는 S<=S*

· S*>S 상황에서 보수를 받는 플레이어가 적어도 한 명 있습니다.

"죄수의 딜레마" 문제에서 파레토 평형은 다른 플레이어의 위치를 악화시키지 않고는 어느 플레이어의 위치도 개선할 수 없을 때 사각형의 상황에 해당합니다(2; 2).

고려하다 예 1.

갈등 이론에서 최적의 전략은 플레이어를 안정적인 평형 상태로 이끄는 전략입니다. 모든 플레이어를 만족시키는 몇 가지 상황.

게임 이론에서 솔루션의 최적성은 개념을 기반으로 합니다. 균형 상황:

1) 다른 모든 플레이어가 균형 상태에 남아 있는 경우 어느 플레이어도 평형 상태에서 벗어나는 것은 이익이 되지 않습니다.

2) 균형의 의미 - 게임을 반복적으로 반복하면 플레이어는 균형 상황에 도달하여 모든 전략적 상황에서 게임을 시작합니다.

각 상호작용에서 다음 유형의 평형이 존재할 수 있습니다.

1. 평형 신중한 전략으로 . 플레이어에게 보장된 결과를 제공하는 전략에 따라 결정됩니다.

2. 평형 지배적 전략에서 .

게임이라고 하자 N는 순수 전략 집합이고 는 보수 집합입니다.

게임은 순수 전략과 혼합 전략 모두에서 내쉬 균형을 가질 수 있습니다.

Nash는 허용되는 경우 혼합 전략, 각 게임에서 N플레이어는 적어도 하나의 내쉬 균형을 갖게 됩니다.

내쉬 균형 상황에서 각 플레이어의 전략은 다른 플레이어의 전략에 대한 최상의 대응을 제공합니다.

4. 균형 스타켈버그. 스타켈버그 모델– 정보 비대칭이 존재하는 과점 시장의 게임 이론 모델. 이 모델에서 기업의 행동은 완전한 완벽한 정보를 가진 역동적인 게임으로 설명되며, 여기서 기업의 행동은 다음을 사용하여 모델링됩니다. 공전완전한 정보를 가진 게임. 게임의 주요 특징은 먼저 상품 생산량을 설정하고 나머지 회사는 그에 따라 계산을 안내하는 선도 기업의 존재입니다. 게임의 기본 전제 조건:

산업은 동종 제품을 생산합니다. 다른 회사의 제품 차이는 무시할 수 있습니다. 즉, 구매자는 구매할 회사를 선택할 때 가격에만 집중합니다.

산업에는 소수의 회사가 있습니다.

기업은 생산되는 제품의 수량을 설정하고 가격은 수요에 따라 결정됩니다.

다른 회사가 안내하는 생산량에 소위 리더 회사가 있습니다.

따라서 Stackelberg 모델은 동적 게임에서 최적의 솔루션을 찾는 데 사용되며 한 명 이상의 플레이어가 이미 선택한 후 발전한 조건을 기반으로 플레이어의 최대 보상에 해당합니다. 스탁켈베르그 평형.- 플레이어 중 어느 누구도 일방적으로 승률을 높일 수 없고, 한 플레이어가 먼저 결정을 내리고 두 번째 플레이어에게 알려지는 상황. 죄수의 딜레마 게임에서 Stackelberg 균형은 사각형 (1; 1)에서 도달합니다-두 범죄자 모두 "죄를 인정"합니다.

5. 파레토 최적성- 시스템 상태를 설명하는 각 특정 기준의 값이 다른 플레이어의 위치를 악화시키지 않고는 개선될 수 없는 시스템 상태.

파레토 원칙은 다음과 같이 말합니다. 따라서 누구에게도 추가적인 해를 끼치지 않는 모든 변경에 대한 권리가 인정됩니다.

파레토 최적인 시스템 상태 집합을 "파레토 집합", "파레토의 의미에서 최적 대안 집합" 또는 "최적 대안 집합"이라고 합니다.

파레토 효율이 달성된 상황은 교환의 모든 이점이 소진된 상황입니다.

파레토 효율성은 현대 경제학의 핵심 개념 중 하나입니다. 이 개념을 바탕으로 첫 번째와 두 번째 기본 복지 정리를 구성한다.

상황 S*는 다음과 같은 경우 파레토 우세 상황 S라고 합니다.

모든 플레이어에 대해 그의 보수는 S<=S*

· S*>S 상황에서 보수를 받는 플레이어가 적어도 한 명 있습니다.

고려하다 예 1:

우월 전략의 균형아니요.

내쉬균형. (5.5) 및 (4.4). 플레이어가 선택한 전략에서 개별적으로 벗어나는 것은 수익성이 없기 때문입니다.

파레토 최적. (5.5). 이러한 전략을 선택할 때 플레이어의 보상 이후 더 많은 승리다른 전략을 선택할 때.

Stackelberg 평형:

플레이어 A가 첫 번째 이동을 합니다.

그의 첫 번째 전략을 선택합니다. B는 첫 번째 전략을 선택합니다. A는 5를 얻습니다.

두 번째 전략을 선택합니다. B는 두 번째 것을 선택합니다. A는 4를 얻습니다.

5 > 4 =>

B가 먼저 움직입니다.

그의 첫 번째 전략을 선택합니다. A는 첫 번째 전략을 선택합니다. B는 5를 얻습니다.

두 번째 전략을 선택합니다. 그리고 그는 두 번째 것을 선택합니다. B는 4를 얻습니다.

5 > 4 => 스탁켈베르그 평형 (5, 5)

예 2듀오폴리 모델링.

이 모델의 본질을 고려하십시오.

하나는 "리더 회사"이고 다른 하나는 "추종 회사"인 두 회사가 있는 산업이 있다고 가정합니다. 제품 가격을 보자 선형 함수총 공급량 큐:

피(큐) = ㅏ − bQ.

기업의 단위 생산량당 비용이 일정하고 다음과 같다고 가정하자. 와 함께 1과 와 함께각각 2. 그러면 첫 번째 회사의 이익은 다음에 의해 결정됩니다. 공식

Π 1 = 피(큐 1 + 큐 2) * 큐 1 − 씨 1 큐 1 ,

그리고 두 번째 이익은 각각

∑ 2 = 피(큐 1 + 큐 2) * 큐 2 − 씨 2 큐 2 .

Stackelberg 모델에 따르면 첫 번째 회사인 선두 기업이 첫 번째 단계에서 산출물을 할당합니다. 큐 1 . 그 후 두 번째 회사인 추종자 회사는 리더 회사의 행동을 분석하여 결과를 결정합니다. 큐 2. 두 회사의 목표는 결제 기능을 극대화하는 것입니다.

이 게임의 내쉬 균형은 역진 귀납법에 의해 결정됩니다. 게임의 두 번째 단계인 두 번째 회사의 이동을 고려하십시오. 이 단계에서 회사 2는 회사 1의 최적 생산량을 알고 있습니다. 큐 1 * . 그런 다음 최적의 출력을 결정하는 문제 큐 2*는 두 번째 회사의 보수 함수의 최대점을 찾는 문제를 해결하는 것으로 축소됩니다. 변수에 대해 함수 Π 2 최대화 큐 2 카운팅 큐 1이 주어졌을 때, 우리는 두 번째 회사의 최적 생산량이

이것은 릴리스의 리더 회사의 선택에 대한 팔로어 회사의 최선의 대응입니다. 큐 1 * . 선도 기업은 주어진 함수의 형태로 보수 함수를 극대화할 수 있습니다. 큐 2*. 변수에서 함수 Π 1의 최대 포인트 큐 1 대체할 때 큐 2 * 의지

이것을 식으로 대입하면 큐 2 * , 우리는 얻는다

따라서 균형상태에서 선도기업은 추종기업보다 2배의 생산량을 생산한다.

공급선과 수요선을 하나의 차트로 결합하면 다음과 같은 결과를 얻습니다. 그래픽 이미지좌표의 평형 피, 큐(그림 2.6). 선의 교차점에는 좌표가 있습니다. (P*, Q*),어디 R* -균형 가격, 큐*- 생산과 소비의 균형.

시장 평형- 주어진 가격 수준에서 수요량이 공급량과 동일한 시장 상태입니다.

균형점에서만 이자형시장은 균형을 이루고 있으며 시장 대리인 중 누구도 상황을 바꿀 유인이 없습니다. 이것은 시장 균형이 속성을 가지고 있음을 의미합니다. 지속 가능성 -비평형 상태의 경우 시장 에이전트는 시장을 균형 상태로 되돌리려는 동기를 부여받습니다. 안정성을 증명하기 위해 L. Walras 또는 A. Marshall의 논리가 일반적으로 사용됩니다.

L. Walras에 따르면 너무 높은 가격에는 초과 공급이 있습니다-과잉 생산 (세그먼트 A-B그림에서 2.6i), 그러한 시장을 구매자의 시장구매자는 거래를 체결할 때 가격 인하를 요구할 기회가 있기 때문입니다. 이러한 상황에서 우선 가격을 낮추고 생산량을 줄여야하는 판매자는 관심이 없습니다. 가격이 하락하면 수요량은 증가한다 A-B평형점이 될 때까지 수축 이자형.

~에 낮은 가격수요 초과 - 부족(세그먼트 CFna 그림 2.6a), 개발 판매자의 시장.구매자는 강제

소비자가 소비를 줄이고 희소한 상품에 초과 지불하면 가격이 상승함에 따라 공급량이 증가하고 희소성은 시장 균형이 될 때까지 축소됩니다.

A. Marshall에 따르면(그림. 2.66), 소량 생산의 경우 수요 가격이 판매자의 가격을 초과하고 대량의 경우 그 반대입니다. 어쨌든 불균형 상황은 균형을 향한 가격 또는 수요와 공급량의 이동을 자극합니다. 평형 (ㅏ) Walras에 따르면 가격은 수요와 공급의 불균형을 조절하고, (비) Marshall에 따르면 구매자와 판매자의 가격은 수량 변화로 균형을 이룹니다.

쌀. 2.6. 시장 균형의 확립: c) L. Walras에 따르면; b) A. 마샬에 따르면

시장 수요 또는 공급의 변화는 균형의 변화로 이어집니다(그림 2.7). 예를 들어 시장 수요가 증가하면 수요선이 오른쪽으로 이동하고 균형 가격과 거래량이 증가합니다. 시장 공급이 감소하면 공급선이 왼쪽으로 이동하여 가격이 상승하고 수량은 감소합니다.

이 모델시간이 나타나지 않기 때문에 시장은 정적입니다.

"거미" 모델

시장 균형의 동적 모델의 예로 가장 단순한 "거미줄" 모델을 제시합니다. 수요량이 현재 기간의 가격 수준에 따라 다르다고 가정합니다. 티,및 공급량 - 이전 기간 t-1의 가격에서:

Q di = Q di (P t) , Q s i = Q s i (P t -1) ,

여기서 t = 0.1….T는 기간의 불연속 값입니다.

쌀. 2.7. 시장 균형의 변화:

a) 수요 증가로 인해; 비)감소로 인해

제안

시장 가격 P 티균형 가격과 일치하지 않을 수 있음 아르 자형*,세 가지 가능한 역학이 있습니다 P 티(그림 2.8).

이 모델에서 개발 궤적의 변형은 공급선과 수요선의 기울기 비율에 따라 달라집니다.