Теория игр: 5 простых примеров популярных игровых стратегий

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

См. также: Список игр теории игр

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

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

Развёрнутая форма

Основная статья: Развёрнутая форма игры

Игра «Ультиматум» в развёрнутой форме

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

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

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

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

Основная статья: Нормальная форма игры

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

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

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

Основная статья: Кооперативная игра (математика)

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

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

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

Игра в орлянку

В орлянке участвуют Игрок 1 и Игрок 2. Каждый игрок одновременно выбирает орла или решку. Если они угадывают, Игрок 1 получает пенс Игрока 2. Если же нет — Игрок 2 получает монету Игрока 1.

Выигрышная матрица проста…

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

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

Практическое применение: Пенальти

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

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

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

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

Чистые и смешанные стратегии поведения

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

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

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

Рассмотрим это подробнее. Если моя стратегия заключается в том, чтобы класть шарик в правую руку, то Ваша стратегия заключается в том, чтобы сказать, что шарик в правой руке. Это является одним из видов Вашей чистой стратегии. Если я догадываюсь о Вашем ответе, то моей лучшей стратегией будет поменять руку. Это является моим вариантом чистой стратегии. Таким образом, чистые стратегии в нашей игре не приведут к равновесию. Любой Ваш рациональный вариант поведения невыгоден для меня, любой мой рациональный вариант поведения невыгоден Вам. Однако в подобной игре все же существуют мои и Ваши стратегии, являющиеся равновесными для нас обоих. Это означает, что я или Вы будем придерживаться определенного поведения вне зависимости от поведения противоположной стороны. Как выглядят подобные стратегии? Для ответа на этот вопрос давайте осознаем, что какое бы правило я ни изобрел, в конце концов, оно будет применено против меня. Поэтому моим лучшим решением для выбора руки станет … подбросить монетку. На языке теории игр это означает «смешать стратегии». Какую стратегию в этом случае выберете Вы? Зная, что мое поведение определяется случайным образом, Вы также не будет конструировать каких-либо правил угадывания – ведь со временем я их разгадаю и применю против Вас. Поэтому Вашей лучшей стратегией также становится подбросить монетку. Принятие решения на основе подбрасывания монетки стало равновесием в нашей игре.

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

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

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

Теория ходов и ядерный кризис

fait accompli«Альтернатива»см. рисунок 2

1. BW: выбор Соединёнными Штатами блокады и отзыва ракет Советским Союзом по-прежнему считается компромиссом для обоих игроков — (3,3).
2. BM: перед лицом блокады США сохранение Советами ракет на Кубе ведёт к победе СССР (наилучшему для него результату) и капитуляции США (наихудшему для них результату) — (1,4).
3. AM: авиаудар, уничтожающий сохранённые Советским Союзом ракеты, рассматривается «почётным» для США действием (наилучшим для них результатом) и поражением Советов (их наихудшим результатом) — (4,1).
4. AW: авиаудар, уничтожающий отозванные Советами ракеты, считается «позорным» действием США (результатом чуть лучше наихудшего для них) и поражением Советов (результатом чуть лучше наихудшего) — (2,2).

Рисунок 2: Карибский ядерный кризис как «Альтернатива»циклична

Смысл гипотезы

Рациональный игрок при выборе решения пытается максимизировать некоторую величину (благо); кажется естественным в качестве такой величины использовать математическое ожидание блага, появляющегося в результате избранного решения. Однако опыт показывает, что в реальной жизни многие участники лотерей выбирают решение с меньшим математическим ожиданием, но и с меньшим риском. Например, поставленные перед выбором получить тысячу рублей с вероятностью 0,2 % (математическое ожидание — 2 рубля) или получить один рубль с вероятностью 100 % (математическое ожидание — 1 рубль), многие люди предпочтут гарантированную выплату, несмотря на её меньшее математическое ожидание. Для описания такого поведения и была придумана формула ожидаемой полезности.

История

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

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

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

Джон Нэш в 1949 году пишет диссертацию по теории игр, через 45 лет он получает Нобелевскую премию по экономике. Нэш после окончания Политехнического института Карнеги с двумя дипломами — бакалавра и магистра — поступил в Принстонский университет, где посещал лекции Джона фон Неймана. В своих трудах Нэш разработал принципы «управленческой динамики». Первые концепции теории игр анализировали антагонистические игры, когда есть проигравшие и выигравшие за их счёт игроки. Нэш разрабатывает методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили названия «равновесие по Нэшу», или «некооперативное равновесие», в ситуации стороны используют оптимальную стратегию, что и приводит к созданию устойчивого равновесия. Игрокам выгодно сохранять это равновесие, так как любое изменение ухудшит их положение. Эти работы Нэша сделали серьёзный вклад в развитие теории игр, были пересмотрены математические инструменты экономического моделирования. Нэш показывает, что классический подход к конкуренции А. Смита, когда каждый сам за себя, не всегда оптимален. Более выгодны стратегии, когда каждый старается сделать лучше для себя, делая лучше для других.

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

В 1960—1970 гг. интерес к теории игр угасает, несмотря на значительные математические результаты, полученные к тому времени. С середины 1980-х гг. начинается активное практическое использование теории игр, особенно в экономике и менеджменте. За последние 20 — 30 лет значение теории игр и интерес к ней значительно растёт, некоторые направления современной экономической теории невозможно изложить без применения теории игр.

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

Лауреатами премии по экономике памяти Альфреда Нобеля за достижения в области теории игр и экономической теории стали: Роберт Ауман, Райнхард Зелтен, Джон Нэш, Джон Харсаньи, Уильям Викри, Джеймс Миррлис, Томас Шеллинг, Джордж Акерлоф, Майкл Спенс, Джозеф Стиглиц, Леонид Гурвиц, Эрик Мэскин, Роджер Майерсон, Ллойд Шепли, Элвин Рот, Жан Тироль.

Игроки в теории игр.

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

Предположим, два человека должны поделить торт. Обычно в этом примере речь идет о детях: считается, что дети очень любят сладкое и потому хотят получить самый большой кусок, и это позволяет лучше понять ситуацию. Детский индивидуализм — идеальное качество для нужных нам игроков. Дележ торта будет происходить так: ребенок А будет резать торт, а ребенок В — первым выбирать себе кусок. Таким образом, ребенок А должен всегда помнить о ребенке В и о том, что после того, как он разрежет весь торт, В заберет себе самый большой кусок. Это условие является основополагающим для выбора наилучшей стратегии, которая, разумеется, состоит в том, чтобы разрезать торт на две равные части. Любой другой вариант опасен. Если, например, А подумает, что В — очень хороший и воспитанный ребенок и потому возьмет себе кусок поменьше, то он начнет резать торт на неравные куски. Но это решение содержит много рисков и основывается на догадках или дополнительной информации, которая не имеет ничего общего с игрой.

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

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

Напоследок, видео, в котором рассказывается что такое теория игр простыми словами)

О курсе

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

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

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

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

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

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

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