Vickrey auktion

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 3 oktober 2018; kontroller kräver 11 redigeringar .

Vickrey-auktionen är en sluten auktionsalgoritm i en omgång (vars deltagare inte känner till varandras bud), där deltagaren med det högsta budet får rätt att köpa, men köpet görs till det andra maxbudet.

Auktionen föreslogs av William Vickrey . Denna typ av auktion är strategiskt lik den engelska auktionen , vilket uppmuntrar budgivare att bjuda på deras verkliga värde på föremålet.

Vickrey-auktioner är väl studerade i den ekonomiska litteraturen. En marknad där de används flitigt är frimärkssamlandet . eBay -auktionssystemet liknar också, men inte identiskt, med Vickrey-auktionen. En lätt generaliserad version av Vickrey-auktionen, kallad en generaliserad andraprisauktion , som skiljer sig från VCG-mekanismen , används i Google , Yahoo [1] [2] och Yandex onlineannonseringssystem .

Generaliseringar

Vickreys originalartikel handlade endast om auktioner för försäljning av enkla, odelbara varor. I detta fall är villkoren för Vickrey-auktionen och den stängda auktionen med andrapriset likvärdiga.

Auktion med ett enhetligt pris

I fallet med flera identiska (eller delbara) föremål som säljs i en enda auktion, är den uppenbara generaliseringen att sälja föremålet till alla vinnande budgivare till det högsta priset av otillfredsställda bud. Denna generalisering är känd som auktionen med enhetligt pris. Det senare uppmuntrar deltagarna att bjuda enligt deras verkliga värde endast när varje spelare tillåts köpa endast en vara. Om det är möjligt att lägga bud på flera varor är optimalitetsegenskapen för sanna bud i allmänhet inte uppfylld.

Vickrey-Clark-Groves-mekanism (VCG-auktion)

En generalisering av Vickrey-auktionen till försäljning av flera föremål, samtidigt som incitamenten för rättvis budgivning bibehålls, är känd som Vickrey-Clarke-Groves (VCG)-mekanismen. Tanken bakom en VCG-auktion är att varje budgivare betalar ett pris baserat på hur deras deltagande påverkar alla andra budgivare. Varje spelare betalar nämligen i slutet av auktionen ett belopp som motsvarar det förlorade värdet av varor av andra spelare på grund av att denna spelare deltar i auktionen.

Anta till exempel att vi vill auktionera ut två äpplen med tre budgivare.

Deltagare A vill ha ett äpple och bjuder $5.
Deltagare B vill också ha ett äpple och är villig att betala $2.
Deltagare C gör anspråk på två äpplen och har för avsikt att betala $6 för båda, men är ovillig att köpa ett äpple utan det andra.

Först bestämmer vi vinnarna genom att maximera insatserna: äpplena går till deltagare A och B (eftersom C inte har förlorat ett äpple till deltagare A , gör anspråk på det andra).

För det andra, för att fastställa betalningar, överväger vi vad som skulle hända om vinnaren inte deltog i auktionen.

Vinnare A :s betalning : B får äpplet genom att satsa $2. Om A inte var närvarande skulle C vinna båda äpplena och betala $6 för dem . Så A betalar skillnaden mellan C :s pris för båda äpplena och B :s pris för ett av dem: $6-$2 = $4.
Vinnare B :s utbetalning : A får äpplet genom att satsa $5 och C får ingenting. Utan B skulle C ha fått båda äpplena för $6 (eftersom $6 för två äpplen överstiger A :s $5-bud i frånvaro av andra deltagare) . Därför betalar B mellanskillnaden $6-$5 = $1.

Vickrey-Clark-Groves-mekanismen (VCG-auktion) i onlineannonsering

En VCG-auktion används för att sälja reklamplatser på webbplatser. I synnerhet Yandex [3] , Facebook [4] och Google (i deras partnernätverk) [5] använder denna auktionsmodell . 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_{i})+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.

Med VCG-auktionen är det samma som 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 när det gäller internetannonsering innebär följande: för att lösa problemet med att maximera sin vinst måste annonsören lägga bud så att om priset som debiterades 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$ $x_{1}\cdot p_{1}$ $x_{2}\cdot p_{1}$ $x_{3}\cdot p_{1}$ $\{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}$

$V_{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})$

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

Egenskaper

Stimulera avslöjandet av sanna betyg

I en Vickrey oberoende budauktion maximerar varje deltagare användbarheten genom att ange föremålets verkliga individuella värde. Med andra ord är strategin att tillkännage sanna värderingar dominerande för engångsauktioner från Vickrey.

Resursallokeringseffektivitet

En enda Vickrey-auktion är effektiv (vinnaren är den budgivare vars individuella uppskattning av föremålets värde är högst) i det mest allmänna fallet; det är alltså utgångsmodellen mot vilken effektiviteten av resursallokeringen i andra auktionsmodeller kan utvärderas.

Begränsningar

Med alla fördelar har Vickrey-auktionen ett antal begränsningar:

Det tillåter inte prisundersökningar (köpare att ta reda på marknadspriser om de är osäkra på sin värdering) förutom genom en serie på varandra följande auktioner.
Säljare kan använda "dummy rates" för att öka sina vinster.
I en serie av på varandra följande Vickrey-auktioner är strategin för budgivare som deklarerar sina verkliga värderingar inte längre dominerande.

VCG-mekanismen har ytterligare begränsningar:

Möjlighet att förlora bud från auktionsdeltagare.
Sårbarhet hos köpare på grund av möjligheten till "falska kurser" från säljarens sida.
Bristen på maximering av säljarens intäkter - den senare kan till och med visa sig vara lika med noll i slutet av VCG-auktionen. Om målet med auktionen är att maximera säljarens vinst, och inte bara fördela resurser effektivt bland köparna, så är VCG kanske inte ett bra val.
Säljarens intäkter är inte monotona i förhållande till taxornas storlek.

Icke-monotoniciteten hos säljarens intäkter i förhållande till kursen kan demonstreras av följande exempel.

Betrakta tre deltagare A , B och C , och två identiska produkter Y och Z.

A gör anspråk på både varor och bjuder $2 för summan av Y och Z .
Både B och C bjuder $2 för vardera objektet ($2 för Y eller Z ).

Som ett resultat går Y och Z till B och C , men till en kostnad av $0, som du kan se genom att successivt ta bort B och C .

Dessutom, om C hade bjudit $0 istället för $2, då skulle säljaren ha fått $2 istället för $0. Eftersom säljarens intäkter också kan öka med en höjning av priserna B och C , visar det sig vara icke-monotona.

Se även

Anteckningar

↑ Benjamin Edelman, Michael Ostrovsky och Michael Schwarz : "Internetannonsering och den generaliserade andraprisauktionen: Sälja miljarder dollar värda nyckelord". American Economic Review 97(1), 2007 s. 242-259.
↑ Hal R. Varian: "Positionsauktioner". International Journal of Industrial Organization, 2006, doi:10.1016/j.ijindorg.2006.10.002.
↑ Så fungerar auktionen på direkt (ryska) . Arkiverad från originalet den 12 februari 2018. Hämtad 12 februari 2018.
↑ logotyp/fbfordevelopers . Hämtad 30 juli 2015. Arkiverad från originalet 19 september 2015. (obestämd)
↑ Arkiverad kopia . Hämtad 30 juli 2015. Arkiverad från originalet 9 januari 2016. (obestämd)

Litteratur

W. Vickrey. Motspekulation, auktioner och konkurrenskraftiga förseglade anbud. Columbia University. 1961
von Ahn, Luis (2008-09-30)."Auktioner" (PDF). 15-396: Science of the Web Course Nodes. Carnegie Mellon University. https://web.archive.org/web/20081008174053/http://scienceoftheweb.org/15-396/lectures/lecture09.pdf . Hämtad 2008-11-06.