теория игр



ЛЕКЦИЯ

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

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

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

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

Требуется:

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

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

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

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

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

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

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

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

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

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

,

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

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

,

Откуда

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

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

, .

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

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

Требуется:

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

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

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

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

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

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

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

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



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

,

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

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

,

откуда , .

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

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

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

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

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

(*)

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

,

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

.

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

.

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

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

,

(**)

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

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

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

,

.

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

, .

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

Пример. ,

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

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

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

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

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

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








sitemap
sitemap