6. Максимин и минимакс игры. Максиминные и минимаксные стратегии. Нижняя и верхняя цены игры в чистых стратегиях. Соотношение между ними.

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

Bj A= Ai	B1	B2	…	(1) Bn
A1	a11	a12	…	a1n
A2	a21	a22	…	a2n
…	…	…	…	…
Am	am1	am2	…	amn

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

а_i1, а_i2, …, а_in, (2)

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

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

(4)

то по формуле (3)

(5)

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

называется максиминной стратегией игрока А. Множество всех (чистых) максиминных стратегий игрока А обозначим через

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

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

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

а_1j, а_2j, …, а_mj, (8)

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

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

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

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

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

называется минимаксной стратегией игрока В. Множество всех (чистых) минимаксных стратегий игрока В обозначим через

При выборе игроком В стратегии , его проигрышем может быть один из проигрышей (8), или, другими словами, его выигрышем может быть один из выигрышей

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

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

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

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

Если игрок В придерживается своей минимаксной стратегии а игрок А - любой своей стратегии A_k, k = 1, ..., т, то для проигрыша игрока В в ситуации (A_k, ), с использованием равенств (9) и (12), получим неравенство

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

Для нахождения нижней и верхней цен игры удобно матрицу игры (1) увеличить в размерах, приписав (n+1)-й столбец показателей эффективности α_i: стратегий А_i игрока А и (т+1)-ю строку показателей неэффективности β_j стратегий B_j игрока В. В результате получим следующую матрицу:

Bj Ai	B1	B2	…	Bn	αi
A1	a11	a12	…	a1n	(13) α1
A2	a21	a22	…	a2n	α2
…	…	…	…	…	…
Am	am1	am2	…	amn	αm
βj	β1	β2	…	βn	α β

Следующая простая теорема устанавливает соотношение между показателями эффективности α_i стратегий A_i игрока А, показателями неэффективности β_j стратегий B_j игрока В и выигрышами а_ij и, как следствие этого соотношения, - неравенство между нижней и верхней ценами игры в чистых стратегиях.

Теорема 1. Для элементов матрицы (13) имеют место неравенства

α_i ≤ a_ij ≤ β_j, i = 1, ..., m, j = 1, ...,n, (14)

и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях:

α ≤ β. (15)

Доказательство. По определению (3) показателей эффективности α_i стратегий А_i игрока А и определению (9) показателей неэффективности β_j стратегий B_j игрока В имеем

следовательно, неравенства (14) доказаны.

Так как доказанное неравенство α_i ≤ β_j справедливо для любых i = 1, ..., т, j =1, ..., п, то оно будет справедливым в частности для номеров i = i₀ и j = j₀ соответственно максиминной и минимаксной стратегий и :

Тогда в силу (6) и (12) получим требуемое неравенство (15).