Теорема 4. Любая конечная игра размера m×n имеет решение, в котором число активных стратегий у каждого игрока не превосходит наименьшего из чисел m и n.

Из этой теоремы следует, что у игры размера 2×n всегда имеется решение, в котором каждый игрок использует не более двух активных стратегий.

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

 

Для каждой из n чистых стратегий второго игрока строим график функции выигрыша первого игрока по формуле:

(1) ;

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

Пример 3. Инга и Кора играют в следующую игру: Кора прячет в кулаке либо 1, либо 2, либо 3, либо 4 монеты (достоинством в 1 доллар). Инга угадывает: четное число монет или нечетное. Если она угадала, Кора отдает монеты, иначе Инга должна заплатить ту сумму, которая была в кулаке у Коры.

Решение. Составим платежную матрицу игры размера 2×4 и найдем нижнюю и верхнюю цену игры. = –3 , = 1, < , следовательно, игра без седловой точки.

 

Кора Инга
чет –1 –3 –3
нечет –2 –4 –4
 

 

Функции выигрыша Инги, соответствующие чистым стратегиям Коры вычисляем по формуле (1):

Построим графики функций на отрезке [0, 1] изменения частоты :

 

Рис. 9.2

 

Ломаная ANB является нижней границей выигрышей первого игрока, координаты точки N определяют оптимальную стратегию Инги и цену игры. Тока N – точка пересечения всех четырех графиков, в частности, и с противоположными наклонами, поэтому активными стратегиями Коры можно считать третью и четвертую стратегии. Получаем игру размера 2×2 с платежной матрицей: , для которой находим, что = , = , V = 0, = , = . Поэтому оптимальная стратегия Коры имеет вид:

.

Аналогично можно решить игру размера m×2, где m >2.

 








Дата добавления: 2016-04-14; просмотров: 682;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.