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

Лабораторная работа 4

Тема: Принятие решений в условиях конфликта

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

Рассмотрим матричную игру (m x n) с платежной матрицей

Н = ,

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

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

Пусть игрок А выбирает некоторую стратегию А_i, тогда в наихудшем случае (например, если выбор станет известен игроку В) он получит выигрыш равный min a_ij (значение минимального элемента в строке). Предвидя эту возможность, игрок А должен выбрать такую стратегию, что­бы максимизировать свой минимальный в каждой стратегии выигрыш a.

Таким образом, a = max min a_ij.

i

Величина a называется нижней ценой игры (a — это гарантированный выиг­рыш игрока А).

Очевидно, a находится в одной из строк матрицы Н, пусть в i = 1, тогда стратегия A₁ называется максиминной. Таким образом, если игрок А будет придерживаться максиминной стратегии, то ему при любом поведении игрока В гарантиро­ван выигрыш, во всяком случае, не меньший a.

С другой стороны, противник — игрок В, заинтересован в том, чтобы обратить выигрыш игрока А в минимум, поэтому он должен пересмотреть каждую свою стратегию с точки зрения максимального выигрыша игроком А при этой стратегии. Други­ми словами, при выборе некоторой стратегии В_j он должен исхо­дить из максимального проигрыша в этой стратегии, равного max a_tj, и найти такую стратегия, при которой этот проигрыш будет наименьшим - β.

Величина bназывается верхней ценой игры, а соответствующая ему стратегия B_io — минимаксной. Величина b представляет собой гарантированный проигрыш игрока В при любой стратегии игрока А.

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

Рассмотрим пример решения игры.

Пример 1. Дана платежная матрица 3 х 4

Н = .

Требуется вычислить верхнюю и нижнюю цену игры.

Решение. Представим игру в виде таблицы (таблица 1).

Таблица 1 – Пример решения игры

Дадим пояснения по содержимому таблицы 1. Если игрок А выбирает стратегию А₁, то он может получить максимальный выигрыш равный 10 у.е. (если игрок В применит стратегию В₁). Минимальный же его выигрыш (если игрок В применит стратегию В₂) составляет 4 у. е. Таким образом, если игрок А применит стратегию А₁, то независимо от того, какую стратегию применит игрок В, игрок А получит гарантированный выигрыш равный 4 у.е.

Аналогично рассуждая о стратегиях А₂ и А₃, можно утверждать, что гарантированный выигрыш игрока А при использовании стратегии А₂ составит 6 у.е., а стратегии А₃ – 1 у.е.

Естественно, что в этом случае, игрок А должен принять стратегию А₂. Эта стратегия будет максиминной стратегией, а значение α = 6 у.е. будет нижней ценой игры.

Игрок В стремится минимизировать свой проигрыш. Выбрав стратегию В₁ игрок В может проиграть не более 10 у.е., не зависимо от того, какую стратегию применит при этом игрок А. Аналогично, при выборе стратегий В₂, В₃, В₄ игрок В проиграет не более 6, 11 и 20 у.е. Естественно, игрок В должен выбрать стратегию, при которой его гарантированный проигрыш будет минимальным, т.е стратегию В₂. Эта стратегия будет максиминной, а значение β = 6 – верхней ценой игры.