Теория игр: история и применение. Математическая теория игр. Примеры записи и решения игр из жизни

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

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

Стратегические взаимодействия встречаются практически в любой сфере нашей жизни. Пример из экономики: несколько компаний, конкурирующих на рынке, при принятии решений должны оглядываться на действия конкурентов. Если мы будем говорить о политике, то кандидаты, соперничающие на выборах, объявляя свою предвыборную платформу, естественно, принимают во внимание позиции других кандидатов по отношению к этому вопросу. А если мы изучаем взаимодействие людей в обществе, то с помощью теории игр можно узнать много интересного о склонности людей к кооперации.

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

Сначала по реальной жизненной ситуации нужно построить формальную модель. Как правило, в модели нужно отразить три основные характеристики жизненной ситуации: кто взаимодействует друг с другом (такие агенты в теории игр называются игроками), какие решения могут принимать игроки и какие платежи они в результате этого взаимодействия получают. Формальная модель и называется игрой.

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

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

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

Конечно, Джон Нэш не является единоличным автором теории игр. Теория игр как самостоятельная наука начала развиваться чуть раньше, в начале ХХ века. Первые попытки формально определить игры, стратегии игроков и концепции решения игр восходят к именам Эмиля Бореля и Джона фон Неймана. Однако именно Нэш предъявил концепцию равновесия, которая позволяет гарантированно найти решение в конечных играх. В честь автора теоремы о существовании равновесия в смешанных стратегиях в конечных играх это равновесие стали называть равновесием Нэша.

Врученная в 1994 году первая Нобелевская премия за результаты в области теории игр (Джону Нэшу, Райнхарду Зелтену и Джону Харсаньи) фактически утвердила статус теории игр как самостоятельного научного направления со своими задачами и методами их решений. Последовавшие за этим еще несколько Нобелевских премий вручались как за фундаментальные теоретико-игровые результаты, так и за приложения теории игр к той или иной стороне нашей жизни. В ведущих университетах мира на программах и по экономике, и по политическим наукам теория игр обязательно входит в стандартный набор курсов. Часто ее изучают и психологи, и математики.

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

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

Наконец-то руки дошли продолжить рассказ о теории игр реальными примерами её использования в нашем проекте. Но перед этим осуществим небольшой экскурс по классификации игр, чтобы с помощью неё уже описать вам по всей красе два наших игровых эвента: «Большой Бой» и «Захват Квартала».

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

Идея классификации

Все существующие ныне игры делятся на два типа. Но вот какие именно

Математики всегда питали слабость к двоичным и бинарным системам, и авторы теории игр - не исключение. Поэтому при создании игровой классификации они поступили крайне хитро: определили несколько суб-классификаций (дефиниций), в каждой из которых может быть лишь два взаимоисключающих вида игр:
- Классификация по равноправию ходов : симметричные и несимметричные игры.
- Классификация по размеру выигрыша : игры с нулевой и ненулевой суммой.
- Классификация по возможности кооперации игроков : кооперативные и некооперативные игры.
- Классификация по порядку совершения ходов : параллельные и последовательные игры.
- Классификация по доступной игрокам информации : игры с полной и неполной информацией.

Таким образом, любая игра могла быть описана с помощью её положения в той или иной дефиниции. Чем больше дефиниций - тем точнее описана игра.

Так, например, знакомая многим игра парчис (она же шеш-беш, она же лудо, она же патолли, она же мандавошка) является:
- симметричной;
- с нулевой суммой;
- кооперативной;
- последовательной;
- с полной информацией.

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

Но хватит прелюдий, классифицируем.

Симметричные и несимметричные игры

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

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

Примеры определенно симметричных игр:
- шашки;
- шахматы;
- домино;
- любые карточные игры.

Есть ли в VirCities примеры симметричных игровых ситуаций?

Почти, но не совсем.

Можно было бы сказать, что таковым может быть момент после вайпа, когда обнулятся все параметры, но тогда мы бы слукавили. Потому что изначально в игре уже будет какое-то количество каких-то компаний, корпораций и партий, у которых уже будут какие-то владельцы-игроки. Но кто будет стоять у руля? Самые активные альфа-тестеры, разумеется.

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

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

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

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

Игры с нулевой и с ненулевой суммой

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

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

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

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

Из истории теории игр

История теории игр как самостоятельной дисциплины начинается в 1944 году, когда Джон фон Нейман и Оскар Моргенштерн опубликовали книгу "Теория игр и экономическое поведение" ("Theory of Games and Economic Behavior"). Хотя примеры теории игр встречались и раньше: трактат Вавилонского Талмуда о разделе имущества умершего мужа между его жёнами, карточные игры в 18-м веке, развитие теории шахматной игры в начале 20-го века, доказательство теоремы о минимаксе того же Джона фон Неймана в 1928 году, без которой не было бы никакой теории игр.

В 50-х годах 20-го века Мелвин Дрешер и Мерил Флод из Rand Corporation первыми экспериментально применили дилемму заключённого, Джон Нэш в работах о состоянии равновесия в играх двух лиц развил понятие равновесия Нэша.

Рейнхард Сэлтен в 1965 году опубликовал книгу "Обработка олигополии в теории игр по требованию" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), с которой применение теории игр в экономике получило новую движущую силу. Шагом вперёд в эволюции теории игр связан с работой Джона Мейнарда Смита "Эволюционно стабильная стратегия" ("Evolutionary Stable Strategy", 1974). Дилемма заключённого была популяризована в книге Роберта Аксельрода "Эволюция кооперации" ("The Evolution of Cooperation"), опубликованной в 1984 году. В 1994 году именно за вклад в теорию игр Нобелевской премии были удостоены Джон Нэш, Джон Харсаньи и Рейнхард Сэлтен.

Теория игр в жизни и бизнесе

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

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

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

Военный кофликт, по определению, есть столкновение интересов, в котором ни одна из сторон не распоряжается полностью переменными, определяющими исход, который решается рядом битв. Можно просто считать исход выигрышем или проигрышем и приписать им численные значения 1 и 0.

Одна из самых простых конфликтных ситуаций, которая может быть записана и решена в теории игр - дуэль, представляющая собой конфликт двух игроков 1 и 2, имеющих соответственно p и q выстрелов. Для каждого игрока существует функция, указывающая вероятность того, что выстрел игрока i в момент времени t даст попадание, которое окажется смертельным.

В итоге теория игр приходит к такой формулировке некоторого класса столкновений интересов: имеются n игроков, и каждому нужно выбрать одну возможность из стого определённого набора, причём при совершении выбора у игрока нет никаких сведений о выборах других игроков. Область возможных выборов игрока может содержать такие элементы, как "ход тузом пик", "производство танков вместо автомобилей", или в общем смысле, стратегию, определяющую все действия, которые нужно совершить во всех возможных обстоятельствах. Перед каждым игроком стоит задача: какой выбор он должен сделать, чтобы его частное влияние на исход принесло ему как можно больший выигрыш?

Математическая модель в теории игр и формализация задач

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

заинтересованных сторон;
возможных действий с каждой стороны;
интересов сторон.

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

Реальная конфликтная ситуация не всегда, а игра (в понятии теории игр) - всегда - протекает по определённым правилам , которые точно определяют:

варианты действий игроков;
объём информации каждого игрока о поведении партнёра;
выигрыш, к которому приводит каждая совокупность действий.

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

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

Для игры характерна неопределённость результата . Причины неопределённости можно распределить по следующим группам:

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

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

Целью теории игр является определение оптимальной стратегии для каждого игрока. Определить такую стратегию - значит решить игру. Оптимальность стратегии достигается, когда один из игроков должен получить максимальный выигрыш, при том, что второй придерживается своей стратегии. А второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии.

Классификация игр

Классификация по числу игроков (игра двух и более лиц). Игры двух лиц занимают центральное место во всей теории игр. Основным понятием теории игр для игры двух лиц является обобщение весьма существенной идеи равновесия, которая естественно появляется в играх двух лиц. Что же касается игр n лиц, то одна часть теории игр посвящена играм, в которых сотрудничество между игроками запрещено. В другой части теории игр n лиц предполагается, что игроки могут сотрудничать для взаимной пользы (см. далее в этом параграфе о некооперативных и кооперативных играх).
Классификация по числу игроков и их стратегиям (число стратегий не менее двух, может быть бесконечностью).
Классификация по количеству информации относительно прошлых ходов: игры с полной информацией и неполной информацией. Пусть есть игрок 1 - покупатель и игрок 2 - продавец. Если у игрока 1 нет полной информации о действиях игрока 2, то игрок 1 может и не различить две альтернативы, между которыми ему предстоит сделать выбор. Например, выбирая между двумя видами некоторого товара и не зная о том, что по некоторым признакам товар A хуже товара B , игрок 1 может не видеть различия между альтернативами.
Классификация по принципам деления выигрыша : кооперативные, коалиционные с одной стороны и некооперативные, бескоалиционные с другой стороны. В некооперативной игре , или иначе - бескоалиционной игре , игроки выбирают стратегии одновременно, не зная, какую стратегию выберет второй игрок. Коммуникация между игроками невозможна. В кооперативной игре , или иначе - коалиционной игре , игроки могут объединяться в коалиции и предпринимать коллективные действия, чтобы увеличить свои выигрыши.
Конечная игра двух лиц с нулевой суммой или антогонистическая игра – это стратегическая игра с полной информацией, в которой участвуют стороны с противоположными интересами. Анатагонистическими играми являются матричные игры .

Классический пример из теории игр - дилемма заключённого

Двух подозреваемых берут под стражу и изолируют друг от друга. Окружной прокурор убеждён, что они совершили тяжкое преступление, но не имеет достаточных доказательств, чтобы предъявить им обвинение на суде. Он говорит каждому из заключённых, что у него имеется две альтернативы: признаться в преступлении, которое по убеждению полиции он совершил, или не признаваться. Если оба не признаются, то окружной прокурор предъявит им обвинение в каком-либо незначительном преступлении, например, мелкая кража или незаконное владение оружием, и они оба получат небольшое наказание. Если они оба признаются, то будут подлежать судебной ответственности, но он не потребует самого строгого приговора. Если же один признается, а другой нет, то признавшемуся приговор будет смягчён за выдачу сообщника, в то время как упорствующий получит "на полную катушку".

Если эту стратегическую задачу сформулировать в сроках заключения, то она сводится к следующему:

Таким образом, если оба заключённых не признаются, они получат по 1 году каждый. Если оба признаются, то каждый получит по 8 лет. А если один признается, другой не признается, то тот, который признался отделается тремя месяцами заключения, а тот, который не признается, получит 10 лет. Приведённая выше матрица правильно отражает дилемму заключённого: перед каждым стоит вопрос - признаться или не признаться. Игра, которую окружной прокурор предлагает заключённым, представляет собой некооперативную игру или иначе - бескоалиционную игру . Если бы оба заключённых имели возможность сотрудничать (то есть игра была бы кооперативной или иначе коалиционной игрой ), то оба не признались бы и получили по году тюрьмы каждый.

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

Переходим теперь к рассмотрению решений примеров распространённых классов игр, для которых в теории игр существуют методы исследования и решения.

Пример формализации некооперативной (бескоалиционной) игры двух лиц

В предыдущем параграфе мы уже рассмотрели пример некооперативной (бескоалиционной) игры (дилемма заключённого). Давайте закрепим наши навыки. Для этого подойдёт также классический сюжет, навеянный "Приключениями Шерлока Холмса" Артура Конан Дойля. Можно, конечно, возразить: пример не из жизни, а из литературы, но ведь Конан Дойль не зарекомендовал себя как писатель-фантаст! Классический ещё и потому, что задание выполнено Оскаром Моргенштерном, как мы уже установили - одним из основателей теории игр.

Пример 1. Будет приведено сокращённое изложение фрагмента одного из "Приключений Шерлока Холмса". Согласно известным понятиям теории игр составить модель конфликтной ситуации и формально записать игру.

Шерлок Холмс намерен отправиться из Лондона в Дувр с дальнейшей целю попасть на континент (европейский), чтобы спастись от профессора Мориарти, который преследует его. Сев в поезд, он увидел на вокзальной платформе профессора Мориарти. Шерлок Холмс допускает, что Мориарти может выбрать особый поезд и обогнать его. У Шерлока Холмса две альтернативы: продолжать поездку до Дувра или сойти на станции Кентерберри, являющейся единственной промежуточной станцией на его маршруте. Мы принимаем, что его противник достаточно разумен, чтобы определить возможности Холмса, поэтому перед ним те же две альтернативы. Оба противника должны выбрать станцию, чтобы сойти на ней с поезда, не зная, какое решение примет каждый из них. Если в результате принятия решения оба окажутся на одной и той же станции, то можно однозначно считать, что Шерлок Холмс будет убит профессором Мориарти. Если же Шерлок Холмс благополучно доберётся до Дувра, то он будет спасён.

Решение. Героев Конан Дойля можем рассматривать как участников игры, то есть игроков. В распоряжении каждого игрока i (i =1,2) две чистые стратегии:

сойти в Дувре (стратегия s i1 (i =1,2) );
сойти на промежуточной станции (стратегия s i2 (i =1,2) )

В зависимости от того, какую из двух стратегий выберет каждый из двух игроков, будет создана особая комбинация стратегий как пара s = (s 1 , s 2 ) .

Каждой комбинации можно поставить в соответствие событие - исход попытки убийства Шерлока Холмса профессором Мориарти. Составляем матрицу данной игры с возможными событиями.

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

Пример формализации и решения кооперативной (коалиционной) игры n лиц

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

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

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

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

Для игры n обозначим множество всех её игроков как N = {1,2,...,n} Любое непустое подмножество множества N обозначим как Т (включая само N и все подмножества, состоящие из одного элемента). На сайте есть занятие "Множества и операции над множествами ", которое при переходе по ссылке открывается в новом окне.

Характеристическая функция обозначается как v и область её определения состоит из возможных подмножеств множества N . v (T ) - значение характеристической функции для того или иного подмножества, например, доход, полученный коалицией, в том числе, возможно, состоящей из одного игрока. Это важно по той причине, что теория игр требует проверить наличие супераддитивности для значений характеристической функции всех непересекающихся коалиций.

Для двух непустых коалиций из подмножеств T 1 и T 2 аддитивность характеристической функции кооперативной (коалиционной) игры записывается так:

А супераддитивность так:

Пример 2. Трое студентов музыкальной школы подрабатывают в разных клубах, свою выручку они получают от посетителей клубов. Установить, выгодно ли им объединять свои силы (если да, то с какими условиями), используя понятия теории игр для решения кооперативных игр n лиц, при следующих исходных данных.

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

у скрипача 600 единиц;
у гитариста 700 единиц;
у певицы 900 единиц.

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

скрипач + гитарист зарабатывали 1500 единиц;
скрипач + певица зарабатывали 1800 единиц;
гитарист + певица зарабатывали 1900 единиц;
скрипач + гитарист + певица зарабатывали 3000 единиц.

Решение. В этом примере число участников игры n = 3 , следовательно, область определения характеристической функции игры состоит из 2³ = 8 возможных подмножеств множества всех игроков. Перечислим все возможные коалиции T :

коалиции из одного элемента, каждая из которых состоит из одного игрока - музыканта: T {1} , T {2} , T {3} ;
коалиции из двух элементов: T {1,2} , T {1,3} , T {2,3} ;
коалиция из трёх элементов: T {1,2,3} .

Каждому из игроков присвоим порядковый номер:

скрипач - 1-й игрок;
гитарист - 2-й игрок;
певица - 3-й игрок.

По данным задачи определим характеристическую функцию игры v :

v(T{1}) = 600 ; v(T{2}) = 700 ; v(T{3}) = 900 ; эти значения характеристической функции определены исходя из выигрышей соответственно первого, второго и третьего игроков, когда они не объединяются в коалиции;

v(T{1,2}) = 1500 ; v(T{1,3}) = 1800 ; v(T{2,3}) = 1900 ; эти значения характеристической функции определены по выручке каждой пары игроков, объединившихся в коалиции;

v(T{1,2,3}) = 3000 ; это значение характеристической функции определено по средней выручке в случае, когда игроки объединялись в тройки.

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

Как выполняются условия супераддитивности в этом примере? Определим, как игроки образуют непересекающиеся коалиции T 1 и T 2 . Если часть игроков входят в коалицию T 1 , то все остальные игроки входят в коалицию T 2 и по определению эта коалиция образуется как разность всего множества игроков и множества T 1 . Тогда, если T 1 - коалиция из одного игрока, то в коалиции T 2 будут второй и третий игроки, если в коалиции T 1 будут первый и третий игроки, то коалиция T 2 будет состоять только из второго игрока, и так далее.

И Оскар Моргенштерн стали основателями нового интересного направления математики, которое получило название "теория игр". В 1950-е годы этим направлением заинтересовался молодой математик Джон Нэш. Теория равновесия стала темой его диссертации, которую он написал, будучи в возрасте 21 год. Так родилась новая стратегия игр под названием «Равновесие по Нэшу», заслужившая Нобелевскую премию спустя много лет - в 1994 году.

Долгий разрыв между написанием диссертации и всеобщим признанием стал испытанием для математика. Гениальность без признания вылилась в серьезные ментальные нарушения, но и эту задачу Джон Нэш смог решить благодаря прекрасному логическуму разуму. Его теория "равновесие по Нэшу" удостоилась премии Нобеля, а его жизнь экранизации в фильме «Beautiful mind» («Игры разума»).

Кратко о теории игр

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

Теория игр изучает поведение участников (агентов) в условиях взаимодействия друг с другом по типу игры, когда исход зависит от решения и поведения нескольких людей. Участник принимает решения, руководствуясь своими прогнозами относительно поведения остальных, что и называется игровой стратегией.

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

Дилемма заключенного и научный прорыв

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

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

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

Пример дилеммы заключенного

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

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

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

Цепь логических умозаключений

Итак, преступник А рассматривает следующие варианты:

Я молчу и молчит мой напарник — мы оба получим по 1 году тюрьмы.
Я сдаю напарника и он сдает меня — мы оба получим по 2,5 года тюрьмы.
Я молчу, а напарник меня сдает — я получу 5 лет тюрьмы, а он свободу.
Я сдаю напарника, а он молчит - я получаю свободу, а он 5 лет тюрьмы.

Приведем матрицу возможных решений и исходов для наглядности.

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

Вопрос состоит в том, что выберет каждый участник?

«Молчать, нельзя говорить» или «молчать нельзя, говорить»

Чтобы понять выбор участника, нужно пройти по цепочке его размышлений. Следуя рассуждениям преступника А: если я промолчу и промолчит мой напарник, мы получим минимум срока (1 год), но я не могу узнать, как он себя поведет. Если он даст показания против меня, то мне также лучше дать показания, иначе я могу сесть на 5 лет. Лучше мне сесть на 2,5 года, чем на 5 лет. Если он промолчит, то мне тем более нужно дать показания, поскольку так я получу свободу. Точно так же рассуждает и участник B.

Нетрудно понять, что доминирующая стратегия для каждого из преступников - это дача показаний. Оптимальная точка этой игры наступает тогда, когда оба преступника дают показания и получают свой «приз» — 2,5 года тюрьмы. Теория игр Нэша называет это равновесием.

Неоптимальное оптимальное решение по Нэшу

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

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

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

Эгоистично или рационально

Теория равновесия Нэша дала потрясающие выводы, опровергнувшие существующие до этого принципы. Например, Адам Смит рассматривал поведение каждого из участников как абсолютно эгоистичное, что и приводило систему в равновесие. Эта теория носила название «невидимая рука рынка».

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

Чисто мужской эксперимент

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

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

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

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

Вся наша жизнь игра

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

Конечно, рассмотренные игровые ситуации с преступниками и баром - это всего лишь отличные иллюстрации, демонстрирующие равновесие Нэша. Примеры таких дилемм очень часто возникают на реальном рынке, а особенно это работает в случаях с двумя монополистами, контролирующими рынок.

Смешанные стратегии

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

Рассмотрим два вида стратегии:

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

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

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

Пенальти и смешанная стратегия

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

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

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

И кибернетики , особенно с проявлением интереса к интеллектуальным агентам .

История

Оптимальные решения или стратегии в математическом моделировании предлагались ещё в XVIII в. Задачи производства и ценообразования в условиях олигополии , которые стали позже хрестоматийными примерами теории игр, рассматривались в XIX в. А. Курно и Ж. Бертраном . В начале XX в. Э. Ласкер , Э. Цермело, Э. Борель выдвигают идею математической теории конфликта интересов.

Математическая теория игр берёт своё начало из неоклассической экономики . Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» (англ. Theory of Games and Economic Behavior ).

Эта область математики нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Нэша , нобелевского лауреата по экономике и учёного в области теории игр; а в по мотивам книги был снят фильм «Игры разума ». Некоторые американские телевизионные шоу, например, «Friend or Foe », «Alias» или «NUMB3RS», периодически ссылаются на теорию в своих эпизодах.

Математическая теория игр сейчас бурно развивается, рассматриваются динамические игры. Однако математический аппарат теории игр затратен . Его применяют для оправданных задач: политика, экономика монополий и распределения рыночной власти и т. п. Ряд известных ученых стали Нобелевскими лауреатами по экономике за вклад в развитие теории игр, которая описывает социально-экономические процессы. Дж. Нэш , благодаря своим исследованиям в теории игр, стал одним из ведущих специалистов в области ведения «холодной войны» , что подтверждает масштабность задач, которыми занимается теория игр.

Представление игр

Игры представляют собой строго определённые математические объекты. Игра образуется игроками, набором стратегий для каждого игрока и указания выигрышей, или платежей , игроков для каждой комбинации стратегий. Большинство кооперативных игр описываются характеристической функцией, в то время как для остальных видов чаще используют нормальную или экстенсивную форму. Характеризующие признаки игры как математической модели ситуации:

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

Экстенсивная форма

Основная статья: Экстенсивная форма игры

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

На рисунке слева - игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает - выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй - A (для каждого из них это оптимальные стратегии ); тогда они получат соответственно 8 и 2 очка.

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

Нормальная форма

	Игрок 2 стратегия 1	Игрок 2 стратегия 2
Игрок 1 стратегия 1	4 , 3	–1 , –1
Игрок 1 стратегия 2	0 , 0	3 , 4
Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии.

В нормальной, или стратегической, форме игра описывается платёжной матрицей . Каждая сторона (точнее, измерение) матрицы - это игрок, строки определяют стратегии первого игрока, а столбцы - второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки. В примере справа, если игрок 1 выбирает первую стратегию, а второй игрок - вторую стратегию, то на пересечении мы видим (−1, −1), это значит, что в результате хода оба игрока потеряли по одному очку.

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

Характеристическая функция

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

Основания такого подхода можно найти ещё в книге фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция C , то против неё выступает коалиция N \ C . Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2 N , где N - количество игроков), то выигрыш для C будет некоторой характеристической величиной , зависящей от состава коалиции. Формально игра в такой форме (также называемая TU-игрой ) представляется парой (N, v) , где N - множество всех игроков, а v: 2 N → R - это характеристическая функция.

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

Применение теории игр

Теория игр как один из подходов в прикладной математике применяется для изучения поведения человека и животных в различных ситуациях. Первоначально теория игр начала развиваться в рамках экономической науки, позволив понять и объяснить поведение экономических агентов в различных ситуациях. Позднее область применения теории игр была расширена на другие социальные науки; в настоящее время теория игр используется для объяснения поведения людей в политологии, социологии и психологии. Теоретико-игровой анализ был впервые использован для описания поведения животных Рональдом Фишером в 30-х годах XX века (хотя даже Чарльз Дарвин использовал идеи теории игр без формального обоснования). В работе Рональда Фишера не появляется термин «теория игр». Тем не менее, работа по существу выполнена в русле теоретико-игрового анализа. Разработки, сделанные в экономике, были применены Джоном Майнардом Смитом в книге «Эволюция и теория игр». Теория игр используется не только для предсказания и объяснения поведения; были предприняты попытки использовать теорию игр для разработки теорий этичного или эталонного поведения. Экономисты и философы применяли теорию игр для лучшего понимания хорошего (достойного) поведения.

Описание и моделирование

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

Нормативный анализ (выявление наилучшего поведения)

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

Типы игр

Кооперативные и некооперативные

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

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

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

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

Симметричные и несимметричные

	А	Б
А	1, 2	0, 0
Б	0, 0	1, 2
Несимметричная игра

Основная статья: Симметричная игра

Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков - симметричные. В частности, таковыми являются: «Дилемма заключённого », «Охота на оленя », «Ястребы и голуби ». В качестве несимметричных игр можно привести «Ультиматум» или «Диктатор».

В примере справа игра на первый взгляд может показаться симметричной из-за похожих стратегий, но это не так - ведь выигрыш второго игрока при профилях стратегий (А, А) и (Б, Б) будет больше, чем у первого.

С нулевой суммой и с ненулевой суммой

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

Многие изучаемые математиками игры, в том числе уже упоминавшаяся «Дилемма заключённого», иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме - это делается введением фиктивного игрока , который «присваивает себе» излишек или восполняет недостаток средств.

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

Категории

Выбор редакции