Теория игр 1819

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

? ! ??!! ???!!! ????!!! !........
Измерить то, что легко измеряемо. Само по себе, это нормально.
Отбросить то, что нельзя легко измерить или придать этому некое количественное значение. Это искусственно и вводит в заблуждение.
Представить то, что нельзя измерить, как несущественное. Это - слепота.
Заявить, что то, чего нельзя легко измерить, на самом деле не существует. Это - самоубийство.»

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

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

Черты конфликтной ситуации:
наличие заинтересованных сторон
наличие своих интересов (целей) у каждой стороны *
наличие набора возможных действий у каждой из сторон
часто недостаток информации (неопределенность)
ПРИМЕРЫ
Покупатель и продавец
Работник и работодатель
Спортивные состязания
Вооруженные конфликты …….
………………………………

Игроки – заинтересованные стороны в игре (участники игры).
Парная игра – игра, в которой принимают участие два игрока.
Множественная игра – игра с числом участников более двух.
Коалиция - объединение игроков
Коалиции действия
Коалиции интересов

Стратегия – любое возможное действие (комплекс действий) игрока
Ход - выбор действия игроками (личный ход *)
Ситуация (исход игры) – состояние, в котором оказываются игроки после очередного хода

Будем предполагать, что каждый из участников парной игры обладает своим набором чистых стратегий: SA={A1,A2,…,Am}, SB={B1,B2,…,Bn}
В условиях конфликта каждый игрок делает свой ход, т.е. выбирает одну из своих возможных стратегий.
Сделав ход, игроки оказываются в ситуации Хij={Ai, Bj}.
Правила игры могут запрещать отдельные ситуации, которые называются «запрещенными».
Если в процессе игры возникает запрещенная ситуация, то игра считается несостоявшейся.

Функция выигрыша – степень удовлетворения интересов игрока (FA).
Функция выигрыша определена на множестве ситуаций (SA, SB) и ставит в соответствие каждой ситуации Xij некоторое число F(Xij), называемое выигрышем игрока А в данной ситуации.
Реализация игры – выбор игроками своих возможных стратегий и получение в сложившейся ситуации своего выигрыша.

Предполагается, что игра происходит по определенным правилам (без этого не возможна формализация задачи).
Правила - система условий, которые описывают:
возможные действия каждого из игроков;
объем информации, которую может получить каждая из сторон о возможных действиях противника;
исход (результат) игры после каждой совокупности «ходов» противника

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

Замечания:
Выбор оптимальной стратегии базируется на принципе разумности каждого игрока, т.е. поведение каждого из них направлено на достижение своих целей.
Оптимальность опирается на некоторый критерий. Поэтому возможны случаи, когда стратегия является оптимальной в смысле одного критерия и не оптимальной в смысле другого.

Парная игра с нулевой суммой выигрыша
Определение. Игры, в которых каждый из игроков преследует противоположные интересы называются антагонистическими.
В антагонистической игре один из игроков выигрывает ровно столько, сколько проигрывает другой.
Следовательно: FA(AiBj) = - FB(BjAi) или
FA(AiBj) + FB(BjAi) = 0
Антагонистическая парная игра определяется совокупностью {SA, SB, FA}

Пусть игроки А и В имеют наборы стратегий SA={A 1 A2,…,Am} и SB={B1,B2,…,Bn}.
Cитуация Хij=(Ai, Bj) полностью определяет выигрыш игрока А, который равен значению функции выигрыша FА(AiBj)= aij.
Это число в антагонистической парной игре одновременно проигрыш игрока В.
Матрица А={aij}, в которой номер строки - номер стратегии игрока А, а номер столбца – номер стратегии игрока В, называется матрицей выигрыша игрока А.

Платежная матрица
А =
Аналогичным образом можно построить матрицу выигрышей игрока В.
При этом В= - АТ.
Таким образом матрица В
полностью определяется матрицей А.
Матрица А называется также платежной матрицей или матрицей игры.

Замечания.
Матрица игры существенно зависит от упорядочивания множеств SA и SB. При иной нумерации стратегий матрица окажется другой. Т.е. одна и та же игра может быть представлена различными матрицами. Но функция FA остается однозначно определенной.
Построение матрицы игры является весьма сложной задачей. Однако, всякую конечную игру можно привести к матричной форме.

Пример построения платежной матрицы
Задача. Две фирмы А и В производят один и тот же сезонный товар, который поступает на рынок в моменты времени i и j. Цель фирмы В разорить фирму А и стать монополистом на рынке, пойдя на некоторые убытки.
Товар обладает следующим свойством. Чем дольше он находится в производстве, тем выше его качество.
Способ борьбы один: поставлять товар более высокого качества.
Для разорения фирмы А необходимо минимизировать ее доходы.
Необходимо. Построить матрицу игры А для n = 4 при условии, что доход равен величине С (в единицу времени).

Решение
Стороны А и В имеют противоположные интересы.
Фирма обладает набором стратегий SA={A1,A2,A3,A4} поставки товара в момент времени i, а фирма В набором SB={B1,B2,B3,В4} поставки товара в момент времени j.
Возможны три варианта сравнения моментов поставки товара: i
j.
С – некоторая постоянная величина, n – число моментов поставки.

В результате для n = 4 получим матрицу:

Максиминные и минимаксные стратегии
Пусть имеем парную антагонистическую игру между игроками А и В:
SA={A1,A2,… ,Am},
SB={B1,B2,…,Bn},
FA(i,j)= aij.
Анализ платежной матрицы: игрок А.
Если игрок А выбирает одну из своих стратегий (Аi), то его выигрыш – одно из значений aij, лежащее в строке i.
А исходит из того, что игрок В в ответ выберет наилучшую из своих стратегий, при которой выигрыш игрока А будет минимальным.

А выберет ту стратегию, при которой показатель эффективности αi принимает максимальное значение: α =max(αi ) = max min(aij) при 1≤ j ≤n и 1≤ i ≤m.
Данный принцип выбора стратегии называется максиминным.
α – максимин стратегий игрока А.
SAmaxmin – множество максиминных стратегий игрока А.
Если игрок А выбирает одну из максиминных стратегий Аimaxmin, то его выигрыш будет aimaxmink ≥ α при любой стратегии игрока В.
Пусть αi = min(aij) при 1≤ j ≤n для всех 1≤ i ≤m
αi – показатель эффективности стратегии Аi.

Анализ платежной матрицы : игрок В
В антагонистической игре результат игры для игрока В удобно анализировать как «проигрыш».
Для стратегий Вj «выигрыши» расположены в столбцах матрицы FA: aji.
Максимальный выигрыш игрока А есть:
βj = max(aji) при 1≤ i ≤m
Интерес игрока В : выбрать такую стратегию, при которой игрок А будет иметь минимальный выигрыш:
β = min(βj ) = minmax(aji)
Это минимаксный принцип.
β – минимакс стратегий игрока В.
SBminimax – множество минимаксных стратегий игрока В.
α – нижняя граница игры
β – верхняя граница игры α ≤ β

Замечание: α и β могут быть любыми действительными числами. Если α <0 термин проигрыш не употребляется.
Пример. Найти верхнюю и нижнюю границы игры и максиминную и минимаксную стратегии игроков А и В.
Т.к.α2=α3, то стратегии
А2 и А3 – максиминные стратегии игрока А.
У игрока В стратегия В2 минимаксная.

Уменьшение размерности игры

Приведение матричной игры к задаче линейного программирования

Игры с природой

5.1.Критерий Бейса относительно выигрышей
Показателем эффективности чистой стратегии игрока по критерию Бейса называется среднее значение выигрыша для данной стратегии
Оптимальной по критерию Бейса относительно выигрышей является чистая стратегия с максимальным показателем эффективности

5.2. Критерий Бейса относительно рисков
Показателем неэффективности стратегии А относительно рисков называется среднее взвешенное значение рисков по этой стратегии
Оптимальной по критерию Бейса относительно рисков является стратегия с минимальным значением неэффективности

Решение задачи

Решение задачи

Критерии Бейса