От Нэша до Ляпунова
Знать, куда вы хотите отправиться, - это не то же самое, что добраться туда и другие математические темы, изложенные на простом английском языке.
Равновесие Нэша - любимая концепция игроков в покер, экономистов и компьютерных ученых. В настоящий момент криптосообщество с энтузиазмом занимается изучением алгоритмической теории игр. Наиболее частая мотивация - это разработка и анализ криптоэкономических протоколов. Я предпочитаю думать о них как о координационных протоколах, поскольку они переключают внимание на общую цель, для достижения которой протокол предназначен, а не на ложное предположение о том, что рассматриваемые игры по своей природе имеют нулевую сумму.
Нэш - вполне разумное место для начала, поскольку равновесие Нэша характеризуется игрой и набором стратегий всех игроков, для которых это не является односторонним стимулом к отклонению. Нэш доказал, что в случае игр N игроков всегда существует такое равновесие, если мы допускаем смешанные стратегии. Равновесие Нэша - это частный случай неподвижной точки, определенной для формальных математических объектов, которые мы называем играми. По мере того, как сами игры становятся более сложными, например, с большим количеством игроков, асимметрией или более сложной динамикой, определяющей взаимосвязь выплат для игроков, доказательство существования фиксированной точки становится намного менее полезным.
Во-первых, существование и уникальность - это разные математические свойства неподвижных точек. Обнаружение, определение или вывод равновесия по Нэшу для конкретной игры не исключает существования других равновесий по Нэшу. Можно доказать, что в некоторых играх нет чистого равновесия по Нэшу, что означает, что требуются смешанные или рандомизированные стратегии - например, камень, ножницы, бумага. Равновесие по Нэшу - это то, что каждый игрок с равной вероятностью выбирает одного из трех.
Внедрение смешанных стратегий - это и благословение, и проклятие. За счет введения возможности применять стратегии с энтропией основная проблема оптимизации наилучшего ответа превращается в непрерывную область из потенциально трудноразрешимой комбинаторной проблемы. Такое расслабление известно тем, что делает трудные проблемы решаемыми. Однако для произвольных функций вознаграждения это может быстро привести к большому количеству равновесий, фактически локальных оптимумах.
Столкнувшись с проблемой, когда целью разработки игры является создание скоординированного результата, разумно охарактеризовать глобальную награду или социальную функцию полезности, кодирующую цель игры. В хорошо продуманной игре будут четкие математические отношения между функциями вознаграждения локальных агентов и глобальной целью. Подробнее об этом позже, сначала давайте определим инструмент для оценки конкретного равновесия.
Цена анархии сравнивает социальную полезность равновесия по Нэшу с социальной полезностью профиля стратегии, определяемой централизованной максимизацией стратегического пространства всех игроков, как если бы один всеведущий игрок играл каждого агента. Эти результаты ограничивающего типа помогают оценить, насколько хорошо конкретная игра обеспечивает координацию для достижения конкретной общей цели.
Эталонными примерами для игр с высокой ценой анархии являются Дилемма заключенных для двух игроков и трагедия общества для многих игроков. В каждом из этих случаев профили локально оптимальной стратегии для отдельных агентов приводят к ошеломляюще неблагоприятному исходу не только по отношению к центральному оптимальному решению, но на самом деле все стороны также находятся в строго худшем положении в их соответствующих локальных функциях вознаграждения.
Это подводит нас к обсуждению того, какими должны быть глобальные социальные услуги. Эти примеры демонстрируют, что простое определение социальной полезности как суммы индивидуальных функций вознаграждения не обязательно приводит к желаемым результатам. На самом деле, возможно, виновата сама независимость местных функций вознаграждения.
В других задачах координации, таких как флокирование, именно соединение целевых функций приводит систему к оптимальной координате. Обзор исследований мультиагентной координации на основе биологических факторов обнаруживает возникновение координации в рамках консенсусных процессов. В отличие от алгоритмов консенсуса, обсуждаемых для решения проблемы византийского генерала, которая является комбинаторной проблемой, эти процессы консенсуса включают динамические системы и координацию в непрерывно оцениваемом пространстве состояний. Существуют фундаментальные алгоритмы усреднения, способные обеспечить потрясающе надежную сходимость к скоординированному равновесию.
Обратите внимание, что традиционно теория игр не оснащена инструментами сходимости, несмотря на то, что динамика является ключевым элементом теории неподвижных точек. В случае теории игр подразумеваемый процесс - это сама игра, или, точнее, совместный процесс каждого игрока, ищущего оптимальный лучший ответ друг другу. В одноразовой игре, которая является базовой конструкцией, этот поиск происходит полностью в сознании игрока, пытаясь рекурсивно оценить действия всех остальных по отношению к их собственным. Наивный подход состоит в том, чтобы просто использовать точку Шеллинга, но другая крайность - это неразрешимая бесконечная рекурсия. К счастью, реальная реализация теоретико-игровых структур редко бывает однократной, и повторение меняет природу проблемы. Объединение и временная динамика порождают радикально разные профили риска и, следовательно, парадигмы принятия решений, как часто указывал Н.Н. Талеб .
Чтобы ввести понятие динамики, мы переходим к повторяющимся играм, в которых стратегии характеризуются как зависимые от состояния или даже исторически зависимые функции. Полная историческая траектория включает в себя историю всех состояний и действий, произведенных при многократном прохождении игры с набором других агентов. Фактически, агенты, принимающие решения, имеют некоторую политику ввода-вывода с ограниченным пространством ввода, но набор всех таких политик должен иметь несколько, если вообще какие-либо другие предположения, связанные с ним формально; По иронии судьбы то, что является рациональной целью, является субъективным утверждением.
Математика быстро усложняется, и лучшие ответы быстро становятся трудноразрешимыми, и даже хорошие решения требуют больших вычислительных ресурсов, включая такие методы, как динамическое программирование. Мы не пойдем слишком далеко по этому пути; в конце концов, если равновесие слишком сложно вычислить или, как в данном случае, требует высокой абстрактной функциональной оптимизации за дисконтированное время, нельзя реалистично ожидать, что открытая экономика обнаружит его естественным образом.
Вместо этого давайте сосредоточимся на простоте нашей био-вдохновленной координации и важности введения понятия динамики. Поскольку большая часть литературы о блокчейнах родилась в области экономики и информатики, она также не имеет естественного представления о динамике. Это не случайно, ранее в этом году я опубликовал статью, в которой строится именно эта конструкция для экономик, использующих блокчейн. Создав основу для динамики, я с уверенностью могу перейти к обсуждению другого класса игр, которые гораздо более практичны для инженеров.
Возможные игры - это игры, в которых целями могут быть потенциальные поля. В целях согласования с литературой по выпуклой оптимизации мы будем думать о максимальном вознаграждении как о минимизации штрафа (который является в точности отрицательным для функции вознаграждения).
В такой потенциальной игре минимумы в потенциальном поле - это равновесия по Нэшу. Кроме того, при повторении одной и той же игры можно рассматривать динамику развивающихся стратегий и действий агентов как реализации алгоритмов типа стохастического градиентного спуска. Если каждый локальный агент делает движение индивидуально под уклон, то это шаг под уклон в глобальной цели до тех пор, пока градиент глобальной цели имеет отрицательный внутренний продукт с общесистемным вектором обновления, определяемым всеми этими индивидуальные действия. Это может показаться сложным, но это всего лишь определение алгоритма спуска.
Этот результат говорит нам, что мы обнаружим локальный минимум, который сам по себе является одним из потенциально многих равновесий по Нэшу в общем случае. Однако, как разработчик указанной игры, можно добиться большего, если выполнить требование, чтобы функция глобального потенциала была выпуклой. Это снимает критическую дискуссию, которую мы обсуждали ранее, об уникальности. Алгоритм типа спуска будет итеративно сходиться к уникальному глобальному минимуму выпуклой функции, наивно спускаясь по ее градиенту.
Однако у нас все еще есть одна проблема, я говорю о функции глобального потенциала. Мы разрабатываем местные стимулы, а не глобальные. Это то место, где необходима небольшая математика. Как мы соединяем наши глобальные и локальные функции? Оказывается, что в литературе по выпуклому анализу есть много хороших результатов, касающихся выпуклых функций. Некоторые полезные из них - это суммы выпуклых функций, квадратичные формы с любой положительно полуопределенной матрицей, супремум по любому набору выпуклых функций и наиболее распространенные функции регуляризации. Не нужно сейчас беспокоиться об этих деталях, потому что вы можете найти их, когда они вам понадобятся. Важным моментом является то, что существует множество способов создания математически правильно выровненных локальных и глобальных выпуклых функций полезности, если вы знаете, какое координационное поведение вы разрабатываете.
С этой точки зрения разработки протокола координации на самом деле нет другого алгоритма оптимизации, кроме самих агентов, поэтому основные представляющие интерес результаты - это результаты сходимости и стабильности вокруг равновесия Нэша, которое является уникальным глобальным минимумом, без необходимости характеризовать агентов. поведение за пределами уменьшения потенциальной функции в ожидании. Этот тип случайного процесса называется супермартингалом, который фактически позволяет каждому агенту довольно часто действовать вопреки собственным интересам, не нарушая свойств сходимости.
Что касается экономических систем, мне особенно нравится эта конструкция, потому что она дает очень слабое понятие рациональности: агентам не нужно играть наилучшим образом, им просто нужно опускаться в ожидании, что допускает немалую иррациональность или даже временный антагонизм. Поскольку эти потенциальные функции в значительной степени имеют финансовую природу, можно довольно разумно предположить, что постоянные попытки подняться до потенциальной функции, эффективно работающей против протокола координации, всегда будут стоить вам денег. Без бесконечного запаса средств человек в конечном итоге упадет в потенциальную яму только для того, чтобы оставаться платежеспособным.
В качестве преимущества введения концепции динамических систем существует гораздо более полная теория, связанная с устойчивостью вокруг неподвижных точек. Результат может идти от крайне абстрактного типа теоремы Брауэра о неподвижной точке до практических результатов по супермартингальной сходимости случайных процессов. В частном случае экономики блокчейна реальным углом будет схождение к окрестности равновесия и доказательством того, что событие, когда государство покидает это соседство, имеет нулевую меру, что делает его вероятность бесконечно малой. Я уже писал доказательства такого рода для децентрализованных алгоритмов. Хотя формально они могут потребовать больших усилий, неформальное доказательство довольно интуитивно понятно. Вы можете представить себе воду, стекающую с холма и сходящуюся в самой нижней точке; даже если в образовавшемся бассейне есть турбулентность, он все равно остается в нижней точке.
Это более или менее охватывает темы, необходимые для превращения сети агентов в рамках единого механизма с единой целью в проблему эволюционной оптимизации, где генетический процесс неизвестен. Этот подход по-прежнему в основном основан на структурах стимулов и предположении, что стимулы агентов фактически соответствуют местным коммунальным предприятиям, из которых был разработан механизм.
На практике часто существуют внешние эффекты, заставляющие агентов отдавать предпочтение действиям, отличным от предполагаемых в модели. Одним из основных преимуществ блокчейна в экономических сетях с внешними эффектами является то, что затраты на эти внешние эффекты могут быть смоделированы в качестве стимулов, и реальные затраты могут быть возложены на агентов, чтобы избежать сбоев в координации, как в случае трагедии общества.
Во время этого обсуждения мы приложили все усилия, чтобы найти самые слабые предположения о поведении агентов, от которых мы можем реально ожидать сходимости к окрестности известного равновесия. Существует концепция следующего уровня, которую я считаю не менее важной, если не более важной: пространства конфигурации или достижимые пространства. Эти темы также встречаются в обучении с подкреплением, связанном с агентами, которые должны узнавать о своей среде, взаимодействуя с ней.
Когда система определяется тем, как она может изменяться, как в случае с сетями блокчейнов, для которых должны быть явные правила, определяющие все законные транзакции, текущего состояния и набора всех юридических действий достаточно, чтобы охарактеризовать все состояния, которые могут быть достигнуты. в будущем. Что еще более важно, эти наборы юридических действий разрабатываются как часть процесса проектирования экономической системы.
Эти пространства действий определяют все возможное поведение агентов независимо от мотивации или стимулов, а полученные пространства конфигурации определяют все возможные будущие состояния. Полезно рассмотреть эти концепции в контексте других целей высокого уровня, таких как планирование движения.
Предположим, у вас есть инструмент для разработки этих наборов юридических действий, чтобы гарантировать, что цели вашей системы были зафиксированы в самом пространстве конфигурации, а не в качестве побочного продукта какой-либо конкретной модели поведения. Можно в принципе игнорировать все модели поведения агентов, за исключением предположения, что цепочка блоков гарантирует, что все предпринимаемые действия разрешены. Удобно, что именно это и делают консенсусные алгоритмы в сети блокчейнов: независимо от попыток агентов, в противном случае фактически происходит только действительная транзакция.
У нас действительно есть этот инструмент, и мы его уже используем; он называется инвариантом как в информатике, так и в динамических системах. Инвариант - это любая функция пространства состояний, которая остается неизменной при судебном иске. Основываясь на этом, мы можем рассматривать любые скалярные функции пространства состояний и исследовать, как они развиваются при всех юридических действиях. В моей статье мы математически исследуем, как сумма всех биткойнов остается равной сумме всех вознаграждений за майнинг, несмотря на бесконечно увеличивающееся количество уникальных учетных записей. Сама сумма всего биткойна является скалярной функцией состояния.
Все становится очень интересно, когда мы исследуем более общие скалярные функции состояния системы, которые я называю функциями значения. Функции значений, должным образом объединенные с состояниями судебного иска, могут привести пространство конфигурации системы к желаемому подпространству способом, который можно доказать в соответствии с теоремой Брауэра о фиксированной точке, упомянутой ранее.
Это очень неинтуитивный подход, потому что мы на самом деле не обсуждаем, что делают агенты или в каком состоянии находится система, а, скорее, делаем топологические аргументы относительно пространств действий и достижимых пространств состояний при любой последовательности этих действий. Аналогичные абстрактные методы применяются для формального доказательства сходимости алгоритмов управления при высоких степенях неопределенности с использованием неотрицательных скалярных функций состояния, называемых функциями Ляпунова. Об этих функциях можно думать как о дополнении существующих энергетических полей, таких как гравитация, дополнительными полями, наполненными стимулами или другими математическими конструкциями, которые существенно изменяют форму пространства, ну, фактически, киберпространства.
Методы Ляпунова демонстрируют свойства системы, исследуя, как скалярные функции, кодирующие желаемые свойства, развиваются при всех юридических изменениях состояния, которые в поле управления определяются композицией системного объекта и контроллера, спроектированных для изменения поведения замкнутого цикла этой системы. Слишком распространенное заблуждение о теории управления состоит в том, что у человека есть много возможностей контроля; на самом деле контролеры - от всеведущих и всемогущих. Все поле вращается вокруг того, чего можно достичь с ограниченными степенями управляемости и наблюдаемости. В связи с этим работа большинства элементов управления в достаточной степени неотличима от оптимизации и ИИ для конкретных задач, поэтому она больше не привлекает внимания как область, которой она заслуживает.
Хотя системы блокчейнов интуитивно отличаются от систем управления, они имеют глубокое математическое сходство. Примечательно их систематическое разложение между внутренней динамикой и входными данными, что наиболее очевидно в представлении линейной модели пространства состояний.
Установив инварианты как скалярные функции, которые остаются неизменными, можно распространить это понятие на любые функции с доказуемыми желаемыми свойствами в рамках набора законных транзакций. Свойство сходимости или слежения к желаемому подпространству может быть закодировано с использованием такой конструкции, как функция Ляпунова, которая, если вернуться к предыдущим обсуждениям, лучше всего понимать как обобщенную потенциальную функцию. Неформальные доказательства сходимости и устойчивости по Ляпунову очень похожи на наши аргументы для потенциальных игр и выпуклой функции, но абстрагированы до функций и пространств. Чуть более конкретные примеры можно найти в теории массового обслуживания сетей. Мои последние работы в этой области можно найти здесь.
С момента вступления в сообщество исследователей блокчейнов я возобновил свою работу и начал создавать область исследований на стыке теории оптимизации, динамических систем и теории игр, которая, как я утверждаю, представляет первостепенный интерес для сообщества блокчейнов, поскольку она обеспечивает наиболее общие возможны гарантии поведения системы.
Что касается семантики, я считаю, что вполне уместно, чтобы область криптографии была расширена для учета экономики таким образом, чтобы доказывать факты о том, что может и не может произойти, а не просто что является или не может быть вероятным при определенных условиях. поведенческие предположения ». Предварительные рамки этого общего подхода представлены здесь (третий раз - шарм). Помните: все модели неправильные, но некоторые полезны; Надеюсь, моя вам пригодится.
