Теория принятия решений |
Конспект лекций |
Матричные игры в формате Microsoft Power Point
Лекция №7. Модели теории игр. Матричные игры
Теория игр – это математическая теория конфликтных ситуаций. Ее цель – разработка рекомендаций для оптимального поведения участников конфликта. Математическая модель конфликта называется игрой. Правилами игры называют совокупность условий, регламентирующих:
1) возможные варианты действий сторон;
2) объем информации каждой стороны о поведении другой;
3) результат данной совокупности действий.
Ходом игрока называют действие, осуществленное этим игроком и предусмотренное правилами игры.
Стратегией игрока называют совокупность правил, определяющих выбор варианта действий. Оптимальной стратегией игрока называют такую последовательность его действий, которая обеспечивает максимальный выигрыш.
Если в игре участвуют две стороны, она называется парной, если более двух – множественной.
В зависимости от числа стратегий игры делятся на конечные и бесконечные.
Игрой с нулевой суммой называют такую игру, в которой сумма выигрышей всех участников равна нулю (то есть игрок выигрывает только за счет других).
Игра называется матричной, если информация о стратегиях участников конфликта дана в виде матрицы.
Итак, нами рассматривается матричная игра (конечная игра двух игроков с нулевой суммой), в которой задается выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям). Первый игрок имеет m стратегий i = 1,2,…,m, второй – n стратегий j = 1,2,…,n. Каждой паре стратегий (i, j) поставлено в соответствие число aij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию , 2 – свою j-ю стратегию
, после чего игрок 1 получает выигрыш aij за счет игрока 2 (если aij<0, то это значит, что первый игрок платит второму сумму |aij|). На этом игра заканчивается.
Каждая стратегия игрока ;
часто называется чистой стратегией.
Если рассмотреть матрицу
то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 – j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша aij.
Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2
.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию. Затем из этих минимальных выигрышей отыскивается такая стратегия i=io, при которой этот минимальный выигрыш будет максимальным, т.е. находится
Число называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.
Игрок 2 при оптимальном поведении должен стремиться за счёт своих стратегий максимально уменьшить выигрыш 1 игрока. Поэтому для игрока 2 отыскивается
т.е. определяется максимальный выигрыш игрока 1 при условии, что игрок 2 применит свою j-ю чистую стратегию; затем игрок 2 отыскивает такую свою j=j1 стратегию, при которой игрок 1 получит минимальный выигрыш, т.е. находит
Число называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.
Другими словами, применяя свои чистые стратегии, игрок 1 может обеспечить себе выигрыш не меньше , а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем
.
Если в игре с матрицей А , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры
.
Седловая точка – это пара чистых стратегий (io, jo) соответственно игроков 1 и 2, при которых достигается равенство . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке.
Математически это можно записать и иначе:
где i, j – любые чистые стратегии соответственно игроков 1 и 2; а (io, jo) – стратегии, образующие седловую точку.
Таким образом, cедловой элемент aiojo является минимальным в i0-й строке и максимальным в j0-м столбце в матрице А. В этом и состоит принцип минимакса (или максимина). Он был сформулирован в 1928 году в работе Неймана и Моргенштерна «Теория игр и экономическое поведение».
Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (io, jo) игроков 1 и 2, образующая седловую точку и седловой элемент aiojo , называется решением игры. При этом i0 и j0 называются оптимальными чистыми стратегиями, соответственно, игроков 1 и 2.
Пример 2.
Решение. Седловой точкой является пара чисел (io=3, jo=1), при которой =2. Заметим, что хотя выигрыш для точки (3;3) также равен 2=
, она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.
Пример 3.
Решение. Из анализа матрицы выигрышей видно, что , т.е. данная матрица не имеет седловой точки. (Такие игры называются играми без седловой точки). Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i=1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь, игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д. Таким образом, в игре без седловой точки игроки вынуждены применять так называемые смешанные стратегии, заключающиеся в том, что игроки применяют не одну стратегию и выбирают среди них случайным образом.
Приведем пример, когда .
Пример 4. Пусть задана матрица экспертных оценок значений
Найти оптимальную стратегию для первого игрока (А), обеспечивающую ему максимальный средний выигрыш.
Решение. Найдем верхнюю и нижнюю цены игры.
Видим, что , то есть в этом случае игра без седловой точки.
Решение в данном случае находится по смешанной стратегии, то есть чистые стратегии A1 и A2 игрока А берутся с вероятностями p1 и p2 .
Аналогично, стратегии B1 и B2 игрока B берутся с вероятностями q1 и q2
Оптимальный выигрыш v находится как решение задачи линейного программирования:
является оптимальным решением. Применяя эти формулы в нашем случае, получим:
Итак, из 28 случаев игрок А должен придерживаться стратегии A1 и лишь в 9 случаях – стратегии A2. При этом выигрыш составит v=0,928 (). Таким образом оптимальной смешанной стратегией игрока А будет
.
Приведем основную теорему теории игр, утверждающую, что оптимальная смешанная стратегия существует.
Теорема Неймана–Моргенштерна. В матричной игре с нулевой суммой у каждого игрока имеется, по крайней мере, одна смешанная оптимальная стратегия.
Для матриц с большими размерностями используют, например, симплексный метод. Такие задачи рассмотрены далее.