История развития теории игр в России

 

2. ВТОРОЙ ЭТАП РАЗВИТИЯ ТЕОРИИ ИГР

Рассматривая монографию Дж. фон Неймана и О. Моргенштерна, Н.Н. Воробьев приводит ряд замечаний «теоретико-игрового» и «общеметодологического» характера по каждой главе.

Постановка  экономической проблемы

Исходя из названия монографии «Теория игр и экономическое  поведение», может сложиться впечатление, что работа посвящена приложению методов теории игр к экономике, однако, работа носит чисто математический характер. Как отмечает в своей  статье Воробьев, экономика в монографии присутствует в таком виде, при  котором экономические явления становятся просто наблюдаемыми фактами, а упоминающиеся в книге экономические термины (монополия, дуополия и т.д.) рассматриваются не с точки зрения экономических явлений, а как «определенные варианты столкновения противоречивых интересов». [10]

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

Бескоалиционные игры

В монографии приводится определение  стратегической игры, которое ввел Джон фон Нейман в одной из своих  статей, впоследствии получивших название бескоалиционных игр. Цель каждого  участника такой игры авторы монографии определяют как получение индивидуального  выигрыша, даже в случае объединения  игроков. Однако, как отмечает Воробьев, в экономической и социальной действительности нередко полученный коалицией выигрыш не подлежит дальнейшему распределению между участниками. Также в монографии предполагается конечность множества игроков. Игры с бесконечным множеством участников рассмотрены в работах Шепли, Дэвиса, Калиша и Неринга.

В качестве еще одного вида бескоалиционных игр автор приводит антагонистические игры. [10] Антагонистической игрой называется некооперативная игра, в которой участвуют два игрока, выигрыши которых противоположны. Простейшим примером антагонистической игры является игра «Орлянка». Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает — он платит первому одну денежную единицу, если угадывает — первый платит ему одну денежную единицу. [8] При этом он замечает, что антагонизм в математическом смысле существенно отличается от его философского понятия, что необходимо учитывать при моделировании адекватных социальных, военных и других видов реальных конфликтов. Оптимальным принципом поведения в антагонистической игре, Нейман и Моргенштерн называют принцип максимина (минимакса). [10]

Кооперативные игры

В отличие от антагонистических  игр, где игрок некоторым способом поведения обеспечивает себе уверенный  выигрыш, в кооперативных играх  игрок получает определенный ему  теорией выигрыш лишь при определенном поведении других участников игры. Основным понятием в кооперативной  теории Воробьев называет понятие характеристической функции, определенной на множестве  всех коалиций, а основной задачей  –«формализация перехода от заданных возможностей каждой коалиции к индивидуальным возможностям игроков». Таким образом, возникает задача построения таких дележей, которые были бы справедливыми с точки зрения системы аксиом, предложенных Нейманом и Моргенштерном в монографии. Однако такая постановка вопроса не дает возможности для исчерпывающего анализа игры. Эту проблему решил Шепли, предложив свою систему аксиом. [10]

 

3. ТРЕТИЙ ЭТАП РАЗВИТИЯ ТЕОРИИ ИГР

В третьей главе своей  статьи Воробьев Н.Н. рассматривает  наиболее типичные результаты, полученные в области основных направлений  теории игр. 

Матричные игры

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

В качестве второго способа  называется построение алгоритмов нахождения решений для произвольных матричных  игр и называет создателей первых алгоритмов такого типа - Шепли и  Сноу.

Еще один  метод решения матричных игр основан на дифференциальных уравнениях. Он был предложен Брауном и фон Нейманом. Также Воробьев упоминает о методе последовательных приближений, предложенный Брауном и строго обоснованный Дж. Робинсоном.

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

Эквивалентность пары двойственных задач и матричной игры доказывается в теореме Данцига и Брауна. Значимость этой теоремы состоит  в том, что для решения матричных  игр можно применять все методы, разработанные для решения задач  линейного программирования. В частности, для нахождения оптимальных стратегий  в матричных играх можно использовать симплекс-метод. [10] 

Бесконечные антагонистические игры

Бесконечная антагонистическая  игра задается как тройка (А,B,H), где А и В представляют из себя множества стратегий двух игроков, Н – функции выигрыша на произведении этих двух множеств. Тогда, используя максиминный принцип, можно найти множество равноценных решений, в связи с чем возникает вопрос побочного принципа оптимального поведения. В качестве примера Воробьев приводит принцип наилучшего использования ошибок противника, предложенный Баком и Хейбертс.

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

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

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

.

Свойства таких игр  изучали Дрешер, Карлин и Шепли.

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

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

Кооперативная теория

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

Как замечает Воробьев, кооперативная  теория была разработана Нейманом и  Моргенштерном особенно тщательно. Однако дальнейшее развитие этой теории встретило ряд трудностей на своем  пути. Автор статьи указывает три  причины, по которым кооперативная  теория замедлила свое развитие после  выхода в свет монографии.

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

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

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

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

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

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

Переход от классической кооперативной  теории к теории без побочных платежей рассматривает в своих работах  Ауман. Целесообразность такого перехода обусловлена тем, что возможности игр без побочных платежей существенно шире. Однако и для классической теории и для теории без побочных платежей существенным является вопрос о выборе из множества дележей, принадлежащих решению игры, единственного, удовлетворяющего понятиям «справедливости». Работы в этом направлении вели Шепли и Ауман. [10]

Бескоалиционные игры

В общем виде бескоалиционная  игра задается следующим образом:

Где I - это множество всех игроков,   - множество всех стратегий i-го игрока,  - функция выигрыша i-го участника.

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

Однако, как замечает Воробьев, встречаются случаи, когда получившиеся ситуации равновесия оказываются «неравноправными»  друг относительно друга. Такая ситуация разрешается переговорами между  участниками.

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

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

Позиционные игры

В своей статье Воробьев, рассматривая позиционные игры, говорит  о том, что после появления  монографии Неймана и Моргенштерна, данный класс игр был представлен  всего лишь «громоздкой системой определений» и теоремой об играх  с полной информацией. В связи  с чем, автор статьи обращает особое внимание на работы Куна, в которых  было сформулировано «естественное  и прозрачное» определение позиционной  игры и выяснена суть той неопределенности, с которой сталкивается игрок, в  игре в позиционной форме.

Интересным является тот  факт, что в позиционной игре, участники могут сравнивать свои выигрыши, лишь находясь в последней  позиции игры, то есть по ее окончанию. Однако Воробьев указывает на то, что  переход от позиции к позиции  может давать игроку промежуточные  выигрыши, утрачиваемые в дальнейшем. В связи с чем, возникает вид  игр,  в которых «непосредственная борьба ведется за те или иные позиции игры». В качестве примера он приводит работы М.М. Ботвинника применительно к шахматам и  схему «рекурсивной игры», предложенную Эвереттом.