Vickrey-Clark-Groves mechanizmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. július 13-án felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

Az aukcióelméletben a Vickrey-Clark-Groves aukciós mechanizmus (általánosított Vickrey aukció ) a több tételből álló zárt formájú aukciók egyik fajtája. A résztvevők olyan ajánlatokat tesznek, amelyek megfelelnek az áruk becsült értékének, anélkül, hogy ismernék a többi résztvevő ajánlatát. Az aukció „társadalmilag optimális” módon osztja el az árut (az aukciós résztvevők vonatkozásában garantáltan az árut a legmagasabbra értékelt résztvevő kapja meg): az aukción minden résztvevő a saját árverési hatásával megegyező árat fizet. részvétel az aukció eredményén (az alapján, hogy részvétele hogyan érinti a többi résztvevőt) [1] . Arra is ösztönzi az ajánlattevőket, hogy saját értékükre tegyenek ajánlatot a tételre vonatkozóan, biztosítva, hogy az ajánlattevő számára az optimális stratégia az, hogy a tétel értékére vonatkozó értékelésüket az ajánlatukon keresztül a valóságnak megfelelően közöljék (a tétel valódi értékének licitálása). Ez a Vickrey aukció általánosítása a több tételes aukciókra. Az aukció William Vickrey [2] , Edward Clark [3] és Theodore Groves [4] nevéhez fűződik, akik sikeresen általánosították a Vickrey aukció ötletét egy tételes aukció esetére egy többtételes aukció esetére. aukciót a papírjaikban.

Formai leírás

Meghatározás

Legyen az aukción eladott áruk és a résztvevők összessége a „közhasznú” (a résztvevők halmaza „társadalomként” működik) a VCG aukció eredményéből egy adott ajánlatsorra. A résztvevőre és az árukra a résztvevő díja . $M=\{t_{1},\ldots ,t_{m}\}$ $N=\{b_{1},\lpontok ,b_{n}\}$ $V_{N}^{M}$ $kettős}$ $t_{j}$ $v_{{i}}(t_{{j}})$

A nyertes kinevezése

Az a résztvevő nyeri meg az aukciót , akinek a termékre tett ajánlata , azaz a maximális licit a résztvevők között, de kifizeti nyereményéből a fennmaradó résztvevők meg nem kapott hasznának összegét (magát a nyereményt a többi határozza meg a résztvevők közül). $kettős}$ $t_{j}$ $v_{{i}}(t_{{j}})$ $V_{{N\setminus \{b_{i}\}}}^{{M}}-V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j }\}}}$

Magyarázat (intuíció)

A versenyben résztvevők csoportja a következőképpen van meghatározva: . Ha egy termék elérhető a versenytársak számára, gazdagságot érhetnek el . Ha egy résztvevő nyer egy árut , a rendelkezésre álló javak készlete - ra csökken , de a jólét továbbra is elérhető . A két jóléti szint közötti különbség a többi játékos elvesztett nyeresége lesz, feltéve, hogy a játékos megkapja a javakat (a versenyzők engedték , hogy nyerjen). Ez az érték a versengő résztvevők jelentkezésétől függ, és a résztvevő nem ismeri . $kettős}$ $N\setminus \{b_{i}\}$ $t_{j}$ $V_{{N\setminus \{b_{i}\}}}^{{M}}$ $kettős}$ $M\setminus \{t_{j}\}$ $V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}$ $kettős}$ $t_{j}$ $kettős}$

A hasznossági függvény értéke a nyertes számára

A nyertes licitáló, akinek az ajánlata a tétel valódi értéke , a maximális nyereséget kapja. $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}\}}}\jobbra).$

Példák

1. példa

Apple példa a Vickrey aukciós példák részben .

2. példa

Tegyük fel, hogy két játékos van, és , és két áru, és , és minden résztvevő csak egy árut kaphat. Legyen ez a termék értéke a játékos számára . Tegyük fel , , , és . Látható, hogy mind a játékosok, mind a játékosok szívesebben veszik át az árut ; azonban a "társadalmilag optimális" aukciós terv egy árut rendel a játékoshoz (tehát a kapott értéke ), és egy jószágot a játékoshoz (tehát a kapott értéke ). Így a kapott összérték egyenlő lesz , ami optimális. $b_{1}$ $b_{2}$ $t_{1}$ $t_{2}$ $v_{{i,j}}$ $t_{j}$ $kettős}$ $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}$ $tíz$ $t_{2}$ $b_{2}$ $3$ $13$

Ha a játékos nem vesz részt az aukción, a résztvevő akkor is megkapja az árut , vagyis semmi sem változik számára. Az aktuálisan kapott érték egyenlő lesz a -val , ezért a játékos díjat számít fel . $b_{2}$ $b_{1}$ $t_{1}$ $tíz$ $b_{2}$ $10-10=0$

Ha a játékos nem vesz részt az aukción, a tárgy a játékoshoz kerül, és értéke . Az aktuálisan kapott érték egyenlő lesz a -val , ezért a játékos díjat számít fel . $b_{1}$ $t_{1}$ $b_{2}$ $5$ $3$ $b_{1}$ $5-3=2$

3. példa

Fontolja meg a több tételes aukciót. Hagyja, hogy az aukción részt vegyenek az ajánlattevők, a házak és a ház értéke az ajánlattevő számára . Az aukció lehetséges eredménye ebben az esetben egy bipartit gráfban történő párosítás lehet, melynek segítségével házpárok készíthetők aukciós résztvevőkkel. Ha ismerjük az értékeket, akkor a társadalmi jólét maximalizálása arra korlátozódik, hogy a megfelelő bipartit gráfban megtaláljuk a maximális súlyillesztést [5] . Ha nem ismerjük az értékeket, akkor ehelyett kérhetjük, hogy a tag mennyit hajlandó fizetni a házért . Jelölje , ha a résztvevő házat kap a párosításban . Most kiszámítjuk a maximális súly illesztését a kétrészes gráfban arányokban súlyként történő hozzárendelés esetén és kiszámítjuk $n$ $n$ ${\tilde v}_{{ij))$ $j$ $én$ ${\tilde b}_{{ij}}$ $én$ $j$ $b_{i}(a)={\tilde b}_{{ik))$ $én$ $k$ $a$ $a^{*}$

p_{i}=\left[\max _{{a\in A}}\sum _{{j\neq i}}b_{j}(a)\right]-\sum _{{j\neq i }}b_{j}(a^{*})

Az első tag egy másik maximális súlyegyeztetés a kétrészes gráfban, a második tag pedig könnyen beszerezhető a -ból . $a^{*}$

A termék értékére vonatkozó értékelésének valós feltárására irányuló stratégia optimalitása

Az ebben a bekezdésben leírtak azt igazolják, hogy az Ön valódi értékbecslésével megegyező ajánlat beállítása optimális az Ön számára [6] . Legyen minden résztvevő számára a jó valódi értéke, mondjuk (az általánosság elvesztése nélkül), amit a jószág valódi értékére licitálva kap . Ekkor a résztvevő által elért nettó nyereség . Mivel ez nem függ ettől, a nettó nyereség maximalizálása az aukciós mechanizmus szerint történik, miközben maximalizálja a beállított licit összbevételét . Más szóval, az aukciós mechanizmus úgy osztja ki a kifizetéseket, hogy amikor a játékos eléri a maximális jövedelmet, akkor eléri a maximális profitértéket. A résztvevő feladata pedig nem az árfolyamok manipulálása, hanem az, hogy olyan árfolyamot állítson be, amely megegyezik az áru valódi értékével. Ez lehetővé teszi a résztvevőknek, hogy kizárják a fizetési funkciót a nyereségük optimalizálásának feladatából. $kettős}$ $v_{i}$ $t_{i}$ $kettős}$ $t_{i}$ $U_{i}$ $kettős}$ $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}$

Írjuk fel az átvett áru valódi értékével megegyezően licitáló résztvevő nettó nyeresége és az árura hamis ajánlattételi stratégiát alkalmazó és az árut valós értékű árut átvevő résztvevő nettó nyeresége közötti különbséget . ez a hamis ajánlattételi stratégia által generált maximális teljes megtérülés. De az áruk résztvevőhöz való hozzárendelése eltér az áruk résztvevőhöz való hozzárendelésétől , amely a maximális összjövedelmet biztosítja. Ezért , és így tovább. $U_{i}-U_{j}=\left[v_{i}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}} \jobbra]-\balra[v_{j}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\jobbra]$ $U_{i}$ $kettős}$ $v_{i}$ $t_{i}$ $U_{j}$ $kettős}$ $v'_{i}$ $t_{i}$ $t_{j}$ $v_{j}$ $\left[v_{j}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\jobbra]$ $t_{j}$ $kettős}$ $t_{i}$ $kettős}$ $\left[v_{i}+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{i}\}}}\jobbra]-\left[v_{j }+V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j}\}}}\right]\geq 0$ $U_{i}\geq U_{j}$

Használata az online reklámozásban

A VCG aukciót internetes oldalakon lévő hirdetési felületek értékesítésére használják. Ezt az aukciós modellt különösen a Facebook [7] , a Google (partnerhálózatában) [8] és a Yandex (a keresési eredményoldalon) [9] használja . Egy másik népszerű hirdetési felület értékesítési modell az általánosított másodáras aukció.

Engedje be a reklámblokkoló helyeket. Számos hirdetés verseng ezekért a helyekért. A kattintásonkénti fizetési modellben a versengő hirdetések fontos paraméterei az ajánlatok és a kattintási valószínűségek. $K$ ${kettős}}$ ${p_{i}}$

Egy jelölt értékét ebben a modellben a függvény adja meg . A legmagasabb értékű hirdetések jelennek meg. A - edik játékosnak . $V(b,p)=b\cdot p$ $K$ $én$ $V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}$

Az értékfüggvény bonyolultabb változatai is lehetségesek , ennek a függvénynek fontos követelménye a sebesség monotonitása . $V$ $b$

A VCG aukció szabályai egy adott értékfüggvényre és a hirdetési blokkban elhelyezett helyekre a következők: ki kell választani azokat a hirdetéseket, ahol a maximum van, és a -edik játékostól annyi pénzt vesz fel kattintásonként , hogy az érték kevesebb, mint a eredeti ajánlatának értéke pontosan annyival, amennyivel a megjelenített játékosok összértéke csökkenne, ha a játékos nem vesz részt az aukción. $V(b,p)$ $K$ $K$ $V$ $én$ $c_{i}$ $V(c_{i},p_{i})$ $V(b_{i},p_{i})$ $én$

Tekintsük azt az esetet, amikor minden pozíció egyformán jó, vagyis a hirdetésekre leadott kattintások valószínűsége nem függ a pozíciótól.

Ezután három hely esetén ( ) az első hirdetés kattintásonkénti költségének kiszámításához meg kell oldania a következő egyenletet: $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})$

Ebben az egyenletben a két tag érvénytelenítve adja: $V(c_{1},p_{1})=V(b_{4},p_{4}).$

Azaz az első hirdetés CPC-jének kiszámításához csökkentenie kell annak ajánlatát, hogy az értéke az első meg nem jelenő játékos értékére csökkenjen (jelen esetben a 4. hirdetés).

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

Hasonló állítás igaz a 2. és 3. játékosra is:

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

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

Így ha az aukción részt vevő hirdetések kattintási valószínűsége egyenlő (a CTR -értékek azonosak), és az ajánlatuk 10, 7, 5, 2, akkor az első három kerül a megjelenítésre, és mindannyian fizetnek. 2 - a 4. hirdetés ára.

Abban az esetben, ha a VCG aukció egybeesik a második áras aukcióval. $K=1$

Egy aukción keverhetők azok a játékosok, akik hajlandók rubelt fizetni kattintásonként (értékkel ), és azok a játékosok, akik hajlandók rubelt fizetni megjelenítésenként, ekkor az értékük egyenlő . A megjelenítésre vonatkozó nyilvános ajánlat amnesztiájának kiszámítására szolgáló algoritmus hasonló képletekből származik. $b$ $V=b\cdot p$ $A$ $V(A)=A$ $A$

A VCG aukció ajánlattételi valóságtartalma (igazságosság) online hirdetés esetén a következőket jelenti: a hirdetőnek a nyereség maximalizálása problémájának megoldása érdekében úgy kell licitálnia, hogy ha a levont ár pontosan megegyezne a beállított árral. , akkor a hirdető nulla nyereséghez jutna a kattintások átlagából. Abban az esetben, ha a hirdető egy bizonyos meghatározott érték feletti ROI -val szeretne nyereséget elérni , be kell állítania azt a minimális ajánlatot, amelynél eléri a kívánt ROI-t. A ROI felső határával és anélkül is, az optimális tét nem függ a többi játékos tététől.

Ha egy hirdetőnek a ROI-korláton kívül fix időegységre eső hirdetési költségkerete van, és ez a korlát nem fiktív, hanem rendszeresen eléri, akkor a VCG aukción az optimális ajánlat beállítására (a profit maximalizálására) vonatkozó algoritmusa megszűnik. egyszerű leírása van.

Ezenkívül az optimális ráta kiszámításának algoritmusa is összetett, és a versenytársak árfolyamaitól függ, amikor nem a profit maximalizálása, hanem a forgalom és a nyereség valamilyen kombinációja.

A helyek eltérő kattinthatóságának esete

Tekintsük azt az esetet, amikor a hirdetésre való kattintás valószínűsége a helytől függ. Legyen a hirdetés 1., 2., 3. helyére történő kattintás valószínűsége egyenlő , , , vagyis vannak 1- nél kisebb tényezők, amelyek meghatározzák a kezdeti kattintási valószínűség multiplikatív korrekcióit. Nevezzük őket kattinthatósági pozícióknak. Az általánosság elvesztése nélkül tekintsük azt az esetet, amikor a pozíciók a kattinthatóság csökkenő sorrendjében vannak elrendezve, azaz . Az első hirdetés kattintásonkénti költségének meghatározására szolgáló egyenlet a következő: $én$ ${\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})$

Behelyettesítve a következőket kapjuk: $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})$

Így az 1. ajánlata éppen annyira csökken, hogy annak értéke egyenlő legyen az alább látható hirdetések és egy láthatatlan hirdetés értékeinek súlyozott átlagával. Ebben az átlagolásban a súlyokat a pozíciók kattinthatósága határozza meg. $V(c_{1},p_{1})$

Linkek

↑ von Ahn, Luis Szponzorált keresés (PDF) (a link nem érhető el) . 15–396: Science of the Web Course Notes . Carnegie Mellon Egyetem (2011. október 13.). Letöltve: 2015. április 13. Az eredetiből archiválva : 2015. március 6.. (határozatlan)
↑ Vickrey, William. Ellenspekuláció, aukciók és zárt versenypályázatok // The Journal of Finance : folyóirat. - 1961. - 1. évf. 16 , sz. 1 . - 8-37 . o . - doi : 10.1111/j.1540-6261.1961.tb02789.x .
↑ Clarke, E. Közjavak többrészes árképzése (meghatározatlan) // Public Choice. - 1971. - T. 11 , 1. sz . - S. 17-33 . - doi : 10.1007/bf01726210 .
↑ Groves, T. Incentives in Teams // Econometrica : Journal. - 1973. - 1. évf. 41 , sz. 4 . - P. 617-631 . - doi : 10.2307/1914085 .
↑ Douglas Brent West. Bevezetés a gráfelméletbe. — 2. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ Archivált másolat . Letöltve: 2015. augusztus 4. Az eredetiből archiválva : 2015. szeptember 23.. (határozatlan)
↑ logó/fbfordevelopers . Letöltve: 2015. augusztus 4. Az eredetiből archiválva : 2015. szeptember 19. (határozatlan)
↑ Archivált másolat . Letöltve: 2015. augusztus 4. Az eredetiből archiválva : 2016. január 9.. (határozatlan)
↑ Új aukció és új rangsor a Yandex.Direct - Advertising Technology Blogban . Letöltve: 2015. szeptember 27. Az eredetiből archiválva : 2015. szeptember 12.. (határozatlan)