2.2. Минимаксы

Итак, при задании антагонистической игры нет необходимости указывать функции выигрыша обеих игроков. свою стратегию Ь Тогда в на«-

В условиях антагонистической игры, как и в случае произвольной игры, разумные игроки должны стремиться к ситуациям равновесия. Применительно к антагонистическим играм сформулированные в разделе «Цели игроков и их осуществление» условия равновесности ситуации (x*, y*) можно записать так:

H(x*,y*)>=H(x,y*),

H(x*,y*)>=H(x*,y)

(В рассматриваемом случае Н = Н_] = — Н₂).

Антагонистическую игру можно интерпретировать как выбор точки на некоторой местности, причем игрок I выбирает географическую её широту, а игрок II – долготу, а значением функции выигрыша является высота выбранной точки над уровнем моря. Если на нашей местности имеется возвышающаяся над остальной поверхностью горная цепь, тянущаяся в широтном направлении, а в этой горной цепи – сравнительно низкий перевал, то этот перевал («седло») будет соответствовать ситуации равновесия в этой игре. В связи с возможностью такой интерпретации, ситуации равновесия в антагонистических играх часто называют седловыми точками.

То есть, при правильной игре игрок I может получить не меньше, чем наименьший из максимумов в столбцах матрицы. При правильной игре игрока II игрок I получит не больше, чем наибольший из минимумов в строках матрицы. Если эти элементы матрицы равны, то общее их значение является значением игры, а приводящий к нему выбор игроками строки и столбца матрицы дает седловую точку.

Определение 2.4. Ситуация (х*,…,у*) называется ситуацией равновесия в чистых стратегиях, если для лю­бых х х и уу выполнено двойное неравенство

H(x,y*)≤ H(x*,y*)≤ H(x,y*), (2.8)

где х*, у* — соответственно максиминная и минимаксная чистые стратегии игроков в случае v (Г) = (Г).

Ситуация равновесия приемлема для каждого из иг­роков, ибо, как видно из (2.8), ни одному из них не вы­годно отклоняться от этой ситуации. В этом смысле ситуация равновесия является устойчивой. Если каждый из игроков стремится достичь ситуации равновесия, то принцип, которому они следуют, называют принципом равновесия. В антагонистических играх, действуя соглас­но этому принципу, игрок поступает также согласно принципу максимина, рассмотренному ниже (при том очевидном условии, что этот принцип реализуем, т. е. при условии существования ситуации равновесия).

Разумное поведение игроков в антагонистической игре можно установить еще и следующими рассуждениями.

Предположим, что игрок 1 в антагонистической игре Г=[X,Y,Н] выбирает некоторую свою стратегию x. Тогда в наихудшем случае (например, если выбор игроком 1 стратегии станет известным игроку 2), он получит выигрыш . Предвидя такую возможность, игрок 1 должен выбрать свою стратегию x* таким образом, чтобы максимизировать этот свой минимальный выигрыш:

Стоящий в правой части написанного неравенства «максимин» является, таким образом, гарантированным выигрышем игрока 1.

Взглянем теперь на эту игру глазами игрока2. Пусть он выбирает некоторую свою стратегию y. Тогда в наихудшем случае его проигрыш составит . Действуя с расчётом на наименее благоприятный для себя ход событий, игрок 2 должен выбрать свою стратегию y* так, чтобы минимизировать свой максимальный проигрыш:

Стоящий справа «минимакс» является максимальным неизбежным проигрышем игрока 2. Это значит, что, действуя достаточно разумно, игрок 2 не может не дать игроку 1 выиграть больше, чем этот минимакс.

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

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

B самом деле, при любых x и y

Н(x,y) max H(x, y)

и, тем более,

Так как это равенство выполняется при любом а, оно будет справедливо и для того x, которое обращает в максимум :

Так как это неравенство, в свою очередь, имеет место при всяком y, то оно остается в силе и для такого y, кото­рое обращает в минимум:

а это и требовалось.

Если оба минимакcа равны:

(2.9)

то выигрыш игрока 1 является вполне определенным чис­лом. Игрок 1 этот выигрыш всегда может себе обеспе­чить, а большей суммы ему не позволит выиграть про­тивник. Этот точный выигрыш игрока 1 называется зна­чением игры. Участие игрока в игре означает получение им от игрока 2 именно этой суммы. Значение игры назы­вается иногда ценой игры, так как его можно понимать, как ту справедливую цену, которую игрок 1 может запла­тить за право участия в игре Г. Значение игры Г обычно обозначается через v_T или просто v.

Итак, если имеет место равенство «минимаксов» (2.9), то разумные действия обоих участников игры приведут к тому, что игрок 1 выиграет (а игрок 2 соответственно проиграет) сумму, равную значению игры Г. Но, с другой стороны, разумные действия игроков должны приводить к ситуациям равновесия. Поэтому естественно ожидать, в случае равенства минимаксов игроки, действуя указанным выше образом, осуществляют ситуацию равновесия, седловую точку.

Теорема. Для того чтобы антагонистическая игра Г=[X,Y,Н] имела седловую точку, необходимо и достаточно равенства минимаксов

Доказательство. Необходимость. Пусть (x*,y*) — одна из «седловых» точек игры Г. Это значит, что и

(2.10)

(2.11)

Неравенство (2.10) справедливо при любом значении с из X.. Следовательно, это неравенство выполняется и для того x, при котором Н(x,y*) принимает максимальное значение:

(2.12)

Далее, зависит от y, являясь тем самым функцией y. Одним из значений этой функции является . Это значение, очевидно, не меньше, чем наименьшее значение рассматриваемой функции:

. (2.13)

Вместе с (2.12) это дает нам

(2.14)

Аналогичные рассуждения, связанные с неравенством (2.11), дают нам

(2.15)

Из (2.14) и (2.15) следует, что

Так как обратное неравенство установлено ранее, то

(2.16)

Достаточность доказывается совсем просто. Пусть минимум в левой части (2.16) достигается при y= y*, а максимум в правой - при x = x*. Тогда равенство (2.16) можно переписать как

.

Но тогда очевидно, что

Значит,

(2.17)

и так как

,

и равенство (10) дает нам

,

а это и требовалось.

Из всего сказанного выше следует, что если игра Г такова, что минимаксы и равны, то оптимальные действия игроков могут быть найдены без труда. Именно, игрок 1 должен выбирать такую стратегию x*, которая максимизирует выражение H (x, y), а игрок 2 —такую стратегию y*, которая минимизирует выражение .

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

Очевидно, основной задачей-1 при анализе игры является выявление ситуаций равновесия в этой игре. Поэтому ситуации равновесия игры называются ее решениями. Решением называется также и процесс нахождения ситуаций равновесия игры.

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

Для игры, заданной матрицей выигрышей H=||h_ij|| можно записать (исходя из доказанной теоремы):

max min h_ij = min max h_ij (2.18) _(1.10)

i j j i

Неравенство (2.8) можно переписать в виде

Н(i,j*)≤Н(i*,j*)≤Н(i*,j), (2.19)

где i*,j * - чистые максиминная и минимаксная страте­гии соответственно игроков I и II.

Выигрыш в ситуации равновесия (i*, j*) равен мини­муму всех элементов строки i* матрицы выигрышей игры и максимуму элементов столбца /*. Поэтому ситуацию равновесия в чистых стратегиях иногда называют седловой точкой. Нахождение ситуаций равновесия (седловых точек) может быть выполнено по следующей схеме:

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

1 2 4

3. 5

рис.2.1

** - наибольший минимум по строкам;

*** - наименьший максимум по столбцам.

Таким образом, в нашем случае

max min h_ij = min max h_ij = 0 _(1.10)

i j j i

Поэтому оптимальные стратегии игроков состоят в том, что каждый из них называет точку 4. Соответствующая ситуация равновесия отмечена на матрице звездочкой. Значение игры равно нулю.

Пример 2.2. Пусть задана матрица выигрышей игрока I

Седловой точкой является пара (i* = 3, j* = 1), при которой v = v(Г) = (Г) = 2. Заметим, что хотя выигрыш в ситуации (3, 3) также равен 2 = v(Г) = v(Г), она не является седловой точкой, так как этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2.3. Пусть задана матрица выигрышей иг­рока I

H=

Из анализа матрицы выигрышей видно, что v(Г)<(Г), т. е. данная матрица не имеет седловой точки, а игра пи имеет ситуаций равновесия в чистых стратегиях. Если теперь игрок I выбирает свою чистую максиминную стра­тегию i⁰ = 2, то игрок II, выбрав свою чистую минимакс­ную стратегию j° = 2, проигрывает только 20. В этом слу­чае игроку I выгодно выбрать стратегию i = 1, т. е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку II будет выгодно выбрать стра­тегию j = 1, т. е. отклониться от своей чистой минимакс­ной стратегии и проиграть 10. В свою очередь игрок I должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок II ответит выбором своей 2-й стратегии и т. д.

Как действовать в этом случае – рассмотрим ниже.