Я боролся с техническими деталями доказательства теории аукциона в этой статье: http://users.eecs.northwestern.edu/~hartline/omd.pdf
В частности, теорема 2.5: необходимые и достаточные условия для правдивого механизма.
Более конкретно, прямое направление доказательства, приведенное на странице 6. Определяя истинное значение как , а общее, возможно, ложное, значение (например, ставку) как , автор продолжает постулировать две дополнительные величины, и .
Затем он устанавливает, что , , что приводит к неравенству, основанному на предыдущей работе статьи.
Он также оговаривает, что , , что приводит к аналогичному, но другому неравенству, основанному на предыдущей работе статьи.
Хорошо, достаточно справедливо. Затем он вычитает одно неравенство из другого и переходит к получению желаемого результата на основе последующей алгебры. Я не понимаю, почему это вычитание оправдано - он, кажется, вычитает два неравенства, основанных на совершенно разных (на самом деле, противоположных) предположениях, и каждый раз, когда я вижу это, меня сильно выбрасывает из цепочки мыслей.
Я почти уверен, что видел этот базовый подход еще (книга Шохама и Лейтона-Брауна? У меня нет его под рукой, чтобы проверить), так что, похоже, это общая идея, но я не могу от нее отказаться. Может ли кто-нибудь помочь мне понять, почему это так, или объяснить, что мне не хватает?
(Я пытался доказать желаемый результат, предполагая три значения - истинное значение и две ставки, и - чтобы получить желаемый результат, но также не удалось. Таким образом, он может быть не только общим, но необходимым для делай это по-автору. Но я до сих пор этого не понимаю.)
Обновление: я знал, что видел нечто подобное в книге Шохама и Лейтона-Брауна . Это не совсем то же самое, но это очень похоже и имеет дело с тем же уравнением и предметом. Это случай 1 теоремы 10.4.3.
Исходя из контекста правдивых механизмов, они сначала принимают правдивые и ложные и получают, что платеж на основе меньше или равен платежу на основе , например, . Затем они принимают противоположное, правдивое и ложное , и получают противоположный результат, что платеж на основе меньше, чем платеж на основе , например, , Хорошо, это имеет смысл.
Затем они считают, что платежи, основанные на и должны быть равными, как если бы они говорили, что и одновременно истинны, даже хотя они являются результатом не просто разных, а противоположных предположений.
источник
Я думаю, что вы хотите следующее предложение.
Предложение. ПозволятьV а также A быть наборы. Позволятьf:Vn→A а также p1,…,pn:Vn→R , Предположим, что для всехi,xi,yi,v−i у нас есть
Доказательство. Вводxi=vi а также yi=v′i у нас есть
Интерпретация механизма проектирования этого предложения состоит в том, что каждый совместимый с стимулом (то есть доказательством стратегии, т.е. правдивым) механизм обладает «слабой монотонностью».
По какой-то причине принято спорить, ссылаясь на истинные предложения и ложь. В этом контексте «истина» и «ложь» являются просто именами переменных, такими как «х» и «у». Можно использовать одно и то же имя для ссылки на разные вещи в отдельных аргументах, потому что между истинной заявкой и ложью нет формальной разницы.
источник