Показатели эффективности чистых стратегий. Максиминные и минимаксные стратегии.

Рассмотрим матричную m × n - игру с игроками А и В,в кото­рой игрок А обладает mчистыми стратегиями ={А₁,..., А_m}, a игрок В - n чистыми стратегиями ={В₁,..., В_n}. Значения функции выигрыша игрока A обозначим через а_ij,т. е. F_A (i, j) = а_ij, и тогда матрица игры будет иметь вид

Bj A = Ai	B 1	B 2	…	Bn
A 1	a 11	a 12	…	a 1 n
A 2	a 21	a 22	…	a 2 n
…	…	…	…	…
Am	am 1	am 2	…	amn

Перед игроком А стоит задача выбора чистой стратегии из множества , эффективной в определенном смысле, в результате применения которой он получит максимально возможный гарантированный выигрыш. Если игрок А выбрал стратегию А_i (i =1, …, m),, то его выигрышем может быть один из выигрышей

а_{i 1}, а_{i 2}, …, а_in,

расположенных в i -й строке матрицы, в зависимости от выбранной игроком В стратегии. Предполагая поведение игрока А крайне осмотрительным, необходимо считать, что игрок В сыграет наилучшим для себя образом и на выбор игроком А стратегии А_i выберет ту стратегию B_j, при которой выигрыш игрока А окажется минимальным. Обозначим минимальный среди выигрышей через α _i:

и назовем его показателем эффективности стратегии А_i.

Продолжая действовать разумно, игрок А должен выбрать ту стратегию, которая максимизирует показатель эффективности, т.е. для которой число α _i максимально. Если обозначить это максимальное число через α:

тогда

Описанный принцип выбора эффективной стратегии игроком А называется максиминным принципом, а выигрыш α - максимином. Стратегия соответствующая максимину α, т. е. стратегия номер i ₀ которой максимизирует показатель эффективности α _i, т. е.

называется максиминной стратегией игрока А.

Пусть игрок А выбрал максиминную стратегию а игрок В - какую-то произвольную стратегию B_j, j = 1,..., п. Тогда в создавшейся ситуации ( B_j) выигрыш игрока А в чистых стратегиях будет для которого в силу равенств и будет справедливо неравенство

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

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

а _{1 j}, а _{2 j}, …, а_mj,

 

выигрышей, стоящих в j -м столбце игровой матрицы, в зависимости от того, какой стратегии будет придерживаться игрок А. Но так как игрок В предполагает, что игрок А играет наилучшим для себя образом, то выигрышем игрока А будет максимальное из чисел а _{1 j}, а _{2 j}, …, а_mj; обозначим его через β_j:

и назовем показателем неэффективности стратегии В_j. Таким образом, для любой стратегии B_j игрока В наибольший его проигрыш равен β _j. В интересах игрока В - выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел обозначим β:

Отсюда в силу формулы получим для β выражение:

Выбор игроком В стратегии с наименьшим показателем β _j оправдывает то, что он назван показателем неэффективности.

Критерий выбора эффективной стратегии для игрока В называется минимаксным принципом, а выигрыш β называется минимаксом. Стратегия для которой

называется минимаксной стратегией игрока В.

При выборе игроком В стратегии , его проигрышем может быть один из проигрышей а _{1 j}, а _{2 j}, …, а_mj, или, другими словами, его выигрышем может быть один из выигрышей

b_j1 = -a_1j, b_j2 = -a_2j,..., b_jm = -a_mj.

Тогда показателем эффективности стратегии B_j (относительно выигрышей игрока В) будет минимальное из этих чисел, которое, в силу обозначения , можно представить так:

а максимином будет число выражающееся иначе следующим образом:

Таким образом, показатель эффективности стратегии B_j (относительно выигрышей игрока B) противоположен показателю неэффективности стратегии B_j (относительно проигрышей игрока В) и максимин (относительно выигрышей игрока В) противоположен минимаксу (относительно проигрышей игрока B).