Mecanismul Vickrey-Clark-Groves

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 13 iulie 2019; verificările necesită 4 modificări .

În teoria licitațiilor, mecanismul de licitație Vickrey-Clark-Groves ( licitație Vickrey generalizată ) este un tip de licitații în formă închisă cu mai multe articole. Participanții plasează oferte care corespund estimărilor lor cu privire la valoarea bunurilor, fără a cunoaște ofertele altor participanți. Licitația distribuie bunurile într-un mod „optim din punct de vedere social” (în raport cu participanții la licitație, participantul cu cea mai mare evaluare a bunurilor este garantat să le primească): fiecare participant la licitație plătește un preț egal cu impactul său. participarea la rezultatul licitației (pe baza modului în care participarea sa îi afectează pe toți ceilalți participanți) [1] . De asemenea, creează stimulente pentru ofertanți să-și ofere propria evaluare a articolului, asigurându-se că strategia optimă pentru ofertant este să comunice cu adevărat evaluarea valorii articolului prin oferta lor (oferind valoarea reală a articolului). Aceasta este o generalizare a licitației Vickrey pentru licitațiile cu mai multe articole. Licitația poartă numele lui William Vickrey [2] , Edward Clark [3] și Theodore Groves [4] care au generalizat cu succes ideea licitației Vickrey pentru cazul unei licitații cu un articol în cazul unui articol multiplu. licitație în actele lor.

Descriere formală

Definiție

Pentru orice set de bunuri vândute la licitație și un set de participanți , să fie „beneficiu public” (setul de participanți acționează ca o „societate”) din rezultatul licitației VCG pentru un anumit set de oferte. Pentru participant și bunuri, tariful participantului va fi de . $M=\{t_{1},\ldots ,t_{m}\}$ $N=\{b_{1},\ldots ,b_{n}\}$ $V_{N}^{M}$ $b_{i}$ $t_{j}$ $v_{{i}}(t_{{j}})$

Numirea câștigătorului

Participantul , a cărui ofertă pentru produs , și anume , este maximul dintre participanți, câștigă licitația, dar plătește din câștigurile sale egal cu valoarea beneficiului neprimit al participanților rămași (câștigul în sine este determinat de restul) a participanților). $b_{i}$ $t_{j}$ $v_{{i}}(t_{{j}})$ $V_{{N\setminus \{b_{i}\}}}^{{M}}-V_{{N\setminus \{b_{i}\}}}^{{M\setminus \{t_{j }\}}}$

Explicație (intuiție)

Setul de participanți concurenti pentru sunt definiti astfel: . Atunci când un produs este disponibil concurenților, aceștia pot obține bogăție . Câștigarea unui bun de către un participant reduce setul de bunuri disponibile la , dar bunăstarea este încă realizabilă . Diferența dintre aceste două niveluri de bunăstare va fi profitul pierdut al celorlalți jucători, cu condiția ca jucătorul să primească marfa (concurenții i-au permis să câștige). Această valoare depinde de aplicațiile participanților concurenți și nu este cunoscută de participant . $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}$

Valoarea funcției de utilitate pentru câștigător

Ofertantul câștigător, a cărui ofertă este valoarea sa reală a articolului , primește profitul maxim. $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}\}}}\dreapta).$

Exemple

Exemplul #1

Exemplu Apple în secțiunea Exemple de licitații Vickrey .

Exemplul #2

Să presupunem că există doi jucători, și , și două bunuri, și , și fiecare participant poate primi doar un bun. Fie ca aceasta să fie valoarea produsului pentru jucător . Să punem , , , și . Se poate observa ca ambii jucatori si vor prefera sa primeasca marfa ; cu toate acestea, un design de licitație „optim din punct de vedere social” atribuie un bun jucătorului (deci valoarea sa primită este ) și un bun jucătorului (deci valoarea sa primită este ). Astfel, valoarea totală obținută va fi egală cu , ceea ce este optim. $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}$ $zece$ $t_{2}$ $b_{2}$ $3$ $13$

Dacă jucătorul nu participă la licitație, participantul primește în continuare bunurile , adică nu se schimbă nimic pentru el. Valoarea curentă primită va fi egală cu , prin urmare jucătorul va fi taxat . $b_{2}$ $b_{1}$ $t_{1}$ $zece$ $b_{2}$ $10-10=0$

Dacă jucătorul nu participă la licitație, elementul merge către jucător și are o valoare de . Valoarea curentă primită va fi egală cu , prin urmare jucătorul va fi taxat . $b_{1}$ $t_{1}$ $b_{2}$ $5$ $3$ $b_{1}$ $5-3=2$

Exemplul #3

Luați în considerare o licitație cu mai multe articole. Lăsați licitația să implice ofertanți, case și valoarea casei pentru ofertant . Un posibil rezultat al licitației în acest caz poate fi o potrivire într-un grafic bipartit , cu ajutorul căruia se pot face perechi de case cu participanți la licitație. Dacă cunoaștem valorile, atunci maximizarea bunăstării sociale se limitează la găsirea unei potriviri maxime a ponderii în graficul bipartit corespunzător [5] . Dacă nu cunoaștem valorile, putem în schimb să cerem tarifele pe care membrul este dispus să le plătească pentru casă . Indicați dacă participantul primește o casă în potrivire . Acum calculăm , potrivirea ponderii maxime în graficul bipartit în cazul atribuirii în rate ca ponderi și calculăm $n$ $n$ ${\tilde v}_{{ij))$ $j$ $i$ ${\tilde b}_{{ij))$ $i$ $j$ $b_{i}(a)={\tilde b}_{{ik))$ $i$ $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^{*})

Primul termen este o altă potrivire a ponderii maxime în graficul bipartit, iar al doilea termen poate fi obținut cu ușurință din . $a^{*}$

Optimitatea strategiei de a dezvălui cu adevărat aprecierile cuiva asupra valorii unui produs

Ceea ce este scris în acest paragraf demonstrează că stabilirea unei sume licitate egale cu valoarea estimată a dvs. reală este optimă pentru dvs. [6] . Pentru fiecare participant , să fie adevărata sa valoare a bunului , să spunem (fără pierderea generalității) ce obține prin ofertarea adevăratei sale valori a bunului. Atunci profitul net realizat de participant va fi . Deoarece nu depinde de , maximizarea profitului net se realizează conform mecanismului de licitaţie , maximizând în acelaşi timp venitul total pentru oferta stabilită . Cu alte cuvinte, mecanismul de licitație atribuie plățile în așa fel încât atunci când este atins venitul maxim al jucătorului, să fie atinsă valoarea maximă a profitului. Iar sarcina participantului nu este să manipuleze ratele, ci să stabilească o rată care să fie egală cu adevărata sa valoare a mărfurilor. Acest lucru permite participanților să excludă funcția de plată din sarcina de a-și optimiza profiturile. $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}$

Să notăm diferența dintre profitul net al participantului care licitează egal cu valoarea sa reală a bunurilor primite și profitul net al participantului cu o strategie de licitare falsă pentru bunurile și a primit bunurile cu valoarea adevărată . aceasta este rentabilitatea totală maximă generată de strategia de licitare falsă. Dar atribuirea bunurilor către participant diferă de atribuirea bunurilor către participant, care oferă venitul total maxim. Prin urmare , și așa mai departe. $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}$ $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}\}}}\right]$ $t_{j}$ $b_{i}$ $t_{i}$ $b_{i}$ $\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]\geq 0$ $U_{i}\geq U_{j}$

Utilizare în publicitatea online

O licitație VCG este folosită pentru a vinde spații publicitare pe site-uri de internet. În special, acest model de licitație este folosit de Facebook [7] , Google (în rețeaua sa parteneră) [8] și Yandex (pe pagina cu rezultatele căutării) [9] . Un alt model popular de vânzare a spațiului publicitar este licitația generalizată la prețul doi.

Lăsați în locurile blocului de anunțuri . Mai multe reclame concurează pentru aceste locuri. În modelul de plată pe clic , parametrii importanți ai anunțurilor concurente sunt sumele licitate și probabilitățile de clic ale acestora. $K$ ${b_{i}}$ ${p_{i}}$

Valoarea unui candidat în acest model este dată de funcția . Sunt afișate anunțurile cu cea mai mare valoare . Pentru al-lea jucător avem . $V(b,p)=b\cdot p$ $K$ $i$ $V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}$

Sunt posibile versiuni mai complexe ale funcției de valoare , o cerință importantă pentru această funcție este monotonitatea în ceea ce privește rata . $V$ $b$

Regulile unei licitații VCG pentru o anumită funcție de valoare și locuri într-un bloc de anunțuri sunt următoarele: trebuie să selectați anunțurile cu maximum până la și de la al -lea jucător luați atât de mulți bani pe clic încât valoarea este mai mică decât valoarea licitației sale inițiale exact cu suma în care ar scădea valoarea totală a jucătorilor afișați dacă jucătorul nu ar participa la licitație. $V(b,p)$ $K$ $K$ $V$ $i$ $c_{i}$ $V(c_{i},p_{i})$ $V(b_{i},p_{i})$ $i$

Luați în considerare cazul în care toate pozițiile sunt la fel de bune, adică probabilitățile de clicuri pe anunțuri nu depind de poziție.

Apoi, pentru cazul a trei locuri ( ) pentru a calcula costul pe clic al primului anunț , trebuie să rezolvați ecuația: $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})$

Cei doi termeni din această ecuație se anulează pentru a da: $V(c_{1},p_{1})=V(b_{4},p_{4}).$

Adică, pentru a calcula CPC-ul primului anunț, trebuie să-i reduceți suma licitată, astfel încât valoarea acesteia să scadă la valoarea primului jucător neafișat (în acest caz, al 4-lea anunț).

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

O afirmație similară este valabilă pentru al 2-lea și al 3-lea jucător:

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

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

Astfel, dacă probabilitățile de clic ale anunțurilor din licitație sunt egale ( scorurile CTR sunt aceleași), iar sumele licitate ale acestora sunt 10, 7, 5, 2, atunci primele trei vor merge la afișare și toți vor plăti 2 - pretul celui de-al 4-lea anunt.

În cazul în care licitația VCG coincide cu a doua licitație de preț. $K=1$

Într-o licitație, atât jucătorii care sunt dispuși să plătească ruble pe clic (cu o valoare de ) cât și jucătorii care sunt dispuși să plătească ruble pe afișare pot fi amestecați, atunci valoarea lor este egală . Algoritmul de calcul al amnistiei ofertei expuse pentru o impresie se obține din formule similare. $b$ $V=b\cdot p$ $A$ $V(A)=A$ $A$

Proprietatea de veridicitate a licitației (veritate) a unei licitații VCG în cazul publicității online înseamnă următoarele: pentru a rezolva problema maximizării profitului său, agentul de publicitate trebuie să liciteze astfel încât, dacă prețul dedus ar fi exact egal cu prețul stabilit. , agentul de publicitate ar primi profit zero din media clicurilor. Pentru cazul în care agentul de publicitate dorește să obțină profit cu un ROI peste o anumită valoare specificată, trebuie să stabilească suma licitată minimă la care este atins rentabilitatea investiției de care are nevoie. Atât cu cât și fără plafon pentru ROI, pariul optim nu depinde de pariurile altor jucători.

Atunci când un agent de publicitate, pe lângă limita ROI, are un buget fix de publicitate pe unitatea de timp și această limită nu este fictivă, ci atinsă în mod regulat, atunci algoritmul său de stabilire a ofertei optime (maximizarea profitului) într-o licitație VCG nu mai are o descriere simplă.

De asemenea, algoritmul de calculare a ratei optime este, de asemenea, complex și depinde de ratele concurenților, când nu profitul este maximizat, ci o combinație de cifra de afaceri și profit.

Cazul de clicabilitate diferită a locurilor

Luați în considerare cazul în care probabilitățile de a face clic pe un anunț depind de locație. Fie probabilitatea unui clic pe locurile 1, 2, 3 pentru anunț să fie egală cu , , , respectiv , adică există factori mai mici decât 1 care determină corecțiile multiplicative ale probabilității inițiale de clic. Să le numim poziții de clic. Fără a pierde generalitatea, să luăm în considerare cazul când pozițiile sunt aranjate în ordinea descrescătoare a clicabilității, adică . Ecuația pentru determinarea costului pe clic al primului anunț ar fi: $i$ $x_{1}\cdot p_{i)$ $x_{2}\cdot p_{i)$ $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})$

Înlocuind obținem: $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})$

Astfel, suma licitată pentru primul este redusă suficient pentru ca valoarea acesteia să devină egală cu media ponderată a valorilor reclamelor afișate mai jos și a unui anunț invizibil. Ponderile din această medie sunt determinate de posibilitatea de a face clic pe poziții. $V(c_{1},p_{1})$

Link -uri

↑ von Ahn, Luis Sponsored Search (PDF) (link nu este disponibil) . 15–396: Note de curs Știința Web-ului . Universitatea Carnegie Mellon (13 octombrie 2011). Consultat la 13 aprilie 2015. Arhivat din original pe 6 martie 2015. (nedefinit)
↑ Vickrey, William. Contraspeculații, licitații și licitații competitive sigilate // The Journal of Finance : jurnal. - 1961. - Vol. 16 , nr. 1 . - P. 8-37 . - doi : 10.1111/j.1540-6261.1961.tb02789.x .
↑ Clarke, E. Multipart Pricing of Public Goods (nespecificat) // Public Choice. - 1971. - T. 11 , nr 1 . - S. 17-33 . - doi : 10.1007/bf01726210 .
↑ Groves, T. Incentives in Teams // Econometrica : journal. - 1973. - Vol. 41 , nr. 4 . - P. 617-631 . - doi : 10.2307/1914085 .
↑ Douglas Brent West. Introducere în teoria grafurilor. — al 2-lea. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ Copie arhivată . Preluat la 4 august 2015. Arhivat din original la 23 septembrie 2015. (nedefinit)
↑ logo/fbfordevelopers . Preluat la 4 august 2015. Arhivat din original la 19 septembrie 2015. (nedefinit)
↑ Copie arhivată . Preluat la 4 august 2015. Arhivat din original la 9 ianuarie 2016. (nedefinit)
↑ Licitație nouă și clasament nou în Yandex.Direct - Blogul de tehnologie de publicitate . Consultat la 27 septembrie 2015. Arhivat din original la 12 septembrie 2015. (nedefinit)