По существу, к бескоалиционным играм относится теория справедливого дележа, выросшая из старинной задачи о разделе имущества, проводимого по принципу «один делит - другой выбирает». Впервые с теоретико-игровой точки зрения к этой задаче подошел Штейнгауз (см. сообщения Кнастера и Штейнгауза [1]). Последние результаты в этом направлении содержатся в статье Куна [3].
7. Каждой игре присущ некоторый набор полезностей, за обладание которыми ведут борьбу игроки. В классической кооперативной теории (с трансферабельной полезностью) такая полезность была единой для всех игроков. В теории бескоалиционных игр этих полезностей имеется ровно столько, сколько игроков, и каждый игрок имеет свою собственную полезность, описываемую его функцией выигрыша. Естественное и вполне актуальное обобщение, допускающее разнообразные интерпретации, состоит в том, что каждому виду полезности, фигурирующему в качестве целей игроков, соответствует некоторое (очевидно, непустое) множество игроков, причем один игрок может, вообще говоря, быть заинтересованным в различных полезностях. Множество всех игроков, ведущих борьбу в направлении максимизации одной и той же полезности, является коалицией (именно коалицией интересов). Выигрыш каждой коалиции считается принадлежащим ей как таковой и не подлежащим какому-либо разделению между членами коалиции. Ясно, что различные коалиции могут и пересекаться.
Наряду с коалициями интересов в играх встречаются еще и коалиции действия, участники которых могут обмениваться информацией по выбору совместной коалиционной стратегии и, в частности, предпринимать коррелированные рандомизированные действия. Рассмотрение таких совместных рандомизированных действий пересекающихся коалиций осложняется тем, что действия различных групп игроков должны быть согласованными, а это может оказаться препятствием к вероятностной интерпретации смешанных действий. Поэтому «комплекс коалиций» не может быть произвольным, а должен подчиняться некоторым комбинаторным условиям.
Естественное распространение принципа осуществимости цели на коалиционные игры приводит к рассмотрению устойчивых ситуаций, в которых некоторые группы игроков не заинтересованы в отклонении от своих запланированных действий, даже если те или иные их партнеры по коалициям нарушат свои первоначально взятые обязательства.
В частности, если правилами игры не предусмотрена какая-либо «реакция» игроков на нарушения обязательств их партнеров по коалициям, т. е. если игра фактически превращается в бескоалиционную, то описанные устойчивые ситуации превращаются в равновесные ситуации в смысле Нэша (см. III.4.1).
Существование такого рода, устойчивых ситуаций доказано в статье Н. Н. Воробьева [5].
§ 5. ДИНАМИЧЕСКИЕ ИГРЫ
1. Использование смешанных стратегий в качестве оптимальных решений, распространение теоремы о минимаксах н8 различные классы бесконечных игр, связь матричных игр с линейным программированием - все это на первых порах заслонило, быть может, даже более глубокие идеи, содержащиеся в монографии фон Неймана и Моргенштерна: теорщо позиционных игр и кооперативную теорию. Достаточно сказать, что до появления в 1953 г. сборника [3] к этим вопросам никто не возвращался.
(Больше того, в относящейся к 1950 г. книге Вальда «Статистические решающие функции» теоретико-игровая сторона вопроса была представлена играми в нормальной форме, несмотря на всю «позиционность» проблемы по существу.)
Заметим сразу же, что эти вопросы после выхода в свет монографии фон Неймана и Моргенштерна находились в совершенно различных состояниях. Кооперативная теория была разработана весьма глубоко: ее результаты касались узловых вопросов теории, а некоторые частные случаи были разобраны с исчерпывающей подробностью. Теория же позиционных игр ограничивалась громоздкой системой определений да теоремой об играх с полной информацией (известной к тому же в своих основных чертах со времен работы Цермело [1] о шахматах).
2. Тем больший интерес представляет работа Куна [1]. Прежде всего, в ней было сформулировано естественное и прозрачное определение позиционной игры, в том числе четко определены стратегии игроков как функции на множествах их информационных состояний (а содержательно - на семействах множеств позиций, неразличимых для игрока в соответствующий момент; эти множества позиций называются информационными множествами). Кроме того, в этой работе было выяснено «внутреннее» строение той неопределенности, с которой приходится иметь дело игроку в позиционной игре. В качестве такого «атома» неопределенности Кун выбирает факт перекрывания одним информационным множеством другого. Содержательно перекрывание информационным множеством V информационного множества U означает, что находящийся в множестве U игрок не знает одновременно, находилась ли ранее игра в множестве U и какое решение было в U принято (очевидно, тем из игроков, чья очередь хода была в U). Очевидно, в играх с полной информацией, в которых каждое информационное множество состоит из единственной позиции, никакие информационные множества друг друга не перекрывают.
3. Чем «больше» перекрываний имеется среди информационных множеств в игре, тем «большим» оказывается, вообще говоря, необходимое смешивание в оптимальных (или, если речь идет об общих бескоалиционных играх, в равновесных) стратегиях. Так, если игрок имеет полную память, т. е. если его собственные информационные множества не перекрывают друг друга, то игрок может ограничиться стратегиями поведения, т. е. такими смешанными стратегиями, в которых его действия смешиваются в различных информационных множествах независимо. Дальнейшее развитие этих идей содержится в статьях Томпсона [1] и Н. Н. Воробьева [2, 6].
В каждой позиционной игре существенную роль играет множество позиций с указанием возможных переходов от одних позиций к другим, т. е. некоторый объект, изучаемый теорией графов. Систематическое рассмотрение комбинаторного аспекта в позиционных играх заставляет применять терминологию и методы теории графов. Весьма большое число результатов теории игр было изложено с этих позиций Бержем в его книге [1].
Расщепление информационного множества на более мелкие информационные множества содержательно означает увеличение информации, которой располагают игроки, а формально - расширение множества их стратегий. В частности, при полном расщеплении информационных множеств до однопозиционных в полученном расширенном множестве стратегий будут содержаться оптимальные (соответственно равновесные) стратегии. Ясно, что полное расщепление для существования чистых
оптимальных стратегий является достаточным, но не необходимым. Необходимые условия такого расщепления были указаны Берчем [1].
В идущей от статьи Куна [1] теории позиционных игр принимается, что информационные множества не должны «предшествовать сами себе», т. е. что игрок не должен на протяжении одной партии принимать дважды решение в одном и том же информационном состоянии. Это ограничение представляется не вполне естественным и потому несколько стеснительным. Исбелл [1] положил начало теории «финитарных» игр, которые этим условием не ограничены.
4. На первый взгляд теорема о существовании ситуаций равновесия в чистых стратегиях для игр с полной информацией представляется весьма общим фактом, поддающимся широким обобщениям. Однако Гейл и Стюарт [1] привели пример позиционной игры (разумеется, бесконечной) с полной информацией, в которой игроки не имели чистых оптимальных стратегий. Этот пример показал, что теория бесконечных позиционных игр с полной информацией является весьма сложной. Дальнейшие результаты в этом направлении принадлежат Вульфу [1], Окстоби [1], Ханани [1], Э. Д. Стоц-кому [1], Дэвису [1], Мыцельскому [1] и др.
Вместе с тем весьма прямолинейное использование аксиомы выбора при построении этого примера давало основания предполагать, что он принадлежит к числу парадоксов, порождаемых применением этой аксиомы. Последовательным развитием такой точки зрения занялись Штейнгауз и Мыцельский [1]. Они приняли полную определенность антагонистической игры с полной информацией за самостоятельную аксиому теории множеств (в ее абстрактной формулировке, очевидно, можно обойтись без теоретико-игровой терминологии), назвав ее аксиомой определенности. Интуитивный смысл этой аксиомы состоит в том, что для абсолютно осведомленных в правилах и тонкостях игры участников исход партии предопределен. Такая игра должна по существу быть чисто комбинаторной. Ясно, что аксиома определенности противоречит примеру Гейла - Стюарта. В действительности она противоречит примененной при построении этого примера аксиоме выбора. Однако в известной мере аксиома определенности способна также и заменять аксиому выбора. Мыцельский показал [2], что большое число следствий аксиомы выбора удается доказать на основе аксиомы определенности и без использования аксиомы выбора. В частности, в его работе, написанной совместно со Сверчков-ским [1], из аксиомы определенности выводится измеримость по Лебегу любого линейного множества. Дальнейшее изучение игр с полной информацией в этом направлении было проведено Мыцельским в статье [1].
5. В позиционных играх выигрыши выплачиваются игрокам лишь в окончательных позициях партии. Поэтому, говоря формально, сравнивать между собой игроки могут только окончательные позиции. Однако (если говорить для определенности об антагонистических играх) пребывание игрока в любой позиции уже предопределяет некоторый его выигрыш, которым можно измерять ценность самой позиции. Таким образом, пере-* ход игры из позиции в позицию может означать для игроков приобретение некоторых временных преимуществ, которые вполне могут быть утрачены при дальнейшей неоптимальной игре. В связи со сказанным целесообразно рассматривать такие игры, в которых непосредственная борьба ведется за те или иные позиции игры, которые оказываются своеобразными ресурсами игроков в ходе их дальнейшей борьбы. Применительно шахматам такой подход детально развивает М. М. Ботвинник [1].