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

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

(1.2)

Где i-я строка соответствует Аi-й стратегии игрока А;

j-й столбец соответствует Вj-й стратегии игрока В.

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

Очевидно, находится в одной из строк матрицы Н, пусть в i0, тогда стратегия называется максиминной.

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

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

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

Принцип осторожности, диктующий игрокам выбор стратегий максиминной или минимаксной соответственно, в теории игр именуют принципом минимакса, а сами стратеги максиминные и минимаксные – общим термином минимаксные стратегии.

Рассмотрим пример нахождения и .

Пример (п.1.1)

Пусть игра задана матрицей

Определим нижнюю и верхнюю цены игры.

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

10 4 3 10

В этом примере нижняя и верхняя цены игры совпадают: