Mechanizm optymalny bayesowsko

Mechanizm optymalny Bayesa (BOM) to mechanizm , w którym projektant nie zna wycen agentów, dla których mechanizm jest zaprojektowany, ale wie, że są to zmienne losowe i zna rozkład prawdopodobieństwa tych zmiennych.

Typowym zastosowaniem jest sprzedawca, który chce sprzedać niektóre przedmioty potencjalnym nabywcom. Sprzedający chce wycenić przedmioty w sposób, który zmaksymalizuje ich zysk. Optymalne ceny zależą od kwoty, jaką każdy kupujący jest skłonny zapłacić za każdy przedmiot. Sprzedawca nie zna tych kwot, ale zakłada, że ​​są one wylosowane z pewnego znanego rozkładu prawdopodobieństwa . Wyrażenie „optymalny projekt mechanizmu bayesowskiego” ma następujące znaczenie:

• Bayesowski oznacza, że ​​znamy rozkład prawdopodobieństwa, z którego wyprowadzane są wyceny agentów (w przeciwieństwie do projektowania mechanizmu bez uprzedniego , które nie zakłada żadnego uprzedniego rozkładu prawdopodobieństwa).
• Optymalny oznacza, że ​​chcemy zmaksymalizować oczekiwany przychód licytatora, gdzie oczekiwanie przewyższa losowość w wycenach agentów.
• Mechanizm oznacza, że ​​chcemy zaprojektować zasady, które definiują prawdomówny mechanizm , w którym każdy agent ma motywację do zgłaszania swojej prawdziwej wartości.

Przykład

Do sprzedania jest jedna sztuka. Potencjalnych nabywców jest dwóch. Wycena każdego nabywcy jest losowana iid z rozkładu równomiernego na [0,1].

Aukcja Vickreya jest mechanizmem zgodnym z prawdą, a jej oczekiwany zysk wynosi w tym przypadku 1/3 ( aukcja pierwszej ceny z zapieczętowaną ofertą jest mechanizmem nieprawdziwym i jej oczekiwany zysk jest taki sam ).

Ta aukcja nie jest optymalna. Można uzyskać lepszy zysk ustalając cenę rezerwacji . Aukcja Vickreya z ceną wywoławczą 1/2 osiąga oczekiwany zysk 5/12, który w tym przypadku jest optymalny.

Notacja

Zakładamy, że agenci mają jednoparametrowe funkcje użyteczności, takie jak aukcja pojedynczego przedmiotu. Każdy agent $)$$.$ , reprezentuje „zwycięską wartość” agenta (np. wycenę przedmiotu przez agenta Nie znamy tych wartości, ale wiemy, że każda $jest$ iid z określonego rozkładu prawdopodobieństwa Oznaczamy przez skumulowaną funkcję dystrybucji : ${\ displaystyle F_ {i}}$

${\ Displaystyle F_ {i} (z) = \ Pr [v_ {i}<z]}$

i przez funkcję rozkładu prawdopodobieństwa : fa $\ displaystyle f_ {i}}$

${\ Displaystyle f_ {i} (z) = F_ {i} '(z)}$

Alokacja $a$ wektor $taki$ , że dla każdego $,$ 1 jeśli agent $,$ 0 w przeciwnym Każda alokacja może mieć koszt dla licytatora, ${\ displaystyle c (x)}$ .

Nadwyżkę alokacji definiuje się jako :

${\ Displaystyle S (x) = \ suma _ {i} x_ {i} \ cdot v_ {i} -c (x)}$

Jest to całkowity zysk agentów pomniejszony o koszt licytatora.

Nadwyżka to największy możliwy zysk. $Jeśli$$zwycięski$ agent dokładnie swoją wartość $dokładnie$ zysk jest oznacza to, że licytator bierze całą nadwyżkę dla siebie i pozostawia zerową użyteczność agentom.

$,$ ponieważ jeśli prowadzący aukcję będzie próbował obciążyć każdego zwycięskiego agenta jego wartością kłamać i zgłaszać niższą wartość, aby zapłacić mniej. Mechanizm Myersona rozwiązuje ten problem.

Mechanizm Myersona

Roger Myerson zaprojektował mechanizm optymalny pod względem Bayesa dla jednoparametrowych agentów użyteczności. Kluczową sztuczką w mechanizmie Myersona jest wykorzystanie wirtualnych wycen . Dla każdego agenta zdefiniuj jego wirtualną wycenę jako: ${\ displaystyle i}$

${\ Displaystyle w_ {i} (v_ {i}) = v_ {i} - {\ Frac {1-F_ {i}(v_{i})}{f_{i}(v_{i})}}}$

Należy pamiętać, że wirtualna wycena jest zwykle mniejsza niż rzeczywista wycena. Możliwe jest nawet, że wycena wirtualna będzie ujemna, podczas gdy wycena rzeczywista będzie dodatnia.

Zdefiniuj wirtualną nadwyżkę alokacji jako: ${\ displaystyle x}$

${\ Displaystyle S ^ {*} (x) = \ suma _ {i} x_ {i} \ cdot w_ {i} (v_{i})-c(x)}$

Należy zauważyć, że wirtualna nadwyżka jest zwykle mniejsza niż rzeczywista nadwyżka.

Kluczowe twierdzenie Myersona mówi, że:

Oczekiwany zysk każdego prawdomównego mechanizmu jest równy jego oczekiwanej wirtualnej nadwyżce.

(oczekiwanie przejmuje losowość w wycenach agentów).

Twierdzenie to sugeruje następujący mechanizm:

• Poproś każdego agenta $v$ aby zgłosił swoją wycenę $\ displaystyle v_ {i}}$
• W oparciu o odpowiedź i znane funkcje dystrybucji ${i}}$${\ displaystyle F_ {i}, f_$ . .
• Oblicz alokację x, która maksymalizuje wirtualną nadwyżkę ${\ Displaystyle S ^ {*} (x)}$ .

Aby dopełnić opisu mechanizmu, należy podać cenę, jaką musi zapłacić każdy wygrywający agent. Jednym ze sposobów obliczenia ceny jest użycie mechanizmu VCG do wirtualnych wycen ${\ displaystyle w_ {i}}$ . Mechanizm VCG zwraca zarówno alokację, która maksymalizuje wirtualną nadwyżkę, jak i wektor ceny. Ponieważ wektor ceny odpowiada wartościom wirtualnym, musimy przekonwertować go z powrotem na przestrzeń wartości rzeczywistych. Tak więc ostatnim krokiem mechanizmu jest:

• Weź od każdego zwycięskiego agenta $cenę$ p $\ Displaystyle p_ {i} = w_ {i} ^ {- 1} (p'_ {i}$$,$ gdzie ceną określoną przez mechanizm

Prawdomówność

Mechanizm Myersona jest prawdziwy wtedy, gdy reguła alokacji spełnia własność słabej monotoniczności , tj. funkcja alokacji słabo rośnie w wartościowaniach agentów. Reguła alokacji VCG jest rzeczywiście słabo rosnąca w wycenach, ale używamy jej w przypadku wycen wirtualnych, a nie rzeczywistych. Dlatego mechanizm Myersona jest prawdziwy, jeśli wartości wirtualne słabo rosną w wartościach rzeczywistych. $znaczy,$ jeśli $i$ jest słabo rosnącą funkcją $}}$ .

Jeśli $można$ słabo rosnącą funkcją , $to$ zastosować prasowanie

Mechanizm Myersona można zastosować w różnych ustawieniach. Poniżej przedstawiono dwa przykłady.

Aukcja pojedynczej sztuki

Załóżmy, że chcemy sprzedać pojedynczy przedmiot i wiemy, że wyceny wszystkich agentów pochodzą z tego samego rozkładu prawdopodobieństwa z funkcjami ${\ displaystyle F, f}$ . Następnie wszyscy oferenci mają tę samą funkcję wyceny wirtualnej, ${\ displaystyle w}$ . Załóżmy, że funkcja ta jest słabo rosnąca. W tym przypadku mechanizm VCG sprowadza się do aukcji Vickreya : przydziela przedmiot agentowi o najwyższej wycenie (najwyższej ofercie). Ale mechanizm Myersona wykorzystuje VCG z wirtualnymi wycenami, które mogą być ujemne. Dlatego mechanizm Myersona sprowadza się w tym przypadku do aukcji Vickreya z ceną minimalną . Przydziela przedmiot agentowi z największą wyceną, ale tylko wtedy, gdy jego wirtualna wycena wynosi co najmniej 0 . Oznacza to, że cena rezerwacyjna mechanizmu Myersona wynosi dokładnie:

${\ Displaystyle w ^ {- 1} (0)}$

$więc$$,$ jeśli znamy funkcje rozkładu prawdopodobieństwa , możemy obliczyć funkcję znaleźć optymalną cenę rezerwacji.

Aukcja towarów cyfrowych

Na aukcji towarów cyfrowych mamy nieograniczoną liczbę identycznych przedmiotów. Każdy agent chce co najwyżej jeden przedmiot. Wyceny agentów pozycji pochodzą z tego samego rozkładu prawdopodobieństwa, z funkcjami i $funkcją$ wyceny wirtualnej $displaystyle w$ Mechanizm VCG przydziela przedmiot każdemu agentowi z nieujemną wirtualną wyceną i pobiera minimalną wygraną, która wynosi:

${\ Displaystyle w ^ {- 1} (0)}$

To dokładnie równa się optymalnej cenie sprzedaży – cenie, która maksymalizuje oczekiwaną wartość zysku sprzedawcy, przy danym rozkładzie wycen:

${\ Displaystyle \ arg \ max _ {z} {z \ cdot (1-F (z))}}$

Alternatywy

Projekt mechanizmu Bayesa-optymalnego wymaga znajomości rozkładów, z których wyprowadzane są wyceny agentów. To wymaganie nie zawsze jest wykonalne. Istnieje kilka innych alternatyw:

• Gdy rozkład nie jest znany, można zastosować mechanizm niezależny od wcześniejszego .
• Gdy nie można nawet założyć, że agenty pochodzą z jakiegoś rozkładu prawdopodobieństwa, należy zastosować mechanizm bez priorytetów .