ГЛАВА XV. ИГРЫ n ЛИЦ С НУЛЕВОЙ СУММОЙ

1. Характеристические функции

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

К сожалению, для этого, более широкого класса игр нет теории, которая была бы интуитивно столь же приемлема, как теория игр двух лиц. Хотя большая часть книги фон Неймана и Моргенштерна [92] (примерно 400 страниц из 600) посвящена играм с числом игроков больше двух, математики в основном, по-видимому, не удовлетворены теорией, изложенной в этой книге. За последние несколько лет по этому разделу теории игр было проведено сравнительно мало исследований.

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

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

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

Поскольку игра имеет нулевую сумму, функции удовлетворяют (тождественно по ) равенству

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

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

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

Мы будем обозначать множество игроков через N, так что

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

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

Пусть . Тогда, очевидно, имеются функции такие, что

есть платеж игроку i, когда применяет стратегию и —Т применяет стратегию ; действительно, если

то

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

а общий платеж игроку —Т будет

Поскольку первоначальная игра имела нулевую сумму, то

Поскольку множество С содержит и элементов, смешанная стратегия игрока Т есть элемент множества . Аналогично, смешанная стратегия игрока — Т есть элемент множества .

Но если Т применяет смешанную стратегию и —Т применяет смешанную стратегию , то общее математическое ожидание выигрыша для Т равно

а общее математическое ожидание выигрыша для —Т равно

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

Поскольку для всех , то очевидно, что

На основании теории прямоугольных игр двух лиц мы заключаем:

Полагаем

Итак, мы имеем функцию v, определенную для всякого подмножества Т множества N и значение которой представляет для любого Т общую сумму, которую могут надеяться получить члены множества Т, если они составят коалицию; мы называем и характеристической функцией игры. Ввиду того, что платеж переносим, мы вправе предполагать, что все вопросы относительно коалиции и побочных платежей можно решить на основании одной лишь характеристической функции; например, если плата игроку за присоединение к некоторой коалиции в данной игре равна , то она будет точно так же равна я в любой другой игре с такой же характеристической функцией. Этот вопрос, очевидно, мог быть разрешен определенно, если бы мы могли дать надлежащую теорию игр лиц только на основе характеристических функций. Фон Нейман и Моргенштерн полагают, что им это удалось сделать.

Мы установим теперь некоторые математические свойства характеристических функций.

Теорема 15.1. Пусть v — характеристическая функция игры n лиц с нулевой суммой, где N — множество игроков. Тогда

(1)

(2) для любого подмножества Т множества N мы имеем ;

(3) если R и Т — непересекающиеся подмножества множества N, то

Доказательство. Для доказательства (1) разделим игроков множества N на две коалиции N и , тогда не существует стратегий для второй коалиции (пустого множества игроков), а стратегия (чистая) первой коалиции есть упорядоченный n-мерный вектор , где . Следовательно, каждая из функций есть функция одного лишь элемента множества С. Итак, для любой стратегии А выбранной коалицией N, общий платеж коалиции N (ввиду того, что первоначальная игра имела нулевую сумму) равен

Отсюда непосредственно следует, что

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

Для доказательства (2) пишем:

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

Пусть стратегии (чистые) игроков 1, 2 и 3 суть соответственно

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

Смешанная стратегия игрока 1 есть вектор множества который приписывает частоту чистой стратегии аналогичные стратегии имеются у игроков 2 и 3. Смешанная стратегия коалиции {1, 2} есть вектор

множества , который приписывает частоту чистой стратегии ; аналогичные стратегии имеются у коалиций {1, 3} и {2, 3}.

Пусть — элемент множества такой

Пусть — элемент множества такой

Легко убедиться, что вектор

принадлежит множеству . Поэтому имеем:

Поскольку минимальное значение суммы двух функпнй не меньше суммы их минимальных значений, мы заключаем из (4), что

Пусть теперь — элемент множества - такой, что

и пусть — элемент множества такой, что

Из (5), (6) и (7) мы получаем:

Поскольку мы заключаем, что вектор

принадлежит множеству Следовательно,

Из (2) и (9) мы заключаем, что

Так же заключаем, что

Наконец, из (8), (9) и (11) мы видим, что

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

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

Лемма 15.2. Пусть N — некоторое множество и — действительная функция, определенная для всякого подмножества Т множества N и удовлетворяющая условиям теоремы 15.1. Тогда

(1)

(2) если — непересекающиеся подмножества множества N, то

(3) если — непересешющиеся подмножества множества N, сумма которых есть N, то

Доказательство. Утверждение (1) вытекаем непо средственно из условий (1) и (2) теоремы 15.1, ибо

Утверждение (2) выводится из условия (3) теоремы 15.1 индукцией по . Утверждение (3) вытекает из утверждения (2) и условия (1) теоремы 15.1, ибо

Теперь мы можем доказать упомянутую выше теорему, обратную теореме 15.1.

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

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

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

Подмножество Т множества N называется характерным (по отношению к данной партии игры), если либо

(а) ТЗС для всякого х в Т, либо

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

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

Предположим теперь, что для данной партии игры характерные подмножества множества N суть и что содержит элементов. Тогда, если игрок принадлежит множеству то выигрыш его определяется так:

где — данная функция.

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

Сумма выигрышей всех членов множества N равна, следовательно

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

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

Мы покажем сначала, что для всякого подмножества Т множества N

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

и, следовательно, общий выигрыш членов множества Т равен

Поскольку члены множества Т могут гарантировать себе, что они получат по меньшей мере

мы заключаем, что

Из условия (3) леммы 15.2 мы видим, что

Из (12) и (13) с учетом положительности мы заключаем, что

Поскольку (14) справедливо для всех подмножеств Т множества N, то оно остается справедливым после замены Т на —Т. Итак,

На основании условия (2) теоремы 15.1 из этого вытекает

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

Из (14) и (15) мы заключаем, что

Это завершает доказательство теоремы.

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