적대적인 매트릭스 게임. 매트릭스 게임 해결 적대적 매트릭스 게임

게임 이론의 기본 가정으로 각 플레이어는 파트너의 모든 행동에 따라 가능한 최대의 승리를 보장하기 위해 노력한다고 가정합니다. 첫 번째 플레이어의 보수 행렬과 그에 따른 두 번째 플레이어의 보수 행렬을 갖는 유한 제로섬 게임이 있다고 가정해 보겠습니다. 선수 1이 어떤 전략을 선택하든 선수 2는 자신의 보수를 최대화하고 그에 따라 선수 1의 보수를 최소화하는 전략을 선택할 것이라고 믿게 하십시오.

그래서 플레이어 1이 선택합니다 나

플레이어 2는 또한 상대방이 선택한 전략에 관계없이 최대의 승리(또는 동등하게 최소의 손실)를 보장하기 위해 노력합니다. 그의 최적 전략은 칼럼이 될 것이다. H 0가장 낮은 최대 지불액으로. 그래서 선수 2는 선택할 것입니다. 제이- 문제에 대한 해결책인 전략

결과적으로, 플레이어 1이 선택한 전략(이라고 함)을 따른다면 최대화 전략 ), 그의 보수는 어떤 경우에도 최대값(라고 함)보다 작을 것입니다. "게임 최저 가격" ), 즉.

따라서 플레이어 2가 자신의 미니맥스 전략을 고수한다면 그의 손실은 최대값("이라고 함)보다 크지 않을 것입니다. "게임 최고 가격" ), 즉.

게임의 상위 가격이 하위 가격과 동일한 경우, 즉 = , 두 플레이어 모두 보장된 지불금을 받고 그 가치는 안녕 ij *~라고 불리는 게임 비용으로 .

매트릭스 요소 안녕하세요전략에 대응하는 보수 매트릭스를 호출합니다. 행렬의 안장점 N.

적대적인 게임의 비용이 0이면 해당 게임을 호출합니다. 공정한 .

플레이어 1이 두 가지 전략을 가지고 있고 플레이어 2가 세 가지 전략을 가지고 있는 게임을 생각해 보세요. 플레이어 1의 보수 매트릭스는 다음과 같습니다:

논평 . 우리는 제로섬 게임의 예를 고려하고 있기 때문에 플레이어 2의 보수 매트릭스는 다음과 같습니다. N 2 = -H 1.

플레이어 1은 첫 번째 전략(즉, 매트릭스의 첫 번째 행)을 선택하면 다음과 같이 계산합니다. H 1), 상대방은 두 번째 전략(즉, 두 번째 열)을 선택하여 보상이 다음과 같게 됩니다. 1 . 그가 두 번째 전략을 선택하면 상대방은 첫 번째 전략을 선택할 수 있으므로 보상은 다음과 같습니다. -1.

획득된 값을 분석한 결과: 플레이어 1은 첫 번째 전략을 결정했으며, 이는 그에게 1에 해당하는 최대 보장 승리를 제공합니다.

마찬가지로, 플레이어 2는 상대가 첫 번째 또는 두 번째 전략을 선택할 때 최악의 옵션을 고려하거나, 플레이어 2가 세 번째 열을 선택할 때 상대가 두 번째 전략을 선택할 때 최악의 옵션을 고려합니다. 이 옵션은 2, 1, 6열의 최대값에 해당합니다.

이러한 최대값 중 최소값을 취하여 플레이어 2는 손실이 최소화되고 다음과 같은 두 번째 전략을 결정합니다.

결과적으로, 이 게임에는 전략의 공동 선택이 있습니다. 이자형

따라서 이 게임에서는 상대방이 자신이 선택한 전략을 고수할 것으로 기대하는 것이 합리적입니다. 매트릭스 적대적 게임 - 완전확실한 게임, 혹은 순수전략에 해결책이 있는 게임이라고 합니다.

그러나 모든 매트릭스 적대적 게임이 잘 정의된 것은 아닙니다.

엄격한 불평등이 유지되는 게임을 불완전하게 결정된 게임(또는 순수 전략에 해결책이 없는 게임)이라고 합니다.

이 게임의 예를 살펴보겠습니다.

이 게임을 위해.

결과적으로 플레이어가 위에서 제안한 규칙을 따르면 플레이어 1은 전략 1을 선택하고 플레이어 2는 전략 2를 선택할 것으로 예상하며 여기서 손실은 -2입니다. 반면 플레이어 2는 전략 3을 선택하고 플레이어 1이 보수가 4인 전략 2를 선택합니다.

그러나 선수 2가 세 번째 전략을 선택하면 선수 1은 첫 번째 전략보다는 두 번째 전략을 선택하는 것이 더 나을 것입니다. 마찬가지로, 플레이어 1이 첫 번째 전략을 선택하면 플레이어 2는 세 번째 전략보다는 두 번째 전략을 선택하는 것이 더 좋습니다. 분명히 교활한 유형의 게임에서는 순수 전략의 해결 원리가 부적합한 것으로 판명되었습니다.

설명된 상황에서는 적이 어떤 전략을 사용할지 추측하지 않는 것이 플레이어에게 중요합니다. 이 계획을 실행하려면 플레이어는 소위 혼합 전략을 사용해야 합니다.

본질적으로 플레이어의 혼합 전략은 순수 전략을 무작위로 선택하는 방식입니다. 수학적으로 이는 특정 플레이어의 순수 전략 집합에 대한 확률 분포로 표현될 수 있습니다. 결과적으로, 플레이어 1이 전략을 사용할 확률에 해당하는 벡터 와 는 이 플레이어의 혼합 전략을 지정합니다. 플레이어 2의 혼합 전략도 비슷하게 결정됩니다. .

우리는 플레이어의 혼합 전략 사용이 독립적이므로 플레이어 1이 해당 전략을 선택하고 플레이어 2가 선택할 확률은 와 같다고 가정합니다. 이 경우 결제 . 과 를 합산하면 플레이어 1의 승리에 대한 수학적 기대치를 알 수 있습니다.

또는 행렬 표기법

일련의 혼합 전략에서 최대 보장 상금을 달성하려는 플레이어 1은 예상 상금의 최소값 중 최대값을 얻기 위해 확률 벡터를 선택합니다. 문제를 해결합니다.

.

마찬가지로 플레이어 2의 목표는 손실의 최소 최대 값을 달성하는 것입니다. 그는 문제를 해결한다

.

게임 이론의 근본적인 결과는 소위 미니맥스 정리(Minimax Theorem)입니다. 이는 플레이어 1과 플레이어 2의 공식화된 문제가 항상 모든 보상 매트릭스에 대한 솔루션을 갖는다는 것입니다.

잘 정의된 게임의 경우 플레이어 1의 전략은 다음과 같습니다. 맥시민 전략 , 플레이어 2 전략 - 미니맥스 전략, 가치 - 게임 비용 ; 게임이 공정하다고 불리는 경우.

Minimax 정리의 명백한 결과는 다음 관계입니다.

.

이는 플레이어 2가 미니맥스 전략을 적용할 경우 플레이어 1의 어떤 전략도 게임 가격보다 큰 금액을 얻을 수 없게 하고, 플레이어 2의 어떤 전략도 게임 가격보다 적은 금액을 잃을 수 없게 한다는 것을 의미합니다. 플레이어 1이 최대화 전략을 적용한다면.

이는 혼합 전략의 특별한 경우인 순수 전략에도 적용됩니다. (순수 전략은 확률 1을 사용하는 전략이기 때문에): 어떠한 순수 전략을 사용하더라도 상대가 최적의 전략을 사용한다면 게임 비용보다 더 많은 승리(적은 손실)를 허용하지 않습니다.

이 사실은 적대적 매트릭스 게임을 해결하기 위한 특정 알고리즘을 개발하는 데 종종 사용됩니다.

최적의 전략을 계산하는 것은 전략의 수가 증가함에 따라 훨씬 더 어려워집니다. 최적의 전략을 찾기 위해 여러 가지 접근 방식을 사용할 수 있습니다.

게임의 차원을 줄이기 위해 행 및 열 우위가 사용됩니다. 일반적으로 행렬의 i번째 행이 i번째 행을 지배한다고 말합니다(즉, 하나의 순수한 행이 다른 행을 지배함). 모든 에 대해 적어도 하나의 .

마찬가지로, 모든 항목에 대해 하나 이상이 있는 경우 번째 열이 번째 열을 지배합니다.

이 정의의 요점은 지배적 전략이 지배적 전략보다 결코 나쁘지 않으며 어떤 경우에는 훨씬 더 낫다는 것입니다. 따라서 중요한 결론은 플레이어가 지배적인 전략을 사용할 필요가 없다는 것입니다. 이를 통해 실제로 지배적인 모든 행과 열을 버릴 수 있어 행렬의 크기가 줄어듭니다(이 접근 방식은 순수 전략에서 솔루션을 검색할 때도 사용할 수 있습니다).

예. 다음 매트릭스가 포함된 게임을 생각해 보세요.

두 번째 행을 제거하면 행렬이 생성됩니다. 이 잘린 행렬의 세 번째 열은 두 번째 열의 지배를 받고 두 번째 열을 생략하면 다음과 같은 결과가 나옵니다.

결과적으로, 결과 게임에 대한 해법을 찾을 수 있다면, 제외된 행과 열에 확률을 0으로 할당하기만 하면 쉽게 원래 게임을 해결하는 데 사용할 수 있습니다.

행렬을 단순화하는 또 다른 방법은 보수 행렬의 아핀 변환(즉, 규칙에 따라 행렬의 모든 요소를 ​​변환 , 여기서 )이 게임의 해를 변경하지 않는다는 속성을 기반으로 합니다. 또한 변환된 게임의 가격은 동일한 규칙을 사용하여 원래 게임의 가격에서 얻을 수 있습니다. 이는 게임의 임무에 대해 원칙적으로 상금이 어떤 단위(루블 또는 달러)로 측정되는지는 중요하지 않으며 고정된 금액을 추가(빼기)하면 각 플레이어의 승(패)이 다음과 같이 변경됨을 의미합니다. 게임의 솔루션을 변경하지 않고 동일한 금액.

이 속성은 보수 행렬을 단순화하고 더 명확하게 만드는 데 사용할 수 있습니다(행렬에 대한 연산과 유사하게 사용됨 - 행렬에 상수를 곱하고 행을 더하고 빼는 것 외에도 이 속성을 사용하면 모든 행렬 제로섬 게임을 만들 수 있음) 공정하기 때문에 보상 매트릭스의 모든 요소로부터 게임 가격을 계산해야 합니다.

또한 그래픽 방법을 사용하여 게임(및 일반적인 게임)을 해결할 수 있습니다.

예를 들어 보수 행렬은 다음과 같습니다.

플레이어 1이 확률로 첫 번째 전략을 선택하고 확률로 두 번째 전략을 선택하도록 합니다. 선수 2가 첫 번째 전략을 선택하면 (매트릭스의 첫 번째 열에서) 선수 1에 대한 기대치는 가 됩니다. 플레이어 2가 두 번째 전략을 선택하면 매트릭스의 두 번째 열에 따라: .

이들 방정식 각각은 좌표와 가 있는 그래프 영역의 직선 세그먼트로 그래픽으로 표시될 수 있습니다.

최종 제어 테스트

1. 적대적인 게임을 설정할 수 있습니다:

a) 플레이어와 안장 지점을 위한 일련의 전략.

b) 두 플레이어 모두를 위한 일련의 전략과 첫 번째 플레이어의 보상 기능.

2. 혼합 전략의 매트릭스 게임에는 게임 가격이 항상 존재합니다.

가) 그렇습니다.

3.보수 행렬의 모든 열이 동일하고 (4 5 0 1) 형식을 갖는다면 첫 번째 플레이어에게 가장 적합한 전략은 무엇입니까?

가) 먼저.

b) 둘째.

c) 네 가지 중 하나.

4. 매트릭스 게임에서 첫 번째 플레이어의 혼합 전략 중 하나는 (0.3, 0.7)의 형태를 갖고, 두 번째 플레이어의 혼합 전략 중 하나는 (0.4, 0, 0.6)의 형태를 갖는다고 가정합니다. 이 행렬의 차원은 무엇입니까?

가) 2*3.

c) 다른 차원.

5. 지배력의 원리를 사용하면 한 단계로 매트릭스에서 제거할 수 있습니다.

a) 전체 라인.

b) 개별 번호.

6. 2*m 게임을 해결하기 위한 그래픽 방법에서는 그래프에서 직접 다음을 찾습니다.

a) 두 플레이어의 최적 전략.

b) 게임 가격과 두 번째 플레이어의 최적 전략.

c) 게임 가격과 첫 번째 플레이어의 최적 전략.

7. 2*m 게임을 해결하는 그래픽 방법에 대한 하위 엔벨로프의 그래프는 일반적인 경우입니다.

가) 깨졌다.

b) 똑바로.

c) 포물선.

8. 2*2 매트릭스 게임에는 플레이어의 혼합 전략에 두 가지 구성 요소가 있습니다.

a) 서로의 가치를 결정합니다.

b) 독립적이다.

9. 매트릭스 게임에서 aij 요소는 다음과 같습니다.

a) 첫 번째 플레이어가 i번째 전략을 사용할 때의 승리, 두 번째 - j번째 전략을 사용할 때의 승리.

b) 상대가 i번째 또는 j번째 전략을 사용할 때 첫 번째 플레이어의 최적 전략.

c) 첫 번째 플레이어가 j번째 전략을 사용할 때 손실, 두 번째 - i번째 전략을 사용할 때.

10. 행렬 요소 aij는 안장점에 해당합니다. 다음과 같은 상황이 가능합니다:

a) 이 요소는 라인의 모든 요소 중에서 엄밀히 말하면 가장 작습니다.

b) 이 요소는 줄에서 두 번째 요소입니다.

11. 브라운-로빈슨 방법에서는 각 플레이어가 다음 단계에서 전략을 선택할 때 다음 사항을 따릅니다.

a) 이전 단계에서 적의 전략.

b) 이전 단계의 전략.

c) 다른 것.

12. 수학적 기대의 기준에 따라 각 플레이어는 다음 사실로부터 진행됩니다.

a) 그에게 최악의 상황이 일어날 것이다.

c) 주어진 확률로 모든 상황 또는 일부 상황이 가능합니다.

13. 모든 요소가 음수인 행렬로 행렬 게임을 구현해 보겠습니다. 게임 가격은 긍정적입니다.

b) 아니요.

c) 명확한 대답이 없습니다.

14. 게임 가격은 다음과 같습니다.

가) 번호.

b) 벡터.

c) 매트릭스.

15. 5*5 차원 게임에서 사용할 수 있는 안장점의 최대 수는 얼마입니까(행렬에는 어떤 숫자도 포함될 수 있습니다):

16. 2*3 차원의 매트릭스 게임에서 첫 번째 플레이어의 혼합 전략 중 하나가 (0.3, 0.7) 형식을 갖고, 두 번째 플레이어의 혼합 전략 중 하나가 (0.3, x, 0.5) 형식을 갖는다고 가정합니다. . 숫자 x는 무엇입니까?

c) 다른 번호.

17. 게임 매트릭스의 어떤 차원에서 Wald 기준이 Laplace 기준으로 바뀌나요?

c) 다른 경우에만.

18. 게임의 최고 가격은 항상 게임의 최저 가격보다 낮습니다.

b) 아니요.

b) 질문이 올바르지 않습니다.

19. 매트릭스 게임에는 어떤 전략이 있습니까?

가) 깨끗하다.

b) 혼합.

c) 둘 다.

20. 일부 적대적 게임에서 일부 변수 값에 대한 두 플레이어의 보수 함수 값이 1이 될 수 있습니까?

가) 항상.

b) 가끔.

c) 결코.

21. 매트릭스 게임에서 첫 번째 플레이어의 혼합 전략 중 하나를 (0.3, 0.7) 형식으로 하고, 두 번째 플레이어의 혼합 전략 중 하나를 (0.4, 0.1,0.1,0.4) 형식으로 설정합니다. . 이 행렬의 차원은 무엇입니까?

c) 다른 차원.

22. 지배력의 원리를 사용하면 한 단계로 매트릭스에서 제거할 수 있습니다.

a) 전체 열,

b) 개별 번호.

c) 더 작은 크기의 부분행렬.

23. 3*3 매트릭스 게임에는 플레이어의 혼합 전략에 두 가지 구성 요소가 있습니다.

a) 세 번째를 결정하십시오.

b) 정의하지 마십시오.

24. 매트릭스 게임에서 aij 요소는 다음과 같습니다.

a) j번째 전략을 사용할 때 두 번째 플레이어의 손실, 그리고 두 번째 - i번째 전략을 사용할 때 손실.

b) 상대가 i번째 또는 j번째 전략을 사용할 때 두 번째 플레이어의 최적 전략,

c) 첫 번째 플레이어가 j번째 전략을 사용할 때의 승리, 그리고 두 번째 - i번째 전략을 사용할 때의 승리,

25. 행렬 요소 aij는 안장점에 해당합니다. 다음과 같은 상황이 가능합니다:

a) 이 요소는 열에서 가장 큽니다.

b) 이 요소는 해당 줄에서 순서대로 가장 큰 요소입니다.

c) 문자열에는 이 요소보다 크고 작은 요소가 모두 포함되어 있습니다.

26. Wald 기준에 따르면 각 플레이어는 다음을 가정합니다.

a) 그에게 최악의 상황이 일어날 것이다.

b) 모든 상황이 동일하게 가능합니다.

c) 주어진 특정 확률로 모든 상황이 가능합니다.

27. 낮은 가격이 게임의 높은 가격보다 낮습니다.

b) 항상 그런 것은 아닙니다.

c) 결코.

28. 매트릭스 게임의 혼합 전략 구성 요소의 합은 항상 다음과 같습니다.

a) 1과 같습니다.

b) 음수가 아님.

c) 긍정적이다.

d) 항상 그런 것은 아니다.

29. 2*3 차원의 매트릭스 게임에서 첫 번째 플레이어의 혼합 전략 중 하나가 (0.3, 0.7) 형식을 갖고, 두 번째 플레이어의 혼합 전략 중 하나가 (0.2, x, x) 형식을 갖는다고 가정합니다. . 숫자 x는 무엇입니까?

지식 기반에서 좋은 작업을 보내는 것은 간단합니다. 아래 양식을 사용하세요

연구와 업무에 지식 기반을 활용하는 학생, 대학원생, 젊은 과학자들은 여러분에게 매우 감사할 것입니다.

소개

1. 이론적인 부분

1.3 게임 순서 2x2

1.4 대수적 방법

1.5 그래픽 방식

1.6 게임 2xn 또는 mx2

1.7 매트릭스 방법을 사용하여 게임 해결

2. 실무적인 부분

2.2 게임 2xn 및 mx2

2.3 매트릭스 방법

2.4 브라운법

결과 분석

소개

제로섬 게임은 제로섬 게임이다. 제로섬 게임은 보수가 반대인 두 플레이어가 참여하는 비협조적 게임입니다.

공식적으로 적대적 게임은 트로이카로 표현될 수 있습니다. 여기서 X와 Y는 각각 첫 번째와 두 번째 플레이어의 전략 세트이고, F는 각 전략 쌍(x,y)를 할당하는 첫 번째 플레이어의 보수 함수입니다. 여기서 실수는 유틸리티의 효용에 해당합니다. 주어진 상황을 구현하는 첫 번째 플레이어.

플레이어의 이해관계가 반대이기 때문에 함수 F는 동시에 두 번째 플레이어의 손실을 나타냅니다.

역사적으로 제로섬 게임은 도박을 설명하는 수학적 게임 이론 모델의 첫 번째 클래스입니다. 이 연구 주제가 게임 이론이라는 이름을 얻은 곳이라고 믿어집니다. 요즘에는 적대적 게임이 비협조적 게임의 더 넓은 종류의 일부로 간주됩니다.

1. 이론적인 부분

1.1 게임의 기본 정의 및 조항

이 게임은 게임 참가자 수, 가능한 행동, 행동과 결과에 따른 상금 분배를 결정하는 규칙 시스템이 특징입니다. 플레이어는 다른 그룹의 이해관계와 일치하지 않는 공통된 이해관계를 가진 한 명의 참가자 또는 게임 참가자 그룹으로 간주됩니다. 따라서 모든 참가자가 플레이어로 간주되는 것은 아닙니다.

게임의 규칙이나 조건은 게임 개발의 모든 단계에서 플레이어의 가능한 행동, 선택 및 움직임을 결정합니다. 플레이어를 선택한다는 것은 플레이어의 행동 옵션 중 하나를 선택한다는 의미입니다. 그런 다음 플레이어는 동작을 사용하여 이러한 선택을 합니다. 이동이란 게임의 특정 단계에서 게임 규칙에 따라 제공되는 가능성에 따라 전체 또는 일부 선택을 한 번에 수행하는 것을 의미합니다. 게임의 특정 단계에 있는 각 플레이어는 선택한 선택에 따라 움직입니다. 첫 번째 플레이어의 선택을 알든 모르든 다른 플레이어도 이동합니다. 각 플레이어는 게임 규칙에 따라 그러한 가능성이 허용되는 경우 게임의 과거 개발에 대한 정보를 고려하려고 합니다.

게임의 결과로 발생하는 상황에 따라 플레이어가 각 동작에서 어떤 선택을 해야 하는지 명확하게 알려주는 일련의 규칙을 플레이어의 전략이라고 합니다. 게임 이론의 전략은 플레이어를 위한 특정 완전한 행동 계획을 의미하며, 게임 개발의 가능한 모든 경우에 플레이어가 어떻게 행동해야 하는지 보여줍니다. 전략은 게임 개발의 모든 단계에서 플레이어가 사용할 수 있는 모든 정보 상태에 대한 모든 지침의 총체를 의미합니다. 이를 통해 전략이 좋을 수도 있고 나쁠 수도 있고, 성공할 수도 있고 실패할 수도 있다는 것이 이미 분명해졌습니다.

제로섬 게임은 각 게임에서 모든 플레이어의 승리의 합이 0이 되는 경우입니다. 즉, 제로섬 게임에서는 모든 플레이어의 총 자본이 변하지 않고 플레이어 간에 재분배됩니다. 결과에 따라. 따라서 많은 경제적, 군사적 상황은 제로섬 게임으로 볼 수 있습니다.

특히 두 플레이어 간의 제로섬 게임은 플레이어의 목표가 정반대이기 때문에 적대적이라고 합니다. 한 플레이어의 이득은 다른 플레이어의 손실을 통해서만 발생합니다.

1.1.1 순수 전략에서 매트릭스 게임의 정의, 예 및 솔루션

2인용 제로섬 매트릭스 게임은 다음과 같은 추상적인 2인용 게임으로 생각할 수 있습니다.

첫 번째 플레이어는 t개의 전략 i =1, 2,..., t를 가지고, 두 번째 플레이어는 n개의 전략 j = 1, 2,..., p를 가지고 있습니다. 각 전략 쌍(i, j)은 숫자 aij와 연관되어 있습니다. 첫 번째 플레이어가 i번째 전략을 사용하고 두 번째 플레이어가 j번째 전략을 사용하는 경우 두 번째 플레이어로 인한 첫 번째 플레이어의 승리입니다.

각 플레이어는 한 번의 이동을 합니다. 첫 번째 플레이어는 i번째 전략(i = 1, 2,..., m)을 선택하고, 두 번째 플레이어는 j번째 전략(j = 1, 2,..., n)을 선택합니다. , 그 후 첫 번째 플레이어는 두 번째 플레이어를 희생하여 승리 aij를 받습니다(만약 aij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

플레이어 i의 각 전략 = 1, 2,…, t; j = 1, 2,…, n은 종종 순수 전략이라고 불립니다.

2인용 제로섬 매트릭스 게임은 이제부터 간단히 매트릭스 게임이라고 부르겠습니다. 분명히 매트릭스 게임은 적대적 게임에 속합니다. 정의에 따르면 매트릭스 게임을 정의하려면 첫 번째 플레이어의 보수 순서에 대한 매트릭스 A = (a ij)를 지정하는 것으로 충분합니다.

보상 매트릭스를 고려한다면

그런 다음 매트릭스 A를 사용하여 매트릭스 게임의 각 게임을 플레이하는 것은 i 번째 행의 첫 번째 플레이어, j 번째 열의 두 번째 플레이어의 선택으로 축소되고 첫 번째 플레이어는 (두 번째를 희생하여) ) i번째 행과 j번째 열의 교차점에 있는 행렬 A에 위치한 상금입니다.

실제 갈등 상황을 매트릭스 게임 형태로 공식화하려면 각 플레이어의 순수 전략을 식별하고 번호를 다시 매겨 보상 매트릭스를 생성해야 합니다.

다음 단계는 플레이어의 최적의 전략과 승리를 결정하는 것입니다.

게임 연구에서 가장 중요한 것은 플레이어의 최적 전략 개념입니다. 이 개념은 직관적으로 다음과 같은 의미를 갖습니다. 이 전략을 사용하여 다른 플레이어의 가능한 모든 전략에 대해 가장 큰 승리를 보장한다면 플레이어의 전략은 최적입니다. 이러한 위치를 기반으로 첫 번째 플레이어는 다음과 같이 공식 (1.1)을 사용하여 자신의 보수 매트릭스 A를 검사합니다. i의 각 값(i = 1, 2,..., t)에 대해 최소 보수 값은 다음에 따라 결정됩니다. 두 번째 플레이어가 사용하는 전략

(i = 1, 2,..., m) (1.2)

즉, 첫 번째 플레이어에 대한 최소 보수가 결정되고, 그가 i번째 순수 전략을 적용하면 이 최소 보수로부터 이 최소 보수가 최대가 되는 전략 i = i 0이 발견됩니다.

정의. 공식(1.3)에 의해 결정된 숫자 b는 게임의 하한 순 가격이라고 하며 두 번째 플레이어의 가능한 모든 행동에 대해 순수 전략을 적용하여 첫 번째 플레이어가 스스로 보장할 수 있는 최소 상금을 보여줍니다.

최적의 행동을 하는 두 번째 플레이어는 가능하다면 자신의 전략을 통해 첫 번째 플레이어의 승리를 최소화하도록 노력해야 합니다. 따라서 두 번째 플레이어에 대해 우리는 다음을 찾습니다.

즉, 두 번째 플레이어가 j번째 순수 전략을 적용하면 첫 번째 플레이어의 최대 보수가 결정되고, 두 번째 플레이어는 첫 번째 플레이어가 최소 보수를 받을 수 있는 j = j 1 전략을 찾습니다.

정의. 공식(1.5)에 의해 결정된 숫자 b는 게임의 순 상한 가격이라고 하며 첫 번째 플레이어가 자신의 전략을 통해 스스로 보장할 수 있는 최대 승리를 보여줍니다. 즉, 순수 전략을 적용함으로써 첫 번째 플레이어는 b 이상의 보수를 보장할 수 있고, 두 번째 플레이어는 순수 전략을 적용하여 첫 번째 플레이어가 b보다 더 많은 승리를 거두는 것을 방지할 수 있습니다.

정의. 행렬 A가 있는 게임에서 게임의 순 가격 하한과 상한이 일치하면(즉, b = c) 이 게임은 순수 전략과 게임의 순 가격에서 안장점을 갖는다고 합니다.

n = b = v (1.6)

안장점은 각각 첫 번째와 두 번째 플레이어의 한 쌍의 순수 전략()으로, 여기서 평등이 달성됩니다.

안장점의 개념은 다음과 같은 의미를 갖습니다. 플레이어 중 한 명이 안장점에 해당하는 전략을 고수하면 다른 플레이어는 안장점에 해당하는 전략을 고수하는 것보다 더 나은 결과를 얻을 수 없습니다. 플레이어의 최선의 행동이 상금 감소로 이어져서는 안 되며, 최악의 행동이 상금 감소로 이어질 수 있다는 점을 염두에 두고 이러한 조건은 다음 관계의 형태로 수학적으로 작성할 수 있습니다.

여기서 i, j는 각각 첫 번째와 두 번째 플레이어의 순수 전략입니다. (i 0 , j 0)은 안장점을 형성하는 전략입니다. 아래에서는 안장점의 정의가 조건(1.8)과 동일하다는 것을 보여줍니다.

따라서 식 (1.8)에 따르면 새들 요소는 행렬 A의 i번째 0번째 행에서 최소이고 j번째 0번째 열에서 최대값입니다. 행렬 A의 새들점을 찾는 것은 쉽습니다. 행렬 A에서 최소 요소는 다음에서 연속적으로 발견됩니다. 각 행을 살펴보고 이 요소가 해당 열의 최대값인지 확인하세요. 만약 그렇다면 그것은 안장 요소이고, 이에 상응하는 전략 쌍이 안장점을 형성합니다. 안장 지점과 안장 요소를 형성하는 첫 번째와 두 번째 플레이어의 한 쌍의 순수 전략(i 0 , j 0)을 게임에 대한 솔루션이라고 합니다.

안장점을 형성하는 순수 전략 i 0 과 j 0 을 각각 첫 번째 플레이어와 두 번째 플레이어의 최적 순수 전략이라고 합니다.

정리 1. f(x, y)를 두 변수 x A와 y B의 실수 함수로 두고 존재한다고 가정합니다.

그러면 b = c.

증거. 최소값과 최대값의 정의로부터 다음과 같습니다.

(1.11)의 좌변에서 x는 임의이므로,

부등식(1.12)의 오른쪽에서 y는 임의적이므로

Q.E.D.

특히, 행렬()은 함수 f(x, y)의 특수한 경우입니다. 즉, x = i, y = j, = f(x, y)를 넣으면 정리 1에서 더 낮은 순을 얻습니다. 가격은 매트릭스 게임 플레이의 상위 순 가격을 초과하지 않습니다.

정의. f (x, y)를 두 변수 x A와 y B의 실수 함수로 둡니다. 다음 부등식이 충족되면 점 (x 0, y 0)을 함수 f (x, y)에 대한 안장점이라고 합니다.

f(x,y0)f(x0,y0)f(x0,y)(1.14)

임의의 x A 및 y B에 대해.

1.2 최적의 혼합 전략과 그 속성

매트릭스 게임에 대한 연구는 순수 전략에서 안장점을 찾는 것부터 시작됩니다. 매트릭스 게임이 순수 전략에 안장점을 갖고 있다면 게임 연구는 이 점을 찾는 것으로 끝난다. 매트릭스 게임에서 순수 전략에 안장점이 없다면 이 게임의 순 가격의 하한값과 상한값을 찾을 수 있습니다. 이는 첫 번째 플레이어가 게임의 상한 가격보다 더 많은 승리를 바라서는 안 된다는 것을 의미하며 다음과 같은 결과를 얻을 수 있습니다. 게임 가격만큼 저렴하지 않게 승리를 거두십시오. 순수 전략의 안장점이 없는 매트릭스 게임에서 플레이어의 행동에 관한 이러한 권장 사항은 연구자와 실무자를 만족시킬 수 없습니다. 매트릭스 게임의 솔루션 개선은 순수 전략 사용의 비밀성과 게임 형태로 게임을 여러 번 반복할 수 있는 가능성을 활용하는 데서 모색되어야 합니다. 예를 들어, 일련의 체스, 체커, 축구 게임이 진행되고, 플레이어가 전략을 적용할 때마다 상대방이 자신의 콘텐츠에 대해 전혀 알지 못하게 되며, 이런 식으로 평균적으로 전체 게임 시리즈를 플레이하여 특정 상금을 획득하세요. 이러한 상금은 평균적으로 게임의 최저 가격보다 크고 게임의 최고 가격보다 낮습니다. 이 평균값이 높을수록 플레이어가 사용하는 전략이 더 좋습니다. 따라서 특정 확률로 순수 전략을 무작위로 적용하는 아이디어가 탄생했습니다. 이는 사용의 비밀을 완전히 보장합니다. 각 플레이어는 평균 보수를 최대화하고 최적의 전략을 얻는 방식으로 순수 전략을 사용할 확률을 변경할 수 있습니다. 이 아이디어는 혼합 전략의 개념으로 이어졌습니다.

정의. 플레이어의 혼합 전략은 순수 전략을 사용할 확률의 전체 집합입니다.

따라서 첫 번째 플레이어가 m개의 순수 전략 1, 2, … i, … m을 가지고 있다면 그의 혼합 전략 x는 다음을 만족하는 숫자 집합 x = (x 1, x 2, ..., x i,…, x m )입니다. 관계

x i 0 (i = 1, 2, ... , t), = 1. (1.15)

마찬가지로 n개의 순수 전략을 가진 두 번째 플레이어의 경우 혼합 전략 y는 다음 관계를 만족하는 숫자 집합 y = (y 1, ..., y j, ... y n)입니다.

y j 0 (j = 1, 2, ... , n), = 1. (1.16)

플레이어가 하나의 순수 전략을 사용할 때마다 다른 전략의 사용이 배제되므로 순수 전략은 호환되지 않는 이벤트입니다. 게다가 그것들은 유일하게 가능한 사건들이다.

분명히, 순수 전략은 혼합 전략의 특별한 경우입니다. 실제로 혼합 전략에서 i번째 순수 전략이 확률 1로 적용되면 다른 모든 순수 전략은 적용되지 않습니다. 그리고 이 i번째 순수 전략은 혼합 전략의 특별한 경우입니다. 비밀을 유지하기 위해 각 플레이어는 다른 플레이어의 선택에 관계없이 자신의 전략을 적용합니다.

정의. 행렬 A를 사용하는 매트릭스 게임에서 첫 번째 플레이어의 평균 보수는 그의 보수에 대한 수학적 기대값으로 표현됩니다.

E(A, x, y) = (1.20)

분명히 첫 번째 플레이어의 평균 보수는 두 변수 x와 y 세트의 함수입니다. 첫 번째 플레이어는 혼합 전략 x를 변경하여 평균 보상 E(A, x, y)를 최대화하는 것을 목표로 하고, 두 번째 플레이어는 혼합 전략을 통해 E(A, x, y)를 최소화하려고 노력합니다. 게임을 해결하려면 게임의 최고 가격이 달성되는 x, y를 찾아야 합니다.

1.3 순서 22의 게임

22차 매트릭스 게임은 첫 번째 플레이어에 대한 다음과 같은 보수 매트릭스로 제공됩니다.

이 게임의 해결책은 순수 전략에서 안장점을 찾는 것부터 시작되어야 합니다. 이렇게 하려면 첫 번째 행에서 최소 요소를 찾아 해당 열에서 최대값인지 확인하세요. 해당 요소가 발견되지 않으면 동일한 방식으로 두 번째 줄을 확인합니다. 이러한 요소가 두 번째 줄에 있으면 안장입니다.

안장 요소를 찾는 것은 해결책을 찾는 프로세스를 종료합니다. 이 경우 게임의 가격(안장 요소와 안장 지점)이 발견되었기 때문입니다. 즉, 첫 번째와 안장 요소에 대한 한 쌍의 순수 전략입니다. 최적의 순수 전략을 구성하는 두 번째 플레이어입니다. 순수 전략에 안장점이 없다면 혼합 전략에서는 안장점을 찾아야 하는데, 이는 매트릭스 게임의 주요 정리에 따라 필연적으로 존재합니다.

첫 번째와 두 번째 플레이어의 혼합 전략을 각각 x = (x 1 , x 2), y = (y 1 , y 2)로 표시하겠습니다. x 1은 첫 번째 플레이어가 첫 번째 전략을 사용할 확률을 의미하고 x 2 = 1 - x 1은 두 번째 전략을 사용할 확률을 의미합니다. 마찬가지로 두 번째 플레이어의 경우: 1은 그가 첫 번째 전략을 사용할 확률이고, 2 = 1 - 1은 그가 두 번째 전략을 사용할 확률입니다.

정리의 결과에 따르면 혼합 전략 x와 y가 최적이 되려면 음수가 아닌 x 1, x 2, y 1, y 2에 대해 다음 관계가 유지되는 것이 필요하고 충분합니다.

이제 매트릭스 게임이 순수 전략에 안장점을 갖지 않는다면 이러한 불평등은 평등으로 바뀌어야 한다는 것을 보여드리겠습니다.

물론. 게임이 순수 전략에 안장점을 가지지 않도록 하여 혼합 전략의 최적 값이 불평등을 충족시킵니다.

0<<1, 0<< 1,

0< <1, 01. (1.25)

(1.22)의 두 부등식이 모두 엄격하다고 가정해 보겠습니다.

그러면 정리에 따르면 y 1 = y 2 = 0이며 이는 조건(1.25)과 모순됩니다.

(1.23)의 두 부등식은 모두 엄밀한 부등식이 될 수 없다는 것도 유사하게 입증되었습니다.

이제 부등식 중 하나(1.22)가 엄격할 수 있다고 가정해 보겠습니다.

이는 정리에 따르면 y 1 = 0, y 2 = 1임을 의미합니다. 결과적으로 (1.23)으로부터 우리는 다음을 얻습니다.

두 부등식(1.24)이 엄격하다면 정리에 따르면 x 1 = x 2 = 0이며 이는 (1.25)와 모순됩니다. a 12 a 22이면 부등식 중 하나(1.27)는 엄격하고 다른 하나는 동일합니다. 더욱이, 12와 22의 더 큰 요소에 대해 동등성이 유지됩니다. 즉, (1.27)의 한 가지 불평등은 엄격해야 합니다. 예를 들어 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

따라서 매트릭스 게임이 순수 전략에서 안장점을 가지지 않는다면 첫 번째 플레이어의 최적 전략에 대해서는 불평등(1.22)이 평등으로 바뀌는 것으로 나타났습니다. 불평등(1.23)에 관한 유사한 추론은 이 경우 불평등(1.23)이 평등해야 한다는 사실로 이어질 것입니다.

따라서 22차 매트릭스 게임에 안장점이 없으면 방정식 시스템(1.24)을 풀어 플레이어의 최적 혼합 전략과 게임 가격을 결정할 수 있습니다. 또한 2x2 순서의 매트릭스 게임에서 플레이어 중 한 명이 최적의 순수 전략을 가지고 있다면 다른 플레이어도 최적의 순수 전략을 가지고 있다는 것이 확립되었습니다.

결과적으로, 매트릭스 게임이 순수 전략에서 안장점을 갖지 않는다면, 방정식(1.24)에 의해 결정되는 혼합 전략의 해를 가져야만 합니다. 시스템의 솔루션(1.25)

1.4 대수적 방법

대수적 방법을 사용하여 문제를 해결하는 경우는 두 가지가 있습니다.

1. 매트릭스에는 안장점이 있습니다.

2. 매트릭스에는 안장점이 없습니다.

첫 번째 경우, 해결책은 게임의 안장점을 형성하는 한 쌍의 전략입니다. 두 번째 경우를 고려해 보겠습니다. 여기서 해결책은 혼합 전략을 통해 찾아야 합니다.

전략을 찾아보자... 예를 들어, 첫 번째 플레이어가 최적의 전략을 사용하면 두 번째 플레이어는 두 가지 순수 전략을 적용할 수 있습니다.

더욱이, 속성으로 인해 플레이어 중 한 명이 최적의 혼합 전략을 사용하고 다른 플레이어가 확률이 0이 아닌 최적의 혼합 전략에 포함된 순수 전략을 사용하는 경우 승리에 대한 수학적 기대는 항상 변경되지 않고 동일하게 유지됩니다. 게임 가격, 즉

이러한 각 경우의 상금은 게임 V의 가격과 동일해야 합니다. 이 경우 다음 관계가 유효합니다.

두 번째 플레이어의 최적 전략을 위해 (2.5), (2.6)과 유사한 방정식 시스템을 구성할 수 있습니다.

정규화 조건을 고려하면 다음과 같습니다.

미지수와 관련하여 방정식 (1.37) - (1.41)을 함께 풀면 한 번에 모두 풀 수는 없지만 한 번에 세 개를 풀 수 있습니다. 개별적으로 (1.36), (1.38), (1.40) 및 (1.37), ( 1.39), (1.41). 솔루션의 결과로 우리는 다음을 얻습니다.

1.5 그래픽 방식

게임 22에 대한 대략적인 해는 그래픽 방법을 사용하여 매우 간단하게 얻을 수 있습니다. 그 본질은 다음과 같습니다.

그림 1.1 - 단위 길이의 단면 찾기

X축에서 단위 길이의 단면을 선택합니다. 왼쪽 끝은 첫 번째 플레이어의 첫 번째 전략을 나타내고 오른쪽 끝은 두 번째 플레이어를 나타냅니다. 모든 중간 지점은 첫 번째 플레이어의 혼합 전략에 해당하며 지점 오른쪽에 있는 세그먼트의 길이는 첫 번째 전략을 사용할 확률과 동일하고 왼쪽에 있는 세그먼트의 길이는 사용 확률입니다. 첫 번째 플레이어의 두 번째 전략.

두 개의 축 I-I 및 II-II가 그려집니다. 첫 번째 플레이어가 첫 번째 전략을 사용하면 I-I에, 두 번째 전략을 사용하면 II-II에 승리를 거둘 것입니다. 예를 들어, 두 번째 플레이어가 첫 번째 전략을 적용한 경우 값은 I-I 축에 표시되고 값은 II-II 축에 표시되어야 합니다.

첫 번째 플레이어의 혼합 전략에 대해 그의 보상은 세그먼트의 가치에 따라 결정됩니다. 라인 I-I는 두 번째 플레이어가 첫 번째 전략을 적용한 것에 해당하며 이를 두 번째 플레이어의 첫 번째 전략이라고 부르겠습니다. 마찬가지로 두 번째 플레이어의 두 번째 전략을 구성할 수 있습니다. 그러면 일반적으로 게임 매트릭스의 그래픽 표시는 다음과 같은 형식을 취합니다.

그림 1.2 - 게임 가격 찾기

그러나 이 구성은 첫 번째 플레이어를 대상으로 수행되었다는 점에 유의해야 합니다. 여기서 세그먼트의 길이는 게임 가격 V와 같습니다.

1N2 라인을 승리 하한선이라고 합니다. 여기에서 N점은 첫 번째 플레이어의 보장된 상금의 최대 금액에 해당한다는 것을 분명히 알 수 있습니다.

일반적으로 말하자면, 두 번째 플레이어의 전략은 예를 들어 다음과 같은 방법으로 이 그림에서 결정될 수도 있습니다. I-I 축에서:

또는 축 II-II에

그러나 두 번째 플레이어의 전략은 첫 번째 플레이어의 전략과 유사하게 결정될 수 있습니다. 그런 그래프를 만들어 보세요.

그림 1.3 - 두 번째 플레이어의 전략 결정

여기서 라인 1N2는 손실의 상한선입니다. N점은 두 번째 플레이어의 가능한 최소 손실에 해당하며 전략을 결정합니다.

행렬 계수의 특정 값에 따라 그래프의 형식이 다를 수 있습니다. 예를 들면 다음과 같습니다.

그림 1.4 - 첫 번째 플레이어의 최적 전략 결정

이러한 상황에서 첫 번째 플레이어의 최적 전략은 순수합니다.

1.6 게임 2n 또는 m2

2n차 게임에서 첫 번째 플레이어는 2개의 순수 전략을 갖고, 두 번째 플레이어는 n개의 순수 전략을 가지고 있습니다. 첫 번째 플레이어의 지불 매트릭스는 다음과 같은 형식을 갖습니다.

그러한 게임에 안장점이 있으면 쉽게 찾고 해결책을 얻을 수 있습니다.

게임에 안장점이 있다고 가정해 보겠습니다. 그런 다음 이러한 혼합 전략을 찾고 그에 따라 관계를 만족하는 첫 번째 및 두 번째 플레이어와 게임 가격 v를 찾아야 합니다.

게임에는 안장점이 없으므로 부등식(1.54)이 부등식으로 대체됩니다.

시스템 (1.56), (1.55), (1.53)을 풀려면 그래픽 방법을 사용하는 것이 좋습니다. 이를 위해 불평등의 좌변(1.53)에 대한 표기법을 소개합니다.

매트릭스 게임 수학적 모델

또는 (1.55)로부터 간단한 변환을 수행하면 다음을 얻습니다.

첫 번째 플레이어가 혼합 전략을 사용하고 두 번째 플레이어가 j번째 순수 전략을 사용하는 경우 평균 보수는 어디입니까?

식에 따르면 각 값 j=1, 2, …, n은 직각좌표계의 직선에 해당합니다.

두 번째 플레이어의 목표는 전략을 선택하여 첫 번째 플레이어의 승리를 최소화하는 것입니다. 그러므로 우리는 계산한다

제한 세트의 하한은 어디에 있습니까? 그림 1.6에서는 함수 그래프가 굵은 선으로 표시됩니다.

http://www.allbest.ru/에 게시됨

그림 1.6 - 함수 그래프

첫 번째 플레이어의 목표는 선택을 통해 승리를 극대화하는 것입니다. 계산하다

그림 1.6에서 점은 에서 얻은 최대값을 의미한다. 게임 가격은 다음과 같습니다.

이러한 방식으로 첫 번째 플레이어의 최적 혼합 전략과 두 번째 플레이어의 순수 전략 쌍이 그래픽으로 결정되며 교차점에서 점을 형성합니다. 그림 1.6은 두 번째 플레이어의 두 번째 및 세 번째 전략을 보여줍니다. 그러한 전략에서는 불평등(1.53)이 평등으로 변합니다. 그림 1.6에서 이는 j=2, j=3 전략입니다.

이제 우리는 연립방정식을 풀 수 있습니다

및 값을 정확하게 결정합니다 (그래픽으로 대략적으로 결정됨). 그런 다음 점을 형성하지 않는 j에 대한 모든 값을 입력하여 방정식 시스템(1.56)을 해결합니다. 그림 1.6에 표시된 예의 경우 이는 다음 시스템입니다.

이 시스템은 j=j0에 대해 두 번째 플레이어의 전략이 M0점을 형성하고 제한 세트의 하한 경계의 최대값이 축 이 경우 첫 번째 플레이어는 무한히 많은 최적 값과 게임 가격을 가지고 있습니다. 이 경우는 그림 1.7에 설명되어 있으며 세그먼트 MN은 상한을 나타내고 최적 값은 한도 내에 있습니다. 두 번째 플레이어 순수 최적 전략 j=j 0 을 가집니다.

m2 차수의 매트릭스 게임은 그래픽 방법을 사용하여 풀 수도 있습니다. 이 경우 첫 번째 플레이어의 보수 행렬은 다음과 같은 형식을 갖습니다.

첫 번째와 두 번째 플레이어의 혼합 전략은 각각 2n차 게임의 경우와 유사하게 정의됩니다. 첫 번째 플레이어가 순수 i번째 전략(i=1, 2, ..., m), 두 번째 - 그의 혼합 전략(y 1, 1- y 1) =y. 예를 들어 m=4일 때 그래픽적으로)는 그림 1.7과 같이 표현될 수 있다.

그림 1.7 - 함수 그래프)

첫 번째 플레이어는 평균 보수를 최대화하려고 시도하므로 다음을 찾으려고 노력합니다.

함수는 굵은 선으로 표시되며 제약 조건 집합의 상한을 나타냅니다. 두 번째 플레이어는 자신의 전략을 선택하여 최소화하려고 합니다. 값은 해당

그림에서 값은 점으로 표시됩니다. 즉, 첫 번째 플레이어의 두 가지 전략과 두 번째 플레이어의 확률이 평등이 달성되는 방식으로 결정됩니다.

그림에서 우리는 게임의 가격이 점의 세로 좌표이고 확률이 점의 가로 좌표임을 알 수 있습니다. 최적의 혼합 전략에서 첫 번째 플레이어의 나머지 순수 전략에 대해서는 ()이 필요합니다.

따라서 해결 시스템(1.69)을 통해 우리는 두 번째 플레이어의 최적 전략과 게임 가격을 얻습니다. 우리는 다음 방정식 시스템을 풀어 첫 번째 플레이어를 위한 최적의 혼합 전략을 찾습니다.

1.7 게임 해결을 위한 매트릭스 방법

명칭:

차수 행렬의 모든 정사각형 하위 행렬

매트릭스(1);

다음으로 전치된 행렬;

B에 인접한 매트릭스;

- (1) 수신 시 삭제된 행에 해당하는 요소를 삭제하여 X에서 얻은 행렬;

- (1) 수신 시 삭제된 행에 해당하는 요소를 삭제하여 얻은 행렬.

연산:

1. 차수 행렬()의 정사각형 부분행렬을 선택하고 계산합니다.

2. 일부 또는 경우 발견된 행렬을 버리고 다른 행렬을 시도하십시오.

3. (), ()이면 X와 and로부터 계산하고 구성하며 적절한 위치에 0을 추가합니다.

부등식을 만족하는지 확인하기

모두를 위한 (1.75)

불평등

모두를 위한 (1.76)

관계 중 하나가 만족스럽지 않으면 다른 관계를 시도합니다. 모든 관계가 유효하면 X와 필요한 솔루션이 필요합니다.

1.8 게임가격의 연속근사방법

게임 상황을 연구할 때 게임에 대한 정확한 솔루션을 얻을 필요가 없거나 어떤 이유로 인해 게임 가격의 정확한 가치와 최적의 혼합 전략을 찾는 것이 불가능하거나 매우 어려운 경우가 종종 발생합니다. 그런 다음 대략적인 방법을 사용하여 매트릭스 게임을 해결할 수 있습니다.

이러한 방법 중 하나, 즉 게임 가격을 연속적으로 근사화하는 방법을 설명하겠습니다. 이 방법을 사용할 때 계산되는 숫자는 보수 행렬의 행과 열 수에 대략 비례하여 증가합니다.

이 방법의 본질은 다음과 같습니다. 게임은 정신적으로 여러 번 진행됩니다. 순차적으로, 각 게임에서 플레이어는 그에게 가장 큰 전체(총) 승리를 제공하는 전략을 선택합니다.

이러한 일부 게임의 구현 후, 첫 번째 플레이어의 승리와 두 번째 플레이어의 손실의 평균값이 계산되고, 이들의 산술 평균이 게임 비용의 대략적인 값으로 사용됩니다. 이 방법을 사용하면 두 플레이어의 최적 혼합 전략의 대략적인 값을 찾을 수 있습니다. 즉, 각 순수 전략의 적용 빈도를 계산하여 해당 플레이어의 최적 혼합 전략의 대략적인 값으로 가져오는 것이 필요합니다.

프로그램 게임 수를 무제한으로 늘리면 첫 번째 플레이어의 평균 이득과 두 번째 플레이어의 평균 손실이 게임 가격에 무한정 접근한다는 것을 증명할 수 있으며, 혼합 전략의 대략적인 값은 다음과 같습니다. 게임에 고유한 솔루션이 있는 경우 각 플레이어의 최적의 혼합 전략이 나타나는 경향이 있습니다. 일반적으로 말하면, 이 값 이상의 근사값이 실제 값에 접근하는 경향은 느립니다. 그러나 이 프로세스는 기계화하기 쉬우므로 상대적으로 큰 보상 행렬을 사용하더라도 필요한 정확도로 게임에 대한 솔루션을 얻는 데 도움이 됩니다.

2. 실무적인 부분

부부는 산책할 곳을 정하고 둘에게 유익한 시간을 보낸다.

소녀는 신선한 공기를 마시기 위해 공원을 산책하고, 저녁에는 가장 가까운 영화관에서 영화를 보기로 결정합니다.

그 남자는 기술 단지에 가서 중앙 경기장에서 지역 클럽 축구 선수들의 경기를 관람할 것을 제안합니다.

이에 따라 플레이어 중 한 사람의 목표를 달성하는 데 걸리는 시간을 찾아야 합니다. 승리 매트릭스는 다음과 같습니다.

표 1. 보수 매트릭스

1 2 이후, 분명히 이 게임은 순수 전략에 있어 안장점이 없습니다. 따라서 우리는 다음 공식을 사용하여 다음을 얻습니다.

http://www.allbest.ru/에 게시됨

2.2 게임 2xn 및 mx2

문제 1(2xn)

건조하고 습한 기후를 위해 두 가지 곡물 작물이 재배됩니다.

그리고 자연 상태는 건조함, 습함, 보통 상태로 간주할 수 있습니다.

http://www.allbest.ru/에 게시됨

M()의 최대값은 j=1, j"=2에 해당하는 선의 교차점으로 형성된 점 M에서 달성됩니다. 이에 따라 다음과 같이 가정합니다.

문제 2(mx2)

한 남자와 여자가 ​​주말에 어디로 갈지 고민하고 있습니다.

휴양지를 선택하는 방법은 공원, 영화관, 레스토랑 등으로 생각할 수 있습니다.

http://www.allbest.ru/에 게시됨

M()의 최대값은 j=1, j"=2에 해당하는 선의 교차로 형성된 점 E에서 달성됩니다. 이에 따라 다음과 같이 가정합니다.

v 값을 결정하려면 다음 방정식을 풀어야 합니다.

2.5 매트릭스 방법

서로 경쟁하는 두 레스토랑(케이터링 시설)은 다음과 같은 서비스를 제공합니다. 첫 번째 레스토랑은 시내 중심에 있고, 다른 레스토랑은 도시 외곽에 있습니다.

중앙 레스토랑에는 다음과 같은 서비스가 포함되어 있습니다:

1) 더 비싸고 고품질의 고객 서비스;

2) 요리는 프랑스 요리에 중점을 두고 있습니다.

두 번째 레스토랑에서는 다음을 제공합니다.

1) 저렴하고 고품질의 서비스;

2) 메뉴에는 세계의 다양한 유명 요리가 결합되어 있습니다.

3) 지속적인 프로모션 및 할인;

4) 택배 주문을 배달하고 수락합니다.

작업에 따라 두 레스토랑 간의 하루 수익은 다음과 같이 분배됩니다.

표 2. 보수 매트릭스

행렬 방법을 사용하여 다음 형식의 게임을 해결합니다.

6개의 하위 행렬이 있으며 다음과 같습니다.

행렬을 고려해보세요:

x 1 = ? 0, x 2 = ? 0

x 2 = 이후< 0, то мы отбрасываем.

이제 행렬을 고려해 보겠습니다.

x 1 = ? 0, x 2 = ? 0

게임 가격.

이 비율은 요구 사항에 위배되므로 적합하지 않습니다.

이제 행렬을 고려해 보겠습니다.

x 1 = , x 2 = ? 0,

와이 1 =< 0, y 2 = ? 0.

y 1 =이므로< 0, то мы отбрасываем и.

이제 행렬을 고려해 보겠습니다.

x 1 = , x 2 = 0, x 2 = 0이므로 및를 버립니다.

이제 행렬을 고려해 보겠습니다.

x 1 = , x 2 = ? 0. x 1 = 0이므로 and를 버립니다.

이제 행렬을 고려해 보겠습니다.

x 1 = , x 2 =, y 1 = , y 2 =, 그런 다음 계속 진행합니다.

x 1 = , x 2 = , y 1 = , y 2 = 또는

게임 가격.

이제 기본 관계가 확인되었습니다.

http://www.allbest.ru/에 게시됨

답: x 1 = , x 2 =, y 1 = , y 2 = , y 3 =0, y 4 =0,.

브라운 방식

어느 회사 근로자들의 요청으로 노조는 회사 비용으로 따뜻한 점심을 준비하는 것에 대해 경영진과 협상한다. 노동자를 대표하는 노동조합은 점심 식사의 질이 최대한 높아져 가격도 더 비싸지기를 원합니다. 회사 경영진은 서로 반대되는 이해관계를 가지고 있습니다. 결국 당사자들은 다음 사항에 합의했습니다. 노동조합(선수 1)은 따뜻한 식사를 공급하는 세 회사(A1, A2, A3) 중 하나를 선택하고, 회사 경영진(선수 2)은 가능한 세 가지 옵션(B1, B2) 중에서 요리 세트를 선택합니다. , 나 3) . 계약에 서명한 후 노동조합은 다음과 같은 지불 매트릭스를 생성하며, 그 요소는 요리 세트 비용을 나타냅니다.

게임을 다음 보수 매트릭스로 정의하겠습니다.

두 번째 플레이어가 두 번째 전략을 선택했다고 가정하면 첫 번째 플레이어는 다음을 받게 됩니다.

2, 첫 번째 전략을 사용하면

세 번째 전략을 사용하는 경우 3입니다.

얻은 값은 표 1에 요약되어 있습니다.

표 3. 두 번째 플레이어의 전략

표 3에서 두 번째 플레이어의 두 번째 전략을 사용하면 첫 번째 플레이어가 두 번째 또는 세 번째 전략을 사용하여 가장 큰 보상 3을 받게 된다는 것을 알 수 있습니다. 첫 번째 플레이어는 최대한의 승리를 원하기 때문에 두 번째 플레이어의 두 번째 전략에 두 번째 전략으로 대응합니다. 첫 번째 플레이어의 두 번째 전략으로 두 번째 플레이어는 다음을 잃게 됩니다.

1 만약 그가 첫 번째 전략을 사용한다면,

3, 2번째 전략을 사용한다면,

4번째 전략을 사용하는 경우.

표 4. 첫 번째 플레이어 전략

표 2에서 첫 번째 플레이어의 두 번째 전략을 사용하면 두 번째 플레이어가 첫 번째 전략을 적용하면 손실이 가장 작은 1임을 알 수 있습니다. 두 번째 플레이어는 더 적은 손실을 원하므로 첫 번째 플레이어의 두 번째 전략에 대응하여 첫 번째 전략을 사용합니다. 얻은 결과는 표 5에 요약되어 있습니다.

표 5. 첫 번째와 두 번째 플레이어의 전략 각각

테이블에 5 두 번째 줄의 두 번째 플레이어의 전략 열에는 숫자 1이 있는데, 이는 두 번째 게임에서 두 번째 플레이어가 첫 번째 전략을 사용하는 것이 유익하다는 것을 나타냅니다. 열에는 첫 번째 게임에서 첫 번째 플레이어가 받은 가장 큰 평균 승리 3이 표시됩니다. w 열에는 첫 번째 게임에서 두 번째 플레이어가 받은 가장 작은 평균 손실인 1이 포함됩니다. v 열에는 산술 평균 v = (u + w)가 포함됩니다. 즉, 게임에서 한 게임의 패배로 얻은 게임 가격의 대략적인 값입니다. 두 번째 플레이어가 첫 번째 전략을 적용하면 첫 번째 플레이어는 첫 번째, 두 번째, 세 번째 전략으로 각각 3, 1, 2를 받게 되며 두 게임 모두에서 첫 번째 플레이어의 총 승리액은 다음과 같습니다.

첫 번째 전략으로 2 + 3=5,

두 번째 전략으로 3 + 1=4,

그의 세 번째 전략은 3 + 2=5입니다.

이러한 총 상금은 테이블의 두 번째 행에 기록됩니다. 3 및 첫 번째 플레이어의 전략에 해당하는 열: 1, 2, 3.

모든 총 승리 중에서 가장 큰 승리는 5입니다. 첫 번째 플레이어의 첫 번째 및 세 번째 전략으로 얻은 것이며, 그 중 하나를 선택할 수 있습니다. 이러한 경우에 두 개(또는 여러 개)의 동일한 총 승리가 있을 때 가장 낮은 숫자의 전략을 선택한다고 가정해 보겠습니다(우리의 경우 첫 번째 전략을 사용해야 합니다).

첫 번째 플레이어의 첫 번째 전략으로 두 번째 플레이어는 첫 번째, 두 번째, 세 번째 전략으로 각각 3, 2, 3을 잃게 되며 두 게임 모두에서 두 번째 플레이어의 총 손실은 다음과 같습니다.

첫 번째 전략으로 1 + 3=4,

두 번째 전략으로 3 + 2=5,

그의 세 번째 전략은 4 + 3=7입니다.

이러한 총 손실은 표의 두 번째 행에 기록됩니다. 5와 두 번째 플레이어의 1차, 2차, 3차 전략에 해당하는 열에 있습니다.

두 번째 플레이어의 총 손실 중 가장 작은 것은 4입니다. 이는 첫 번째 전략으로 획득하므로 세 번째 게임에서 두 번째 플레이어는 첫 번째 전략을 적용해야 합니다. 두 게임에 걸쳐 첫 번째 플레이어가 얻은 가장 큰 총 상금을 게임 수로 나눈 값이 열에 표시됩니다. w 열에는 두 게임에 걸쳐 두 번째 플레이어의 가장 작은 총 손실이 게임 수로 나누어 표시됩니다. v 열에는 이 값의 산술 평균이 입력됩니다. 즉, 이 숫자는 두 개의 "플레이된" 게임이 포함된 게임 가격의 대략적인 값으로 간주됩니다.

따라서, 두 게임에 대해 다음 표 4가 얻어졌다.

표 6. 두 게임 플레이 후 플레이어의 총 승패

두 번째 플레이어의 전략 열에 있는 표 6의 세 번째 행에는 숫자 1이 있는데, 이는 세 번째 게임에서 두 번째 플레이어가 첫 번째 전략을 적용해야 함을 나타냅니다. 이 경우 첫 번째 플레이어는 각각 첫 번째, 두 번째, 세 번째 전략을 사용하여 3, 1, 2를 승리하며 3게임에 대한 총 승리 수는 다음과 같습니다.

첫 번째 전략으로 3 + 5 = 8,

두 번째 전략으로 1 +4 = 5,

그의 세 번째 전략은 2 + 5 = 7입니다.

이러한 첫 번째 플레이어의 총 승리 수는 표 6의 세 번째 행과 그의 전략 1, 2, 3에 해당하는 열에 기록됩니다. 첫 번째 플레이어의 총 승리 수 중 가장 큰 8개는 첫 번째 전략으로 획득되므로 1번째 선수가 선택됩니다. 따라서.

첫 번째 플레이어의 첫 번째 전략으로 두 번째 플레이어는 첫 번째, 두 번째, 세 번째 전략으로 각각 3, 1, 2를 잃게 되며 두 게임 모두에서 두 번째 플레이어의 총 손실은 다음과 같습니다.

첫 번째 전략으로 3 + 4=7,

두 번째 전략으로 2 + 5=7,

그의 세 번째 전략은 3 + 7 = 10입니다.

이러한 총 손실은 표의 세 번째 줄에 기록됩니다. 6과 두 번째 플레이어의 첫 번째, 두 번째, 세 번째 전략에 해당하는 열에 있습니다. 그의 총 손실 중에서 7이 가장 작으며 첫 번째와 두 번째 전략으로 얻은 것입니다. 그런 다음 두 번째 플레이어는 첫 번째 전략을 적용해야 합니다.

테이블에 열의 세 번째 줄에 6이 기록되어 있으며 3게임에 걸쳐 첫 번째 플레이어의 최대 총 승리를 게임 수로 나눈 값으로 기록됩니다. w 열에는 세 게임에 걸쳐 두 번째 플레이어의 가장 작은 총 손실이 게임 수로 나누어 배치됩니다. v 열에는 산술 평균이 포함됩니다.

따라서 우리는 테이블을 얻습니다. 3경기에 7개.

표 7. 3경기 진행 후 플레이어의 총 승패

표 8. 20경기 플레이 후 최종 테이블

테이블에서 도 7과 8을 통해 20번의 패배 게임에서 첫 번째 플레이어의 전략 1, 2, 3이 각각 12, 3, 5회 발생하므로 상대 빈도가 각각 동일하다는 것을 알 수 있습니다. 두 번째 플레이어에 대한 전략 1, 2, 3은 각각 7, 11,2번 발생하므로 상대 빈도는 각각 동일합니다. 게임의 대략적인 가격. 이 근사치는 꽤 좋습니다.

마지막으로, 게임에 두 개 이상의 솔루션이 있는 경우 게임 비용의 근사치는 여전히 게임의 실제 비용에 무한정 접근하며 플레이어 전략의 상대 빈도는 더 이상 플레이어의 실제 최적 값에 접근하지 않습니다. 혼합 전략.

결과 분석

본 교과목에서는 그래픽, 매트릭스 방법, 게임가격의 연속근사법을 이용하여 제로섬 게임의 해법을 찾는 자료를 연구하였다. 첫 번째와 두 번째 플레이어의 최적 전략과 2x2, 2xn 및 mx2 게임과 매트릭스 방법 및 브라운 방법을 사용하는 게임에서의 플레이 비용이 발견되었습니다.

쌍의 예를 사용하여 2x2 게임을 시뮬레이션하고 대수적 및 그래픽 방법을 사용하여 해결했습니다. 대수적으로 게임을 해결한 솔루션은 최적의 혼합 전략을 사용하여 첫 번째와 두 번째 플레이어가 4.6시간을 함께 보낼 것임을 보여줍니다. 문제에 대한 그래픽 솔루션은 작은 오류로 얻어졌으며 4.5시간에 달했습니다.

그리고 2xn과 mx2의 두 가지 문제도 시뮬레이션되었습니다. 문제 2xn에서는 농작물을 고려했으며 전략에 따르면 밭에 50~50개를 심는 것이 더 좋으며 게임 가격은 375만 루블이었습니다. 그리고 문제 mx2에서는 공원과 영화관에 가는 것이 더 저렴하고 비용이 4.3 루블이 될 것이라는 전략을 보여주는 부부가 고려되었습니다.

두 개의 레스토랑을 고려한 매트릭스 방법으로 문제를 모델링했는데, 문제를 해결하면 최적 혼합 전략을 사용할 경우 첫 번째 레스토랑의 수익은 1,560만 루블이 되고 두 번째 레스토랑에서 최적 혼합 전략을 사용할 경우 수익이 발생하는 것으로 나타났습니다. 레스토랑에서는 첫 번째 사람이 1,560만 루블 이상을 벌 수 없습니다. 그래픽 솔루션에서 오류가 발생했으며 게임 가격은 1,490만 루블이었습니다.

브라운의 방법에서는 노동조합과 회사 경영진을 고려하는 과제가 작성되었으며, 그들의 임무는 근로자에게 음식을 제공하는 것입니다. 두 플레이어가 모두 최적의 전략을 사용하면 1인당 식량은 245,000 루블이 됩니다.

사용된 소스 목록

1) Vilisov V.Ya. 강의 노트 "게임 이론 및 통계적 결정", - 지점 - "Voskhod" MAI. 1979. 146p.

2) 크루셰프스키 A.V. 게임 이론, - Kyiv: Vishcha School, 1977. - 216 p.

3) Churchmen U., Akof R., Arnof L., 운영 연구 소개. -M .: 과학. 1967.-488p.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Allbest.ru에 게시됨

유사한 문서

특별한 유형의 인간 활동으로서의 의사 결정. 게임 매트릭스의 합리적인 표현. 순수 전략과 혼합 전략의 매트릭스 게임의 예. 운영 연구: 선형 프로그래밍 문제와 게임 이론 모델의 관계.

코스 작업, 2010년 5월 5일에 추가됨


여러 번 반복되는 게임, 고유한 속성과 단계. 실제로 사용되는 혼합 전략, 조건 및 가능성. 2x2 유형의 게임을 해결하기 위한 분석 방법. 직사각형 게임의 기본 정리. 대수적 솔루션.

프레젠테이션, 2013년 10월 23일에 추가됨


바이매트릭스 게임 이론의 기본 정의. 바이매트릭스 게임 "학생-교사"의 예입니다. 바이매트릭스 게임의 혼합 전략. "균형 상황"을 검색하십시오. 각 플레이어가 두 가지 전략을 가지고 있는 경우의 2x2 바이매트릭스 게임 및 공식.

초록, 2011년 2월 13일에 추가됨


매트릭스와 제로섬 게임에 대한 일반적인 정보를 알아보세요. 위치 플레이, 트리, 정보 세트의 개념입니다. 최대의 원리와 평형의 원리에 대한 고찰. 파레토 최적성. 위치 비적대적 게임, 그 속성.

과정 작업, 2014년 10월 17일에 추가됨


게임 이론은 갈등 상황에서 최적의 결정을 내리기 위한 수학적 모델을 연구하는 수학의 한 분야입니다. 반복 브라운-로빈슨 방법. 매트릭스 게임을 해결하기 위한 단조로운 반복 알고리즘입니다.

논문, 2007년 8월 8일에 추가됨


결제 매트릭스를 작성하고, 게임의 순 가격 하한 및 상한, 플레이어의 최대 및 최소 최대 전략을 검색합니다. 결제 매트릭스 단순화. 선형 계획법 문제 축소 및 "해법 검색" 추가 기능을 사용하여 매트릭스 게임을 해결합니다.

테스트, 2014년 11월 10일에 추가됨


게임 이론은 갈등 상황에 대한 수학적 이론입니다. 2인 제로섬 게임의 수학적 모델 개발, 프로그램 코드 형태의 구현. 문제 해결 방법. 입력 및 출력 데이터. 프로그램, 사용설명서.

코스 작업, 2013년 8월 17일에 추가됨


단순 방법에 대한 기본 정보, 선형 프로그래밍에서의 역할 및 중요성 평가. 기하학적 해석과 대수적 의미. 선형 함수의 최대값과 최소값 찾기, 특수한 경우. 단순 행렬 방법을 사용하여 문제를 해결합니다.

논문, 2015년 6월 1일에 추가됨


기능의 구조와 프로세스를 반영하는 컴퓨터 시스템의 수학적 모델을 구축하는 기술입니다. 평균적인 문제를 해결하는 과정에서 파일에 액세스한 횟수입니다. 외부 메모리 드라이브에 파일을 저장할 가능성을 결정합니다.

실험실 작업, 2013년 6월 21일에 추가됨


수학적 모델의 설계. 틱택토 게임에 대한 설명입니다. 부울 대수학을 기반으로 한 논리 게임 모델입니다. 디지털 전자 장치 및 수학적 모델 개발. 게임 콘솔, 게임 컨트롤러, 게임 필드 라인.

모스크바 에너지 연구소

(기술대학)

실험실 보고서

게임이론에서는

“행렬 형태로 주어진 짝지어진 제로섬 게임의 최적 전략을 찾기 위한 프로그램”

학생들이 완료함

그룹 A5-01

아쉬라포프 달레르

아쉬라포바 올가

게임 이론의 기본 개념

게임이론은 다음과 같은 문제를 해결하기 위해 고안되었습니다. 갈등 상황 , 즉. 서로 다른 목표를 추구하는 둘 이상의 당사자의 이해관계가 충돌하는 상황.

당사자의 목표가 정반대라면 그들은 다음과 같이 말합니다. 적대적 갈등 .

게임 갈등 상황의 단순화되고 공식화된 모델이라고 합니다.

한 게임의 처음부터 끝까지의 단일 플레이를 호출합니다. 파티 . 게임의 결과는 지불 (또는 상금 ).

파티는 다음과 같이 구성됩니다. 움직임 , 즉. 특정 가능한 대안 세트에서 플레이어를 선택합니다.

움직임은 다음과 같습니다. 개인의그리고 무작위의.개인 이동 , 달리 무작위의 , 일부 옵션에 대한 플레이어의 의식적인 선택이 포함됩니다.

최소한 하나의 개인적인 움직임이 있는 게임을 호출합니다. 전략적 .

모든 동작이 무작위로 이루어지는 게임을 호출합니다. 도박 .

개인적으로 움직일 때 그들은 또한 다음과 같이 이야기합니다. 전략 플레이어, 즉 플레이어의 선택을 결정하는 규칙 또는 규칙 집합에 대해 설명합니다. 동시에 전략은 포괄적이어야 합니다. 선택은 게임 중 발생할 수 있는 상황에 따라 결정되어야 합니다.

게임 이론 문제– 플레이어를 위한 최적의 전략 찾기, 즉 최대 이득 또는 최소 손실을 제공하는 전략.

게임 이론 모델의 분류

게임 N사람은 일반적으로 다음과 같이 표시됩니다.
- i번째 플레이어의 전략 세트,
- 게임 결제.

이 지정에 따라 게임 이론 모델의 다음 분류가 제안될 수 있습니다.

이산형(다중 전략 이산)

결정적인

끝없는

지속적(여러 전략 마디 없는)

끝없는

N명 (
)

연합 (협동)

비연합(비협조)

2명(쌍)

적대적(제로섬 게임)

(당사자의 이익은 반대입니다. 즉, 한 플레이어의 손실은 다른 플레이어의 이익과 동일합니다)

비적대적

완전한 정보 포함(개인적인 움직임을 하는 플레이어가 게임의 전체 배경, 즉 상대의 모든 움직임을 알고 있는 경우)

불완전한 정보

금액이 0인 경우(총액이 0임)

넌제로섬

원무브(복권)

멀티패스

짝을 이루는 제로섬 게임의 매트릭스 표현

이 튜토리얼에서는 다음을 살펴보겠습니다. 2인 대결 게임 , 행렬 형태로 제공됩니다. 이는 우리가 첫 번째 플레이어(플레이어)의 많은 전략을 알고 있음을 의미합니다. ㅏ){ ㅏ 나 }, 나 = 1,…, 중그리고 두 번째 플레이어(플레이어)를 위한 다양한 전략 비){ 비 제이 }, 제이 = 1,..., N, 또한 행렬이 주어지면 ㅏ = || ㅏ ij || 첫 번째 플레이어의 승리. 우리는 적대적인 게임에 대해 이야기하고 있으므로 첫 번째 플레이어의 이득은 두 번째 플레이어의 손실과 동일하다고 가정합니다. 우리는 행렬 요소가 ㅏ ij– 전략을 선택한 첫 번째 플레이어의 승리 ㅏ 나그리고 그에 대한 두 번째 플레이어의 전략적인 반응 비 제이. 우리는 그러한 게임을 다음과 같이 나타낼 것입니다.
, 어디 중 - 플레이어 전략의 수 ㅏ,N - 플레이어 전략의 수 안에.일반적으로 다음 표로 나타낼 수 있습니다.

실시예 1

간단한 예로, 게임이 두 가지 동작으로 구성된 게임을 생각해 보세요.

첫 번째 이동: 플레이어 ㅏ상대방에게 자신의 선택에 대해 알리지 않고 숫자(1 또는 2) 중 하나를 선택합니다.

두 번째 이동: 플레이어 안에숫자(3 또는 4) 중 하나를 선택합니다.

결론: 플레이어의 선택 ㅏ그리고 안에접. 그 합이 짝수이면 안에플레이어에게 그 가치를 지불합니다. ㅏ, 홀수인 경우 - 그 반대의 경우도 마찬가지입니다. ㅏ플레이어에게 금액을 지불합니다. 안에.

이 게임은 다음과 같은 형식으로 표시될 수 있습니다.
다음과 같은 방법으로:

이 게임은 적대적임을 쉽게 알 수 있으며, 게다가 정보가 불완전한 게임이기 때문에 플레이어에게 안에,개인적인 움직임을 보이는 경우, 플레이어가 어떤 선택을 했는지는 알 수 없습니다. ㅏ.

위에서 언급했듯이 게임 이론의 임무는 플레이어의 최적 전략을 찾는 것입니다. 최대 이득 또는 최소 손실을 제공하는 전략. 이 과정을 게임 솔루션 .

매트릭스 형태로 게임을 풀 때는 게임의 존재 여부를 확인해야 합니다. 안장 포인트 . 이를 위해 두 가지 값이 입력됩니다.

– 게임 가격에 대한 낮은 추정치 및

– 게임 가격의 상한 추정치.

첫 번째 플레이어는 두 번째 플레이어의 가능한 모든 답변 중에서 최대한의 승리를 얻는 전략을 선택할 가능성이 높으며, 두 번째 플레이어는 반대로 자신의 손실을 최소화하는 전략, 즉 1차 승리 가능성.

다음이 증명될 수 있다 α ≤ V ≤ β , 어디 V–게임 가격 즉, 첫 번째 플레이어가 승리할 가능성이 높습니다.

관계가 유지된다면 α = β = V, 그러면 그들은 이렇게 말해요 게임에는 안장 지점이 있습니다
, 그리고 순수 전략으로 해결 가능 . 즉, 몇 가지 전략이 있습니다.
, 플레이어에게 제공 ㅏV.

실시예 2

예제 1에서 고려했던 게임으로 돌아가서 안장점이 있는지 확인해 보겠습니다.

이 게임의 경우
= -5,
= 4,
따라서 안장점이 없습니다.

이 게임은 정보가 불완전한 게임이라는 점을 다시 한 번 주목해보자. 이 경우, 우리는 플레이어에게만 조언을 드릴 수 있습니다. ㅏ전략을 선택하다 , 왜냐하면 이 경우 그는 가장 큰 승리를 얻을 수 있지만 플레이어의 선택에 따라 달라집니다. 안에전략 .

실시예 3

예제 1의 게임 규칙을 일부 변경해 보겠습니다. 플레이어에게 제공해드립니다 안에플레이어 선택 정보 ㅏ.그럼 안에두 가지 추가 전략이 나타납니다.

- 이익이 되는 전략 ㅏ.선택의 경우 A - 1,저것 안에선택한다면 3을 선택한다 A - 2,저것 안에 4를 선택합니다.

- 이익이 되지 않는 전략 ㅏ.선택의 경우 A - 1,저것 안에선택한다면 4를 선택한다 A - 2,저것 안에 3을 선택합니다.

이 게임에는 완전한 정보가 포함되어 있습니다.

이 경우
= -5,
= -5,
따라서 게임에는 안장 지점이 있습니다.
. 이 안장점은 두 쌍의 최적 전략에 해당합니다.
그리고
. 게임 가격 V= -5. 에 대한 것은 분명하다 ㅏ그런 게임은 수익성이 없습니다.

예제 2와 3은 게임 이론에서 입증된 다음 정리를 잘 보여줍니다.

정리 1

완전한 정보를 지닌 모든 짝짓기 적대 게임은 순수 전략으로 해결될 수 있습니다.

저것. 정리 1에 따르면 완전한 정보가 있는 2인 게임에는 안장점이 있고 한 쌍의 순수 전략이 있습니다.
, 플레이어에게 제공 ㅏ게임 가격과 동일한 지속 가능한 상금 V.

안장점이 없는 경우, 소위 혼합 전략 :, 어디 피 나 그리고큐 제이– 전략 선택 확률 ㅏ 나 그리고 비 제이각각 첫 번째와 두 번째 플레이어. 이 경우 게임의 해결책은 한 쌍의 혼합 전략입니다.
, 게임 가격의 수학적 기대치를 최대화합니다.

다음 정리는 정리 1을 정보가 불완전한 게임의 경우로 일반화합니다.

정리 2

짝을 이루는 적대적인 게임에는 적어도 하나의 최적 솔루션이 있습니다. 즉, 일반적인 경우에는 한 쌍의 혼합 전략이 있습니다.
, 플레이어에게 제공 ㅏ게임 가격과 동일한 지속 가능한 상금 V, 그리고 α ≤ V ≤ β .

특수한 경우, 안장점이 있는 게임의 경우 혼합 전략의 솔루션은 한 요소가 1과 같고 나머지는 0인 벡터 쌍처럼 보입니다.

게임 이론에서 자세히 전개된 가장 간단한 사례는 유한 제로섬 쌍 게임(두 사람 또는 두 연합의 적대적인 게임)입니다. 서로 반대되는 이해관계를 갖고 있는 두 명의 플레이어 A와 B가 참여하는 게임 G를 생각해 보세요. 한 사람의 이득은 다른 사람의 손실과 같습니다. 플레이어 A의 보수는 반대 부호를 가진 플레이어 B의 보수와 동일하므로 우리는 플레이어 A의 보수에만 관심을 가질 수 있습니다. 당연히 A는 최대화를 원하고 B는 a를 최소화하려고 합니다.

단순화를 위해 정신적으로 자신을 플레이어 중 한 명(A라고 가정)과 동일시하고 그를 "우리"라고 부르고 플레이어 B를 "상대"라고 부르겠습니다(물론 A가 이로부터 얻을 수 있는 실질적인 이점은 없습니다). 가능한 전략과 상대 - 가능한 전략을 생각해 봅시다(이러한 게임을 게임이라고 합니다). 우리가 전략을 사용하고 상대방이 전략을 사용하면 우리의 승리를 표시하겠습니다.

표 26.1

각 전략 쌍에 대해 보수(또는 평균 보수) a가 알려져 있다고 가정해 보겠습니다. 그런 다음 원칙적으로 플레이어의 전략과 해당 보상을 나열하는 직사각형 테이블(매트릭스)을 구성하는 것이 가능합니다(표 26.1 참조).

그러한 테이블이 컴파일되면 그들은 게임 G가 매트릭스 형태로 축소되었다고 말합니다(게임을 그러한 형태로 가져오는 것은 그 자체로 이미 어려운 작업일 수 있으며 때로는 전략의 엄청나게 다양하기 때문에 거의 불가능할 수도 있습니다). ). 게임이 매트릭스 형태로 축소되면 다중 이동 게임은 실제로 단일 이동 게임으로 축소됩니다. 플레이어는 전략을 선택하는 한 가지 이동만 하면 됩니다. 게임 매트릭스를 간략하게 설명하겠습니다.

행렬 형태의 게임 G(4X5)의 예를 살펴보겠습니다. 우리는 네 가지 전략 중에서 선택할 수 있고 적에게는 다섯 가지 전략이 있습니다. 게임 매트릭스는 표 26.2에 나와 있습니다.

우리(플레이어 A)는 어떤 전략을 사용해야 할지 생각해 볼까요? Matrix 26.2에는 "10"이라는 유혹적인 보상이 있습니다. 우리는 이 "맛있는 정보"를 얻을 수 있는 전략을 선택하고 싶은 유혹을 받습니다.

하지만 잠깐만요. 적도 바보가 아니거든요! 우리가 전략을 선택하면 그는 우리를 괴롭히기 위해 그 전략을 선택할 것이고 우리는 한심한 보상 "1"을 얻게 될 것입니다. 아니요, 전략을 선택할 수 없습니다! 어떻게 될까요? 분명히, 주의 원칙(그리고 이것이 게임 이론의 기본 원칙임)을 바탕으로 최소 이득이 최대가 되는 전략을 선택해야 합니다.

표 26.2

이것은 소위 "최소 최대 원칙"입니다. 상대의 최악의 행동을 고려할 때 최대의 승리를 얻을 수 있도록 행동하십시오.

표 26.2를 다시 작성하고 오른쪽 추가 열에 각 행(최소 행)의 최소 승리 값을 적어 보겠습니다. 이를 라인 a에 표시해 보겠습니다(표 26.3 참조).

표 26.3

모든 값(오른쪽 열) 중에서 가장 큰 값(3)이 강조 표시됩니다. 전략은 이에 해당합니다. 이 전략을 선택함으로써 우리는 어떤 경우에도 (적의 어떤 행동에 대해) 3 이상 승리할 것이라고 확신할 수 있습니다. 이 값은 우리의 보장된 승리입니다. 신중하게 행동하면 이보다 더 적게 얻을 수는 없으며 어쩌면 더 많이 얻을 수도 있습니다.)

이 승리를 게임의 최저 가격(또는 "최대" - 최소 승리의 최대값)이라고 합니다. 우리는 그것을 a로 표기하겠습니다. 우리의 경우

이제 적의 관점과 그에 대한 이유를 살펴보겠습니다. 그는 어떤 종류의 졸도 아니지만 똑똑합니다! 전략을 선택할 때 그는 더 적은 양을 주고 싶어하지만 우리의 최악의 행동을 기대해야 합니다. 그가 전략을 선택하면 우리는 그에게 대답할 것이고 그는 10을 줄 것입니다. 그가 선택하면 우리는 그에게 대답하고 그는 줄 것입니다. 우리는 표 26.3에 추가 결론을 추가하고 그 열의 최대값을 기록할 것입니다. 분명히 신중한 상대는 이 값이 다음과 같은 전략을 선택해야 합니다. 최소(해당 값 5는 표 26.3에 강조 표시되어 있습니다). 이 값 P는 합리적인 상대가 확실히 우리에게 제공하지 않는 것 이상의 이득 값입니다. 이를 게임의 최고 가격(또는 "mi-nimax" - 최대 상금의 최소값)이라고 합니다. 우리의 예에서는 적의 전략으로 달성됩니다.

따라서 주의 원칙(재보험 규칙은 "항상 최악의 경우를 계산합니다!")을 바탕으로 전략 A와 적 전략을 선택해야 합니다. 이러한 전략을 "미니맥스"(미니맥스 원칙에 따름)라고 합니다. 우리 예에서 양측이 모두 미니맥스 전략을 고수하는 한 보상은 다음과 같습니다.

이제 적이 전략을 따르고 있다는 것을 우리가 배웠다고 잠시 상상해 봅시다. 자, 이에 대해 그를 처벌하고 전략을 선택합시다. 우리는 5를 얻게 될 것입니다. 그렇게 나쁘지는 않습니다. 그러나 적 역시 실패자가 아닙니다. 그에게 우리의 전략이 이라는 것을 알려 주면 그는 또한 서둘러 선택하여 우리의 상금을 2로 줄일 것입니다. (파트너는 "전략을 가지고 돌진했습니다"). 간단히 말해서, 우리 예의 미니맥스 전략은 상대방의 행동에 대한 정보와 관련하여 불안정합니다. 이러한 전략에는 균형의 속성이 없습니다.

항상 그런가요? 항상 그런 것은 아닙니다. 표 26.4에 주어진 행렬의 예를 생각해 보십시오.

이 예에서는 게임의 낮은 가격이 높은 가격과 같습니다. 이것으로부터 무엇이 나오나요? 플레이어 A와 B의 미니맥스 전략은 안정적입니다. 두 플레이어가 모두 이를 고수하는 한 보상은 6입니다. 상대(B)가 전략 B를 고수한다는 것을 (A) 알게 되면 어떻게 되는지 볼까요?

표 26.4

그러나 전략에서 벗어나면 상황이 더욱 악화될 수 있기 때문에 아무것도 변하지 않을 것입니다. 마찬가지로, 상대방이 받은 정보는 그를 자신의 전략에서 벗어나도록 강요하지 않을 것입니다. 한 쌍의 전략은 균형(균형 잡힌 전략 쌍)의 속성을 가지며, 이 전략 쌍을 통해 달성되는 보상(우리의 경우 6) 를 "행렬의 안장점"이라고 합니다. 안장점과 균형 잡힌 전략 쌍이 존재한다는 신호는 게임의 최저 가격과 최고 가격이 동일하다는 것입니다. 총 가치를 게임 가격이라고 합니다. 표기해보겠습니다

이 이득이 달성되는 전략(이 경우)을 최적 순수 전략이라고 하며, 그 전체를 게임에 대한 솔루션이라고 합니다. 이런 경우에는 게임 자체에 대해 순수 전략으로 해결된다고 한다. 당사자 A와 B 모두 자신의 위치가 가장 좋은 최적의 전략을 제공받을 수 있습니다. 그리고 플레이어 A가 6을 이기고 B가 졌다면 게임의 조건은 다음과 같습니다. A에게는 유리하고 B에게는 불리합니다.

독자는 다음과 같은 질문을 할 수 있습니다. 최적의 전략을 "순수"라고 부르는 이유는 무엇입니까? 조금 더 살펴보면, 우리는 이 질문에 답할 것입니다. 플레이어가 단지 하나의 전략이 아니라 여러 전략을 무작위로 사용한다는 사실로 구성된 "혼합" 전략이 있습니다. 따라서 순수 전략 외에 혼합 전략을 허용한다면 모든 유한 게임에는 균형점이라는 솔루션이 있습니다. 그러나 이에 대해서는 아직 논의가 필요합니다.

게임에서 안장점의 존재는 규칙이 아니라 예외입니다. 대부분의 게임에는 안장 지점이 없습니다. 그러나 항상 안장점이 있어서 순수한 전략으로 해결되는 게임 유형이 있습니다. 이것은 소위 "완전한 정보를 갖춘 게임"입니다. 완전한 정보를 가진 게임은 각 플레이어가 개인적인 움직임을 가지고 개발의 전체 배경, 즉 개인적이고 무작위적인 모든 이전 움직임의 결과를 알고 있는 게임입니다. 완전한 정보가 포함된 게임의 예로는 체커, 체스, 틱택토 등이 있습니다.

게임 이론에서는 완전한 정보를 갖춘 모든 게임에는 안장 지점이 있으므로 순수한 전략으로 해결된다는 것이 입증되었습니다. 완전한 정보가 담긴 모든 게임에는 게임 비용과 동일한 안정적인 보상을 제공하는 한 쌍의 최적 전략이 있습니다. 그러한 게임이 개인적인 움직임으로만 구성되어 있다면 각 플레이어가 최적의 전략을 사용할 때 게임은 게임 비용과 동일한 승리로 매우 확실한 방식으로 끝나야 합니다. 즉, 게임의 해결책을 알면 게임 자체의 의미가 사라진다는 뜻입니다!

완전한 정보가 포함된 게임의 기본 예를 들어보겠습니다. 두 명의 플레이어가 원탁에 니켈을 번갈아 놓고 동전 중앙의 위치를 ​​무작위로 선택합니다(동전이 서로 겹치는 것은 허용되지 않음). 마지막 니켈을 넣는 사람이 승리합니다(다른 사람을 위한 공간이 없을 때). 이 게임의 결과는 본질적으로 미리 결정되어 있다는 것을 쉽게 알 수 있습니다. 동전을 먼저 놓는 사람이 승리하도록 보장하는 특정 전략이 있습니다.

즉, 그는 먼저 테이블 중앙에 니켈을 놓은 다음 대칭적인 움직임으로 각 상대의 움직임에 반응해야 합니다. 분명히 적이 어떻게 행동하든 패배를 피할 수는 없습니다. 상황은 완전한 정보가 포함된 일반적으로 체스와 게임의 경우와 동일합니다. 매트릭스 형식으로 작성된 모든 게임에는 안장점이 있습니다. 이는 솔루션이 순수한 전략에 있음을 의미하므로 이 솔루션이 있는 경우에만 의미가 있습니다. 발견되지 않았습니다. 체스 게임이 항상 백의 승리로 끝나거나 항상 흑의 승리로 끝나거나 항상 무승부로 끝나지만 우리는 아직 정확히 무엇인지 알지 못한다고 가정해 보겠습니다(다행히 체스 애호가에게는). 또한 덧붙이자면, 전략의 수가 너무 많아서 게임을 매트릭스 형태로 가져오고 안장점을 찾는 것이 (불가능하지는 않더라도) 극히 어렵기 때문에 가까운 미래에는 알 수 없을 것 같습니다.

이제 게임에 안장점이 없으면 무엇을 해야 할지 자문해 보겠습니다. 각 플레이어가 하나의 순수 전략을 선택하도록 강요받는다면 할 일이 없습니다. 우리는 미니맥스 원칙을 따라야 합니다. 전략을 "혼합"할 수 있는지, 일부 확률로 무작위로 교체할 수 있는지는 또 다른 문제입니다. 혼합 전략의 사용은 다음과 같이 생각됩니다. 게임은 여러 번 반복됩니다. 게임의 각 게임 전에 플레이어에게 개인적인 차례가 주어지면 그는 자신의 선택을 우연에 "맡기고" "제비를 뽑고" 나온 전략을 취합니다. (우리는 이미 이전 장에서 제비를 구성하는 방법을 알고 있습니다. ).

게임 이론의 혼합 전략은 플레이어 중 누구도 주어진 게임에서 상대가 어떻게 행동할지 알지 못하는 경우 변경 가능하고 유연한 전술의 모델입니다. 이 전술은 (일반적으로 수학적 근거가 없지만) 카드 게임에서 자주 사용됩니다. 동시에 적으로부터 자신의 행동을 숨기는 가장 좋은 방법은 무작위 캐릭터를 부여하여 무엇을 할 것인지 미리 알지 못하는 것입니다.

이제 혼합 전략에 대해 이야기해 보겠습니다. 우리는 플레이어 A와 B의 혼합 전략을 각각 표시할 것입니다. 여기서 (총 1개를 구성) - 플레이어 A가 전략을 사용할 확률 - 플레이어 B가 전략을 사용할 확률

1을 제외한 모든 확률이 0이고 이 확률이 1인 특별한 경우에는 혼합 전략이 순수 전략으로 변합니다.

게임 이론의 기본 정리가 있습니다. 유한한 2인 제로섬 게임에는 적어도 하나의 솔루션, 즉 일반적으로 혼합된 한 쌍의 최적 전략과 그에 상응하는 가격이 있습니다.

게임에 대한 솔루션을 형성하는 한 쌍의 최적 전략에는 다음과 같은 속성이 있습니다. 플레이어 중 한 명이 자신의 최적 전략을 고수하면 다른 플레이어가 자신의 최적 전략에서 벗어나는 것은 수익성이 없습니다. 이 전략 쌍은 게임에서 특정 균형 위치를 형성합니다. 한 플레이어는 이득을 최대로 바꾸고 다른 플레이어는 최소로 바꾸고 싶어하며 각각은 자신의 방향으로 당기고 두 가지 모두의 합리적인 행동으로 균형과 안정적인 이득을 얻습니다. v가 확립되었습니다. 그렇다면 게임은 우리에게 유익하고, 적에게는 유익합니다. 게임이 "공정"하면 두 참가자 모두에게 똑같이 유익합니다.

안장점이 없는 게임의 예를 고려하고 (증거 없이) 해결책을 제시해 봅시다. 게임은 다음과 같습니다. 두 명의 플레이어 A와 B가 동시에 아무 말도 하지 않고 손가락 하나, 둘 또는 세 개를 보여줍니다. 총 손가락 수에 따라 승리가 결정됩니다. 짝수이면 A가 이기고 B로부터 이 숫자와 동일한 금액을 받습니다. 홀수이면 반대로 A는 B에게 이 숫자와 동일한 금액을 지불합니다. 플레이어는 무엇을 해야 합니까?

게임 매트릭스를 만들어 보겠습니다. 한 게임에서 각 플레이어는 손가락 하나, 둘, 세 개를 보여주는 세 가지 전략을 가지고 있습니다. 3x3 행렬은 표 26.5에 나와 있습니다. 추가 오른쪽 열은 행 최소값을 표시하고 추가 하단 행은 열 최대값을 표시합니다.

게임의 낮은 가격은 전략에 해당합니다. 이는 합리적이고 신중한 행동으로 우리가 3 이상을 잃지 않을 것이라고 보장한다는 것을 의미합니다. 작은 위로이지만 여전히 일부 셀에서 발견되는 5의 승리보다 낫습니다. 매트릭스의. L 선수님, 우리에게는 안 좋은 일입니다... 하지만 우리 자신을 위로합시다. 적의 입장은 훨씬 더 나쁜 것 같습니다. 게임 가격이 더 낮습니다. 그는 우리에게 최소한 4개의 합리적인 행동을 줄 것입니다.