16.Принцип минимакса.

Пусть дана парная игра с нулевой суммой, заданная платежной матрицей размерности mn. Решить матричную игру означает определить наилучшую стратегию игрока A, а также наилучшую стратегию игрока B. Если рассматривается стратегическая игра, то предполагается, что противники одинаково разумны, и каждый из них делает все для того, чтобы добиться своей цели. Поэтому каждый игрок должен рассчитывать на самое неблагоприятное для себя поведение противника.

Используя этот принцип, найдем наилучшую стратегию игрока A. Выбирая стратегию Ai, мы должны рассчитывать, что игрок B ответит на нее той из своих стратегий Bj, для которой выигрыш игрока A будет минимальным. Поэтому для каждой стратегии Ai найдем

где– минимальный гарантированный выигрыш игрока А при применении стратегии Аi.

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

.

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

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

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

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

Можно показать, что всегда максимин не превосходит минимакс, т.е.

.

Если нижняя цена игры равна верхней ( ), то говорят, что игра имеет седловую точку и чистую цену игры . Стратегии Ai* и Bj*, позволяющие достичь этого значения, называются оптимальными, а пара оптимальных стратегий (Аi*,Вj*), называется седловой точкой матричной игры.

Таким образом, решив игру с седловой точкой, мы рекомендуем каждому игроку применять одну свою стратегию (Ai* или Bj*). Тогда игроку А гарантировано, что он получит выигрыш, не меньший чистой цены игры . Игроку В гарантировано, что он получит проигрыш, не больший чистой цены игры .