Нижняя и верхняя цена игры. Принцип минимакса

Рассмотрим матричную игру типа с платежной матрицей

.

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

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

· Число

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

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

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

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

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

· Число

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

Таким образом, если игрок В применяет минимаксную стратегию, то игрок А не может выиграть больше, чем .

· Принцип осторожности, заставляющий игроков придерживаться максиминной и минимаксной стратегий соответственно, называют «Принципом минимакса», а минимаксную стратегию называют общим термином «Минимаксные стратегии».

Пример 2.1. Найти нижнюю и верхнюю цены игры с платежной матрицей

.

Решение. В каждой строке платежной матрицы найдем наименьший элемент, и запишем его справа от матрицы. В каждом столбце платежной матрицы найдем наибольший элемент, и запишем его снизу от матрицы. В результате получим таблицу

.

Нижняя цена игры

.

Верхняя цена игры

.