ГЛАВА VI. ОБЩАЯ ТЕОРИЯ ИГР В РАЗВЕРНУТОЙ ФОРМЕ

1. Общее определение конечных игр

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

Итак, мы будем рассматривать конечную игру n лиц как систему, состоящую из следующих частей:

1. Дерево Т (в том смысле, как было объяснено в главе V).

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

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

4. Каждой точке q разветвления дерева Г, которой, согласно пункту 3, ставится в соответствие число О, соответствует элемент множества . Здесь есть число альтернатив в точке , то есть число прямых, выходящих из q.

5. Разбиения точек разветвления на непересекающиеся и полные множества (информационные множества), удовлетворяющие следующим условиям:

а) Все точки разветвления, принадлежащие данному информационному множеству, относятся, согласно пункту 3, к одному игроку.

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

в) Если (см. пункт 3) точке разветвления q поставлено в соответствие число 0, то информационное множество, в котором находится , состоит только из этой точки.

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

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

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

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

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

Рис. 23

Стратегией игрока является функция F, определенная для и такая, что

Если мы говорим, что выбирает, например, следующую стратегию:

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

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

Если выбор является случайным; то вероятность определяется согласно пункту 4 определения игры. Мы обозначаем эти вероятности через , где есть упорядоченное множество стратегий, которые применяют игроки, — точка разветвления, a i — альтернатива.

Так, предположим, что в игре, изображенной на рис. применяет стратегию :

а применяет стратегию :

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

Однако для некоторых целей направление партии после выбора лучше обозначать указанием не числа альтернатив, а вершины, к которым приведет этот выбор. Так, на рис. 23 первая альтернатива для точки может привести к одной из вершин вторая альтернатива — к одной из вершин , а третья альтернатива — к одной из вершин .

Первая альтернатива для точки может привести к или а вторая альтернатива — к или .

Символом , где — упорядоченное множество стратегий, — точка разветвления и t — вершина, мы будем обозначать вероятность того, что после того, как в партии достигнута точка разветвления q, партия будет продолжаться по пути, который окончится в t. Так, для игры, изображенной на рис. 23, вместо того чтобы писать

мы можем написать

или

и т. д. Вместо того чтобы писать

мы можем написать

или

Применяя это обозначение, мы, конечно, также получим , когда t не является конечной точкой партии, проходящей через q. Так, например, для для игры, изображенной на рис. 23, мы получим

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

Тогда если положить

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

Аналогично

Для проверки мы замечаем, что

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

Тогда математическое ожидание выигрыша игрока выражается формулой

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

Тогда для упорядоченного множества стратегий а, рассмотренного выше, мы имеем

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

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

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

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

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