Лекция 10. Равновесия Нэша (продолжение)

Сравнение с предыдущими понятиями. Равновесие Нэша тесно связано с предыдущими понятиями решения и хорошо согласуется с ними.

a) Доминирующие стратегии. Очевидно, что равновесие в доминирующих стратегиях является равновесием Нэша.

Впрочем, наряду с доминирующими равновесиями могут встречаться и другие, как правило, дурацкие. Рассмотрим, например, аукцион второй це­ны. Он интересен тем, что при его использовании у каждого участника есть доминирующая стратегия. Однако есть и много других, "плохих" равновесий Нэша. А именно (если участников > 3), для любого участника г и любого числа р < и; существует равновесие Нэша, при котором участник / получает предмет за цену р. Для этого все, кроме /-го. предлагают цену р. а он пред­лагает цену, большую тах(м^). В этом "дурацком" равновесии предмет торга достается и дешевле, и не тому.

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

имеет цены, то осторожные стратегии не образуют равновесие.

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

Первая - что для нахождения равновесной (=осторожной) стратегии каждый из игро­ков может действовать индивидуально. В отличие от общего случая, ему не нужно знать или делать догадки относительно Глядя только на таблицу (своих) выигрышей он может выделить множество Р{ своих осторожных стратегий и выбрать произвольный эле­мент в нем в качестве з*. В частности, множество НЕ равновесий Нэша устроено как произведение /' х !'■> н любое равновесие дает участнику одну и ту же полезность.

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

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

Лемма. Если н\- - равновесие Нэша, то > щ для любого игрока г.

В самом деле, сравним равновесную стратегию в* с осторожной в^. Мы имеем и^(а*,5^) > > а^.П

На самом деле верно (и столь же просто доказывается), что равновесные выигрыши не меньше Д.

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

Леммы. Пусть для каждого г заданы подмножества Б[ С Предпо­ложим, что «д- - равновесие в игре (Ы, (5^), (щ)), и кроме того в* £ 5г' для любого г. Тогда н\- является равновесием в игре (]У, (50,

Если С00 - игра, полученная после итеративного исключения сильно до­минируемых стратегий, то предыдущее замечание дает включение

ЫЕ(в) С ЫЕ(С°°).

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

= ЫЕ(С°°).

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

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

1,1

100,0

0,100

100,100

Здесь стратегия в2 слабо доминируется стратегией в1, но пара (в2,£2) обра­зует равновесие, причем неплохое.

Если мы выбросили некоторую слабо доминируемую стратегию (и обозна­чили полученную игру как С), то легко показать (покажите!), что

ЫЕ(С) С ЫЕ(в).

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

Равновесия Нэша и конкурентные равновесия. Конкурентные равновесия, кото­рые встречаются в теории общего экономического равновесия, очень похожи на равновесия Нэша. Опишем в самых общих чертах общее равновесие. Там имеется несколько агентов, которые реагируя на цены р, принимают какие-то (оптимальные) решения Х{. Конкурент­ность проявляется в том, что они только реагируют на цены, но сами на них не влияют, не пытаются менять. Равновесие - когда решения .г( удовлетворяют неким балансам, на­пример, когда ^ хг < 0.

Тут полезно ввести фиктивного игрока 0, который контролирует цены и занимается до­стижением баланса. Обычно ему приписывается фиктивная полезность, равная р(^2гхг)-Тогда равновесие Нэша (р*, (х*)) в этой вспомогательной игре дает конкурентное эконо­мическое равновесие. В самом деле, по определению х* - наилучшие ответы агентов при цене р*, и остается проверить, что выполнены балансы. Если некоторые компоненты век­тора ^2х* положительны, то оптимальное (для игрока 0) значение р*(^2х*) > 0. С другой стороны из закона Вальраса стоимость ^х* в текущих ценах равна 0. Полученное про­тиворечие и дает, что ^2/Х* < 0.

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

Голосования с опросом. Идея, близкая к равновесию, применима и для исследования схем голосования. Пусть X - множество альтернатив (или кандидатов); у каждого игрока функция полезности и, на X. Голосование производится путем заполнения бюллетеней; обычно они одинаковы для всех игроков, но мы все равно обозначим через ^ множество заполнений для игрока (избирателя) г. Схема голосования задается отображением / : xSi —У X. Так возникает игра.

Однако в ней сложно разобраться, поэтому делается такой методологический трюк. Говорится, что "до голосования" производится опрос населения и эти результаты дово­дятся до сведения публики. Множество возможных результатов опроса обозначим У; это может быть А (.V) - предсказание о шансах кандидатов, а может быть предсказание о распределении голосов. Главный смысл опроса - что он помогает определиться избирате­лям, помогаем им решить, за кого голосовать (как заполнять бюллетени). Мы ударимся в крайность и будем считать, что у каждого избирателя есть своя функция ф{ : У —У >'( (зависящая от предпочтений щ). Тем самым определено отображение Ф : У —У X.

Как проводится опрос и как подводятся итоги, модель не уточняет. Вместо этого требу­ется, чтобы результаты опроса как-то согласовывались с реальным исходом голосования. Последнее задается отображением (быть может, многозначным) Ф : X —У У. Равновеси­ем в такой системе называется пара (х*,у*) из реального исхода голосования х* и опроса у*, такая что Ф(ж*) = у*, а ф(у*) = х*.

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

Ограничимся для простоты двумя фирмами. Пусть их издержки (при вы­пуске товара в количестве д) задаются функциями С^(д). Каждая фирма независимо принимает решение о выпуске д^. Полный выпуск = д1 +д2- Це­на, по которой он может быть продан, задается (обратной) функцией спроса Р = Р(Я)- Поэтому прибыль каждой фирмы равна

щ = ч%р{ч\ + 42) -

Каждая фирма стремится максимизировать 7Г^. Курно, который впервые ис­следовал эту задачу, предположил, что при этом выпуск другой фирмы неиз­менен. Поэтому условия максимизации первого порядка имеют вид

р(Я1 +   + щР'{ч\ + 42) = ИЗЛ^Ы-

Упростим все, считая издержки линейными, С^(д) = сд, а р(0) = М — (так что М - это максимальная цена, по которой можно продать товар). Тогда

<&) = (М - с - д! - д2)ф.

Найдем лучший ответ 1-й фирмы на выбор д2. ()тг\/()<{\ = М — с — 2д| — д2:

приравнивая его нулю, мы получаем

д^ = Д!(д2) = (М-с-д2)/2.

Аналогично для второй фирмы. Равновесие получается в точке пересечения кривых реакций, и д* = (М — с)/3. Цены равны р* = (М + 2с)/3.

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

 

Первая фирма видит, что вторая использует стратегии от 0 до М/2, Поэтому ее наи­лучшие ответы расположены на отрезке [М/4, М/2]. Соответственно наилучшие ответы второй фирмы находятся на отрезке [М/4, ЗМ/8]. Тогда наилучшие ответы первой фирмы располагаются на отрезке [5М/16, ЗМ/8]. И так далее. Эти вложенные отрезки сходятся к точкам Д//.'к Здесь для простоты с = 0.

Заметим, что если бы была монополия, т.е. одна фирма с теми же из­держками, то ее прибыль максимизировалась бы при д = (М — с)/2 по цене рт = (М + с)/2 (конечно, считается, что М > с). Т.е. при монополии це­ны выше, а выпуски меньше. При конкуренции цена рс = с, а выпуск равен М — с. Кстати, конкуренцию можно рассматривать как олигополию с боль­шим числом фирм.

Добровольное финансирование общественного блага. Представим, что группа индивидов имеет технологию, способную преобразовывать деньги I в общественное благо у = /(£). Если трансферабельная полезность обще­ственного блага для индивида г задается функцией щ(у)7 мы получаем игру. Стратегии игрока г задаются числами (сколько он жертвует на обществен­ное благо), а выигрыши измеряются функциями

После этого можно искать равновесия Нэша. Рассмотрим два более конкрет­ных примера.

Пример 1. 20 соседей в деревне думают построить бассейн для купания. Полезность бассейна для каждого равна 16, а весь проект стоит 200. Что произойдет - сказать трудно, ибо имеется масса равновесий.

Пример 2. Картель из 9 фирм хочет протолкнуть законопроект, сулящий (в случае принятия) каждой фирме прибавок в 40 000 долларов. Для лоббирова­ния этого законопроекта фирмы добровольно вносят по Ь{ тысяч. Вероятность прохождения проекта равна р = £/(10 + £), где I = ^ ^.

Найдем равновесие Нэша. Ожидаемый выигрыш фирмы равен (в тысячах долларов) 40(^/(10 + £)) — и. Дифференцируя, получаем 40-10 = (£+10)2, т.е. Ь = 10. Итого будет собрано 10 тысяч (в среднем с каждой фирмы по 1.100). Полная прибыль картеля составит 170 тысяч. В то же время оптимальный для картеля уровень затрат находится из максимизации функции 9-40(^/(10+ £)) — что дает £ = 50 (примерно по 5.5 с фирмы). Полная прибыль картеля составила бы тогда 300-50=250 тысяч.

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

1) если игра с нулевой суммой, то седловая точка дает равновесие;

2) алгоритм Цермело-Куна дает равновесие в "развернутой" игре с совер­шенной информацией.

Существование (и вычисление) равновесий в общем случае основано на анализе соответствий наилучших ответов. Раньше мы для каждого игрока г определили соответствие Вс^1 : ==$■ Б;. или подмножество Вс^; С .9 у • Так вот множество равновесий Нэша - это в точности общие точки всех Вев^.

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

1

*7

4

*2Ф

3

*9

Здесь мы знаком Л отмечали лучшие ответы первого игрока, а знаком Ф ­лучшие ответы второго. Оба значка стоят в клетке с 2; это и есть равновесие Нэша в данной игре.

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

Теорема Нэша. Предположим,, что в игре (И, (5^), (м^)) все множества - выпуклые компакты, а функции выигрыша щ - непрерывны и вогнуты

по своей переменной (т.е. щ вогнута по в^). Тогда существует хоть одно

равновесие Нэша.

Доказательство фактически уже приводилось в Лекциях о неподвижных точках. Напомним его основные моменты. Для каждой ситуации .%• д- £ = $1 х ... х Бп и каждого игрока г рассмотрим его наилучший ответ Besti(sJx) = Агрт1ах(1^(-, Это непустое (непрерывность щ) и выпуклое (вогнутость

щ) подмножество Рассмотрим теперь соответствие В '. Б \ У Б \. кото­рое точку 5дг переводит в множество Bestl(sN) х ... х Bestn(sN)■ Довольно легко проверить (проверьте!), что это замкнутое (или полунепрерывное свер­ху) соответствие. Поэтому применима теорема Какутани, которая утвержда­ет существование неподвижной точки .%-д- £ .Р(в^г). Понятно, что .%-д- будет равновесием Нэша.П

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

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