Zrozumienie dowodu projektu mechanizmu

Walczyłem ze szczegółami technicznymi dowodu dotyczącego teorii aukcji w tym artykule: http://users.eecs.northwestern.edu/~hartline/omd.pdf

W szczególności Twierdzenie 2.5: Warunki konieczne i wystarczające dla prawdziwego mechanizmu.

Mówiąc dokładniej, kierunek dowodu do przodu, podany na stronie 6. Definiując prawdziwą wartość jako oraz ogólną, być może fałszywą, wartość (np. Ofertę) jako , autor kontynuuje postulowanie dwóch dodatkowych wielkości, i .$v_i$$b_i$$z_1$$z_2$

Następnie stwierdza, że , , co daje nierówność w oparciu o poprzednią pracę artykułu. $v_i = z_1$$b_i = z_2$

Zastrzega także, że , , co daje podobną, ale różną nierówność w oparciu o poprzednią pracę. $v_i = z_2$$b_i = z_1$

Okej, w porządku. Następnie odejmuje jedną nierówność od drugiej i uzyskuje pożądany wynik na podstawie wynikowej algebry. Nie rozumiem, dlaczego to odejmowanie jest uzasadnione - wydaje się, że odejmuje dwie nierówności oparte na zupełnie innych (w rzeczywistości przeciwnych) założeniach i za każdym razem, gdy to widzę, jestem gwałtownie wyrzucany z toru myślenia.

Jestem prawie pewien, że widziałem już inne podstawowe podejście (książka Shohama i Leytona-Browna? Nie mam go pod ręką, żeby to sprawdzić), więc wydaje się, że jest to powszechny pomysł, ale nie mogę go ominąć. Czy ktoś może mi pomóc zrozumieć, dlaczego jest to ważne, lub wyjaśnić mi, czego mi brakuje?

(Próbowałem udowadniając pożądanego rezultatu zakładając trzy values-- prawdziwą wartość oraz dwie oferty, i - aby uzyskać jego pożądanego rezultatu, ale również nie tak, że nie może być tylko wspólne, ale. Niezbędne do zrób to na swój sposób. Ale nadal tego nie rozumiem.)$v_i$$b_1$$b_2$

Aktualizacja: Wiedziałem, że widziałem coś podobnego w książce Shoham i Leyton-Brown . Nie jest dokładnie taki sam, ale jest bardzo podobny i dotyczy tego samego równania i przedmiotu. Jest to przypadek 1 twierdzenia 10.4.3.

Zaczynając od kontekstu mechanizmów zgodnych z prawdą, najpierw zakładają prawdziwą i fałszywą i wywodzą, że płatność oparta na jest mniejsza lub równa płatności opartej na , np. . Następnie zakładają coś przeciwnego, prawdziwego i fałszywego , i uzyskują przeciwny wynik, że płatność oparta na jest mniejsza niż płatność oparta na , np. . Ok, to ma sens. $v_i$$v_i'$$v_i$$v_i'$$P_i(v_i) \leq P_i(v_i')$$v_i'$$v_i$$v_i'$$v_i$$P_i(v_i') \leq P_i(v_i)$

Utrzymują następnie, że płatności oparte na i muszą być równe, jakby twierdzili, że i są jednocześnie prawdziwe, nawet choć są wynikiem nie tylko różnych, ale przeciwnych założeń.$v_i$$v_i'$$P_i(v_i) \leq P_i(v_i')$$P_i(v_i') \leq P_i(v_i)$

Odpowiedź jest taka, że ​​mechanizm musi być prawdziwy dla każdego zestawu możliwych typów: mechanizm nie wie, które są prawdziwymi typami przed czasem. Tak dla pary typów$v_i$ i $v_i'$, mechanizm musi być prawdziwy, jeśli prawdziwy typ agenta to $v_i$: tzn. jego użyteczność musi być większa, jeśli licytuje $v_i$ niż jeśli licytuje $v_i'$. Ale mechanizm musi być również prawdziwy, jeśli prawdziwy typ agenta to$v_i'$! W końcu jeśli chodzi o mechanizm, to może być! W takim przypadku użyteczność agenta musi być większa, jeśli licytuje$v_i'$ w porównaniu do $v_i$.

Chodzi o to, że prawdomówność nakłada wiele różnych nierówności na ten sam mechanizm jednocześnie: po jednym na każdy typ, jaki może mieć agent i na każde odchylenie, które może rozważyć. Wszystkie z nich trzymają się. Ten dowód wykorzystuje tylko dwie z tych nierówności

Myślę, że chcesz następującą propozycję.

Propozycja. Pozwolić$V$ i $A$być zestawami. Pozwolić$f:V^n\to A$ i $p_1,\dots,p_n:V^n\to\mathbb{R}$. Załóżmy, że dla wszystkich$i,x_i,y_i,v_{−i}$ mamy

$$x_i (f(x_i , v_{−i})) − p_i (x_i , v_{−i}) \geq x_i (f(y_i , v_{−i})) − p_i (y_i , v_{−i}).$$ Potem dla wszystkich $i,v_i,v'_i,v_{-i}$ mamy $$v_i(f(v_i,v_{-i}))-v_i(f(v'_i,v_{-i}))\geq v'_i(f(v_i,v_{-i}))-v'_i(f(v'_i,v_{-i})).$$

Dowód. Putting$x_i=v_i$ i $y_i=v'_i$ mamy

$$v_i (f(v_i , v_{−i})) − p_i (v_i , v_{−i}) \geq v_i (f(v'_i , v_{−i})) − p_i (v'_i , v_{−i}).$$ Putting $x_i=v_i$ i $y_i=v'_i$ mamy $$v'_i (f(v'_i , v_{−i})) − p_i (v'_i , v_{−i}) \geq v'_i (f(v_i , v_{−i})) − p_i (v_i , v_{−i}).$$ Wynik wynika z dodania tych nierówności i zmiany kolejności.

Interpretacja projektu tego twierdzenia polega na tym, że każdy mechanizm zgodny z zachętami (tj. Dowód strategii, tj. Prawdziwy) ma „słabą monotoniczność”.

Z jakiegoś powodu konwencjonalną argumentacją jest odwoływanie się do prawdziwych ofert i kłamstw. W tym kontekście „prawda” i „kłamstwo” to tylko nazwy zmiennych, takie jak „x” i „y”. Można używać tej samej nazwy do różnych rzeczy w oddzielnych argumentach, ponieważ nie ma formalnej różnicy między prawdziwą ofertą a kłamstwem.