Теория экономических механизмов

Теория экономических механизмов

2-е издание, исправленное

Николенко С.И.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Теория экономических механизмов/ С.И. Николенко - М.: Национальный Открытый Университет
“ИНТУИТ”, 2016

Теория экономических механизмов (mechanism design theory) — быстроразвивающаяся и
относительно молодая область экономики, направленная на создание механизмов взаимодействия
между эгоистичными агентами.
Как наука теория экономических механизмов использует методы теории вероятностей,
математической статистики, теории игр, теории оптимизации и теоретической информатики; это
мультидисциплинарная область, в которой находят применение идеи из самых разных областей
математики и экономики. Курс представляет собой введение в теорию экономических механизмов с
изложением основных классических результатов в данной области; она содержит много интересных
примеров и обсуждений, но при этом не отклоняется от математической строгости.

(c) ООО “ИНТУИТ.РУ”, 2011-2016
(c) Николенко С.И., 2011-2016

3

Теория игр

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

Основные концепции

Теория игр — наука молодая, хотя, конечно, и не такая молодая, как теория
экономических механизмов. Первые шаги на пути к теории игр были сделаны в XVIII
веке, первая опубликованная работа относится к первой половине XIX века — это
знаменитая книга Антуана Огюстена Курно [14]. Примечательно, что много важных
замечаний, относящихся к теории игр, были сделаны биологами, рассматривавшими
теорию естественного отбора и поведения животных; поведение было, разумеется,
эгоистическим. Классический труд Рональда Фишера [19] содержит многие методы
теории игр, а уже после математического оформления этой теории эстафету принял
Джон Майнард Смит [46]. Математически же теорию игр оформил Джон фон Нейман:
сначала в статьях 1920-х годов [61], а затем в книге с Оскаром Моргенштерном [62], с
которой, наверное, и нужно вести историю теории игр как развитого математического
аппарата. Учебники по теории игр мы здесь пересказывать не будем, цель этой книги
совершенно другая; мы просто изложим вкратце некоторые вещи из теории игр, без
которых нам совсем уж не обойтись. А если читатель заинтересуется теорией игр
всерьез, рекомендуем ему учебники [20,23,64,65,79].

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

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

Определение 1.1.Стратегическая игра — это тройка

где обозначения расшифровываются следующим образом:

4

1. 
 — конечное множество игроков.

2. 
 — множество доступных игрокам действий, где 
 — множество

действий, доступных игроку . Будем обозначать через 
 действие игрока ,

а через 
 — вектор действий всех игроков, кроме i1). Через 

будем обозначать множество всех векторов действий игроков, через 
— множество векторов действий всех игроков, кроме . Вектор 

 будем называть профилем действий, или исходом.

3. 
 — множество функций выплат 
.

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

Есть и еще одно важное замечание: в течение этой лекции мы предполагаем, что у
участников есть предпочтения по поводу исходов игры и эти предпочтения можно
выразить при помощи функций 
. Это далеко не всегда так, и в лекции 6 мы

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

Если множество стратегий 
 конечно, то множество исходов игры можно выразить 

-мерной матрицей, в ячейке которой с координатами 
 стоят исходы 

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

самую обычную матрицу.

Пример 1.1. Первый пример возьмем совсем уж из детства — рассмотрим
классическую игру “камень-ножницы-бумага”2). Камень побеждает ножницы,
ножницы побеждают бумагу, бумага — камень. У игры получается вот какая матрица
(где  означает победу того игрока, чьи стратегии выписаны слева, а 
 — победу

игрока, стратегии которого стоят в первой строке):

Конец примера 1.1.

Пример 1.2. В качестве второго примера рассмотрим классическую игру полковника
Блотто [70,79]. Полковник Блотто должен распределить свои силы ( 
 солдат) между

несколькими участками поля боя ( 
 участков). Его противник должен сделать то же

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

Например, пусть участков боя в игре три, причем и Блотто, и его противник

5

располагает тремя солдатами. Тогда множество стратегий у обоих участников
сражения состоит из следующих элементов:

(3,0,0),  (2,1,0),  (2,0,1),  (1,2,0),  (1,1,1),
(1,0,2),  (0,3,0),  (0,2,1),  (0,1,2),  (0,0,3).

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

противник,  — случилась ничья.

Конец примера 1.2.

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

верно, что 
 .

В дальнейшем нас будут интересовать не только игры с конечными множествами
стратегий, но и игры с непрерывными такими множествами. Возьмем классический
пример — конкуренцию по Курно (Cournot competition)3)

Рис. 1.1.  Конкуренция по Курно: функции оптимального ответа

Пример 1.3. Рассмотрим рынок некоего продукта, на котором находятся ровно две
фирмы: 
. Стратегия каждого из участников — количество продукта, которое

он производит: 
.

6

Прибыль каждого участника в результате игры — это его общий доход за вычетом
себестоимости:

где 
 — функция, по которой определяется цена, а 
 — цена за единицу для

компании . Мы будем предполагать, что 
. В качестве функции  мы

рассмотрим

Давайте попробуем проанализировать, как фирмам лучше всего играть в свою игру.
Попробуем построить оптимальную стратегию для игрока , если игрок  произвел
товара 
 (best response function, 
 ). Если 
, то производить ничего не

надо, потому что равновесная цена все равно будет равна нулю. Если же 
, то

оптимальную стратегию придется искать так:

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

Конец примера 1.3.

Доминантные и доминируемые стратегии

Что же делать участвующим в игре агентам? Как им определить, какая стратегия
лучше других?

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

Определение 1.2. Стратегия 
 агента  называется доминируемой, если

существует такая стратегия 
, что

В таком случае говорят, что 
 доминирует над .

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

агентов. Значит, нет вообще никакой причины предпочитать , и ее можно просто
отбросить при анализе.

7

Пример 1.4. Вспомним пример 1.2, в котором полковник Блотто собирался расставить
войска на поле. Если проанализировать матрицу из примера 1.2, станет очевидным, что
стратегии 
, 
 и 
 доминируются другими: например, стратегия 

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

Блотто. Таким образом, матрица существенно сократится.

Конец примера 1.4.

Пример 1.5. В примере 1.3, в котором мы обсуждали конкуренцию по Курно, было
очень много доминируемых стратегий. Таковыми были все стратегии 
: они

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

сразу можно было ограничиться анализом квадрата 
 в качестве множества

стратегий.

Конец примера 1.5.

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

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

Определение 1.3. Стратегия 
 агента  называется доминантной, если всякая

другая стратегия 
 ею доминируется, то есть

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

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

Определение 1.4. Равновесие в доминантных стратегиях для стратегической игры 

 — это такой профиль стратегий 
, что для всякого агента 

8

 стратегия 
 является доминантной.

Такое равновесие является самым устойчивым из всех. В следующей лекции мы
приведем пример из теории экономических механизмов, в котором возникает такое
равновесие — так называемый аукцион Викри (см. теорему 2.1.

Но, к сожалению, счастье достижимо далеко не всегда. Ни в примере 1.1, ни в примере
1.2, ни в примере 1.3 никакого равновесия в доминантных стратегиях не получалось.
Для каждой стратегии 
 игрока  там существовал профиль стратегий других игроков

, в котором игроку  было бы выгодно сменить 
 на ту или иную 
.

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

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

Тогда приходится учитывать не только свои собственные стратегии, но и стратегии
других агентов. Учет этот приведет к понятию равновесия, сформулированному в 1950
году Джоном Нэшем [60].

Определение 1.5. Равновесие Нэша в чистых стратегиях для стратегической игры 

 — это такой профиль стратегий 
, что для всякого агента 

выполняется следующее условие:

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

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

Пример 1.6. Продолжаем рассматривать беднягу Блотто. Матрица игры полковника без
доминируемых стратегий была приведена в примере 1.4. Из матрицы легко видеть, что
если один игрок выбирает стратегию 
, то от выбора другого уже ничего не

зависит, то есть можно сказать, что другому тоже нет резона отклоняться от стратегии 

. Все это значит, что для данной игры профиль стратегий 

находится в равновесии Нэша.

Конец примера 1.6.

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

Пример 1.7. Вернемся к анализу конкуренции по Курно из примера 1.3. На этот раз мы
не будем ничего упрощать: пусть цена задается неизвестной функцией 
, а

себестоимость производства для каждой фирмы — неизвестной функцией 
.

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

9

определяется как

Чтобы определить максимум функции 
 для фиксированного 
, нужно просто найти

производную

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

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

Конец примера 1.7.

В определении 1.5 упоминался странный термин “чистые стратегии“: а какими еще
они бывают? Оказывается, что стратегии бывают не только чистыми, но и
смешанными. Смешанные стратегии — логичное расширение понятия стратегии:
давайте разрешим игроку не только выбирать одну из 
, но и делать из них более или

менее случайный выбор.

Определение 1.6. Смешанная стратегия для игрока  в стратегической игре 

 — это распределение вероятностей 
, где 
 — множество

всех распределений вероятностей над 
 .

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

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

Пример 1.8. Вспомним игру “камень-ножницы-бумага”, матрицу которой мы уже
выписывали в примере 1.1.

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

10