X* -\-X*2=l.
Решая эту систему, получим оптимальную стратегию
22-21
И цену игры
«11+22 | -012-21 |
«И | -«12 |
| -%-«21 |
«22«11 | -«1221 |
| -%-«21 |
Применяя теорему об активных стратегиях при отыскании оптимальной смешанной стратегии второго игрока, получаем, что при любой чистой стратегии первого игрока средний проигрыш второго игрока равен V, т.е.
+12>2=
2Л +22>2= >,*+>2=1-
Тогда оптимальная стратегия второго игрока определяется по формулам:
.ci22-an
11+22-12-21
11-21
У2=-
11+22-12-21
Известно несколько методов нахождения оптимальных стратегий X*. и y*j в играх двух лиц с нулевой суммой. Мы приведем только два
из них, а именно: графический метод решения игр вида (2х«) или (тх2) и общий метод сведения игры двух лиц с нулевой суммой к задаче линейного программирования.
5.2.5. Диагональные игры. Пусть игра задана диагональной матрицей вида
О...............0
О «22 О..........О
..О а
пп J
Пусть К{х, >) = Ё £ ijiyj - платежная функция матричной игры, а
/=1У=1
х* и у. - оптимальные смешанные стратегии игроков.
Тогда из теории матричных игр вытекает справедливость следующих соотношений
v= min(/,>;)<(/,) hv = maxiC(x ,у)>К{е\у\
где е - чистая /-я стратегия игроков. Откуда щУ < v < и ♦ v «
у < - <х, , / = 1, «. Просуммировав все двойные последние нера-
п \
венства, получим 1 < vX- 1 • Откуда следует, что полученное двой-/=1 л,.,.
ное неравенство и все предыдущие двойные неравенства выполняются как равенства. Тогда решение игры задается следующими соотношениями
v = -j-Г-, =у = - ,1= 1,2,
-+ ...4--"
5.2.6. Доминирование стратегий. Говорят, что некоторая стратегия / первого игрока (задается /-й строкой платежной матрицы) доминиру-ется некоторой другой стратегией к первого игрока, если все элементы строки / не больше соответствующих элементов строки к, а именно:
<a,j,j= 1, «. Аналогичное определение можно привести и для
стратегий второго игрока, а именно: некоторая стратегия j второго игрока (задается j-u столбцом платежной матрицы) доминируется некоторой другой стратегией к второго игрока, если все элементы столбца j не меньше соответствующих элементов столбца к, а именно: < а,,
/= 1, .,„т. 122
Доминирование представляет отношение между стратегиями, наличие которого во многих практических случаях дает возможность сократить размеры исходной платежной матрицы игры. Это следует из того факта, что доминируемые стратегии могут быть исключены, при этом цена игры не изменяется.
Рассмотрим это понятие на примере матрицы
-0,5 3 -Г , О 2 0,5/
Рассуждая с позиции игрока 2, можно обнаружить преимущество его третьей стратегии перед второй, поскольку при первой стратегии игрока 1 выигрыш игрока 2 равен -3 (вторая стратегия) и 1 (третья стратегия), а при второй стратегии игрока 1 выигрыш игрока 2 равен -2 (вторая стратегия) и -0,5 (третья стратегия). Таким образом, при любой стратегии игрока 1 игроку 2 выгоднее применять свою третью стратегию по сравнению со второй. При наличии третьей стратегии игрок 2, если он стремится играть оптимально, никогда не будет использовать свою вторую стратегию, поэтому ее можно исключить из игры, т.е. в исходной платежной матрице можно вычеркнуть 2-й столбец:
-о -1 . о 0,5/
С позиции игрока 1 его первая стратегия оказывается хуже второй, так как по первой стратегии он только проигрывает. Поэтому первую стратегию можно исключить, а матрицу игры преобразовать к виду:
(О 0,5).
Учитывая интересы игрока 2, следует оставить только его первую стратегию, поскольку, выбирая вторую стратегию, игрок 2 оказывается в проигрыше (0,5 - выигрыш игрока 1), и матрица игры принимает простейший вид: (0), т.е. имеется седловая точка.
Доминирование можно распространить и на смешанные стратегии. Справедлива следующая теорема.
Теорема 6. Если элементы одной строки (столбца) не все меньше (больше) или равны соответствующим элементам других строк, но все меньше (больше) или равны некоторым выпуклым линейным комбинациям соответствующих элементов других строк (столбцов), то эту стра-