 |
Упрощение платёжных матриц
|
|
|
|
Поиск оптимальных стратегий тем сложнее, чем больше размерность платёжной матрицы. Поэтому поиск оптимальных стратегий начинают с упрощения платёжной матрицы.
Определение 20. Если в платёжной матрице элементы 
-ой строки не меньше соответствующих элементов 
-ой строки, то есть 
(
), то говорят, что стратегия 
доминирует над стратегией 
.
Определение 21. Если в платёжной матрице элементы 
-го столбца не превосходят соответствующих элементов 
-го столбца, то есть 
(
), то говорят, что стратегия 
доминирует над стратегией 
.
Определение 22. Стратегии и ( и ) называются дублирующими друг друга, если 
() (
()).
Замечание. Дублирование является частным случаем доминирования. Игрокам выгоднее пользоваться доминирующими стратегиями. Поэтому вероятность применения доминируемых стратегий равна нулю. Исключая из платёжной матрицы доминируемые стратегии, можно уменьшить её размерность, что упрощает решение игры. При исключении доминируемых стратегий цена игры не меняется.
Теорема 4. Оптимальные смешанные стратегии 
и 
в игре с платёжной матрицей 
и ценой 
остаются оптимальными и для игры с платёжной матрицей 
(
) и ценой 
.
На основании теоремы 4 платёжную матрицу всегда можно преобразовать так, что её элементы будут целыми неотрицательными числами, что упрощает расчёты.
Пример 2.6 [2]. Найти решение игры, заданной платёжной матрицей:
.
Решение. 1) Найдём верхнюю и нижнюю цены игры:
, 
.
Так как 
, то седловой точки в чистых стратегиях нет. Оптимальной стратегией первого игрока является стратегия 
, так как в ней расположен максимин 
. Оптимальной стратегией второго игрока является стратегия 
, так как в ней расположен минимакс 
.
2) Исключим доминируемые (невыгодные) стратегии первого игрока. Так как все элементы строки 
не превосходят элементов строки , то строку можно исключить. Аналогично, все элементы строки 
не превосходят элементов строки , поэтому исключаем и её. Строку 
исключить нельзя, так как в ней есть элементы, превосходящие элементы строки . Тогда преобразованная платёжная матрица игры будет иметь вид 
.
|
|
|
3) Исключим доминируемые стратегии второго игрока. Все элементы столбцов 
, 
и 
больше соответствующих элементов столбца , поэтому эти столбцы можно исключить. В столбце 
есть элементы, меньшие соответствующих элементов столбца , поэтому этот столбец следует оставить. Преобразованная платёжная матрица игры будет иметь вид 
.
4) Найдём седловую точку матрицы 
в смешанных стратегиях.
Пусть оптимальные стратегии игроков определяются, соответственно векторами вероятностей 
, 
, компоненты которых удовлетворяют условию нормировки: 
, 
.
Функция выигрыша будет иметь вид:
.
Так как, согласно теореме о минимаксе, требуется найти максимум функции выигрыша, то должно быть 
и, следовательно, должно выполняться равенство: 
. Система уравнений для определения оптимальных стратегий и имеет вид:
В ней содержится 3 уравнения и 5 неизвестных.
Для отыскания 
и 
запишем: 
и 
, тогда 
. Подставим полученное соотношение в первое уравнение системы, получим: 
или 
.
Так как по теореме 3 значения 
и 
должны быть отличны от нуля (как оптимальные), то последнее равенство выполняется при произвольных положительных 
и 
только в том случае, когда
или 
.
Так как , то 
, и 
. Раскрывая скобки и выражая 
, получим 
, 
.
Таким образом, вероятности оптимальных стратегий первого игрока 
, 
.
Применяя аналогичный приём для отыскания и получаем, что так как и , то 
. Подставим это соотношение в первое уравнение системы, получим:
.
Сгруппируем слагаемые в этом уравнении относительно и 
:
.
Так как значения и отличны от нуля, то последнее равенство выполняется только в том случае, когда
|
|
|
или 
.
Так как , то 
, и 
. Раскрывая скобки и выражая , получим 
, 
.
Таким образом, вероятности оптимальных стратегий второго игрока 
, 
.
Подставим найденные оптимальные вероятности смешанных стратегий в функцию выигрыша, найдём цену игры:
.
Ответ: 
при 
и 
. Первый игрок может с одинаковыми вероятностями применять обе стратегии. Второму игроку выгоднее чаще использовать первую стратегию.
|
|
|
