Глава III

ТЕОРИЯ ИГР-РАЗДЕЛ МАТЕМАТИКИ

За время, прошедшее с момента выхода в свет монографии Теория игр и экономическое поведение , теория игр разрослась в обширную дисциплину; ей посвящено значительное число монографий, о которых достаточно обстоятельно говорится в предисловии О. Моргенштерна к данному изданию, а также огромное количество статей (библиография, составленная в 1959 г. Д. Томпсон и Дж. Томпсоном [1], уже насчитывала 1009 названий).

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

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

§ 1. МАТРИЧНЫЕ ИГРЫ

1. К настоящему времени матричные игры теоретически изучены достаточно хорошо. Боненбласт, Карлин и Шепли [1] выяснили возможное расположение многогранников оптимальных стратегий игроков в матричных играх в симплексах всех их смешанных стратегий, указав необходимые соотношения для размерностей тех и других. Они же указали способ построения матричной игры с заданным решением. Исследование этого последнего вопроса было завершено в работе Гейла и Шер-мана [1], которые охарактеризовали множество пар выпуклых многогранников, которые могут быть множествами оптимальных стратегий игроков в некоторой матричной игре, а также нашли способ описания всех игр с заданными множествами оптимальных стратегий игроков. Множественность решений, обычно присущая играм, для матричных игр является в некотором смысле исключением. Боненбласт, Карлин и Шепли [1] установили, что множество всех т X тг-игр, имеющих единственные решения, открыто и всюду плотно в яш-мерном евклидовом- пространстве всех т х тг-игр.

Весьма интересные исследования, касающиеся общих комбинаторных свойств седловых точек в матрицах, были выполнены Шепли [6].

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

Во-первых, можно пытаться выделять те или иные классы матричных игр зависящих от небольшого числа параметров (см. по этому поводу сказанное в II.4.2). Решения для таких классов игр (впрочем, довольно узких и немногочисленных) можно найти в книгах Карлина [3] и Дрешера [1].

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

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

Пусть X и Y - оптимальные стратегии игроков I и II в игре с матрицей выигрышей А, значение которой отлично от нуля. Тогда для того, чтобы X и Y были крайними точками (вершинами) соответствующих многогранников оптимальных стратегий, необходимо и достаточно, чтобы нашлась такая невырожденная г х г-подматрица В матрицы А, что

*.-jJ!. -Тту *<A-j£& < >

(здесь Хв и YB означают те части векторов X и У, которые составлены из компонент, отвечающих строкам или столбцам матрицы А, участвующим в образовании ее подматрицы В; Jr - г-мерный вектор, все компоненты которого равны единице).

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

3. Весьма интересный, основанный на дифференциальных уравнениях способ приближенного нахождения оптимальных стратегий игроков в матричной игре предложили Браун и фон Нейман [1].

Пусть А - кососимметрическая n X ?г-матрица (рассмотрение, игр только с кососимметрическими матрицами выигрышей общности рассмотрений не умаляет). Тогда оптимальной стратегией каждого из игроков является каждая из предельных точек решения системы дифференциальных уравнений

= Ф, (*)-*, 2 Ф,(*) (2)

при произвольных начальных условиях (#£, для которых

Фг (х) = max {0, 2 axj}.

К сожалению, на практике даже численное решение системы (2) представляет большие трудности.

4. Еще один путь нахождения хотя бы одной стратегии каждого из игроков, предложенный Брауном и строго обоснованный Дж. Робинсон

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

Оценка сходимости описанного процесса, данная Шапиро [1], показывает, что он сходится весьма медленно: погрешность в определении

1

значения п X етг-игры за t шагов имеет порядок t nm 2.

5. Как пишет Гейл [1], одним из самых удивительных событий, связанных с появлением современной теории линейных экономических моделей, явилось одновременное, но независимое развитие теории линейного программирования, с одной стороны, и теории игр, с другой, и выявившаяся затем тесная связь между этими двумя предметами . По свидетельству Данцига [1], на связь между линейным программированием и теорией матричных игр указывал еще Дж. фон Нейман в 1947 г. Затем этими вопросами занимались Гейл, Кун и Таккер [1]. В наиболее естественной форме эквивалентность пары двойственных друг другу задач линейного программирования и матричной игры дается теоремой, принадлежащей Данцигу и Брауну и опубликованной Данцигом [2].

Рассмотрим пару двойственных задач линейного программирования

АХТВТУ YAC,

CXT->max, 75r-min

(ХО), (УО).

Для того чтобы векторы Х° и У0 являлись оптимальными решениями этих задач, необходимо и достаточно, чтобы вектор

(tX\ tY°, t)

был оптимальной стратегией одного из игрокоз в игре с матрицей

О -А Вт\ Ат О -Ст\ -В с о /

(поскольку эта матрица кососимметрична, неважно, о каком именно игроке идет речь), причем t > 0.

Эквивалентность решения матричной игры решению задач линейного программирования позволяет применять к решению первых все приемы, разработанные для решения вторых. В частности, оптимальные стратегии в матричных играх можно находить при помощи известного симплекс-метода. Весьма практичный способ решения матричной игры при помощи линейного программирования предложил Таккер [1].

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