Ceny optymalne Bayesa

Wycena optymalna bayesowska (wycena BO) to rodzaj wyceny algorytmicznej , w której sprzedawca określa ceny sprzedaży na podstawie probabilistycznych założeń dotyczących wycen kupujących. Jest to prosty rodzaj mechanizmu Bayesa-optymalnego , w którym cena jest ustalana z góry bez zbierania rzeczywistych ofert kupujących.

Pojedynczy przedmiot i jeden kupujący

W najprostszym ustawieniu sprzedawca ma do sprzedania jeden przedmiot (bez kosztów) i jest tylko jeden potencjalny nabywca. Najwyższa cena, jaką kupujący jest skłonny zapłacić za przedmiot, nazywana jest wyceną kupującego. Sprzedający chciałby ustalić cenę dokładnie według wyceny kupującego. Niestety sprzedający nie zna wyceny kupującego. W modelu bayesowskim zakłada się, że wycena nabywcy jest zmienną losową losowaną ze znanego rozkładu prawdopodobieństwa.

Załóżmy, że $skumulowana$ funkcja dystrybucji kupującego to $, zdefiniowana jako$ prawdopodobieństwo , wycena sprzedawcy Następnie, jeśli cena jest ustawiona na , oczekiwana wartość przychodu sprzedawcy wynosi: ${\ displaystyle p}$

{\ Displaystyle Rev (p) = p \ cdot (1-F (p))}

ponieważ prawdopodobieństwo, że kupujący będzie chciał kupić przedmiot, wynosi , a jeśli tak się stanie, przychód sprzedawcy wyniesie $1-$ $(p)}$ .

Sprzedawca chciałby znaleźć cenę, która maksymalizuje ${\ Displaystyle Rev (p)}$ . Warunek pierwszego rzędu, który powinna spełniać optymalna cena, to: ${\ displaystyle p ^ {*}}$

{\ Displaystyle p ^ {*} = {1-F (p ^ {*}) \ ponad f (p ^ {*})}}

gdzie ${\ Displaystyle f (p) = F' (p) =} funkcja$ gęstości prawdopodobieństwa .

Na przykład, jeśli rozkład prawdopodobieństwa wyceny kupującego jest jednolity w ${\ Displaystyle [a, a + d]}$ , to ${\ displaystyle F (v) = (va)/d}$ i ${\ Displaystyle f (v) = 1/d}$ (w ${\ Displaystyle [a, a + d] }$ ). Warunek pierwszego rzędu to ${\ Displaystyle p ^ {*} = (a + dp ^ {*})}$ , co implikuje ${\ styl wyświetlania p^{*}=(a+d)/2}$ . Jest to optymalna cena tylko $). [$ $Displaystyle [a, a + d]$ w przedziale tj. kiedy jest w przedziale } W $optymalna$ razie (gdy cena to ${\ Displaystyle p ^ {*} = a$ }

Ta optymalna cena ma alternatywną interpretację: jest rozwiązaniem równania:

{\ Displaystyle w (p ^ {*}) = 0}

gdzie $wyceną$ wirtualną agenta . Tak więc w tym przypadku wycena BO jest równoważna mechanizmowi optymalnemu bayesowskiemu , który jest aukcją z ceną minimalną ${\ displaystyle p ^ {*}}$ .

Pojedynczy przedmiot i wielu kupujących

W tym ustawieniu sprzedawca ma do sprzedania jeden przedmiot (przy zerowym koszcie), a istnieje wielu potencjalnych nabywców, których wyceny są losowym wektorem losowanym z pewnego znanego rozkładu prawdopodobieństwa. Tutaj przychodzą na myśl różne metody ustalania cen:

Ceny symetryczne : sprzedawca ustala jedną cenę za przedmiot. Jeśli jeden lub więcej kupujących zaakceptuje tę cenę, jeden z nich jest wybierany arbitralnie.
ceny dyskryminacyjne : sprzedający ustala inną cenę dla każdego kupującego. Jeśli co najmniej jeden kupujący zaakceptuje tę cenę, zostanie wybrany kupujący, który zaakceptował najwyższą cenę. Dyskryminację cenową można wprowadzić sekwencyjnie, porządkując ceny w porządku malejącym i przekazując przedmiot pierwszemu kupującemu, który zaakceptuje zaoferowaną mu cenę.

W przypadku wielu kupujących wycena BO nie jest już równoważna z aukcją BO : w przypadku ustalania cen sprzedawca musi z góry określić cenę/ceny, podczas gdy w przypadku aukcji sprzedawca może określić cenę na podstawie ofert agentów. Konkurencja między kupującymi może umożliwić licytatorowi podniesienie ceny. W teorii sprzedający może więc uzyskać wyższy przychód na aukcji.

Przykład. Jest dwóch kupujących, których wyceny rozkładają się równomiernie w przedziale ${\ Displaystyle [\ 100 $, \ 200 $]}$ .

Aukcja BO to aukcja Vickreya z ceną minimalną 100 USD (= odwrotna wirtualna wycena równa 0). Oczekiwany przychód to 133 USD.
Dyskryminacyjny schemat cenowy BO polega na zaoferowaniu jednemu agentowi ceny 150 USD, a drugiemu 100 USD. Oczekiwany przychód wynosi 0,5*150 + 0,5*100 = 125 USD.

W praktyce jednak aukcja jest dla kupujących bardziej skomplikowana, ponieważ wymaga wcześniejszego zadeklarowania wyceny. Złożoność procesu aukcyjnego może odstraszyć kupujących i ostatecznie doprowadzić do utraty przychodów. Dlatego interesujące jest porównanie przychodów z optymalnej ceny z optymalnymi przychodami z aukcji, aby zobaczyć, ile przychodów traci sprzedawca przy użyciu prostszego mechanizmu.

Kupujący z niezależnymi i identycznymi wycenami

Blumrosen i Holenstein badają szczególny przypadek, w którym wyceny nabywców są zmiennymi losowymi losowanymi niezależnie od tego samego rozkładu prawdopodobieństwa. Pokazują one, że gdy rozkład wycen nabywców ma ograniczone wsparcie , ceny BO i aukcja BO zbiegają się, dając ten sam przychód. Tempo konwergencji jest asymptotycznie takie samo, gdy ceny dyskryminacyjne , i wolniejsze o czynnik logarytmiczny, gdy trzeba zastosować ceny symetryczne. Na przykład, gdy rozkład jest jednolity w [0,1] i są potencjalni nabywcy: ${\ displaystyle n}$

dochód z aukcji BO ( aukcja Vickreya z ceną minimalną określoną przez rozkład prawdopodobieństwa) wynosi ${\ Displaystyle 1-2/n}$ ;
dochód z dyskryminacyjnych cen BO wynosi ${\ Displaystyle 1-4/n}$ ;
dochód z symetrycznych cen BO wynosi ${\ Displaystyle 1-\ log (n) / n}$ .

W przeciwieństwie do tego, gdy rozkład wycen nabywców ma nieograniczone wsparcie , wycena BO i aukcja BO mogą nie być zbieżne z tym samym przychodem. Np. gdy cdf to ${\ Displaystyle F (x) = 1-1 / x ^ {2}}$ :

dochód z aukcji BO wynosi ${\ displaystyle .88 {\ sqrt {n}}}$ ;
dochód z dyskryminacyjnych cen BO wynosi $.7{\sqrt {n}}$ ;
dochód z symetrycznych cen BO wynosi ${\ displaystyle .64 {\ sqrt {n}}}$ .

Kupujący z niezależnymi i różnymi wycenami

Chawla i Hartline oraz Malec i Sivan badają sytuację, w której wyceny nabywców są zmiennymi losowymi losowanymi niezależnie od różnych rozkładów prawdopodobieństwa. Ponadto istnieją ograniczenia dotyczące zestawu agentów, które mogą być obsługiwane razem (na przykład: istnieje ograniczona liczba jednostek). Rozważają dwa rodzaje dyskryminujących systemów cenowych:

W mechanizmie cenowym nieświadomym zamówienia (OPM) projektant mechanizmu określa cenę dla każdego agenta. Agenci pojawiają się w dowolnej kolejności. Gwarancje mechanizmu dotyczą najgorszego przypadku (kontradyktoryjnego) zamówienia agentów, ustalanego po wylosowaniu wycen agentów.
W mechanizmie wyceny sekwencyjnej (SPM) projektant mechanizmu określa zarówno cenę dla każdego agenta, jak i kolejność agentów. Mechanizm zapętla agentów we wcześniej ustalonej kolejności. Jeśli obecny agent może być obsłużony razem z poprzednio obsługiwanymi agentami (zgodnie z ograniczeniami), wówczas oferowana jest mu jego osobista cena, którą może przyjąć lub zrezygnować.

Ich ogólny schemat obliczania cen jest następujący:

Dla każdego agenta $z$ prawdopodobieństwo, $jakim$ $BO$ ( mechanizm Myersona) służy Można to obliczyć analitycznie lub za pomocą symulacji.
cena agenta $wynosi$ p ${\ Displaystyle p_ {j}: = F_ {j} ^ {- 1} (1-$ $stałą$ , gdzie jest (1, 1/2 lub 1/3, w zależności od ustawienia). Innymi słowy, cena spełnia następujący warunek: ${\ displaystyle p_ {j}}$

{\ displaystyle j}

wynosi co najmniej

{\ displaystyle p_ {j}}

] =

{\ displaystyle C \ razy}

Prob [mechanizm BO służy agentowi

{\ displaystyle j}

] .

Jeśli $.$ krańcowe prawdopodobieństwo, że agent jest obsługiwany przez SPM, jest równe krańcowemu prawdopodobieństwu, że jest obsługiwany przez

Współczynniki aproksymacji możliwe do uzyskania przez OPM zależą od struktury ograniczeń:

jednolite ograniczenia matroidów lub podziałów matroidów - 2 (tj. przychód BO OPM wynosi co najmniej 1/2 przychodu z aukcji BO Myersona).
matryca graficzna - 3
Przecięcie dwóch matroidów podziałowych - 6,75
Przecięcie matroidy graficznej i matroidy działowej - 10,66
Ogólny matroid z rangą matroidów ${\ Displaystyle k}$ - ${\ Displaystyle O (\ log (k))}$

Ponadto pokazują dwie dolne granice:

OPM nie może zagwarantować więcej niż 1/2 dochodu z aukcji BO, nawet w przypadku ustawienia pojedynczego przedmiotu.
OPM $_$ gdy -zamknięte więzy niematroidowe.

Współczynniki przybliżenia, które można uzyskać za pomocą SPM, są oczywiście lepsze:

Matroid jednorodny, matroid podziału - e/(e-1) ≅ 1,58
Matroid ogólny - 2
Przecięcie dwóch matroidów - 3

Dolna granica (potwierdzona przez ) wynosi około 1,25.

Yan wyjaśnia sukces podejścia sekwencyjnego ustalania cen opartego na koncepcji luki korelacji w następujący sposób. Przychód mechanizmu jest powiązany z ustaloną funkcją ${\ displaystyle f}$ . Np. na aukcji k-jednostek funkcją jest ${\ Displaystyle f (S) = \ min (| S |, k)}$

Przychody z aukcji BO wynoszą co najwyżej $\ Displaystyle f (zwycięzcy) \ cdot Price}$ , gdzie „Zwycięzcy” to zbiór k agentów o najwyższych wycenach .
Przychód BO $SPM$ „ cena.

Zarówno „Zwycięzcy”, jak i „Popyt” to zestawy losowe, określone na podstawie wycen agentów. Co więcej $Zwycięzcach ” i$ ostrożnie ustalając cenę, można zapewnić, że każdy agent ma takie samo prawdopodobieństwo znalezienia się w „ $„$ Popycie Jednak w „Zwycięzcach” istnieje silna korelacja między różnymi agentami (jeśli jeden agent wygrywa, istnieje większe prawdopodobieństwo, że inni agenci przegrają), podczas gdy w „Demand” agenci są niezależni. W związku z tym luka korelacji stanowi górną granicę utraty wydajności w przypadku korzystania z aukcji BO SPM zamiast aukcji BO. Daje to następujące współczynniki przybliżenia:

Ogólne matroid - ${\ Displaystyle e / (e-1)}$
aukcje jednostek k (podprzypadek ogólnych matroidów) - ${\ Displaystyle 1 / (1-1 / {\ sqrt {2 \ pi k}})}$
p-niezależne systemy zbiorów (uogólnienie przecięcia $matroidów$ ) - ${\ displaystyle p + 1$ }

Różne przedmioty i jeden kupujący na żądanie

W tym ustawieniu sprzedawca ma na sprzedaż kilka różnych przedmiotów (np. samochody różnych modeli). Jest jeden potencjalny nabywca, który jest zainteresowany pojedynczym przedmiotem (np. jednym samochodem). Kupujący ma inną wycenę dla każdego typu przedmiotu (tzn. ma wektor wyceny). Biorąc pod uwagę podane ceny, kupujący kupuje przedmiot, który daje mu najwyższą użyteczność netto (wycena pomniejszona o cenę).

Wektor wyceny kupującego jest wektorem losowym z wielowymiarowego rozkładu prawdopodobieństwa. Sprzedawca chce obliczyć wektor ceny (cenę za sztukę), który zapewni mu najwyższy oczekiwany przychód.

Chawla, Hartline i Kleinberg badają przypadek, w którym wyceny różnych przedmiotów przez kupującego są niezależnymi zmiennymi losowymi. Pokazują, że:

$typy$ jednostkowej popytu BO, gdy istnieją $,$ jest co najwyżej przychodem z aukcji BO pojedynczego przedmiotu, gdy są potencjalni nabywcy.
Gdy wyceny kupującego dla różnych pozycji są niezależnymi losowaniami z tej samej dystrybucji, cena jednostkowa popytu BO, która wykorzystuje tę samą cenę dla wszystkich pozycji, osiąga co najmniej 1/2,17 przychodu z aukcji pojedynczej pozycji BO.
Gdy wyceny kupującego są niezależnymi losowaniami z różnych dystrybucji, wycena na żądanie na jednostkę BO, która wykorzystuje tę samą cenę wirtualną (na podstawie wirtualnych wycen ), osiąga co najmniej 1/3 przychodów z aukcji pojedynczego przedmiotu BO.

Rozważają również zadanie obliczeniowe polegające na obliczeniu optymalnej ceny. Głównym $wyzwaniem$ jest obliczenie wirtualnej funkcji

W przypadku dyskretnego i regularnego rozkładu wyceny istnieje wielomianowe przybliżenie 3.
Dla ciągłego i regularnego rozkładu wartościowania (dostępnego przez wyrocznię) istnieje przybliżenie w czasie wielomianowym (3+ε) z dużym prawdopodobieństwem oraz szybsze przybliżenie (6+ε) z prawdopodobieństwem 1.

Różne przedmioty i wielu kupujących na żądanie

W tym ustawieniu istnieją różne rodzaje elementów. Każdy kupujący ma różne wyceny dla różnych przedmiotów, a każdy kupujący chce co najwyżej jeden przedmiot. Co więcej, istnieją z góry określone ograniczenia dotyczące zestawu par kupujący-przedmiot, które mogą być przydzielane razem (na przykład: każdy przedmiot może być przydzielony co najwyżej jednemu kupującemu; każdy kupujący może otrzymać co najwyżej jeden przedmiot itp.).

Chawla i Hartline oraz Malec i Sivan badają dwa rodzaje dyskryminujących systemów cenowych:

W mechanizmie sekwencyjnej wyceny (SPM) projektant mechanizmu określa cenę dla każdej pary kupujący-przedmiot oraz kolejność par kupujący-przedmiot. Mechanizm zapętla pary kupujący-przedmiot w ustalonej kolejności. Jeśli obecna para kupujący-przedmiot jest wykonalna, wówczas kupujący otrzymuje przedmiot po z góry ustalonej cenie i może go wziąć lub zrezygnować.
W mechanizmie cenowym nieświadomym zamówienia (OPM) projektant mechanizmu określa cenę dla każdej pary kupujący-przedmiot. Nabywcy pojawiają się w dowolnej kolejności, która może zostać określona w sposób kontradyktoryjny po sporządzeniu wycen przez agentów.

Mechanizm wyceny sekwencyjnej na ogół nie jest mechanizmem zgodnym z prawdą , ponieważ agent może odrzucić dobrą ofertę w nadziei, że później otrzyma lepszą ofertę. Jest to zgodne z prawdą tylko wtedy, gdy dla każdego kupującego pary kupujący-przedmiot są uporządkowane według malejącej użyteczności netto. Wtedy zawsze najlepiej jest, aby kupujący zaakceptował pierwszą ofertę (jeśli jego użyteczność netto jest dodatnia). Szczególnym przypadkiem tej sytuacji jest ustawienie jednego parametru : dla każdego kupującego istnieje tylko jedna para kupujący-przedmiot (np. jeden przedmiot jest na sprzedaż).

Każdemu ustawieniu wieloparametrowemu odpowiada ustawienie jednoparametrowe, w którym każda para kupujący-przedmiot jest uważana za niezależnego agenta. W ustawieniu z jednym parametrem konkurencja jest większa (ponieważ agenci pochodzący od tego samego nabywcy konkurują ze sobą). W związku z tym przychód BO w ustawieniu jednoparametrowym jest górną granicą przychodów BO w ustawieniu wieloparametrowym. Dlatego też, jeśli OPM jest r -przybliżeniem optymalnego mechanizmu dla ustawienia pojedynczego parametru, to jest również r - przybliżeniem odpowiedniego ustawienia wielu parametrów. Powyżej podano współczynniki przybliżenia OPM w różnych ustawieniach.

Więcej informacji można znaleźć w rozdziale 7 „Aproksymacja wielowymiarowa”.

Wielu kupujących i sprzedających na żądanie

Ostatnio system SPM został rozszerzony na podwójną aukcję , w której występują zarówno kupujący, jak i sprzedający. Rozszerzony mechanizm nosi nazwę 2SPM. Jest sparametryzowany przez zlecenie na kupujących, zlecenie na sprzedających oraz macierz cen - cenę dla każdej pary kupujący-sprzedający. Ceny są oferowane kupującym i sprzedającym, którzy mogą przyjąć lub odrzucić ofertę. Współczynnik przybliżenia wynosi od 3 do 16, w zależności od ustawienia.

Zobacz też

Ceny monopolistyczne