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

      Министерство образования и науки Российской Федерации
           Уральский федеральный университет
        имени первого Президента России Б. Н. Ельцина
                А. Г. Кремлев
           Основные понятия 
               теории игр
                Рекомендовано 
             методическим советом УрФУ
          в качестве учебного пособия для студентов,
          обучающихся по программе бакалавриата 
        по направлению подготовки 080100 — Экономика
                 Екатеринбург
           Издательство Уральского университета
                   2016

            УДК 519.83(075.8)
            ББК 22.18я73
                      К79
                                         Рецензенты:
                А. Н. Красовский, д‑р физ.‑мат. наук, проф., завкафедрой «Инфор‑
                мационные технологии и математическое моделирование» Ураль‑
                ского государственного аграрного университета;
                С. С. Титов, д‑р физ.‑мат. наук, проф., завкафедрой прикладной 
                математики и технической графики УралГАХА
                Научный редактор — А. М. Тарасьев, д‑р физ.‑мат. наук, проф., 
                завсектором Института математики и механики им. Н. Н. Красов‑
                ского УрО РАН
                Кремлев, А. Г.
            К79    Основные понятия теории игр : учебное пособие / А. Г. Крем‑
                лев. — Екатеринбург : Изд‑во Урал. ун‑та, 2016. — 144 с.
                   ISBN 978‑5‑7996‑1940‑4
                    Изложены базовые понятия и положения теории игр, типичные моде‑
                ли и применяемые методы решения и анализа антагонистических и беско‑
                алиционных игр. В качестве основных принципов оптимальности рассма‑
                триваются оптимальность по Парето и равновесность по Нэшу. Каждый 
                раздел включает теоретические сведения, сопровождающие примеры, кон‑
                трольные вопросы и задания.
                    Предназначено студентам, обучающимся по направлению подготовки 
                «Экономика», а также всем, интересующимся теорией игр.
                    Библиогр.: 32 назв. Рис. 17.
                                                               УДК 519.83(075.8)
                                                               ББК 22.18я73
            ISBN 978‑5‑7996‑1940‑4                 © Уральский федеральный
                                                        университет, 2016

                         Оглавление
          Предисловие .....................................................................5
          1. Общее представление о теории игр ............................11
            Предмет теории игр ....................................................11
            Неопределенность в игровых ситуациях ...................13
            Применение теории игр .............................................14
            Классификация игр ....................................................16
            Примеры классических игр двух лиц .........................17
            Контрольные вопросы и задания ...............................25
          2. Формализация бескоалиционных игр .......................28
            Нормальная форма игры ............................................28
            Ситуации равновесия по Нэшу ..................................29
            Доминирование стратегий .........................................31
            Оптимальные по Парето ситуации ............................34
            Стратегическая эквивалентность игр ........................38
            Свойство наилучших ответов игроков .......................43
            Контрольные вопросы и задания ...............................44
          3. Матричные игры .........................................................47
            Определение матричной игры ...................................47
            Ситуации равновесия в матричной игре ...................49
            Смешанные стратегии ................................................54
            Ситуации равновесия в смешанных стратегиях ........56
            Свойства значения игры.............................................60
            Контрольные вопросы и задания ...............................62
                                                   3

                                         Оглавление
        4. Решение матричных игр .............................................64
          Задачи игроков в матричной игре ..............................65
          Решение матричной игры 2×2 ...................................67
          Графический метод решения матричной игры .........69
          Теорема о дополняющей нежесткости 
          (теорема равновесия) ..................................................77
          Решение матричных игр 2×n и m×2 ...........................80
          Теоремы о доминировании строк (столбцов) 
          платежной матрицы ....................................................86
          Контрольные вопросы и задания ...............................90
        5. Сведение матричной игры к задаче линейного 
        программирования (ЛП) ................................................92
          Эквивалентные задачи ЛП для игроков ....................92
          Общий вид задачи ЛП ................................................95
          Правила работы с симплекс‑таблицей ....................100
          Контрольные вопросы и задания .............................107
        6. Биматричные игры ...................................................108
          Определение биматричной игры .............................108
          Смешанное расширение биматричных игр .............109
          Условия равновесия (в смешанных стратегиях) 
          в биматричной игре 2×2 ...........................................111
          Поиск ситуаций равновесия в биматричных играх ....115
          Графический метод решения биматричных 
          игр 2×n и m×2 ...........................................................124
          Свойства равновесных стратегий .............................128
          Доминирование смешанных стратегий ...................134
          Контрольные вопросы и задания .............................137
        Библиографический список ........................................139
       4

         
                       Предисловие
                         Представляется также необходимым фикси‑
                         ровать не только то, чем занимается, но и то, 
                         чем не занимается теория игр в ее современ‑
                         ном состоянии, тем более, что на этот счет бы‑
                         туют самые фантастические представления.
                                          Н. Н. Воробьев
              анное пособие посвящено изучению основ теории игр. 
              Теория игр связана с разделом прикладной математи‑
          Д
              ки «Исследование операций», в котором занимаются 
        разработкой и применением методов нахождения оптимальных 
        решений (наилучших по тем или иным признакам) на основе 
        математического моделирования в различных областях чело‑
        веческой деятельности.
          Современная экономическая теория характеризуется вы‑
        соким уровнем формализации, что определяет существенное 
        использование математических методов и моделей. Адекват‑
        ная математическая модель социально‑экономического явле‑
        ния должна отражать присущие ему особенности. Одна из ха‑
        рактерных черт всякого социально‑экономического явления 
        состоит в различии интересов участвующих в нем сторон (на‑
        личии разных точек зрения на само явление и его возможные 
        исходы), в разнообразии действий, которые эти стороны мо‑
        гут осуществлять для достижения своих целей. Такие ситуации, 
        обусловленные множественностью (несовпадением) интересов 
        участников, стремлением как можно больше выиграть у конку‑
        рентов (получить наилучший индивидуальный результат), на‑
        зывают конфликтными ситуациями (конфликтами).
                                                 5

                                                                                          Предисловие
                  Принятие управленческих решений в условиях конфлик‑
              та требует специального исследования, основанного на ис‑
              пользовании методов теории игр. Для таких ситуаций каче‑
              ство и количество имеющейся информации о данной ситуации 
              (объекте управления и внешней среде) определяют, каким об‑
              разом может быть формализована и решена задача принятия 
              решения.
                  Формализация конфликтной ситуации в форме игры заклю‑
              чается в описании ее основных элементов, к которым относят‑
              ся субъекты игры (игроки), множество их стратегий (допусти‑
              мые альтернативы), способы выбора стратегий, информация, 
              которой обладает каждый игрок при осуществлении такого вы‑
              бора, выигрыш каждого игрока при каждом наборе выбранных 
              стратегий. Доступная игрокам информация о намерениях дру‑
              гих игроков, их возможностях (могут ли они договариваться, 
              действовать сообща против других игроков) может существен‑
              но повлиять на принимаемое решение.
                  Всякая игра регламентирована определенными правилами, 
              указывающими:
                  ·   порядок чередования действий (или «ходов») участников;
                  ·  правила выполнения каждого хода;
                  ·  количественный результат игры (выигрыш, проигрыш), 
                      к которому приводит данная совокупность ходов.
                  Сформулировать реальную конфликтную ситуацию в игро‑
              вой форме — это значит схематизировать ее так, чтобы ясно 
              были видны возможные способы поведения участников (на‑
              зываемые стратегиями) и численный результат (количествен‑
              ная оценка — платеж), к которому приводит каждая комбина‑
              ция стратегий участвующих сторон.
                  Формализованная схема конфликтной ситуации в матема‑
              тической форме представляет ее математическую модель.
                  Целью теории игр является выработка рекомендаций для 
              разумного поведения игроков в конфликтных ситуациях, т. е. 
              определение оптимальной стратегии каждого из игроков.
              6

            Предисловие
            Оптимальной стратегией игрока называется такая страте‑
          гия, которая при многократном повторении игры обеспечи‑
          вает данному игроку максимально возможный средний выи‑
          грыш (или, что равносильно, минимально возможный средний 
          проигрыш).
            При выборе игроком этой стратегии за основу берется пред‑
          положение, что его противник (или противники) является 
          вполне разумным (мыслящим рационально) и делает все, что‑
          бы помешать ему (игроку) добиться своей цели.
            Основной принцип теории игр можно сформулировать сле‑
          дующим образом: выбирай свое поведение так, чтобы оно было 
          рассчитано на наихудший для тебя образ действий противника.
            Если игроки (участники некоторой игры) одинаково разум‑
          ны (действуют рационально), то должно быть найдено некото‑
          рое равновесное положение, определяющее равновесный сред‑
          ний выигрыш для каждого игрока. Этот равновесный средний 
          выигрыш, на который вправе рассчитывать каждый игрок, ре‑
          ализуется, если игроки будут вести себя разумно, т. е. придер‑
          живаться своих оптимальных стратегий. Следует заметить, что 
          если какой‑то игрок будет вести себя неразумно (нерациональ‑
          но) и примет иную, отличную от оптимальной, стратегию, то его 
          выигрыш может уменьшиться (в общем случае не увеличиться 
          по сравнению с равновесным выигрышем).
            В современных условиях принятие эффективного управлен‑
          ческого решения невозможно без сочетания творческого мыш‑
          ления субъекта управления, обладающего достаточным уров‑
          нем знаний и умений (квалификаций), применения различных 
          моделей и методов (которые способен разработать и внедрить 
          субъект управления), а также современной техники обработ‑
          ки информации (системно достаточной и организованной для 
          выработки решения). Включение дисциплины «Теория игр» 
          в учебный план по направлению «Экономика» имеет целью 
          изучение теоретических основ формирования моделей теории 
          игр, освоение навыков практического поиска (выбора) опти‑
                                                            7

                                                     Предисловие
         мальных стратегий и использования расчетных методов этой 
         дисциплины.
           В данном пособии рассматриваются базовые понятия и по‑
         ложения теории игр, типичные модели и применяемые мето‑
         ды решения и анализа антагонистических и бескоалиционных 
         игр. В качестве основных принципов оптимальности рассма‑
         триваются оптимальность по Парето и равновесность по Нэшу.
           Пособие состоит из шести разделов, каждый из которых 
         включает теоретические сведения, сопровождаемые примера‑
         ми, контрольными вопросами и заданиями. В разделе 1 дается 
         общее представление о теории игр (предмет и содержание тео‑
         рии игр, виды неопределенностей в игровых ситуациях), при‑
         водятся некоторые сведения о применении результатов теории 
         игр, указывается общая классификация игр, рассматриваются 
         примеры классических игр двух лиц («Дилемма заключенно‑
         го», «Семейный спор», «Орлянка»).
           Раздел 2 посвящен формализованному представлению бес‑
         коалиционной игры (в нормальной форме), в которой целью 
         каждого игрока является оптимизация индивидуального вы‑
         игрыша (причем игроки не могут координировать совместно 
         свои стратегии). В этом разделе определяются ситуации рав‑
         новесия по Нэшу, рассматриваются вопросы доминирования 
         «чистых» стратегий, дается определение оптимальных по Па‑
         рето ситуаций, приводится геометрическая интерпретация 
         предпочтительности ситуаций, излагаются основные свой‑
         ства стратегически эквивалентных игр, указывается свойство 
         равновесной по Нэшу ситуации относительно наилучших от‑
         ветов игроков.
           Разделы 3–5 посвящены матричным играм (конечным анта‑
         гонистическим играм). В разделе 3 вводятся основные понятия 
         матричной игры, указываются формализованные цели игроков, 
         приводятся определение ситуации равновесия в чистых страте‑
         гиях (седловая точка матрицы), условия существования ситуа‑
         ций равновесия, схема нахождения седловых точек, смешанное 
         8

                                        Предисловие
        Библиографический список включает как источники, ко‑
       торые использовались при написании данного пособия, так 
       и работы, которые позволяют более глубоко рассмотреть суть 
       теоретико‑игровой проблемы, понять широту применения ре‑
       зультатов и методов (направлений исследований) теории игр. 
       Достаточно обширная библиография по теории игр и сопря‑
       женным вопросам приведена в [4].
        Для первоначального ознакомления с основными поня‑
       тиями и методами теории игр можно рекомендовать работы  
       [5–7, 10, 11, 17, 22, 27, 28].
        Большинство из представленных в библиографическом спи‑
       ске работ можно найти в электронных информационных ре‑
       сурсах.
       10

          
               1. Общее представление о теории игр
           Предмет теории игр
                редметом теории игр является математический ана‑
                лиз конфликтных ситуаций, формализованное опи‑
           Псание которых представлено в виде математической 
         модели, определяющей некоторую игру.
           Конфликтная ситуация — это ситуация, в которой сталки‑
         ваются интересы двух (и более) противодействующих сторон, 
         преследующих различные цели (несовпадающие полностью или 
         частично). Эти конфликтующие стороны стремятся предпри‑
         нять такие действия (выбрать такие решения), чтобы достичь 
         наибольшего для себя в данных условиях успеха. Таким обра‑
         зом, если цели сторон противоположны, то максимизация успе‑
         ха (выигрыша) одной из сторон будет означать максимизацию 
         проигрыша другой стороны. А если сторон несколько (более 
         двух), то это ведет к уменьшению их возможных выигрышей. 
         Поэтому конфликтующие стороны будут осуществлять поиск 
         наиболее приемлемых для себя решений (причем эта приемле‑
         мость должна быть для каждой из сторон).
           Если каждая из сторон (в результате собственной оценки 
         текущей ситуации) примет какое‑то определенное решение, 
         то последующая реализация принятых решений приведет к кон‑
         кретному результату — распределению выигрышей сторон. Ре‑
                                                      11

                                                         1. Общее представление о теории игр
            шения сторонами могут приниматься независимо друг от друга 
            и не сообщаться заранее другим сторонам конфликта.
               Таким образом, каждой из сторон приходится принимать 
            решение в условиях неопределенности поведения противо‑
            действующих сторон, т. е. выигрыш каждой стороны зависит 
            от того, как поведут себя другие стороны конфликта. Как опти‑
            мизировать принятие (или выбор) правильного решения? Ка‑
            кие требования предъявляются к таким оптимальным решени‑
            ям? Как найти оптимальные решения?
               Теория игр занимается исследованием математических мо-
            делей конфликтных ситуаций (игр) и их формальным решени‑
            ем, что позволяет:
               ·  смоделировать процесс игры и ее возможные результаты 
                   до ее фактического начала;
               ·  по результатам анализа смоделированной игры принять 
                   решение о целесообразности участия и оптимальном по‑
                   ведении в реальном конфликте.
               Таким образом, теория игр дает математический прогноз 
            конфликта (с учетом степени адекватности используемой мо‑
            дели конфликта).
               Итак, теория игр — это теория математических моделей при‑
            нятия решений в условиях неопределенности, когда принима‑
            ющий решение субъект («игрок») располагает информацией 
            лишь о множестве возможных ситуаций, в одной из которых 
            он в действительности находится, о множестве решений («стра‑
            тегий»), которые он может принять, и о количественной мере 
            того «выигрыша», который он мог бы получить, выбрав в дан‑
            ной ситуации данную стратегию1.
               Содержание теории игр: установление принципов оптималь‑
            ного поведения в условиях неопределенности, доказательство 
            существования решений, удовлетворяющих этим принципам, 
            указание алгоритмов нахождения решений, их реализация.
               1 
                Воробьев Н. Н. Философская энциклопедия. Т. 5. М., 1970. С. 208.
            12