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

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

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

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

Рекомендовано
УМО по образованию в области прикладной математики
и управления качеством в качестве учебного пособия
для студентов высших учебных заведений,
обучающихся по направлению 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

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

Наибольшее практическое значение имеют парные игры, поэто-
му основное внимание уделим рассмотрению этого класса игр.
Развитие игры во времени представляется состоящим из ряда
последовательных «ходов». Ходом в теории игр называется выбор
одного из предусмотренных правилами игры действий и его осуще-
ствление. Ходы бывают личные и случайные. Личным ходом назы-
вается сознательный выбор игроком одного из возможных вариан-
тов действий и его осуществление. Случайным ходом называется
выбор из ряда возможных альтернатив, осуществляемый некоторой
незаинтересованной средой — назовем ее природой. Для каждого
случайного хода правила игры определяют распределение вероят-
ностей возможных исходов [1].
Задача теории игр — рекомендовать игрокам определенные
«стратегии» при выборе их личных ходов.
Стратегией игрока называется совокупность правил, опреде-
ляющих выбор варианта действий при каждом личном ходе этого
игрока, в зависимости от ситуации, сложившейся в ходе игры.
Целью теории игр является определение «оптимальной страте-
гии» для каждого игрока.
Оптимальной стратегией игрока называется такая стратегия,
которая при многократном повторении игры обеспечивает данному
игроку максимально возможный средний выигрыш. При выборе
этой стратегии считается, что противник делает все, чтобы поме-
шать игроку добиться своей цели.
При постановке игровых задач должны быть определены следу-
ющие условия:

стороны, принимающие решения;

множество всех возможных действий (стратегий);

выигрыши сторон для каждой ситуации.

Рассмотрим игру двух игроков, скажем А и В, каждый из кото-
рых имеет конечное число стратегий. Предположим, игрок А имеет
m стратегий: А1, А2, ..., Аm, а игрок В — n стратегий: B1, B2, ..., Bn.
Каждой паре стратегий (Аi, Bj) ставится в соответствие число aij,

ГЛАВА 1
ПРИНЯТИЕ РЕШЕНИЙ
В АНТАГОНИСТИЧЕСКИХ КОНФЛИКТАХ

выражающее выигрыш игрока А за счет игрока В (если aij > 0) или
проигрыш игрока А игроку В (если aij < 0), когда А применяет свою
стратегию Аi, а В — стратегию Bj.
В том случае, когда цели двух конкурирующих сторон являются
прямо противоположными,
для них можно определить единый
критерий: одна из сторон будет заинтересована в увеличении значе-
ния этого критерия, а другая — в его уменьшении.
В случае единого критерия данная игра полностью может быть
описана матрицей размерности m n, которая называется матри-
цей игры или платежной матрицей (отсюда следует и название
данного класса игр — матричные игры).

A B
B
B
a
a
a
a
a
a

a

n

n

n

m

1
2

11
12
1

21
22
2

1

...
...
...
...
...
...
...
a
a

A
A

A
m
mn
m
2

1

2

...
...

.

Рассмотрим пример. Пусть матрица игры имеет вид

A 5
6
3
10
4
1 .

Сторона А имеет две стратегии, а сторона В — три стратегии.
Если игрок А применяет свою стратегию А2, а В — стратегию В3,
то, следовательно, игрок А выигрывает 1 у. е., а игрок В проигрыва-
ет игроку А 1 у. е. Если игрок А применяет свою стратегию А1, а В —
стратегию В2, то, следовательно, игрок А проигрывает 6 у. е. игроку
В, а игрок В выигрывает 6 у. е. у игрока А.
В данной игре один игрок выигрывает ровно столько, сколько
проигрывает другой, т. е. сумма выигрышей игроков равна нулю.
Поэтому игры данного класса называют играми с нулевой суммой.
Ценой игры называется средний выигрыш игрока А.
Рассмотрим несколько примеров построения платежных мат-
риц.

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

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