Смешанные стратегии

Пример

Проверим наличие седловой точки.

Для игрока А: Max (1, 1, 10) = 10

Для игрока В: min(16, 10, 10, 16) = 10

Седловые точки - (3, 2) и (3, 4). Цена игры = 10; оптимальный выбор для игрока 1 - третий, для игрока 2 равнозначны второй и третий

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

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

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

и - вероятности, с которыми игроки А и В выбирают свои чистые стратегии и в ходе игры.

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

Функцию называют функцией выигрыша или платежной функцией.

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

Величину называют ценой игры.

Поиск оптимальных смешанных стратегий начинают с упрощения платежной матрицы. Если в платежной матрице элементы k -й строки не меньше соответствующих элементов s -й строки, т. е. , то говорят, что стратегия доминирует над стратегией . Аналогично, если элементы l -го столбца не превосходят соответствующих элементов r -го столбца, т. е. , то говорят, что стратегия доминирует над стратегией . Частным случаем доминирования стратегий является дублирование стратегий, когда или . Исключение из платежной матрицы доминируемых стратегий (ими игрокам пользоваться заведомо невыгодно) позволяет уменьшить ее размерность, а это упрощает решение игры. Вероятность применения доминируемых стратегий равна нулю.

Оптимальные смешанные стратегии и в игре с платежной матрицей и ценой v остаются оптимальными и для игры с платежной матрицей (где b > 0) и ценой bv + с. На этом основании платежную матрицу можно всегда преобразовать так, что ее элементы будут целыми неотрицательными числами, а это упрощает расчеты.