2. Игры с полной информацией. Точки равновесия

Обратимся теперь к играм особого рода — к так называемым играм с «прлной информацией». Эти игры характеризуются тем, что во всякой точке в любой партии игрок, чья очередь делать ход, точно знает, какие выборы были сделаны раньше. По отношению к диаграмме игры это значит, что любое информационное множество состоит из одного элемента. Так, например, игра, изображенная на рис. 24, есть игра с полной информацией.

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

Учащийся сам может распознать, какие из обычных салонных игр являются играми с полной информацией. Таковы, например, тик-так-ту, шашки, шахматы и трик-трак.

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

Рис. 24.

Мы покажем теперь, что матрица любой игры в нормальной форме двух лиц с нулевой суммой и полной информацией имеет седловую точку, то есть в такой игре есть оптимальные чистые стратегии.

Рис. 25.

Для такой простой игры, как тик-так-ту, это, конечно, известно каждому, кто когда-нибудь играл в эту игру хоть несколько раз. Каждый игрок в тик-так-ту может играть таким образом, что он выиграет (если другой игрок будет играть неправильно) или добьется ничьей.

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

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

Пусть платежные функции стратегии игры лиц суть , множество чистых стратегий игрока есть и А — декартово произведение множеств . Мы говорим, что элемент множества А есть точка равновесия, если для каждого i и для любого элемента у множества

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

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

Но поскольку игра имеет нулевую сумму, мы имеем:

поэтому из второго неравенства, написанного выше, мы заключаем, что

или

Отсюда мы получаем:

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

Рис 26.

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

Чтобы провести наше доказательство, удобно ввести цоцятие усечения игры с полной информацией.

Мы под разумеваем под этим игру, которая получается из данной исключением первого хода. Так, предположим, что игра имеет диаграмму, показанную на рис. 26, и платежная функция для выражается действительной функцией определенной в точках .

Рис. 27.

Рис. 28.

Тогда имеются три усечения этой игры, соответствующие трем альтернативам при первом ходе. Их диаграммы приведены на рис. 27, 28, 29. Платежные функции для этих усеченных игр суть лервоначальные платежные функции, но их области определения соответственно ограничены. Так, платежная функция для игры, изображенной на рис. 27, есть функция определенная в точках и такая, что для .

(Нужно заметить, что такой способ образования усеченных игр возможен потому, что игра является игрой с полной информацией. Если бы мы попытались определить усечения для такой игры, как, например, игра, изображенная на рис. 23, то перед нами возникла бы задача разделить каким-нибудь образом информационные множества и .

Рис. 29.

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

Теорема 6.1. Пусть — множества стратегий, имеющихся у в игре двух лиц с полной информацией, и пусть — их декартово произведение. Тогда А имеет точку равновесия.

Доказательство. Мы докажем теорему индукцией по длине игры, то есть по числу точек разветвления в самой длинной возможной партии игры.

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

Мы предполагаем, что теорема справедлива для всех игр длины меньше к; пусть Г — игра длиной к. Предположим, что для первого хода имеются альтернатив, и пусть усечений игры Г (они существуют потому, что игра Г есть игра с полной информацией).

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

По условию индукции, имеется точка равновесия в каждом из множеств . Пусть для каждого i есть точка равновесия множества Тогда, обозначив платежные функции стратегий в игре Г через имеем:

для для любого из и для любого из .

Мы будем различать три случая: 1) первый ход игры Г случайный, 2) первый ход игры Г делает и 3) первый ход игры Г делает .

Случай 1. Если q есть точка разветвления одной из усеченных игр , соответствующая ходу, который делает то мы полагаем

Аналогично, если q есть точка разветвления одной из усеченных игр , соответствующая ходу игрока , мы полагаем

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

Аналогично, g есть элемент множества Мы хотим показать, что точка находящаяся, таким образом, в А, есть точка равновесия множества А.

Пусть альтернативам при первом ходе назначены вероятности так что и .

Пусть — платежные функции стратегий в игре Г Соответственно для Тогда очевидно, что если и g — любые стратегии игроков в игре Г и если и — усечения этих стратегий для усеченной игры то

В частности, поскольку стратегии суть усечения стратегии суть усечения стратегии g, мы имеем:

и

Из неравенств (1), с учетом неотрицательности всех , выводим:

Подставляя (2) и (3) в (4), получаем:

так что пара действительно есть точка равновесия игры Г, что и требовалось доказать.

Случай 2. В этом случае первый ход игры Г делает Множество чисел

конечно и, следовательно, имеет максимум. Пусть целое число таково, что

Определим функцию , положив

а если — точка одной из усеченных игр соответствующая ходу, который делает то

Мы определяем функцию g точно так же, как в первом случае, то есть если q — точка одной из усеченных игр , соответствующая ходу, который делает , то мы полагаем

Очевидно, и суть стратегии соответственно для в игре Г. Мы хотим показать, что есть точка равновесия множества А. Из равенства (6) мы видим, что если g есть любая стратегия игрока в Г и если есть ее усечение для игры Г, то

и

Из равенств (7) и (8), поскольку g? есть усечение стратегии g для игры мы получаем, в частности,

и

Итак, если g есть любая стратегия игрока в Г и если g есть ее усечение для игры , то мы видим из равенства (10), из второго неравенства (1) и из равенства (8), что

Пусть теперь f - любая стратегия игрока в Г. Предположим, что выбирает альтернативу на первом ходу, то есть

Пусть -усечение стратегии для Тогда мы видим, что если g есть любая стратегия игрока есть ее усечение для игры Г, то

в частности,

Из равенства (5) мы имеем:

Из (9), (13), первого неравенства (1) и из (12) мы заключаем, что

Из (11) и (14) мы видим, что есть точка равновесия игры Г, что и требовалось доказать.

Случай 3 аналогичен случаю 2.

Теорема доказана.

Следствие 6.2. Матрица любой игры в нормальной форме двух лиц с нулевой суммой и полной информацией имеет седловую точку.

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

Замечание 6.3. Теорему 6.1 можно столь же легко доказать для игр n лиц, но обозначения будут несколько сложнее. Это расширение теоремы мы оставляем в качестве упражнения.

Мы определили точки равновесия только среди множеств чистых стратегий. Однако можно, очевидно, определить точки равновесия также среди смешанных стратегий. Действительно, можно доказать, что всякая игра n лиц имеет точку равновесия в множестве смешанных стратегий. Этому факту большое значение придают те, кто лелеет надежду построить всю теорию рационального способа игры в играх n лиц на понятии точки равновесия. Не принимая полностью эту точку зрения, мы можем, по крайней мере, сделать следующее замечание. Когда группа лиц часто и в течение долгого времени играет в некоторую игру, они иногда приобретают привычку выбирать точку равновесия. Если кто-нибудь играет в эту игру с членами данной группы, самое лучшее для него — самому выбрать точку равновесия. Таким образом, точка равновесия представляет, так сказать, принятую норму поведения для группы: нарушающий соглашение рискует проиграть, если ему не удастся убедить и других нарушить соглашение.