Тема 3. Решение игр в смешанных стратегиях

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

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

Cмешанными стратегиями игроков А и В в матричной игре называются распределения вероятностей на множестве их чистых стратегий, т.е. любые вектора х =(х ₁, х ₂, …, х_m) и y =(y ₁, y ₂, …, y_n) соответственно, обладающие свойствами:

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

Если игроками выбраны смешанные стратегии (х, у), то функция выигрыша F (x, y) игрока А определяется равенством:

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

Седловая точка матричной игры в смешанных стратегиях находится из условия:

где х, у − вероятностные вектора. Общее значение левой и правой части этого равенства называется ценой матричной игры Q в смешанных стратегиях и обозначается через q. Она удовлетворяет двойному неравенству:

где, как и выше, a − нижняя цена, b − верхняя цена матричной игры Q.

Седловая точка (x*, y*) называется оптимальным решением (или решением) матричной игры; вероятностный вектор x* − оптимальной смешанной стратегией игрока А, вероятностный вектор y* − оптимальной смешанной стратегией игрока B.

Основная теорема теории игр − теорема Неймана: каждая конечная матричная игра имеет оптимальное решение (седловую точку) в смешанных стратегиях.

Таким образом, у каждого игрока существует оптимальная смешанная стратегия. Если матричная игра имеет цену в чистых стратегиях (a = b), то оптимальное решение в чистых и смешанных стратегиях совпадают.

Пусть х* = (х* ₁, х* ₂, …, х*_m), y* = (y* ₁, y* ₂, …, y*_n) − оптимальные смешанные стратегии игроков А и В. Если чистые стратегии А_i, В_j входят в оптимальные смешанные стратегии с отличными от нуля вероятностями (х*_i >0, y*_j >0), то они называются активными стратегиями.

Если х* − оптимальная смешанная стратегия игрока А, а В_j − активная стратегия игрока В (y*_j >0), то:

т.е. при любой активной стратегии игрока В выигрыш остается неизменным и равным цене игры q. Если В_k − не активная стратегия игрока В (y*_k =0), то:

т.е. выигрыш игрока А будет больше цены игры q.

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

Множеству оптимальных стратегий можно дать графическую интерпретацию. Для этого в декартовой системе координат строят графики прямых выигрыша F(x, j) для смешанной стратегии x игрока А и чистых стратегий В_j игрока В. Для построения этих прямых применяются средства построения диаграмм в электронных таблицах Excel. Анализируя полученные на диаграмме графики, проводят нижнюю огибающую прямых и находят на ней верхнюю точку. Пересекающиеся в этой точке прямые – стратегии В_j – следует считать активными стратегиями в оптимальном решении рассматриваемой игры.

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

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

Определение 1. Если в платежной матрице игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующее этим строкам (столбцам) стратегии называются дублирующими.

Определение 2. Если в платежной матрице игры все элементы некоторой строки, определяющей стратегию А_i игрока А, не больше (т.е. меньше или некоторые равны) соответствующих элементов другой строки, то стратегия А_i называется доминируемой (заведомо невыгодной).

Определение 3. Если в платежной матрице игры все элементы некоторого столбца, определяющего стратегию В_i игрока В не меньше (т.е. больше или некоторые равны) соответствующих элементов другого столбца, то стратегия В_i называется доминируемой (заведомо невыгодной).

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

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

Свойство 1. Если ко всем элементам платежной матрицы прибавить (вычесть) одно и тоже число b, то оптимальные смешанные стратегии игроков не изменятся, только цена игры увеличится (уменьшится) на это число b.

Свойство 2. Если каждый элемент платежной матрицы умножить на положительное число k, то оптимальные смешанные стратегии игроков не изменятся, а цена игры умножится на k.

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

Рассмотрены принципы аналитического решения задач 2×2 и графоаналитический метод 2× n и m ×2.

Дата добавления: 2014-01-07