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

Размещено на http://www.allbest.ru/

ЛЕКЦИЯ

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

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

Когда у одного из игроков имеется всего 2 стратегии, можно найти оптимальные смешанные стратегии графически.

Задача 1. Рассматривается антагонистическая игра двух лиц с нулевой суммой и платежной матрицей (первый игрок получатель платежа, выбирает строку платежной матрицы, второй плательщик, выбирает столбец).

Требуется:

1) определить верхнюю и нижнюю цену игры в чистых стратегиях;

2) найти цену игры и оптимальные смешанные стратегии игроков.

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

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

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

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

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

Нам надо построить графики четырех функций, равных величине математического ожидания платы при использовании второго игрока своей первой, второй, третьей и четвертой стратегий, соответственно. Имеем:

оптимальная стратегия игрок платёжная матрица

Остается для каждого определить

,

а затем найти .

Из рисунка видно, что точка максимина соответствует пересечению графиков второй и третьей функции, то есть

,

Откуда

Для определения смешанной стратегии второго игрока следует решить уравнение

(поскольку в вершине, отвечающей нижней цене игры, пересекаются прямые, отвечающие второй и третьей стратегиям второго игрока), откуда

, .

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

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

Требуется:

1) определить верхнюю и нижнюю цену игры в чистых стратегиях;

2) найти цену игры и оптимальные смешанные стратегии игроков.

Решение. Найдем верхнюю цену игры в чистых стратегиях

Найдем нижнюю цену игры в чистых стратегиях.

Поскольку , цены игры и решения в чистых стратегиях нет.

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

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

Нам надо построить графики четырех функций, равных величине математического ожидания платы при использовании первым игроком своей первой, второй, третьей и четвертой стратегий, соответственно. Имеем:

Остается для каждого определить

,

а затем найти .

Из рисунка видно, что точка минимакса соответствует пересечению графиков первой, второй и третьей функции, то есть

,

откуда , .

Для определения смешанной стратегии первого игрока следует решить вырожденную систему уравнений

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

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

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

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

(*)

Действительно, если _ максиминная стратегия первого игрока, а второй игрок привилегирован, то для какой _ либо чистой стратегии второго игрока (или, быть может, для нескольких из них) имеет место равенство

,

в то время как для всех остальных стратегий имеет место строгое неравенство

.

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

.

Следовательно, если для какого-либо числа неравенства (*) выполняются, то это число удовлетворяет оценке

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

,

(**)

Если есть решение задачи (**), то цена игры равна , а оптимальная стратегия игрока определяется из соотношений .

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

хотя бы для одного допустимого набора . Обозначая , получаем следующую задачу линейного программирования

,

.

Если решение задачи, то

, .

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

Пример. ,

Приведем задачу к стандартной форме:

Запишем условия задачи в виде симплекс таблицы.

Найдено следующее решение задачи линейного программирования:

Переходя к вероятностям, получим

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

Размещено на Allbest.ru