Решение матричных игр вида 2хn и mх2

Простейшая матричная игра 2×2 определяется матрицей.

Если в игре есть седловая точка, то игра имеет решение в чистых стратегиях, иначе она решается в смешанных стратегиях (х°, у^п), где.

причем.

По определению, оптимальные смешанные стратегии для случая 2×2 могут быть определены из условия.

Если первый игрок придерживается своей оптимальной стратегии х°, он не получит меньше и при любых стратегиях у второго игрока:

Это справедливо в том числе если второй игрок выбирает свои чистые стратегии у = (1, 0) и у = (0, 1). Для этих двух случаев мы имеем.

Выполнение данной системы неравенств возможно в случае.

Решая данную систему уравнений, находим.

Аналогичные рассуждения приводят к выводу о том, что оптимальная стратегия второго игрока у⁰ = (г/,°, г/®) удовлетворяет системе уравнений.

откуда Таким образом, решение простейшей матричной игры (х°, у°, и) найдено аналитически, и оно является единственным.

Однако в образовательной практике и практике принятия реальных решений для решения игр такого вида быстрее и удобнее не запоминать полученные итоговые формулы для х°, у°, о, а решить соответствующие системы уравнений с коэффициентами, определяемыми платежной матрицей конкретной игры.

Далее рассмотрим графоаналитический метод, который применим к матричным играм, в которых один из игроков имеет только две чистые стратегии, а другой — любое конечное число чистых стратегий^[1].

Рассмотрим игру вида 2 х п с платежной матрицей.

Первый игрок имеет две чистые стратегии х, и х₂. Второй игрок имеет п чистых стратегий г/, у." …, у_п. Будем считать, что игра не имеет седловой точки. Платежи первого игрока при его смешанных стратегиях (х, 1 — х,) и чистых стратегиях второго игрока представлены в табл. 4.1.

Таблица 4.1

Платежи первого игрока при чистых стратегиях второго игрока (общий случай).

Таким образом, платежи первого игрока линейно зависят от его стратегии при любых чистых стратегиях второго игрока и могут быть отражены на графике прямыми. Идея метода решения игр такого вида заключается в том, чтобы графически построить прямые платежей первого игрока и визуально определить прямые, точка пересечения которых соответствует точке максимина, в которой обеспечивается максимум минимальных платежей первого игрока. Проиллюстрируем этот подход на примерах.

Пример 4.5. Рассмотрим игру 2×4:

Эта игра не имеет седловой точки. Платежи первого игрока при его смешанных стратегия (х, 1 — х,) и чистых стратегиях второго игрока представлены в таблице:

Платежи первого игрока при четырех возможных чистых стратегиях второго игрока представлены на рис. 4.2 (для определения координат опорных точек используются значения х, = 0 и х, = 1).

Спектр минимальных возможных платежей первого игрока определяется нижней огибающей, формируемой прямыми 3 и 4. Максимин достигается при х, = 0,5, что может быть определено аналитически, например ив условия х, + 2 = = -7Х[ + 6 (этот же результат может быть получен решением системы уравнений любых двух прямых, пересекающихся в точке максимина, — 2, 3, 4). Следовательно, оптимальной стратегией первого игрока является стратегия (0,5; 0,5). Цена игры определяется подстановкой х, = 0,5 в уравнение любой из прямых, проходящих через точку максимина, например прямой 2: -0,5 + 3 = 2,5.

Оптимальная смешанная стратегия второго игрока определяется уравнениями любых двух прямых, проходящих через точку максимина и имеющих противоположные наклоны. В данном случае это прямые 2,3 и 3,4. Возьмем, к примеру, прямые 2 и 3. Платежи второго игрока равны с обратным знаком платежам первого игрока, поэтому для простоты условно будем называть их проигрышами второго игрока. Платежи первого игрока (т.е. проигрыши второго игрока) при чистых стратегиях первого игрока и смешанной стратегии второго игрока представлены в таблице:

Оптимальная смешанная стратегия второго игрока определяется из условий -у₂ + 3 = у₂ + 2 и у₃ = 1 — у₂, что дает (0; 0,5; 0,5; 0). Подстановка у₂ в любое из уравнений дает цену игры 2,5, как и должно было получиться. В случае если для отыскания оптимальной смешанной стратегии мы используем прямые 3 и 4, то получим в качестве оптимальной стратегию (0,0,7/8,1/8), которая гак же, естественно, обеспечивает цену игры 2,5. Любое средневзвешенное решение, полученное путем комбинирования оптимальных стратегий (0; 0,5; 0,5; 0) и (0, 0, 7/8, 1/8), также будет являться оптимальным и обеспечивать ту же цену игры. Для нашего случая оптиматьной стратегией второго игрока будет стратегия (0,¼, 11/16,1/16). Первая чистая стратегия второго игрока нс входит в его оптимальные смешанные стратегии, так как является доминируемой, что также иллюстрируется рис. 4.2. Таким образом, решение игры найдено, причем у второго игрока три оптимальные стратегии.

Пример 4.6. Рассмотрим решение игры вида т х 2:

Рис. 4.2. Пример графического решения игры 2 х п.

(подготовлено в MS Excel)

Игра не решается в чистых стратегиях. Следуя логике решения предыдущей игры, определим проигрыши второго игрока при чистых стратегиях первого игрока и представим их в таблице:

Прямые, определяющие проигрыши второго игрока, представлены на рис. 4.3.

Рис. 4.3. Пример графического решения игры т X 2.

Второй игрок стремится минимизировать свой проигрыш, поэтому он руководствуется принципом минимакса. Спектр максимальных проигрышей второго игрока определяется верхней огибающей, формируемой прямыми 4, 1 и 3. Минимакс достигается в точке пересечения прямых 1 и 3 при г/, = 2/3, что может быть определено решением системы уравнений соответствующих прямых (1 и 3). Цена игры о = 8/3 определяется подстановкой у, в уравнение любой из прямых, проходящих через точку минимакса.

Прямые, пересекающиеся в точке минимакса, соответствуют стратегиям 1 и 3 первого игрока:

Следовательно, оптимальной стратегией первого игрока, определяемой из условиях, + 3 = 2х, + 2, является стратегия (1/3, 0, 2/3, 0), что обеспечивает цену игры х = 8/3. Решение игры найдено.

Для простейших игр 2×2 данный метод также может применяться, но при этом нет необходимости строить графики: достаточно сформулировать и решить две системы двух линейных уравнений.

• [1] Описание метода приводится по материалам книги [19].