Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Теория игр

Покупка
Артикул: 769573.01.99
Доступ онлайн
180 ₽
В корзину
В настоящем учебном пособии изложены основные вопросы теории игр. Рассматриваются формы представления игр, как способы формализации различных задач. В учебное пособие включены для рассмотрения следующие классы игровых моделей: конечные и бесконечные антагонистические игры, бескоалиционные игры, кооперативные игры. Для каждого из рассматриваемых классов игровых моделей приводятся принципы оптимальности и методы нахождения оптимального решения. Теоретический материал иллюстрируются многочисленными примерами. Предназначено для студентов, обучающихся по направлению 080700 «Бизнес-информатика» и студентов родственных направлений.
Салмина, Н. Ю. Теория игр : учебное пособие / Н. Ю. Салмина. - Томск : Томский государственный университет систем управления и радиоэлектроники, 2015. - 107 с. - Текст : электронный. - URL: https://znanium.com/catalog/product/1845845 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
 
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ 
Федеральное государственное бюджетное образовательное учреждение  
высшего профессионального образования 
 
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ  
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ 
 
 
 
 
 
 
 
 
 
 
 
Н.Ю. Салмина 
 
 
ТЕОРИЯ ИГР 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


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


 
ОГЛАВЛЕНИЕ 
 
    Предисловие………………………….…….….……..……………....... 
    Введение …………………………………..………….……………….. 
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 
    Литература ..…………………....…………………………………... 
    Глоссарий………………………………………………………………. 
 


 
ПРЕДИСЛОВИЕ 
 
Теория игр является составной частью исследования операций. Она находит 
широкое применение в различных областях человеческой деятельности, таких, 
как экономика и менеджмент, промышленность и сельское хозяйство, военное 
дело и строительство и т.д. Теория игр исследует операции в условиях конфликта, занимается анализом математических моделей принятия рациональных 
решений в условиях неопределенного поведения конфликтующих сторон. 
В данном пособии рассматриваются некоторые общие вопросы теории игр: 
представление игр в различных формах; принципы оптимальности в антагонистических и неантагонистических играх; методы нахождения решений. Рассмотрены различные классы игровых моделей. Большое внимание уделено изучению антагонистических игр, как конечных, так и бесконечных. Достаточно 
подробно изложены также идеи кооперативного принятия решений на основе 
классических кооперативных игр.  
Для усвоения основных результатов и понятий, приведенных в учебном пособии, достаточно знания курса математики в объеме университетской программы. Во всех главах содержатся многочисленные примеры, иллюстрирующие основные положения теории игр. 
Дисциплина «Теория игр» — одна из основных дисциплин подготовки бакалавров по направлению «Бизнес-информатика». Основной задачей курса 
«Теория игр» является формирование у студентов профессиональных знаний и 
практических навыков по решению задач принятия решений в условиях противодействия, а также по решению задач кооперативного принятия решений; разработке и созданию игровых моделей с целью исследования сложных систем, 
решению экономических задач. 
 
 
 


 
Введение  
 
Теория игр — это раздел математики, в котором исследуются математические модели принятия решений в условиях конфликта, т.е. в условиях столкновения сторон, каждая из которых  стремится воздействовать на развитие конфликта в своих собственных интересах. При этом каждая сторона вынуждена 
принимать решения в условиях неопределенности, когда принимающий решение субъект (игрок) располагает информацией лишь о множестве возможных 
ситуаций, в одной из которых он может находиться, о множестве решений 
(стратегий), которые он может принять, и о количественной мере того выигрыша, который он мог бы получить, выбрав в данной ситуации данную стратегию. 
Неопределенность, как правило, является следствием сознательной  деятельности другого лица (лиц), отстаивающего свои интересы [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) начальная точка — исходная позиция игры; 


Доступ онлайн
180 ₽
В корзину