Vickrey-Clark-Groves -mekanismi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 13. heinäkuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Huutokauppateoriassa Vickrey-Clark-Groves-huutokauppamekanismi (yleistetty Vickrey - huutokauppa ) on eräänlainen usean kohteen suljetun muodon huutokauppa. Osallistujat tekevät tarjouksia, jotka vastaavat heidän arvioimaansa tavaroiden arvoa, tietämättä muiden osallistujien tarjouksia. Huutokauppa jakaa tavarat "sosiaalisesti optimaalisella" tavalla (huutokaupan osallistujiin suhteutettuna tavaran korkeimman arvostuksen omaava osallistuja saa sen taatusti): jokainen huutokaupan osallistuja maksaa hinnan, joka on yhtä suuri kuin hänen saamansa vaikutus. osallistuminen huutokaupan tulokseen (sen perusteella, kuinka hänen osallistumisensa vaikuttaa kaikkiin muihin osallistujiin) [1] . Se myös kannustaa tarjoajia tekemään omasta arvostuksensa tuotteesta ja varmistaa, että tarjoajan paras strategia on ilmoittaa totuudenmukaisesti arvionsa kohteen arvosta tarjouksensa kautta (tarjoamalla kohteen todellisen arvon). Tämä on yleistys Vickreyn huutokaupasta usean kohteen huutokaupoista. Huutokauppa on nimetty William Vickreyn [2] , Edward Clarkin [3] ja Theodore Grovesin [4] mukaan, jotka onnistuneesti yleistivät Vickrey-huutokaupan idean yhden kohteen huutokaupan tapauksessa usean esineen tapauksessa. huutokaupan papereissaan.

Muodollinen kuvaus

Määritelmä

Olkoon minkä tahansa huutokaupassa myytyjen tavaroiden ja osallistujien joukon "yleinen hyöty" (osallistujien joukko toimii "yhteiskuntana") VCG-huutokaupan tuloksesta tietylle tarjousjoukolle. Osallistujalle ja tavaroille osallistujahinta on . $M=\{t_{1},\ldots ,t_{m}\}$ $N=\{b_{1},\ldots ,b_{n}\}$ $V_{N}^{M}$ $b_{i}$ $t_{j}$ $v_{{i}}(t_{{j}})$

Voittajan nimittäminen

Osallistuja , jonka tarjous tuotteesta on suurin osallistujien joukossa, voittaa huutokaupan, mutta maksaa sen summan, joka vastaa jäljellä olevien osallistujien saamaa saamaa voittoa (voitto itse määräytyy lopun mukaan osallistujista). $b_{i}$ $t_{j}$ $v_{{i}}(t_{{j}})$ $V_{{N\setminus \{b_{i}\}}}^{{M}}-V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j }\}}}$

Selitys (intuitio)

Kilpailevien osallistujien joukko määritellään seuraavasti: . Kun tuote on kilpailijoiden saatavilla, he voivat saavuttaa vaurautta . Kun osallistuja voittaa tavaran, käytettävissä olevien tavaroiden määrä pienenee , mutta hyvinvointi on silti saavutettavissa . Ero näiden kahden hyvinvointitason välillä on muiden pelaajien menetetyt voitot edellyttäen, että pelaaja saa tavarat (kilpailijat antoivat hänen voittaa). Tämä arvo riippuu kilpailevien osallistujien sovelluksista, eikä se ole osallistujan tiedossa . $b_{i}$ $N\setminus \{b_{i}\}$ $t_{j}$ $V_{{N\setminus \{b_{i}\}}}^{{M}}$ $b_{i}$ $M\setminus \{t_{j}\}$ $V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}$ $b_{i}$ $t_{j}$ $b_{i}$

Hyötyfunktion arvo voittajalle

Voittaja, jonka tarjous on hänen tuotteensa todellinen arvo , saa suurimman voiton. $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}\}}}\oikea).$

Esimerkkejä

Esimerkki #1

Apple-esimerkki Vickreyn huutokauppaesimerkit -osiossa .

Esimerkki #2

Oletetaan, että on kaksi pelaajaa, ja , ja kaksi tavaraa, ja , ja jokainen osallistuja voi vastaanottaa vain yhden tavaran. Olkoon tämä tuotteen arvo pelaajalle . Laitetaan , , ja . Voidaan nähdä, että molemmat pelaajat ja haluavat vastaanottaa tavarat ; kuitenkin "sosiaalisesti optimaalinen" huutokauppasuunnittelu antaa pelaajalle hyvän (siis sen vastaanotettu arvo on ) ja pelaajalle tavaran (siis sen vastaanotettu arvo on ). Siten saatu kokonaisarvo on yhtä suuri kuin , mikä on optimaalinen. $b_{1}$ $b_{2}$ $t_{1}$ $t_{2}$ $v_{{i,j}}$ $t_{j}$ $b_{i}$ $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}$ $kymmenen$ $t_{2}$ $b_{2}$ $3$ $13$

Jos pelaaja ei osallistu huutokauppaan, osallistuja saa silti tavarat , eli mikään ei muutu hänen osaltaan. Nykyinen vastaanotettu arvo on yhtä suuri kuin , joten pelaajaa veloitetaan . $b_{2}$ $b_{1}$ $t_{1}$ $kymmenen$ $b_{2}$ $10-10 = 0$

Jos pelaaja ei osallistu huutokauppaan, esine menee pelaajalle ja sen arvo on . Nykyinen vastaanotettu arvo on yhtä suuri kuin , joten pelaajaa veloitetaan . $b_{1}$ $t_{1}$ $b_{2}$ $5$ $3$ $b_{1}$ $5-3 = 2$

Esimerkki #3

Harkitse usean kohteen huutokauppaa. Olkoon huutokaupassa mukana tarjoajat, talot ja talon arvo tarjoajalle . Huutokaupan mahdollinen tulos tässä tapauksessa voi olla täsmäys kaksiosaisessa kaaviossa , jonka avulla voidaan tehdä talopareja huutokaupan osallistujien kanssa. Jos arvot tiedetään, niin sosiaalisen hyvinvoinnin maksimointi rajoittuu maksimipainosovituksen löytämiseen vastaavasta kaksiosaisesta graafista [5] . Jos emme tiedä arvoja, voimme sen sijaan kysyä hintoja, jotka jäsen on valmis maksamaan talosta . Merkitse , jos osallistuja saa talon vastaavuudessa . Nyt lasketaan , maksimipainon vastaavuus kaksiosaisessa kaaviossa , jos osuudet on annettu painoina ja lasketaan $n$ $n$ ${\tilde v}_{{ij))$ $j$ $i$ ${\tilde b}_{{ij))$ $i$ $j$ $b_{i}(a)={\tilde b}_{{ik))$ $i$ $k$ $a$ $a^{*}$

p_{i}=\vasen[\max _{{a\in A}}\summa _{{j\neq i}}b_{j}(a)\oikea]-\summa _{{j\neq i }}b_{j}(a^{*})

Ensimmäinen termi on toinen maksimipainosovitus kaksiosaisessa kaaviossa, ja toinen termi voidaan helposti saada osoitteesta . $a^{*}$

Strategian optimaalisuus paljastaa totuudenmukaisesti omat arvionsa tuotteen arvosta

Tässä kappaleessa kirjoitettu osoittaa, että todellista arvoa vastaavan hintatarjouksen asettaminen on optimaalinen sinulle [6] . Olkoon jokaiselle osallistujalle hänen todellisen tuotteen arvonsa , sanokaamme (yleisyyden menettämättä) se, mitä hän saa tarjoamalla hyvän arvon. Tällöin osallistujan saavuttama nettotulos on . Koska se ei ole riippuvainen , nettovoiton maksimointi saavutetaan huutokauppamekanismin mukaisesti ja maksimoi samalla asetetun tarjouksen kokonaistulot . Toisin sanoen huutokauppamekanismi jakaa maksut siten, että kun pelaajan maksimitulot saavutetaan, saavutetaan maksimivoittoarvo. Ja osallistujan tehtävänä ei ole manipuloida hintoja, vaan asettaa korko, joka on yhtä suuri kuin hänen tavaroiden todellinen arvo. Näin osallistujat voivat sulkea maksutoiminnon voittojensa optimoinnin ulkopuolelle. $b_{i}$ $v_{i}$ $t_{i}$ $b_{i}$ $t_{i}$ $U_{i}$ $b_{i}$ $U_{i}=v_{i}-\left(V_{{N\setminus \{b_{i}\}}}^{{M}}-V_{{N\setminus \{b_{i}\} }}^{{M\setminus \{t_{i}\}}}\right)=\sum _{{i}}v_{i}-\sum _{{j\neq i}}v_{j} +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\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}$

Kirjataan ylös saadun tavaran todellista arvoa vastaavan tarjouksen tehneen osallistujan nettovoiton ja tavarasta väärän tarjousstrategian käyttäneen ja todellisella arvolla tavarat vastaanottaneen osallistujan nettovoiton välillä . tämä on väärän hintatarjousstrategian tuottama suurin kokonaistuotto. Mutta tavaroiden luovutus osallistujalle eroaa tavaroiden luovuttamisesta osallistujalle, joka tuottaa suurimman kokonaistulon. Siksi ja niin edelleen. $U_{i}-U_{j}=\vasen[v_{i}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}} \oikea]-\vasen[v_{j}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\oikea]$ $U_{i}$ $b_{i}$ $v_{i}$ $t_{i}$ $U_{j}$ $b_{i}$ $v'_{i}$ $t_{i}$ $t_{j}$ $v_{j}$ $\left[v_{j}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\oikea]$ $t_{j}$ $b_{i}$ $t_{i}$ $b_{i}$ $\vasen[v_{i}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}}\oikea]-\vasen[v_{j }+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\right]\geq 0$ $U_{i}\geq U_{j}$

Käytä verkkomainonnassa

VCG-huutokauppaa käytetään mainospaikkojen myymiseen Internet-sivustoilla. Erityisesti tätä huutokauppamallia käyttävät Facebook [7] , Google (kumppaniverkostossaan) [8] ja Yandex (hakutulossivulla) [9] . Toinen suosittu mainostilan myyntimalli on yleinen toisen hinnan huutokauppa.

Päästä sisään mainoslohkopaikkoja . Useat mainokset kilpailevat näistä paikoista. Pay per click -mallissa kilpailevien mainosten tärkeitä parametreja ovat niiden hinnat ja napsautustodennäköisyys. $K$ ${b_{i}}$ ${p_{i}}$

Ehdokkaan arvon tässä mallissa antaa funktio . Mainokset, joiden arvo on suurin, näytetään. - : nnelle pelaajalle, joka meillä on . $V(b,p)=b\cpiste p$ $K$ $i$ $V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}$

Arvofunktiosta on mahdollista tehdä monimutkaisempia versioita , tärkeä vaatimus tälle funktiolle on monotonisuus nopeuteen nähden . $V$ $b$

VCG-huutokaupan säännöt tietylle arvofunktiolle ja sijoituksille mainoslohkossa ovat seuraavat: sinun on valittava mainokset, joissa on maksimi, ja -. pelaaja ottaa niin paljon rahaa napsautuksesta , että arvo on pienempi kuin alkuperäisen tarjouksensa arvosta täsmälleen sen verran, että näytettyjen pelaajien kokonaisarvo laskisi, jos pelaaja ei osallistu huutokauppaan. $V(b,p)$ $K$ $K$ $V$ $i$ $c_{i}$ $V(c_{i},p_{i})$ $V(b_{i},p_{i})$ $i$

Harkitse tilannetta, jossa kaikki paikat ovat yhtä hyviä, eli mainosten napsautusten todennäköisyys ei riipu paikasta.

Sitten kolmen paikan tapauksessa ( ) ensimmäisen mainoksen napsautuskohtaisen hinnan laskemiseksi sinun on ratkaistava yhtälö: $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})$

Tämän yhtälön kaksi termiä kumoutuvat antamaan: $V(c_{1},p_{1})=V(b_{4},p_{4}).$

Toisin sanoen ensimmäisen mainoksen napsautuskohtaisen hinnan laskemiseksi sinun on alennettava sen hintaa niin, että sen arvo laskee ensimmäisen näytettävän soittimen arvoon (tässä tapauksessa neljännen mainoksen).

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

Samanlainen väite pätee toiselle ja kolmannelle pelaajalle:

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

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

Jos siis huutokaupassa olevien mainosten napsautustodennäköisyydet ovat yhtä suuret ( napsautussuhteet ovat samat) ja niiden hintatarjoukset ovat 10, 7, 5, 2, ensimmäiset kolme siirtyvät näyttökertaan ja ne kaikki maksavat. 2 - 4. ilmoituksen hinta.

Siinä tapauksessa, että VCG-huutokauppa osuu samaan aikaan toisen hintahuutokaupan kanssa. $K = 1$

Yhdessä huutokaupassa sekä pelaajat, jotka ovat valmiita maksamaan ruplaa napsautuksesta (arvolla ) että pelaajat, jotka ovat valmiita maksamaan ruplaa näyttökerrasta, voidaan sekoittaa, jolloin heidän arvonsa on sama . Algoritmi näyttökerran paljastetun hintatarjouksen armahduksen laskemiseksi saadaan samanlaisista kaavoista. $b$ $V=b\cdot s$ $A$ $V(A)=A$ $A$

VCG-huutokaupan tarjouksen todenmukaisuusominaisuus (rehellisyys) tarkoittaa verkkomainonnan tapauksessa seuraavaa: Ratkaistakseen voiton maksimointiongelman, mainostajan on tarjottava niin, että jos vähennetty hinta olisi täsmälleen sama kuin asetettu hinta , mainostaja ei saisi napsautusten keskiarvosta voittoa nolla. Siinä tapauksessa, että mainostaja haluaa tehdä voittoa tietyn määritetyn arvon ylittävällä sijoitetun pääoman tuottoprosentilla , hänen on asetettava vähimmäishinta, jolla hänen tarvitsemansa ROI saavutetaan. Sekä sijoitetun pääoman tuottorajoituksella että ilman sitä, optimaalinen panos ei riipu muiden pelaajien panoksesta.

Kun mainostajalla on sijoitetun pääoman tuottorajan lisäksi kiinteä mainosbudjetti aikayksikköä kohden ja tämä raja ei ole kuvitteellinen, vaan saavutetaan säännöllisesti, hänen algoritminsa optimaalisen tarjouksen asettamiseksi (voittonsa maksimoimiseksi) VCG-huutokaupassa ei enää ole on yksinkertainen kuvaus.

Myös optimaalisen koron laskemisalgoritmi on monimutkainen ja riippuu kilpailijoiden koroista, kun voittoa ei maksimoida, vaan liikevaihdon ja voiton yhdistelmä.

Paikkojen erilaisen napsautettavuuden tapaus

Harkitse tapausta, jossa mainoksen napsautuksen todennäköisyys riippuu sijainnista. Olkoon mainoksen kohdissa 1, 2, 3 napsautuksen todennäköisyys yhtä suuri kuin , , , eli on olemassa tekijöitä, jotka ovat pienempiä kuin 1, jotka määräävät alkuperäisen napsautustodennäköisyyden kertovat korjaukset. Kutsutaan niitä napsautusasetuksiksi. Yleisuutta menettämättä tarkastellaan tapausta, jossa paikat on järjestetty napsautettavuuden laskevaan järjestykseen, eli . Yhtälö ensimmäisen mainoksen napsautuskohtaisen hinnan määrittämiseksi olisi: $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}\cpiste V(c_{1},p_{1})+x_{2}\cpiste V(b_{2},p_{2})+x_{3}\cpiste V(b_{3} ,p_{3})=x_{1}\cpiste V(b_{2},p_{2})+x_{2}\cpiste V(b_{3},p_{3})+x_{3}\ cdot V(b_{4},p_{4})$

Korvaamalla saamme: $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})$

Näin ollen 1.:n tarjousta pienennetään juuri sen verran, että sen arvo on yhtä suuri kuin alla olevien mainosten ja yhden näkymättömän mainoksen arvojen painotettu keskiarvo. Tämän keskiarvon painot määräytyvät sijaintien napsautettavuuden mukaan. $V(c_{1},p_{1})$

Linkit

↑ von Ahn, Luis Sponsoroitu haku (PDF) (linkki ei saatavilla) . 15–396: Tiede verkkokurssin muistiinpanot . Carnegie Mellon University (13. lokakuuta 2011). Haettu 13. huhtikuuta 2015. Arkistoitu alkuperäisestä 6. maaliskuuta 2015. (määrätön)
↑ Vickrey, William. Vastakeinottelu, huutokaupat ja kilpailukykyiset sinetöidyt tarjoukset // The Journal of Finance : päiväkirja. - 1961. - Voi. 16 , ei. 1 . - s. 8-37 . - doi : 10.1111/j.1540-6261.1961.tb02789.x .
↑ Clarke, E. Julkisten hyödykkeiden moniosainen hinnoittelu (määrittelemätön) // Public Choice. - 1971. - T. 11 , nro 1 . - S. 17-33 . - doi : 10.1007/bf01726210 .
↑ Groves, T. Incentives in Teams // Econometrica : Journal. - 1973. - Voi. 41 , no. 4 . - s. 617-631 . - doi : 10.2307/1914085 .
↑ Douglas Brent West. Johdatus graafiteoriaan. – 2. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ Arkistoitu kopio . Haettu 4. elokuuta 2015. Arkistoitu alkuperäisestä 23. syyskuuta 2015. (määrätön)
↑ logo/fbfordevelopers . Haettu 4. elokuuta 2015. Arkistoitu alkuperäisestä 19. syyskuuta 2015. (määrätön)
↑ Arkistoitu kopio . Haettu 4. elokuuta 2015. Arkistoitu alkuperäisestä 9. tammikuuta 2016. (määrätön)
↑ Uusi huutokauppa ja uusi sijoitus Yandex.Direct - Advertising Technology Blogissa . Haettu 27. syyskuuta 2015. Arkistoitu alkuperäisestä 12. syyskuuta 2015. (määrätön)