Mechanizm Vickreya-Clarke’a-Grovesa

Mechanizm Vickreya-Clarke’a-Grovesa (VCG) – uogólnienie aukcji Vickreya-Clarke’a-Grovesa do postaci rodziny uniwersalnych procedur wyboru społecznie optymalnych rozwiązań w teorii gier. Strukturyzuje sytuację tak, aby dominującą strategią dla każdego uczestnika było wierne i prawdomówne ujawnienie prywatnych preferencji, co pozwala na dokonanie utylitarnie trafnej decyzji.

Choć udowodniono, że nie jest wystarczająco odporny, aby mógł być powszechnie stosowany w zrównoważony budżetowo sposób, znalazł szereg specyficznych wykorzystań, oraz zainspirował dalsze badania.

Mechanizm rozwinął się od oryginalnego pomysłu aukcji w sekwencji publikacji Williama Vickreya o systemie Vickreya, a następnie Edwarda Clarke’a i Theodore’a Grovesa w latach 1961–1973. Jego opracowanie było jednym z bodźców inicjujących rozważania nad podobnymi rozwiązaniami w nurcie projektowania mechanizmów. Vickrey (1997), oraz Hurwicz, Maskin i Myerson (2007) zostali uhonorowani za prace w tej dziedzinie „ekonomicznymi Noblami”.

Opis formalny

Dla $n$ uczestników, którzy wybierają rozwiązania ze zbioru $X$ i wartościują je przy pomocy indywidualnych funkcji oceny korzyści $v_{i}(x),$ a następnie deklarują tę wycenę – prawdomównie lub nie – wybierane jest rozwiązanie, które maksymalizuje sumę korzyści wszystkich uczestników:

$x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}v_{i}(x).$

Jeśli uczestnicy są prawdomówni, a rozwiązanie okazuje się tańsze od ogólnej korzyści jakie przynosi, to jest optymalne (w sensie utylitarnym lub Pareto) i warte realizacji. W praktyce w samolubnym interesie każdego uczestnika może leżeć ukrycie prawdziwej wyceny, aby zredukować własne koszty (efekt gapowicza). Może to niesprawiedliwie obciążać pozostałe osoby, lub skutkować całkowitym zaniechaniem realizacji społecznie wartościowego pomysłu.

Mechanizm VCG wprowadza dodatkowe indywidualne rabaty lub dopłaty, które mają przeciwdziałać temu problemowi. Cena jaką płaci każdy uczestnik to:

$p_{i}=\sum _{m\neq i}v_{m}(x^{opt})-h_{i}(v_{-i}),$

gdzie pierwsza suma reprezentuje wartość jaką uzyskują pozostałe osoby przy jego udziale, a funkcja $h_{i}$ jest proporcjonalna do poziomu tej wartości pod jego nieobecność.

Oznacza to, że rabat jest tym wyższy, im bardziej udział jednostki zbliża pozostałych uczestników $(m\neq i)$ do oszacowanego optimum. Z punktu widzenia każdego gracza $h_{i}$ jest stałą, która internalizuje efekty zewnętrzne jego decyzji i uniezależnia go od motywacji do oszukiwania. Dominującą strategią w takich warunkach jest aby każda osoba była prawdomówna.

Reguła Clarke’a

Ustalenie $h_{i}=0$ gwarantuje realizację projektu, wiąże się jednak z poważnym przepłaceniem. Clarke zaproponował regułę wyboru $h_{i},$ która minimalizuje ogólne transfery:

$h_{i}(v_{-i})=max_{x\in X}\sum _{m\neq i}v_{i}(x).$

Przykładowo, jeśli wyraża całą wartość społeczną jaką wnosi udział danej osoby:

$p_{i}=\sum _{m\neq i}v_{m}(x^{opt})-\sum _{m\neq i}v_{m}(x_{-i}^{opt}),$

to płacą tylko osoby, których obecność przeważa głosowanie na rzecz korzystnego rozwiązania, i najwyżej tyle, na ile same je sobie cenią. Jest to podstawą szczegółowych propozycji politycznych, takich jak podatek Clarke’a mający ułatwić finansowanie dóbr publicznych. Taka funkcja $h_{i}$ nie gwarantuje jednak, że organizator i w tym przypadku nie będzie musiał dopłacić do projektu (jest to wręcz bardzo prawdopodobne).