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

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

Рассмотрим парную игру с нулевой суммой, в которой выигрыш одного игрока равен проигрышу другого.

У каждого игрока А и В конечное число возможных действий – чистых стратегий.

Игрок А располагает m чистыми стратегиями А1, А2, … , Аm. Игрок В – n чистыми стратегиями B1, B2, … , Bn. Игра определена, если указано правило, сопоставляющее каждой паре чистых стратегий Ai и Bj число aij – выигрыш игрока А за счет игрока B. При aij<0 игрок А платит игроку В сумму |aij|. Если известны значения aij выигрыша для каждой пары (Ai,Bj) стратегий, то можно составить матрицу игры – платежную матрицу.

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

Ai Bj B1 B2 B3 ……………… Bn
A1 a11 a12 a13 ……………… a1n
A2 a21 a22 a23 ……………… a2n
………………
Am am1 am2 am3 ……………… amn

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

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

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

С учетом этого игрок А анализирует матрицу выигрышей: для каждой чистой стратегии Аi он определяет минимальное значение . Затем по минимальным выигрышам αi он отыскивает такую чистую стратегию Аi0, при которой этот минимальный выигрыш будет максимальным, т.е. находит

.

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

Игрок В старается максимально уменьшить проигрыш. Для каждой чистой стратегии Вj он отыскивает . Затем по βj находит свою стратегию Bj0, при которой его проигрыш будет минимальным, т.е.

.

Число β называется верхней чистой ценой игры (минимаксом). Оно показывает, какой максимальный проигрыш при использовании своих чистых стратегий может быть у игрока В. Соответствующая чистая стратегия Bj0 игрока B минимаксной.

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



Пример. Найти максиминную и минимаксную стратегии в игре с матрицей

Решение.

B1 B2 B3 В4 αi
A1 -1 -1
A2
A3 -2 -1 -2
βj

Максиминной чистой стратегией является А2.

Минимаксной для игрока B является стратегия В3.

Теорема 1. В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т.е. α ≤ β.

Доказательство:

По определению

,

значит αi ≤ aij ≤ βj или αi ≤ βj.

Это неравенство справедливо при любых комбинациях i и j. Будет оно справедливо для тех i и j, для которых и , и при этих i и j получим α ≤ β.

Если в матричной игре нижняя и верхняя чистые цены игры совпадают, т.е. α = β, то это игра имеет седловую точку в чистых стратегиях и чистую цену игры .

Обозначим через i* и j* номера чистых стратегий, при которых имеет место равенство α = β. Пару чистых стратегий игроков А и В, при которых достигается равенство α = β, называют седловой точкой матричной игры, а элемент ai*j* матрицы, стоящий на пересечении i* строки и j* столбца, – седловым элементом платежной матрицы.

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



Пример. Швейное предприятие планирует к массовому выпуску новую модель одежды. Спрос на эту модель не может быть точно определен. Предполагают, что его величина характеризуется тремя возможными состояниями (I, II, III). С учетом этих состояний анализируется три возможных варианта выпуска данной модели (А1, А2, А3). Каждый из этих вариантов требует своих затрат и обеспечивает различный эффект. Прибыль (тыс. руб.), которую получает предприятие при данном объеме выпуска модели и соответствующем состоянии спроса, определяется матрицей

I II III
A1
A2
A3

Найти объем выпуска модели одежды обеспечивающий среднюю величину прибыли при любом состоянии спроса.

Решение. Проверим, имеет ли исходная матрица седловую точку.

.

Число 22 – цена игры. Игра имеет седловую точку, соответствующую варианту А1 выпуска модели одежды. Объем выпуска модели, соответствующий данному варианту, обеспечивает прибыль в 22 тыс. руб. при любом состоянии спроса.

Упрощение игр

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

Если в матрице (aij)m×n игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующие строкам (столбцам) стратегии называются дублирующими.

Если в матрице (aij)m×n игры все элементы некоторой строки, определяющей i-ю стратегию Аi игрока А, не больше (меньше или равны) соответствующих элементов другой строки, то i-я стратегия Аi называется заведомо невыгодной.

Если в матрице (aij)m×n игры все элементы некоторого столбца, определяющего j-ю стратегию Вj игрока В, не меньше (больше или равны) соответствующих элементов другого столбца, то j-я стратегия Вj называется заведомо невыгодной.

Рассмотрим платежную матрицу игры:

B1 B2 B3 В4 В5 αi
A1
A2
A3
A4
βj

α = 3 ≠ β = 5. Платежная матрица игры не имеет седловой точки.

Сравнивая почленно элементы второй и третьей строк, видим, что все элементы второй строки меньше соответствующих элементов третьей строки. Следовательно, вторая стратегия для игрока А заведомо невыгодна и ее можно исключить. Аналогично, сравнивая А3 и А4, исключаем А4. Получаем матрицу игры:

B1 B2 B3 В4 В5
A1
A3

Замечаем, что 1, 2, 3 стратегии игрока В заведомо невыгодны по сравнению с 5-й стратегией, поскольку игрок В стремится уменьшить выигрыш игрока А. Исключая эти стратегии, получаем матрицу 2×2, в которой нет дублирующих и заведомо невыгодных стратегий.

В4 В5
A1
A3

Перенумеруем стратегии, запишем платежную матрицу:

В1 В2 αi
A1
A2
βj

α = 3, β = 5.

Если для упрощенной матрицы α = β, то число α = β = v есть цена игры не только с упрощенной, но и со сходной матрицей. Если α < β, то анализируется упрощенная матрица, а затем осуществляется возвращение к исходной матрице.


mdk0301-differencialnaya-diagnostika-i-okazanie-neotlozhnoj-medicinskoj-pomoshi-na-dogospitalnom-etape-temi-1-8.html
mdk0302teoriya-i-metodika-razvitiya-rechi-u-detej.html
    PR.RU™