Vickrey-Clark-Groves mekanism

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 juli 2019; kontroller kräver 4 redigeringar .

I auktionsteorin är Vickrey-Clark-Groves-auktionsmekanismen ( generaliserad Vickrey-auktion ) en typ av auktioner i sluten form med flera föremål. Deltagarna lägger bud som motsvarar deras uppskattningar av varans värde, utan att känna till andra deltagares bud. Auktionen distribuerar varorna på ett "socialt optimalt" sätt (i förhållande till auktionsdeltagarna är deltagaren med högst värdering av varorna garanterad att få den): varje deltagare i auktionen betalar ett pris som motsvarar effekten av hans deltagande på resultatet av auktionen (baserat på hur hans deltagande påverkar alla andra deltagare) [en]. Det skapar också incitament för budgivare att bjuda sin egen värdering av föremålet, vilket säkerställer att den optimala strategin för budgivaren är att sanningsenligt kommunicera sin värdering av föremålets värde genom sitt bud (buda deras verkliga värde på föremålet). Detta är en generalisering av Vickrey-auktionen för auktioner med flera föremål. Auktionen är uppkallad efter William Vickrey [2] , Edward Clark [3] och Theodore Groves [4] som framgångsrikt generaliserade idén med Vickrey-auktionen för fallet med en auktion med ett föremål till fallet med en multi-artikel auktion i sina tidningar.

Formell beskrivning

Definition

För varje uppsättning varor som säljs på auktionen och en uppsättning deltagare , låt vara "allmännyttan" (uppsättningen av deltagare fungerar som ett "samhälle") från resultatet av VCG-auktionen för en given uppsättning bud. För deltagaren och varorna blir deltagarens pris . $M=\{t_{1},\ldots ,t_{m}\}$ $N=\{b_{1},\ldots ,b_{n}\}$ $V_{N}^{M}$ $bi}$ $t_{j}$ $v_{{i}}(t_{{j}})$

Utnämning av vinnare

Deltagaren , vars bud på produkten , nämligen är det maximala bland deltagarna, vinner auktionen, men betalar vad som är lika med summan av den icke mottagna förmånen för de återstående deltagarna från hans vinster (vinsten i sig bestäms av resten av deltagarna). $bi}$ $t_{j}$ $v_{{i}}(t_{{j}})$ $V_{{N\setminus \{b_{i}\}}}^{{M}}-V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j }\}}}$

Förklaring (intuition)

Uppsättningen av tävlande deltagare för definieras enligt följande: . När en produkt är tillgänglig för konkurrenter kan de uppnå rikedom . Att vinna en vara av en deltagare minskar mängden tillgängliga varor till , men välfärden är fortfarande uppnåbar . Skillnaden mellan dessa två nivåer av välbefinnande kommer att vara den förlorade vinsten för de andra spelarna, förutsatt att spelaren får varorna (konkurrenter tillät honom att vinna). Detta värde beror på applikationer från konkurrerande deltagare och är inte känt för deltagaren . $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}$

Värdet på nyttofunktionen för vinnaren

Den vinnande budgivaren, vars bud är hans verkliga värde på föremålet , får den maximala vinsten. $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}\}}}\höger).$

Exempel

Exempel #1

Apple-exempel i avsnittet Vickrey Auktionsexempel .

Exempel #2

Anta att det finns två spelare, och , och två varor, och , och varje deltagare kan bara få en vara. Låt detta vara värdet av produkten för spelaren . Låt oss sätta , , , och . Det kan ses att både spelare och kommer att föredra att ta emot varorna ; dock tilldelar en "socialt optimal" auktionsdesign en vara till spelaren (så dess mottagna värde är ) och en vara till spelaren (så dess mottagna värde är ). Således kommer det totala värdet som erhålls att vara lika med , vilket är optimalt. $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}$ $tio$ $t_{2}$ $b_{2}$ $3$ $13$

Om spelaren inte deltar i auktionen får deltagaren fortfarande varorna , det vill säga ingenting förändras för honom. Det aktuella mottagna värdet kommer att vara lika med , därför kommer spelaren att debiteras . $b_{2}$ $b_{1}$ $t_{1}$ $tio$ $b_{2}$ $10-10=0$

Om spelaren inte deltar i auktionen går föremålet till spelaren och har ett värde på . Det aktuella mottagna värdet kommer att vara lika med , därför kommer spelaren att debiteras . $b_{1}$ $t_{1}$ $b_{2}$ $5$ $3$ $b_{1}$ $5-3=2$

Exempel #3

Överväg en auktion med flera föremål. Låt auktionen involvera budgivare, hus och husets värde för budgivaren . Ett möjligt resultat av auktionen i detta fall kan vara en matchning i en tvådelad graf , med hjälp av vilken huspar med auktionsdeltagare kan göras. Om vi känner till värdena så är maximeringen av social välfärd begränsad till att hitta en maximal viktmatchning i motsvarande tvådelade graf [5] . Om vi inte känner till värdena kan vi istället be om de priser medlemmen är villig att betala för huset . Ange om deltagaren får ett hus i matchningen . Nu beräknar vi matchningen av den maximala vikten i den tvådelade grafen vid tilldelning i priser som vikter och beräknar $n$ $n$ ${\tilde v}_{{ij))$ $j$ $i$ ${\tilde b}_{{ij))$ $i$ $j$ $b_{i}(a)={\tilde b}_{{ik))$ $i$ $k$ $a$ $a^{*}$

p_{i}=\vänster[\max _{{a\in A}}\summa _{{j\neq i}}b_{j}(a)\höger]-\summa _{{j\neq i }}b_{j}(a^{*})

Den första termen är en annan maximal viktmatchning i den tvådelade grafen, och den andra termen kan enkelt erhållas från . $a^{*}$

Optimalitet i strategin att sanningsenligt avslöja sina bedömningar av värdet av en produkt

Det som står i det här stycket bevisar att det är optimalt för dig att sätta ett bud som är lika med din sanna värdeuppskattning [6] . För varje deltagare , låt hans sanna värde av godan vara, låt oss säga (utan förlust av allmänhet) vad han får genom att bjuda sitt sanna värde på godan. Då blir nettovinsten som uppnås av deltagaren . Eftersom det inte beror på , uppnås maximeringen av nettovinsten enligt auktionsmekanismen samtidigt som den totala inkomsten för det angivna budet maximeras . Med andra ord, auktionsmekanismen tilldelar betalningar på ett sådant sätt att när spelarens maximala inkomst uppnås, uppnås det maximala vinstvärdet. Och deltagarens uppgift är inte att manipulera priserna, utan att sätta en kurs som kommer att vara lika med hans verkliga värde på varorna. Detta gör att deltagarna kan utesluta betalningsfunktionen från uppgiften att optimera sina vinster. $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)=\summa _{{i}}v_{i}-\summa _{{j\neq i}}v_{j} +V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}}-V_{{N\setminus \{b_{i}\}}} ^{M}=\summa _{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}$ $=\summa _{i}v_{i}-V_{{N\setminus \{b_{i}\}}}^{M}$ $V_{{N\setminus \{b_{i}\}}}^{M}$ $v_{i}$ $\sum _{i}v_{i}$ $v_{i}$

Låt oss skriva ner skillnaden mellan nettovinsten för deltagaren som bjuder lika med hans verkliga värde av de mottagna varorna och nettovinsten för deltagaren med en falsk budstrategi för varorna och fick varorna med det verkliga värdet . detta är den maximala totala avkastningen som genereras av den falska budgivningsstrategin. Men tilldelningen av varorna till deltagaren skiljer sig från tilldelningen av varorna till deltagaren, som ger den maximala totala inkomsten. Därför och så vidare. $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}\}}}\höger]-\left[v_{j }+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\right]\geq 0$ $U_{i}\geq U_{j}$

Använd i onlineannonsering

En VCG-auktion används för att sälja reklamplatser på webbplatser. I synnerhet används denna auktionsmodell av Facebook [7] , Google (i dess partnernätverk) [8] och Yandex (på sökresultatsidan) [9] . En annan populär modell för försäljning av annonsutrymme är den generaliserade andraprisauktionen.

Släpp in annonsblocksplatserna . Flera annonser konkurrerar om dessa platser. I betala per klick- modellen är de viktiga parametrarna för konkurrerande annonser deras bud och klicksannolikheter. $K$ ${bi}}$ ${pi}}$

Värdet av en kandidat i denna modell ges av funktionen . Annonserna med det högsta värdet visas. För den -e spelaren vi har . $V(b,p)=b\cdot sid$ $K$ $i$ $V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}$

Mer komplexa versioner av värdefunktionen är möjliga , ett viktigt krav för denna funktion är monotoni med avseende på hastigheten . $V$ $b$

Reglerna för en VCG-auktion för en given värdefunktion och placeringar i ett annonsblock är följande: du måste välja annonser med maximalt av och från den -:e spelaren tar så mycket pengar per klick att värdet är mindre än värdet av sitt ursprungliga bud exakt med det belopp som det totala värdet av de visade spelarna skulle falla om spelaren inte deltog i auktionen. $V(b,p)$ $K$ $K$ $V$ $i$ $c_{i}$ $V(c_{i},p_{i})$ $V(b_{i},p_{i})$ $i$

Tänk på fallet när alla positioner är lika bra, det vill säga sannolikheten för annonsklick beror inte på positionen.

Sedan för tre platser ( ) för att beräkna kostnaden per klick för den första annonsen måste du lösa ekvationen: $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})$

De två termerna i denna ekvation tar bort för att ge: $V(c_{1},p_{1})=V(b_{4},p_{4}).$

Det vill säga, för att beräkna CPC för den första annonsen måste du minska dess bud så att dess värde minskar till värdet för den första spelaren som inte visas (i det här fallet den 4:e annonsen).

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

Ett liknande uttalande gäller för andra och tredje spelarna:

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

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

Således, om klicksannolikheterna för annonserna i auktionen är lika ( CTR- poängen är desamma) och deras bud är 10, 7, 5, 2, kommer de tre första att gå till visningen, och de kommer alla att betala 2 - priset för den fjärde annonsen.

I det fall där VCG-auktionen sammanfaller med den andra prisauktionen. $K=1$

I en auktion kan både spelare som är villiga att betala rubel per klick (med ett värde av ) och spelare som är villiga att betala rubel per visning blandas, då är deras värde lika . Algoritmen för att beräkna amnestin för det exponerade budet för en visning erhålls från liknande formler. $b$ $V=b\cdot sid$ $A$ $V(A)=A$ $A$

Sanningsegenskapen för budgivning (truthfulness) för en VCG-auktion i fallet med onlineannonsering betyder följande: för att lösa problemet med att maximera sin vinst måste annonsören bjuda så att om det avdragna priset var exakt lika med det fastställda priset , skulle annonsören få noll vinst från genomsnittet av klick. För fallet när annonsören vill göra en vinst med en ROI över ett visst specificerat värde, måste han ställa in det lägsta bud för vilket den ROI han behöver uppnås. Både med och utan tak på ROI, den optimala insatsen beror inte på andra spelares insatser.

När en annonsör, utöver ROI-gränsen, har en fast annonsbudget per tidsenhet och denna gräns inte är fiktiv, utan regelbundet nås, då inte längre hans algoritm för att sätta det optimala budet (maximera sin vinst) i en VCG-auktion har en enkel beskrivning.

Algoritmen för att beräkna den optimala hastigheten är också komplex och beror på konkurrenternas priser, när inte vinsten maximeras, utan någon kombination av omsättning och vinst.

Fallet med olika klickbarhet för platser

Tänk på fallet där sannolikheten att klicka på en annons beror på platsen. Låt sannolikheten för ett klick på plats 1, 2, 3 för annonsen vara lika med , , , respektive , det vill säga det finns faktorer mindre än 1 som bestämmer de multiplikativa korrigeringarna av den initiala klicksannolikheten. Låt oss kalla dem klickbarhetspositioner. Utan förlust av allmänhet, låt oss överväga fallet när positionerna är ordnade i fallande ordning för klickbarhet, det vill säga . Ekvationen för att bestämma kostnaden per klick för den första annonsen skulle vara: $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})$

Ersättare får vi: $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})$

Således reduceras budet för den första så att dess värde blir lika med det viktade genomsnittet av värdena för annonserna som visas nedan och en osynlig annons. Vikterna i detta medelvärde bestäms av positionernas klickbarhet. $V(c_{1},p_{1})$

Länkar

↑ von Ahn, Luis Sponsrad sökning (PDF) (länk ej tillgänglig) . 15–396: Science of the Web Kursanteckningar . Carnegie Mellon University (13 oktober 2011). Hämtad 13 april 2015. Arkiverad från originalet 6 mars 2015. (obestämd)
↑ Vickrey, William. Motspekulation, auktioner och konkurrenskraftiga slutna anbud // The Journal of Finance : journal. - 1961. - Vol. 16 , nr. 1 . - S. 8-37 . - doi : 10.1111/j.1540-6261.1961.tb02789.x .
↑ Clarke, E. Flerdelad prissättning av allmänna nyttigheter (ospecificerat) // Offentligt val. - 1971. - T. 11 , nr 1 . - S. 17-33 . - doi : 10.1007/bf01726210 .
↑ Groves, T. Incentives in Teams // Econometrica : journal. - 1973. - Vol. 41 , nr. 4 . - s. 617-631 . - doi : 10.2307/1914085 .
↑ Douglas Brent West. Introduktion till grafteori. — 2:a. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ Arkiverad kopia . Hämtad 4 augusti 2015. Arkiverad från originalet 23 september 2015. (obestämd)
↑ logotyp/fbfordevelopers . Hämtad 4 augusti 2015. Arkiverad från originalet 19 september 2015. (obestämd)
↑ Arkiverad kopia . Hämtad 4 augusti 2015. Arkiverad från originalet 9 januari 2016. (obestämd)
↑ Ny auktion och ny ranking i Yandex.Direct - Advertising Technology Blog . Hämtad 27 september 2015. Arkiverad från originalet 12 september 2015. (obestämd)