Mechanizm niezależny od wcześniejszych

Mechanizm niezależny od priorytetu (PIM) to mechanizm , w którym projektant wie, że wyceny agentów pochodzą z pewnego rozkładu prawdopodobieństwa , ale nie zna rozkładu.

Typową aplikacją jest sprzedawca, który chce sprzedać jakiś przedmiot potencjalnemu nabywcy. Sprzedawca chce wycenić towar w sposób, który zmaksymalizuje jego zysk. Optymalne ceny zależą od kwoty, jaką każdy kupujący jest skłonny zapłacić za każdy przedmiot. Sprzedawca nie zna tych wartości, ale zakłada, że są to zmienne losowe o nieznanym rozkładzie prawdopodobieństwa.

PIM zwykle obejmuje proces losowego pobierania próbek . Sprzedawca pobiera próbki z nieznanych rozkładów i na ich podstawie konstruuje aukcję, która przyniesie w przybliżeniu optymalne zyski. Głównym pytaniem badawczym w projektowaniu PIM jest: jaka jest przykładowa złożoność mechanizmu? Tzn. ile czynników musi pobrać próbka, aby uzyskać rozsądne przybliżenie optymalnego dobrostanu?

Aukcje pojedynczych przedmiotów

Wyniki sugerują kilka ograniczeń złożoności próby maksymalizacji przychodów w przypadku aukcji pojedynczych przedmiotów:

Dla $przybliżenia$ optymalnego oczekiwanego przychodu złożoność próbki $wynosi$ . Dzieje się tak nawet wtedy, gdy oferenci nie są iid
Dla $oczekiwanego przychodu, gdy oferenci są iid LUB gdy istnieje nieograniczona podaż pozycji (towarów cyfrowych$ , złożoność próbki wynosi ${\ Displaystyle O (1/\ epsilon ^ {2})}$ gdy rozkłady agentów mają monotoniczny współczynnik hazardu i ${\ Displaystyle O (1/\ epsilon ^ {3})}$ gdy rozkłady agentów są regularne , ale nie mają współczynnika ryzyka monotonicznego.

Sytuacja staje się bardziej skomplikowana, gdy agentów nie ma iid (wartość każdego agenta jest pobierana z innego rozkładu regularnego), a podaż towarów jest ograniczona. Gdy agenci pochodzą z $\$ rozkładów, przykładowa złożoność przybliżenia optymalnego oczekiwanego przychodu na aukcjach pojedynczych przedmiotów wynosi: k $}$

co najwyżej ${\ Displaystyle O ({k ^ {10} \ ponad \ epsilon ^ {7}} \ ln ^ {3} {k \ ponad \ epsilon})}$ - wykorzystując wariant empirycznej aukcji Myersona.
co najmniej ${\ Displaystyle \ Omega ({k \ over {\ sqrt {\ epsilon \ ln k}}})}$ (dla regularnych wycen współczynnika ryzyka monotonicznego) i co najmniej ${\ Displaystyle \ Omega ({k \ over \ epsilon})}$ (dla dowolnych regularnych wycen).

Agenci jednoparametryczni

omawiaj arbitralne aukcje z jednoparametrowymi agentami użyteczności publicznej (nie tylko aukcjami pojedynczych przedmiotów) i arbitralnymi mechanizmami aukcyjnymi (nie tylko konkretnymi aukcjami). Na podstawie znanych wyników dotyczących złożoności próby pokazują, że liczba próbek wymagana do przybliżenia aukcji o maksymalnym dochodzie z danej klasy aukcji wynosi:

{\ Displaystyle O {\ bigg (} ({H \ ponad \ epsilon}) ^ {2} (D \ ln ({H \over \epsilon })+\ln({1 \over \delta })){\bigg )}}

Gdzie:

wyceny agentów są ograniczone w ${\ displaystyle [1, H]$ }
pseudo- VC klasy aukcji wynosi co najwyżej , re $\ displaystyle D}$
wymagany $_$ przybliżenia
wymagane prawdopodobieństwo sukcesu wynosi ${\ displaystyle 1- \ delta}$ .

W szczególności rozważają klasę prostych aukcji zwanych poziomie $:$ $na$ aukcje z cenami minimalnymi (aukcja Vickreya z pojedynczą ceną minimalną to aukcja 1-poziomowa) Udowadniają, że wymiar pseudo-VC tej klasy to ${\ displaystyle O (nt \ ln (nt))}$ , co natychmiast przekłada się na ograniczenie ich błędu uogólnienia i złożoności próbki. Wykazują także granice błędu reprezentacji tej klasy aukcji.

Agenci wieloparametryczni

Devanur i in. badają rynek z różnymi typami towarów i agentami popytu jednostkowego .

Chawla i in. badają PIM pod kątem problemu minimalizacji rozpiętości czasowej .

Hsu i wsp. badają rynek z różnymi typami artykułów. Zaopatrzenie jest stałe. Kupujący mogą kupować pakiety przedmiotów i mieć różne wyceny pakietów. Dowodzą, że jeśli $rozkładu , obliczony zostanie optymalny wektor ceny, a następnie ten wektor$ zostanie zastosowany do świeżej próby nabywców, wówczas ${\ displaystyle n}$ dobrobyt społeczny jest w przybliżeniu optymalny. Współczynnik konkurencyjności wynikający z ich twierdzenia 6.3 wynosi co najmniej z prawdopodobieństwem ${\ displaystyle 1- \ delta}$

{\ Displaystyle 1-O {\ bigg (}{\ sqrt {h ^ {3} n ^ {0,5} m ^ {4 }\ln ^{2}m\ln ^{2}{1 \over \delta } \over {\text{OptimalWelfare}}}}{\bigg )}}

.

Alternatywy

Mechanizmy niezależne od priorytetu (PIM) należy porównać z dwoma innymi typami mechanizmów:

Mechanizmy optymalne Bayesa (BOM) zakładają, że wyceny agentów opierają się na znanym rozkładzie prawdopodobieństwa. Mechanizm jest dostosowany do parametrów tego rozkładu (np. jego mediany lub wartości średniej).
Mechanizmy bez priorytetów (PFM) nie zakładają, że wyceny agentów opierają się na jakimkolwiek rozkładzie prawdopodobieństwa (znanym lub nieznanym). Celem sprzedającego jest zaprojektowanie aukcji, która przyniesie rozsądny zysk nawet w przypadku najgorszych scenariuszy.

Z punktu widzenia projektanta najłatwiejszy jest BOM, potem PIM, potem PFM. Oczekuje się przybliżonych gwarancji BOM i PIM, podczas gdy PFM są w najgorszym przypadku.

Zobacz też