Понимание механизма проектирования Доказательство

9

Я боролся с техническими деталями доказательства теории аукциона в этой статье: http://users.eecs.northwestern.edu/~hartline/omd.pdf

В частности, теорема 2.5: необходимые и достаточные условия для правдивого механизма.

Более конкретно, прямое направление доказательства, приведенное на странице 6. Определяя истинное значение как , а общее, возможно, ложное, значение (например, ставку) как , автор продолжает постулировать две дополнительные величины, и .vibiz1z2

Затем он устанавливает, что , , что приводит к неравенству, основанному на предыдущей работе статьи. vi=z1bi=z2

Он также оговаривает, что , , что приводит к аналогичному, но другому неравенству, основанному на предыдущей работе статьи. vi=z2bi=z1

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

Я почти уверен, что видел этот базовый подход еще (книга Шохама и Лейтона-Брауна? У меня нет его под рукой, чтобы проверить), так что, похоже, это общая идея, но я не могу от нее отказаться. Может ли кто-нибудь помочь мне понять, почему это так, или объяснить, что мне не хватает?

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

Обновление: я знал, что видел нечто подобное в книге Шохама и Лейтона-Брауна . Это не совсем то же самое, но это очень похоже и имеет дело с тем же уравнением и предметом. Это случай 1 теоремы 10.4.3.

Исходя из контекста правдивых механизмов, они сначала принимают правдивые и ложные и получают, что платеж на основе меньше или равен платежу на основе , например, . Затем они принимают противоположное, правдивое и ложное , и получают противоположный результат, что платеж на основе меньше, чем платеж на основе , например, , Хорошо, это имеет смысл. viviviviпя(vя)пя(vя')vя'vяvя'vяпя(vя')пя(vя)

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

Новак
источник

Ответы:

11

Ответ заключается в том, что механизм должен быть правдивым для каждого набора возможных типов: механизм не знает, какие из них являются истинными типами раньше времени. Таким образом, для пары типов и механизм должен быть правдивым, если истинным типом агента является : т.е. его полезность должна быть больше, если он предлагает чем если он предлагает . Но механизм также должен быть правдивым, если истинный тип агента ! В конце концов, что касается механизма, это может быть! Таким образом, в этом случае полезность агента должна быть выше, если он предлагает по сравнению с .vяvя'vяvяvя'vя'vя'vя

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

Аарон Рот
источник
Я думаю, что наконец-то начинаю понимать это. На самом деле, знание того, что доказательство является правильным (и почему), еще больше впечатляет меня, насколько строгой и сильной является концепция «правдивости». Спасибо.
Novak
4

Я думаю, что вы хотите следующее предложение.

Предложение. ПозволятьV а также Aбыть наборы. Позволятьf:VnA а также p1,,pn:VnR, Предположим, что для всехi,xi,yi,vi у нас есть

xi(f(xi,vi))pi(xi,vi)xi(f(yi,vi))pi(yi,vi).
Тогда для всех i,vi,vi,vi у нас есть
vi(f(vi,vi))vi(f(vi,vi))vi(f(vi,vi))vi(f(vi,vi)).

Доказательство. Вводxi=vi а также yi=vi у нас есть

vi(f(vi,vi))pi(vi,vi)vi(f(vi,vi))pi(vi,vi).
Ввод xi=vi а также yi=vi у нас есть
vi(f(vi,vi))pi(vi,vi)vi(f(vi,vi))pi(vi,vi).
Результат следует, добавляя эти неравенства и переставляя.

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

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

Колин Маккуиллан
источник
Это предложение в вопросе. (Хотя я думаю, что у вас есть опечатка в третьей строке вашего доказательства - назначения v_i следует поменять местами с первой строки.) Я все еще сомневаюсь, почему допустимо добавлять два неравенства, если они вытекают из разных предположений. Да, нет формальной разницы между истинной и ложной ставкой; они оба числа. Но они (или, если быть точным, они могут быть) разные числа.
Новак
@Novak: Как насчет этого: если я скажу вам, что g(a,b)=1 для всех a,bпримете ли вы это g(x,y)g(y,x)=0 для всех x,y?
Колин МакКиллан
Да. Но позвольте мне немного остановиться на этом в контексте разработки механизма. (И в то же время обновите мой оригинальный пост в Mathjax и добавьте аналогичный случай, который я выкопал из Shoham и Leyton-Brown.)
Novak
Что меня беспокоит здесь, так это ваше предложение. Когда я вижу это утверждение, что утверждение верно, оно уже в контекстеxi является истинным значением, и yiявляется (возможно) ложной ставкой. Я также подвергаю сомнению идею о том, что «истина» и «ложь» являются именами переменных; скорее, правда и ложь, по-видимому, являются реальными качествами сообщаемых ценностей, смысл игры заключается в том, чтобы использовать это различие для стимулирования представления достоверного качества.
Новак
Конкретнее, если вы скажете мне, что g(a,b)=1 за все правдивое a, для всех b (что немного ближе к исходному контексту), тогда я могу принять это g(x,y)g(y,x)=0 если я знаю, что оба x а также yправдивы.
Новак