Mechanismus Vickrey-Clark-Groves

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 13. července 2019; kontroly vyžadují 4 úpravy .

V aukční teorii je aukční mechanismus Vickrey-Clark-Groves (zobecněná aukce Vickrey ) typem vícepoložkových uzavřených aukcí. Účastníci zadávají nabídky, které odpovídají jejich odhadům hodnoty zboží, aniž by znali nabídky ostatních účastníků. Aukce distribuuje zboží „společensky optimálním“ způsobem (ve vztahu k účastníkům aukce má zaručeno, že jej obdrží účastník s nejvyšším oceněním zboží): každý účastník aukce zaplatí cenu rovnající se dopadu jeho účast na výsledku aukce (na základě toho, jak jeho účast ovlivní všechny ostatní účastníky) [1] . Vytváří také pobídky pro dražitele, aby nabízeli své vlastní ocenění položky, což zajišťuje, že optimální strategií pro dražitele je pravdivě sdělit své ocenění hodnoty položky prostřednictvím své nabídky (přihazování své skutečné hodnoty položky). Toto je zobecnění aukce Vickrey pro vícepoložkové aukce. Aukce je pojmenována po Williamu Vickrey [2] , Edward Clark [3] a Theodore Groves [4] , kteří úspěšně zobecnili myšlenku aukce Vickrey pro případ aukce jedné položky na případ více položek. aukce ve svých papírech.

Formální popis

Definice

Pro jakýkoli soubor zboží prodávaného v aukci a soubor účastníků budiž „veřejný prospěch“ (množina účastníků vystupuje jako „společnost“) z výsledku aukce VCG pro daný soubor nabídek. Pro účastníka a zboží bude účastnická sazba . $M=\{t_{1},\ldots ,t_{m}\}$ $N=\{b_{1},\ldots ,b_{n}\}$ $V_{N}^{M}$ $bi}$ $t_{j}$ $v_{{i}}(t_{{j}})$

Jmenování vítěze

Účastník , jehož nabídka za produkt , a to , je maximální mezi účastníky, vyhrává aukci, ale ze své výhry zaplatí částku rovnající se výši neobdrženého prospěchu zbývajících účastníků (o samotné výhře rozhoduje zbytek účastníků). $bi}$ $t_{j}$ $v_{{i}}(t_{{j}})$ $V_{{N\setminus \{b_{i}\}}}^{{M}}-V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j }\}}}$

Vysvětlení (intuice)

Množina soutěžících účastníků o je definována takto: . Když je produkt dostupný pro konkurenty, mohou dosáhnout bohatství . Vyhrané zboží účastníkem snižuje množinu dostupného zboží na , ale blahobyt je stále dosažitelný . Rozdíl mezi těmito dvěma úrovněmi pohody bude ušlý zisk ostatních hráčů za předpokladu, že hráč obdrží zboží (soutěžící mu umožnili vyhrát). Tato hodnota závisí na žádostech soutěžících účastníků a není účastníkovi známa . $bi}$ $N\setminus \{b_{i}\}$ $t_{j}$ $V_{{N\setminus \{b_{i}\}}}^{{M}}$ $bi}$ $M\setminus \{t_{j}\}$ $V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}$ $bi}$ $t_{j}$ $bi}$

Hodnota užitné funkce pro vítěze

Vítězný dražitel, jehož nabídka je jeho skutečnou hodnotou položky , získá maximální zisk. $A$ $t_{j}$ $v_{{i}}(t_{{j}})=A,$ $A-\left(V_{{N\setminus \{b_{i}\}}}^{{M}}-V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\vpravo).$

Příklady

Příklad č. 1

Příklad Apple v sekci Příklady aukce Vickrey .

Příklad č. 2

Předpokládejme, že existují dva hráči a , a dvě zboží a , a každý účastník může obdržet pouze jedno zboží. Nechť je to hodnota produktu pro hráče . Položme , , , a . Je vidět, že jak hráči, tak budou preferovat příjem zboží ; „společensky optimální“ návrh aukce však přiřadí zboží hráči (takže jeho přijatá hodnota je ) a zboží hráči (takže jeho přijatá hodnota je ). Celková získaná hodnota se tedy bude rovnat , což je optimální. $b_{1}$ $b_{2}$ $t_{1}$ $t_{2}$ $v_{{i,j}}$ $t_{j}$ $bi}$ $v_{{1,1}}=10$ $v_{{1,2}}=5$ $v_{{2,1}}=5$ $v_{{2,2}}=3$ $b_{1}$ $b_{2}$ $t_{1}$ $t_{1}$ $b_{1}$ $deset$ $t_{2}$ $b_{2}$ $3$ $13$

Pokud se hráč aukce nezúčastní, účastník stále dostává zboží , to znamená, že se pro něj nic nemění. Aktuální přijatá hodnota bude rovna , proto bude hráči účtován poplatek . $b_{2}$ $b_{1}$ $t_{1}$ $deset$ $b_{2}$ $10-10=0$

Pokud se hráč aukce nezúčastní, předmět připadne hráči a má hodnotu . Aktuální přijatá hodnota bude rovna , proto bude hráči účtován poplatek . $b_{1}$ $t_{1}$ $b_{2}$ $5$ $3$ $b_{1}$ $5-3=2$

Příklad č. 3

Zvažte aukci s více položkami. Ať aukce zahrnuje dražitele, domy a hodnotu domu pro dražitele . Možným výsledkem aukce v tomto případě může být párování v bipartitním grafu , s jehož pomocí lze sestavit dvojice domů s účastníky aukce. Pokud známe hodnoty, pak se maximalizace sociálního blahobytu omezuje na nalezení maximálního váhového párování v odpovídajícím bipartitním grafu [5] . Pokud hodnoty neznáme, můžeme se místo toho zeptat na sazby, které je člen ochoten za dům zaplatit . Označte , zda účastník získá dům ve shodě . Nyní vypočítáme shodu maximální váhy v bipartitním grafu v případě přiřazení v sazbách jako váhy a vypočítáme $n$ $n$ ${\tilde v}_{{ij}}$ $j$ $i$ ${\tilde b}_{{ij}}$ $i$ $j$ $b_{i}(a)={\tilde b}_{{ik))$ $i$ $k$ $A$ $a^{*}$

p_{i}=\left[\max _{{a\v A}}\součet _{{j\neq i}}b_{j}(a)\vpravo]-\součet _{{j\neq i }}b_{j}(a^{*})

První člen je další shoda maximální váhy v bipartitním grafu a druhý člen lze snadno získat z . $a^{*}$

Optimalita strategie pravdivého zveřejnění vlastního hodnocení hodnoty produktu

To, co je napsáno v tomto odstavci, dokazuje, že nastavení nabídky rovnající se vašemu skutečnému odhadu hodnoty je pro vás optimální [6] . Pro každého účastníka nechť je jeho skutečná hodnota statku , řekněme (bez ztráty obecnosti), jakou získá nabízením své skutečné hodnoty statku. Čistý zisk dosažený účastníkem pak bude . Jelikož nezávisí na , je dosaženo maximalizace čistého zisku podle aukčního mechanismu při maximalizaci celkového příjmu za nastavenou nabídku . Jinými slovy, aukční mechanismus přiděluje platby tak, že při dosažení maximálního příjmu hráče je dosaženo maximální hodnoty zisku. A úkolem účastníka není manipulovat s kurzy, ale stanovit sazbu, která se bude rovnat jeho skutečné hodnotě zboží. To umožňuje účastníkům vyloučit platební funkci z úkolu optimalizovat své zisky. $bi}$ $v_{i}$ $t_{i}$ $bi}$ $t_{i}$ $U_{i}$ $bi}$ $U_{i}=v_{i}-\left(V_{{N\setminus \{b_{i}\}}}^{{M}}-V_{{N\setminus \{b_{i}\} }}^{{M\setminus \{t_{i}\}}}\right)=\součet _{{i}}v_{i}-\součet _{{j\neq i}}v_{j} +V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}}-V_{{N\setminus \{b_{i}\}}} ^{M}=\součet _{i}v_{i}-V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}}+V_ {{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}}-V_{{N\setminus \{b_{i}\}}}^{ M}$ $=\sum _{i}v_{i}-V_{{N\setminus \{b_{i}\}}}^{M}$ $V_{{N\setminus \{b_{i}\}}}^{M}$ $v_{i}$ $\sum _{i}v_{i}$ $v_{i}$

Zapišme si rozdíl mezi čistým ziskem účastníka , který přihazuje rovnající se jeho skutečné hodnotě přijatého zboží , a čistým ziskem účastníka s falešnou nabídkovou strategií za zboží a přijatým zbožím se skutečnou hodnotou . toto je maximální celková návratnost generovaná strategií falešných nabídek. Ale přiřazení zboží účastníkovi se liší od přiřazení zboží účastníkovi, které přináší maximální celkový příjem. Proto a tak dále. $U_{i}-U_{j}=\left[v_{i}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}} \right]-\left[v_{j}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\right]$ $U_{i}$ $bi}$ $v_{i}$ $t_{i}$ $U_{j}$ $bi}$ $v'_{i}$ $t_{i}$ $t_{j}$ $v_{j}$ $\left[v_{j}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\right]$ $t_{j}$ $bi}$ $t_{i}$ $bi}$ $\left[v_{i}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}}\right]-\left[v_{j }+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\right]\geq 0$ $U_{i}\geq U_{j}$

Použití v online reklamě

Aukce VCG se používá k prodeji reklamních ploch na internetových stránkách. Tento aukční model využívají zejména Facebook [7] , Google (ve své partnerské síti) [8] a Yandex (na stránce s výsledky vyhledávání) [9] . Dalším oblíbeným modelem prodeje reklamního prostoru je všeobecná aukce druhé ceny.

Pusťte místa do reklamního bloku . O tato místa soutěží několik reklam. V modelu platby za proklik jsou důležitými parametry konkurenčních reklam jejich nabídky a pravděpodobnosti kliknutí. $K$ ${bi}}$ ${p_{i}}$

Hodnota kandidáta v tomto modelu je dána funkcí . Zobrazí se reklamy s nejvyšší hodnotou . Pro -tého hráče máme . $V(b,p)=b\cdot p$ $K$ $i$ $V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}$

Jsou možné i složitější verze hodnotové funkce , důležitým požadavkem na tuto funkci je monotónnost s ohledem na sazbu . $PROTI$ $b$

Pravidla aukce VCG pro danou hodnotovou funkci a místa v reklamním bloku jsou následující: musíte vybrat reklamy s maximem tím a od -th hráče, který vezme tolik peněz za kliknutí , že hodnota je menší než hodnotu jeho původní nabídky přesně o částku, o kterou by klesla celková hodnota zobrazených hráčů, pokud by se hráč aukce nezúčastnil. $V(b,p)$ $K$ $K$ $PROTI$ $i$ $c_{i}$ $V(c_{i},p_{i})$ $V(b_{i},p_{i})$ $i$

Zvažte případ, kdy jsou všechny pozice stejně dobré, to znamená, že pravděpodobnost kliknutí na reklamu nezávisí na pozici.

V případě tří míst ( ) pak pro výpočet ceny za proklik na první reklamu musíte vyřešit rovnici: $K=3$ $c_{1}$ $V(c_{1},p_{1})+V(b_{2},p_{2})+V(b_{3},p_{3})=V(b_{2},p_ {2})+V(b_{3},p_{3})+V(b_{4},p_{4})$

Dva členy v této rovnici se ruší a dávají: $V(c_{1},p_{1})=V(b_{4},p_{4}).$

To znamená, že pro výpočet CPC první reklamy je třeba snížit její nabídku tak, aby její hodnota klesla na hodnotu prvního nezobrazeného hráče (v tomto případě 4. reklamy).

$c_{1}=b_{4}\cdot p_{4}/p_{1}.$

Podobné tvrzení platí pro 2. a 3. hráče:

$c_{2}=b_{4}\cdot p_{4}/p_{2}.$

$c_{3}=b_{4}\cdot p_{4}/p_{3}.$

Pokud jsou tedy pravděpodobnosti kliknutí reklam v aukci stejné ( skóre CTR jsou stejné) a jejich nabídky jsou 10, 7, 5, 2, první tři přijdou na zobrazení a všechny zaplatí 2 - cena 4. inzerátu.

V případě, že se aukce VCG shoduje s aukcí druhé ceny. $K=1$

V jedné aukci lze smísit jak hráče, kteří jsou ochotni zaplatit rubly za kliknutí (s hodnotou ), tak hráče, kteří jsou ochotni zaplatit rubly za zobrazení, pak se jejich hodnota rovná . Algoritmus pro výpočet amnestie vystavené nabídky za zobrazení je získán z podobných vzorců. $b$ $V=b\cdot p$ $A$ $V(A)=A$ $A$

Vlastností pravdivosti nabídky (pravdivostí) aukce VCG se v případě online inzerce rozumí: k vyřešení problému maximalizace zisku musí inzerent nabízet tak, aby v případě, že odečtená cena byla přesně rovna stanovené ceně , inzerent získá nulový zisk z průměru kliknutí. Pro případ, kdy chce inzerent dosáhnout zisku s ROI nad určitou zadanou hodnotu, je potřeba nastavit minimální nabídku, při které je dosahována potřebná ROI. Jak s limitem ROI, tak bez něj, optimální sázka nezávisí na sázkách ostatních hráčů.

Když má inzerent kromě limitu návratnosti investic fixní rozpočet na reklamu za jednotku času a tento limit není fiktivní, ale pravidelně dosahovaný, pak jeho algoritmus pro nastavení optimální nabídky (maximalizace zisku) v aukci VCG přestane fungovat. má jednoduchý popis.

Algoritmus pro výpočet optimální sazby je také složitý a závisí na sazbách konkurentů, kdy není maximalizován zisk, ale nějaká kombinace obratu a zisku.

Případ různé klikatelnosti míst

Zvažte případ, kdy pravděpodobnost kliknutí na reklamu závisí na lokalitě. Nechť je pravděpodobnost kliknutí na místa 1, 2, 3 pro reklamu rovna , , , respektive , to znamená, že existují faktory menší než 1, které určují multiplikativní opravy počáteční pravděpodobnosti kliknutí. Říkejme jim klikatelné pozice. Bez ztráty obecnosti uvažujme případ, kdy jsou pozice uspořádány sestupně podle klikatelnosti, tedy . Rovnice pro určení ceny za proklik na první reklamu by byla: $i$ ${\displaystyle x_{1}\cdot p_{i))$ ${\displaystyle x_{2}\cdot p_{i))$ ${\displaystyle x_{3}\cdot p_{i))$ $\{x_{1},x_{2},x_{3}\}$ $x_{1}\geq x_{2}\geq x_{3}$ $c_{1}$

$x_{1}\cdot V(c_{1},p_{1})+x_{2}\cdot V(b_{2},p_{2})+x_{3}\cdot V(b_{3} ,p_{3})=x_{1}\cdot V(b_{2},p_{2})+x_{2}\cdot V(b_{3},p_{3})+x_{3}\ cdot V(b_{4},p_{4})$

Nahrazením dostaneme: $V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}$

$c_{1}\cdot p_{1}=((x_{1}-x_{2})\cdot V_{2}+(x_{2}-x_{3})\cdot V_{3} +x_{3}\cdot V_{4})/x_{1}$

$c_{1}=((x_{1}-x_{2})\cdot b_{2}\cdot p_{2}+(x_{2}-x_{3})\cdot b_{3}\cdot p_ {3}+x_{3}\cdot b_{4}\cdot p_{4})/(x_{1}\cdot p_{1})$

Nabídka 1. je tedy snížena právě natolik, aby se její hodnota rovnala váženému průměru hodnot reklam zobrazených níže a jedné neviditelné reklamy. Váhy v tomto průměrování jsou určeny klikatelností pozic. $V(c_{1},p_{1})$

Odkazy

↑ von Ahn, Luis Sponsored Search (PDF) (odkaz není k dispozici) . 15–396: Poznámky ke kurzu Science of the Web . Carnegie Mellon University (13. října 2011). Získáno 13. dubna 2015. Archivováno z originálu 6. března 2015. (neurčitý)
↑ Vickrey, William. Protispekulace, aukce a konkurenční zapečetěné tendry // The Journal of Finance : deník. - 1961. - Sv. 16 , č. 1 . - str. 8-37 . - doi : 10.1111/j.1540-6261.1961.tb02789.x .
↑ Clarke, E. Multipart Pricing of Public Goods (unspecified) // Public Choice. - 1971. - T. 11 , č. 1 . - S. 17-33 . - doi : 10.1007/bf01726210 .
↑ Groves, T. Incentives in Teams // Econometrica : journal. - 1973. - Sv. 41 , č. 4 . - S. 617-631 . - doi : 10.2307/1914085 .
↑ Douglas Brent West. Úvod do teorie grafů. — 2. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ Archivovaná kopie . Získáno 4. srpna 2015. Archivováno z originálu dne 23. září 2015. (neurčitý)
↑ logo/fbfordevelopers . Získáno 4. srpna 2015. Archivováno z originálu 19. září 2015. (neurčitý)
↑ Archivovaná kopie . Získáno 4. srpna 2015. Archivováno z originálu 9. ledna 2016. (neurčitý)
↑ Nová aukce a nové hodnocení v blogu Yandex.Direct - Advertising Technology Blog . Získáno 27. září 2015. Archivováno z originálu 12. září 2015. (neurčitý)