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

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

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

• Так как же разработать игру, которая побуждает всех правдиво сообщать о своих коммунальных услугах?
• Какие ставки следует использовать: открытые или закрытые, по возрастанию или по убыванию?
• Должен ли победитель заплатить самую высокую объявленную цену или другую цену?
• Равным образом, при разработке процесса голосования, который всегда выбирает кандидата, которого все избиратели предпочитают всем другим кандидатам, следует ли выбирать победителей на основе большинства?
• Должен быть один или несколько туров голосования?
• Должны ли избиратели подавать единичный вариант выбора или предпочтения?

Это типичные вопросы в конструкции механизмов.

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

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

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

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

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

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

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

Это то, о чем говорят, когда вы видите ссылки на «квазилинейные» коммунальные услуги, т.е. Предпочтения линейны в денежной / транзакционной составляющей.

На практике, как дизайнер, вы можете контролировать выбор механизма, но не игроков или их типы. Вы можете видеть эти «заданные» элементы, называемые настройками.

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

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

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

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

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

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

Теперь, когда мы определили некоторые основные термины, какие типы результатов мы можем использовать при разработке механизма?
Что такое «хороший» механизм и как убедиться, что мы его выбрали?

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

Имеет смысл ввести некоторые из наиболее распространенных ограничений, с которыми вы столкнетесь:

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

Ключевая проблема, возникающая в теории проектирования механизмов, заключается в том, что ограничения, такие как

• баланс бюджета,
• эффективность
• индивидуальная рациональность,

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

Как правило, особенности механизмов, можно сказать, справедливы и для агентов:

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

Возвращаясь к нашей аналогии с покером, вы можете подумать о том, какие заявления вы можете сделать до того, как какие-либо карты будут вытянуты из колоды (ex-ante), когда вы знаете свою собственную руку (ex-interim) и когда все руки будут раскрыты (ex-post).

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

Например, на аукционе вы можете искать совместимый со стимулами, индивидуально рациональный механизм, который максимизирует доход.

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

Набор очень мощных механизмов, с которыми вы часто будете сталкиваться, известен как Vickrey-Clarke-Groves механизмы.

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

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

Обобщением аукциона Викри является основной механизм (также называемый механизмом Кларка или «механизмом VCG», хотя VCG иногда может относиться к более общему классу механизмов).

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

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

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

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

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

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

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

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

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

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

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

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

Например, скажем, у меня есть друг в тренерском штабе Голден Стэйт, который сказал мне, что Стеф Карри повредил лодыжку. Непонятно, как такую ​​частную информацию можно преобразовать в точную вероятность того, выиграет ли Golden State свою следующую игру (PS, я не питаю зла на Стеф Карри или его лодыжку).

Как и в случае с аукционами, при рассмотрении децентрализованной версии этих рынков возникает особый набор проблем.

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

Эта статья Карлстена и др. является отличным примером того, как можно использовать дизайн механизмов при рассмотрении децентрализованных систем. Авторы утверждают, что, хотя Namecoin решает критическую техническую проблему (эффективно возводит в квадрат треугольник Зуко), система сталкивается с рядом сложных экономических проблем. В статье показано, что лишь 0,02% зарегистрированных доменов принадлежали не скваттерам и на момент написания отображали нетривиальный контент, в то время как вторичный рынок доменов практически отсутствовал. Я считаю, что это подтверждает тот факт, что как создатель протокола вы просто не можете пренебрегать разработкой надлежащих стимулов для пользователей, независимо от технических достоинств вашего проекта.

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

Анализ также рассматривает влияние различных вариантов выбора в пространстве дизайна: насколько сильным должен быть индивидуальный контроль над именем?
Как первичный рынок должен распределять имена?
Как должна система перераспределять выручку от продаж имен?

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

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

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

Возможно, наиболее активным исследованием приложений проектирования механизмов в мире криптовалюты является работа фонда Ethereum

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

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

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

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

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

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

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

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

Таким образом, злоумышленник может эффективно испортить игру с большим бюджетом, но с нулевыми фактическими затратами, поскольку ни один из подкупленных перебежчиков не окажется в большинстве. Биткоин и другие протоколы Proof-of-Work, по крайней мере теоретически, уязвимы для этого типа атак (хотя кто-то должен достоверно продемонстрировать огромный бюджет).

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

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

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

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

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

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

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

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

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

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

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

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

Еще меньше ученых-экономистов начали серьезно изучать теоретико-игровые свойства протоколов блокчейн.

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