В результате освоения данной главы студент должен:

знать

• определение равновесия по Нэшу (как в чистых, так и в смешанных стратегиях);
• основные свойства равновесия по Нэшу;
• теоремы, формулирующие условия существования равновесия по Нэшу в стратегических играх;
• определение понятия "равновесие дрожащей руки";

уметь

Решать задачу нахождения равновесия по Нэшу в биматричных играх (в том числе графическим методом для игр);

владеть

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

В данной главе мы рассмотрим основной объект исследования теории бескоалиционных игр, получивший название равновесия по Нэшу. Данное понятие было предложено выдающимся американским математиком Джоном Нэшем (John Forbes Nash) сначала в его диссертации, а затем в серии работ, вышедших в 1950-1953 гг. .

^ Ситуацию s* в игре Г = (I, {} i Î I , {(s)} i Î I) будем называть равновесием но Нэшу (в чистых стратегиях), если для любого игрока i Î I

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

Рассмотрим отображения, которые для каждого игрока i Î I для каждой возможной подситуации Î ставят в соответствие некоторую стратегию , являющуюся его наилучшим ответом для данной подситуации:

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

В свою очередь, из условия (3.3) вытекают следующие свойства.

• 1. Строго доминируемые стратегии и НЛО-стратегии не могут входить в равновесие по Нэшу.
• 2. Стратегии, образующие равновесие по Нэшу, не могут быть исключены в процессе удаления строго доминируемых стратегий и рационализации игры.

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

Для рассмотрения свойств равновесия по Нэшу вернемся к игре "дилемма заключенного" (см. табл. 2.1).

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

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

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

Таким образом, дилемма заключенного достаточно ярко отражает тот факт, что

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

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

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

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

Продемонстрируем возможности практического использования концепции равновесия по Нэшу на примере сюжетов из литературного приложения.

• За свой вклад в теорию некооперативных игр Дж. Нэш в 1994 г. получил Нобелевскую премию по экономике
• Введено итальянским экономистом и социологом Вильфредо Парето (1848-1923)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Возникшая в сороковых годах XX века математическая теория игр чаще всего применяется именно в экономике. Но как с помощью концепции игр смоделировать поведение людей в обществе? Зачем экономисты изучают, в какой угол чаще бьют пенальти футболисты, и как выиграть в «Камень, ножницы, бумагу» в своей лекции рассказал старший преподаватель кафедры микроэкономического анализа ВШЭ Данил Федоровых.

Джон Нэш и блондинка в баре

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

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

Стратегия - описание действий игрока во всех возможных ситуациях.

Исход - комбинация выбранных стратегий.

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

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

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

«Камень, ножницы, бумага»

Рассмотрим другие игры на предмет равновесия. Например, в «Камне, ножницах, бумаге» нет равновесия по Нэшу: во всех ее вероятных исходах нет варианта, в котором оба участника были бы довольны своим выбором. Тем не менее, существует Чемпионат мира и World Rock Paper Scissors Society, собирающее игровую статистику. Очевидно, что вы можете повысить свои шансы на победу, если будете что-то знать об обычном поведении людей в этой игре.

Чистая стратегия в игре - это такая стратегия, при которой человек всегда играет одинаково, выбирая одни и те же ходы.

По данным World RPS Society, камень является самым часто выбираемым ходом (37,8%). Бумагу ставят 32,6%, ножницы - 29,6%. Теперь вы знаете, что нужно выбирать бумагу. Однако, если вы играете с тем, кто тоже это знает, вам уже не надо выбирать бумагу, потому что от вас ожидается то же самое. Есть знаменитый случай: в 2005 году два аукционных дома Sotheby“s и Christie”s решали, кому достанется очень крупный лот - коллекция Пикассо и Ван Гога со стартовой ценой в 20 миллионов долларов. Собственник предложил им сыграть в «Камень, ножницы, бумагу», и представители домов отправили ему свои варианты по электронной почте. Sotheby“s, как они позже рассказали, особо не задумываясь, выбрали бумагу. Выиграл Christie”s. Принимая решение, они обратились к эксперту - 11-летней дочери одного из топ-менеджеров. Она сказала: «Камень кажется самым сильным, поэтому большинство людей его выбирают. Но если мы играем не с совсем глупым новичком, он камень не выбросит, будет ожидать, что это сделаем мы, и сам выбросит бумагу. Но мы будем думать на ход вперед, и выбросим ножницы».

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

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

Более серьезных примеров смешанных стратегий очень много. Например, куда подавать в теннисе или бить/принимать пенальти в футболе. Если вы ничего не знаете о вашем сопернике или просто постоянно играете против разных, лучшей стратегией будет поступать более-менее случайно. Профессор Лондонской школы экономики Игнасио Паласиос-Уэрта в 2003 году опубликовал в American Economic Review работу, суть которой заключалась в поиске равновесия по Нэшу в смешанных стратегиях. Предметом исследования Паласиос-Уэрта выбрал футбол и в связи с этим просмотрел более 1400 ударов пенальти. Разумеется, в спорте все устроено хитрее, чем в «Камне, ножницах, бумаге»: там учитывается сильная нога спортсмена, попадания в разные углы при ударе со всей силы и тому подобное. Равновесие по Нэшу здесь заключается в расчете вариантов, то есть, к примеру, определении углов ворот, в которые надо бить, чтобы выиграть с большей вероятностью, зная свои слабые и сильные стороны. Статистика по каждому футболисту и найденное в ней равновесие в смешанных стратегиях, показало, что футболисты поступают примерно так, как предсказывают экономисты. Вряд ли стоит утверждать, что люди, которые бьют пенальти, читали учебники по теории игр и занимались довольно непростой математикой. Скорее всего, есть разные способы научиться оптимально себя вести: можно быть гениальным футболистом, и чувствовать, что делать, а можно - экономистом, и искать равновесие в смешанных стратегиях.

В 2008 году профессор Игнасио Паласиос-Уэрта познакомился с Авраамом Грантом, тренером «Челси», который играл тогда в финале Лиги чемпионов в Москве. Ученый написал записку тренеру с рекомендациями по серии пенальти, которые касались поведения вратаря соперника - Эдвина ван дер Сара из «Манчестер Юнайтед». Например, по статистике, он почти всегда отбивал удары на среднем уровне и чаще бросался в естественную для пробивающего пенальти сторону. Как мы определили выше, правильнее все-таки рандомизировать свое поведение с учетом знаний о сопернике. Когда счет по пенальти был уже 6:5, Николя Анелька, нападающий «Челси», должен был забивать. Показывая перед ударом в правый угол, ван дер Сар будто спросил у Анелька, не собирается ли он бить туда.

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

«Дилемма заключенного»

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

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

Улучшение по Парето

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

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

Трагедия общины

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

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

Когда вас призывают прийти на субботник, ни от кого в отдельности не будет зависеть, станет двор чистым или нет: если я выйду один, я не смогу убрать все, или, если выйдут все, то не выйду я, потому что все и без меня уберут. Другой пример - перевозка грузов в Китае, о котором я узнал в замечательной книге Стивена Ландсбурга «Экономист на диване». 100-150 лет назад в Китае был распространен способ перевозки грузов: все складывалось в большой кузов, который тащили семь человек. Заказчики платили, если груз доставлялся вовремя. Представьте, что вы - один из этих шести. Вы можете прилагать усилия, и тянуть изо всех сил, и если все будут так делать, груз доедет вовремя. Если кто-нибудь один так делать не будет, все тоже доедут вовремя. Каждый думает: «Если все остальные тянут как следует, зачем это делать мне, а если все остальные тянут не со всей силы, то я ничего не смогу изменить». В итоге, со временем доставки все было очень плохо, и сами грузчики нашли выход: они стали нанимать седьмого и платить ему деньги за то, чтобы он стегал лентяев плетью. Само наличие такого человека заставляло всех работать изо всех сил, потому что иначе все попадали в плохое равновесие, из которого никому в отдельности с выгодой не выйти.

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

Сommitment device

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

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

Другие примеры игр:

Модель Бертрана

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

Разъезд на узкой дороге

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

В забаве Chiken, когда два человека едут на большой скорости навстречу друг другу, тоже есть два равновесия. Если оба сворачивают на обочину, возникает ситуация, которая называется Chiken out, если оба не сворачивают, то погибают в страшной аварии. Если я знаю, что мой соперник едет прямо, мне выгодно съехать, чтобы выжить. Если я знаю, что мой соперник съедет, то мне выгодно ехать прямо, чтобы после получить 100 долларов. Сложно предсказать, что случится на самом деле, однако, у каждого из игроков есть свой метод выиграть. Представьте, что я закрепил руль так, что его нельзя повернуть, и показал это своему сопернику. Зная, что у меня нет выбора, соперник отскочит.

QWERTY-эффект

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

Определение 2.10. Пусть задана игра G в нормальной форме (N,Sj , Исход s = (s, s 2 > > %)е5 называется равновесием

Нэша (NE - Nash Equilibrium) игры G, если Vi е 1.....N, Уу, е 5,

Иначе говоря, каждый из игроков максимизирует свою функцию полезности

на множестве своих стратегий.

В точке равновесия Нэша стратегия х,- - одна из лучших для игрока i стратегий в ответ на х_ ; =(х 1 ,х 2 ,--.,^_ 1 ,х 1+1 ,...,х лг) - стратегии остальных игроков. Игрок i рассматривает стратегии из х_ ; как заданную вполне определенную совокупность стратегий «внешнего мира», на которую он не может активно воздействовать. Он может активно выбирать лишь свою стратегию в, которая будет наилучшим выбором, если остальные игроки выберут s_j. При этом игрок i полагает, что аналогично выбирают свои стратегии и все остальные игроки.

В точке равновесия Нэша игроку i невыгодно в одиночку отклоняться от стратегии s it если остальные игроки придерживаются стратегий 5 1 ,s 2 ,...s,-_ 1 ,s i+1 ...s N . Действия «в одиночку» могут только уменьшить выигрыш игрока i. Поиск точки равновесия Нэша, таким образом, сводится к решению системы из N задач максимизации функций полезности по соответствующим переменным

Пусть G - (N, 5,-, Uj , i - 1,..N) - конечная игра в нормальной форме.

Назовем X,- множеством смешанных стратегий игрока i, а множество X = X,-Х 2 -...-X jV - множеством профилей всех смешанных стратегий. Обозначим аеХ - элементы этого множества.

Назовем игру G = (N; X; и) смешанным расширением игры G. Тогда равновесие в смешанных стратегиях в игре G - это равновесие Нэша в ее смешанном расширении.

Пример 2.17. Задана биматричная игра

Какие выигрыши будут у игроков при выборе ими стратегий т = 0,а + 0,6Ь и п = 0,25с + 0,75d ?

Решение

Запишем рядом с чистыми стратегиями вероятности их выбора:

Поскольку выбор стратегий осуществляется игроками независимо, вероятность профиля (а; с) равна 0,4-0,25 = 0,1. Аналогично рассчитываются вероятности выигрышей игроков при остальных наборах чистых стратегий. Для удобства выигрыши игроков представим в виде вектор-столбца:

Ответ: щ - 2; и 2 = 0,25.

Наряду с равновесием Нэша введем еще одно важное понятие - доминирования по Парето.

Пусть задана игра в нормальной форме G = (N,Si, u it i = l,...,N). Рассмотрим два профиля стратегий x = (x,x 2 ,...,x jY)e5 и i/ = (i/ v i/ 2 ,...,yy)&S.

Определение 2.11. Профиль стратегий х доминирует по Парето профиль стратегий у, если

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

Определение 2.12. Профиль стратегий х называется оптимальным по Парето (Парето-оптимальным), если он недоминируем но Парето.

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

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

Решение

Очевидно, ни одна из стратегий не является строго доминируемой. Поэтому равновесия в строго доминирующих стратегиях нет.

Для определения равновесий Нэша подчеркнем наибольшие выигрыши каждого из игроков при фиксированных ходах противника:

Исходы с двойными подчеркиваниями будут равновесиями Нэша: (a; d) (b; с); (b;d ).

Для определения Парето-оптимальных исходов удобно изобразить все точки биматричной игры в критериальной плоскости (рис. 2.21 - по осям откладываем выигрыши игроков).

Рис. 2.21

Парето-оптимальными являются точки, в направлении штриховки от которых (к «северо-востоку») нет других точек. Таковыми являются исходы (а ; d) (а; с); (Ь; с). Введем для краткости обозначения для Парето- оптимальных точек - Р и для равновесных по Нэшу - N. Получим

Выясним, существуют ли в этой игре равновесные по Нэшу профили смешанных стратегий.

Пусть стратегии а и b играются с вероятностями р и 1 - р соответственно, а стратегии с и d - с вероятностями q и 1 - q.

Максимизируем функцию щ(р, q) = 3q - 2pq по переменной р е при постоянном значении q

К аналогичному результату приводит рассмотрение рационального поведения второго игрока, оптимизирующего u 2 (p,q ) по переменной q при постоянном значении р

Изобразим полученный результат (рис. 2.22) в координатах (q, р ):

Рис. 2.22

Как видим, оба графика совпали.

Равновесия Нэша:

Пример 2.19. Найти точки равновесия Нэша (в смешанных стратегиях) и Парето-оптимальные точки в матричной игре двух игроков с заданными платежными матрицами:

Решение

Очевидно, доминирующих стратегий в игре нет. Точек равновесия Нэша в чистых стратегиях также нет. Парето-оптимальные профили: (а ; d) и {b d).

Рассмотрим смешанные стратегии игроков.

Пусть стратегии а и b играются с вероятностями р и 1 - р соответственно, а стратегии cud - с вероятностями q и 1 - q. Запишем матрицу ожидаемых выигрышей первого и второго игроков:

Очевидно, первый игрок решает задачу

Решением задачи является

Эти три случая представлены на рис. 2.23.

Рис. 2.23

Аналогично второй игрок решает задачу Решением задачи является

Эти три случая представлены на рис. 2.24.

Рис. 2.24

Совмещая рисунки, получим рис. 2.25.

Рис. 2.25

Точка N (р = 0,75; q = 0,6), очевидно, является точкой равновесия Нэша в смешанных стратегиях, поскольку она получена в результате решения задач максимизации функции u x (p,q ) пори u 2 (p,q) по q.

Ответ: равновесие Нэша:

Как соотносятся между собой решения игр в чистых стратегиях, полученные методом итерационного исключения строго доминируемых стратегий (если они существуют) и равновесий Нэша? Ответ на этот вопрос дают следующие две теоремы.

Теорема 2.3. Если существует процедура итерационного исключения строго доминируемых стратегий в игре G - (S ;, щ;i - 1,...,N), которая приводит к единственному исходу s = (s i ,s 2 ,...,s N), то этот исход является единственным равновесием Нэша.

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

Замечание. Если в теореме 2.3 исключить слово «строго», то она перестает быть справедливой. Например, в игре

исходы (а; с) и (Ь; с) являются точками равновесия Нэша, хотя стратегия b доминируема.

Теорема 2.4. Если исход явля

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

Доказательство теоремы следует из определения строгой доминируемости стратегии.

Пример 2.20. Рассмотрим матричную игру:

Точка равновесия Нэша - (а,х). Однако стратегия а первого игрока доминируема (не строго) стратегией с, а стратегия х второго игрока доминируема стратегией у. Тем самым мы показали, что условие строгой доминируемое™ в теореме существенно.

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

В данной игре исход (Футбол; футбол) является точкой равновесия Нэша. Это значит, что если игроки договорились о выборе каждым из них первой стратегии, то ни одному из них невыгодно будет отклоняться от нее, если другой ее придерживается. Аналогично и исход (Балет; балет) будет точкой равновесия Нэша. Рассмотрим теперь возможность выбора игроками смешанных стратегий. Пусть первый игрок (Саша) выбирает первую и вторую чистые стратегии с вероятностями соответственно р и 1 - р. Второй игрок (Маша) выбирает первую и вторую чистые стратегии с вероятностями соответственно q и 1 -q. Получаем матрицу

Выигрыш Саши равен

Стратегия Саши определяется выбором вероятности р. Функция выигрыша Саши и с (р, q) р ,

если , и, следовательно, приСаша выберет максимальное значение вероятности, т.е.р = 1.

Аналогично если, то функция u c (p,q) - убывающая по переменной/;, и, следовательно, при Саша, максимизируя свой выигрыш, выберет минимальное значение вероятности, т.е. р = 0.

При функция и с (р> q) не зависит от р и Сашу удовлетворяет любое значение р е . Таким образом, имеем

Все сказанное наглядно представляется диаграммой (рис. 2.26).

Рис. 2.26

Выигрыш Маши равен

Стратегия Маши определяется выбором вероятности q. Функция выигрыша Маши u M (p,q) является монотонно возрастающей по переменной q,

если , и, следовательно, приМаша выберет максимальное значение вероятности, т.е.q = 1.

Аналогично если , то функция u M (p,q) - убывающая по переменной q, и, следовательно, приМаша выберет минимальное значение

вероятности, т.е.

При функция и и (р, q) не зависит от q и Машу удовлетворяет

любое значение

Все сказанное наглядно представляется диаграммой (рис. 2.27). Совмещение диаграмм на рис. 2.26 и 2.27 дает три точки пересечения наилучших выборов игроков на всевозможные действия другого игрока (рис. 2.28).

Имеем три точки равновесия Нэша. Первые

две из них соответствуют выбору чистых стратегий (Балет; балет) и (Футбол; футбол). Третья точка представляет собой точку равновесия Нэша в смешанных стратегиях.

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

эта точка не будет точкой равновесия, поскольку если Маша будет придерживаться стратегии , то Саше будет более выгодна стратегия р = 1,

поскольку

Рис. 2.27

Пример 2.22. Рассмотрим пример биматричной игры, в которой существует бесконечно много равновесий 11эша:

Выигрыш первого игрока равен

р получим

Графически этот выбор изображается следующим образом (рис. 2.29).

Рис. 2.29

q вторым игроком. Но первый игрок не знает, каков выбор второго игрока. Он лишь знает, что второй игрок будет также максимизировать свою функцию выигрыша по переменной q.

Выигрыш второго игрока равен

Из условия максимизации функции выигрыша по переменной q получим

Графически этот выбор изображается следующим образом (рис. 2.30).

Рис. 230

Совместим графики на рис. 2.29 и 2.30 (рис. 2.31).

Рис. 2.31

Графики совпадают на отрезке АВ и в начале координат. Все эти точки и будут равновесиями Нэша в смешанных стратегиях. Точка p = q = 0 означает выбор профиля чистых стратегий (b;d ). Поэтому получим: NE:{(b;d), (pa + (l-p)b ; с), ре }.

Следующая теорема дает ответ на вопрос о существовании равновесия Нэша в довольно широком классе игр.

Теорема 2.5 (Нэш, 1950). Для любой конечной игры (т.е. множество игроков и множества их чистых стратегий конечны) в нормальной форме G = (N,S jt Uj,i = 1,..., N) всегда существует по крайней мере одна точка равновесия Нэша, возможно, в смешанных стратегиях.

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

Пример 2.23. Дана биматричная игра:

Найти все равновесия Нэша в смешанных стратегиях.

Решение

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

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

Очевидно, никакая смешанная стратегия ра + (1- р)Ь не сможет доминировать чистую стратегию с, поскольку неравенство /?-0 + (1-/?)-2>14 невыполнимо ни при каких значениях р е . Значит, стратегия с не может быть строго доминируема даже с применением смешанных стратегий.

Как было доказано выше, величина f(p) = p-A + (l-p) B при /?е, {А и В - действительные числа) может принимать все значения между числами А и В. Действительно, поскольку /(/?) - линейная функция, то множеством ее значений является отрезок E(f) = .

Аналогично стратегия а не может быть доминируема смешанной стратегией pb + (l-р)с, поскольку (при выборе вторым игроком стратегии е) потребуется выполнение неравенства 4/?+ 4(1-/?) >6.

Предполагая, что смешанная стратегия pa + (1 - р)с может строго доминировать чистую стратегию Ь, также получим невыполнимое неравенство 2/?+ 4(1-/?) >8.

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

Рассмотрим стратегии второго игрока. Выпишем матрицу его выигрышей:

Очевидно, стратегии ей/ недоминируемы. Поскольку 2 е , 1 е , то можем предположить, что существует смешанная стратегия qe + (l-q)f, строго доминирующая чистую стратегию d. Проверим наше предположение. Для этого требуется выполнение системы неравенств:

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

видно, что смешанная стратегия строго доминирует стратегию d.

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

Вычеркнув первый столбец, получим матрицу

Нетрудно увидеть, что в этой матрице смешанная стратегия первого

игрока строго доминирует стратегию с (это стало очевидным только

после исключения стратегии d). Игра сократилась до биматричной игры размерности 2x2:

Теперь е>/. Получим

И наконец, а >- Ь.

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

Пример 2.24. Последовательным исключением строго доминируемых чистых стратегий привести биматричную игру к игре размерности 2x2 (смешанная стратегия может доминировать чистую). Найти все равновесия Нэша в смешанных стратегиях.

5) Пусть первый игрок играет смешанную стратегию рА + ( 1 - р)С, а второй - qE + (-q)F.

Выигрыш первого игрока равен

Из условия максимизации функции выигрыша по переменной р получим

Графически этот выбор изображается следующим образом (рис. 2.32).

Рис. 2.32

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

Выигрыш второго игрока равен

Из условия максимизации функции выигрыша по переменной q получим Графически этот выбор изображается следующим образом (рис. 2.33).

Рис. 2.33

Совместим графики на рис. 2.32 и 2.33 (рис. 2.34).

Рис. 2.34

Графики совпадают в трех точках. Эти точки и будут определять равновесия Нэша:

Пример 2.25. Найти все равновесия Нэша в смешанных стратегиях в биматричной игре

Решение

Способ 1. Нетрудно видеть, что в данной игре не существует строго доминируемых стратегий. Введем смешанные стратегии игроков:

Выигрыш первого игрока максимизируем по переменной р:

Выигрыш второго игрока максимизируем по переменным q и г.

Рассмотрим различные значения р (рис. 2.35).

Рис. 235

Случай 1. Пусть р 0,5. Тогда из (2) и (3) получим р - 0. Итак, (р = ();q = 0;г = 1) - равновесие Нэша. Это исход (b, d).

Случай 2. Пусть р = 0,5. Тогда из (2) получим q = 0, а из (1) 5г= 3, или г = 0,6. Следовательно, (р = 0,5; q = 0; г = 0,6) - равновесие Нэша. Это исход (0,5а + 0,56, 0,6d + 0,4е).

Случай 3. Пусть р е (0,5; 1). Тогда из (2) и (3) получим q = 0; г= 0. Но тогда из (1) имеем р = 1, что противоречит исходному условию.

Случай 4. Пусть р = 1. Тогда из (3) получим г = 0, а из (1) q 3, что выполняется при всех допустимых q. Итак, (р = 1; е;г = 0) - равновесия Нэша. Это исходы (a, qc + (-q)e), qe[ 0; 1].

Ответ: (6, d) (0,5а + 0,56, 0,6с/ + 0,4с); (a,qc + (-q)e), ^е.

Покажем еще один способ нахождения равновесий Нэша в таких играх.

Способ 2 (решения примера 2.25). Рассмотрим выигрыши второго игрока при условии выбора первым игроком смешанной стратегии ра + (-р)Ь. Выигрыш второго игрока при выборе им чистой стратегии с равен U - 3 р при выборе чистой стратегии d - = р + 3(- р)] при выборе чистой стратегии е - U? 2 =Зр + (-р).

Построим графики функций выигрыша второго игрока (рис. 2.36).

Рис. 2.36

Случай 1. Пусть р d. Но наилучшим ответом первого игрока на стратегию второго d является чистая стратегия b (2 > 0), т.е. р- 0, что удовлетворяет исходному условию р 0,5. Следовательно, (b , d) - равновесие Нэша.

Случай 2. Пусть р е (0,5; 1). Тогда второй игрок выбирает чистую стратегию е. Но наилучшим ответом первого игрока на стратегию второго е является чистая стратегия а (4 > 1), т.е. р = 1, что не удовлетворяет исходному условию. В данном промежутке нет равновесий Нэша.

Случай 3. Пусть р = 0.5. Тогда вторым игроком не будет играться стратегия с, г.е. q - 0. Рассмотрим игру

Математическое ожидание выигрыша первого игрока равно

Значение р = 0,5 может быть наилучшим ответом на смешанную стратегию второго игрока только при г = 0,6. Тогда исход (0,5а + 0,56, 0,6d + + 0,4с) - равновесие Нэша.

К тому же результату мы придем и из других рассуждений. А именно, для первого игрока значение р = 0,5 возможно только в случае его безразличия к выбору стратегии а или Ь. Э го значит:

Случай 4. Пусть р= 1. Тогда вторым игроком не будет играться стратегия d, т.е. г = 0. Матрица принимает вид

Тогда (a, qc + (1 - q)e) - равновесие Нэша при любых

Пример 2.26. Найти все равновесия Нэша в смешанных стратегиях в биматричной игре

Решение

Рассмотрим выигрыши второго игрока при использовании им чистых стратегий в ответ на смешанную стратегию первого игрока:

Построим графики этих функций (рис. 2.37).

Рис. 2.37

В точке А пересекаются прямые d не. Найдем точку пересечения:

В точке В пересекаются прямые сие. Найдем точку пересечения:

Ломаная линия MABN - наилучший ответ второго игрока при различных значениях р. Рассмотрим несколько случаев.

Случай 1:

чистая стратегия d. d й, что соответствует значению b, d).

Случай 2: . Тогда наилучшим ответом второго игрока является

чистая стратегия е. Но наилучшим ответом первого игрока на чистую стратегию е второго игрока является чистая стратегия а , что соответствует значению . В этом промежутке нет равновесий Нэша.

Случай 3: . Тогда наилучшим ответом второго игрока является

чистая стратегия с. Но наилучшим ответом первого игрока на чистую стратегию с второго игрока является чистая стратегия а , что соответствует значению . В этом промежутке получили единственное равновесие Нэша (а } с).

Случай 4: (точка Л). В этой точке заведомо не играется стратегия с. Матрица игры принимает вид

Рассмотрим математическое ожидание выигрыша первого игрока:

При равновесном по Нэшу исходе первый игрок максимизирует по р свою функцию полезности:

Очевидно, если является оптимальным для первого игрока, то

. Это значение можно получить из условия равенства значений функции выигрыша первого игрока при выборе им а и /;. Иными словами, первому игроку безразлично, выберет он а или b :

Следовательно, профиль стратегий является равно

весием Нэша.

Случай 5: (точка В). В этой точке заведомо не играется стратегия d. Матрица игры принимает вид

Поскольку а >- b , то р = 1 , что противоречит исходному условию Следовательно, не существует равновесия Нэша, при котором второй игрок выбирает

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

• Здесь и далее в аналогичных примерах стратегии Саши (Футбол, Балет) обозначенысловом, начинающимся с заглавной буквы, стратегии Маши - со строчной.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Равновесие Нэша

Введение

1. Джон Форбс Нэш

1.1 Научные достижения Джона Нэша

2. Равновесие Нэша

2.1 Проблема существования равновесий Нэша

2.2 Проблема единственности равновесия Нэша

2.3 Проблема эффективности равновесия Нэша

2.4 Оптимальные по Парето ситуации

3. Проблемы практического применения

Заключение

Список литературы

Введение

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

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

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

В начале 50-х Джон Нэш разрабатывает методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили названия «равновесие по Нэшу».

1. Джон Форбс Нэш

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

«Хорошие научные идеи не приходили бы мне в голову, если бы я думал как нормальные люди.» Д. Нэш

Трудовую деятельность Джон Нэш начал в корпорации "РЭНД" (Санта-Моника, Калифорния), где работал летом 1950 года, а также в 1952 и 1954 годах.

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

В 1951 - 1952 гг. Джон работает научным ассистентом в Кембридже (Массачусетский технологический институт).

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

1.1 Научные достижения Джона Нэша

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

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

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

нэш математик единственность равновесие

2. Равновесие Нэша

Основной математической моделью конфликтной ситуации является игра в нормальной форме. Эта модель задается совокупностью

где множество участников или игроков;

множество допустимых стратегий игрока;

ситуация игры, возникающая в результате выбора всеми игроками своих стратегий;

выигрыш игрока в ситуации.

Важнейшим принципом принятия решений в конфликтных ситуациях является понятие равновесия Нэша.

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

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

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

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

2 .1 Проблема существования равновесий Нэша

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

Стратегиям первого игрока соответствуют строки, а стратегиям второго игрока столбцы. Элемент матрицы равен выигрышу игрока, если первый игрок использует свою -тую стратегию, а второй игрок применяет свою -тую стратегию.

Пример игры, в которой не существует равновесий Нэша

Рассмотрим следующую биматричную игру:

Игре с такими матрицами выигрышей можно дать следующую интерпретацию: происходит игра "в монетку": второй игрок загадывает "орел" или "решку", а первый игрок отгадывает. Если он угадывает правильно, то получает от второго игрока "1", иначе отдает "1" второму игроку.

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

2 .2 Проблема единственности равновесия Нэша

Перейдем к ответу на второй вопрос: если существует равновесие Нэша, то является ли оно единственным?

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

матрица выигрышей жены,

матрица выигрышей мужа.

Легко убедиться, что в этой игре существует два равновесия Нэша: когда оба игрока используют первую стратегию (т.е. супруги идут на балет), либо когда оба игрока используют вторую стратегию (т.е. супруги идут на футбол).

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

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

2 .3 Проблема эффективности равновесия Нэша

Рассмотрим биматричную игру, называющуюся "Дилемма заключенного". (Эта игра достаточно знаменита. Ей посвящено несколько тысяч работ, дающих различные интерпретации этой игры.) Игроками являются два находящихся под следствием человека. У каждого из них есть две стратегии: сознаться в совершенном преступлении или не сознаваться. Следователь предлагает каждому заключенному такие условия: если он сознается, а другой подозреваемый нет, то тогда первого, учитывая его помощь следствию, осудят по минимальному обвинению (на 1 год), а второму дадут максимальный срок (10 лет). Если сознаются оба, то их обоих осудят и дадут срок, соответствующий их преступлению (по 5 лет лишения свободы каждому). Наконец, если оба подследственных не сознаются, то их смогут осудить за недостаточностью улик только по части обвинения (например, за незаконное хранение оружия вместо более тяжкого преступления, которое они на самом деле совершили). В этом случае оба получат по 2 года.

Получаем следующие матрицы выигрышей ("С" сознаться, "Н" не сознаваться):

для первого игрока

для второго игрока

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

Описанная в примере игра имеет следующую структуру:

2.4 Оптимальные по Парето ситуации

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

Пусть задана игра в нормальной форме. Набор стратегий называется Парето-оптимальным, если для любого

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

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

3 . Проблемы практического применения

Мы отметили три недостатка понятия равновесия по Нэшу:

равновесий Нэша в игре может не существовать;

равновесие Нэша может быть не единственно;

равновесие Нэша может быть неэффективно.

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

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

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

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

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

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

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

Заключение

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

Где же сегодня применяются открытия Нэша?

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

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

Список литературы

1. Васин А. А., Морозов В. В. Теория игр и модели математической экономики. -- М.: МГУ, 2005, 272 с.

2. Воробьёв Н. Н. Теория игр для экономистов-кибернетиков. -- М.: Наука, 1985

3. http://dic.academic.ru/dic.nsf/econ_dict/22119

4. http://economicportal.ru/ponyatiya-all/nash_equilibrium.html

Размещено на Allbest.ru

Подобные документы

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

курсовая работа , добавлен 06.01.2012


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

контрольная работа , добавлен 11.06.2011


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

курсовая работа , добавлен 04.08.2011


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

курсовая работа , добавлен 20.08.2010


Условия равновесия в экономической модели. Методы регулирования совокупного спроса. Исследование возможностей получения эффективных равновесий в макроэкономике. Использование монетарной и фискальной политик в процессе регулирования рыночных отношений.

дипломная работа , добавлен 18.11.2017


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

курсовая работа , добавлен 19.06.2009


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

контрольная работа , добавлен 30.03.2016


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

реферат , добавлен 14.02.2011


Классическая теория оптимизации. Функция скаляризации Чебышева. Критерий Парето-оптимальность. Марковские процессы принятия решений. Метод изменения ограничений. Алгоритм нахождения кратчайшего пути. Процесс построения минимального остовного дерева сети.

контрольная работа , добавлен 18.01.2015


Рассмотрение теоретических и практических аспектов задачи принятия решения. Ознакомление со способами решения с помощью построения обобщенного критерия и отношения доминирования по Парето; примеры их применения. Использование критерия ожидаемого выигрыша.