Матричные игры в формате 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 (). Таким образом оптимальной смешанной стратегией игрока А будет .

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

Теорема Неймана–Моргенштерна. В матричной игре с нулевой суммой у каждого игрока имеется, по крайней мере, одна смешанная оптимальная стратегия.

Для матриц с большими размерностями используют, например, симплексный метод. Такие задачи рассмотрены далее.

наверх