2. Приведенная форма

Основные вопросы, которые мы разбирали в теории игр n лиц, — это, как было сказано выше, вопросы о том, насколько сильны будут стремления игроков образовывать коалиции и какие взносы игроки должны уплачивать друг другу при вступлении в данную коалицию. Если две игры не различаются в этом отношении (хотя бы их платежные функции и характеристические функции и были различны), то с нашей точки зрения они будут по существу одинаковы. Уместно дать какое-нибудь название такому соотношению между двумя играми; мы назовем это соотношение стратегической эквивалентностью.

Конечно, понятие стратегической эквивалентности есть лишь интуитивное понятие без какого-либо математического содержания, ибо оно основано на таких понятиях, как «стремление к образовании? коалиции», которые сами не были определены математически. Но, очевидно, это понятие чрезвычайно важно для нашей цели, и одна из основных задач теории игр — найти для него точное математическое определение. Можно привести приемлемые интуитивные доводы, которые покажут, что некоторые условия достаточны для стратегической эквивалентности; мы сделаем это в следующих абзацах.

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

Допустим, далее, что существует положительное число k, такое, что для , и для любого элемента из декартового произведения множеств

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

Другое достаточное условие мы получим, заменив условие (16) нижеследующим: существует чисел таких, что

и для и для любого элемента из декартового произведения множеств

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

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

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

Определение 15.5. Пусть Г и — две игры лиц с нулевой суммой, в которых выборы производятся соответственно из множеств и платежные функции суть соответственно Игры Г и Г' называются S-эквивалентными, если существуют функции действительные числа и действительное положительное число удовлетворяющие следующим условиям:

1)

2) отображает взаимно однозначным образом на .

3) Для и для любого элемента декартова произведения множеств

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

Теорема 15.6. Соотношение S-эквивалентности рефлексивно, симметрично и транзитивно.

Теорема 15.7. Если Г и - две игры лиц с нулевой суммой, которые S-эквивалентны относительно констант и к и если v и — характеристические функции игр Г и Г соответственно, то для любого подмножества Т множества N

В силу теоремы 15.7 две характеристические функции v и называются S-эквивалентными, если они удовлетворяют уравнению этой теоремы, то есть если имеется положительная константа к и константы (при такие, что для всякого подмножества Т множества N

Согласно теореме 15.6 соотношение S-эквивалентности разбивает класс всех игр лиц с нулевой суммой на цепересекающиеся классы такие, что любые два элемента одного класса S-эквивалентны, а элементы разных классов не S-эквивалентны.

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

Определение 15.8. Игра лиц с характеристической функцией v называется игрой в приведенной форме, если

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

Теорема 15.9. Если v — характеристическая функция в приведенной форме с модулем у и если Т — подмножество множества N, содержащее элементов, то

Доказательство. Из условия (2) леммы 15.2 мы видим, что

и, следовательно,

Так как неравенство (18) справедливо для любого Т, то мы можем заменить в нем Т на —Т; поскольку —Т содержит элементов, мы получаем отсюда, что

Из (19) мы заключаем, на основании условия (2) теоремы 15.1, что

и, следовательно,

Уравнения (18) и (20) совместно и выражают указанную теорему.

Следствие 15.10. Если v есть характеристическая функция в приведенной форме с модулем 0, то для всякого подмножества Т множества N

В самом деле, на основании теоремы 15.9 мы имеем:

откуда

что и требовалось доказать.

Теорема. 15.11 Если v и суть S-эквивалентные характеристические функции в приведенной форме, то для всякого подмножества Т множества N

Доказательство. Пусть модули функций v и равны соответственно и Поскольку v и S-эквивалентны, то существует положительное число к и числа сумма которых равна 0, такие, что для всякого подмножества Т множества N

В частности,

Складывая все уравнения системы (22), мы получаем:

и, следовательно, поскольку обе функции в приведенной форме,

Итак,

и, кроме того, и либо оба равны нулю, либо оба равны —1. Если оба равны нулю, то на основании следствия 15.10 мы имеем для всякого Т

Если оба модуля равны — 1, то k = 1, и, следовательно, из (22) мы имеем:

так что (для ) таким образом, из (21). мы имеем для любого Т

что завершает доказательство.

Теорема 15.12. Всякая характеристическая функция S-эквивалентна одной и только одной характеристической функции в приведенной форме.

Доказательство. Пусть - характеристическая функция. Чтобы показать, что v S-эквивалентна характеристической функции в приведенной форме, мы будем различать два случая, соответственно для или .

В первом случае мы берем . Тогда

Далее, по теореме 15.7 характеристическая функция у, -эквивалентная функции у относительно этих констант, удовлетворяет для условию

Если мы берем:

и для

Тогда

И

Тот факт, что характеристическая функция не S-эквивалентна двум различным характеристическим функциям в приведенной форме, вытекает из теоремы 15.11 и из того, что соотношение S-эквивалентности транзитивно.

Замечание 15.13. Из теорем 15.12 и 15.7 следует, что для того чтобы дать надлежащую теорию всех игр лиц с нулевой суммой, достаточно рассмотреть лишь игры в приведенной форме.

Следствие 15.10 показывает, что игры в приведенной форме с модулем 0 резко отличаются от игр с модулем — 1. Действительно, из 15.10 мы видим, что когда модуль равен 0, любое множество игроков получает 0; итак, в такой игре нет смысла образовывать коалиции, и не может бытьречи о побочных платежах для того, чтобы побудить игрока вступить в коалицию; следовательно, для таких игр не нужно никакой особой теории. Поэтому мы можем впредь ограничиться играми в приведенной форме с модулем — 1. Мы будем называть такие игры существенными, в отличие от игр с модулем 0, которые будут называться несущественными.

Игры не в приведенной форме мы называем существенными или несущественными в зависимости от того, являются ли они S-эквивалентными существенным или несущественным играм в приведенной форме.

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

Теорема 15.14. Игра несущественна тогда и только тогда, когда ее характеристическая функция v удовлетворяет условию

Теорема 15.15. Игра несущественна тогда и только тогда, когда ее характеристическая функция v такая, что если мы имеем:

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

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

и, следовательно, на основании условия (2) теоремы 15.1

поскольку мы имеем также

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

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

Если v — характеристическая функция существенной игры лиц в приведенной форме, то мы сразу видим, что

Итак, значение функции v(Т) определено, за исключением случая, когда Т содержит два элемента. Но в силу того, что

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

Далее, по теореме 15.9 мы видим, что если Т есть любое множество с двумя элементами, то

Итак, если мы положим

то мы будем иметь

и

Далее, легко убедиться, что если — любые числа, удовлетворяющие соотношению (26), и если мы определяем v (Т) соотношениями (23), (24) и (25), то и есть характеристическая функция существенной игры четырех лиц в приведенной форме. Для этого необходимо лишь показать, что функция и, определенная таким образом, удовлетворяет условиям теоремы 15.1.

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

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

Пример 15.16. Игра, называемая «один лишний», проводится следующим образом: каждый из игроков (их всего три) пишет на листке бумаги «герб» или «решка».

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

Таким образом, если и -платежные функции для трех игроков и если обозначим «герб» как «1», а «решку» как «2», то

и аналогично для .

Предположим теперь, что игроки 2 и 3 составляют коалицию против игрока 1. Игрок 1 имеет, очевидно, лишь две стратегии: он может выбрать 1 или 2. Коалиция {2, 3} имеет четыре стратегии: оба игрока могут выбрать 1; оба игрока могут выбрать 2; игрок 2 выбирает 1, а игрок 3 выбирает 2; игрок 2 выбирает 2, а игрок 3 выбирает 1. Из определения функции мы легко можем вычислить платежную матрицу игрока 1 для различных выбранных стратегий. Так, если, например, игрок 1 выбирает 1, а коалиция {2, 3} выбирает , то поскольку , выигрыш игрока 1 будет равен 1. Полной матрицей будет матрица 1.

Матрица 1

Поскольку второй и третий столбцы матрицы 1 превосходят первый, мы видим, что если коалиция {2, 3} хочет применять оптимальную стратегию, то игроки не будут никогда применять стратегии . Решая матрицу, мы находим, что цена игры (для игрока 1) равна — 1. Итак,

и, следовательно,

Из симметрии мы заключаем, что

и

Далее (как и для любой игры трех лиц с нулевой суммой)

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

Библиографические замечания

Материал этой главы можно найти главным образом у фон Неймана и Моргенштерна [92]. Полный разбор S-эквивалентности есть у Мак-Кинси [74].