Вильямс Дж.Д. Совершенный стратег, или Букварь по ТЕОРИИ СТРАТЕГИЧЕСКИХ ИГР.
Пер. с англ. № 18. Изд. 2

Оглавление

От редактора перевода

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

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

Появление быстродействующих электронных вычислительных машин (ЭВМ), резко расширившее возможности быстрой обработки больших количеств информации, явилось, по-видимому, одной из решающих причин того, что методы точных наук, в частности численные методы, стали находить себе широкое применение в совершенно новых областях. При этом практическая ценность получаемых с помощью ЭВМ решений оказалась настолько большой, что она с лихвой окупила значительные расходы на создание и эксплуатацию машин. Однако для нормального использования ЭВМ необходимо было заботиться не только о технической, но и о математической стороне работы машины. Иначе говоря, каждая новая задача требовала строгой постановки и формулировки в терминах операций, доступных машине, требовала составления сводки правил проведения расчетов, т.е. "алгоритма" новой задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однако теория игр в ее современном состоянии не является еще законченной теорией. Ценность ее сегодня заключается главным образом "в отчетливой формулировке основных, принципиальных особенностей конфликтной ситуации, и это чрезвычайно важно для правильного подхода к задачам. Что же касается конструктивных методов решения игровых задач, то арсенал математической теории игр не может похвастать их обилием. Хорошо разработаны методы решения только одного типа игр, а именно конечных дискретных парных игр с нулевой суммой платы. Но даже для игр этого типа решение сколько-нибудь сложных игровых задач требует очень большой вычислительной работы. А в ряде задач (например, в непрерывных играх) общие методьы решения еще мало разработаны. Ценным подспорьем в решении дискретных игр в нормальной форме являются методы линейного программирования.

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

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

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

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

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

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

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

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

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

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

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

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

Предисловие

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

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

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

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

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

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

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

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

Однако боязнь кого-нибудь пропустить при перечислении (а это неизбежно, когда у тебя так много кредиторов) не может удержать меня от попытки опубликовать все мои долги. Прежде всего, неоценимую помощь в моем образовании оказали внушительные рукописи М.Э.Дрешера из РЭНД-корпорейшн и Дж. К.Маккинзи (работавшего ранее в РЭНД-корпорейшн, а затем в Стэнфордском университете), в которых суммированы десятки статей как моих коллег, так и других авторов. Я весьма признателен за отдельные идеи Р.Э.Беллману, Р.Л.Белзеру, Н.К.Долки, Дж. М.Дэнскину, У. X. Флемингу, Д.Р.Фулкерсону, Мельвину Хауснеру, Олафу Хельмеру, С.М.Джонсону, Абрахаму Каплану, А.М.Муду, Э.У.Пэксону, Э.С.Кваду, Р.Д.Шпехту и Дж.Венделю-все из РЭНД-корпорейшн, а также Э.У.Баранкину из Калифорнийского университета, Д.X. Блекуэллу из Говардского университета, С.К.Клини из Висконсинского университета, Оскару Моргенштерну и А.У.Тэккеру из Принстонского университета, Ф.М.Морзу из Массачусетсского технологического института, Р.М.Троллу из Мичиганского университета и К.Б.Томпкинсу из университета Джорджа Вашингтона.

Следующие лица, помимо некоторых из перечисленных выше, прочли и комментировали (многие из них весьма подробно) рукопись: Бернард Броди, Дж. У.Браун, Р.У.Клюитт, Ф.Р.Коллбом, Дж. Б.Дантциг, М.М.Флуд, О.А.Гросс, К.Хастингс (младший), Б.У.Хейдон, С.П.Джефрис, Дж. Л.Кеннеди, Дж. А.Кершоу, Дж. С.Кинг (младший) и Р.А.Вагнер, – все из РЭНД-корпорейшн, а также Э.Ф.Беккенбах из Калифорнийского университета, генерал-майор в отставке Дж. Р.Кук, К, Ф.Мостеллер из Гарвардского университета и, по всей вероятности, другие.

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

РЭНД-корпорейшн позволила мне организовать свою службу так, чтобы иметь возможность выполнить свою задачу и написать книгу.

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