Mechanizm losowego próbkowania

Mechanizm losowego próbkowania (RSM) to prawdziwy mechanizm , który wykorzystuje próbkowanie w celu osiągnięcia w przybliżeniu optymalnego wzmocnienia w mechanizmach bez uprzednich i niezależnych od uprzednich .

Załóżmy, że chcemy sprzedać niektóre przedmioty na aukcji i osiągnąć maksymalny zysk. Podstawową trudnością jest to, że nie wiemy, ile każdy kupujący jest skłonny zapłacić za przedmiot. Jeśli wiemy przynajmniej, że wyceny kupujących są zmiennymi losowymi o pewnym znanym rozkładzie prawdopodobieństwa , możemy zastosować mechanizm optymalizacji bayesowskiej . Ale często nie znamy rozkładu. W takim przypadku alternatywne rozwiązanie zapewniają mechanizmy losowego próbkowania .

RSM na dużych rynkach

Schemat zmniejszania o połowę rynku

Gdy rynek jest duży, można zastosować następujący ogólny schemat:

Kupujący proszeni są o ujawnienie swoich wycen.
Kupujący są podzieleni na dwa rynki podrzędne, $”)$ $)$ i („prawy przy użyciu prostego losowego próbkowania : każdy kupujący idzie na jedną ze stron, rzucając uczciwą monetą .
$Na$ $jest$ rynku funkcja dystrybucji .
Mechanizm optymalnego bayesowskiego $\ displaystyle M_ {L}$ $}$ Myersona) jest stosowany na rynku podrzędnym $oraz$ dystrybucją na rynku z ${\ Displaystyle F_ {R}}$ .

Schemat ten nosi nazwę „Random-Sampling Empirical Myerson” (RSEM).

Deklaracja każdego kupującego nie ma wpływu na cenę, którą musi zapłacić; cena jest ustalana przez kupujących na drugim rynku cząstkowym. dominującą strategią kupujących jest ujawnianie swojej prawdziwej wyceny. Innymi słowy, jest to prawdziwy mechanizm .

Intuicyjnie, zgodnie z prawem wielkich liczb , jeśli rynek jest wystarczająco duży, to rozkłady empiryczne są wystarczająco podobne do rozkładów rzeczywistych, więc spodziewamy się, że RSEM osiągnie prawie optymalny zysk. Jednak nie we wszystkich przypadkach musi to być prawdą. Zostało to udowodnione w niektórych szczególnych przypadkach.

Najprostszym przypadkiem jest aukcja towarów cyfrowych . Tam krok 4 jest prosty i polega jedynie na obliczeniu optymalnej ceny na każdym subrynku. Optymalna cena w $\ displaystyle M_ {R}}$ do ${$ i odwrotnie. Dlatego mechanizm nazywa się „Optymalna cena losowego próbkowania” (RSOP). Ten przypadek jest prosty, ponieważ zawsze oblicza możliwe alokacje. Oznacza to, że zawsze istnieje możliwość przeniesienia ceny obliczonej z jednej strony na drugą. Niekoniecznie tak jest w przypadku towarów fizycznych.

Nawet w przypadku aukcji towarów cyfrowych RSOP niekoniecznie prowadzi do optymalnego zysku. Zbiega się tylko przy $:$ ograniczonych wycen dla każdego kupującego wycena przedmiotu mieści się w $przedziale od$ , gdzie jest pewną stałą. Szybkość konwergencji RSOP do optymalności zależy od ${\ displaystyle h}$ . Stopień konwergencji zależy również od liczby możliwych „ofert” rozpatrywanych przez mechanizm.

Aby zrozumieć, czym jest „oferta”, rozważmy aukcję towarów cyfrowych, w której wyceny kupujących w dolarach są ograniczone do ${\ displaystyle [1, h]}$ . Jeśli mechanizm $wykorzystuje tylko ceny$ pełnych dolarach, to są tylko możliwe oferty.

Ogólnie rzecz biorąc, problem optymalizacji może dotyczyć znacznie więcej niż tylko jednej ceny. Na przykład możemy chcieć sprzedać kilka różnych towarów cyfrowych, z których każdy może mieć inną cenę. Więc zamiast "ceny" mówimy o "ofercie". $,$ że istnieje globalny zbiór ofert. $kwota$ $g$ ) \ $($ , którą agent $sol {\ displaystyle i}$ płaci, gdy przedstawiono mu ofertę ${\ displaystyle g}$ . $zbiorem$ przykładzie towarów cyfrowych jest możliwych cen. Dla każdej możliwej ceny istnieje funkcja $g_ {p}}$ $displaystyle$ taka, że ${\ displaystyle g_ {p} (i)}$ wynosi albo 0 (jeśli ${\ displaystyle v_ {i}<p}$ } lub ${\ displaystyle p}$ (jeśli ${\ displaystyle v_ {i} \ geq p}$ ).

Dla każdego zestawu agentów zysk mechanizmu z przedstawienia oferty agentom w $displaystyle S}$ $\ displaystyle S}$ : $S {$

{\ Displaystyle g (S): = \ suma _ {i \ w S} g (i)}

a optymalny zysk mechanizmu to:

{\ Displaystyle OPT_ {G} (S): = \ max _ {g \ w G} g (S)}

$M_ {s}}$ oblicza dla każdego podrynku optymalną ofertę obliczoną następujący sposób: $displaystyle$

{\ Displaystyle g_ {s}: = \ arg \ max _ {g \ in G} g (M_ {s})}

Oferta jest stosowana do kupujących w $,$ ${\ displaystyle M_ {R}}$ tj.: każdy kupujący, powiedział, $\ displaystyle i \ in M_ {R}}$ sol $g_ {L} (i)> 0}$ ${\ Displaystyle g_ {L} (i)}$ otrzymuje oferowaną alokację i płaci ; każdy kupujący w ${\ displaystyle M_ {R}}$ kto powiedział, że nie otrzymują i nic nie płacą ${\ displaystyle g_ {L} (i) = 0}$ Oferta $sposób$ $w$ kupujących podobny

Schemat wyroczni zysków

Wyrocznia zysków to kolejny schemat RSM, który można zastosować na dużych rynkach. Jest to przydatne, gdy nie mamy bezpośredniego dostępu do wycen agentów (np. ze względu na prywatność). Wszystko, co możemy zrobić, to przeprowadzić aukcję i obserwować jej oczekiwany zysk. W aukcji pojedynczego przedmiotu, w której są $displaystyle K$ $}$ a dla każdego licytującego są co najwyżej możliwe wartości (wybrane losowo z nieznanym prawdopodobieństwem), aukcja o maksymalnym dochodzie może być K {\ nauczył się za pomocą:

{\ Displaystyle O (n ^ {2} K ^ {2})}

wezwania do wyroczni-zysk.

RSM na małych rynkach

RSM zbadano również w najgorszym scenariuszu, w którym rynek jest mały. W takich przypadkach chcemy uzyskać bezwzględny, multiplikatywny współczynnik przybliżenia, który nie zależy od wielkości rynku.

Zmniejszenie rynku o połowę, towary cyfrowe

Pierwsze badanie w tym ustawieniu dotyczyło aukcji towarów cyfrowych z narzędziem jednoparametrowym .

Dla mechanizmu Random-Sampling Optimal-Price obliczono kilka coraz lepszych przybliżeń:

Przez, zysk mechanizmu wynosi co najmniej 1/7600 optymalnego.
Przez mechanizm zysk wynosi co najmniej 1/15 optymalnego.
Według mechanizmu zysk wynosi co najmniej 1/4,68 optymalnego, aw większości przypadków 1/4 optymalnego, czyli wąskiego.

Pojedyncza próbka, towary fizyczne

Gdy wyceny agentów spełniają pewien techniczny warunek prawidłowości (zwany stopą hazardu monotonicznego ), możliwe jest osiągnięcie stałego współczynnika przybliżenia do aukcji maksymalnego zysku za pomocą następującego mechanizmu:

Wypróbuj pojedynczego losowego agenta i zapytaj o jego wartość (zakłada się, że agenci mają użyteczność jednego parametru ).
W przypadku pozostałych agentów przeprowadź aukcję VCG z ceną minimalną określoną przez agenta objętego próbą.

Zysk z tego mechanizmu wynosi co najmniej , gdzie ${\ displaystyle {n-1 \ ponad 4 n}}$ $liczba$ agentów. Jest to 1/8, gdy jest dwóch agentów i rośnie do 1/4, gdy liczba agentów rośnie. Ten schemat można uogólnić, aby poradzić sobie z ograniczeniami dotyczącymi podzbiorów agentów, które mogą wygrywać jednocześnie (np. istnieje tylko skończona liczba elementów). Może również obsługiwać agentów o różnych atrybutach (np. młodzi kontra starzy oferenci).

Przykładowa złożoność

Złożoność próby mechanizmu losowego próbkowania to liczba agentów, których musi pobrać próbka, aby osiągnąć rozsądne przybliżenie optymalnego dobrostanu.

Wyniki implikują kilka ograniczeń przykładowej złożoności maksymalizacji przychodów z aukcji pojedynczych przedmiotów:

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

Sytuacja komplikuje się, gdy agenci nie są iid (wartość każdego agenta jest pobierana z innego regularnego rozkładu), a podaż towarów jest ograniczona. Gdy agenci pochodzą z $}$ dystrybucji, próbka złożoności przybliżenia optymalnego oczekiwanego dochodu w aukcjach pojedynczego przedmiotu wynosi: k ${$

najwyżej ${\ Displaystyle O ({k ^ {10} \ ponad \ epsilon ^ {7}} \ ln ^ {3} {k \ ponad \ epsilon})}$ - używając wariantu empirycznej aukcji Myersona.
co najmniej ${\ Displaystyle \ Omega ({k \ ponad {\ sqrt {\ epsilon \ ln k}}})}$ (dla regularnych wycen poziomu zagrożenia monotonicznego) i co najmniej ${\ Displaystyle \ Omega ({k \ ponad \ epsilon})}$ (dla dowolnych regularnych wycen).

omawiać arbitralne aukcje z jednoparametrowymi agentami użyteczności publicznej (nie tylko aukcje pojedynczych przedmiotów) oraz arbitralne mechanizmy aukcyjne (nie tylko aukcje określone). Opierając się na znanych wynikach dotyczących złożoności próby , pokazują, że liczba próbek wymagana do aproksymacji aukcji o maksymalnym dochodzie z danej klasy aukcji wynosi:

{\ Displaystyle O {\ bigg (} ({H \ nad \ 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 jest co najwyżej ${\ displaystyle D$ }
wymagany współczynnik przybliżenia to ${\ Displaystyle 1-\ epsilon}$ ,
wymagane prawdopodobieństwo sukcesu wynosi ${\ Displaystyle 1-\ delta}$ .

W szczególności biorą pod uwagę klasę prostych aukcji zwanych poziomie $:$ $na$ aukcje z cenami minimalnymi (aukcja Vickreya z jedną ceną minimalną to aukcja 1-poziomowa) Dowodzą, ż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. Dowodzą również granic błędu reprezentacji tej klasy aukcji.

Zazdrość

Wadą mechanizmu losowego próbkowania jest to, że nie jest on wolny od zazdrości . $ceny$ na dwóch rynkach podrzędnych $i$ i różne, to kupującym na każdym rynku podrzędnym oferuje się inną Innymi słowy, mamy do czynienia z dyskryminacją cenową . Jest to nieuniknione w następującym sensie: nie istnieje jednolita strategiczna , która przybliżałaby optymalny zysk.

Zobacz też

Badania rynku
cennik
Szacunek konsensusu - alternatywne podejście do projektowania mechanizmu bez uprzedniego .