Оригинално заглавие:
MATHEMATICAL METHODS AND THEORY IN GAMES, PROGRAMMING, AND ECONOMICS
by SAMUEL KARLIN Stanford University PERGAMON PRESS LONDON - PARIS 1959
*
Перевод с английского
Н. А. Бобина, Л. И. Горькова, А. А. Корбута, А. Н. Ляпунова, Н. М. Митрофановой, А. Н. Смирнова и Е. Б. Яновской
*
Под редакцией
Н. Н. Воробьева
**
АННОТАЦИЯ
Эта книга посвящена математическому анализу ситуаций, возникающих при управлении самыми разнообразными формами деятельности человека с целью достижения максимального эффекта.
Книга состоит из трех частей: матричные игры, программирование и математическая экономика, бесконечные игры. Первая и третья части имеют много точек соприкосновения, в то время как вторая часть является более самостоятельной.
Основное внимание автор уделяет теории антагонистических игр, изложение которой является наиболее полным из имеющихся в мировой литературе.
Книга адресована широкому кругу читателей: студентам-математикам, изучающим теорию игр, линейное и нелинейное программирование, студентам-экономистам, имеющим определенную математическую подготовку, научным работникам самых разнообразных специальностей, занимающимся исследованием операций.
***
ОГЛАВЛЕНИЕ
Предисловие редактора 5
Предисловие 9
Введение. Сущность математической теории процессов решения .... 13
1. Общие замечания 13
2. Классификация математического аппарата задач принятия решений 16
3. Основные дисциплины 19
Обозначения 23
ЧАСТЬ I ТЕОРИЯ МАТРИЧНЫХ ИГР
Глава 1. Определение игры и теорема о минимаксе 27
1.1. Введение. Игры в нормальной форме 27
1.2. Примеры 32
1.3. Выбор стратегий 34
1.4. Теорема о минимаксе для конечных матричных игр 37
1.5. Общая теорема о минимаксе 42
1.6. Задачи 45
Комментарии и библиография к главе 1 48
Глава 2. Свойства оптимальных стратегий матричных игр 51
2.1. Свойства оптимальных стратегий 51
2.2. Виды строгого доминирования 53
2.3. Нахождение оптимальных стратегий 57
2.4. Описание крайних оптимальных стратегий 61
2.5. Вполне смешанные матричные игры 69
2.6. Симметричные игры 74
2.7. Задачи 76
Комментарии и библиография к главе 2 79
Глава 3. Соотношения размерностей для множеств оптимальных стратегий 31
3.1 Основная теорема 81
3.2. Доказательство теоремы 3.1.1 32
3.3. Доказательство теоремы 3.1.2 87
3.4. Обращение теоремы 3.1.2 90
3.5. Единственность оптимальных стратегий 95
3.6. Задачи 101
Комментарии и библиография к главе 3 103
Глава 4. Решения некоторых матричных игр 105
4.1. Игра полковника Блотто 106
4.2. Опознание своего и неприятеля 107
4.3. Игра в покер 110
4.4. Один пример рекламы 116
4.5*. Пример торгов 120
4.6.' Задачи 125
Комментарии и библиография к главе 4 127
Решения задач из глав 1—4 129
ЧАСТЬ II
ЛИНЕЙНОЕ И НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ И МАТЕМАТИЧЕСКАЯ ЭКОНОМИКА
Глава 5. Линейное программирование 141
5.1. Формулировка задачи линейного программирования 142
5.2. Задача линейного программирования и двойственная ей задача 145
5.3. Основные теоремы линейного программирования (предварительные результаты) 147
5.4. Основные теоремы линейного программирования (продолжение) 152
5.5*. Связь между задачами линейного программирования и теорией игр 154
5.6*. Обобщения теоремы двойственности .г 155
5.7. Задача о рациональном использовании склада 158
5.8. Задача об оптимальном назначении ' 161
5.9. Транспортная задача и задача о потоке 167
5.10. Теорема о максимальном потоке и минимальном разрезе . . 172
5.11*. Задача о поставщике 174
5.12*. Модель биржевой игры 180
5.13. Задачи 184
Комментарии и библиография к главе 5 . . . 188
Глава 6. Вычислительные методы линейного программирования и теории игр 191
6.1. Симплекс-метод 192
6.2*. Вспомогательные варианты симплекс-метода 202
6.3. Пример применения симплекс-метода 207
6.4*. Вычисление потока в сети 210
6.5. Метод приближенного вычисления значения игры 214
6.6*. Доказательство сходимости 217
6.7. Метод определения значения игры при помощи дифференциальных уравнений 224
6.8 Задачи 228
Комментарии и библиография к главе 6 232
Глава 7. Нелинейное программирование 234
7.1. Вогнутое программирование 235
7.2. Примеры вогнутого программирования 240
7.3*. Градиентный метод Эрроу — Гурвица 249
7.4. Векторная задача максимизации 253
7.5*. Сопряженные функции 256
7.6*. Композиция сопряженных функций 260
7.7*. Сопряженные вогнутые функции 265
7.8*. Теоремы двойственности для нелинейного программирования . 266
7.9*. Приложения теории сопряженных функций к выпуклым множествам 270
7.10. Задачи 279
Комментарии и библиография к главе 7 282
Глава 8. Математические методы в изучении экономических моделей 285
8.1. Открытые и замкнутые линейные модели Леонтьева 286
8.2. Теория положительных матриц 289
8.3. Приложения теории положительных матриц к изучению линейных моделей равновесия и обмена 300
8.4. Теория производства 303
8.5. Эффективные точки модели леонтьевского типа 307
8.6*. Теория потребительского выбора 311
8.7. Нелинейные модели равновесия 320
8.8*. Модель равновесия конкурентной экономики (Эрроу — Дебре) 328
8.9. Задачи 333
Комментарии и библиография к главе 8 337
Глава 9. Математические методы в изучении экономических моделей (продолжение) 341
9.1*. Экономика благосостояния 343
9.2. Устойчивость конкурентного равновесия 351
9.3. Локальная устойчивость 356
9.4. Глобальная устойчивость процесса регулирования цен .... 361
9.5*. Глобальная устойчивость (продолжение) 372
9.6*. Формулировка глобальной устойчивости в терминах разностных уравнений 378
9.7. Устойчивость и ожидания (модель I) 381
9.8. Устойчивость и ожидания (модель II) 386
9.9. Модель расширяющейся экономики фон Неймана 389
9.10. Общая модель сбалансированного роста 391
9.11. Задачи • 397
Комментарии и библиография к главе 9 401
Решения задач к главам 5—9 * * 404
ЧАСТЬ III ТЕОРИЯ БЕСКОНЕЧНЫХ ИГР
Глава 10. Природа и структура бесконечных игр 417
10.1. Введение 417
10.2. Игры на единичном квадрате 421
10.3. Классы игр на единичном квадрате 424
10.4. Бесконечные игры, у которых пространства стратегий являются известными функциональными пространствами 432
10.5. Как решать бесконечные игры 436
10.6. Задачи 440
Комментарии и библиография к главе 10 443
Глава 11*. Вырожденные и полиномиальные игры 445
11.1. Конечные выпуклые игры общего вида 445
11.2. Метод неподвижной точки для конечных выпуклых игр . . . 448
11.3. Соотношения между размерностями для конечных выпуклых игр 453
11.4. Метод сопряженных конусов 457
11.5. Структура множеств решений вырожденных игр 461
11.6. Общие замечания о выпуклых множествах в пространстве Еп 463
11.7. Пространства обобщенных моментов 467
11.8. Полиномиальные игры 472
11.9. Задачи 479
Комментарии и библиография к главе 11 . 481
Глава 12. Игры с выпуклыми и обобщенно-выпуклыми ядрами . . . 483
12.1. Введение 483
12.2. Непрерывные выпуклые игры 484
12.3*. Обобщенно-выпуклые игры 488
12.4. Игры с выпуклой функцией выигрыша в Еп 493
12.5*. Одна теорема о выпуклых функциях 500
12.6. Задачи 503
Комментарии и библиография к главе 12 505
Глава 13. Игры с «выбором момента времени при однократном действии каждого игрока 507
13.1. Примеры игр с выбором момента времени 508
13.2. Интегральные уравнения для игр с выбором момента времени и их решения 517
13.3*. Интегральные уравнения с положительными ядрами 526
13.4. Доказательство существования 532
13.5. Бесшумная дуэль с произвольными функциями меткости . . 546
13.6. Задачи , 551
Комментарии и библиография к главе 13 554
Глава 14. Игры с выбором момента времени (продолжение) .... 556
14.1. Игры с выбором момента времени; класс I . 556
14.2. Примеры 557
14.3*. Доказательство теоремы 14.1.1 560
14.4*. Игры с выбором нескольких моментов времени 565
14.5*. Бабочкообразные ядра 574
14.6. Задачи 584
Комментарии и библиография к главе 14 586
Глава 15*. Различные игры 588
15.1. Игры с аналитическими ядрами 589
15.2. Колоколообразные ядра 594
15.3. Колоколообразные игры 599
15.4. Другие типы непрерывных игр 606
15.5. Инвариантные игры 609
15.6. Задачи 615
Комментарии и библиография к главе 15 620
Глава 16. Бесконечные классические игры, разыгрываемые не на единичном квадрате . 622
16.1. Предварительные результаты (леммы Неймана — Пирсона). . 623
16.2*. Приложение леммы Неймана — Пирсона к вариационной задаче 626
16.3. Дуэль снайпера с пулеметчиком 632
16.4*. Решение дуэли снайпера с пулеметчиком 636
16.5*. Дуэль двух пулеметчиков 643
16.6. Задачи 653
Комментарии и библиография к главе 16 656
Глава 17. Покер и общие салонные игры 658
17.1. Упрощенная игра „черный валет" 661
17.2. Модель покера с одним кругом ставок и одним размером ставки 666
17.3. Модель покера с несколькими размерами ставки 669
17.4. Модель покера с двумя кругами ставок 676
17.5*. Модель покера с к повышениями 683
17.6. Покер с одновременными ходами 687
17.7. Игра „проходящий туз" 689
17.8*. „У кого старше, тот выигрывает" 693
17.9. Задачи .698
Комментарии и библиография к главе 17 701
Решения задач к главам 10—17 703
Приложения 740
Приложение А. Векторные пространства и матрицы 741
А. 1. Евклидовы и унитарные пространства 741
Упражнения 742
А. 2. Подпространства, линейная независимость, базис, прямые суммы, ортогональные дополнения 743
Упражнения 745
А. 3. Линейные преобразования, матрицы и линейные уравнения . . 745
Упражнения 751
А. 4. Собственные значения. Собственные векторы. Каноническая форма Жордана 752
Упражнения 759
А. 5. Транспонированные, нормальные и эрмитовы матрицы; ортогональные дополнения 760
Упражнёния . . . 763
А. 6. Квадратичные формы 763
Упражнения 765
А. 7. Функции от матриц 765
Упражнения 768
А. 8. Определители, миноры, алгебраические дополнения 768
Упражнения 771
А. 9. Некоторые тождества 771
А. 10. Блочные матрицы 777
Упражнения 779
Приложение Б. Выпуклые множества и выпуклые функции 779
Б. 1. Выпуклые множества в Еп 779
Упражнения 782
Б. 2. Выпуклые оболочки множеств и крайние точки выпуклых множеств 782
Упражнения 785
Б. 3. Выпуклые конусы 785
Упражнения 788
Б. 4. Выпуклые и вогнутые функции 788
Упражнения 790
Приложение В. Различные вопросы 790
В. 1. Полунепрерывные и равностепенно непрерывные функции . . 790
В. 2. Теоремы о неподвижной точке 793
В. 3. Функции множеств и распределения вероятностей 793
Библиография 798
Предметный указатель 819
Именной указатель 830
****
ПРЕДИСЛОВИЕ РЕДАКТОРА
В последнее время идеи и приемы исследования операций начинают приобретать все большее значение в процессах принятия решений, а математические методы исследования операций складываются в широко разветвленные научные дисциплины. Эти математические теории можно классифицировать по самым различным признакам. Несколько таких классификаций приводятся в этой книге (см. Введение, § 2).
Одна из них основана на противопоставлении статических задач динамическим. Первые можно охарактеризовать как задачи, в которых процесс принятия решения сводится к некоторому единичному акту. В динамических же задачах принятие решения состоит из последовательности (быть может, бесконечной) принятия частичных решений. Такие задачи возникают, например, в связи со всевозможными процессами управления. Для задач динамического типа показательно изменение самого субъекта, принимающего ре шения, по мере принятия им решений. Именно в ходе многошагового процесса решения может приобретаться или, наоборот, теряться существенная для выбора решения информация, могут изменяться сравнительные ценности тех или иных последствий принятых решений, могут, наконец, открываться новые возможности или становиться недоступными старые.
Другая классификация связана с выделением детерминированного и стохастического вариантов задач. Детерминированные задачи отражают невероятностный, достоверный подход к явлениям, тогда как в задачи стохастического типа всегда входят случайные события, величины или процессы.
Укажем еще на одну возможную классификацию. Математические теории, используемые в процессах принятия решений, можно разбить на „дескриптивные" теории, которые математически описывают изучаемые процессы, и на теории „управления", отражающие целенаправленность принимаемых решений. В первом случае обычно выявляются последствия того или иного произвольно принятого решения; во втором— на передний план выдвигается то, что автор (на стр. 15) называет нормативной сущностью теории; основные усилия направляются на поиски именно того решения, последствия от принятия которого будут наиболее благоприятными („оптимальными"). Весьма характерным примером теории, относящейся к первому классу, может служить теория массового обслуживания; теории второго класса достаточно ярко представлены различными „программированиями". Разумеется, эта классификация (как и всякая другая классификация научных направлений) не может претендовать на абсолютную четкость. Так, например, в теории массового обслуживания уже появились решения отдельных оптимизационных задач; с другой стороны, проблемы существования решений в ряде задач оптимального программирования, в сущности, являются чисто описательными, познавательными задачами, решение которых не связывается непосредственно с принятием того или иного решения.
После всего сказанного содержание данной монографии С. Кар-лина можно коротко описать следующим образом. Эта книга содержит строгое и систематическое изложение математического аппарата теории принятия решений и исследования операций, связанного с детерминированными статическими оптимизационными задачами. Именно, книга охватывает теорию антагонистических игр в нормальной форме (несколько более половины всего объема книги), линейное программирование, нелинейное программирование и некоторые разделы современной математической экономики, примыкающие к оптимальному программированию (модели типа „затраты — выпуск", теория равновесия и др.).
„Динамичность" игр с выбором момента времени и рассматриваемых автором экономических моделей чисто кажущаяся, потому что в обоих этих случаях решения принимаются единожды на весь процесс. Точно так же использование вероятностных соображений в излагаемых вопросах теории игр еще не составляет стохастического подхода к этим вопросам.
Стремление автора ограничиться детерминированными статическими оптимизационными задачами объясняет отсутствие в книге разделов, посвященных динамическим играм (в том числе статистическим решающим функциям), динамическому программированию, теории массового обслуживания, а также „самой операционной из теорий исследования операций"—теории управления запасами (в которой, кстати сказать, автор является видным специалистом). Это обстоятельство нельзя считать ни пробелом в изложении, ни тем более недостатком книги. Оно является естественным следствием четкого определения ее предмета.
Хотя все проводимые автором математические рассуждения достаточно прозрачны, требования, формально предъявляемые к математической подготовке читателя, довольно скромны, а выходящие за пределы общеизвестного сведения по линейной алгебре, анализу и теории выпуклых множеств приведены в трех приложениях, назвать книгу элементарной никак нельзя. Больше того, несмотря на независимое от каких-либо других руководств изложение предмета, начинающееся с исходных определений, ее едва ли можно рекомендовать как учебник для первоначального знакомства с теорией игр, программированием или математической экономикой. Лучше всего приступать к чтению этой книги, имея уже достаточно основательные познания о предмете (например, в объеме чрезвычайно доходчиво написанной книги Д. Гейла „Теория линейных экономических моделей", ИЛ, 1963). Обладающий же известной предварительной подготовкой читатель сможет извлечь из книги много полезного.
Во-первых, целенаправленное развитие „сюжета" выявляет единство математических идей, лежащих в основе формально столь различных между собой теорий. Это обстоятельство педагогически чрезвычайно важно и делает целесообразным использование книги в качестве учебника для глубокого изучения предмета.
Во-вторых, разнообразие приложений убедительно показывает возможность применения излагаемых математических методов в самых различных областях человеческой деятельности. Конечно, при интерпретации математико-экономических вопросов автор выступает с обычных позиций буржуазного ученого. Однако ценность развиваемого при этом математического аппарата с этими интерпретациями непосредственно не связана. Например, ход разрешения споров между профсоюзом и предпринимателем (§ 4.5) хотя и рисуется в слишком уж упрощенном виде, но как условный пример даже интересен.
Наконец, в-третьих, приведенные в конце каждой главы задачи (общим числом более трехсот) иллюстрируют и развивают излагаемый в книге материал. Даже внимательный анализ читателем приведенных в книге решений этих задач (не говоря уже о самостоятельном их решении) несомненно принесет большую пользу.
Перевод книги выполнили Н. А. Бодин (главы 1 — 4), А. Н. Смирнов (главы 5—6), А. А. Корбут (главы 8—9), Л. И. Горьков (главы 7, 10—12), Е. Б. Яновская (главы 13—16), А. Н. Ляпунов (глава 17) и Н. М. Митрофанова (приложения). Обширная авторская библиография дополнена наиболее значительной новой литературой по тематике данной монографии. Эта работа выполнена А. А. Корбутом.
Н. Н. Воробьев
*****
ПРЕДИСЛОВИЕ
Разделы математики, используемые в процессах принятия решений, играют все более важную роль в анализе задач управления производством, в вопросах экономики, военной тактики и исследования операций. Эти области приложения привели к созданию математических дисциплин нового типа. Развитие теории игр, линейного и нелинейного программирования, а также математической экономики характеризует одну из значительных сторон такого рода математики.
По существу, настоящая книга является попыткой предварительного синтеза понятий теории игр и теории программирования с понятиями и методами математической экономики в единую систематическую теорию. Кроме того, мы надеемся, что данная книга окажется полезной в качестве учебника или справочника по этим предметам, а также послужит основой для последующего их изучения и разработки.
Содержание этой книги ни в коей мере не является исчерпывающим; мы придавали особое значение тем вопросам, которые считали более важными. В то же время мы пытались сообщить читателю основную традиционную информацию, от которой зависит правильное понимание теории игр и теории программирования. Изложение каждого предмета хотелось сделать замкнутым в себе и вполне строгим; вместе с тем мы стремились выявить идейную глубину и формальное изящество всей теории. В данной книге принципы теории игр и теории программирования применяются к большому числу упрощенных задач, связанных с экономическими моделями, с моделями принятия деловых решений и задачами военной тактики, для того чтобы пояснить рассматриваемые математические понятия и указать на их применимость к такого рода проблемам.
Каждая глава содержит некоторое количество более сложного материала, который обычно сведен в параграфы, отмеченные звездочкой (*). Элементарные вспомогательные сведения изложены в приложениях, а более сложные включены непосредственно в текст.
Каждая глава содержит задачи различной трудности; многие из этих задач приводят к обобщениям теории. Решения большинства задач и краткие указания относительно решения остальных задач даны в конце каждой части.
Три части монографии, за исключением материала в разделах, отмеченных звездочкой, не зависят друг от друга: их можно изучать (вместе с относящимися к ним приложениями) независимо. Для удобства читателя на следующей странице дается схема, показывающая взаимосвязи основного материала, содержащегося в книге.
Каждая глава завершается разделом, содержащим исторические замечания, некоторые соображения, касающиеся тех или иных деталей, и перечисление книг и статей, которыми можно воспользоваться для получения дополнительной информации. Вся цитированная литература перечислена в библиографии в конце книги. В некоторых случаях исторические замечания состоят в указании на приоритет выдающихся открытий; любые неточности или упущения в этом отношении являются совершенно непреднамеренными, и автор заранее глубоко о них сожалеет.
Я многим выражаю свою признательность, и в первую очередь Станфордскому университету, Калифорнийскому технологическому институту, Корпорации РЭНД и Управлению морских исследований, которые вдохновили меня на создание этой книги и обеспечили благоприятные условия и поддержку при ее написании.
Среди моих университетских коллег я благодарен профессорам Боукеру, Либерману, Мадоу, Парзену и Скарфу (Станфордский университет) за их постоянную поддержку; профессору Боненбласту из Калифорнийского технологического института, познакомившему меня с этой областью науки и обучившему меня очень многому, за что я всегда буду перед ним в долгу; моим ученикам Р. Рестрепо и Р. Миллеру, записавшим мои лекции, на материале которых основана эта книга; моим ученикам У. Пруитту и Ч. Стоуну, каждый из которых сделал ценные предложения по организации и улучшению окончательного варианта рукописи; профессорам Удзава и Эрроу, которые научили меня большей части того, что я знаю по математической экономике; моим друзьям Мелвину Дрешеру, Рею Фулкер-сону и Харвею Вагнеру за их полезные замечания по первым шести главам и Ирвингу Гликсбергу за помощь в написании приложений.
Наконец, я приношу благодарность моей жене, которая принимала теплое участие, проявила безграничное терпение и доброту в течение этих долгих лет писательства.
Станфорд, Калифорния Август, 1959
