Теория равновесия нэша. Научная электронная библиотека

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

знать

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

уметь

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

владеть

простейшими методами анализа свойств биматричных игр 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)

В реальной жизни часто появляются вопросы, почему на одних рынках фирмы сотрудничают, а на других - агрессивно конкурируют; к каким средствам следует прибегать фирме, чтобы не допустить вторжения потенциальных конкурентов; как принимаются решения о цене; когда меняются условия спроса или издержек. Изучая эти проблемы, ученые используют теорию игр.
Первыми исследователями в области теории игр были американский математик Дж.-Ф. Нейман и австро-американский экономист О. Моргенштерн («Теория игр и экономическое поведение», 1944). Они распространили математические категории на экономическую жизнь общества, вводя понятия оптимальных стратегий, максимизации ожидаемой полезности, доминирование в игре (на рынке), коалиционные соглашения. Эти ученые оказали стимулирующее влияние на развитие социальных наук в целом, математической статистики, экономической мысли, в частности в области практического использования теории вероятности и теории игр в экономике.
Ученые стремились сформулировать основополагающие критерии рационального поведения участника рынка. Они различали два вида игр. Первый - «с нулевой суммой» - предусматривает такой выигрыш который формируется из издержек других игроков, то есть общая сумма выгоды и издержек всегда равна нулю. Другой вид - «игра с плюсовой суммой», когда индивидуальные игроки ведут борьбу за выигрыш, складывающийся из их ставок. Иногда этот выигрыш создается за счет наличия «выходного» (термин из карточной игры в бридж; так называют одного из игроков, который, делая ставки, не принимает участия в игре), совсем пассивного и часто такого, который служит объектом эксплуатации. И в том, и в другом случае игра неминуемо соединена с риском, поскольку каждый из ее участников, как считали Дж.-Ф. Нейман и О. Моргенштерн, «стремится максимально повысить функцию, переменные которой не контролируются». Если все игроки одинаково умелые, то решающим фактором становится случайность. Однако так происходит редко. Почти всегда важнейшую роль в игре играет хитрость, с помощью которой делаются попытки раскрыть замысел противника и завуалировать свои намерения, а потом занять выгодные позиции и вынудить противника действовать в убыток себе. Важная роль отводится и «контрхитрости».
Во время игры много зависит и от рационального поведения игрока, то есть продуманного выбора и оптимальной стратегии. Разработке формализованного (в виде моделей) описания конфликтных ситуаций, в частности «формулы равновесия», то есть устойчивости решений противников в игре, занимался Дж.-Ф. Нэш
Нэш (Nash) Джон-Форбс (род в 1928) - американский экономист, лауреат Нобелевской премии (1994). Родился в г. Блуэфилд (штат Западная Вирджиния, США). Учился в Университете Карнеги-Меллона по специальности инженера-химика, но, увлекшись математикой, перевелся на математический факультет. Получил диплом бакалавра математики и одновременно магистра математики.
Поступил в аспирантуру по математической специализации Принстонского университета, где защитил докторскую диссертацию на тему «Некооперативные игры» (1950). В следующем году ее опубликовали отдельной статьей в журнале «Анналы математики». Когда обучался на старших курсах университета, принимал участие в исследовательской работе фирмы «RAND Corp.», которая финансировала ряд его разведывательных проектов в области теории игр, математической экономики и общей теории рационального поведения в игровых ситуациях.
В 1951-1959 гг. Дж.-Ф. Нэш - преподаватель Массачусетского технологического института. Одновременно ведет научно-исследовательскую деятельность. Ему удалось решить классическую проблему, связанную с дифференциальной геометрией.
Из-за тяжелой болезни он в течение 20 лет не мог работать.
В 70-е годы болезнь отступила. Но продуктивные научные результаты высшей пробы ему не удавались.
Дж.-Ф. Нэш продолжает исследования по математике. В целом он опубликовал 21 научную работу, 16 из них увидели свет до 1959 г.
Он член Национальной академии наук США, Эконометрического общества и Американской академии искусств и наук.
В классической теории игр кооперативные и бескоалиционные игры трактуются по-разному. Дж.-Ф. Нэш первым указал на отличие между ними и определил кооперативные игры как игры, допускающие свободный обмен информацией и принудительные условия между игроками, а бескоалиционные - как такие, которые не допускают свободного обмена информацией и принудительных условий. Некооперативной является такая игра, когда кооперирование между игроками не допускается вообще. В статьях «Точки равновесия в играх с N-числом участников» и «Проблема заключения сделок» (1951) он математически точно вывел правила действий участников (игроков), которые выигрывают в соответствии с выбранной стратегией. Каждый из игроков старается снизить степень риска с помощью самой выгодной стратегии, то есть путем постоянного приспособления к поведению тех, кто тоже хочет достичь наиболее лучших результатов.
Досконально изучив разные игры, создав серию новых математических игр и наблюдая за действиями участников в разных игровых ситуациях, Дж.-Ф. Нэш стремился понять, как функционирует рынок, как компании принимают решения, связанные с риском, почему покупатели действуют так, а не иначе. Ведь в экономике, как и в игре, руководители фирм должны учитывать не только последние, но и предыдущие шаги конкурентов, а также ситуацию на всем экономическом (игровом, например, шахматном) поле и другие факторы.
Известно, что субъекты экономической жизни - активные ее участники, которые на рынке в условиях конкуренции идут на риск, и он должен быть оправдан. Поэтому каждый из них, как и игрок, должен иметь свою стратегию. Именно из этого исходил Дж.-Ф. Нэш, разрабатывая метод, который позже назвали «равновесием Неша».
Равновесие Неша - совокупность стратегий или действий, согласно которым каждый участник реализовывает оптимальную стратегию, предвидя действия соперников.
«Стратегию» как основное понятие теории игр Дж.-Ф. Нэш разъясняет на основе «игры с нулевой суммой» («симметричная игра»), когда каждый участник имеет определенное количество стратегий. Выигрыш каждого игрока зависит от выбранной им стратегии, а также от стратегии его соперников. На этой основе строится матрица для нахождения оптимальной стратегии, которая при многократном повторении игры обеспечивает определенному игроку максимально возможный средний выигрыш (или максимально возможный средний проигрыш). Поскольку этому игроку неизвестно, какую стратегию выберет противник, ему самому целесообразнее выбрать стратегию, рассчитанную на самое неблагоприятное для него поведение противника (принцип «Гарантированного результата»). Действуя осторожно и считая конкурента сильным, этот игрок выберет для каждой своей стратегии минимально возможный выигрыш. И таким образом из всех минимально выигрышных стратегий выберет такую, которая обеспечит ему максимальный из всех минимальных выигрышей («максимин»).
Его противник, наверное, рассуждает так же. Он найдет для себя наибольшие проигрыши во всех стратегиях этого игрока, а потом из этих максимальных проигрышей выберет минимальный («минимакс»). При равенстве максимина минимаксу решения игроков будут устойчивыми, а игра будет иметь равновесие. Устойчивость (равновесие) решений (стратегий) заключается в том, что обоим участникам игры будет невыгодно отходить от выбранных стратегий. Когда же максимин не равен минимаксу, то решения (стратегии) обоих игроков, если они хотя бы в какой-то мере угадали выбор стратегии противника, будут неустойчивыми, неравновесными.
Значит, равновесие Нэша - результат, в котором стратегия каждого из игроков является лучшей среди других стратегий, принятых остальными участниками игры. Это определение основывается на том, что каждый из игроков изменением собственной роли не может достичь наибольшей выгоды (максимизации функции полезности), если другие участники твердо придерживаются собственной линии поведения.
Свою «формулу равновесия» Дж.-Ф. Нэш усилил показателем оптимального объема информации. Он вывел его из анализа ситуаций с полным информированием игрока о своих противниках и с неполным информированием о них. Переведя этот постулат с математического языка на язык экономической жизни, ученый ввел (как важный информационный элемент знания условий «внешней среды») неуправляемые переменные рыночных отношений.
Появление в науке равновесия Дж.-Ф. Нэша открыло многочисленные исследования с целью приближения его к реальной экономической действительности. На усовершенствование равновесия Дж.-Ф. Нэша были направлены исследования многих ученых. Среди них Дж.-Ч. Харшани.
Харшани (Harsanyi) Джон-Чарльз (1920-2000) - американский экономист, лауреат Нобелевской премии (1994). Родился в г. Будапеште (Венгрия), закончил Лютеранскую гимназию.
Получил высшее медицинское образование. В 1947 г., защитив докторскую диссертацию, начал работать преподавателем университетского Института социологии. Из-за антимарксистских взглядов в 1948 г. вышел в отставку, а потом выехал в Австралию. Там работал на заводе, одновременно обучался в Сиднейском университете, где изучал английский язык и экономику. В 1953 г. получил степень магистра.
С 1954 г. он лектор экономики Брисбенского университета. Через два года Дж.-Ч. Харшани был отмечен Фондом Рокфеллера, что давало ему право в течение следующих двух лет писать докторскую диссертацию в Стэнфордском университете.
В 1958 г. Дж.-Ч. Харшани возвращается в Австралию. Однако, почувствовав определенную изолированность, поскольку в этой стране в то время теория игр фактически не была известна, переехал в США, где работал профессором экономики Детройтского университета. В 1964 г. он профессор Экономического центра Волтера Хааса при университете Беркли в штате Калифорния.
Первые научные работы Дж.-Ч. Харшани опубликовал в начале 50-х годов, посвятив их вопросам использования функции полезности Неймана-Моргенштерна в экономике благосостояния и в этике. Дж.-Ч. Харшани является автором многих работ по утилитарной этике, экономики благосостояния, а также в сфере, граничащей между экономикой и моральной философией. В работе «Рациональное поведение и переговорное равновесие в играх и социальных ситуациях» (1977) он обосновывает «общую теорию рационального поведения», охватывающую «теорию индивидуального решения», вопросы деловой этики и теорию игр. Среди его книг «Эссе по этике, социальному поведению и научному объяснению» (1976), «Работы по теории игр» (1982), «Общая теория выбора равновесия в играх» (1988, совместно с Р.-Дж.-Р. Селтеном), которая в 2001 г. издана на русском языке, «Рациональное взаимодействие» и др.
Дж.-Ч. Харшани - почетный доктор Северно-Западного и почетный профессор Калифорнийского университетов (США).
Предметом исследования Дж.-Ч. Харшани были сложные ситуации, которые случаются при наличии асимметричной информации. В игре с полной информацией все игроки знают преимущества других, а в игре с неполной информацией они нуждаются в этих знаниях.
Поскольку толкование равновесия Нэша базировалось на прогнозе, что игроки знают преимущества других, все методы были недоступны для анализа игр с неполной информацией, несмотря на то, что такие игры более полно отражают стратегические взаимосвязи в реальном мире.
Ситуацию радикально изменили исследования Дж.-Ч. Харшани («Игры с неполной информацией, сыгранные байсианскими игроками»). Ученый исходил из того, что каждый игрок является одним из нескольких «типов», а каждый тип отвечает набору возможных преимуществ для игрока и вероятно распределяет почти всех на типы игроков. Значит, каждый игрок в игре с неполной информацией выбирает стратегию одного из таких типов. С согласованным требованием в отношении возможности распределения игроков Дж.-Ч. Харшани показал, что для каждой игры с неполной информацией существует эквивалентная игра с полной информацией. То есть он трансформировал игру с неполной информацией в игру с несовершенной информацией. В таком случае игра может регулироваться стандартными моделями.
Примером игры с неполной информацией может быть ситуация, когда частные фирмы и финансовые рынки точно не знают преимуществ центрального банка в отношении дилеммы между инфляцией и безработицей. Соответственно неизвестна и банковская политика в отношении будущих процентных ставок. Взаимодействие между будущими ожиданиями и политикой центрального банка можно проанализировать с помощью методики, предложенной Дж.-Ч. Харшани. В самом простом виде банк может или ориентироваться на борьбу с инфляцией и, значит, готовиться к осуществлению ограничительной политики с высокими процентными показателями, или будет бороться с безработицей с помощью низких процентных показателей.
Равновесие Нэша доработал и усовершенствовал, в частности относительно игр с неполной информацией, Р.-Дж.-Р. Селтен.
Селтен (Selten) Рейнхард-Джустус-Реджинальд (род в 1930) - немецкий экономист, лауреат Нобелевской премии (1994). Родился в г. Бреслау (ныне г. Вроцлав, Польша). В 1951 г. закончил в г. Мелсунген среднюю школу. Уже здесь заинтересовался математикой, впервые узнал о теории игр. Учился на математическом факультете Университета во Франкфурте-на Майне, окончил его в 1957 г. в течение десяти лет
Р.-Дж.-Р. Селтен работал там ассистентом. Этот период его жизни был насыщен активной экспериментаторской работой. В 1959 г. защитил докторскую диссертацию по математике. На протяжении 1969-1972 гг. он профессор экономики Свободного университета в Западном Берлине. Потом работал в Билефельдском университете, в котором продолжил экспериментальные исследования теории игр.
С 1984 г. Р.-Дж.-Р. Селтен - профессор кафедры экономики Боннского университета имени Фридриха-Вильгельма. Выступив организатором научно-исследовательского года (с 1 октября 1987 года по 30 сентября 1988 года) по теории игр в поведенческих науках, он сумел собрать большую международную группу экономистов, биологов, математиков, политологов, психологов и философов. Их общая работа изложена
в 4-х книгах «Модели равновесия игры» (1991). Р.-Дж.-Р. Селтен - основатель теории некооперативных игр.
В 1995 г. Р.-Дж.-Р. Селтен избран вице-президентом Европейской экономической ассоциации, а в 1997 г. - ее президентом. Он член Американских экономической ассоциации и эконометрического общества, входит в состав многих редколлегий научных журналов, является почетным иностранным членом Американской академии искусств и наук, членом Национальной академии наук США, а также почетным доктором Билефельдского, Бреславского, Грацского университетов, Университета Франкфурта-на-Майне и др.
В статье «Модель олигополии с инерцией спроса» (1965)
Р.-Дж.-Р. Селтен разработал «чистую стратегию» с интуитивным выбором. Последовательно усложняя и уточняя отмеченное «равновесие» дополнительными условиями для предыдущих договоренностей об игре, ученый развивал ее с точки зрения динамики и приближал к условиям реальной жизни. Он на противоположных примерах доказал, что даже точки равновесия могут вызвать иррациональное поведение. По мнению ученого, только специальный класс точек равновесия (он их назвал «истинными», или «совершенными точками равновесия») обеспечивает на самом деле рациональное поведение в бескоалиционной игре.
Понятие «равновесие Нэша» распространяется на теорию динамичных игр. В этом случае каждый участник выбирает стратегию (то есть план действий для каждого периода игры), которая максимизирует его выигрыш при заданных стратегиях других игроков. Основная проблема с динамичным равновесием Неша заключается в том, что в последнем периоде игры игроки могут вести себя иррационально. В тот момент, когда становится ясно, что данный период игры последний, ранее выбранное действие может оказаться иррациональным (не максимизирует выгоду). Усовершенствованное понятие равновесия, предложенное в 1975 г.
Р.-Дж.-Р. Селтеном, позволяет избавиться от непредвиденных предпосылок о стратегиях. Это понятие «совершенного равновесия Нэша», или совершенного равновесия субигры, предусматривает, что стратегии, выбранные игроками, являются равновесными, по Нешу, в каждой субигре (то есть в каждой однопериодной игре основной игры) независимо от того, какие действия были выполнены раньше.
Внедрение равновесия Нэша стало важным шагом в микроэкономике. Его использование способствовало углубленному пониманию развития и функционирования рынков, обоснованию стратегических решений, принимающихся менеджерами разных фирм. Важным является вклад Р.-Дж.-Р. Селтена, который усовершенствовал концепцию равновесия Нэша для анализа стратегического взаимодействия в динамике и использовал это для анализа конкуренции при условии небольшого количества участников. А методология анализа игры с неполной информацией Дж.-Ч. Харшани обеспечила теоретическую основу для исследования экономики информации.
Равновесием Нэша можно пользоваться при изучении процесса ведения политических переговоров и экономического поведения, в частности на олигополистических рынках (форма организации рынка, где существует несколько производителей однородного или дифференцированного товара). Именно Р.-Дж.-Р. Селтен выявил возможности использования моделей в политике. Его сотрудничество с американским ученым-политиком А. Пелмутером позволило разработать так называемый сценарий пакетного метода - систематизированный способ создания простых моделей игры конкретных международных конфликтов, благодаря которым можно осуществлять экспертные проверки эмпирических фактов.
Таким образом, дополненная теория игр дала экономике мощный математический инструментарий, который помог экономистам освободиться от зависимости от формального математического аппарата физики. Равновесие Нэша - это гибкий метод анализа разнообразных конкретных проблем и ситуаций на рынках.
Теория игр в дальнейшем была использована в исследованиях Томаса Шеллинга и Роберта Оманна. Их интересовал вопрос: «Почему некоторые группы людей, организаций и стран преуспевают в сотрудничестве, в то время как другие страдают от постоянных конфликтов?»
Шеллинг (Schelling) Томас Кромби (род. в 1921) - американский экономист, лауреат Нобелевской премии 2005 г. «За расширение понимания проблем конфликта и кооперации с помощью анализа в рамках теории игр». Профессор Мэрилендского университета. Президент Американской экономической ассоциации в 1991 г. Лауреат премии Фрэнка Сейдмана (1977). Основные произведения: «Стратегия конфликта» (The Strategy of Conflict, 1960); «Микромотивы и макровыбор» (Micromotives and Macrobehavior, 1978); «Выбор и последствия» (Choice and Consequence, 1985).
Использовал теорию игр для принятия рациональных решений в условиях недостаточной информации о возможных последствиях, как базу для объединения и исследования общественных наук в своей книге «Стратегия конфликта» (The Strategy of Conflict), опубликованной в 50-е годы прошлого века в условиях гонки вооружений.
В своей книге Шеллинг показывает, например, что способность принять ответные меры может быть иногда более полезной, чем способность выдержать атаку, или что возможное неизвестное возмездие часто более эффективно, нежели известное неотвратимое возмездие.
В книге Шеллинга рассматривались возможности решения стратегических конфликтов и способы избежать войны, однако его выводы могли объяснить и широкий диапазон явлений в сфере экономики и конкурентоспособности предприятий.
Р. Ауманн в свою очередь, посвятил свои исследования изучению теории бесконечных повторяющихся игр или того, каким образом можно поддерживать определенные результаты в отношениях в течение долгого периода времени.
Ауманн (Aumann) Исраэль Роберт Джон (также Оман) (род. в 1930) - израильский математик, профессор Еврейского университета в Иерусалиме, лауреат Нобелевской премии по экономике 2005 года «За расширение понимания проблем конфликта и кооперации с помощью анализа в рамках теории игр».
В 1983 году Оман был награждён премией Харви. В 1994 году профессор Оман был награждён Государственной премией Израиля по экономике вместе с профессором Михаэлем Бруно.
Р. Оман возглавлял Общество теории игр, а в начале 1990-х являлся президентом Израильского союза математиков. Кроме того являлся ответственным редактором «Журнала Европейского математического общества». Ауманн также консультировал Агентство США по контролю за вооружениями и разоружению. Он занимался теорией игр и её приложениями около 40 лет. Основные произведения: «Почти строго конкурентные игры» (Almost Strictly Competitive Games, 1961); «Смешанные и поведенческие стратегии в бесконечно расширенных играх» (Mixed and Behavior Strategies in Infinite Extensive Games, 1964).
Теория игр - это наука о стратегии, она изучает, как различные соперничающие группы - бизнесмены или любые другие сообщества - могут сотрудничать с получением идеального результата.
Оман специализировался в «повторяющихся играх», анализируя развитие конфликта во времени. Исследования Ауманна базировались на идее о том, что сотрудничество во многих ситуациях легче установить в ходе долгосрочных стабильных отношений.
Теория Ауманна объясняет, почему более трудно достичь сотрудничества между большим количеством участников, учитывая насколько часты, продолжительны и надежны контакты между ними и насколько каждый участник может предвидеть действия других.
Исследования направлены на объяснение таких экономических конфликтов, как ценовые и торговые войны, раскрытие механизма переговоров в различных условиях - от требований о повышении заработной платы до заключения международных торговых соглашений.

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

Второй игрок выберет стратегию A, если предполагает, что первый выберет стратегию Z; в то же время стратегия B для него предпочтительнее в случае, если первый выберет Y.

Таблица 16.8.

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

16.2.4 Равновесие по Нэшу

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

игроки при принятии решений ориентируются на предполагаемые действия партнеров;

ожидания являются равновесными (совпадают с фактически выбранными партнерами действиями).

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

Формально равновесие Нэша определяется следующим образом.

Определение 90:

Набор стратегий x X является равновесием Нэша15 , если

1) стратегия x i каждого игрока является наилучшим для него откликом на ожидаемые им стратегии других игроков xe −i :

ui (xi , xe −i ) = max ui (xi , xe −i ) i = 1, . . . , n;

x iX i

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

15 Американский математик Джон Нэш получил Нобелевскую премию по экономике в 1994 г. вместе с Дж. Харшаньи и Р. Зельтеном «за новаторский анализ равновесий в теории некооперативных игр». Концепция равновесия была предложена в следующих статьях: J. F. Nash: Equilibrium Points in N-Person Games,

Proceedings of the National Academy of Sciences of the United States of America 36 (1950): 48–49; J. F. Nash: NonCooperative Games, Annals of Mathematics 54 (1951): 286–295 (рус. пер. Дж. Нэш: Бескоалиционные игры, в кн. Матричные игры, Н. Н. Воробьев (ред.), М.: Физматгиз, 1961: 205–221).

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

xe −i = x−i i = 1, . . . , n

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

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

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

Набор стратегий x X является равновесием Нэша, если стратегия xi каждого игрока является наилучшим для него откликом на стратегии других игроков x−i :

ui (xi , x−i ) = max ui (xi , x−i ) i = 1, . . . , n

x iX i

Это свойство можно также записать в терминах так называемых функций (отображений) отклика.

Определение 91:

Отображение отклика i-го игрока,

Ri : X−i 7→Xi

сопоставляет каждому набору стратегий других игроков, x−i X−i , множество стратегий i-го игрока, каждая из которых является наилучшим откликом на x−i . Другими словами,

ui (yi , x−i ) = max ui (xi , x−i ) x−i X−i , yi Ri (x−i )x i X i

Введение отображений отклика позволяет записать определение равновесия Нэша более компактно: набор стратегий x X является равновесием Нэша, если

xi Ri (x−i ) i = 1, . . . , n

Если отклик каждого игрока однозначен (является функцией), то множество равновесий Нэша совпадает с множеством решений системы уравнений:

xi = Ri (x−i ) i = 1, . . . , n.

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

Проиллюстрируем использование функций отклика на примере игры, в которой игроки имеют континуум стратегий.

Игра 5. «Международная торговля»

Две страны одновременно выбирают уровень таможенных пошлин, τi . Объем торговли между странами16 , x, зависит от установленных пошлин как

x = 1 − τ1 − τ2

Цель каждой страны - максимизировать доходы ui = τi x.

Максимизируем выигрыш 1-й страны,

τ1 (1 − τ1 − τ2 )

по τ1 считая фиксированным уровень пошлины, установленный 2-й страной. Условие первого порядка имеет вид

1 − 2τ1 − τ2 = 0

Поскольку максимизируемая функция строго вогнута, то условие первого порядка соответствует глобальному максимуму.

Условие первого порядка для задачи максимизации выигрыша 2-й страны находится аналогично:

1 − τ1 − 2τ2 = 0

Решив систему из двух линейных уравнений, найдем равновесие Нэша:

τ1 = τ2 = 1/3

Оптимальный отклик 1-й страны на уровень таможенной пошлины, установленной 2-й страной описывается функцией

τ1 (τ2 ) =1 − τ 2

Аналогично, функция отклика 2-й страны имеет вид

τ2 (τ1 ) =1 − τ 1 2

Чтобы найти равновесие Нэша, требуется решить систему уравнений

τ1 (τ2 ) = τ1 ,

τ2 (τ) = τ .

Графически поиск равновесия Нэша показан не Рис. 16.3 . Точки, лежащие на кривых оптимального отклика τ1 (τ2 ) и τ2 (τ1 ), характеризуются тем, что в них касательные к кривым безразличия игроков параллельны соответствующей оси координат. Напомним, что кривой безразличия называют множество точек, в которых полезность рассматриваемого индивидуума одна и та же (ui (x) = const). Равновесие находится как точка пересечения кривых отклика.

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

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

16 В этой игре мы для упрощения не делаем различия между экспортом и импортом.


		(τ2 )
		(τ2 )
				равновесия



				τ2 (τ1 )

Рис. 16.3. Равновесие Нэша в игре «Международная торговля»

Теорема 151:

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

Обратная теорема верна в случае единственности.

Теорема 152:

Если в результате последовательного отбрасывания строго доминируемых стратегий у каждого игрока остается единственная стратегия, xi , то x = (x1 , . . . , xm ) - равновесие Нэша в этой игре.

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

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

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

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

Игра 6. «Инспекция»

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


Таблица 16.9.
		Инспектор
	проверять		не проверять

нарушать
нарушать

Проверяемый
не нарушать

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

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

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

Xi = {x1 i , . . . , xn i i }

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

µi = (µ1 i , . . . , µn i i )

Обозначим множество смешанных стратегий i-го игрока через Mi :

Mi = µi µk i > 0, k = 1, . . . , ni ; µ1 i + · · · + µn i i = 1

Как мы уже отмечали, стандартное предположение теории игр (как и экономической теории) состоит в том, что если выигрыш - случайная величина, то игроки предпочитают действия, которые приносят им наибольший ожидаемый выигрыш. Ожидаемый выигрыш i-го игрока, соответствующий набору смешанных стратегий всех игроков, (µ1 , . . . , µm ), вычисляется по формуле

Ожидание рассчитывается в предположении, что игроки выбирают стратегии независимо (в статистическом смысле).

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

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

Определение 92:

Набор смешанных стратегий µ = (µ1 , . . . , µm ) являетсяравновесием Нэша в смешанных стратегиях , если

1) стратегия µ i каждого игрока является наилучшим для него откликом на ожидаемые им стратегии других игроков µe −i :

U(µi , µe −i ) = max U(µi , µe −i ) i = 1, . . . , n;

µ iM i

2) ожидания совпадают с фактически выбираемыми стратегиями:

µe −i = µ−i i = 1, . . . , n.

Заметим, что равновесие Нэша в смешанных стратегиях является обычным равновесием Нэша в так называемом смешанном расширении игры, т. е. игре, чистые стратегии которой являются смешанными стратегиями исходной игры.

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

Обозначим через µ вероятность того, что налогоплательщик не платит подоходный налог,

а через ν - вероятность того, что налоговой инспектор проверяет налогоплательщика.

В этих обозначениях ожидаемый выигрыш налогоплательщика равен

U1 (µ, ν) = µ[ν · (−1) + (1 − ν) · 1] + (1 − µ)[ν · 0 + (1 − ν) · 0] =

= µ(1 − 2ν),

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

U2 (µ, ν) = ν[µ · 1 + (1 − µ) · (−1)] + (1 − µ)[µ · 0 + (1 − µ) · 0] = = ν(2µ − 1)

Если вероятность проверки мала (ν < 1/2), то налогоплательщику выгодно не платить налог, т. е. выбрать µ = 1. Если вероятность проверки велика, то налогоплательщику выгодно заплатить налог, т. е. выбрать µ = 0. Если же ν = 1/2, то налогоплательщику все равно, платить налог или нет, он может выбрать любую вероятность µ из интервала . Таким образом, отображение отклика налогоплательщика имеет вид:

Рассуждая аналогичным образом, найдем отклик налогового инспектора:

0, если µ < 1/2

ν(µ) = , если µ = 1/2

1, если µ > 1/2.

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

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

Графики отображений отклика обоих игроков представлены на Рис. 16.4 . По осям на этой диаграмме откладываются вероятности (ν и µ соответственно). Они имеют единственную общую точку (1/2, 1/2). Эта точка соответствует равновесию Нэша в смешанных стратегиях. В этом равновесии, как это всегда бывает в равновесиях с невырожденными смешанными стратегиями (то есть в таких равновесиях, в которых ни одна из стратегий не выбирается с вероятностью 1), каждый игрок рандомизирует стратегии, которые обеспечивают ему одинаковую ожидаемую полезность. Вероятности использования соответствующих чистых стратегий, выбранные игроком, определяются не структурой выигрышей данного игрока, а структурой выигрышей его партнера, что может вызвать известные трудности с интерпретацией данного решения.

Рис. 16.4. Отображения отклика в игре «Инспекция»

В отличие от равновесия в чистых стратегиях, равновесие в смешанных стратегиях в конечных играх существует всегда19 , что является следствием следующего общего утверждения.

Теорема 153:

Предположим, что в игре G = hI, {Xi }i I , {ui }i I i у любого игрока множество стратегий Xi непусто, компактно и выпукло, а функция выигрыша ui (·) вогнута по xi и непрерывна. Тогда в игре G существует равновесие Нэша (в чистых стратегиях).

Существование равновесия Нэша в смешанных стратегиях в играх с конечным числом чистых стратегий является следствием того, что равновесие в смешанных стратегиях является равновесием в чистых стратегиях в смешанном расширении игры.

Теорема 154 (Следствие (Теорема Нэша)):

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

Заметим, что существование в игре равновесия в чистых стратегиях не исключает существования равновесия в невырожденных смешанных стратегиях.

Рассмотрим в Игре 16.2.1 «Выбор компьютера» случай, когда выгоды от совместимости значительны, т. е. a < c и b < c. В этом варианте игры два равновесия в чистых стратегиях: (IBM, IBM) и (Mac, Mac). Обозначим µ и ν вероятности выбора компьютера IBM PC первым и вторым игроком соответственно. Ожидаемый выигрыш 1-го игрока равен

U1 (µ, ν) = µ[ν · (a + c) + (1 − ν) · a] + (1 − µ)[ν · 0 + (1 − ν) · c] = = µ[ν · 2c − (c − a)] + (1 − ν)c

а его отклик имеет вид

µ(ν) = ,

Ожидаемый выигрыш 2-го игрока равен

если ν < (c − a)/2c

если ν = (c − a)/2c

если ν > (c − a)/2c.

U2 (µ, ν) = ν[µ · c + (1 − µ) · 0] + (1 − ν)[µ · b + (1 − µ) · (b + c)] =

= ν[µ · 2c − (b + c)] + b + (1 − µ)c

а его отклик имеет вид

ν(µ) = ,

если µ < (b + c)/2c

если µ = (b + c)/2c

если µ > (b + c)/2c.

Графики отображений отклика и точки, соответствующие трем равновесиям изображены на Рис. 16.5 . Как видно, в рассматриваемой игре кроме двух равновесий в чистых стратегиях имеется одно равновесие в невырожденных смешанных стратегиях. Соответствующие вероятности равны

µ = b + cи ν = c − a

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

Приложение A

Теорема повторяется, номер обновляется, ссылки на это приложение нет. Можно поменять местами A и B

Теорема 155:

Предположим, что в игре G = hI, {Xi }i I , {ui0 }i I i у любого игрока множество стратегий Xi непусто, компактно и выпукло, а функция выигрыша ui (·) вогнута по xi и непрерывна. Тогда существует равновесие Нэша.

Доказательство: Докажем, что отображение отклика, Ri (·), каждого игрока полунепрерывно сверху и его значение при каждом x−i X−i непусто и выпукло. Непустота следует из теоремы Вейерштрасса (непрерывная функция на компакте достигает максимума).

16.2. Статические игры с полной информацией

Докажем выпуклость. Пусть z0 , z00 Ri (x−i ). Очевидно, что u(z0 , x−i ) = u(z00 , x−i вогнутости по xi функции ui (·) следует, что при α

u(αz0 + (1 − α)z00 , x−i ) > αu(z0 , x−i ) + (1 − α)u(z00 , x−i ) =

U(z0 , x−i ) = u(z00 , x−i )

Поскольку функция ui (·) достигает максимума в точках z0 и z00 , то строгое неравенство

невозможно. Таким образом,

αz0 + (1 − α)z00 Ri (x−i )

Докажем теперь полунепрерывность сверху отображения Ri (·). Рассмотрим последовательность xn i сходящуюся к x¯i и последовательность xn −i сходящуюся к x¯−i , причем xn i Ri (xn −i ). Заметим, что в силу компактности множеств Xj x¯i Xi и x¯−i X−i . Нам нужно доказать, что x¯i Ri (x¯−i ). По определению отображения отклика

u(xn i , xn −i ) > u(xi , xn −i ) xi Xi , n

Из непрерывности функции ui (·) следует, что

u(¯xi , x¯−i ) > u(xi , x¯−i ) xi Xi

Тем самым, по введенному выше определению отображения отклика, x¯i Ri (x¯−i ). Опираясь на доказанные только что свойства отображения Ri (·) и на теорему Какутани,

докажем существование равновесия по Нэшу, то есть такого набора стратегий x X , для

которого выполнено

xi Ri (x−i ) i = 1, . . . , n

Определим отображение R(·) из X в X следующим образом:

R(x) = R1 (x−1 ) × · · · × Rn (x−n )

Отметим, что это отображение удовлетворяет тем же свойствам, что и каждое из отображений Ri (·), так как является их декартовым произведением.

Отображение R(·) и множество X удовлетворяют свойствам, которые необходимы для выполнения теоремы Какутани. Таким образом, существует неподвижная точка отображения

Очевидно, что точка x есть равновесие по Нэшу.

Приложение B

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

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

G = hI, {Xi }I , {ui }I i.

Определим последовательность игр {G[t] }t=0,1,2,... , каждая из которых получается из последующей игры отбрасыванием строго доминируемых стратегий. Игры отличаются друг от друга множествами допустимых стратегий:

G[t] = hI, {Xi [t] }I , {ui }I i

Процедура начинается с G= G.

Множество допустимых стратегий i-го игрока на шаге t + 1 рассматриваемой процедуры берется равным множеству не доминируемых строго стратегий i-го игрока в игре t-го шага. Множества не доминируемых строго стратегий будем обозначать через NDi (см. определение строго доминируемых стратегий (Определение89 , с.631 )). Формально

NDi = xi Xi yi Xi : ui (yi , x−i ) > ui (xi , x−i ) x−i X−i

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

X i = ND i [t]

где NDi [t] - множество не доминируемых строго стратегий в игре G[t] .

Приведем теперь доказательства Теорем 151 и152 (с.636 ). Теорема151 утверждает следующее:

: Если x = (x1 , . . . , xm ) - равновесие Нэша в некоторой игре, то ни одна из стратегий не может быть отброшена в результате применения процедуры последовательного отбрасывания строго доминируемых стратегий.

Если использовать только что введенные обозначения, то Теорема 151 утверждает, что если x - равновесие Нэша в исходной игре G, то на любом шаге t выполнено

xi Xi [t] , i I, t = 1, 2, . . .

x X[t] , t = 1, 2, . . .

Доказательство (Доказательство Теоремы 151 ): Пусть есть такой шаг τ , что на нем должна быть отброшена стратегия xi некоторого игрока i I . Предполагается, что на предыдущих шагах ни одна из стратегий не была отброшена:

x X[t] , t = 1, . . . , τ.

По определению строгого доминирования существует другая стратегия игрока i, x0 i Xi [τ] , которая дает этому игроку в игре G[τ] более высокий выигрыш при любых выборах других

ui (x0 i , x−i ) > ui (xi , x−i ) x−i X− [τ i ]

В том числе, это соотношение должно быть выполнено для x−i , поскольку мы предположили, что стратегии x−i не были отброшены на предыдущих шагах процедуры (x−i X− [τ i ] ). Значит,

: Если в результате последовательного отбрасывания строго доминируемых стратегий у каждого игрока остается единственная стратегия, xi , то x = (x1 , . . . , xm ) - равновесие Нэша в этой игре.

Данная теорема относится к случаю, когда в процессе отбрасывания строго доминируемых

стратегий начиная с некоторого шага ¯ остается единственный набор стратегий, т. е. t x

Теорема утверждает, что x является единственным равновесием Нэша исходной игры.

Доказательство (Доказательство Теоремы 152 ): Поскольку, согласно доказанной только что теореме, ни одно из равновесий Нэша не может быть отброшено, нам остается только доказать, что указанный набор стратегий x является равновесием Нэша. Предположим, что это не так. Это означает, что существует стратегия x˜i некоторого игрока i, такая что

ui (xi , x−i ) < ui (˜xi , x−i )

По предположению, стратегия x˜i была отброшена на некотором шаге τ , поскольку она не совпадает с xi . Таким образом, существует некоторая строго доминирующая ее стратегия x0 i Xi [τ] , так что

ui (x0 i , x−i ) > ui (˜xi , x−i ) x−i X− [τ i ]

В том числе это неравенство выполнено при x−i = x−i :

ui (x0 i , x−i ) > ui (˜xi , x−i )

Стратегия x0 i не может совпадать со стратегией xi , поскольку в этом случае вышеприведенные неравенства противоречат друг другу. В свою очередь, из этого следует, что должна существовать стратегия x00 i , которая доминирует стратегию x0 i на некотором шаге τ0 > τ , т. е.

	(x00									[τ0 ]
								−i

В том числе

ui (x00 i , x−i ) > ui (x0 i , x−i )

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

Продолжая эти рассуждения, мы получим последовательность шагов τ < τ0 < τ00 < . . .

и соответствующих допустимых стратегий x0 i , x00 i , x000 i , . . ., не совпадающих с xi . Это противо-

/ 667. Два игрока размещают некоторый объект на плоскости, то есть выбирают его координаты (x, y). Игрок 1 находится в точке (x 1 , y1 ), а игрок 2 - в точке (x2 , y2 ). Игрок 1 выбирает координату x, а игрок 2 - координату y. Каждый стремиться, чтобы объект находился как можно ближе к нему. Покажите, что в этой игре у каждого игрока есть строго доминирующая стратегия.

/ 668. Докажите, что если в некоторой игре у каждого из игроков существует строго доминирующая стратегия, то эти стратегии составляют единственное равновесие Нэша.

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

Найдите в следующих играх все равновесия Нэша.

/ 670. Игра 16.2.1 (с.625 ), выигрыши которой представлены в Таблице??////??

/ 671. «Орехи»

Два игрока делят между собой 4 ореха. Каждый делает свою заявку на орехи: xi = 1, 2 или 3. Если x1 + x2 6 4, то каждый получает сколько просил, в противном случае оба не получают ничего.

/ 672. Два преподавателя экономического факультета пишут учебник. Качество учебника (q) зависит от их усилий (e1 и e2 соответственно) в соответствии с функцией

q = 2(e1 + e2 ).

Целевая функция каждого имеет вид

ui = q − ei ,

т. е. качество минус усилия. Можно выбрать усилия на уровне 1, 2 или 3.

/ 673. «Третий лишний» Каждый из трех игроков выбирает одну из сторон монеты: «орёл» или «решка». Если

выборы игроков совпали, то каждому выдается по 1 рублю. Если выбор одного из игроков отличается от выбора двух других, то он выплачивает им по 1 рублю.

/ 674. Три игрока выбирают одну из трех альтернатив: A, B или C . Альтернатива выбирается голосованием большинством голосов. Каждый из игроков голосует за одну и только за одну альтернативу. Если ни одна из альтернатив не наберет большинство, то будет выбрана альтернатива A. Выигрыши игроков в зависимости от выбранной альтернативы следующие:

u1 (A) = 2, u2 (A) = 0, u3 (A) = 1,

u1 (B) = 1, u2 (B) = 2, u3 (B) = 0,

u1 (C) = 0, u2 (C) = 1, u3 (C) = 2.

/ 675. Формируются два избирательных блока, которые будут претендовать на места в законодательном собрании города N-ска. Каждый из блоков может выбрать одну из трех ориентаций: «левая» (L), «правая» (R) и «экологическая» (E). Каждая из ориентаций может привлечь 50, 30 и 20% избирателей соответственно. Известно, что если интересующая их ориентация не представлена на выборах, то избиратели из соответствующей группы не будут голосовать. Если блоки выберут разные ориентации, то каждый получит соответствующую долю голосов. Если блоки выберут одну и ту же ориентацию, то голоса соответствующей группы избирателей разделятся поровну между ними. Цель каждого блока - получить наибольшее количество голосов.

/ 676. Два игрока размещают точку на плоскости. Один игрок выбирает абсциссу, другой -

ординату. Их выигрыши заданы функциями:

а) ux (x, y) = −x2 + x(y + a) + y2 , uy (x, y) = −y2 + y(x + b) + x2 ,

б) ux (x, y) = −x2 − 2ax(y + 1) + y2 , uy (x, y) = −y2 + 2by(x + 1) + x2 , в) ux (x, y) = −x − y/x + 1/2y2 , uy (x, y) = −y − x/y + 1/2x2 ,

(a, b - коэффициенты).

/ 677. «Мороженщики на пляже»

Два мороженщика в жаркий день продают на пляже мороженое. Пляж можно представить как единичный отрезок. Мороженщики выбирают, в каком месте пляжа им находиться, т. е. выбирают координату xi . Покупатели равномерно рассредоточены по пляжу и покупают мороженое у ближайшего к ним продавца. Если x1 < x2 , то первый обслуживают (x1 + x2 )/2 долю пляжа, а второй - 1 − (x1 + x2 )/2. Если мороженщики расположатся в одной и той же точке (x1 = x2 ), покупатели поровну распределятся между ними. Каждый мороженщик стремиться обслуживать как можно большую долю пляжа.

/ 678. «Аукцион» Рассмотрите аукцион, подобный описанному в Игре 16.2.2 , при условии, что выигравший

аукцион игрок платит названную им цену.

/ 679. Проанализируйте Игру 16.2.1 «Выбор компьютера» (с.624 ) и найдите ответы на следующие вопросы:

а) При каких условиях на параметры a, b и c будет существовать равновесие в доминирующих стратегиях? Каким будет это равновесие?

б) При каких условиях на параметры будет равновесием Нэша исход, когда оба выбирают IBM? Когда это равновесие единственно? Может ли оно являться также равновесием в доминирующих стратегиях?

/ 680. Каждый из двух соседей по подъезду выбирает, будет он подметать подъезд раз в неделю или нет. Пусть каждый оценивает выгоду для себя от двойной чистоты в a > 0 денежных единиц, выгоду от одинарной чистоты - в b > 0 единиц, от неубранного подъезда - в 0, а свои затраты на личное участие в уборке - в c > 0. При каких соотношениях между a, b и c в игре сложатся равновесия вида: (0) никто не убирает, (1) один убирает, (2) оба убирают?

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

/ 682. Каждый из двух игроков (i = 1, 2) имеет по 3 стратегии: a, b, c и x, y, z соответственно. Взяв свое имя как бесконечную последовательность символов типа иваниваниван. . . , задайте выигрыши первого игрока так: u1 (a, x) = «и», u1 (a, y) = «в», u1 (a, z) = «а», u1 (b, x) = «н», u1 (b, y) = «и», u1 (b, z) = «в», u1 (c, x) = «а», u1 (c, y) = «н», u1 (c, z) = «и». Подставьте вместо каждой буквы имени ее номер в алфавите, для чего воспользуйтесь Таблицей16.10 . Аналогично используя фамилию, задайте выигрыши второго игрока, u2 (·).

1) Есть ли в Вашей игре доминирующие и строго доминирующие стратегии? Если есть, то образуют ли они равновесие в доминирующих стратегиях?

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

3) Найдите равновесия Нэша этой игры.

Таблица 16.10.

/ 683. Составьте по имени, фамилии и отчеству матричную игру трех игроков, у каждого из которых по 2 стратегии. Ответьте на вопросы предыдущей задачи.

/ 684. Заполните пропущенные выигрыши в следующей таблице так, чтобы в получившейся игре. . .

(0) не было ни одного равновесия Нэша,

		было одно равновесие Нэша,

		было два равновесия Нэша,


		было три равновесия Нэша,

(4) было четыре равновесия Нэша.

/ 685. 1) Объясните, почему в любом равновесии Нэша выигрыш i-го игрока не может быть меньше, чем

min max ui (xi , x−i ).

x −iX −ix iX i

2) Объясните, почему в любом равновесии Нэша выигрыш i-го игрока не может быть

меньше, чем

x iX ix −iX −i

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

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

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

Наиболее известный пример некооперативной игры с ненулевой суммой – “дилемма заключённого”.

Итак. С поличным поймали 2х воров, которым предъявлено обвинение в ряде краж. Перед каждым из них встаёт дилемма – признаваться ли в старых (недоказанных) кражах или нет. Если признается только 1 из воров, то признавшийся получает минимальный срок заключения – 1 год, а другой максимальный – 10 лет. Если оба вора одновременно сознаются, то оба получать небольшое снисхождение – 6 лет, если же оба не признаются, то понесут наказание, только за последнюю кражу – 3 года. Заключённые сидят в разных камерах и не могут договориться друг с другом. Перед нам игра с некооперативная с ненулевой (отрицательной) суммой. Характерной чертой этой игры является невыгодность для обоих участников руководствоваться своими частными интересами. “дилемма заключённого” наглядно показывает особенности олигополистического ценообразования.

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

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

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

Формальное определение.

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

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

Возможно, будет полезно почитать: