Vickrey auktion

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 3. oktober 2018; checks kræver 11 redigeringer .

Vickrey-auktionen er en en-runde lukket auktionsalgoritme (hvis deltagere ikke kender hinandens bud), hvor deltageren med det højeste bud får ret til at købe, men købet sker til det andet maksimumbud.

Auktionen blev foreslået af William Vickrey . Denne type auktion er strategisk lig den engelske auktion , hvilket tilskynder budgivere til at byde på deres sande værdi af varen.

Vickrey-auktioner er godt undersøgt i den økonomiske litteratur. Et marked, hvor de er meget brugt, er frimærkeindsamling . eBay - auktionssystemet ligner også, men ikke identisk, med Vickrey-auktionen. En let generaliseret version af Vickrey -auktionen, kaldet en generaliseret andenprisauktion , forskellig fra VCG-mekanismen , bruges i Google , Yahoo [1] [2] og Yandex online reklamesystemer .

Generaliseringer

Vickreys originale artikel omhandlede kun auktioner for salg af simple, udelelige varer. I dette tilfælde er betingelserne for Vickrey-auktionen og den lukkede auktion med den anden pris tilsvarende.

Auktion med ensartet pris

I tilfælde af flere identiske (eller delelige) genstande solgt på en enkelt auktion, er den åbenlyse generalisering at sælge genstanden til alle vindende budgivere til den højeste pris af utilfredse bud. Denne generalisering er kendt som ensartet prisauktion. Sidstnævnte tilskynder deltagerne til kun at byde i henhold til deres sande værdi, når hver spiller kun må købe én genstand. Hvis det er muligt at afgive bud på flere varer, er optimalitetsegenskaben ved sande bud generelt ikke opfyldt.

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

En generalisering af Vickrey-auktionen til salg af flere genstande, samtidig med at incitamenter til fair bud bevares, er kendt som Vickrey-Clarke-Groves (VCG)-mekanismen. Tanken bag en VCG-auktion er, at hver budgiver betaler en pris baseret på, hvordan deres deltagelse påvirker alle andre budgivere. Hver spiller betaler nemlig ved afslutningen af auktionen et beløb svarende til den tabte værdi af varer af andre spillere på grund af, at denne spiller deltager i auktionen.

Antag for eksempel, at vi vil bortauktionere to æbler med tre bydere.

Deltager A vil have ét æble og byder $5.
Deltager B ønsker også et æble og er villig til at betale $2.
Deltager C gør krav på to æbler og har til hensigt at betale $6 for begge, men er uvillig til at købe det ene æble uden det andet.

Først bestemmer vi vinderne ved at maksimere indsatsen: Æblerne går til deltager A og B (da, efter at have tabt et æble til deltager A , gør C ikke krav på det andet).

For det andet, for at bestemme betalinger, overvejer vi, hvad der ville ske, hvis vinderen ikke deltog i auktionen.

Vinder A 's betaling : B får æblet ved at satse $2. Hvis A ikke var til stede, ville C vinde begge æbler og betale $6 for dem . Så A betaler forskellen mellem C 's pris for begge æbler og B 's pris for et af dem: $6-$2 = $4.
Vinder B 's udbetaling : A får æblet ved at satse $5 og C får intet. Uden B ville C have modtaget begge æbler for $6 (fordi $6 for to æbler overstiger A 's $5-bud i fravær af andre deltagere) . Derfor betaler B forskellen $6-$5 = $1.

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

En VCG-auktion bruges til at sælge annoncepladser på internetsider. Især Yandex [3] , Facebook [4] og Google (i deres partnernetværk) [5] bruger denne auktionsmodel . En anden populær model til salg af reklameplads er den generaliserede andenprisauktion.

Lad i annonceblok steder. Flere annoncer konkurrerer om disse pladser. I betal pr. klik -modellen er de vigtige parametre for konkurrerende annoncer deres bud og kliksandsynligheder . $K$ ${b_{i}}$ ${p_{i}}$

Værdien af en kandidat i denne model er givet af funktionen . Annoncerne med den højeste værdi vises. For den -te spiller har vi . $V(b,p)=b\cdot s$ $K$ $jeg$ $V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}$

Mere komplekse versioner af værdifunktionen er mulige , et vigtigt krav til denne funktion er monotoni med hensyn til hastigheden . $V$ $b$

Reglerne for en VCG-auktion for en given værdifunktion og -placeringer i en annonceblok er som følger: du skal vælge annoncerne med det maksimale af og fra den -th spiller tager så mange penge pr. klik , at værdien er mindre end værdien af dets oprindelige bud nøjagtigt med det beløb, som den samlede værdi af de viste spillere ville falde, hvis spilleren ikke deltog i auktionen. $V(b,p)$ $K$ $K$ $V$ $jeg$ $c_{i}$ $V(c_{i},p_{i})$ $V(b_{i},p_{i})$ $jeg$

Overvej det tilfælde, hvor alle positioner er lige gode, det vil sige, at sandsynligheden for annonceklik ikke afhænger af positionen.

Så i tilfælde af tre steder ( ) for at beregne prisen pr. klik for den første annonce , skal du løse ligningen: $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 to led i denne ligning annullerer for at give: $V(c_{1},p_{1})=V(b_{4},p_{4}).$

Det vil sige, at for at beregne CPC for den første annonce, skal du reducere dens bud, så dens værdi falder til værdien af den første spiller, der ikke vises (i dette tilfælde den 4. annonce).

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

Et lignende udsagn gælder for 2. og 3. spillere:

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

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

Hvis kliksandsynligheden for annoncerne i auktionen er ens ( CTR- score er de samme), og deres bud er 10, 7, 5, 2, så vil de første tre gå til visningen, og de vil alle betale 2 - prisen på den 4. annonce.

Med VCG auktion er det samme som den anden pris auktion. $K=1$

I én auktion kan både spillere, der er villige til at betale rubler pr. klik (med en værdi på ) og spillere, der er villige til at betale rubler pr. visning blandes, så er deres værdi lig . Algoritmen til at beregne amnestien for det eksponerede bud på et indtryk er hentet fra lignende formler. $b$ $V=b\cdot s$ $EN$ $V(A)=A$ $EN$

Den bydende sandhedsegenskab (truthfulness) for en VCG-auktion i tilfælde af internetannoncering betyder følgende: For at løse problemet med at maksimere sin fortjeneste, skal annoncøren byde sådan, at hvis den opkrævede pris var nøjagtigt lig med den fastsatte pris , ville annoncøren få nul fortjeneste fra klikgennemsnit. I det tilfælde, hvor annoncøren ønsker at tjene penge med et ROI over en bestemt specificeret værdi, skal han indstille minimumsbuddet, hvor det ROI, han har brug for, opnås. Både med og uden loft på ROI afhænger den optimale indsats ikke af andre spilleres indsats.

Når en annoncør, ud over ROI-grænsen, har et fast reklamebudget pr. tidsenhed, og denne grænse ikke er fiktiv, men regelmæssigt nået, så er hans algoritme til at indstille det optimale bud (maksimere hans fortjeneste) i en VCG-auktion ikke længere har en enkel beskrivelse.

Algoritmen til at beregne den optimale sats er også kompleks og afhænger af konkurrenternes satser, når ikke profit er maksimeret, men en kombination af omsætning og profit.

Tilfældet med forskellig klikbarhed af steder

Overvej det tilfælde, hvor sandsynligheden for at klikke på en annonce afhænger af placeringen.

Lad sandsynligheden for et klik på pladserne 1, 2, 3 for annoncen være lig med henholdsvis , , , det vil sige, at der er faktorer mindre end 1, der bestemmer de multiplikative korrektioner til den indledende kliksandsynlighed. Lad os kalde dem klikbarhedspositioner. Uden tab af generalitet, lad os overveje tilfældet, når positionerne er arrangeret i faldende rækkefølge af klikbarhed, dvs. Ligningen for at bestemme prisen pr. klik for den første annonce ville være: $jeg$ $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})$

Udskiftning 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 vil sige, at buddet på 1. bliver reduceret, så dets værdi bliver lig med det vægtede gennemsnit af værdierne af annoncerne nedenfor og én usynlig annonce. Vægtene i denne gennemsnitsberegning bestemmes af positionernes klikbarhed. $V(c_{1},p_{1})$

Egenskaber

Stimulering af offentliggørelsen af sande karakterer

I en Vickrey uafhængig budauktion maksimerer hver deltager nytten ved at angive den sande individuelle værdi af varen. Med andre ord er strategien med at annoncere sande værdiansættelser dominerende for engangs Vickrey-auktioner.

Ressourceallokeringseffektivitet

En enkelt Vickrey-auktion er effektiv (vinderen er den budgiver, hvis individuelle estimat af varens værdi er højest) i det mest generelle tilfælde; det er således startmodellen, som effektiviteten af ressourceallokering i andre auktionsmodeller kan vurderes ud fra.

Begrænsninger

Med alle fordelene har Vickrey-auktionen en række begrænsninger:

Det tillader ikke prisundersøgelser (købere kan finde ud af markedspriser, hvis de er usikre på deres værdiansættelse), undtagen gennem en række på hinanden følgende auktioner.
Sælgere kan bruge "dummy rates" til at øge deres fortjeneste.
I en række på hinanden følgende Vickrey-auktioner er strategien med budgivere, der erklærer deres sande værdiansættelser, ikke længere dominerende.

VCG-mekanismen har yderligere begrænsninger:

Mulighed for at miste bud fra auktionsdeltagere.
Sårbarhed hos købere på grund af muligheden for "falske kurser" fra sælgers side.
Manglen på maksimering af sælgers omsætning - sidstnævnte kan endda vise sig at være lig nul ved slutningen af VCG-auktionen. Hvis målet med auktionen er at maksimere sælgers fortjeneste og ikke blot fordele ressourcer effektivt blandt køberne, så er VCG måske ikke et godt valg.
Sælgers omsætning er ikke ensformig i forhold til satsernes størrelse.

Ikke-monotoniciteten af sælgers omsætning i forhold til satsen kan påvises med følgende eksempel.

Overvej tre deltagere A , B og C og to identiske produkter Y og Z.

A gør krav på både varer og byder $ 2 for summen af Y og Z.
Både B og C byder $2 for begge varer ($2 for Y eller Z ).

Som et resultat går Y og Z til B og C , men til en pris på $0, som du kan se ved successivt at fjerne B og C .

Desuden, hvis C havde budt $0 i stedet for $2, så ville sælgeren have modtaget $2 i stedet for $0. Da sælgers omsætning også kan stige med en stigning i satserne B og C , viser det sig at være ikke-monotonisk.

Se også

Noter

↑ Benjamin Edelman, Michael Ostrovsky og Michael Schwarz : "Internetannoncering og den generaliserede andenprisauktion: Sælger milliarder af dollars værd af søgeord". American Economic Review 97(1), 2007 s. 242-259.
↑ Hal R. Varian: "Positionsauktioner". International Journal of Industrial Organisation, 2006, doi:10.1016/j.ijindorg.2006.10.002.
↑ Sådan fungerer auktionen på Direct (russisk) . Arkiveret fra originalen den 12. februar 2018. Hentet 12. februar 2018.
↑ logo/fbfordevelopers . Hentet 30. juli 2015. Arkiveret fra originalen 19. september 2015. (ubestemt)
↑ Arkiveret kopi . Hentet 30. juli 2015. Arkiveret fra originalen 9. januar 2016. (ubestemt)

Litteratur

W. Vickrey. Modspekulation, auktioner og lukkede udbud. Columbia University. 1961
von Ahn, Luis (30-09-2008). "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 . Hentet 2008-11-06.