Основы теории игр

Основы
теории игр

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

Л. В. Колобашкина

Рекомендовано
УМО по образованию в области прикладной математики
и управления качеством в качестве учебного пособия
для студентов высших учебных заведений,
обучающихся по направлению 231300 –
Прикладная математика

5-е издание, электронное

Москва
Лаборатория знаний
2021

УДК 519.83(075)
ББК 22.193я7
К60
Р е ц е н з е н т ы:
доктор физ-мат. наук, проф., зав. кафедрой А. Л. Калабин,
доктор техн. наук Н. Н. Филатова
(Тверской государственный технический университет,
кафедра «Программное обеспечение
вычислительной техники»),
кандидат техн. наук, доцент кафедры вычислительной
техники МЭИ И. Н. Андреева

Колобашкина Л. В.
К60
Основы теории игр : учебное пособие / Л. В. Колобашкина. —
5-е изд., электрон. — М. : Лаборатория знаний, 2021. — 198 с. —
Систем. требования: Adobe Reader XI ; экран 10". — Загл. с титул.
экрана. — Текст : электронный.
ISBN 978-5-906828-81-1
В пособии изложены основные положения и сведения из теории игр,
подробно рассмотрены методы выбора оптимальных стратегий поведения
в антагонистических и неантагонистических конфликтах. Приведены критерии определения оптимальных стратегий в «играх с природой». Рассмотрены
методы принятия решений в антагонистических и неантагонистических
позиционных играх с полной и неполной информацией. Рассмотрены
принципы оптимальности для кооперативных игр. Все представленные
методы сопровождаются подробно рассмотренными примерами. Доступность изложения материала делает знакомство с принципами рационального
поведения в конфликтах привлекательным для широкого круга читателей.
Пособие предназначено для студентов высших учебных заведений,
обучающихся по специальностям «Прикладная математика», «Прикладная
математика и информатика», «Математические методы в экономике».
УДК 519.83(075)
ББК 22.193я7

Деривативное издание на основе печатного аналога: Основы теории
игр : учебное пособие / Л. В. Колобашкина. — 3-е изд., испр. и доп. —
М. : БИНОМ. Лаборатория знаний, 2014. — 195 с. : ил.
ISBN 978-5-9963-1716-5.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных
техническими
средствами
защиты
авторских
прав,
правообладатель вправе требовать от нарушителя возмещения убытков или
выплаты компенсации

ISBN 978-5-906828-81-1
© Лаборатория знаний, 2015

Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Глава 1. Принятие решений в антагонистических
конфликтах . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.1. Матричные игровые задачи.
Составление модели игры . . . . . . . . . . . . . . . . . 11

1.2. Сокращение размерности игровой задачи . . . . . . . . 14
1.3. Решение игровых задач в «чистых» стратегиях.
Принцип минимакса . . . . . . . . . . . . . . . . . . . . 17

1.4. Смешанные стратегии. . . . . . . . . . . . . . . . . . . . 21
1.5. Методы решения матричных игр 22 . . . . . . . . . . 24

1.5.1. Аналитический метод . . . . . . . . . . . . . . . . . . 24
1.5.2. Метод, основанный на понятии равновесия
по Нэшу . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.5.3. Графическая интерпретация игры 22 . . . . . . . . 28

1.6. Игры 2n и m2. . . . . . . . . . . . . . . . . . . . . . . . 32

1.6.1. Игра 2n . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.6.2. Игра m2 . . . . . . . . . . . . . . . . . . . . . . . . . 36

1.7. Методы решения матричных игр nn
. . . . . . . . . . 39

1.7.1. Решение игр размерности nn методом
Лагранжа . . . . . . . . . . . . . . . . . . . . . . . . . 39

1.7.2. Решение игр размерности nn методом
Крамера . . . . . . . . . . . . . . . . . . . . . . . . . . 42

1.7.3. Метод обратной матрицы. . . . . . . . . . . . . . . . 48

1.8. Методы решения матричных игр mn . . . . . . . . . . 52

1.8.1. Решение игр размерности mn
методами линейного программирования . . . . . . 52

1.8.2. Итерационный метод решения игровых задач
размерности mn . . . . . . . . . . . . . . . . . . . . 61

1.9. Практическое применение смешанных стратегий . . . 66

Глава 2. Принятие решений в неопределенных ситуациях
(игры «с природой») . . . . . . . . . . . . . . . . . . . . 71

2.1. Элементы теории статистических решений . . . . . . . 71
2.2. Критерии принятия решений в играх «с природой» . . 74
2.3. Планирование эксперимента
в условиях неопределенности . . . . . . . . . . . . . . . 76
2.3.1. Случай «идеального» эксперимента . . . . . . . . . 76
2.3.2. Случай «неидеального» эксперимента . . . . . . . . 79

Оглавление

Глава 3. Принятие решений в неантагонистических
конфликтах . . . . . . . . . . . . . . . . . . . . . . . . . 85

3.1. Биматричные игровые задачи . . . . . . . . . . . . . . . 85
3.2. Отношения доминирования в биматричных играх . . . 87
3.3. Графический способ решения
биматричных задач 22 . . . . . . . . . . . . . . . . . . . 94

3.4. Аналитический метод решения биматричных
игровых задач mn. Алгоритм Лемке–Хоусона . . . . 100

Глава 4. Многошаговые процессы принятия решений. . . . 114

4.1. Позиционные игры. . . . . . . . . . . . . . . . . . . . . 114
4.2. Нормализация позиционной игры. . . . . . . . . . . . 116
4.3. Решение позиционных игровых задач
с неполной информацией
. . . . . . . . . . . . . . . . 120

4.4. Решение позиционных игровых задач
с полной информацией . . . . . . . . . . . . . . . . . . 139

4.5. Принятие организационно-управленческих
решений с помощью позиционных игр . . . . . . . . . 147
4.5.1. «Планирование производства» . . . . . . . . . . . . 147
4.5.2. «Погоня за конкурентом» . . . . . . . . . . . . . . . 151

Глава 5. Принятие решений в кооперативных играх. . . . . 163

5.1. Принципы кооперации . . . . . . . . . . . . . . . . . . 163
5.2. Дележ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.3. Алгоритм выделения экономически устойчивых
коалиций в кооперативной игре . . . . . . . . . . . . . 168

5.4. Анализ полезности формирования коалиций
с помощью нормализованной формы игры . . . . . . 174

5.5. Принцип оптимальности в форме С-ядра . . . . . . . 178
5.6. НМ-решение . . . . . . . . . . . . . . . . . . . . . . . . 183
5.7. Вектор Шепли. . . . . . . . . . . . . . . . . . . . . . . . 185

Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

4
Оглавление

ВВЕДЕНИЕ

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

раций — это искусство давать плохие ответы на те практические
вопросы, на которые даются еще худшие ответы другими способами [2]. Это говорит о том, что практические ситуации, в которых
приходится принимать решение, часто бывают настолько сложными и важными, что даже незначительная помощь со стороны математических методов оказывается весьма существенной.
Особенно сложные управленческие проблемы возникают в сфере социально-экономических отношений. Обычно развитие социально-экономического явления зависит от действий многих лиц,
каждое из которых лишь частично контролирует ситуацию. Лица,
принимающие решения, имеют свои интересы, часто не полностью
выявленные и представленные с некоторой долей неопределенности. Эти интересы могут совпадать (возможно, частично), что ведет к сотрудничеству и кооперации. Но они могут и противоречить
друг другу (возможно, частично), что ведёт к соперничеству и конфликту [3].
При решении ряда практических задач (в области экономики,
военного дела и т. д.) приходится анализировать ситуации, в которых сталкиваются две и более враждующие стороны, преследующие
различные цели. Причем результат любого мероприятия каждой из
сторон зависит от того, какой образ действий выберет противник.
Такие ситуации называются конфликтными ситуациями.
Исследованием операций в условиях конфликта занимается теория игр.
Теория игр — математическая теория конфликтных ситуаций.
Чтобы сделать возможным математический анализ конфликтной
ситуации, необходимо построить упрощенную схематизированную
модель ситуации, которую будем называть игрой. Заметим, что понятия игра и конфликт — синонимы.
В игре могут сталкиваться интересы двух и более сторон. Целью
каждого участника игры является получение возможного большего
выигрыша.
Теория игр занимается исследованием математических моделей
конфликтов и их формальным решением, что позволяет:

смоделировать процесс и возможные результаты будущей
игры еще до ее фактического начала;

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

6
Введение

Реальные конфликтные ситуации приводят к различным видам
игр. В зависимости от вида игры разрабатывается и метод ее
решения.
Классификация игр осуществляется по целому ряду направлений [4].

По количеству игроков: парные игры и игры n игроков. Наибольшие успехи достигнуты при изучении парных игр.
Трудности решения игровых задач с увеличением количества игроков повышаются.

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

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

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

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

Введение
7

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

По виду функций выигрыша: матричные, биматричные,
непрерывные. Матричная игра — это конечная игра двух игроков с нулевой суммой, в которой выигрыши первого игрока равны проигрышам второго и наоборот; задается в виде
одной
матрицы. Биматричная игра — это конечная игра
двух игроков с ненулевой суммой, в которой выигрыши каждого игрока сосредоточены в матрице игры данного игрока;
данный вид игр задается двумя матрицами. Непрерывной
считается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий.
Данное учебное пособие состоит из четырех глав.
Глава 1 посвящена методам принятия решений в антагонистических конфликтах. В этой главе вводятся основные понятия теории матричных игр, рассматриваются вопросы составления модели
игры, уменьшения размерности задачи путем применения отношений доминирования, излагаются способы определения равновесных ситуаций в «чистых» стратегиях, приводятся аналитические,
итерационные и графические методы определения оптимальных
смешанных стратегий в зависимости от размерности задачи,
рассматриваются вопросы практического применения полученных
результатов.
В ряде задач функция выигрыша зависит от неопределенных
факторов, к которым можно отнести погодные условия, состояние
рынка, курс валюты, инфляцию, психоэмоциональное состояние
лица, принимающего решения, и т. д. Рассчитывая на «худший» вариант, этот неопределенный фактор, который называют «природой», отождествляют со стратегией противника, имеющего противоположные интересы. Методы принятия решений в играх с
«природой», являющихся разновидностью антагонистических игр,
рассматриваются в главе 2.
В главе 3 приводятся методы поиска оптимальных решений в
неантагонистических конфликтных ситуациях, рассматриваются
вопросы редуцирования размерности задачи в зависимости от
целевого критерия.
Глава 4 посвящена многошаговым процессам принятия решений.
В ней описывается структура позиционной игры, рассматриваются

8
Введение

вопросы ее нормализации, излагаются методы принятия решений в
антагонистических и неантагонистических позиционных играх с полной и неполной информацией, приводятся практические примеры
решения организационно-управленческих задач с помощью позиционных игр.
В главе 5 приводятся базовые понятия теории кооперативных
игр, дается математическое обоснование для выделения устойчивых коалиций в кооперативных играх на основе взаимных экономических интересов. Рассматриваются варианты распределения
выигрыша между игроками коалиции. Излагаются принципы оптимальности для кооперативных игр — С-ядро, НМ-решение и
вектор Шепли.
В пособии приняты следующие обозначения: новые понятия
выделены жирным курсивом; матрицы в общем виде приводятся
в круглых скобках, а матрицы с числовыми значениями — в квадратных.
Книга рассчитана, в первую очередь, на практика, впервые знакомящегося с предметом. Доступность изложения материала делает
знакомство с принципами рационального поведения в конфликтах
привлекательным для широкого круга читателей.
Данное пособие написано на основе курса лекций, читаемого
автором в Московском инженерно-физическом институте (НИЯУ
МИФИ).

Введение
9