Теория игр

Проиллюстрируем решение матричной игры на конкретном примере, с заданной платежной матрицей .

Составим следующую таблицу .

	j	1	2	3	4	i
i
1		2	1	5	4	1
2		1	3	–1	4	–1
j		2	3	5	4		 =
						 =

Имеем , , , , , , , .

Так как , поэтому седловой точки у данной матрицы нет, и следовательно, игра не имеет оптимального решения в чистых стратегиях.

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

Графический способ решения матричной игры

Графически решаются задачи в случае, когда у одного из игроков всего лишь две чистые стратегии. В рассматриваемом примере у игрока I две стратегии, а у игрока II – четыре стратегии.

Графически решается задача игрока, имеющего две стратегии, т.е. в нашем случае задача игрока I. Оптимальная стратегия игрока II находится аналитическим путем после решения задачи игрока I.

На рисунке четыре отрезка, соответствующие четырем чистым стратегиям игрока II.

Находим теперь нижнюю границу выигрышей игрока I в виде ломаной линии, огибающей снизу все эти отрезки. Эта граница показана на рисунке жирной линией.

Решение задачи игрока I сводится к отысканию на нижней границе его выигрышей точки, соответствующей наибольшему выигрышу, т.е. наиболее удаленной точки отрезка.

На рисунке это будет точка М, находящаяся на пересечении первого и второго отрезков. Первая и вторая чистые стратегии игрока II называются активными, и он их должен использовать в своей оптимальной стратегии q^* с ненулевой вероятностью. Третий и четвертый отрезки не проходят через точку М, поэтому третья и четвертая стратегии, наоборот, называются пассивными – игрок II не должен их использовать в оптимальной стратегии.

Далее определяются графически цена игры v как расстояние от точки М до единичного отрезка (взятое с учетом знака) и оптимальная смешанная стратегия . Так как графическое определение числовых значений этих величин является довольно грубым, то следует уточнить их аналитическим путем решения системы линейных уравнений.

1

Решив полученную систему, находим

Найдем теперь оптимальную стратегию игрока II. Как уже отмечалось, третья и четвертая стратегии его являются пассивными, поэтому Остальные компоненты вектора q^* находятся аналитическим путем решения системы уравнений

+

Так как значение v уже известно, то для определения неизвестных достаточно взять какие-либо два уравнения этой системы. Возьмем, например, первое и третье уравнения:

+

откуда находим

В итоге получены следующее оптимальное решение игры и ее цена:

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

При составлении системы уравнений для игрока I столбцы этой матрицы умножаются скалярно на столбец неизвестных , а при составлении системы для игрока II строчки этой матрицы скалярно умножаются на строку неизвестных (q₁, q₂).