Петросян Л.А. и др. Теория игр

Подождите немного. Документ загружается.

Л.А.Петросян Н.А.Зенкевич Е.А.Семина

ТЕОРИЯ

ИГР

Учебное пособие

Рекомендовано

Министерством общего и

профессионального образования

Российской Федерации

в качестве учебного пособия

для студентов университетов,

обучающихся по специальности

«Математика»

31 Т) V2.

тКт

1°

Москва §1 IVI и

1998 g\ ' Vi?

УДК 51

ББК22.1

ПЗО

Рецензенты: кафедра исследования операций Московского государствен-

ного института электроники и математики (зав. кафедрой д-р физ.-мат. наук,

проф.

В. А. Каштанов) и кафедра исследования операций факультета вычисли-

тельной математики и кибернетики Московского государственного университета

им.

М. В. Ломоносова (зав. кафедрой чл.-кор. АН РАН П. С. Краснощекое).

Петросян Л. А. и др.

П 30 Теория игр: Учеб. пособие для ун-тов:/Л. А. Петросян,

Н. А. Зенкевич, Е. А. Семина. -

М.:

Высш. шк., Книжный дом

«Университет»,

1998.

- 304 с: ил.

ISBN 5-06-001005-8

ISBN 5-8013-0007-4

Книга представляет собой краткое и сравнительно элементарное учебное посо-

бие,

пригодное как для первоначального, так и для углубленного изучения теории

игр;

в ней проводится исследование математических моделей принятия решений в

условиях конфликта. Впервые в отечественной научной литературе дано системати-

ческое изложение единой теории статических и динамических игр. Рассмотрены

конечные и бесконечные антагонистические игры, многошаговые игры, бескоалици-

онные и кооперативные игры, дифференциальные игры. В каждой главе содержатся

задачи разной сложности.

Книга предназначена для студентов и аспирантов университетов, экономических

и технических учебных заведений, представляет интерес как для математиков, рабо-

тающих в области теории игр, так и для специалистов в области экономики, теории

управления и исследования операций.

ISBN 5-06-001005-8

ISBN 5-8013-0007-4

Е.А. Семина, 1998

ОГЛАВЛЕНИЕ

Предисловие 5

Введение 7

Глава I. Матричные игры 9

§ 1. Определение антагонистической игры в нормальной форме . . 9

§ 2. Максиминные и минимаксные стратегии 14

§ 3. Ситуации равновесия 16

§ 4. Смешанное расширение игры 21

§ 5. Некоторые сведения из теории вьшуклых множеств и систем линей-

ных неравенств 25

§ 6. Существование решения матричной игры в классе смешанных стра-

тегий 28

§ 7. Свойства оптимальных стратегий и значения игры 32

§ 8. Доминирование стратегии 40

§ 9. Вполне смешанные и симметричные игры 46

§ 10. Итеративные методы решения матричных игр 52

Упражнения и задачи 56

Глава II. Бесконечные антагошиiическне игры 60

§ 1. Бесконечные игры 60

§ 2. Ситуация е-равновесия, е-седловые точки и г-оптимальные стратегии 63

§ 3. Смешанные стратегии 68

§ 4. Игры с непрерывной функцией выигрыша 77

§ 5. Игры с выпуклой функцией выигрыша 84

§ 6. Одновременные игры преследования 94

§ 7. Один класс игр с разрывной функцией выигрыша 101

§ 8. Решение бесконечных одновременных игр поиска 104

Упражнения и задачи 109

Глава III. Неавтагонистнческне игры 113

§ 1. Определение бескоалиционной игры в нормальной форме . . . . 113

§ 2. Принципы оптимальности в бескоалиционных играх 117

§ 3. Смешанное расширение бескоалиционной игры 125

§ 4. Существование ситуации равновесия по Нашу 129

§ 5. Свойства оптимальных решений 133

§ 6. Равновесие в совместных смешанных стратегиях 138

§ 7. Задача о переговорах 142

§ 8. Игры в форме характеристической функции 146

§ 9. С-ядро и Н—М-решение 155

§ 10. Вектор Шепли 163

Упражнения и задачи 170

Глава IV. Позиционные игры 176

§ 1. Многошаговые игры с полной информацией 176

§ 2. Ситуация абсолютного равновесия 182

§ 3. Основные функциональные уравнения 188

§ 4. Стратегии наказания 191

§ 5. Иерархические игры 194

§ 6. Иерархические игры (кооперативный вариант) 196

§ 7. Многошаговые игры с неполной информацией 204

§ 8. Стратегии поведения 211

§ 9. Функциональные уравнения для одновременных многошаговых игр 218

Упражнения и задачи 224

Глава V. Дифференциальные игры 230

§ 1. Антагонистические дифференциальные игры с предписанной продол-

жительностью 230

§ 2. Многошаговые игры с полной информацией и бесконечным числом

альтернатив 240

§ 3. Существование ситуаций е-равновесия в дифференциальных играх

с предписанной продолжительностью 245

§ 4. Дифференциальные игры преследования на быстродействие .... 253

§ 5. Необходимые и достаточные условия существования оптимальной

программной стратегии убегающего 260

§ 6. Основное уравнение 265

§ 7. Методы последовательных приближений для решения дифференци-

альных игр преследования 273

§ 8. Примеры решения дифференциальных игр преследования .... 278

§ 9. Игры преследования с задержкой информации у преследователя . . 282

Упражнения и задачи 290

Литература 295

ПРЕДИСЛОВИЕ

Математическая теория игр является составной частью исследо-

вания операций. Она находит широкое применение в различных

областях человеческой деятельности, таких, как экономика и менед-

жмент, промышленность и сельское хозяйство, военное дело и стро-

ительство, торговля и транспорт, связь и т. д.

Несмотря на наличие богатой монографической и специальной

литературы по теории игр, учебных пособий, посвященных этому

разделу математики, сравнительно немного и в них рассматриваются

в основном отдельные разделы теории игр. Настоящее учебное посо-

бие восполняет этот пробел. В нем отражено большинство современ-

ных направлений теории игр. Пособие методически построено так,

что понятие модели конфликта (игры) развивается от простой (мат-

ричные игры) до наиболее сложной (дифференциальные игры).

Большинство учебных программ вузов предполагает чтение от-

дельных разделов или специальных курсов по теории игр. Данное

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

могла служить основой такого курса. Для предварительного оз-

накомления с теорией игр достаточно изучить материал гл. I.

Типовой курс по теории игр может быть построен на основе

гл.

I, Ш

и IV. Наиболее подробно изложена теория антагонистических игр

(гл.

I, II, IV, V). В курсах «Системный анализ» и «Модели принятия

решений» целесообразно использовать гл. III и IV. Теория неан-

тагонистических игр изложена в гл. III, IV, а теория динамических

игр — в гл. IV, V. В пособии не отражены результаты теории

дифференциальных игр многих лиц, поскольку этот класс игр еще

недостаточно изучен. Однако имеющиеся в этом направлении рабо-

ты широко представлены в списке литературы

[38,

45,

51,

77, 87, 88].

При построении курса лекций по приложениям теории игр полезно

также воспользоваться специальной литературой [5, 10, 12, 20, 27,

34,

52, 53].

Во всех главах содержатся многочисленные примеры, иллю-

стрирующие основные положения теории. Некоторые из них пред-

ставляют самостоятельный интерес. В конце каждой главы при-

ведены упражнения для индивидуальной работы, расположенные

в порядке изложения материала и возрастания сложности. В ряде

случаев они существенно дополняют содержание главы. Систе-

матическое решение этих упражнений является важной формой

изучения теории игр.

Для усвоения основных понятий и результатов, приведенных

в учебном пособии, достаточно знания курса математики в объеме

университетской программы. Наиболее сложной в математическом

отношении является гл. II, которая предназначена для студентов

математических специальностей. Материал, набранный петитом,

при первоначальном изучении может быть опущен.

В списке рекомендованной литературы приведены основная

(учебники и задачники), дополнительная (монографии и учебные

пособия) и справочная (справочники, обзоры, сборники статей)

литература. В список дополнительной литературы включены также

статьи, которые цитируются в основном тексте книги. Вместе с тем

библиография не претендует на полноту. Библиографические ссыл-

ки можно найти в справочной литературе.

Пособие может быть использовано как для первоначального,

так и для углубленного изучения теории игр. Оно предназначено

для студентов и аспирантов, специализирующихся в области при-

кладной математики, будет также полезно студентам экономичес-

ких и технических специальностей, факультетов менеджмента, из-

учающим математические методы принятия решений в сложных

системах. Книга заинтересует специалистов, занимающихся воп-

росами теории игр, исследования операций, теории управления,

математической экономики, теории менеджмента и их приложени-

ями.

Учебное пособие написано на основе курсов «Теория игр и ис-

следование операций», «Системный анализ», «Математические мо-

дели принятия решений в экономике и управлении», а также ряда

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

танных Л. А. Петросяном и Н. А. Зенкевичем студентам старших

курсов и аспирантам на факультете прикладной математики — про-

цессов управления Санкт-Петербургского государственного универ-

ситета. Параграфы 7, 9 гл. I, § 5, 10 гл. Ш, § 4 — 6, 8 и 9 гл. IV,

§ 2 — 6, 8 гл. V написаны совместно с Е. А. Семиной.

Авторы

ВВЕДЕНИЕ

8.1.

В настоящем учебном пособии изложены основные понятия

и результаты теории игр. Теория игр — это раздел математики,

в котором исследуются математические модели принятия решений

в условиях конфликта, т. е. в условиях столкновения сторон, каждая

из которых стремится воздействовать на развитие конфликта в сво-

их собственных интересах. Теорию математических моделей при-

нятия оптимальных решений принято называть исследованием

операций, поэтому теорию игр следует рассматривать как при-

кладную математическую теорию — составную часть исследования

операций.

8.2. Задачи исследования операций можно классифицировать по

уровню информации о ситуации, которой располагает субъект,

принимающий решение. Наиболее простыми уровнями информа-

ции о ситуации являются детерминированный (когда условия, в ко-

торых принимаются решения, известны полностью) и стохастичес-

кий (когда известно множество возможных вариантов условий и их

вероятностное распределение).

этих случаях задача сводится к на-

хождению экстремума функции (или ее математического ожидания)

при заданных ограничениях. Методы решения таких задач изучают-

ся в курсах математического программирования или методов оп-

тимизации.

Наконец, третий уровень — неопределенный, когда известно

множество возможных вариантов, но без какой-либо информации

об их вероятностях. Такой уровень информации о ситуации являет-

ся наиболее сложным. Эта сложность оказывается принципиальной,

так как могут быть не ясны сами принципы оптимального поведе-

ния. Следуя определению Н. Н. Воробьева, теория игр — это те-

ория математических моделей принятия решений в условиях неоп-

ределенности, когда принимающий решение субъект («игрок») рас-

полагает информацией лишь о множестве возможных ситуаций,

в одной из которых он в действительности находится, о множестве

решений («стратегий»), которые он может принять, и о количествен-

ной мере того «выигрыша», который он мог бы получить, выбрав

в данной ситуации данную стратегию*.

Установление принципов оптимального поведения в условиях

неопределенности, доказательство существования решений, удов-

*Воробъев

Н. Н. Философская энциклопедия. Т. 5. М., 1970. С. 208—210.

летворяющих этим принципам, указание алгоритмов нахождения

решений, их реализация и составляют содержание теории игр.

8.3.

Неопределенность, с которой мы встречаемся в теории игр,

может иметь различное происхождение. Однако, как правило, она

является следствием сознательной деятельности другого лица (лиц),

отстаивающего свои интересы.

связи с этим под теорией игр часто

понимают теорию математических моделей принятия оптимальных

решений в условиях конфликта. Таким образом, моделями теории

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

разные явления: экономические, правовые и классовые конфликты,

взаимодействие человека с природой, биологическую борьбу за

существование и т. д. Все такие модели в теории игр принято

называть играми.

Математическое описание игры сводится к перечислению всех

действующих в ней игроков, указанию для каждого игрока всех его

стратегий, а также численного выигрыша, который он получит

после того, как игроки выберут свои стратегии. В результате игра

становится формальным объектом, который поддается математи-

ческому анализу.

8.4. Игры можно классифицировать по различным признакам.

Во-первых, бескоалиционные игры, в которых каждая коалиция

(множество игроков, действующих совместно) состоит лишь из

одного игрока. Так называемая кооперативная теория бескоалици-

онных игр допускает временные объединения игроков в коалиции

в процессе игры с последующим разделением полученного выигры-

ша или принятие совместных решений. Во-вторых, коалиционные

игры, в которых принимающие решение игроки согласно правилам

игры объединены в фиксированные коалиции. Члены одной ко-

алиции могут свободно обмениваться информацией и принимать

полностью согласованные решения.

По выигрышу игры можно разделить на антагонистические и иг-

ры с ненулевой суммой.

По характеру получения информации — на игры в нормальной

форме (игроки получают всю предназначенную им информацию до

начала игры) и динамические игры (информация поступает игрокам

в процессе развития игры).

По количеству стратегий — на конечные и бесконечные игры.

Начнем изучение теории с простейшей статической модели —

матричной игры, в которой участвуют два игрока, множество

стратегий каждого из игроков конечно, а выигрыш одного игрока

равен проигрышу другого.

ГЛАВА I

МАТРИЧНЫЕ ИГРЫ

§ 1. ОПРЕДЕЛЕНИЕ АНТАГОНИСТИЧЕСКОЙ ИГРЫ

В НОРМАЛЬНОЙ ФОРМЕ

1.1. Определеиие.

Система

Y={X,Y,K),

(1.1)

где Xи Y

— непустые

множества,

функция

К: Хх

Y-*R

называ-

ется

антагонистической игрой

нормальной

форме.

Элементы хеХ и yeY называются стратегиями игроков

1 в 2 соответственно в игре Г, элементы декартового произведения

Хх. Y (т. е. пары стратегий

(JC,

у), где хеХ и ye Y—

ситуациями,

а функция К

— функцией

выигрыша игрока 1. Выигрыш игрока

2 в ситуации (х, у) полагается равным

[—К(х,

у)],

поэтому функция

К также называется функцией выигрыша самой игры Г, а игра

Г —

игрой

с нулевой суммой. Таким образом, используя принятую

терминологию, для задания игры Г необходимо определить множе-

ства стратегий X, Y игроков 1 и 2, а также функцию выигрыша К,

заданную на множестве всех ситуаций Хх Y.

Игра Г интерпретируется следующим образом . Игроки одно-

временно и независимо выбирают стратегии хеХ, yeY. После

этого игрок / получает выигрыш, равный К(х, у), а игрок 2 —

(-К(х,у)).

Определение. Игра Г' = (Х', Y', К

)

называется подыгрой

игры.

Г=(X, Y, К), если X' с X, Y' с У, а функция К':Х'х

Y'-tR

являет-

ся сужением функции К на X' х Y'.

В данной главе будут рассматриваться главным образом ан-

тагонистические игры, в которых множества стратегий игроков

конечны.

1.2. Определение.

Антагонистические

игры, в которых оба

игрока имеют

конечные множества

стратегий,

называются

мат-

ричными.

Пусть игрок 1 в матричной игре (1.1) имеет всего т стратегий.

Упорядочим множество X стратегий первого игрока, т. е. установим

взаимно однозначное соответствие между множествами М={\, 2,

..., т} и X. Аналогично, если игрок 2 имеет и стратегий, то можно

установить взаимно однозначное соответствие между множествами

N={\, 2,..., п} и Y. Тогда игра Г полностью определяется заданием