три стратегии: кредитовать проект 1, 2 или 3. Его противник — природа (общая финансовая ситуация) является игроком 2. Будем считать, что у игрока 2 имеется пять стратегий: исключительно благоприятная общая финансовая ситуация, благоприятная, нейтральная, неблагоприятная и исключительно неблагоприятная. Поскольку банк хочет получить максимальный доход при самой неблагоприятной ситуации, то предполагаем, что природа «хочет» навредить банку как можно сильнее. Если ситуация будет лучше, то доход банка увеличится. В табл. 2 представлена платёжная матрица этой игры:
Рассмотрим платёжную матрицу произвольной антагонистической игры. Основное предположение при анализе антагонистических игр: каждый игрок действует наилучшим для себя образом, т. е. пытается получить максимально возможный выигрыш при любых стратегиях противника, считая, что противник также действует наилучшим для себя образом. Следовательно, игрок 1 считает, что при выборе им любой стратегии (любой строки платёжной матрицы), противник выберет столбец, дающий ему максимальный выигрыш, т. е. минимальный для игрока 1. Тогда оптимальная стратегия игрока 1 - выбрать самый большой из минимальных выигрышей, т. е. выбрать
v = max min aij (2)
i j
Эта стратегия гарантирует наибольший выигрыш независимо от стратегии противника. Такая стратегия называется максиминной стратегией (стратегия максимизации минимального выигрыша), а v — максимином.
Аналогично, если игрок 2 выбирает j-ю стратегию, то в худшем случае он проигрывает max aij
i
поэтому его гарантированный проигрыш:
v*= min max aij
j i (3)
Такая стратегия называется минимаксной стратегией (стратегия минимизации максимального проигрыша), а v- минимаксом.
Например, в игре, моделирующей конкуренцию предприятий, игрок 1 считает, что независимо от его стратегии выбора продукции для производства (т. е. независимо от выбора им строки платёжной матрицы), игрок 2 выберет стратегию (столбец платёжной матрицы), максимизирующую его выигрыш, т.е. минимизирующую выигрыш игрока 1. Если игрок 1 будет производить продукцию А1 (выберет 1-ю строку платёжной матрицы), то игрок 2 может производить продукцию В2 (выбрать 2-й столбец), тогда выигрыш игрока 1 равен 400, а выигрыш игрока 2 — 600. Если игрок 1 будет производить продукцию А2 (выберет 2-ю строку), то игрок 2 может производить продукцию В1 (выбрать 1-й столбец). Тогда выигрыш игрока 1 будет 100, а игрока 2 - 900. Поэтому игроку 1 нужно найти минимальный выигрыш в каждой строке платёжной матрицы и рассматривать только его. Этот выигрыш ему гарантирован. Рассмотрим платёжную матрицу этой игры:
Справа в столбец выписаны минимальные элементы каждой строки. Оптимальная стратегия игрока 1- выбрать строку с самым большим минимальным элементом, это гарантируем ему наибольший выигрыш, независимо от стратегии игрока 2. Максимальный среди минимальных элементов строк выигрыш 700 (он заключён в квадрат). Следовательно, при выпуске любой продукции 2-м предприятием, доход 1-го предприятия не будет меньше 700 денежных единиц, если он будет выпускать продукцию А3. Таким образом, для игрока 1 максиминной является 3-я стратегия, она оптимальна. Максимин равен:
v = max min aij = 700
i j
Игрок 2 также рассматривает наихудшие варианты и стремится обеспечить себе максимальный выигрыш (минимально выигрыш своему противнику). Если игрок 2 выберет 1-й столбец, то игрок 1 может выбрать 3-ю строку и обеспечить себе выигрыш 900. Выигрыш игрока 2 при этом – 100. Если игрок 2 в, берет 3-й столбец, то игрок 1 может выбрать 3-ю строку и обеспечить себе выигрыш 800, а выигрыш игрока 2 при этом – 200. Следовательно, игрок 2 может рассматривать только максимальные элементы каждого столбца. Они выписаны под матрицей. Выбрав среди них наименьший (700), игрок 2 имеет гарантированный проигрыш не больше 700, т.е. выигрыш не меньше 300 (1000 - 700 = 300) при любых деиствиях игрока 1. Таким образом, для игрока 2 минимаксной является 2-я стратегия, она оптимальна, а минимакс:
v* = min max aij = 700
j i
Рассуждая аналогично, найдём максимин и минимакс в игре, моделирующей кредитование проектов банком. Платёжная матрица этой игры:
0
100
320
720 600 680 340 450
максимин и минимакс (курсив):
v = max min aij = 320
i j
v* = min max aij = 340
j i
Максиминная стратегия игрока 1- выбрать 3-ю строку платёжной матрицы (кредитовать проект 3). Она ему гарантирует, что какая бы не сложилась финансовая ситуация, он получит выигрыш не меньше 320.
Для природы минимаксной является 4-я стратегия. Если цель природы - гарантированно максимально уменьшить выигрыш игрока 1, то ей следует создать неблагоприятную финансовую ситуацию.
Если игрок 1 следует максиминной стратегии, то его выигрыш v в игре будет не меньше максимина v , а если игрок 2 выбирает минимаксную стратегию, то его проигрыш (-v) будет не больше минимакса v*, т.е.
v = max min aij ≤ v ≤ v* = min max aij
i j j i
В антагонистической игре всегда v ≤ v*. Если выполнено строгое равенство
v = v*,
то стратегии игроков являются совместимыми, а платёжная матрица имеет седловую точку:
v = v = v* = max min aij = min max aij
i j j i
являющуюся одновременно минимаксом и максимином.
Так, в игре моделирующей конкуренцию между двумя предприятиями, максимин и минимакс совпадают:
v = max min aij = min max aij=v* =700
i j j i
платёжная матрица имеет седловую точку а32, стратегии игроков совместимы. Игрок 1 выбирает 3-ю стратегию, игрок 2 - 2-ю, каждый получает свой гарантированный выигрыш (700 и 300).
Седловая точка соответствует равновесию в игре. При этом, если один из игроков выбирает стратегию, соответствующую положению равновесия, то другому также выгоднее всего избрать стратегию, отвечающую седловой точке. Тогда каждый игрок получает свой гарантированный платёж (выигрыш или проигрыш). Выбор другой стратегии может уменьшить гарантированную прибыль или увеличить возможные потери.
Например, если игрок 2 в модели конкуренции предприятий выберет 3-ю стратегию, то он может получить выигрыш 500 (если игрок 1 выберет 1-ю стратегию), а может - только 200 (если игрок 1 изберёт свою оптимальную 3-ю стратегию).
Игра двух игроков с нулевой суммой, имеющая седловую точку, называется вполне определённой. Игры, в которых выполняется строгое равенство
v = max min aij < v*= min max aij,
i j j i
называются не полностью определёнными играми.
Игра, моделирующая кредитование проектов, является не полностью определённой, так как в ней выполнено строгое неравенство:
v = max min aij =320 0. Разделим соотношения (7) на v и определим:
Задача игрока 1 — максимизировать выигрыш, т.е. максимизировать v. Поскольку
(9)
то v максимально, когда минимальна.
Аналогично, задача игрока 2- минимизировать v, а так как
(10)
то v минимальна, когда максимальна.
Тогда анализ платёжной матрицы с точки зрения игрока 1 эквивалентен задаче линейного программирования: найти минимум целевой функции.
f = x1+x2+…+xm
при условиях
(11)
Задачу игрока 2 также можно сформулировать как задачу линейного программирования, двойственную к задаче (11): найти максимум целевой функции
g = y1+y2+…+yn
при условиях
(12)
Задачи линейного программирования (11) и (12) можно решить, например, симплекс-методом.
Пусть у* = (у*1, у*2, ..., у*n)- решение задачи линейного программирования (12), х* = (х*1, х*2, ..., х*m) — теневые цены (решение двойственной задачи). Тогда значение седловой точки v определяется из условий (9), (10):
(13)
а оптимальные стратегии игроков получаются из решения з| чи линейного программирования нормированием:
ξ*i=v x*i ,i=1,…,m,
η*j=v y*j ji=1,…,n. (14)
Пусть антагонистическая игра задана платёжной матрицей . Словесно-формульное описание алгоритма анализа платёжной матрицы антагонистической игры сведением к задаче линейного программирования:
1* начало процесса.
2* ввод платёжной матрицы игры А.
3* Формулировка задачи линейного программирования (12): найти максимум функции
при условиях Ay ≤ 1, y≥ 0.
4* Решение задачи линейного программирования (12). Результат
у* = (у*1, у*2, ..., у*n)- оптимальный вектор, х* = (х*1, х*2, ..., х*m) теневые цены.
5* Определение положения равновесия: ;
оптимальной стратегии игрока 1:
оптимальной стратегии игрока 2:.
6* Вывод результата
7* Конец процесса