Для того чтобы задать игру в нормальной форме, нужно сделать три вещи.
1. Нужно, во-первых, указать множество всех игроков в этой игре.
2. Во-вторых, указать множество возможных стратегий каждого игрока.
3. И, в-третьих, указать платеж, который получает каждый игрок.
Выполнив все шаги алгоритма, мы можем внести все данные в таблицу, которая называется матрицей игры. Вот так выглядит матрица игры «Орлянка». Выигрыши первого игрока, Алисы, записаны в левом верхнем углу, а выигрыши второго игрока, Боба, записаны в правом нижнем углу. Каждая клетка матрицы обозначает пересечение всех возможных стратегий игроков, а числа, записанные в них, все возможные исходы игроков, в зависимости от принятых ими стратегий.
Заметим, что сумма выигрышей в каждой клетке равна нулю. Более того, любая игра, в которой интересы игроков противоположны, может быть предоставлена в такой форме. Такой тип игр называется играми с нулевой суммой.
Мы пока оставим эту игру без решения, так как она решается при помощи смешанных стратегий, о которых мы расскажем позже. Но зато мы перейдем к другой игре, которую мы сможем решить при помощи одного из методов.
«Дилемма заключённого»
Наиболее популярная в теории игр является так называемая дилемма заключенного. Она является объектом многих споров специалистов в области теории игр, так как ее решение носит парадоксальный характер. Но начнем с условий игры.
Алиса и Боб являются чикагскими гангстерами 1920-х годов. Окружной прокурор знает, что они виновны в совершении крупного преступления, но он не может осудить ни одного из них до тех пор, пока кто-то из них в нём не сознается. Прокурор арестовывает их и предлагает каждому из них по отдельности следующую сделку:
· Если Вы сознаетесь в преступлении, а ваш партнёр- нет, то мы выпускаем Вас из тюрьмы (0).
· Если Вы не сознаетесь, а Ваш партнёр- сознается, то Вы получите максимально возможный срок заключения (-10).
· Если Вы оба сознаетесь, то каждый из Вас получит тюремный срок, но не один из вас не получит максимального срока (-9).
· Если же ни один из Вас не сознается, то вы оба получите незначительный срок за уклонение от налогов (-1).
Итак, мы видим, что это параллельная игра, так как решения игроков принимаются одновременно. Поэтому мы также, как и в прошлом примере записываем эту игру в нормальной форме при помощи таблицы. Стратегия, при которой игрок не сотрудничает со следствием, называется молчать, а стратегия при которой игрок идёт на сотрудничество-стучать.
Может кто-нибудь из вас предположить, какие стратегии выберут Алиса и Боб?
Данную игру можно решить при помощи метода, который предложил известный математик, лауреат Нобелевской премии за «Анализ равновесия в теории некооперативных игр», Джон Нэш. Этот метод получил название равновесие по Нэшу. В более общем виде, мы можем определить равновесие по Нэшу как ситуацию, в которой каждый игрок выбирает наилучший ответ, на стратегию, выбранную его противником. Иными словами, равновесием Нэша называется такой профиль стратегий, что никому из игроков не выгодно отклониться и сыграть другую стратегию при фиксированных стратегиях других игроков.
Для того чтобы понять идеи, которые лежат в основе концепции равновесия по Нэшу, совсем не обязательно быть гением. Мы знаем, что игроки действуют рационально и стремятся максимизировать свой ожидаемый выигрыш.
Почему мы вообще рассматриваем равновесие по Нэшу? На это есть две причины. Первая из них состоит в предположении о том, что именно равновесие по Нэшу является тем решением, к которому стремятся игроки, ведущие себя рационально. Вторым предположением является то, что люди находят путь к решению путём проб и ошибок. Успехи теории игр в прогнозировании поведения игроков вытекают из её способности в совокупности рассматривать оба этих противоположных аспекта.
Итак, вернёмся к нашей игре, и решим её при помощи равновесия по Нэшу. Для этого мы должны найти наилучший ответ игрока на стратегию соперника. То есть мы будем выбирать для каждого игрока наилучшую стратегию, при неизменной стратегии другого игрока. А для этого мы будем сравнивать выигрыши игрока и выбирать наибольший. Например, для Алисы, в ответ на стратегию МОЛЧАТЬ будет более выгодным выбрать стратегию СТУЧАТЬ, так как в таком случае, она получит выигрыш, равный нулю, то есть её отпустят, что будет лучше, если она выберет Молчать и получит выигрыш равный -1, то есть 1 год в тюрьме. Обведём наилучший ответ Алисы на стратегию молчать в кружочек. Теперь определим наилучший ответ Алисы на стратегию СТУЧАТЬ. И это снова будет СТУЧАТЬ, так как -9, больше -10. Проделаем тоже самое и для Боба. Поместим в квадратик наилучшие ответы Боба на стратегии Алисы.
Мы видим, что в нашей матрице есть профиль стратегий, в котором отмечены наилучшие ответы на стратегии противников обоих игроков. Именно этот профиль стратегий, СТУЧАТЬ; СТУЧАТЬ и будет равновесным по Нэшу. Это значит, что ни одному из игроков не будет выгодно отклониться от своей стратегии при неизменной стратегии другого игрока.
Итак, мы с вами видим, что при выборе стратегии равновесия по Нэшу оба игрока проведут значительный срок в тюрьме, поскольку оба решают сознаться. При этом если бы они держали рот на замке, то провели бы за решеткой намного меньше времени. В этом и заключается парадоксальность решения. Но никакого парадокса рациональности не существует. Так как профиль стратегий молчать; молчать может быть достигнут только при помощи предварительного сговора игроков. Но рациональные игроки не стремятся к кооперативному поведению в игре «Дилемма заключенного», поскольку сама формулировка этой игры не предполагает мотивов для кооперации. Игроки не придерживаются никакого правила, например такого как категорический императив Иммануила Канта. Они действуют исключительно рационально, и именно поэтому они всегда выбирают стратегию сотрудничать.
Таким образом, формулировка этой задачи предполагает, что стратегия СТУЧАТЬ является наилучшим ответом на любую стратегию противника. Следовательно, для того чтобы принять наилучшее решение, игроку вообще не важно знать, какую стратегию выберет его противник. Рациональным поведением игрока в данном случае является выбор стратегии СТУЧАТЬ, независимо от того, что захочет сделать другой игрок. В этой конкретной ситуации мы говорим, что стратегия СТУЧАТЬ доминирует альтернативные стратегии.
Доминирование— ситуация, при которой одна из стратегий некоторого игрока дает больший выигрыш, нежели другая, при любых действиях его оппонентов.
Строго доминирующая стратегия-такая стратегия, при которой каждый её выигрыш строго больше выигрышей любой другой стратегии игрока, при неизменных стратегиях других игроков.
Один из основателей теории игр, Фон Нейман, считал, что первым шагом в анализе любой игры должно быть представление её в нормальной форме. Но в случае некоторых игр, таких как шахматы, такая форма является не самым практическим вариантом представления игры, поскольку количество возможных стратегий в этой игре превышает предполагаемое количество электронов во всей вселенной. И даже когда нормальная форма игры не является очень объемной, часто намного проще использовать для анализа развернутую форму игры.
В теории игр обычно используется аналогия с деревом при описании игры в развёрнутой форме. Каждый ход соответствует точке, которая называется узлом, в котором дерево разветвляется. Корень дерева соответствует первому ходу в игре. Ветки, исходящие из каждого узла дерева, отображают возможные варианты ходов, которые могут быть выбраны в данном узле. Листья дерева соответствуют различным исходам игры, при этом на каждом листе должны быть указаны выигрыши каждого игрока. Мы также должны обозначить, какой из игроков делает ход в каждом узле и что он в момент хода знает о событиях, которые произошли в игре ранее.
Такие игры, в которых всё, что ранее происходило в игре, известно игрокам, называются играми с совершенной информацией.
День рождения Иа-Иа
Все мы помним историю, про то, как Винни-Пух нёс на день рождения ослику Иа-Иа горшочек мёда. Но по дороге Вини-Пух проголодался. Перед ним встал нелегкий выбор: съесть мед из горшочка, который он нес в подарок Иа-Иа, или все-таки доставить этот подарок в целости и сохранности. Что было дальше, мы все знаем: Винни-Пух съел мёд и подарил Иа-Иа пустой горшочек. И что самое интересное, Иа-Иа его с радостью принял. Как ни странно, но их действия являются рациональными и равновесными по Нэшу. Таким образом, в этой ситуации разворачивается стратегическое взаимоотношение.
Сначала Винни-Пух решает, съесть мед из горшочка или нет, а потом уже Иа-Иа, зная о том, какое решение принял Винни-Пух, в свою очередь решает, принимать этот подарок или не принимать его.
Давайте подумаем, как устроены предпочтения игроков на множестве возможных исходов.
1. С одной стороны, Винни-Пух очень голоден. С другой стороны, ему хочется порадовать Иа-Иа, подарив тому замечательный подарок. Лучше всего для Винни-Пуха было бы, если бы он съел мед, а Иа-Иа все равно бы согласился принять в подарок этот горшочек.
2. Однако если сравнивать средние альтернативы, то Винни-Пуху было бы лучше все-таки не есть мед при условии, что Иа-Иа примет подарок, чем съесть мед, но потом получить отказ от Иа-Иа.
3. Наконец, хуже всего Винни было бы, если бы он не ел мед, а Иа-Иа все равно бы отказался от его горшочка с медом.
Предпочтения у ослика Иа-Иа устроены так.
1. Для него принять подарок всегда лучше, чем отказаться от него. Ведь иметь что-то лучше, чем этого не иметь.
2. Но при этом получить полный горшочек с медом для Иа-Иа было бы лучше, чем получить пустой.
Описанное взаимодействие можно представить в виде дерева игры.
Данную игру мы будем решать с помощью обратной индукции, то есть мы пойдем от возможных конечных точек игры к её началу.
Давайте начнем решение этой игры с ситуации, в которой Иа-Иа окажется, если ему принесут пустой горшочек. Представим себя на месте Иа-Иа. К нам пришел Винни-Пух, подарил пустой горшочек, что делать? У нас есть два возможных действия: мы можем либо принять этот горшочек, и тогда наш платеж будет равен пяти, либо отказаться от него, и тогда наш платеж будет равен нулю. Мы — рациональный игрок. Соответственно, мы выбираем то действие, которое приносит нам большую полезность. Соответственно, мы принимаем этот горшочек. Отметим наш выбор чёрной полоской.
Если вдруг Винни-Пух принесет нам полный горшочек, то у нас снова есть два возможных действия. Если мы примем этот подарок, то получим платеж, равный десяти, а если откажемся от него, то платеж, равный нулю. Десять больше нуля, соответственно, на этой подыгре мы всегда будем выбирать подарок принимать.
Таким образом, мы проанализировали оптимальные действия Иа-Иа на любой подыгре, в которой он может оказаться. Мы проанализировали все последние подыгры этой игры и теперь можем откатиться на одну подыгру назад.
Теперь уже ход принадлежит Винни-Пуху. Он должен принять решение, что делать: есть мед или не есть его? Мы считаем, что все игроки видят дерево игры. Соответственно, Винни-Пух тоже может проанализировать оптимальные действия Иа-Иа в каждой из подыгр и, зная, как будет вести себя рациональный Иа-Иа в той или иной ситуации, Винни-Пух может предсказать, какой платеж будет у него при принятии того или иного решения. Соответственно, Винни-Пух, принимая решение о том, есть мед или не есть его, должен сравнить свои платежи в первом и во втором случае при условии, что Иа-Иа дальше будет играть оптимально. Если Винни-Пух съест мед, то Иа-Иа дальше примет подарок, и тогда платеж Винни-Пуха будет равен десяти. Если Винни-Пух не съест мед, и Иа-Иа примет подарок, то тогда платеж Винни-Пуха будет равен пяти. Поэтому, сравнивая эти два возможных платежа, мы приходим к выводу, что рациональный Винни-Пух мед съест. Его платеж действительно будет равен десяти.
Тот алгоритм, которым мы сейчас решили эту игру и узнали, как она будет развиваться, называется алгоритмом обратной индукции. Почему алгоритмом обратной индукции? Мы решали эту игру с конца. Мы сначала рассмотрели подыгры последнего уровня. Это такие подыгры, в которых, когда кто-то сделает свой ход, игра закончится, придет в терминальную вершину. Соответственно, проанализировать оптимальное поведение игрока в такой вершине очень просто — достаточно сравнить те платежи, которые он получает в различных терминальных вершинах. После того как мы проанализировали оптимальное поведение игрока в подыграх последнего уровня, мы можем откатиться на один уровень назад и проанализировать поведение всех игроков в подыграх предпоследнего уровня. Причем, анализируя это поведение, мы можем опираться на информацию о том, как будут вести себя рациональные игроки на подыграх последнего уровня и так далее. Проанализировав подыгры предпоследнего уровня, откатываемся еще на один уровень назад, потом еще на один уровень назад. И поскольку у нас конечная игра, рано или поздно мы дойдем до вершины, из которой все начинается. И тогда мы закончим этот анализ. Мы на каждой подыгре найдем оптимальное действие каждого из игроков. Вот именно поэтому — что мы движемся назад и фактически опираемся на информацию о том, что будут делать игроки на последующих подыграх, — именно поэтому алгоритм называется алгоритмом обратной индукции. Иногда его еще называют по имени авторов этого алгоритма — это математики Цермело и Кун. Его называют алгоритмом Цермело — Куна.
Обратная индукция является спорным предметом, однако совершенно очевидно, что мы всегда можем применить этот метод для нахождения максимальных выигрышей игроков в конечных играх с совершенной информацией, если у нас есть мощный компьютер и достаточно много времени. И возможно, что когда-нибудь, ей станет подвластны и шахматы.
Борьба полов
Представим себе, что Алиса и Боб- молодожены, которые проводят медовый месяц в Санкт-Петербурге. За завтраком они думают, куда им пойти вечером: на балет или на футбол, но не приходят к компромиссу. Затем они расстаются на улице, чтобы независимо друг от друга выбрать один из этих вариантов.
Предпочтения супругов таковы, что вечером они хотели бы оказаться в одном месте, но жене больше нравится балет, а мужу —футбол.
Мужу лучше оказаться вместе с женой на балете, чем одному на футболе.
Жене лучше пойти на футбол с мужем, чем пойти одной на балет
Запишем выигрыши игроков в таблицу. Найдем наилучшие ответы игроков на стратегии противников. Наилучшим ответом мужа на стратегию жены футбол, будет стратегия футбол. А лучшим ответом на стратегию балет, будет стратегия балет. Проделаем тоже самое и для жены. Итак, мы с вами видим, что в этой игре имеются два равновесных по Нэшу профиля стратегий: футбол; футбол и балет; балет. Как же тогда решается данная игра? Доминирующих стратегий в ней нет, равновесий по Нэшу два. Решение этой проблемы заключается в том, что мы до сих пор рассматривали только чистые стратегии, но на ряду с ними существуют также смешанные стратегии, которые мы также должны принимать во внимание.
Применение смешанных стратегий состоит в том, что игрок случайным образом выбирает одну из чистых стратегий с определённой вероятностью. Естественно, у любого нормального человека возникают возражения, что только сумасшедшие принимают серьёзные решения случайным образом, но на самом деле люди часто используют смешанные стратегии, не задумываясь об этом.
Использование смешанных стратегий является вполне разумным для игры в орлянку, о которой мы уже рассказывали вам. Любой ребёнок знает, что решением здесь является случайный выбор между орлом и решкой. И если оба игрока используют смешанные стратегии, то в результате они приходят к равновесию по Нэшу. При этом каждый игрок побеждает в половине случаев, и это является их наилучшим ответом на стратегию противника.
В игре «Борьба полов» муж любит футбол в два раза больше, чем балет, поэтому жена должна выбирать футбол в два раза реже чем балет, чтобы ожидаемый средний выигрыш Боба от каждой его чистой стратегии был одинаков. Так как мужу в этом случае не важно, какую из стратегий выбирать, все его стратегии для него будут одинаково хороши, в том числе и смешенная стратегия, при которой он выбирает футбол в два раза чаще чем балет. Но применение им этой стратегии приводит к тому, что жене тоже становится не важно, какую стратегию принимать. Таким образом цепочка замыкается, и мы приходим к равновесию по Нэшу в смешенных стратегиях, при муж и жена выбирают предпочтительные для них варианты в двух случаях их трёх.
История
В 1944 году фон Нейман и Оскар Моргенштерн публикуют работу «Теория игр и экономическое поведение». В ней предпринята попытка построения системы аксиом теории игр. В этой работе фон Нейман и Моргенштерн рассматривают игры двух лиц с нулевой суммой, игры n лиц с нулевой суммой. Они рассматривают в том числе и игры с ненулевой суммой, однако на тот момент никаких систематических результатов для игр в общем случае получено не было.
Это изменилось в 1950 году. Именно тогда, в 50-м и 51-м годах, Джон Нэш в своих статьях «Точки равновесия в играх n лиц» и «Некооперативные игры» вводит понятие равновесия в смешанных стратегиях для игр n лиц, обратите внимание, уже для игр в общем случае, не только для игр с нулевой суммой. И вот Джон Нэш доказывает, что любая конечная игра имеет хотя бы одно равновесие в смешанных стратегиях. Этот результат обобщает результат фон Неймана, который тот доказал для конечных игр двух лиц с нулевой суммой. Далее теория игр начинает развиваться со стремительной быстротой.
В том же 1950 году американские математики Мелвин Дрешер и Мерил Флад, которые работали в корпорации RAND, проводят эксперимент. Они хотят посмотреть, будет ли играться равновесие Нэша в игре, в которой это равновесие не является Парето-оптимальным. Они приводят формальное описание этой игры и просят в нее сыграть различных игроков. Эта модель фактически позволяет ответить, насколько склонен человек к сотрудничеству в ситуации, когда у него есть стимулы к эгоистическому поведению. Альберт Такер дает этой модели красивую интерпретацию. Формулировка Такера получает название «Дилемма заключенного». Именно в этой формулировке эта игра рассказывается всем в настоящее время.
1960 год. Выходит книга Томаса Шеллинга «Стратегия конфликта». В этой книге Шеллинг подробно обсуждает принципы угроз, контругроз, сдерживания, конфликта интересов, координации и других принципов, которые используются во время дипломатических переговоров.
В 1965 году Райнхард Зельтен предлагает идею рафинирования равновесий Нэша в играх в развернутой форме. Он вводит концепцию равновесия Нэша, совершенного на подыграх. Зельтен замечает, что из всех равновесий Нэша некоторые являются более хорошими, в том смысле, что они обладают некоторыми дополнительными хорошими свойствами, а именно на каждой подыгре каждый игрок играет оптимально при фиксированных стратегиях всех остальных.
В 1966 году Джон Харсаньи в своей работе определяет, чем кооперативные игры отличаются от некооперативных. Кооперативными называются игры, в которых различные договоренности, обещания и угрозы являются связывающими, то есть, однажды пообещав осуществить угрозу в том или ином случае, мы гарантируем, что она будет осуществлена. Если же эти обещания можно нарушать, и каждый игрок сможет отклоняться от этих обещаний, то тогда такие игры — некооперативные.
Кеннет Джордж Бинмор
Выдающимся специалистом в теории игр является известный британский экономист Кен Бинмор. Он является автором многих книг по теории игр и её применения. Некоторые из которых, такие как «Fun and Games”, “Playing for real”, «Теория игр: очень краткое введение» вдохновляли нас для создания этого доклада. Кен Бинмор систематизировал все теоретические концепции теории игр, известные на данный момент, и активно применяет их на практике. Так, например, он организовал британский аукцион по продаже частот для сотовой связи (англ. UK 3G Spectrum Auction), принёсшего британскому правительству £23 млрд.
Заключение
Закончить экскурс в мир теории игр хотелось бы обзором проделан-ной работы, а также перспектив и проблем данной области науки. Несомненно, что теория игр находит свое применение во многих сферах жизни: возможно, их даже больше, чем принято считать. Ведь «вся наша жизнь – игра», как верил Вильям Шекспир. Невозможно постоянно добиваться вы-сокого результата, лишь слепо полагаясь на удачу. Необходимо четкое осознание и координация действий, просчет стратегий и выбор выигрышного пути.
Актуальной проблемой, на наш взгляд, является весьма малая доля отечественных исследований в общей теоретической базе данной научной дисциплины. Большинство русскоязычных трудов, как правило, специали-зированы на конкретной тематике, а зарубежные источники нуждаются в адаптации для русскоговорящего читателя и исследователя.
Для решения данной проблемы мы предлагаем следующее:
1. Организовать развитие теории игр в нашей стране.
2. Сформировать полную базу научных материалов в данной области.
3. Уделять должное внимание переводам работ зарубежных авторов.
4. Популяризировать указанную тематику в более широких кругах, нежели исследовательские.