UIC, MIC и OCA Входят в батонку ... и разорвать механизм дизайн
5 августа 2025 г.Таблица ссылок
Аннотация и 1. Введение
1.1 Наши вклад
1.2 TFM Поощрительные представления о совместимости: шпаргалка
Определения
2.1 Механизм платы за транзакцию
2.2 Представления о совместимости стимулирования
Предварительная: лемма Майерсона
Разминка: невозможность UIC + MIC + Global SCP для детерминированных механизмов
Невозможность UIC + MIC + Global SCP для рандомизированных механизмов и 5.1 Доройся
5.2 Формальные доказательства
Осуществимость и невозможность UIC + MIC + OCA-защита
6.1 Непотянутый механизм с UIC + MIC + OCA-защищенным
6.2 Невозможность UIC + MIC + OCA-защита для правдивых механизмов
Как обойти невозможность и 7.1, позволяя глобально оптимальной стратегии координировать
7.2 Разрешение глобально оптимальной стратегии вывести несколько ставок
7.3 Обсуждения в отношении режима и 7.4 и открытые вопросы, касающиеся использования криптографии
Принцип статического откровения для механизмов платы за транзакцию
8.1 Принцип статического откровения: правила торга, которые выводят отдельную ставку
8.2 Принцип статического откровения: разрешение правил торгов, которые выводят несколько заявок
A. Сравнение понятий с сговором сговора
Ссылки
6.2 Невозможность UIC + MIC + OCA-защита для правдивых механизмов
Структура доказательства в этом разделе аналогична доказательству в разделе 5. Фактически, леммы 6.2, 6.3 и 6.6 до 6.8, а теорема 6.9 являются аналогами лемм с 5.1 до 5,5 и теоремой 5.6, соответственно, за исключением того, что нам необходимо работать над изображениями σ, чтобы применить доступа OCA. Прежде чем погрузиться в доказательство, мы делаем несколько замечаний.
• Ключевой шаг в разделе 5 - доказать, что пользователь с истинным значением V должен иметь нулевую утилиту, и мы докажем это, сделав неподтвержденную ставку произвольно близко к V (см. Лемму 5.4). Чтобы расширить аналогичную идею на защиту от OCA, мы требуем, чтобы σ строго увеличивалось и непрерывно. Фактически, мы показываем, что строго увеличивается следствие UIC и OCA-защиты (Lemma 6.4), и строго увеличивает, что существует точка, в которой σ непрерывная (следствие 6.5).
• Поскольку мы видели осуществимость для не правдивых механизмов в разделе 6.1, мы должны требовать, чтобы правило торгов было правдой, чтобы достичь невозможности. Действительно, доказательства леммы 6.4, 6.7 и 6.8 и теорема 6.9 полагаются на лемму Майерсона, и лемма Майерсона требует, чтобы механизм был правдивым. Обратите внимание, что механизм в разделе 6.1 не удовлетворяет требованиям Леммы Майерсона. Если мы применим принцип откровения, чтобы механизм стал правдивым, чтобы лемма Myerson могла применяться, она разбивает OCA-защиту (см. Замечание 1).
• Обратите внимание, что защита от OCA требует, чтобы σ выводит одну реальную ставку. Фактически, если мы позволим σ выводиться несколько заявок, мы можем иметь (несколько удушенный) механизм, который удовлетворяет UIC, MIC и OCA-защищенные (см. Раздел 7.2). В частности, LEMMA 6.4 требует, чтобы σ выводит только одно реальное число.
• Первоначальное определение OCA-защиты в [ROU21] также требует, чтобы σ был индивидуально рациональным, но это не потребуется для доказательства невозможности.
Есть два возможных случая.
Следствие 6.5.Предположим, что правдивый механизм удовлетворяет UIC и защите от OCA с глобальной оптимальной стратегией σ, и пусть размер блока будет k. Затем существует постоянный C ∗ такой, что для любого реального числа A> C ∗ существует реальное число a ∗ ≥ A, при котором σ непрерывно.
ДоказательствоПолем Хорошо известный факт заключается в том, что любая функция, которая является монотонной, должна иметь только счетное значение в любом интервале [x1, x2], где x2> x1; Кроме того, все такие разрывы должны быть разрывами прыжков. По лемме 6.4 существует постоянный C ∗ такой, что σ является монотонным для всех входов, превышающих C ∗. Таким образом, для любого a> c ∗, в пределах интервала [a, a + 1], σ является монотонным, и должна существовать точка a ∗ такая, что σ непрерывна при ∗.
Лемма 6.6.Предположим, что механизм удовлетворяет микрофону и защите от OCA с глобальной оптимальной стратегией σ. Пусть a, b, b ′ быть произвольными векторами. Рассмотрим два сценария (σ (a), σ (b)) и (σ (a), σ (b ′)). Предположим, что σ (b) и σ (b ′) имеют вероятность подтверждения в каждом из двух сценариев соответственно. Затем оба сценария пользуются одной и той же ожидаемой утилитой майнера, социальным благополучием и общей утилитой пользователя.
ДоказательствоПолем Эквивалентность в ожидаемой полезности майнера следует непосредственно от MIC, и тот факт, что майнер может перейти с B на B 'бесплатно или наоборот, поскольку эти предложения не подтверждены.
Эквивалентность в социальном обеспечении следует из OCA-защиты, и тот факт, что σ максимизирует социальное обеспечение. Предположим, например, социальное благосостояние при (σ (a), σ (b)) строго больше, чем (σ (a), σ (b ′)). Затем, в соответствии с сценарием, в котором истинные значения пользователей (A, B ′), все, следующие за σ, не будут максимизировать социальное благосостояние, поскольку существует OCA, в которой пользователи сталкиваются (σ (a), σ (b)) вместо этого, что строго увеличивает социальное благосостояние.
Эквивалентность в общей пользовательской утилите следует непосредственно из вышеперечисленного, поскольку общая утилита пользователя заключается в разнице между социальным благосостоянием и утилитой шахтеров.
Лемма 6.7.Предположим, что правдивый механизм удовлетворяет UIC, MIC и OCA-защите от глобальной оптимальной стратегии σ, а размер блока равен k. Затем существует постоянный C ∗ такой, что для любого i ∈ [k] сохраняется следующее.
Теорема 6.9.Никакая нетривиальная, возможно, рандомизированная правдивая TFM может одновременно удовлетворить UIC, MIC и защиту от OCA, когда размер блока конечен.
ДоказательствоПолем Мы покажем, что при любом достаточно большем a, при котором σ непрерывна, вероятность подтверждения при одной ставке σ (a) является ненулевой. Если мы сможем показать это, то мы можем показать противоречие с UIC и леммой Myerson. В частности, рассмотрим b> a, которые оба достаточно велики и при котором σ непрерывная (следствие 6.5 гарантирует такой A, b существует). По лемме 6.8 в обоих сценариях пользовательская утилита составляет 0 (при условии, что ставка, σ (a) или σ (b), совпадает с истинным значением пользователя). Леммой 6.4, для достаточно большой A, мы имеем σ (b)> σ (a). Однако по лемме Майерсона, если вероятности подтверждения в одном σ (a) и под одним σ (b) оба ненулевые, не может быть так, что в обоих случаях полезность пользователя составляет 0. В противном случае пользователь с истинным значением σ (b) может недооценить σ (a). Поскольку вероятность подтверждения является ненулевой, а платеж больше всего σ (a), пользователь пользуется положительной полезностью, которая нарушает UIC.
Замечание 2.Обратите внимание, что Чунг и Ши [CS23] показали, что ни один TFM не может одновременно удовлетворять UIC и 1-SCP, когда размер блока конечен. Их невозможность не полагается на микрофон, в то время как MIC необходим для доказательства теоремы 6.9. В частности, рассмотрим аукцион второго цена без сжигания, определяемого следующим образом. Учитывая размер блока K, шахтер включает в себя пополнение до k предложения в блоке. Если количество включенных ставок меньше K, то все включенные предложения подтверждаются и ничего не платят. Если количество включенных предложений равно k, то верхние заявки K-1 подтверждаются, в то время как ставка k-th не подтверждена (произвольно). Все подтвержденные предложения оплачивают ставку K-TH, и все платежи отправляются в шахтер. Этот механизм удовлетворяет МСБ, поскольку подтверждение и оплата удовлетворяют требованиям леммы Майерсона. Механизм также удовлетворяет защите от OCA, когда σ просто правдиво тормозит, поскольку подтвержденные предложения всегда являются теми, кто имеет самые высокие истинные значения, что максимизирует социальное благосостояние. Тем не менее, он не удовлетворяет микрофону, поскольку майнер стимулируется, чтобы ввести поддельную ставку на увеличение ставки K-TH.
Авторы:
(1) Хао Чунг ∗, Университет Карнеги -Меллона (haochung@andrew.cmu.edu);
(2) Тим Гроугарден †, Колумбийский университет и A16Z (Crypto tim.roughgarden@gmail.com);
(3) Элейн Ши ∗, Университет Карнеги -Меллона (runting@cs.cmu.edu).
Эта статья есть
Оригинал