Введение в дизайн механизмов

О чем этот курс: суть, история и мотивация

Однако прежде чем продать что-нибудь ненужное, надо купить что-нибудь ненужное. Прежде чем максимизировать прибыль по некоторым правилам игры, нужно, чтобы эти правила игры кто-то разработал! А тот, кто их разрабатывает, может сделать их такими, чтобы в результате совершенно естественного развития событий достигались те или иные цели, его интересующие. Intelligent design, знаете ли: достаточно сделать первый шаг, дать начальный толчок Вселенной, и она по заложенным в нее физическим законам начнет расширяться от Большого Взрыва до наших дней. В гипотезе о существовании Бога Лаплас не нуждался — но и не отрицал ее; совершенно нефальсифицируемо, что кто-то создал Вселенную такой, какая она есть, с некоторым начальным замыслом. В этом курсе мы будем исполнять роль таких вот мини-демиургов: разрабатывать условия, правила игры, в которых совершенно самостоятельные, внешние, эгоистичные, направленные только на извлечение прибыли агенты в итоге будут достигать цели, которую заложил тот, кто создавал правила игры.

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

Главный пример дизайна механизмов — аукционы. В обычном аукционе целей, которые преследует "демиург", может быть не так уж и много: либо организатор пытается максимизировать общую прибыль (social welfare), либо продавец пытается сделать такой аукцион, чтобы продать подороже (см. лекцию 5). Кроме того, хочется достичь ситуации, при которой выявляются истинные предпочтения участников (это называется правдивостью аукциона; мы об этом еще будем подробно говорить), и, конечно, решение должно быть в каком-либо смысле оптимальным и/или устойчивым, иначе оно не сможет реализоваться.

Слово "mechanism" в этом контексте ввел Лео Гурвиц (Leo Hurwicz). Он родился в Москве в 1917 году (тогда его, конечно, звали Леонидом), жил в Польше, в 1940 эмигрировал в США — все вполне логично для того неспокойного и опасного времени. В 1959-1960 годах он сформулировал основные положения теории экономических механизмов [28], в 1973-м сформулировал свойство правдивости [29], а затем и принцип выявления, с которого по сути и началось исследование децентрализованных систем применительно к экономике. Кстати говоря, недавно вышла книга Гурвица о дизайне механизмов [30].

Дальше Эрик Маскин (Eric Maskin) начал разрабатывать так называемую "теорию реализации" (implementation theory) — то есть собственно дизайн механизмов: как сделать такой протокол, чтобы он обладал нужными свойствами [39,43,44]. А потом Роджер Майерсон (Roger Myerson) применил это все к аукционам и окончательно оформил поле деятельности [54-57].

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

Но зачем все это нужно? Зачем нужно разрабатывать какие-то хитрые механизмы, хитрые аукционы? Кто применяет это на практике?

Например, Google и Yahoo. Как известно, интернет-компании зарабатывают практически все свои деньги (мягко скажем, немалые) на контекстной рекламе, которая продается через систему аукционов. Эта система должна быть эффективной, распределенной, работать одновременно для очень большого количества агентов и при этом, конечно, приносить интернет-гигантам максимальную прибыль. Для этого Google, Yahoo и другие аналогичные компании прикладывают значительные усилия для развития теории дизайна механизмов, и расцвет этого направления в последнее время во многом связан именно с интернет-нуждами. Мы не будем подробно рассматривать систему AdWords здесь; возможно, займемся ею в следующем курсе — в конце концов, она относится не к классическим, а к самым последним результатам в теории экономических механизмов [1,17,50]. Не стоит забывать и про eBay — крупнейшую систему интернет-аукционов; правда, eBay в основном не сам использует теорию аукционов, а предоставляет данные для обобщений экономистов [6,27].

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

Еще один важный пример, который тоже сыграл важную роль в теории экономических механизмов, — аукционы на радиочастоты (3G auctions). Эти аукционы проводятся между компаниями сотовой связи: государство за деньги разрешает той или иной компании использовать тот или иной диапазон частот. Традиционно эти аукционы тоже проводятся (или, по крайней мере, впоследствии анализируются) по последнему слову теории [33,34,51].

Есть и менее прямые и очевидные примеры применений, например компьютерные распределенные системы. В задаче планирования в реальном времени (real-time scheduling) к центральному процессору приходят все новые и новые задачи (заранее неизвестные), и процессор должен решить в срок как можно больше задач. Оказывается, что весьма разумно рассматривать подающее задачу устройство как агента, пытающегося максимизировать ожидание того, что задача будет решена. А центр, процессор пытается удовлетворить за данное время как можно больше заявок — то есть как раз максимизировать всеобщее благосостояние [8,66]. Есть и более забавные применения: так, недавно появился так называемый "Nobel powered BitTorrent client"; это peer-to-peer клиент, который работает так, чтобы участникам p2p-сети (в данном случае сети BitTorrent) было выгодно как можно более активно делиться файлами, максимизируя при этом суммарную доступность файлов сети [ 41].

Несколько забавных примеров

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

1. Дилемма заключенного. Мы начнем с так называемой дилеммы заключенного (prisoner's dilemma) — с классического примера из теории игр. Двое заключенных сидят в тюрьме. Им предлагают признаться в преступлении, заложив тем самым своего сообщника. Реальных доказательств главного пункта обвинения у прокуратуры нет, следователи могут рассчитывать только на помощь самих заключенных. Поэтому каждому из них предлагают сделку:

если оба заключенных промолчат, то оба отсидят по полгода за другие грешки;

если оба признаются, то обоим за такое примерное поведение дадут по два года;

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

Держать связь заключенные не могут. Как же поступить каждому из них?

Вот какая получается матрица возможных стратегий этой игры:

$$\begin{center} \begin{tabular}{r|cc} Промолчать Сознаться \\ \hline Промолчать (0.5,0.5) (10, 0) \\ Сознаться (0, 10) (2, 2) \end{tabular} \end{center}$$

Посмотрите, как интересно получается: вне зависимости от выбора первого заключенного второму в любом случае выгоднее признаться! Получается, что для каждого из них "Сознаться" — доминантная стратегия, и в результате... они будут сидеть по 2 года, а не по 0.5. Равновесие получается в доминантных стратегиях, но для каждого из игроков оно неоптимально! И все это получилось благодаря разумным действиям следователя, который смог разработать правильный дизайн "игры" с заключенными.

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

Если рекламы не будет вообще, у них будет одно распределение рынка, определенное производственными мощностями и другими факторами (сетью реализации, например). Предположим, что они обе будут получать прибыль по $$X$$. Если они обе будут активно рекламироваться, то реклама "взаимно сократится", потребитель будет хорошо осведомлен об обоих продуктах, и относительное потребление их продуктов не изменится. Но деньги на рекламу будут потрачены (обозначим их через $$A$$, от "advertising")! Таким образом, ситуация, когда обе фирмы рекламируются, хуже для них обеих. Но если одна фирма не будет рекламироваться, а вторая будет, то та, что будет, получит куда большую прибыль от резко увеличившейся доли рынка (для простоты предположим, что доля рынка вырастет до 100%).

$$\begin{center} \begin{tabular}{r|cc} С рекламой Без рекламы \\ \hline С рекламой (X,X) (2X-A,0) \\ Без рекламы (0,2X-A) (X-A, X-A) \end{tabular} \end{center}$$

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

2. Трагедия общин. Второй пример — так называемая трагедия общин. Этот пример имеет внушительную историю: он известен еще из Фукидида и Аристотеля. Трагедия общин возникает, когда у нескольких игроков на рынке есть некий общий ресурс. Выгоды от его использования индивидуальны, а затраты на использование общие, поэтому все пытаются максимизировать свое собственное использование ресурса, и ресурс истощается для всех.

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

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

3. Парадокс аукциона за доллар. Это пример того, к чему может привести дизайн хитрых механизмов.

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

Участники, разумеется, действуют рационально. Пусть минимальная разность между соседними ставками — один цент. Первый участник, желая заработать 99 центов, объявляет цену в один цент. Второй перебивает ее двумя центами, третий — тремя... Тут первый решает, что заработать 96 центов куда лучше, чем потерять один, и объявляет цену в 4 цента. И так далее.

Рано или поздно цена достигнет 98 центов (пусть такую цену в очередном раунде дал первый участник). Второй участник, желая заработать один цент, дает цену в 99 центов. Но для первого даже остаться в нуле гораздо лучше, чем потерять те 98, которые он уже объявлял! И он ставит 100 центов за доллар. А второй... ставит 101!

Адекватного решения у этого парадокса нет. Собственно, и "парадокса" нет — у игры нет равновесия, и игроки могут в конце концов отдать хитрому аукционеру все свои деньги. С другой стороны, конечно, "рациональность" игроков в этом аукционе тоже под вопросом: когда игрок решает, что выгоднее — потерять 98 центов или получить доллар за 100 центов, вторая альтернатива не равна нулю, а должна принимать во внимание вероятность того, что его оппонент не остановится и сделает новую ставку. Ожидание выигрыша составляет бесконечный расходящийся ряд потерь. С третьей же стороны, если все будут так "рационально" рассуждать, то никто не начнет торг, и не такой умный первый игрок, объявивший цену в один цент, спокойно получит свои 99 центов прибыли. Игры без равновесия — непростое дело...

4. Winner's curse. Возьмем следующую простую ситуацию (в следующих лекциях мы рассмотрим ее гораздо подробнее): есть аукцион, на торги выставлен товар, у каждого участника свое мнение о ценности товара. Участники делают ставки, исходя из своих понятий о ценности. Выигрывает тот, кто сделал самую большую ставку.

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

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

4. Парадокс Браесса. Это пример так называемой "цены анархии", который подтверждает, что зачастую свободный рынок приходит отнюдь не к оптимальному решению.

Рассмотрим две точки, "Старт" и "Финиш", между которыми есть два пути, проходящие через точки $$A$$ и $$B$$. Если машина едет по незаполненной трассе, она едет со скоростью 100 км/ч. Если трасса заполнилась, то скорость передвижения падает до

$$\text{Скорость передвижения}=\frac{\text{Пропускная способность}}{\text{Кол-во автомобилей}}(100\text{ км/ч}).$$

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

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

$$T = (100\text{ км})\frac1{100\text{ км/ч}} + (10\text{ км})\frac{1250}{500 \times 100\text{ км/ч}}= 1,25\text{ ч} = 75\text{ минут}$$

(в числителе первого слагаемого — единица, а не 1250/2000, потому что быстрее 100 км/ч ехать все равно не получится, даже если трасса заполнена лишь наполовину).

(рис 2.1) Парадокс Браесса: исходная ситуация

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

Рассмотрим старое равновесие (1250 на 1250). При появлении новой дороги по ней ехать будет выгоднее, и водители будут выбирать новую дорогу до тех пор, пока все три возможных пути не сравняются по времени. Новое равновесие (когда все пути одинаковы) достигается (проверьте это!), когда из 2500 машин 1500 едут по новой дороге, а по старым — по 500. Но давайте подсчитаем время в пути:

$$T = \frac{2000}{500}\frac{10\text{ км}}{100\text{ км/ч}} + 1\frac{60\text{ км}}{100\text{ км/ч}} + \frac{2000}{500}\frac{10\text{ км}}{100\text{ км/ч}} = \\ = 1,4\text{ ч} = 84\text{ минуты!} $$

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

Замечание. Может показаться, что путей не три, а четыре: вдруг появившийся после постройки новой дороги четвертый путь

$$\text{Старт}\to B\to A\to \text{Финиш},$$

несмотря на большую длину, все-таки будет в каких-то случаях достаточно эффективным, чтобы его избрать? Но при нашей постановке задачи он все-таки будет всегда строго хуже пути $$\text{Старт}\to B\to\text{Финиш}$$: даже если все 2500 машин едут по десятикилометровому участку $$B\to\text{Финиш}$$, там все равно можно добраться быстрее, чем в объезд по пустым дорогам.

(рис 2.2) Парадокс Браесса: после постройки новой короткой дороги

Важно заметить, что в некоторых формулировках парадокса Браесса новая дорога могла бы быть и на пользу. Для этого нужно было бы, грубо говоря, в пунктах "Старт" и $$A$$ посадить двух регулировщиков, которые будут распределять потоки как надо.

Давайте подсчитаем оптимальное время проезда в этой системе с 2500 машинами, если регулировщики работают оптимальным образом. Предположим, что регулировщик в точке "Старт" отправляет $$n$$ машин к $$A$$ и $$2500-n$$ сразу к $$B$$, а регулировщик в точке $$A$$ отправляет $$m$$ машин к точке "Финиш" и $$n-m$$ машин к $$B$$ по новой дороге.

Тогда время в пути будет равно

$$T = \left(\frac{n}{500}\right)^*\frac{10\text{ км}}{100\text{ км/ч}} + \left(\frac{n-m}{2000}\right)^*\frac{60\text{ км}}{100\text{ км/ч}} + \left(\frac{2500-m}{500}\right)^*\frac{10\text{ км}}{100\text{ км/ч}} = \\ = \frac{0.4\max\{n, 500\} + 0.6\max\{n-m, 2000\} + 0.4\max\{2500-m, 500\}}{2000}\text{ ч},$$

где звездочкой мы обозначили тот факт, что если числитель меньше знаменателя, то дробь равна единице. Если оптимизировать это по $$n$$ и $$m$$,

Этот эффект называется "ценой анархии" (price of anarchy): иногда регулируемый рынок действительно функционирует эффективнее, чем управляемый лишь невидимой рукой; наоборот, конечно, не бывает, потому что отсутствие вмешательства — частный случай вмешательства. Дизайн механизмов — один из способов (зачастую единственный) ввести на рынок "видимую руку" того, кто этот дизайн осуществляет.

Дизайн механизмов: определения

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

Поставим задачу чуть формальнее. Во-первых, введем тип агента $$\theta_i\in\Theta_i$$ для $$i$$ -го агента (об этом ниже). У игры есть набор исходов $$\mathcal O$$, и для каждого агента каждый исход означает какую-то прибыль (возможно, отрицательную). Так появляется функция полезности (utility function)

$$u_i(o,\theta_i)$$

для типа $$\theta_i$$ и исхода $$o$$. Агент $$i$$ предпочитает исход $$o_1$$ исходу $$o_2$$, если $$u_i(o_1,\theta_i) > u_i(o_2,\theta_i)$$.

Стратегия агента — это план, который полностью описывает его поведение во всех возможных состояниях окружающего мира. Через $$\Sigma_i$$ мы будем обозначать множество стратегий агента $$i$$, через $$s_i(\theta_i)\in\Sigma_i$$ — какую-нибудь конкретную его стратегию. Стратегии бывают чистые и смешанные; чистые стратегии жестко задают поведение в каждом состоянии окружающего мира, смешанные задают распределения вероятностей на множестве возможных действий агента.

Например, в аукционе возрастающей цены состояние мира для агента полностью описывается парой $$(p,x)$$, где $$p$$ — текущая цена, а бит $$x$$ показывает, является ли агент в текущий момент лидером аукциона. Пусть у агента есть своя (скрытая) оценка лота $$v$$, и он готов заплатить любую сумму, которая была бы меньше $$v$$ (получив при этом для себя выгоду, равную разности между $$v$$ и заплаченной суммой). Тогда так называемая стратегия лучшего ответа (best response strategy) $$s_{BR}(v)$$ описывается следующим образом:

$$b_{BR}(p,x,v)=\begin{cases} p, \text{если }x=0\text{ и }p>v, \\ \text{сидеть молча,} \text{в противном случае}.\end{cases}$$

Здесь $$b$$ (от слова bid) — это ставка, которую должен сделать агент. Понятно, что функцию полезности можно с конкретных исходов продолжить на целые стратегии. Если $$N$$ агентов имеют фиксированные стратегии $$(s_1,...,s_N)$$, то функция полезности

$$u_i(s_1,...,s_N,\theta_i)$$

будет просто равна функции полезности $$u_i(o,\theta_i)$$ на исходе $$o$$, который однозначно задается этими стратегиями.

Рассмотрим тот же аукцион, в котором участвуют два агента и оба исповедуют стратегию лучшего ответа. Для агента $$2$$ ценность лота $$v_2=1$$, для агента $$1$$ она равна $$v_1$$. Тогда функция полезности для первого агента будет равна

$$u_1(s_{BR,1}(v_1), s_{BR,2}(1)) = \begin{cases}v_1-(1+\epsilon), \text{если }v_1>1, \\ 0, \text{в противном случае},\end{cases}$$

где $$\epsilon$$ — минимальное увеличение цены в аукционе.

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

Обозначим через

$$\mathbf s=(s_1,\ldots,s_N)$$

профиль всех стратегий участников. Как и прежде, через

$$\mathbf s_{-i}=(s_1,...,s_{i-1},s_{i+1},...,s_N)$$

мы будем обозначать стратегии всех участников, кроме $$i$$. Введем также аналогичные обозначения $$\mathbf\theta$$ и $$\mathbf\theta_{-i}$$ для типов агентов.

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

Определение 2.1. Профиль стратегий $$\mathbf s$$ находится в равновесии Нэша, если каждый агент при данных стратегиях других агентов выбирает для себя оптимальную стратегию:

$$\forall s^\prime_i\neq s_i\quad u_i(s_i(\theta_i),\mathbf s_{-i}(\mathbf\theta_{-i}), \theta_i)\ge u_i(s^\prime_i(\theta_i),\mathbf s_{-i}(\mathbf\theta_{-i}), \theta_i).$$

В дилемме заключенного только профиль $$(\text{Сознаться},\text{Сознаться})$$ находится в равновесии Нэша — каждому из преступников всегда выгоднее сознаться, чем промолчать. Бывают игры с несколькими равновесиями Нэша.

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

	0	1
0	$100	-$100
1	-$100	$100

Очевидно, у этой игры два равновесия Нэша: $$(0,0)$$ и $$(1,1)$$. В каждом из этих состояний ни одному из игроков не выгодно отклоняться от выбранной стратегии.

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

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

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

Определение 2.2. Стратегия $$s_i$$ называется доминантной, если она (слабо) максимизирует ожидаемую прибыль агента для всех возможных стратегий других агентов:

$$\forall s^\prime_i\neq s_i,\ \forall \mathbf s_{-i}\in \mathbf\Sigma_i_{-i}\quad u_i(s_i,\mathbf s_{-i},\theta_i)\ge u_i(s^\prime_i,\mathbf s_{-i}, \theta_i).$$

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

Сейчас мы рассмотрим первый пример нетривиального дизайна механизмов — аукцион Викри (Vickrey auction). Это аукцион, проводящийся по схеме закрытых ставок (sealed-bid): участники подают свои заявки в конвертах, потом их вскрывают, и объект продается тому, кто предложил самую высокую цену. Например, так обычно проводят тендеры.

Что выгодно делать участнику со скрытой ценностью $$v$$, если ему продадут вещь по той цене, которую он запросит? Это довольно сложная задача: если его скрытая ценность максимальна из всех участников, ему нужно сделать заявку больше, чем у следующего за ним, но желательно только чуть-чуть больше, чтобы максимизировать свою прибыль. Участник, конечно, может решить эту задачу — но ему потребуется масса всяческих предположений, равновесие получится только в ожидании (то есть по Байесу-Нэшу), а не в любом случае (не в доминантных стратегиях), и вообще система будет весьма нестабильной. В результате на самом деле никому не лучше — и продавец не максимизирует доход, и всеобщее благосостояние тоже страдает. Мы потом проанализируем этот случай более подробно.

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

Теорема 2.1. В аукционе Викри правдивая стратегия $$b_i(v_i)=v_i$$ является доминантной.

Доказательство. Ожидаемая полезность стратегии $$b_i(v_i)=v_i$$ равна

$$u_i(b_i,b^\prime,v_i)=\begin{cases}v_i-b^\prime, \text{если }b_i>b^\prime, \\ 0, \text{в противном случае,}\end{cases}$$

где $$b^\prime$$ — это наивысшая ставка среди всех остальных агентов. Какие тут могут быть варианты?

Если $$b^\prime<v_i$$, то оптимальна любая ставка $$b_i\ge b^\prime$$, ведь вещь все равно продадут по цене $$b^\prime$$.

Если $$b^\prime\ge v_i$$, то, опять же, оптимальна любая ставка $$b_i\le v_i$$ (все равно не продадут или продадут с нулевой прибылью).

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

Мы только что буквально на пальцах доказали, что в аукционах Викри каждому участнику выгодно сообщать в качестве ставки свою истинную скрытую стоимость. Это очень важное свойство механизмов — правдивость (truthfulness). Позже (в лекции 3) мы увидим, что на самом деле можно ограничиться только правдивыми механизмами.

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

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

Определение 2.3. Профиль стратегий $$\mathbf s$$ находится в равновесии по Байесу-Нэшу (Bayesian-Nash equilibrium), если каждый агент при известном ему распределении $$F(\mathbf\theta)$$ на типах других агентов выбирает для себя оптимальную стратегию: $$\forall s^\prime_i\neq s_i$$

$$\mathbf E_{F(\mathbf\theta)} u_i(s_i(\theta_i),\mathbf s_{-i}(\mathbf\theta_{-i}), \theta_i)\ge \mathbf E_{F(\mathbf\theta)} u_i(s^\prime_i(\theta_i),\mathbf s_{-i}(\mathbf\theta_{-i}), \theta_i).$$

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

Равновесие по Байесу-Нэшу обобщает обычное — оно делает более естественные предположения о знаниях агентов. Для каждого фиксированного типа $$\bar\theta_i$$ оно тоже должно быть оптимальным: $$\forall s^\prime_i\neq s_i$$

$$\mathbf E_{F(\mathbf\theta)}\left[u_i(s_i(\bar\theta_i),\mathbf s_{-i}(\mathbf\theta_{-i}), \theta_i)\mid\bar\theta_i\right] \ge\mathbf E_{F(\mathbf\theta)}\left[u_i(s^\prime_i(\bar\theta_i),\mathbf s_{-i}(\mathbf\theta_{-i}), \theta_i)\mid\bar\theta_i\right].$$

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

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

$$\text{Равновесие в доминантных стратегиях} \\ \succ \text{Равновесие по Байесу-Нэшу} \\ \succ \text{Равновесие Нэша}.$$

Перейдем теперь собственно к дизайну.

Основные понятия дизайна механизмов

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

Определение 2.4. Функцией социального выбора называется функция

$$f:\Theta_1\times\ldots\times\Theta_N\to\mathcal O,$$

которая выбирает тот или иной желаемый результат $$f(\mathbf\theta)$$ при данных типах $$\mathbf\theta=(\theta_1,...,\theta_N)$$.

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

(рис 2.3) Участники экономического механизма

Определение 2.5. Механизм $$\mathcal M=(\Sigma_1,...,\Sigma_N,g)$$ состоит из наборов стратегий $$\Sigma_i$$ для каждого агента и функции исходов $$g:\Sigma_1\times\ldots\times\Sigma_N\to\O$$, которая определяет исход, предусмотренный механизмом для полученного на вход профиля стратегий

$$\mathbf s=(s_1,...,s_N)\in \Sigma_1\times\ldots\times\Sigma_N.$$

На рис. 2.3 изображено то, что агенты обычно знают о себе и других агентах; они выбирают стратегии $$s_i$$ так, чтобы максимизировать вероятность удачного исхода, а затем "механизм", собрав все "ставки", определяет собственно исход. Кавычки здесь потому, что и механизма может как такового не быть, и ставки могут быть весьма непривычными.

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

Определение 2.6. Механизм $$\mathcal M=(\Sigma_1,...,\Sigma_N,g)$$ реализует функцию социального выбора $$f:\Theta_1\times\ldots\times\Theta_N\to\O$$, если для всех возможных векторов типов $$\mathbf\theta=(\theta_1,\ldots,\theta_N)\in\Theta_1\times\ldots\times\Theta_N$$

$$g(s_1^*(\theta_1),...,s_N^*(\theta_N))=f(\mathbf\theta),$$

где профиль стратегий $$(s^*_1,...,s^*_N)$$ находится в равновесии по отношению к игре, индуцированной $$\mathcal M$$.

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

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

$$g(\theta)=f(\theta).$$

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

$$\max\limits_{\theta^\prime\in\Theta_i}\mathbf E_{\mathbf\theta_{-i}}u_i(\theta^\prime,\mathbf s_{-i}(\mathbf\theta_{-i}),\theta_i).$$

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

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

Определение 2.7. Функция социального выбора $$f:\Theta_1\times\ldots\times\Theta_N\to\mathcal O$$ называется оптимальной по Парето, если для всякого вектора типов $$\mathbf\theta=(\theta_1,\ldots,\theta_i)$$ и всякого исхода $$o^\prime\neq f(\mathbf\theta)$$

$$u_i(o^\prime,\theta_i)>u_i(f(\mathbf\theta),\theta_i) \quad \Rightarrow \quad \exists j:\ u_j(o^\prime,\theta_j) < u_j(f(\mathbf\theta), \theta_j).$$

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

Давайте приведем пример, демонстрирующий, что оптимальность по Парето еще не гарантирует правдивости механизма.

Пример 2.2. Рассмотрим множество исходов $$\mathcal O=\{x,y,z\}$$ и предположим, что действуют два агента. У первого агента ровно один тип, $$\Theta_1=\{\theta_1\}$$, и у этого типа структура предпочтений такова:

$$x>_1y>_1z.$$

А у второго агента два разных типа $$\Theta_2=\{\theta^a_2,\theta^b_2\}$$, и вот их структура предпочтений:

$$z>^a_2y>^a_2x,\quad y>^b_2x>^b_2z.$$

Мы пытаемся реализовать эффективную по Парето (проверьте!) функцию социального выбора:

$$f(\theta_1,\theta_2^a)=y,\qquad f(\theta_1,\theta_2^b)=x.$$

Если мы захотим просто спросить у каждого агента его тип, второму будет выгодно соврать: при типе $$\theta_2^b$$ ему будет выгодно сказать, что он $$\theta_2^a$$, и получить в результате исход $$y$$, а не $$x$$.

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

Можно теперь ввести вполне естественное определение оптимального по Парето механизма.

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

Это определение на самом деле предполагает, что исход окажется оптимальным по Парето уже для конкретных типов агентов, после того как все типы окажутся известными, и функция социального выбора отработает на векторе типов. Такая ситуация, когда некоторое понятие рассматривается апостериорно, называется в теории экономических механизмов ex post. Можно рассматривать оптимальность по Парето ex ante, когда нет исхода, который бы в ожидании строго предпочел один агент и нестрого — все остальные. Получится более слабое определение.

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

Ex ante — до выбора исходов. Ex ante агенты знают только распределения (все, включая свое собственное). Информация у всех агентов одинаковая.

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

Ex post — после того как типы (точнее, стратегии) всех агентов стали известны. Здесь уже поздно что-либо менять; ex post ситуацию рассматривают в тех случаях, когда хотят показать, что ни один агент даже постфактум не пожалеет о сделанном выборе.

То же самое можно сформулировать чуть более конструктивно: о равновесиях или ограничениях можно говорить в трех случаях.

Ex ante — в терминах распределений типов агентов.

Interim — в терминах распределений типов агентов и одного конкретного типа одного агента.

Ex post — в терминах вектора типов всех агентов.

Предположения об агентах

Мы вскоре увидим, что про агентов с произвольными множествами типов можно доказать массу отрицательных результатов. Фактически, с ними нельзя сделать ничего толкового, нельзя реализовать ни одной нормальной функции социального выбора (о том, какие функции ненормальные, мы поговорим в лекции 6).

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

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

Определение 2.9. Квазилинейная функция полезности агента $$i$$ с типом $$\theta_i$$ имеет вид

$$u_i(o,\theta_i)=v_i(a,\theta_i)-p_i,$$

где исход $$o$$ определяет выбор $$a\in\mathcal K$$ из дискретного множества $$\mathcal K$$ и выплату $$p_i$$, производимую агентом.

У агента с квазилинейными преференциями вместо общего вида функции полезности появляется тоже достаточно общего вида функция оценки (valuation function) $$v_i(a)$$, $$a\in\mathcal K$$. Например, на аукционе, где продается одна вещь, $${\mathcal K}=\{0,1\}$$ — агент либо получит эту вещь, либо не получит. А $$p_i$$ в этом случае — выплата агента продавцу. Это достаточно естественное предположение в случае аукциона.

Есть еще одно предположение, которое в жизни часто не выполняется (хотелось написать "к сожалению", но, может, и к счастью). Мы в дальнейшем будем для простоты предполагать, что агенты нейтральны к риску (risk-neutral agents). Что это значит?

В экономике агенты различаются между собой по своему отношению к риску. Можно совсем упростить ситуацию: предположим, что агент может получить возможность с вероятностью $$\frac12$$ получить $100. Тогда:

осторожный (risk-averse) агент готов заплатить за эту возможность сумму, строго меньшую $50;

нейтральный к риску (risk-neutral) агент готов заплатить за эту возможность ровно $50;

рисковый (risk-loving) агент готов заплатить больше $50.

В жизни часто встречаются осторожные агенты (risk-averse agents). Сами посудите: вы готовы заплатить $999 за возможность подбросить монетку и выиграть $2000 при удачном ее выпадении? А нейтральные к риску агенты рассматривают это предложение как очень выгодную сделку.

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

(рис 2.4) Осторожный агент

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

$$U(p) = \sum\limits_{x}p(x)u(x),$$

где сумма берется по возможным исходам лотереи, а $$u(x)$$ — полезность агента от исхода $$x$$. Например, в лотерее с двумя исходами, $$z_1$$ и $$z_2$$, и вероятностью выпадения исхода $$z_1$$, равной $$p$$ (пусть без потери общности, $$u(z_2)>u(z_1)$$ ), ожидаемая полезность играющего в лотерею агента равна

$$U(p) = pu(z_1) + (1-p)u(z_2)$$

(на рис. 2.4 этой функции соответствует прямая между точками $$A$$ и $$B$$ ).

Основная суть осторожного агента в том, что для него получить просто сумму в $$z$$ денег выгоднее, чем играть в лотерею с ожиданием $$\mathbf E[u] = z$$. Иначе говоря, полезность $$u(z)$$ должна быть у него выше, чем $$U(p)$$ (см. рис. 2.4). Это значит, что функция полезности денег для осторожного агента должна быть вогнутой (ее вторая производная, если она существует, должна быть отрицательной).

Можно даже выработать численный показатель того, насколько осторожен агент. Поскольку полезность определена с точностью до аффинных преобразований, просто вторая производная не подойдет. Зато подойдет так называемый коэффициент неприятия риска Эрроу-Пратта (Arrow-Pratt measure of absolute risk aversion, ARA) [4,67]:

$$A_u(w) = -\frac{u^{\prime\prime}(w)}{u^\prime(w)}.$$

Для этой меры справедлива следующая теорема (которую мы доказывать не будем).

Теорема 2.2. Для некоторых функций полезности $$u$$ и $$v$$ неравенство $$A_u(w) \ge A_v(w)$$ верно тогда и только тогда, когда существует такая возрастающая вогнутая функция $$h$$, что $$u(w) = h(v(w))$$.

Проще говоря, если $$A_u$$ доминирует над $$A_v$$, то $$u$$ "более вогнутая", чем $$v$$. Посредством этой меры можно оценивать, насколько осторожен тот или иной агент.

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

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

Пример 2.3. Этот классический пример называется парадоксом Элсберга, хотя история его восходит еще к Кейнсу [l,18,32]. Рассмотрим урну, содержащую 30 красных шаров и 60 других шаров, которые либо черного, либо желтого цвета. Вы не знаете, сколько там черных шаров, а сколько желтых, но знаете, что в сумме тех и других ровно 60. Вам предлагают выбор из двух вариантов:

A. Вы получаете $100, если вытащите красный шар.

B. Вы получаете $100, если вытащите черный шар.

Кроме того, вам предлагают и другой выбор.

C. Вы получаете $100, если вытащите или красный, или желтый шар.

D. Вы получаете $100, если вытащите или черный, или желтый шар.

Поскольку доход одинаковый, то если вы последовательно предпочитаете $$A$$ перед $$B$$, это значит, что вы верите, что вытащить красный шар строго более вероятно, чем вытащить черный шар. Аналогично, если вы последовательно предпочитаете $$C$$ перед $$D$$, это значит, что вы верите, что вытащить красный или желтый более вероятно, чем вытащить черный или желтый. Заметим, что в такой ситуации, если вы верите, что красный вероятнее черного ( $$A$$ лучше $$B$$ ), то автоматически "красный или желтый" становится более вероятным, чем "черный или желтый" (к вероятности просто прибавляется непересекающееся событие, одинаковое в обоих случаях — читатель может сам строго выписать вероятности и убедиться в этом). То есть человек, выбирающий $$A$$, должен выбирать $$C$$. Этот результат совершенно не зависит от степени осторожности агента: любая альтернатива включает в себя риск, и следствие "если $$A$$ лучше $$B$$, то $$C$$ лучше $$D$$ " сохраняется при любой поправке на осторожность (проверьте это!).

Однако проведенные эксперименты показывают, что большинство людей последовательно и строго предпочитают $$A$$ перед $$B$$ и $$D$$ перед $$C$$! Попробуйте сами опросить своих знакомых — наверняка получится нечто подобное, если, конечно, опрашивать будете не специалистов по теории вероятностей.

Получается, что люди предпочитают известный, хотя и больший, риск неизвестному риску, что противоречит теории ожидаемой пользы, которой мы сейчас слегка коснулись. Этот парадокс можно объяснить, если принять, что агент пытается минимизировать не просто свой риск, но некоторую комбинацию из риска и своего знания о риске. Получается крайне интересная теория, так называемая info-gap decision theory, которую мы, к сожалению, в этой книге рассматривать не будем [9].

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