지속적인 전략을 가진 적대적인 게임. 행렬 적대 게임 해결 온라인 적대 게임 해결

2인용 제로섬 게임이 호출되며, 각 게임에서는 유한한 전략 세트가 있습니다. 매트릭스 게임의 규칙은 첫 번째 플레이어의 보수와 두 번째 플레이어의 손실인 보수 행렬에 의해 결정됩니다.

매트릭스 게임 적대적인 게임이다. 첫 번째 플레이어는 게임 가격과 동일한 최대 보장(두 번째 플레이어의 행동에 의존하지 않음) 보수를 받고, 유사하게 두 번째 플레이어는 최소 보장 손실을 얻습니다.

아래에 전략 현재 상황에 따라 플레이어의 각 개인 이동에 대한 변형 동작의 선택을 결정하는 일련의 규칙(원칙)으로 이해됩니다.

이제 모든 것에 대해 순서대로 자세히 설명합니다.

보수 매트릭스, 순수 전략, 게임 가격

에 매트릭스 게임 그 규칙이 결정된다 보수 매트릭스 .

첫 번째 플레이어와 두 번째 플레이어라는 두 명의 참가자가 있는 게임을 생각해 보십시오. 첫 번째 플레이어에게 중순수한 전략, 그리고 두 번째 플레이어의 처분에 - N순수한 전략. 게임을 고려하고 있기 때문에 이 게임에 승패가 있는 것은 당연하다.

에 지불 매트릭스 요소는 플레이어의 이익과 손실을 나타내는 숫자입니다. 승패는 포인트, 돈 또는 기타 단위로 표현할 수 있습니다.

보수 행렬을 만들어 보겠습니다.

첫 번째 플레이어가 선택한 경우 나-번째 순수 전략, 그리고 두 번째 플레이어 제이-번째 순수 전략, 첫 번째 플레이어의 보수는 다음과 같습니다. ㅏ아이단위 및 두 번째 플레이어의 손실도 ㅏ아이단위.

왜냐하면 ㅏij + (- ㅏ ij ) = 0, 그러면 설명된 게임은 제로섬 행렬 게임입니다.

매트릭스 게임의 가장 간단한 예는 동전 던지기입니다. 게임의 규칙은 다음과 같습니다. 첫 번째와 두 번째 플레이어는 동전을 던지고 결과는 앞면 또는 뒷면입니다. 앞면과 앞면, 뒷면 또는 뒷면이 동시에 굴려지면 첫 번째 플레이어가 한 단위를 이기고 다른 경우에는 한 단위를 잃습니다(두 번째 플레이어가 한 단위를 얻음). 두 번째 플레이어는 동일한 두 가지 전략을 사용할 수 있습니다. 해당 보수 매트릭스는 다음과 같습니다.

게임 이론의 임무는 최대 평균 이득을 보장하는 첫 번째 플레이어의 전략 선택과 최대 평균 손실을 보장하는 두 번째 플레이어의 전략 선택을 결정하는 것입니다.

매트릭스 게임에서 전략은 어떻게 선택됩니까?

보수 매트릭스를 다시 살펴보겠습니다.

먼저 첫 번째 플레이어가 다음을 사용하는 경우 지불액을 결정합니다. 나 th 순수 전략. 첫 번째 플레이어가 사용하는 경우 나-번째 순수 전략, 그러면 두 번째 플레이어가 첫 번째 플레이어의 보수가 최소가 되는 순수 전략을 사용할 것이라고 가정하는 것이 논리적입니다. 차례로, 첫 번째 플레이어는 최대의 보상을 제공하는 순수한 전략을 사용할 것입니다. 이러한 조건에 따라 첫 번째 플레이어의 보수는 다음과 같이 표시됩니다. V1 , 라고 한다 최대 승리 또는 낮은 게임 가격 .

~에 이러한 값에 대해 첫 번째 플레이어는 다음과 같이 진행해야 합니다. 각 줄에서 최소 요소의 값을 쓰고 그 중에서 최대값을 선택합니다. 따라서 첫 번째 플레이어의 보수는 최소값의 최대값이 됩니다. 따라서 이름 - maximin win. 이 요소의 줄 번호는 첫 번째 플레이어가 선택한 순수 전략의 번호입니다.

이제 두 번째 플레이어가 다음을 사용하는 경우 손실을 결정해 보겠습니다. 제이-번째 전략. 이 경우 첫 번째 플레이어는 두 번째 플레이어의 손실이 최대가 되는 자신의 순수 전략을 사용합니다. 두 번째 플레이어는 손실이 최소화되는 순수한 전략을 선택해야 합니다. 두 번째 플레이어의 손실, 우리는 다음과 같이 표시합니다. V2 , 라고 한다 최소 손실 또는 최고 게임 가격 .

~에 게임 가격 문제 해결 및 전략 결정 두 번째 플레이어에 대해 이러한 값을 결정하려면 다음과 같이 진행하십시오. 각 열에서 최대 요소의 값을 쓰고 그 중에서 최소값을 선택합니다. 따라서 두 번째 플레이어의 손실은 최대값의 최소값이 됩니다. 따라서 이름 - 최소 최대 이득. 이 요소의 열 번호는 두 번째 플레이어가 선택한 순수 전략의 번호입니다. 두 번째 플레이어가 "minimax"를 사용하는 경우 첫 번째 플레이어의 전략 선택에 관계없이 기껏해야 패배합니다. V2 단위.

실시예 1

행의 가장 작은 요소 중 가장 큰 것은 2이며, 이것은 게임의 더 낮은 가격이며, 첫 번째 행은 이에 해당하므로 첫 번째 플레이어의 최대화 전략이 첫 번째입니다. 열의 가장 큰 요소 중 가장 작은 것은 5이며, 이것은 게임의 상위 가격이고 두 번째 열은 이에 해당하므로 두 번째 플레이어의 최소 최대 전략은 두 번째입니다.

게임의 하한가와 상한가를 구하는 방법, maximin과 minimax 전략을 배웠으니, 이제 이러한 개념을 정식으로 지정하는 방법을 배울 차례입니다.

따라서 첫 번째 플레이어의 보장된 보수는 다음과 같습니다.

첫 번째 플레이어는 최소 보수의 최대값을 제공하는 순수 전략을 선택해야 합니다. 이 이득(최대값)은 다음과 같이 표시됩니다.

첫 번째 플레이어는 두 번째 플레이어의 손실이 최대가 되도록 순수 전략을 사용합니다. 이 손실은 다음과 같이 정의됩니다.

두 번째 플레이어는 손실이 최소화되도록 순수 전략을 선택해야 합니다. 이 손실(최소값)은 다음과 같이 표시됩니다.

같은 시리즈의 다른 예입니다.

실시예 2보수 행렬이 있는 행렬 게임이 주어졌을 때

첫 번째 플레이어의 최대 전략, 두 번째 플레이어의 최소 최대 전략, 게임의 낮은 가격과 높은 가격을 결정합니다.

해결책. 보수 행렬의 오른쪽에 행에서 가장 작은 요소를 작성하고 최대값을 표시하고 행렬의 맨 아래에서 열에서 가장 큰 요소를 선택하고 최소값을 선택합니다.

행의 가장 작은 요소 중 가장 큰 것은 3이고, 이것은 게임의 더 낮은 가격이며, 두 번째 행은 이에 해당하므로 첫 번째 플레이어의 최대화 전략은 두 번째입니다. 열의 가장 큰 요소 중 가장 작은 것은 5이며, 이것은 게임의 상위 가격이며 첫 번째 열은 이에 해당하므로 두 번째 플레이어의 최소 최대 전략이 첫 번째입니다.

매트릭스 게임의 안장점

게임의 상한가와 하한가가 같으면 매트릭스 게임에 안장점이 있는 것으로 간주합니다. 그 반대도 마찬가지입니다. 매트릭스 게임에 안장점이 있는 경우 매트릭스 게임의 상한가와 하한 가격은 동일합니다. 해당 요소는 행에서 가장 작고 열에서 가장 크며 게임의 가격과 같습니다.

따라서 이면 은 첫 번째 플레이어의 최적 순수 전략이고 두 번째 플레이어의 최적 순수 전략입니다. 즉, 동일한 전략 쌍에서 게임의 낮은 가격과 높은 가격이 동일하게 달성됩니다.

이 경우 매트릭스 게임에는 순수 전략의 솔루션이 있습니다. .

실시예 3보수 행렬이 있는 행렬 게임이 주어졌을 때

게임의 낮은 가격은 게임의 높은 가격과 동일합니다. 따라서 게임의 가격은 5입니다. 즉 . 게임의 가격은 안장 포인트의 가치와 동일합니다. 첫 번째 플레이어의 최대 전략은 두 번째 순수 전략이고 두 번째 플레이어의 최소 최대 전략은 세 번째 순수 전략입니다. 이 매트릭스 게임은 순수 전략의 솔루션을 가지고 있습니다.

매트릭스 게임 문제를 스스로 해결하고 솔루션을 확인하십시오.

실시예 4보수 행렬이 있는 행렬 게임이 주어졌을 때

게임의 하한가와 상한가를 찾습니다. 이 매트릭스 게임에 안장점이 있습니까?

최적의 혼합 전략을 갖춘 매트릭스 게임

대부분의 경우 매트릭스 게임에는 안장점이 없으므로 해당 매트릭스 게임에는 순수한 전략 솔루션이 없습니다.

그러나 최적의 혼합 전략에 대한 솔루션이 있습니다. 그것들을 찾으려면 경험을 바탕으로 어떤 전략이 바람직한지 추측할 수 있을 만큼 게임이 충분히 반복된다고 가정해야 합니다. 따라서 결정은 확률 및 평균(기대)의 개념과 관련이 있습니다. 최종 솔루션에는 안장점의 유사점(즉, 게임의 하한선과 상한선의 평등)과 이에 해당하는 전략의 유사점이 있습니다.

따라서 첫 번째 플레이어가 최대의 평균 이득을 얻고 두 번째 플레이어가 최소의 평균 손실을 얻으려면 일정 확률로 순수 전략을 사용해야 합니다.

첫 번째 플레이어가 확률이 있는 순수 전략을 사용하는 경우 , 벡터 첫 번째 플레이어의 혼합 전략이라고 합니다. 즉, 순수 전략의 "혼합물"입니다. 이 확률의 합은 1과 같습니다.

두 번째 플레이어가 확률이 있는 순수 전략을 사용하는 경우 , 벡터 두 번째 플레이어의 혼합 전략이라고 합니다. 이 확률의 합은 1과 같습니다.

첫 번째 플레이어가 혼합 전략을 사용하는 경우 피, 그리고 두 번째 플레이어 - 혼합 전략 큐, 그렇다면 의미가 있습니다. 기대값 첫 번째 플레이어가 이깁니다(두 번째 플레이어가 집니다). 그것을 찾으려면 첫 번째 플레이어의 혼합 전략 벡터(1행 행렬), 보수 행렬, 두 번째 플레이어의 혼합 전략 벡터(1열 행렬)를 곱해야 합니다.

실시예 5보수 행렬이 있는 행렬 게임이 주어졌을 때

첫 번째 플레이어의 혼합 전략이 이고 두 번째 플레이어의 혼합 전략이 인 경우 첫 번째 플레이어의 이득(두 번째 플레이어의 손실)에 대한 수학적 기대치를 결정합니다.

해결책. 첫 번째 플레이어의 이득(두 번째 플레이어의 손실)의 수학적 기대에 대한 공식에 따르면 첫 번째 플레이어의 혼합 전략 벡터, 보수 행렬 및 두 번째 플레이어의 혼합 전략 벡터의 곱과 같습니다.

첫 번째 플레이어는 게임이 충분한 횟수만큼 반복될 경우 최대 평균 보상을 제공하는 혼합 전략이라고 합니다.

최적의 혼합 전략 두 번째 플레이어는 게임이 충분한 횟수만큼 반복되면 최소 평균 손실을 제공하는 혼합 전략이라고 합니다.

순수 전략의 경우 maximin 및 minimax 표기법과 유추하여 최적 혼합 전략은 다음과 같이 표시됩니다(수학적 기대치, 즉 첫 번째 플레이어의 이득과 두 번째 플레이어의 손실의 평균과 연결됨).

이 경우 기능에 대한 이자형 안장점이 있다 , 이는 평등을 의미합니다.

최적의 혼합 전략과 안장점을 찾기 위해, 즉 혼합 전략으로 매트릭스 게임을 풀다 , 행렬 게임을 선형 계획법 문제, 즉 최적화 문제로 축소하고 해당 선형 계획법 문제를 해결해야 합니다.

행렬 게임을 선형 계획법 문제로 축소

혼합 전략의 행렬 게임을 풀려면 직선을 구성해야 합니다. 선형 계획법 문제그리고 이중 작업. 이중 문제에서는 제약 시스템의 변수 계수, 상수 항 및 목표 함수의 변수 계수를 저장하는 증강 행렬이 전치됩니다. 이 경우 원래 문제의 목표 함수의 최소값은 쌍대 문제의 최대값과 연결됩니다.

직접 선형 계획법 문제의 목표 함수:

선형 계획법의 직접 문제에서 제약 조건 시스템:

이중 문제의 목표 기능:

이중 문제의 제약 시스템:

직접 선형 계획법 문제의 최적 계획을 나타냅니다.

이중 문제의 최적 계획은 다음과 같이 표시됩니다.

해당 최적 설계에 대한 선형 형식은 및 로 표시됩니다.

최적 계획의 해당 좌표의 합으로 찾아야 합니다.

이전 섹션의 정의와 최적 계획의 좌표에 따라 다음과 같은 첫 번째 플레이어와 두 번째 플레이어의 혼합 전략이 유효합니다.

수학자들은 다음을 증명했습니다. 게임 가격 는 다음과 같이 최적 계획의 선형 형태로 표현됩니다.

즉, 최적 계획의 좌표 합계의 역수입니다.

우리 실무자들은 이 공식을 혼합 전략의 매트릭스 게임에만 사용할 수 있습니다. 처럼 최적의 혼합 전략을 찾기 위한 공식 각각 첫 번째 및 두 번째 플레이어:

여기서 두 번째 요소는 벡터입니다. 이전 단락에서 이미 정의한 것처럼 최적의 혼합 전략도 벡터입니다. 따라서 숫자(게임 가격)에 벡터(최적 계획의 좌표 포함)를 곱하면 벡터도 얻습니다.

실시예 6보수 행렬이 있는 행렬 게임이 주어졌을 때

게임 가격 찾기 V최적의 혼합 전략 및 .

해결책. 우리는 이 행렬 게임에 해당하는 선형 계획법 문제를 구성합니다.

우리는 직접적인 문제의 해결책을 얻습니다.

찾은 좌표의 합으로 최적 계획의 선형 형태를 찾습니다.

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

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

소개

1. 이론적인 부분

1.3 게임 순서 2v2

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인용 게임으로 볼 수 있습니다.

첫 번째 플레이어는 m개의 전략 i =1, 2,… 첫 번째 플레이어가 자신의 것을 사용하는 경우 두 번째 플레이어로 인한 첫 번째 플레이어의 지불 i번째 전략, 그리고 두 번째 - j 번째 전략.

각 플레이어는 한 번의 이동을 합니다. 첫 번째 플레이어는 i 번째 전략(i = 1, 2, ..., m)을 선택하고 두 번째 플레이어는 --당신의 j번째전략(j = 1, 2,…< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

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

두 명의 플레이어가 하는 제로섬 행렬 게임을 간단히 행렬 게임이라고 합니다. 분명히 매트릭스 게임은 적대적 게임에 속합니다. 매트릭스 게임을 정의하려면 첫 번째 플레이어의 보수 m 정도의 매트릭스 A = (a ij)를 지정하는 것으로 충분하다는 정의에 따릅니다.

보수 매트릭스 고려

그런 다음 행렬 A가 있는 행렬 게임의 각 게임 실행은 첫 번째 플레이어의 선택으로 축소됩니다. i번째 라인, 그리고 j 번째 열의 두 번째 플레이어와 첫 번째 플레이어(두 번째를 희생하여)는 i 번째 행과 j 번째 열의 교차점에서 행렬 A에 위치한 보수를 받습니다.

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

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

게임 연구에서 가장 중요한 것은 플레이어를 위한 최적의 전략 개념입니다. 이 개념은 직관적으로 다음과 같은 의미를 갖습니다. 플레이어의 전략은 이 전략의 적용이 다른 플레이어의 모든 가능한 전략에 대해 가장 큰 보장된 보상을 제공하는 경우 최적입니다. 이러한 위치를 기반으로 첫 번째 플레이어는 공식 (1.1)에 따라 보수 행렬 A를 다음과 같이 조사합니다. 각 값 i(i = 1, 2, ..., m)에 대해 최소 보수 값은 다음에 따라 결정됩니다. 두 번째 플레이어가 사용하는 전략에 대해

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

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

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

최적의 행동을 보이는 두 번째 플레이어는 가능한 한 자신의 전략을 희생하면서 첫 번째 플레이어의 보상을 최소화하기 위해 노력해야 합니다. 따라서 두 번째 플레이어의 경우

즉, 첫 번째 플레이어의 최대 보수가 결정됩니다. 단, 두 번째 플레이어는 j번째 클린전략, 두 번째 플레이어는 첫 번째 플레이어가 최소 보수를 받는 자신의 j = j 1 전략을 찾습니다. 즉, 다음을 찾습니다.

정의. 공식 (1.5)에 의해 결정된 숫자 β를 게임의 순 상한 비용이라고 하며 첫 번째 플레이어가 자신의 전략으로 인해 자신에게 보장할 수 있는 최대 이득을 보여줍니다. 즉, 그의 순수 전략을 적용함으로써 첫 번째 플레이어는 적어도 b의 보수를 확보할 수 있고, 두 번째 플레이어는 그의 순수 전략을 적용하여 첫 번째 플레이어가 c보다 많이 이기는 것을 방지할 수 있습니다.

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

n = b = c (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.

증거. 최소값과 최대값의 정의에서 다음과 같이 표시됩니다.

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

부등식(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, y 0) f (x 0, y 0) f (x 0, y) (1.14)

모든 x A 및 y B에 대해

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

매트릭스 게임의 연구는 순수 전략에서 안장점을 찾는 것으로 시작됩니다. 매트릭스 게임에 순수 전략의 안장점이 있다면 이 점을 찾는 것으로 게임 연구는 끝납니다. 매트릭스 게임에서 순수 전략에 안장점이 없다면, 우리는 이 게임의 더 낮은 순수 가격과 더 높은 순수 가격을 찾을 수 있습니다. 게임의 더 낮은 가격보다 적은 보수를 받는 것을 확신할 수 있습니다. 순수한 전략에서 안장이 없는 매트릭스 게임에서 플레이어의 행동에 대한 이러한 권장 사항은 연구자와 실무자를 만족시킬 수 없습니다. 순수 전략 적용의 비밀과 파티 형태의 게임 반복 반복 가능성을 사용하여 매트릭스 게임의 솔루션을 개선해야 합니다. 예를 들어, 체스, 체커, 축구의 일련의 게임이 진행되고 플레이어가 상대방이 내용을 인식하지 못하는 방식으로 전략을 적용할 때마다 평균적으로 특정 보수를 달성합니다. 게임의 전체 시리즈를 재생합니다. 이러한 보수는 평균적으로 게임의 낮은 가격보다 크고 게임의 높은 가격보다 낮습니다. 이 평균값이 클수록 더 나은 전략플레이어에 의해 적용됩니다. 따라서 순수 전략을 특정 확률로 무작위로 적용하는 아이디어가 떠올랐습니다. 이것은 사용의 비밀을 완전히 보장합니다. 각 플레이어는 평균 보수를 최대화하고 그 과정에서 최적의 전략을 얻을 수 있는 방식으로 순수 전략을 적용할 확률을 변경할 수 있습니다. 이 아이디어는 혼합 전략의 개념으로 이어졌습니다.

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

따라서 첫 번째 플레이어가 m개의 순수 전략 1, 2, … i, … m을 갖고 있다면 그의 혼합 전략 x는 x = (x 1 , x 2 , ..., x i ,…, x t ) 관계

x 나는 0 (나는 = 1, 2, ... , m), = 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 \u003d 1 - x 1은 두 번째 전략을 사용할 확률입니다. 유사하게 두 번째 플레이어의 경우: 1 - 첫 번째 전략을 사용할 확률, y 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)이 모두 엄격하면 정리 x1 = x2 = 0에 따라 (1.25)와 모순됩니다. 그러나 a 12 a 22 이면 부등식(1.27) 중 하나는 엄격하고 다른 하나는 등식입니다. 더욱이, 평등은 a 12 및 a 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 - 단위 길이의 단면 찾기

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

두 개의 축 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=j 0에 대해 두 번째 플레이어의 전략이 점 M 0을 형성하고 제약 집합의 하한의 최대값이 다음과 평행한 세그먼트로 표시됩니다. 축 이 경우 첫 번째 플레이어는 최적값이 무한히 많으며 게임의 가격이 그림 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와 from 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,x2=? 0

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

이제 행렬을 고려하십시오.

x 1 =? 0,x2=? 0

게임 가격.

이 비율은 요구 사항과 상충하므로 적합하지 않습니다.

이제 행렬을 고려하십시오.

x 1 = , x 2 = ? 0,

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

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

이제 행렬을 고려하십시오.

x 1 \u003d, x 2 \u003d 0, x 2 \u003d 0 이후로, 그리고 버립니다.

이제 행렬을 고려하십시오.

x 1 = , x 2 = ? 0. x 1 \u003d 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)은 따뜻한 식사를 공급하는 세 회사(A 1 , A 2 , A 3) 중 하나를 선택하고 회사 경영진(플레이어 2)은 가능한 세 가지 옵션(B 1 , B 2 , 나 3) . 계약에 서명한 후 노동 조합은 다음과 같은 지불 매트릭스를 형성하며 그 요소는 접시 세트 비용을 나타냅니다.

게임에 다음과 같은 보수 행렬이 주어집니다.

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

2 그가 첫 번째 전략을 사용한다면,

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

얻어진 값을 표 1에 요약하였다.

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

배치 번호	2인 플레이 전략	첫 번째 플레이어 승리

표 3은 두 번째 플레이어의 두 번째 전략에서 첫 번째 플레이어가 두 번째 또는 세 번째 전략을 사용하여 가장 큰 보상 3을 받는 것을 보여줍니다. 첫 번째 플레이어는 최대의 보상을 원하기 때문에 두 번째 플레이어의 두 번째 전략에 자신의 두 번째 전략으로 대응합니다. 첫 번째 플레이어의 두 번째 전략으로 두 번째 플레이어는 다음을 잃게 됩니다.

1 그가 첫 번째 전략을 적용하면

3 그가 2차 전략을 사용한다면,

그가 세 번째 전략을 사용한다면 4.

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

배치 번호	1인 전략	2번째 선수의 패배

표 2는 첫 번째 플레이어의 두 번째 전략에서 두 번째 플레이어가 첫 번째 전략을 적용할 경우 최소 손실 1을 가짐을 보여줍니다. 두 번째 플레이어는 덜 지기를 원하므로 첫 번째 플레이어의 두 번째 전략에 대한 응답으로 첫 번째 전략을 적용합니다. 얻어진 결과는 표 5에 요약되어 있다.

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

배치 번호

2인 플레이 전략

첫 번째 플레이어의 총 상금

1인 전략

테이블에서. 두 번째 줄에 있는 두 번째 플레이어의 전략 열에서 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 및 두 번째 플레이어의 첫 번째, 두 번째, 세 번째 전략에 해당하는 열에 표시됩니다.

두 번째 플레이어의 모든 총 손실 중 가장 작은 것은 4입니다. 첫 번째 전략으로 얻을 수 있으므로 세 번째 게임에서 두 번째 플레이어는 첫 번째 전략을 적용해야 합니다. 열에 두 게임에서 첫 번째 플레이어의 가장 큰 총 지불액을 게임 수로 나눈 값을 넣습니다. w 열은 두 게임에서 두 번째 플레이어의 가장 작은 총 손실을 게임 수로 나눈 값을 포함합니다. 즉, ; 이 값의 산술 평균은 v 열에 표시됩니다. 즉 = 이 숫자는 두 개의 "플레이한" 게임이 있는 게임 가격의 대략적인 값으로 간주됩니다.

따라서 게임의 두 세트에 대해 다음 표 4를 얻습니다.

표 6. 두 게임에서 플레이어의 총 이득 및 손실

2인 플레이 전략

첫 번째 플레이어의 총 상금

1인 전략

두 번째 플레이어의 총 손실

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

그의 첫 번째 전략에서 3 + 5 = 8,

1 +4 = 5, 두 번째 전략 사용 시,

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

첫 번째 플레이어의 이러한 총 보수는 표 6의 세 번째 행과 그의 전략 1, 2, 3에 해당하는 열에 기록됩니다. 첫 번째 플레이어의 가장 큰 총 보수 8은 첫 번째 전략으로 얻어지기 때문에 그에 따라 첫 번째 플레이어를 선택합니다 .

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

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

2 + 5=7 그의 두 번째 전략,

3 + 7=10 그의 세 번째 전략.

이 총 손실은 표의 세 번째 줄에 기록됩니다. 6 및 두 번째 플레이어의 첫 번째, 두 번째, 세 번째 전략에 해당하는 열에 표시됩니다. 그의 모든 손실 중 7이 가장 작고 첫 번째 및 두 번째 전략으로 얻은 다음 두 번째 플레이어는 첫 번째 전략을 적용해야 합니다.

테이블에서. 열의 세 번째 행에 6이 있고 세 게임에서 첫 번째 플레이어의 최대 총 상금을 게임 수로 나눈 값, 즉 ; 열 w는 세 게임에서 두 번째 플레이어의 가장 작은 총 손실을 게임 수로 나눈 값을 포함합니다. v 열에 산술 평균을 넣습니다.

따라서 우리는 테이블을 얻습니다. 3당 7명.

표 7. 3경기에서 플레이어의 총 승패

배치 번호

2인 플레이 전략

첫 번째 플레이어의 총 상금

1인 전략

두 번째 플레이어의 총 손실

표 8. 20경기를 치른 파이널 테이블

배치 번호

2인 플레이 전략

첫 번째 플레이어의 총 상금

1인 전략

두 번째 플레이어의 총 손실

테이블에서. 도 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 문제에서는 농업 문화가 고려되었고 전략은 밭에 50x50을 심는 것이 더 낫다는 것을 보여주고 게임의 가격은 375만 루블이었습니다. 그리고 mx2 문제에서 한 쌍이 고려되었으며, 그 전략은 공원과 영화관에 가는 것이 더 저렴하고 가격과 비용은 4.3 루블이 될 것임을 보여주었습니다.

두 개의 레스토랑을 고려한 매트릭스 방법에 대한 작업을 모델링했으며, 문제의 솔루션은 최적의 혼합 전략을 적용할 때 첫 번째 레스토랑의 이익이 1,560만 루블이 되고 최적의 혼합 전략을 사용할 때 두 번째 식당에서는 첫 번째 식당이 1,560만 루블 이상을 벌 수 없습니다. 그래픽 방식의 솔루션은 오류를 제공했으며 게임 가격은 1490만 루블이었습니다.

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

사용된 소스 목록

1) Vilisov V.Ya. 강의 노트 "게임 이론 및 통계 솔루션", - 분기 - "Voskhod" MAI. 1979. 146p.

2) Krushevsky A.V. 게임 이론, - 키예프: Vishcha 학교, 1977. - 216 p.

3) Cherchmen U., Akof R., Arnof L., 운영 연구 소개. - 남: 과학. 1967. - 488페이지.

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일 추가됨

여러 번 반복되는 게임, 독특한 속성과 단계. 실제 사용을 위한 혼합 전략, 조건 및 기회. 2 x 2 게임을 푸는 분석 방법 직사각형 게임의 기본 정리. 대수 솔루션.

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

바이매트릭스 게임 이론의 기본 정의. 바이매트릭스 게임 "Student-Teacher"의 예. 바이매트릭스 게임의 혼합 전략. "평형 상황"을 검색하십시오. 각 플레이어가 두 가지 전략을 가지고 있는 경우에 대한 2x2 바이매트릭스 게임 및 공식.

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

매트릭스 및 적대적 게임에 대한 일반 정보 연구. 위치 게임, 나무, 정보 집합의 개념입니다. 최대 원리와 평형 원리의 고려. 파레토 최적. 위치 적 비 적대 게임, 그 속성.

학기 논문, 2014년 10월 17일 추가됨

게임 이론은 충돌에서 최적의 결정을 내리기 위한 수학적 모델의 연구인 수학의 한 분야입니다. 반복적인 브라운-로빈슨 방법. 매트릭스 게임을 풀기 위한 모노톤 반복 알고리즘.

2007년 8월 8일에 추가된 논문

보수 매트릭스의 편집, 게임의 하한 및 상한 순 가격, 플레이어의 최대값 및 최소값 전략을 검색합니다. 지불 매트릭스의 단순화. 선형 계획법 문제로의 축소와 "해법 검색" 추가 기능을 사용하여 행렬 게임을 풉니다.

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

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

학기 논문, 2013년 8월 17일 추가됨

심플렉스 방법에 대한 기본 정보, 선형 계획법에서의 역할 및 중요성 평가. 기하학적 해석과 대수적 의미. 선형 함수의 최대값과 최소값 찾기, 특수한 경우. 행렬 심플렉스 방법으로 문제를 해결합니다.

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

기능의 구조와 프로세스를 반영하는 컴퓨팅 시스템의 수학적 모델을 구성하는 기술. 평균 작업 중 파일 액세스 수입니다. 외부 메모리 드라이브에 파일을 저장할 가능성 결정.

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

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

게임 이론은 갈등이나 불확실성의 조건에서 의사 결정의 수학적 모델의 이론입니다. 게임에서 당사자의 행동은 특정 전략, 즉 일련의 행동 규칙을 특징으로 한다고 가정합니다. 한쪽의 이득이 필연적으로 다른 쪽의 손실로 이어진다면, 그들은 적대적 게임을 말합니다. 전략의 집합이 제한되어 있으면 그 게임을 매트릭스 게임이라고 하며 매우 간단하게 솔루션을 얻을 수 있습니다. 게임 이론의 도움으로 얻은 솔루션은 경쟁자의 반대 또는 외부 환경의 불확실성에 직면하여 계획을 세우는 데 유용합니다.

바이매트릭스 게임이 적대적이라면 플레이어 2의 수익 매트릭스는 플레이어 1의 수익 매트릭스에 의해 완전히 결정됩니다(이 두 매트릭스의 해당 요소는 부호만 다름). 따라서 바이매트릭스 적대적 게임은 하나의 매트릭스(플레이어 1의 보수 매트릭스)로 완전히 기술되므로 매트릭스 게임이라고 한다.

이 게임은 적대적입니다. 그것에서 j \u003d x2 - O, P 및 R (O, O] \u003d H (P, P) \u003d -I 및 R (O, P) \u003d R (P, O) \u003d 1 또는 행렬 형태 OP

게임의 일부 클래스 Г를 "미러 닫힘"으로 설정합니다. 각 게임과 함께 미러 동형 게임이 포함되어 있습니다(주어진 게임에 미러 동형인 모든 게임은 서로 동형이기 때문에 방금 말한 내용에 따라 하나의 미러 동형 게임에 대해 말할 수 있습니다). 이러한 클래스는 예를 들어 모든 적대 게임의 클래스 또는 모든 매트릭스 게임의 클래스입니다.

적대적 게임에서 수용 가능한 상황의 정의를 상기하면, 매트릭스 게임의 혼합 확장에서 상황(X, Y)이 어떤 x G x 부등식이

게임을 대칭 게임으로 변환하는 과정을 대칭화라고 합니다. 여기에서는 대칭화의 한 가지 방법을 설명합니다. 근본적으로 다른 버전의 대칭이 섹션 26.7에서 제공됩니다. 이러한 대칭화의 두 가지 변형은 실제로 임의의 적대적 게임에 적용할 수 있지만 매트릭스 게임에 대해서만 공식화되고 증명될 것입니다.

따라서 일반 적대 게임 이론의 초기 용어 및 명칭은 매트릭스 게임 이론의 해당 용어 및 명칭과 일치합니다.

유한 적대(매트릭스) 게임의 경우 이러한 극한값의 존재가 10장에서 증명되었습니다. 1, 그리고 요점은 그들의 평등을 확립하거나 적어도 그들의 불평등을 극복할 방법을 찾는 것이었다.

매트릭스 게임에 대한 고려는 플레이어의 초기에 주어진 전략에서 평형 상황이 없는(그리고 e-평형 상황이 없을지라도 충분히 작은 e > 0에 대한) 적대적 게임이 있음을 이미 보여줍니다.

그러나 각 유한(매트릭스) 게임은 무한 게임으로 확장될 수 있습니다. 예를 들어 각 플레이어에게 여러 가지 우세 전략(22장 1 참조)을 제공합니다. 분명히, 플레이어의 전략 세트의 그러한 확장은 실제로 그의 가능성의 확장을 의미하지 않으며 확장된 게임에서의 그의 실제 행동은 원래 게임에서의 그의 행동과 다르지 않아야 합니다. 따라서 우리는 안장점이 없는 무한 적대 게임의 충분한 수의 예를 즉시 얻었습니다. 이런 예도 있습니다.

따라서 무한 적대 게임에서 최대화 원칙을 구현하기 위해서는 유한(매트릭스) 게임의 경우와 같이 플레이어의 전략적 능력의 일부 확장이 필요합니다. 96용

매트릭스 게임(1장, 17장 참조)의 경우와 같이 일반적인 적대적 게임의 경우 중요한 역할은 혼합 전략 스펙트럼의 개념에 의해 수행되지만 여기에서는 보다 일반적인 정의가 주어져야 합니다.

마지막으로, 임의의 적대적 게임에서 플레이어 1의 모든 혼합 전략 세트는 행렬에서와 같이

적대적 게임에 대한 고려조차도 유한 게임을 포함한 많은 수의 매트릭스 게임이 원래의 순수 전략이 아니라 일반화된 혼합 전략에서만 평형 상황을 가지고 있음을 보여줍니다. 따라서 일반적이고 적대적이지 않고 협력적이지 않은 게임의 경우 혼합 전략에서 정확하게 균형 상황을 찾는 것이 자연스럽습니다.

따라서 예를 들어(그림 3.1 참조) "계약자"는 행동 불확실성을 거의 다룰 필요가 없다는 점을 이미 언급했습니다. 그러나 "관리자" 유형의 개념적 수준을 취하면 모든 것이 정반대입니다. 일반적으로 그러한 "의사 결정권자"가 직면해야 하는 주요 유형의 불확실성은 "갈등"입니다. 이제 우리는 이것이 일반적으로 엄격하지 않은 경쟁임을 분명히 할 수 있습니다. 다소 덜 자주, "관리자"는 "자연적 불확실성"의 조건에서 결정을 내리고, 훨씬 더 드물게 그는 엄격하고 적대적인 갈등을 겪습니다. 또한 "관리자"가 결정을 내릴 때 이해 충돌이 발생합니다. 말하자면 "한번", 즉 우리 분류에서 그는 종종 게임의 한 게임(때로는 매우 적은 수)만 플레이합니다. 결과를 평가하기 위한 척도는 종종 양적보다 정성적입니다. "관리자"의 전략적 독립성은 상당히 제한적입니다. 위의 사항을 고려하면 이러한 규모의 문제 상황은 가장 자주 순수 전략에서 비협조적, 적대적 이중 매트릭스 게임을 사용하여 분석해야 한다고 주장할 수 있습니다.

매트릭스 적대적 게임을 해결하기 위한 원리

결과적으로 위에서 설명한 게임에서 상대방이 선택한 전략을 고수할 것으로 예상하는 것이 합리적입니다. max min fiv = min max Aiy인 행렬 적대적 게임>

그러나 모든 매트릭스 적대적 게임이 아주 명확한 것은 아니며 일반적으로

따라서 일반적인 경우 /uxl 차원의 행렬 적대적 게임을 풀기 위해서는 한 쌍의 이중 선형 계획법 문제를 풀어야 최적의 전략 세트가 생성되고 / 게임 비용 v.

두 사람의 매트릭스 적대적 게임은 어떻게 정의됩니까?

행렬 적대적 게임을 단순화하고 해결하는 방법은 무엇입니까?

두 사람의 게임의 경우, 그들의 이익을 정반대라고 생각하는 것이 당연합니다. 게임은 적대적입니다. 따라서 한 플레이어의 수익은 다른 플레이어의 손실과 같습니다(두 플레이어의 수익 합계는 0이므로 이름이 제로섬 게임입니다). 우리는 각 플레이어가 제한된 수의 대안을 가지고 있는 게임을 고려할 것입니다. 이러한 제로섬 2인 게임에 대한 보수 함수는 행렬 형식(보수 행렬 형식)으로 제공될 수 있습니다.

이미 언급했듯이 최종 적대 게임을 매트릭스라고 합니다.

MATRIX GAMES - 두 명의 플레이어가 참여하고 각 플레이어는 제한된 수의 전략을 가지고 있는 적대적 게임 클래스입니다. 한 플레이어가 m개의 전략을 갖고 다른 플레이어가 n개의 전략을 가지고 있다면 차원 txn의 게임 매트릭스를 구성할 수 있습니다. 미. 안장점이 있을 수도 있고 없을 수도 있습니다. 후자의 경우

유한한 제로섬 페어 게임을 고려하십시오. 로 나타내다 ㅏ플레이어의 보수 ㅏ, 그리고 통해 비- 플레이어 승리 비. 왜냐하면 ㅏ = –비, 그런 다음 이러한 게임을 분석할 때 이 두 숫자를 모두 고려할 필요가 없습니다. 플레이어 중 한 명의 보수를 고려하는 것으로 충분합니다. 예를 들어, ㅏ. 다음은 프레젠테이션의 편의를 위해 측면에서 ㅏ우리는 조건부로 " 우리"그리고 옆 비 – "적".

하자 중가능한 전략 ㅏ 1 , ㅏ 2 , …, 이다, 그리고 적 N가능한 전략 비 1 , 비 2 , …, 비앤(이러한 게임을 게임이라고 합니다. m×n). 각 측이 특정 전략을 선택했다고 가정합니다. 일체 포함, 적 비제이. 게임이 개인적인 움직임으로만 구성된 경우 전략 선택 일체 포함그리고 비제이게임의 결과(양수 또는 음수)를 고유하게 결정합니다. 이 이득을 다음과 같이 표시합시다. 아이즈(전략을 선택하면 승리 일체 포함, 그리고 적 - 전략 비제이).

게임에 개인의 무작위 이동 외에도 한 쌍의 전략에 대한 보상이 포함되어 있으면 일체 포함, 비제이모든 무작위 이동의 결과에 따라 달라지는 무작위 변수입니다. 이 경우 기대 보수의 자연 추정치는 다음과 같습니다. 무작위 승리에 대한 수학적 기대. 편의상 다음으로 표시하겠습니다. 아이즈보상 자체(무작위 이동이 없는 게임에서)와 수학적 기대(무작위 이동이 있는 게임에서) 모두.

값을 알고 있다고 가정합니다. 아이즈각 전략 쌍에 대해. 이 값은 행이 우리의 전략에 해당하는 행렬로 작성할 수 있습니다( 일체 포함), 열에는 상대방의 전략이 표시됩니다( 비제이):

비제이아이	비 1	비 2	…	비앤
ㅏ 1	ㅏ 11	ㅏ 12	…	ㅏ 1N
ㅏ 2	ㅏ 21	ㅏ 22	…	ㅏ 2N
…	…	…	…	…
이다	이다 1	이다 2	…	암

이러한 행렬을 게임의 보수 매트릭스또는 단순히 게임 매트릭스.

많은 수의 전략이 있는 게임에 대한 보수 매트릭스를 구성하는 것은 어려운 작업일 수 있습니다. 예를 들어, 체스 게임의 경우 가능한 전략의 수가 너무 많아 보수 행렬의 구성이 실제로 불가능합니다. 그러나 원칙적으로 모든 유한 게임은 행렬 형태로 축소될 수 있습니다.

고려하다 예 1 4×5 적대적 게임. 우리에게는 4가지 전략이 있고 적에게는 5가지 전략이 있습니다. 게임 매트릭스는 다음과 같습니다.

비제이아이	비 1	비 2	비 3	비 4	비 5
ㅏ 1
ㅏ 2
ㅏ 3
ㅏ 4

우리는 어떤 전략(즉, 플레이어 ㅏ) 사용? 우리가 어떤 전략을 선택하든 합리적인 적수는 우리의 보수가 최소화되는 전략으로 이에 대응할 것입니다. 예를 들어 전략을 선택하면 ㅏ 3(10승의 유혹), 상대는 대응 전략을 선택 비 1, 그리고 우리의 보수는 1에 불과합니다. 분명히 주의 원칙(게임 이론의 주요 원칙)에 따라 다음과 같은 전략을 선택해야 합니다. 우리의 최소 이득은 최대입니다.

로 나타내다 나는전략에 대한 최소 보수 가치 일체 포함:

다음 값이 포함된 열을 게임 매트릭스에 추가합니다.

비제이아이	비 1	비 2	비 3	비 4	비 5	행의 최소값 나는
ㅏ 1
ㅏ 2
ㅏ 3
ㅏ 4							최대치

전략을 선택할 때 가치가 있는 전략을 선택해야 합니다. 나는최고. 이 최대값을 다음과 같이 표시합시다. α :

값 α ~라고 불리는 낮은 게임 가격또는 최대치(최대 최소 승리). 플레이어 전략 ㅏ최대값에 해당하는 α , 라고 한다 극대화 전략.

이 예에서 최대 α 는 3이고(표의 해당 셀은 회색으로 강조 표시됨) 최대화 전략은 다음과 같습니다. ㅏ네 . 이 전략을 선택하면 적의 행동에 대해 최소 3승(적의 "불합리한" 행동의 경우 더 많을 수 있음)에서 승리할 수 있습니다. 이 값은 보장된 최소값이며 보장할 수 있습니다. 가장 신중한("재보험") 전략을 고수합니다.

이제 우리는 적에 대해 비슷한 추론을 수행 할 것입니다. 비 비 ㅏ 비 2 - 우리는 그에게 대답할 것이다 ㅏ .

로 나타내다 β j ㅏ 비) 전략을 위해 일체 포함:

β j β :

7. 더 높은 가치의 게임이란 무엇입니까 이제 우리는 상대방을 위해 비슷한 추론을 수행 할 것입니다 비. 그는 우리의 이익을 최소화하는 데 관심이 있습니다. 즉, 우리에게 덜 주는 것입니다. 그러나 그는 우리의 행동에 의존해야 하며, 이는 그에게 최악입니다. 예를 들어 그가 전략을 선택하면 비 1, 그러면 우리는 전략으로 그에게 대답할 것입니다. ㅏ 3, 그리고 그는 우리에게 10을 줄 것입니다. 비 2 - 우리는 그에게 대답할 것이다 ㅏ 2, 그리고 그는 8을 줄 것입니다. 분명히, 신중한 상대는 다음과 같은 전략을 선택해야 합니다. 우리의 최대 이득은 최소일 것입니다.

로 나타내다 β j지불 행렬 열의 최대 값 (플레이어의 최대 지불 ㅏ, 또는 동일하게 플레이어의 최대 손실 비) 전략을 위해 일체 포함:

다음 값이 포함된 행을 게임 매트릭스에 추가합니다.

전략을 선택하면 적은 가치가 있는 전략을 선호할 것입니다. β j최저한의. 로 표기하자. β :

값 β ~라고 불리는 최고 게임 가격또는 미니맥스(최소 최대 승리). 미니맥스에 해당하는 상대방(플레이어)의 전략 비), 호출 미니맥스 전략.

Minimax는 합리적인 상대가 확실히 우리에게주지 않을 이득의 가치입니다 (즉, 합리적인 상대는 β ). 이 예에서 minimax β 5와 같으며(표의 해당 셀은 회색으로 강조 표시됨) 상대방의 전략으로 달성됩니다. 비 3 .

따라서 주의 원칙("항상 최악을 예상하라!")에 따라 전략을 선택해야 합니다. ㅏ 4, 그리고 적 - 전략 비삼 . 주의 원칙은 게임 이론의 기본이며 미니맥스 원리.

고려하다 예 2. 선수들이 ㅏ그리고 에세 숫자 중 하나는 동시에 그리고 서로 독립적으로 쓰여집니다: "1", "2" 또는 "3". 쓰여진 숫자의 합이 짝수이면 플레이어는 비플레이어에게 지불 ㅏ이 금액. 금액이 홀수이면 플레이어가 이 금액을 지불합니다. ㅏ플레이어 에.

게임의 보수 매트릭스를 기록하고 게임의 하한 및 상한 가격을 찾아봅시다(전략 번호는 쓰여진 숫자에 해당함).

플레이어 ㅏ최대화 전략을 준수해야 합니다. ㅏ 1: 최소 -3 승리(즉, 최대 3 패배). Minimax 플레이어 전략 비어떤 전략이든 비 1 및 비 2, 그는 4를 넘지 않도록 보장합니다.

플레이어의 관점에서 보수 행렬을 작성하면 동일한 결과를 얻을 수 있습니다. 에. 사실 이 행렬은 플레이어의 관점에서 구성한 행렬을 전치시켜 얻어진다. ㅏ, 그리고 요소의 부호를 반대 방향으로 변경합니다(플레이어의 보수 이후 ㅏ플레이어의 손실입니다 에):

이 매트릭스를 기반으로 플레이어는 비어떤 전략이든 따라야 함 비 1 및 비 2 (그리고 그는 4 이상을 잃지 않을 것입니다), 그리고 플레이어 ㅏ– 전략 ㅏ 1 (그리고 그는 3 이상을 잃지 않을 것입니다). 보시다시피 결과는 위에서 얻은 것과 완전히 동일하므로 우리가 수행하는 플레이어의 관점에서 분석은 중요하지 않습니다.

8 가치 있는 게임이란?

9. 미니맥스 원칙은 무엇으로 구성되어 있습니까? 2. 게임의 낮은 가격과 높은 가격. 미니맥스 원리

보수 행렬이 있는 유형의 행렬 게임을 고려하십시오.

만약 플레이어가 하지만전략을 선택할 것이다 아이, 모든 가능한 보수는 요소가 됩니다. 나-행렬의 행 에서. 선수로서는 최악 하지만플레이어가 에에 적합한 전략을 적용합니다. 최저한의이 줄의 요소, 플레이어의 보수 하지만숫자와 같을 것입니다.

따라서 최대의 보상을 얻기 위해 플레이어는 하지만당신은 숫자에 대한 전략 중 하나를 선택해야 최고.

게임 이론에서 자세히 설명된 가장 간단한 경우는 제로섬 유한 쌍 게임(두 사람 또는 두 연합의 적대 게임)입니다. 이해가 반대인 두 명의 플레이어 A와 B가 참여하는 게임 G를 생각해 보십시오. 한 사람의 이득은 다른 사람의 손실과 같습니다. 선수 A의 보수는 반대 부호를 가진 선수 B의 보수와 같기 때문에 우리는 선수의 보수에만 관심을 가질 수 있습니다. 당연히 A는 최대화를 원하고 B는 최소화를 원합니다.

간단하게 하기 위해 정신적으로 플레이어 중 한 명(A라고 하자)과 자신을 동일시하고 그를 "우리"라고 부르고 플레이어 B는 "상대방"이라고 부르겠습니다(물론 A에게 실질적인 이점은 없음). 가능한 전략과 상대방 - 가능한 전략을 갖도록합시다 (이러한 게임을 게임이라고 함). 우리가 전략을 사용하고 상대방이 전략을 사용하는 경우 우리의 보수를 표시합시다.

표 26.1

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

이러한 테이블이 컴파일되면 게임 G는 매트릭스 형식으로 축소된다고 합니다(그 자체로 게임을 이러한 형식으로 가져오는 것은 이미 어려운 작업이 될 수 있으며, 방대한 수의 전략으로 인해 때로는 실제로 불가능할 수도 있습니다. ). 게임이 매트릭스 형식으로 축소되면 다중 이동 게임은 실제로 한 번의 이동 게임으로 축소됩니다. 플레이어는 전략을 선택하는 단 한 번의 이동만 수행해야 합니다. 게임 매트릭스를 간단히 표시하겠습니다.

매트릭스 형태의 게임 G(4X5)의 예를 고려하십시오. 우리의 처분에 따라(선택할 수 있는) 4가지 전략, 적에게는 5가지 전략이 있습니다. 게임 매트릭스는 표 26.2에 나와 있습니다.

우리(플레이어 A)가 어떤 전략을 사용하는지 생각해 봅시다. Matrix 26.2에는 매력적인 결과가 "10"이 있습니다. 우리는 이 "소식"을 얻을 전략을 선택하게 됩니다.

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

표 26.2

이것이 소위 "미니맥스 원칙"입니다. 상대방의 최악의 행동으로 최대 이득을 얻는 방식으로 행동하십시오.

표 26.2를 다시 작성하고 오른쪽 추가 열에 각 라인(라인의 최소값)에서 이득의 최소값을 기록할 것입니다. 행으로 표시합시다(표 26.3 참조).

표 26.3

모든 값(오른쪽 열) 중에서 가장 큰 값(3)이 선택됩니다. 전략과 일치합니다. 이 전략을 선택하면 어떤 경우에도 (적의 모든 행동에 대해) 3 이상의 이득을 얻을 수 있습니다. 이 값은 보장된 이득입니다. 조심스럽게 행동하면 이보다 적을 수 없고 더 많이 얻을 수 있습니다.)

이 수익을 게임의 더 낮은 가격(또는 "최대값" - 최소 수익의 최대값)이라고 합니다. 로 표시하겠습니다. 우리의 경우

이제 적의 관점에서 그를 변호합시다. 그는 일종의 폰이 아니지만 합리적입니다! 전략을 선택하면 그는 더 적게 주고 싶지만 우리의 행동에 의존해야 하며 이는 그에게 최악입니다. 그가 전략을 선택하면 우리는 그에게 대답하고 그는 10을 줄 것입니다. 그가 선택하면 우리는 그에게 대답하고 그는 그것을 되돌려 줄 것입니다 우리는 표 26.3에 추가로 더 낮은 행을 추가하고 거기에 열의 최대값을 씁니다. 분명히 신중한 적군은 이 값이 다음과 같은 전략을 선택해야 합니다. 최소(해당 값 5는 표 26.3에서 강조 표시됨) . 이 값 P는 합리적인 상대가 확실히 우리에게주지 않을 이득의 가치입니다. 게임의 상한가(또는 "mi-nimax" - 최대 상금의 최소값)라고 합니다. 우리의 예에서는 상대방의 전략으로 달성됩니다.

그래서 주의 원칙(재보험의 원칙은 “항상 최악이 될 것이다!”)을 바탕으로 A전략과 적-전략을 선택해야 하며, 이러한 전략을 “minimax”(minimax 원칙에서 따옴)라고 한다. 이 예에서 양 당사자가 미니맥스 전략을 고수하는 한 그 결과는 다음과 같습니다.

이제 적이 전략을 따르고 있다는 것을 배웠다고 상상해 보십시오. 자, 우리는 이것에 대해 그를 처벌하고 전략을 선택합니다. 우리는 5를 얻었습니다. 이것은 그리 나쁘지 않습니다. 그러나 결국 적도 놓치지 않습니다. 그에게 우리의 전략이 , 그도 서둘러 선택하고 우리의 보수를 2로 줄인다는 것을 알립니다. 요컨대, 우리의 예에서 minimax 전략은 상대방의 행동에 대한 정보와 관련하여 불안정합니다. 이러한 전략에는 균형 속성이 없습니다.

항상 이렇죠? 항상은 아닙니다. 표 26.4에 주어진 행렬의 예를 고려하십시오.

이 예에서 게임의 낮은 가격은 높은 가격과 같습니다: . 이것으로부터 다음은 무엇입니까? 플레이어 A와 B의 최소 최대 전략은 안정적입니다. 두 플레이어가 모두 그것들을 고수하는 한, 결과는 6입니다. 만약 우리가 (A) 상대방(B)이 전략 B를 고수한다는 것을 알게 된다면 어떤 일이 일어나는지 봅시다.

표 26.4

그리고 정확히 아무것도 바뀌지 않을 것입니다. 전략에서 벗어나면 상황이 악화될 수 있기 때문입니다. 마찬가지로, 상대방이 받은 정보는 그가 그의 전략에서 퇴각하도록 만들지 않을 것입니다. 안장 포인트와 균형 잡힌 전략 쌍이 있다는 표시는 게임의 낮은 가격과 높은 가격이 평등하다는 것입니다. 총 가치를 게임 가격이라고 합니다. 우리는 그것을 표시 할 것입니다

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

독자는 질문이 있을 수 있습니다. "순수"라고 하는 최적의 전략이 무엇입니까? 조금 앞을 내다보면 이 질문에 답해 보겠습니다. "혼합" 전략이 있습니다. 이 전략은 플레이어가 하나의 전략이 아니라 여러 전략을 사용하여 무작위로 교대로 사용한다는 사실로 구성됩니다. 따라서 순수 전략과 혼합 전략을 인정한다면 모든 유한 게임에는 솔루션이 있습니다. 즉, 평형점입니다. 그러나 이것에 대한 자세한 내용은 아직 나오지 않았습니다.

게임에서 안장점의 존재는 규칙이 아니라 예외입니다. 대부분의 게임에는 안장점이 없습니다. 그러나 항상 안장점이 있기 때문에 순수한 전략으로 해결되는 다양한 게임이 있습니다. 이들은 소위 "완전한 정보가 포함된 게임"입니다. 완전한 정보가 포함된 게임은 각 플레이어가 각 개인 이동에서 개발의 전체 선사시대를 알고 있는 게임입니다. 완전한 정보가 있는 게임의 예로는 체커, 체스, 틱택토 등이 있습니다.

게임 이론에서는 완전한 정보가 있는 모든 게임에는 안장점이 있으므로 순수 전략으로 해결할 수 있음이 입증되었습니다. 완벽한 정보가 있는 모든 게임에는 게임 가격과 동일한 안정적인 수익을 제공하는 최적의 전략 쌍이 있습니다. 그러한 게임이 개인적인 움직임으로만 구성되어 있다면, 각 플레이어가 자신의 최적의 전략을 적용할 때 게임 가격과 동일한 보상을 받으며 매우 명확한 방식으로 끝나야 합니다. 그래서 게임의 해법을 알면 게임 자체가 의미를 잃는다!

완전한 정보가 있는 게임의 기본 예를 들어 보겠습니다. 두 명의 플레이어가 번갈아 가며 원탁에 니클을 놓고 코인의 중심 위치를 임의로 선택합니다(동전의 상호 겹침은 허용되지 않음). 승자는 마지막 페니를 넣는 사람입니다(다른 사람을 위한 공간이 없을 때). 이 게임의 결과는 본질적으로 예견된 결론이라는 것을 쉽게 알 수 있습니다. 동전을 먼저 넣는 사람이 이기는 전략이 있습니다.

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

이제 게임에 안장점이 없는 경우 어떻게 해야 하는지 자문해 보겠습니다. 각 플레이어가 단일 순수 전략을 선택해야 하는 경우에는 할 일이 없습니다. 우리는 미니맥스 원칙에 따라야 합니다. 또 다른 것은 전략을 "혼합"할 수 있다면 무작위로 몇 가지 확률로 대체하는 것입니다. 혼합 전략의 사용은 다음과 같이 생각됩니다. 게임은 여러 번 반복됩니다. 게임의 각 게임 전에 플레이어에게 개인적인 이동이 주어졌을 때 그는 자신의 선택을 우연에 "맡기고" "제비를 던지고" 실패한 전략을 취합니다(이전 장에서 제비를 구성하는 방법을 이미 알고 있습니다. ).

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

혼합 전략에 대해 이야기해 보겠습니다. 플레이어 A와 B의 혼합 전략을 각각 표시합니다.

특정한 경우에 1을 제외한 모든 확률이 0이고 이 확률이 1이면 혼합 전략이 순수 전략으로 바뀝니다.

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

게임 솔루션을 구성하는 한 쌍의 최적 전략에는 다음과 같은 속성이 있습니다. 한 플레이어가 자신의 최적 전략을 고수하면 다른 플레이어가 그의 최적 전략에서 벗어나는 것이 이익이 될 수 없습니다. 이 한 쌍의 전략은 게임에서 일종의 균형을 형성합니다. 한 플레이어는 보수를 최대로 돌리고, 다른 플레이어는 최소로 각자 자신의 방향으로 당기고, 둘 다의 합리적인 행동으로 균형과 안정적인 보수 v가 설정됩니다. 게임이 우리에게 유익하다면 - 적에게; 게임이 "공정"할 때 두 참가자 모두에게 똑같이 유익합니다.

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

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

게임의 낮은 가격은 전략과 일치합니다. 이것은 합리적이고 신중한 행동으로 우리가 3 이상 잃지 않을 것을 보장한다는 것을 의미합니다. 매트릭스의 세포. 그것은 우리에게 나쁘다, 플레이어 L... 그러나 우리 스스로를 위로하자. 합리적인 행동, 그는 우리에게 최소 4를 줄 것입니다.