Mechanizm bez priorytetu

Mechanizm bez priorytetów (PFM) to mechanizm , w którym projektant nie ma żadnych informacji na temat wycen agentów, nawet jeśli są to zmienne losowe z nieznanego rozkładu prawdopodobieństwa.

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 kwot i nie może nawet założyć, że kwoty te wynikają z rozkładu prawdopodobieństwa . Celem sprzedającego jest zaprojektowanie aukcji, która przyniesie rozsądny zysk nawet w przypadku najgorszych scenariuszy.

PFM 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 niezależne od priorytetów (PIM) zakładają, że wyceny agentów opierają się na nieznanym rozkładzie prawdopodobieństwa. Próbują z tego rozkładu w celu oszacowania parametrów rozkładu.

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.

Co możemy zrobić bez uprzedzenia? Naiwnym podejściem jest korzystanie ze statystyk : zapytaj potencjalnych nabywców, jakie są ich wyceny i wykorzystaj ich odpowiedzi do obliczenia empirycznej funkcji dystrybucji . Następnie zastosować metody projektowania mechanizmu optymalnego Bayesa do empirycznej funkcji rozkładu.

Problem z tym naiwnym podejściem polega na tym, że kupujący mogą zachowywać się strategicznie. Ponieważ odpowiedzi kupujących wpływają na ceny, które zamierzają zapłacić, mogą być zachęcani do zgłaszania fałszywych wycen w celu obniżenia ceny. Wyzwaniem w PFMD jest zaprojektowanie prawdziwych mechanizmów . W przypadku mechanizmów zgodnych z prawdą agenci nie mogą wpływać na płacone przez siebie ceny, zatem nie mają motywacji do składania nieprawdziwych raportów.

Poniżej opisano kilka podejść do projektowania prawdziwych mechanizmów bez wcześniejszych.

Deterministyczny rozkład empiryczny

Dla każdego agenta niech będzie empiryczną funkcją rozkładu obliczoną na podstawie $}}$ wszystkich agentów z wyjątkiem fa - ja ${$$\$ . $Użyj$ mechanizmu optymalnego Bayesa, $.$ cenę i alokację

Oczywiście oferta agenta $;$ tylko na ceny płacone przez innych agentów, a nie na jego własną cenę dlatego mechanizm jest prawdziwy.

Ten „empiryczny mechanizm Myersona ” działa w niektórych przypadkach, ale nie w innych.

Oto przypadek, w którym sprawdza się to całkiem nieźle. Załóżmy, że bierzemy udział w aukcji towarów cyfrowych . Prosimy Kupujących o wycenę towaru i otrzymujemy następujące odpowiedzi:

1. 51 kupujących złożyło ofertę „1 USD”
2. 50 kupujących złożyło ofertę „3 USD”.

Dla każdego z kupujących w grupie 1 rozkład empiryczny wynosi 50 kupujących za 1 dolara i 50 kupujących za 3 dolary, więc funkcja dystrybucji empirycznej to „0,5 szansy na 1 dolara i 0,5 szansy na 3 dolary”. Dla każdego z kupujących w grupie 2 rozkład empiryczny wynosi 51 kupujących za 1 dolara i 49 kupujących za 3 dolary, więc funkcja dystrybucji empirycznej wynosi „0,51 szansy na 1 dolara i 0,49 szansy na 3 dolary”. Optymalna cena Bayesa w obu przypadkach wynosi 3 dolary. Zatem w tym przypadku cena podana wszystkim kupującym wyniesie 3 dolary. Tylko 50 kupujących z grupy 2 zgadza się na tę cenę, więc nasz zysk wynosi 150 USD. Jest to zysk optymalny (przykładowo cena 1 dolara dałaby nam zysk jedynie 101 dolarów).

Ogólnie rzecz biorąc, mechanizm empiryczny-Myersona działa, jeśli spełnione są następujące warunki:

• Nie ma żadnych ograniczeń wykonalności (żadnych problemów związanych z niezgodnością przydziałów dla różnych agentów), jak w przypadku aukcji towarów cyfrowych ;
• Wyceny wszystkich agentów są sporządzane niezależnie od tego samego nieznanego rozkładu;
• Liczba agentów jest duża.

Wówczas zysk empirycznego mechanizmu Myersona zbliża się do maksimum.

Jeśli niektóre z tych warunków nie są spełnione, wówczas empiryczny mechanizm Myersona może mieć słabą wydajność. Oto przykład. Przypuszczam, że:

1. 10 kupujących złożyło ofertę „10 USD”;
2. 91 kupujących złożyło ofertę „1 USD”.

Dla każdego kupującego w grupie 1 empiryczna funkcja dystrybucji wynosi „0,09 szansy na 10 dolarów i 0,91 szansy na 1 dolara”, więc optymalna cena Bayesa wynosi 1 dolara. Dla każdego kupującego w grupie 2 empiryczna funkcja dystrybucji wynosi „0,1 szansy na 10 dolarów i 0,9 szansy na 1 dolara”, więc optymalna cena Bayesa wynosi 10 dolarów. Kupujący z grupy 1 płacą 1 dolara, a kupujący z grupy 2 nie chcą płacić 10 dolarów, więc ostatecznie mamy zysk w wysokości 10 dolarów. Natomiast cena 1 dolara dla każdego dałaby nam zysk w wysokości 101 dolarów. Nasz zysk jest mniejszy niż 10% wartości optymalnej. Ten przykład można uczynić dowolnie złym.

Co więcej, ten przykład można uogólnić, aby udowodnić, że:

Nie istnieją stałe $b$ we wszystkich zysk co najmniej $OPT / bh \ cdot c$ przypadki, w których wyceny agentów są w ${\ displaystyle [1, h]}$ .

Losowe pobieranie próbek

Główny artykuł: Mechanizm losowego próbkowania

W typowym mechanizmie losowego próbkowania potencjalni nabywcy są losowo dzieleni na dwa podrynki. Każdy kupujący trafia do każdego subrynku z prawdopodobieństwem 1/2, niezależnie od pozostałych. Na każdym podrynku obliczamy empiryczną funkcję dystrybucji i wykorzystujemy ją do obliczenia cen dla drugiego podrynku. Oferta agenta wpływa tylko na ceny na innym rynku, a nie na jego własnym, więc mechanizm jest prawdziwy. W wielu scenariuszach zapewnia dobre przybliżenie optymalnego zysku, nawet w najgorszych scenariuszach; zobacz Mechanizm losowego próbkowania , aby uzyskać odniesienia.

Szacunki konsensusu

Główny artykuł: szacunki konsensusu

Oszacowanie konsensusu to funkcja, na którą z dużym prawdopodobieństwem nie może mieć wpływu pojedynczy czynnik. Na przykład, jeśli obliczymy maksymalny zysk, jaki możemy uzyskać od danej grupy kupujących, wówczas każdy kupujący może wpłynąć na zysk, zgłaszając nieprawdziwe informacje. Jeśli jednak zaokrąglimy maksymalny zysk do najbliższego 1000 dolarów poniżej, a stawki będą ograniczone np. do 10 dolarów, to z dużym prawdopodobieństwem pojedyncza oferta nie będzie miała żadnego wpływu na wynik. Gwarantuje to, że mechanizm jest zgodny z prawdą. Należy starannie wybrać funkcję konsensusu, aby zapewnić dobre przybliżenie zysku; zobacz szacunki konsensusu dla referencji.