Теория игр

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ 

Федеральное государственное бюджетное образовательное учреждение  

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

 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ  
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ 

 
 
 
 
 
 
 
 
 
 
 

Н.Ю. Салмина 

 
 

ТЕОРИЯ ИГР 

 

 

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

 
 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

 
 
 
 
 
 
 
 

 

2015 

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

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

Теоретический материал иллюстрируются многочисленными примерами. 
Предназначено для студентов, обучающихся по направлению 080700 «Биз
нес-информатика» и студентов родственных направлений. 

 

ОГЛАВЛЕНИЕ 

 

Предисловие………………………….…….….……..…………….......
4

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

1. Определение и классификация игр………...………………………
7

2. Формы представления игр ……………...………………………….
10

3. Антагонистические игры ………………...…………………………
16

3.1. Конечные игры …………………...……………….....................
16

3.1.1. Защитные и уравновешенные стратегии………………..
16

3.1.2. Решение игр в чистых стратегиях……………………….
19

3.1.3. Решение игр в смешанных стратегиях…………………..
21

3.1.3.1. Понятие смешанной стратегии……………………
21

3.1.3.2. Графический метод………………………………..
24

3.1.3.3. Метод линейного программирования……………
27

3.1.3.4. Аналитическое решение игр 2х2………………….
33

3.1.3.5. Итеративный метод………………………………...
34

3.1.3.6. Сокращение платежной матрицы…………………
38

3.1.4. Игры в позиционной форме ………………………………
40

3.2. Бесконечные антагонистические игры.……………..................
45

3.2.1. Понятие бесконечной игры……………………………….
45

3.2.2. Смешанное расширение бесконечной игры……………..
47

3.2.3. Игры на единичном квадрате…………………………….
50

3.2.4. Выпуклые и вогнутые игры………………………………
53

4. Игры многих лиц…...……………………...…………………………
62

4.1. Общие понятия……………………...………………………….
62

4.2. Конечные бескоалиционные игры…...………………………..
63

4.3. Кооперативные игры без побочных платежей…….................
69

4.4. Классические кооперативные игры………………...………….
73

4.4.1. Характеристическая функция игры……………………..
73

4.4.2. Принципы оптимальности в кооперативных играх……
76

4.4.3. С-ядро игры……………………………………………….
79

4.4.4. Вектор Шепли…………………………………………….
86

4.4.5. N-ядро игры………………………………………………
89

4.5. Коллективное принятие решений……………………………..
93

4.5.1. Модель распределения затрат……………………………
93

4.5.2. Модель производства общественного продукта……….
99

Заключение……………………………………………………………..
103

Литература ..…………………....…………………………………...
104

Глоссарий……………………………………………………………….
105

 

ПРЕДИСЛОВИЕ 

 

Теория игр является составной частью исследования операций. Она находит 

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

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

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

решений в условиях неопределенного поведения конфликтующих сторон. 

В данном пособии рассматриваются некоторые общие вопросы теории игр: 

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

подробно изложены также идеи кооперативного принятия решений на основе 

классических кооперативных игр.  

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

Дисциплина «Теория игр» — одна из основных дисциплин подготовки ба
калавров по направлению «Бизнес-информатика». Основной задачей курса 

«Теория игр» является формирование у студентов профессиональных знаний и 

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

решению экономических задач. 

 

 

 

Введение  

 

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

принимать решения в условиях неопределенности, когда принимающий реше
ние субъект (игрок) располагает информацией лишь о множестве возможных 

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

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

Неопределенность, как правило, является следствием сознательной  деятельно
сти другого лица (лиц), отстаивающего свои интересы [1]. 

Основные  идеи и термины теории игр заимствованы из классических (са
лонных) игр, таких как карты, домино, шахматы и т.д. Классическая салонная 

игра начинается из начальной позиции и состоит из последовательности шагов 

игры, а каждый шаг включает последовательность ходов (выборов) игроков, 

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

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

принимает решение, не зная, в каком состоянии находится игра. 

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

ему максимально возможный выигрыш (минимальный проигрыш). 

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

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

свои стратегии. В результате игра становится формальным объектом, который 

поддается математическому анализу. 

Теория игр занимается исследованием математических моделей конфликтов 

и их формальным решением, что позволяет [2]: 

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

фактического начала; 

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

Выбор стратегии заранее возможен в игре только с личными ходами. Если в 

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

игроков, то можно говорить лишь о математическом ожидании выигрыша. 

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

классификация игр и рассмотрены основные вопросы теории. Различные фор
мы представления игр рассматриваются во второй главе. 

Третья глава посвящена антагонистическим играм: приведены принципы 

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

как в чистых, так и в смешанных стратегиях. Рассмотрены конечные (матрич
ные) и бесконечные антагонистические игры. 

В четвертой главе пособия рассмотрены игры многих лиц: бескоалицион
ные игры, кооперативные игры без побочных платежей, а также классические 

кооперативные игры. 

1. Определение и классификация игр 

 

Игрой называется математическая модель конфликтной ситуации [3]:  

,
 ,
 ,
Г
N
i
J
U
i
i
 

где 
i
U  — множество стратегий i-го игрока;  

  
iJ  — функция выигрыша i-го игрока;  

  N  — множество игроков. 

Игровой смысл модели заключается в том, что функция выигрыша i -го иг
рока зависит не только от стратегии  
i
U  этого игрока, но от стратегий всех ос
тальных игроков: 
).
 
...,
 ,
  
...,
 ,
(
1
n
i
i
i
U
U
U
J
J
 

Игры, как и все задачи исследования операций, бывают статическими и ди
намическими. Мы будем рассматривать только статические игры (
i
U ,
iJ  не за
висят от времени). Класс статических игр по различным признакам подразделя
ется на подклассы. 

В зависимости от количества игроков все игры делятся на игры двух лиц 

и игры многих лиц. Игры двух лиц разделяются на антагонистические (игры 

со строгим соперничеством) и неантагонистические. 

Игры двух лиц называют антагонистическими, если игроки преследуют 

противоположные цели. Здесь всегда выполняется условие 
1
2
J
J
 (все, что 

выигрывает один игрок, проигрывает другой, и наоборот). Антагонистическую 

игру можно задать тройкой 
,
 ,
 ,
Г
2
1
J
U
U
 где J  — функция выигрыша первого 

игрока. В такой игре сумма выигрышей игроков всегда равна нулю. Антагони
стические игры иногда называют играми с нулевой суммой либо играми двух 

лиц со строгим соперничеством.  

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

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

функции 
выигрыша для обоих игроков и 
игра задается 
четверкой 

.
 ,
 ,
 ,
Г
2
1
2
1
J
J
U
U
 

Игры многих лиц подразделяются на бескоалиционные и коалиционные. В 

бескоалиционных играх целью каждого игрока является максимизация инди
видуального выигрыша (минимизация проигрыша). Коалиционные игры — 

это игры, в которых действия игроков направлены на максимизацию выигрыша 

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

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

делится между членами коалиции по соглашению. 

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

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

Вид функции выигрышей определяет игры с непрерывными функциями 

выигрышей и игры с дискретными функциями выигрышей. Для класса игр 

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

от вида функции выпуклые, вогнутые, выпукло-вогнутые игры. 

Конечной целью исследования любой игры является нахождение опти
мальных стратегий игроков и их выигрышей. Множество оптимальных стра
тегий игроков и вектора выигрышей называется оптимальным решением иг
ры. 

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

выигрыш зависит и от поведения других сторон. Кроме того, оптимальные 

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

участвующие  стороны равноправны. Поэтому понятие оптимальности в любой 

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

1) Необходимость выбора принципа оптимальности перед началом игры. То 

есть необходимо ответить на вопрос: «В чем состоит оптимальность поведе
ния?». 

2) Необходимость выяснения вопроса, реализуем ли выбранный принцип 

оптимальности. Существуют ли оптимальные, в смысле выбранного принципа, 

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

3) Поиск оптимальных решений, если они существуют. Во-первых, необхо
димо выяснить, по каким признакам отличаются оптимальные стратегии от ос
тальных; во-вторых, разработать эффективные методы решений. 

В общем случае для каждого класса игр существуют некоторые общие 

принципы оптимальности («разумного» поведения). Знакомство с этими прин
ципами дает возможность лицу, принимающему решение, обосновать свой вы
бор, основываясь не на интуиции, а на строгих расчетах.  

 

Вопросы для самопроверки 

1. Какая игра называется антагонистической? 

2. Какая игра называется бескоалиционной? 

3. Что является конечной целью любой игры? 

4. Что понимается под оптимальностью в игре? 

5. Перечислите основные проблемы, которые возникают при решении игр. 

2. Формы представления игр 

 

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

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

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

нельзя заранее запланировать свои действия. Но поскольку в таких играх число 

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

Существуют реальные конфликты, в которых участники делают свои ходы 

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

последним участникам. Если в игре участвует случай (раздача карт, бросание 

кубика и т.д.), то игроки могут иметь или не иметь информацию о результатах 

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

игр. 

В зависимости от цели исследования любую игру можно рассматривать в 

развернутой (позиционной) или в нормальной (частный случай — матричной) 

формах. В развернутой форме лучше раскрывается последовательность собы
тий, она более наглядна для многоходовых игр. Здесь показываются очередно
сти ходов игроков, их информированность и выигрыши. Недостатком этой 

формы представления является сложность нахождения решения. Нормальная 

форма игры менее наглядна, зато большинство эффективных методов нахожде
ния решений разработано именно для этой формы. 

Развернутая форма представляет игру в виде дерева, имеющего следую
щую структуру [13]: 

1) начальная точка — исходная позиция игры; 

2) ребра, исходящие из одной и той же вершины, называются альтернатива
ми и нумеруются, либо помечаются в соответствии с ходами игроков; каждое 

ребро соответствует какому-либо ходу игрока; 

3) вершины, имеющие хотя бы одну альтернативу, называются промежу
точными; каждая  промежуточная  позиция соответствует какому-то состоянию 

игры; 

4) вершины, не имеющие ни одной альтернативы, называются конечными и 

означают конец игры; возле каждой конечной вершины записывается вектор  

),
 
...,
 ,
 ,
(
2
1
N
Q
Q
Q
 определяющий  выигрыши  игроков  в  данной  позиции; 

5) множество всех промежуточных вершин (включая начало дерева) разби
вается на  
1
N
 множество  
N
I
I
I
 
...,
 ,
 ,
1
0
 ( N  — количество игроков), называемых 

множествами очередностей; в множестве 
iI  ходит i -й игрок, 
0I — очередь хода 

случая; 

6) каждое множество очередностей 
iI  разбивается на подмножества 
k
iI , на
зываемые информационными множествами, отражающими информированность 

игрока: игрок знает, в каком информационном множестве он находится, но не 

знает, в какой именно вершине; следовательно, вершины одного и того же ин
формационного множества имеют одинаковое число альтернатив; если каждое 

информационное множество игрока содержит только одну вершину дерева, то 

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

имеет полную информацию; 

7) путь от начала дерева до любой конечной позиции называется партией; 

каждая партия содержит не больше одной вершины в каждом информационном 

множестве. 

Рассмотрим примеры представления игры в позиционной форме. 

 

Пример 2.1 

Пусть игрок 1 имеет 2, а игрок 2 — 3 фишки. Независимо и тайно друг от 

друга они откладывают произвольное количество фишек. Если при этом коли