games_theory (Лекции ЮКР)

ЗАНЯТИЕ №1.

Основные понятия теории игр.

Учебные вопросы:

1. Нижняя и верхняя цена игры. Принцип минимакса.

2. Прямоугольные игры с седловой точкой.

3. Прямоугольные игры без седловых точек.

4. Основная теорема теории игр. Свойство оптимальных стратегий.

ЗАНЯТИЕ №2.

Методы решения игровых задач.

Учебные вопросы:

1. Сведение решения игры к задаче ЛП

2. Элементарные методы решения игр 2x2 и 2xn.

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

Учебный вопрос №1. НИЖНЯЯ И ВЕРХНЯЯ ЦЕНА ИГРЫ. ПРИНЦИПЫ МИНИМАКСА.

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

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

Стратегии игроков—способы проведения игры каждым из участников.

Ход игрока—факт выбора игроком одной из возможных стратегий. Саму выбранную стратегию называют выбором.

Игры различаются:

1. По числу участников: игры 2-х и более лиц.

Когда мы говорим “игра n лиц”, то это означает, что, согласно правилам игры, игроки разделены на n непересекающихся множеств, причем в одно множество объединяются участники с общими интересами;

1. По организации платежей: игры с нулевой и ненулевой суммой

Рассмотрим игру n лиц. Пусть a(i=1,...,n)—платеж i-го игрока в конце партии. Если a>0, то a–выигрыш, а если a<0, то проигрыш i-го игрока. При партия игры называется партией с нулевой суммой. Если все партии игры с нулевой суммой, то сама игра называется игрой с нулевой суммой. В парной игре с нулевой суммой выигрыш одного игрока равен проигрышу другого.

Теория игр с ненулевой суммой применяется для изучения экономических процессов, приводящих к созданию или уничтожению общественного богатства;

1. По количеству ходов и числу стратегий: конечные и бесконечные игры.

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

1. По информации, которой располагают участники игры: с полной и неполной информацией.

Если перед каждым ходом игрок знает все предшествующие выборы и платежи, то игра с полной информацией. В противном случае—игра с неполной информацией.

Принцип минимакса.

Рассмотрим конечную игру двух лиц X и Y размерности mxn с нулевой суммой, т. е. Х имеет m стратегий , а Y n стратегий

. Партия состоит в том, что Х и Y выбирают по одной из своих стратегий и , в результате чего платеж Х составляет величину , а платеж Y-- (игра с нулевой суммой).

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

Таблицу, задаваемую функцией целочисленных аргументов i=1,...,m и j=1,...,n , сопоставляющей паре стратегий и платеж , называют платежной матрицей игры, а игру, заданную платежной матрицей, называют игрой, приведенной к нормальной форме.

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

Решение игр основывается на принципе минимакса, который состоит в следующем: какую бы стратегию ни выбрал игрок Х, игрок Y ответит такой стратегией , чтобы заплатить . Следовательно, игроку Х из всех своих стратегий нужно взять такую , которая обеспечивает . называется нижней ценой игры, а стратегия --минимаксной стратегией игрока Х. является гарантированным выигрышем игрока Х при любой стратегии игрока Y. С другой стороны, на всякую стратегию игрока Y сторона Х ответит стратегией , обеспечивающей . Следовательно, из всех надо выбрать такую , которая доставит . Величина называется верхней ценой игры , а --минимаксной стратегией игрока Y. Верхняя цена игры—это тот гарантированный уровень, больше которого Y не заплатит, если только он будет применять свою минимаксную стратегию , какие бы стратегии ни применяла сторона Х.

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

В общем случае . Если же оказывается, что , то минимаксные стратегии и принимают за решение игры, а элемент (*) называют ценой игры. При этом является седловой точкой функции , i=1,..,m; j=1,..,n;

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

Опр. Стратегии и , где точка является седловой для называются оптимальными чистыми стратегиями игроков Х и Y, а --ценой игры.

Будем предполагать, что существуют величины

и

Покажем, что всегда .

По опр. max f:

, правая часть от не зависит;

По опр. min f:

;

Отсюда

Правая часть неравенства не зависит от , а оно выполнено ,поэтому

Аналогично рассуждая для y-ков, получим:

, т.е. .

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

Необходимое условие:

Если --седловая точка , то

По определению седловой точки:

,поэтому

По определению min

С другой стороны, , откуда

,

или

Таким образом,

Учитывая полученное ранее соотношение , получаем

Достаточное условие:

Если существуют величины и

и , то функция имеет седловую точку.

Из существования следует, что существует такое , что ; Из существования :

Т. к. , то

По определению min функции: По определению max Ч. Т. Д.

Заметим, что из всех точек , удовлетворяющих соотношению седловыми будут лишь те, которые удовлетворяют также соотношениям и

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

Учебный вопрос №3. ПРЯМОУГОЛЬНЫЕ ИГРЫ БЕЗ СЕДЛОВЫХ ТОЧЕК.

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

Если же и не имеет седловой точки, то решение игры ищется в смешанных стратегиях.

Опр. В матричной игре смешанной стратегией игрока Х называется совокупность неотрицательных чисел таких, что , причем есть частота (вероятность), с которой игрок Х выбирает стратегию . Для игрока Y соответственно

Обозначим и , соответственно, множества всех смешанных стратегий игроков Х и Y.

Игра с применением чистой стратегии для игрока Х есть игра со смешанной стратегией , где , а остальные .

Мат. ожидание выигрыша игрока Х при применении игроками смешанных стратегий есть:

В соответствии с принципом минимакса игрок Х выберет такую стратегию , чтобы достичь , а игрок Y--такую , чтобы достичь

В качестве решения игры принимают седловую точку функции , т. к. в этом случае

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

Про говорят, что это стратегическая седловая точка. и называются оптимальными смешанными стратегиями игроков Х и Y, а величина называется ценой игры.

Учебный вопрос №4. ОСНОВНАЯ ТЕОРЕМА ТЕОРИИ ИГР. СВОЙСТВО ОПТИМАЛЬНЫХ СТРАТЕГИЙ.

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

и

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

Свойства оптимальных стратегий.

Введем обозначения:

-- средний выигрыш игрока Х, когда он использует чистую стратегию , а игрок Y—смешанную стратегию .

Аналогично, для чистой стратегии : , тогда

1. Если -- оптимальные смешанные стратегии игроков Х и Y, а --цена игры, то ,

Это свойство следует прямо из определения седловой точки функции , для частного случая .

Обратное утверждение также справедливо:

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

Действительно,

т. е. . Положим , тогда и

Таким образом, точка является седловой точкой функции , а --есть значение этой функции в седловой точке.

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