Методы решения матричных игр

Сравнительно просто решаются игры, в которых хотя бы один игрок имеет всего две чистых стратегии: игры 22, 2n, mn. Когда m, n>2 теория игр не имеет собственного точного метода. Такие игры сводятся к задачам линейного программирования и решаются методом симплекс-таблиц. Нужно заметить, что применение симплекс метода приводит к громоздким вычислениям уже для игры 3x3. Для игр больших размеров применяются приближенные методы.

Решение 22-игры

В общем случае игра 22 определяется матрицей

.

Прежде всего, необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков A и B соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет решения в чистых стратегиях, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями.

Пусть U = (, 1  ) – оптимальная стратегия игрока A. Тогда

; .

Аналогично, если W = (, 1 – ) – оптимальная стратегия игрока B, то

.

Решение m n – игры

В некоторых случаях игры больших размеров можно упростить и привести к малым размерам. В основе такого преобразования лежит понятие доминирования стратегий.

Пусть дана mn- игра А. Говорят, что i-я стратегия игрокаAдоминирует его k-ю стратегия, еслидля всехj= 1,2,…,n. Говорят, что j-я стратегия игрокаBдоминирует его l-и стратегию, еслидля всехi= 1,2,…,m. .         Из определения видно, что доминирующая стратегия дает игроку выигрыш не хуже, чем доминируемая. Отсюда следует, что игрок всегда может обойтись без доминируемых стратегий, в частности, если есть одинаковые стратегии, то он может применять только одну из них. Поэтому в матрице А доминируемые стратегии (строки или столбцы) могут быть отброшены, а это приводит к матрице малых размеров. В результате выполнения доминирования получается игра, эквивалентная первоначальной, в смысле следующего утверждения.

Теорема 2. Пусть (x,y) - седловая точкаmn- игры А, а () - седловая точка- игры A' (), полученной из А в результате исключения доминируемых стратегий. Тогда,для всех недоминируемых i, j:=0,для всех доминируемых i:

Пример 1. Рассмотрим игру

Стрелками показаны доминируемые стратегии. Получили 2х2-игру, в которой все стратегии недоминируемы. Игра эквивалентна первоначальной игре А, т.е. оптимальные стратегии в игре А имеют видx=(0,),

        В результате вместо игры А мы можем решить более простую 2х2-игру .

Теперь мы можем указать общий порядок решения матричной игры:

1. проверить, существует ли решение в чистых стратегиях; если есть, то игра решена;

2. если нет решения в чистых стратегиях, то выполнить доминирование;

3. найти решение в смешанных стратегиях.

Решение игр 2

Для построения решений 2- игр существует эффективный метод, основанный на простых геометрических соображениях. Этот метод называют графическим.

Рассмотрим игру 2n:.

Задача игрока Aсостоит в максимизации функции.Так как, мы имеем.

Таким образом, vявляется минимумомnлинейных функций одной переменной; можно вычертить графики этих функций и затем максимизировать их минимум g() графическими методами. Покажем на примере игры 23.

Поясним на примере 1.

На плоскости хОу введём систему координат и на оси Ох отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (х, 1-х). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) - стратегии А2 и т. д.

На перпендикуляре А1 будем откладывать выигрыш игрока 1 при стратегии 1, на втором - при стратегии А2.

Таким образом, ординаты точек, принадлежащих ломаной оMNс определяют минимальный выигрыш игрока 1 при применении им любой смешанной стратегии. Эта минимальная величина является максимальной в точке N; следовательно, этой точке соответствует оптимальная стратегия Х* = (х, 1-х), а её ордината равна цене игры. Координаты точки N находим как пересечение прямых.

Соответствующие два уравнения имеют вид

следовательно, х = (3/11,9/11), при цене игры v = 49/11. таким образом мы можем найти оптимальную стратегию при помощи матрицы

Оптимальные стратегии для игрока 2 можно найти из системы

Укажем основные этапы нахождения решения игры 2n (m2):

1)  Строим прямые, соответствующие стратегиям второго (первого) игрока.

2)  Определяем нижнюю (верхнюю) огибающую графиков, соответствующих столбцам (строкам).

3)  Находим две стратегии второго (первого) игрока, которым соответствует две прямые, пересекающиеся в точке с максимальной (минимальной) ординатой.

4)  Определяем цену игры и оптимальные стратегии игроков.