games_theory (Лекции ЮКР), страница 2

СОДЕРЖАНИЕ ЗАНЯТИЯ №2.

Учебный вопрос №1. СВЕДЕНИЕ РЕШЕНИЯ ИГРЫ К ЗАДАЧЕ ЛИНЕЙНОГО ПОРГРАММИРОВАНИЯ.

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

Сведем теперь решение игры к задаче ЛП.

Имеем:

(**)

По сути дела, нахождение решения игры сводится к решению линейных неравенств:

относительно неизвестных и . Причем величины и должны удовлетворять также условиям:

Заметим, что, если к каждому элементу платежной матрицы прибавить константу C, то получим:

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

Истинная цена игры найдется через как

Введем новые переменные:

Неравенства (**) запишутся в виде:

Считаем, что лежит в окрестности , так что .

Т. к. --непрерывна и

Так как , то переходя к пределу при , получим:

Если --оптимальные решения сопряженных задач ЛП,то

, т. е. , а оптимальные с мешаные стратегии игроков выразятся как .

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

По свойству оптимальных стратегий , следовательно, . Пусть , но тогда и подавно . Откуда ,

что противоречит тому, что --цена игры.

Аналогично доказывается и второе равенство.

Если для какого-либо выполняется , то в

оптимальной смешанной стратегии , т. е. стратегия не

участвует в оптимальном решении игрока X.

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

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

Учебный вопрос №2. ЭЛЕМЕНТАРНЫЕ МЕТОДЫ РЕШЕНИЯ ИГР 2х2 и 2хN.

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

0 1

Оптимальной стратегии Х соответствует

Для определения запишем следующее уравнение:

или

, откуда

Для игрока Y

0

Оптимальной стратегии Y соответствует

Пусть .

0

Геометрически видно, что

Для игрока Y решение свелось к игре (2х2), т. е. его оптимальная смешанная стратегия есть .

Соотношение превосходства.

Если в игре , заданной платежной матрицей выполняется условие (*), где , то говорят, что s-я строка подчинена выпуклой линейной комбинации строк с номерами , или, что выпуклая линейная комбинация стратегий доминирует над стратегией . В этом случае можно отбросить s-ю строку в матрице и перейти к игре размерности .

Если неравенства (*) выполняются как строгие, то говорят о строгом доминировании (превосходстве). При этом решения игры представляют все решения игры . При нестрогом превосходстве часть решений игры может быть потеряна.

По свойству оптимальных смешанных стратегий для игры имеем:

Запишем

Итак, первая группа неравенств выполняется и для .

можно представить в виде:

Т. е. при получили

Следовательно, стратегии и являются оптимальными смешанными стратегиями игроков Х и Y в игре , а --цена игры , но не обязательно должно быть равно 0 и поэтому возможны другие оптимальные стратегии . Если же хотя бы одно неравенство (*) выполнено как строгое, то --по 4-му свойству оптимальных стратегий.

Для игрока Y выпуклая линейная комбинация стратегий подчинена стратегии , т. е. заведомо выгодна для игрока Y.

Лекции составил:

подполковник В. Ярошенко.