Licitație Vickrey

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 3 octombrie 2018; verificările necesită 11 modificări .

Licitația Vickrey este un algoritm de licitație închisă cu o rundă (ai cărui participanți nu se cunosc reciproc ofertele), în care participantul cu cea mai mare ofertă primește dreptul de a cumpăra, dar achiziția se face la a doua ofertă maximă.

Licitația a fost propusă de William Vickrey . Acest tip de licitație este similar din punct de vedere strategic cu licitația engleză , stimulând ofertanții să liciteze pentru valoarea reală a articolului.

Licitațiile Vickrey sunt bine studiate în literatura economică. O piață în care sunt foarte utilizate este colecția de timbre . Sistemul de licitație eBay este, de asemenea, similar, dar nu identic, cu licitația Vickrey. O versiune ușor generalizată a licitației Vickrey, numită licitație generalizată la al doilea preț , diferită de mecanismul VCG , este utilizată în sistemele de publicitate online Google , Yahoo [1] [2] și Yandex .

Generalizări

Articolul original al lui Vickrey se ocupa doar de licitațiile pentru vânzarea de bunuri simple, indivizibile. În acest caz, condițiile licitației Vickrey și licitației închise cu al doilea preț sunt echivalente.

Licitație cu preț uniform

În cazul mai multor articole identice (sau divizibile) vândute într-o singură licitație, generalizarea evidentă este de a vinde articolul tuturor ofertanților câștigători la prețul cel mai mare al ofertelor nesatisfăcute. Această generalizare este cunoscută sub denumirea de licitație cu preț uniform. Acesta din urmă stimulează participanții să liciteze în funcție de valoarea lor reală numai atunci când fiecărui jucător îi este permis să cumpere un singur articol. Dacă este posibil să se plaseze oferte pentru mai multe bunuri, proprietatea de optimitate a ofertelor adevărate nu este în general satisfăcută.

Mecanism Vickrey-Clark-Groves (licitație VCG)

O generalizare a licitației Vickrey la vânzarea de mai multe articole, menținând în același timp stimulente pentru licitarea echitabilă, este cunoscută sub numele de mecanismul Vickrey-Clarke-Groves (VCG). Ideea din spatele unei licitații VCG este că fiecare ofertant plătește un preț în funcție de modul în care participarea sa îi afectează pe toți ceilalți ofertanți. Și anume, fiecare jucător plătește la finalul licitației o sumă egală cu valoarea bunurilor pierdute de către alți jucători din cauza faptului că acest jucător participă la licitație.

De exemplu, să presupunem că vrem să scoatem la licitație două mere cu trei ofertanți.

Participantul A vrea un măr și licita 5 USD.
Participantul B dorește și un măr și este dispus să plătească 2 USD.
Participantul C pretinde două mere și intenționează să plătească 6 USD pentru ambele, dar nu este dispus să cumpere un măr fără celălalt.

În primul rând, determinăm câștigătorii prin maximizarea mizei: merele merg către participanții A și B (deoarece, după ce a pierdut un măr în fața participantului A , C nu pretinde al doilea).

În al doilea rând, pentru a determina plățile, luăm în considerare ce s-ar întâmpla dacă câștigătorul nu ar participa la licitație.

Plata câștigătorului A : B primește mărul pariând 2 dolari. Dacă A nu ar fi prezent, C ar câștiga ambele mere și ar plăti 6 USD pentru ele . Deci A plătește diferența dintre prețul lui C pentru ambele mere și prețul lui B pentru unul dintre ele: 6 $-2 $ = 4 $.
Plata câștigătorului B : A primește mărul pariând 5 USD, iar C nu primește nimic. Fără B , C ar fi primit ambele mere pentru 6 USD (deoarece 6 USD pentru două mere depășește oferta de 5 USD a lui A în absența altor participanți) . Prin urmare , B plătește diferența $6-$5 = $1.

Mecanismul Vickrey-Clark-Groves (licitație VCG) în publicitatea online

O licitație VCG este folosită pentru a vinde spații publicitare pe site-uri de internet. În special, Yandex [3] , Facebook [4] și Google (în rețeaua lor de parteneri) [5] folosesc acest model de licitație . 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_{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})$

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.

Cu licitația VCG este aceeași 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 pe internet înseamnă următoarele: pentru a rezolva problema maximizării profitului, agentul de publicitate trebuie să liciteze astfel încât, dacă prețul practicat a fost 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_{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})$

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

Adică, suma licitată pentru primul este redusă, astfel încât valoarea acesteia să devină egală cu media ponderată a valorilor reclamelor de 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})$

Proprietăți

Stimularea dezvăluirii notelor adevărate

Într-o licitație de licitație independentă Vickrey, fiecare participant maximizează utilitatea precizând adevărata valoare individuală a articolului. Cu alte cuvinte, strategia de a anunța evaluări adevărate este dominantă pentru licitațiile Vickrey unice.

Eficiența alocării resurselor

O singură licitație Vickrey este eficientă (câștigătorul este ofertantul a cărui estimare individuală a valorii articolului este cea mai mare) în cazul cel mai general; astfel, este modelul de pornire pe baza căruia poate fi evaluată eficiența alocării resurselor în alte modele de licitație.

Restricții

Cu toate avantajele, licitația Vickrey are o serie de limitări:

Nu permite cercetarea prețurilor (cumpărătorii să afle prețurile pieței dacă nu sunt siguri de evaluarea lor) decât printr-o serie de licitații succesive.
Vânzătorii pot folosi „ratele inactiv” pentru a-și crește profiturile.
Într-o serie de licitații Vickrey succesive, strategia ofertanților care își declară adevăratele evaluări nu mai este dominantă.

Mecanismul VCG are limitări suplimentare:

Posibilitatea de a pierde ofertele participanților la licitație.
Vulnerabilitatea cumpărătorilor din cauza posibilității de „tarife false” din partea vânzătorului.
Lipsa de maximizare a veniturilor vânzătorului - acesta din urmă se poate dovedi chiar egal cu zero la sfârșitul licitației VCG. Dacă scopul licitației este de a maximiza profiturile vânzătorului și nu doar alocarea eficientă a resurselor în rândul cumpărătorilor, atunci este posibil ca VCG să nu fie o alegere bună.
Venitul vânzătorului nu este monoton în raport cu mărimea tarifelor.

Nemonotonitatea veniturilor vânzătorului în raport cu rata poate fi demonstrată prin următorul exemplu.

Luați în considerare trei participanți A , B și C și doi produse identice Y și Z.

A pretinde atât bunuri și licita 2 USD pentru suma Y și Z .
Atât B , cât și C au oferit 2 USD pentru oricare dintre articole (2 USD pentru Y sau Z ).

Ca rezultat, Y și Z merg la B și C , dar la un cost de $0, după cum puteți vedea eliminând succesiv B și C .

În plus, dacă C ar fi licitat 0 USD în loc de 2 USD, atunci vânzătorul ar fi primit 2 USD în loc de 0 USD. Deoarece veniturile vânzătorului pot crește și cu o creștere a ratelor B și C , se dovedește a fi nemonoton.

Vezi și

Note

↑ Benjamin Edelman, Michael Ostrovsky și Michael Schwarz : „Reclamă pe internet și licitația generalizată la al doilea preț: vânzarea de miliarde de dolari în valoare de cuvinte cheie”. American Economic Review 97(1), 2007 pp. 242-259.
↑ Hal R. Varian: „Position Auctions”. Jurnalul Internațional de Organizare Industrială, 2006, doi:10.1016/j.ijindorg.2006.10.002.
↑ Cum funcționează licitația în direct (rusă) . Arhivat din original pe 12 februarie 2018. Preluat la 12 februarie 2018.
↑ logo/fbfordevelopers . Consultat la 30 iulie 2015. Arhivat din original la 19 septembrie 2015. (nedefinit)
↑ Copie arhivată . Consultat la 30 iulie 2015. Arhivat din original la 9 ianuarie 2016. (nedefinit)

Literatură

W. Vickrey. Contraspeculații, licitații și licitații competitive sigilate. Universitatea Columbia. 1961
von Ahn, Luis (30.09.2008).„Licitații” (PDF). 15-396: Știința nodurilor de curs web. Universitatea Carnegie Mellon. https://web.archive.org/web/20081008174053/http://scienceoftheweb.org/15-396/lectures/lecture09.pdf . Consultat pe 2008-11-06.