Mechanizm ekstrakcji zysków

W projektowaniu mechanizmów i teorii aukcji mechanizm ekstrakcji zysków (zwany także ekstraktorem zysków lub ekstraktorem przychodów ) to prawdziwy mechanizm , którego celem jest zdobycie z góry określonej kwoty zysku, jeśli jest to możliwe.

Pozyskiwanie zysków na aukcji towarów cyfrowych

Rozważmy aukcję towarów cyfrowych , podczas której producent filmowy chce określić cenę, za jaką będzie sprzedawał kopie swojego filmu. Możliwe podejście polega na tym, aby producent zdecydował się na określony przychód R, jaki chce osiągnąć. Następnie ekstraktor R-profit działa w następujący sposób:

• Zapytaj każdego agenta, ile jest skłonny zapłacić za film.
• Dla każdej liczby całkowitej ${\ displaystyle k = 1,2,...}$$będzie$ niech agentów gotowych zapłacić co najmniej ${\ displaystyle R / k}$ . $,$ że słabo rośnie wraz $.$
• Jeśli istnieje taki, że $($${\ displaystyle N_ {k} \ geq k}$ , to znajdź największy taki $displaystyle$ musi być równy ${k}}$${\$ ), sprzedaj film tym $od$ każdego takiego agenta cenę w wysokości ${\ displaystyle R / k}$ .
• Jeśli taki nie $,$ aukcja zostaje anulowana i nie ma zwycięzców.

To jest prawdziwy mechanizm . Dowód : Ponieważ agenty mają jednoparametryczne funkcje użyteczności, prawdziwość jest równoważna monotoniczności . Ekstraktor zysków jest monotoniczny, ponieważ:

• Jeśli zwycięski agent zwiększy swoją ofertę, wówczas $, którzy$ wzrośnie, a agent nadal będzie jednym z oferentów $zaoferują$ najwyższą cenę, więc nadal wygrywa
• Zwycięski agent płaci $progową$ - cenę, poniżej której oferta przestaje być

Szacowanie maksymalnego przychodu

$z$ aukcji opartej na ekstraktorze zysków jest wybór najlepszej wartości . Idealnie chcielibyśmy, $aby był$ maksymalny przychód, jaki można uzyskać z rynku. Nie znamy jednak z góry tego maksymalnego przychodu. Możemy spróbować oszacować go na jeden z następujących sposobów:

1. Losowe pobieranie próbek :

losowo podziel licytantów na dwie grupy w taki sposób, aby każdy licytant miał 1/2 szansy na przejście do każdej grupy. Niech R1 będzie maksymalnym przychodem w grupie 1, a R2 maksymalnym przychodem w grupie 2. Uruchom R1-ekstraktor zysków w grupie 2 i R2-ekstraktor zysków w grupie 1.

Mechanizm ten gwarantuje zysk w wysokości co najmniej 1/4 maksymalnego zysku. Wariant tego mechanizmu dzieli agentów na trzy grupy zamiast na dwie i osiąga co najmniej 1/3,25 maksymalnego zysku.

2. Szacunek konsensusu :

Oblicz maksymalny dochód w całej populacji; zastosować pewien losowy proces zaokrąglania, który gwarantuje, że obliczenia są prawdziwe z dużym prawdopodobieństwem. Niech R będzie szacunkowym przychodem; uruchomić ekstraktor R-profit w całej populacji.

Mechanizm ten gwarantuje zysk w wysokości co najmniej 1/3,39 maksymalnego zysku na aukcji towarów cyfrowych.

Ekstrakcja zysku w aukcji podwójnej

Ideę ekstrakcji zysku można uogólnić na dowolne jednoparametrowe czynniki użyteczności publicznej. W szczególności można go zastosować w aukcji podwójnej , gdzie kilku sprzedawców sprzedaje jedną jednostkę jakiegoś przedmiotu (z różnymi kosztami), a kilku kupujących chce co najwyżej jedną jednostkę tego przedmiotu (z różnymi wycenami). Poniższy mechanizm jest przybliżonym ekstraktorem zysków:

• Uporządkuj kupujących według ceny malejącej, a sprzedających według ceny rosnącej.
• Znajdź największy taki, że $($$) \ geq R$ }
• Kupujący $o$$_$ przedmiot . Tani $_$$.$ przedmiot _

Mechanizm jest prawdziwy – można to udowodnić za pomocą argumentu monotoniczności podobnego do aukcji towarów cyfrowych. Przychód licytatora wynosi ${\ Displaystyle (k-1) \ cdot (b_ {k} -s_ {k}) \ geq {k-1 \over k}R}$ , który zbliża się do wymaganego przychodu, gdy jest wystarczająco duży.

Połączenie tego ekstraktora zysków z estymatorem konsensusu daje prawdziwy mechanizm podwójnej aukcji, który gwarantuje zysk w wysokości co najmniej 1/3,75 maksymalnego zysku.

Historia

Mechanizm pobierania zysków jest szczególnym przypadkiem mechanizmu podziału kosztów . Został on dostosowany z literatury dotyczącej podziału kosztów do warunków aukcji.