Towary wspólne

Rozważmy teraz inny rodzaj gry, w której kraje ustalają swoją politykę kontrolowania zanieczyszczenia powietrza. Każdy kraj ma wybór: mogą zmniejszyć zanieczyszczenie kosztem -10 punktów za wdrożenie niezbędnych zmian lub mogą nadal zanieczyszczać, co daje im użyteczność netto -5 (w dodanych kosztach zdrowia itp.), a także dodaje -1 punktów każdemu innemu krajowi (ponieważ powietrze jest dzielone między kraje). Oczywiście dominującą strategią dla każdego kraju jest „kontynuowanie zanieczyszczania”, ale jeśli jest 100 krajów i każdy postępuje zgodnie z tą polityką, wówczas każdy kraj uzyskuje całkowitą użyteczność wynoszącą -104, podczas gdy jeśli każdy kraj zmniejszyłby zanieczyszczenie, każdy z nich miałby użyteczność -10. Ta sytuacja nazywana jest tragedią wspólnego dobra: jeśli nikt nie musi płacić za korzystanie ze wspólnego zasobu, może on zostać wykorzystany w sposób, który prowadzi do niższej ogólnej użyteczności dla wszystkich agentów. Jest to podobne do dylematu więźnia: istnieje inne rozwiązanie gry, które jest lepsze dla wszystkich stron, ale wydaje się, że racjonalni agenci nie mogą znaleźć takiego rozwiązania w obecnej grze. Jednym ze sposobów radzenia sobie z tragedią wspólnego dobra jest zmiana mechanizmu na taki, który obciąża każdego agenta za korzystanie z tego wspólnego. Mówiąc bardziej ogólnie, musimy zapewnić, że wszystkie efekty zewnętrzne – wpływy na globalną użyteczność, które nie są rozpoznawane w transakcjach poszczególnych agentów – są jasno określone. Prawidłowe ustalenie cen to trudna część. Podejście to sprowadza się do stworzenia mechanizmu, w którym każdy agent jest faktycznie wymagany do maksymalizacji globalnej użyteczności, ale może to zrobić, podejmując lokalną decyzję. W tym przykładzie podatek węglowy byłby przykładem mechanizmu, który pobiera opłaty za korzystanie z dóbr wspólnych w sposób, który, jeśli zostanie dobrze wdrożony, maksymalizuje globalną użyteczność.

Okazuje się, że istnieje konstrukcja mechanizmu, znana jako mechanizm Vickrey-Clarke-Groves lub VCG, który ma dwie korzystne właściwości. Po pierwsze, jest to maksymalizacja użyteczności – to znaczy maksymalizuje użyteczność globalną, która jest sumą użyteczności dla wszystkich stron, Σ_iv_i. Po drugie, mechanizm polega na ujawnianiu prawdy – dominującą strategią wszystkich agentów jest ujawnianie ich prawdziwej wartości. Nie muszą angażować się w skomplikowane kalkulacje licytacji strategicznych. Podamy przykład wykorzystując problem alokacji niektórych dóbr wspólnych. Załóżmy, że miasto zdecyduje, że chce zainstalować bezpłatne bezprzewodowe urządzenia nadawczo-odbiorcze do Internetu. Jednak liczba dostępnych nadajników-odbiorników jest mniejsza niż liczba dzielnic, które ich potrzebują. Miasto chce zmaksymalizować globalną użyteczność, ale jeśli powie każdej radzie sąsiedzkiej: „Ile cenisz darmowy nadajnik-odbiornik (a przy okazji oddamy go stronom, które cenią je najbardziej)?” wtedy każda dzielnica będzie miała motywację do zgłoszenia bardzo wysokiej wartości. Mechanizm VCG zniechęca do tej sztuczki i daje im motywację do zgłaszania ich prawdziwej wartości. Działa w następujący sposób:

1. Centrum prosi każdego agenta o zgłoszenie wartości przedmiotu, v_i.
2. Centrum przydziela towary do zestawu zwycięzców,W, aby zmaksymalizować Σ_iεW v_i.
3. Centrum oblicza dla każdego zwycięskiego agenta, jaką stratę spowodowała jego indywidualna obecność w grze u przegranych (z których każdy otrzymał 0 użyteczności, ale mógłby otrzymać v_j, gdyby był zwycięzcą).
4. Każdy zwycięski agent płaci następnie do centrum podatek równy tej stracie.

Załóżmy na przykład, że dostępne są 3 transceivery i 5 licytujących, którzy licytują 100, 50, 40, 20 i 10. Zatem zestaw 3 zwycięzców, W, to ci, którzy licytują 100, 50 i 40, a globalna użyteczność od przydzielenia tych dóbr wynosi 190. W przypadku każdego zwycięzcy, gdyby nie był w grze, zwycięzcą byłaby oferta 20. W ten sposób każdy zwycięzca płaci do centrum podatek w wysokości 20. Wszyscy zwycięzcy powinni być szczęśliwi, ponieważ płacą podatek niższy niż ich wartość, a wszyscy przegrani są tak szczęśliwi, jak tylko mogą, ponieważ wyceniają towary mniej niż wymagany podatek. Dlatego mechanizm ujawnia prawdę. W tym przykładzie kluczowa wartość to 20; byłoby irracjonalne licytować powyżej 20, jeśli twoja prawdziwa wartość była w rzeczywistości poniżej 20 i na odwrót. Ponieważ kluczową wartością może być dowolna (w zależności od innych oferentów), oznacza to, że licytowanie czegokolwiek innego niż Twoja prawdziwa wartość jest zawsze irracjonalne. Mechanizm VCG jest bardzo ogólny i można go zastosować do wszelkiego rodzaju gier, nie tylko aukcji, z lekkim uogólnieniem opisanego powyżej mechanizmu. Na przykład w aukcji kombinatorycznej dostępnych jest wiele różnych przedmiotów, a każdy licytujący może złożyć wiele ofert, każda na podzbiór przedmiotów. Na przykład w licytacji działek jeden oferent może chcieć wybrać działkę X lub działkę Y, ale nie obie; inny może chcieć dowolnych trzech sąsiadujących działek i tak dalej. Mechanizm VCG można wykorzystać do znalezienia optymalnego wyniku, chociaż przy 2^N podzbiorach N dóbr, z którymi trzeba się zmagać, obliczenie optymalnego wyniku jest NPkompletne. Z kilkoma zastrzeżeniami mechanizm VCG jest wyjątkowy: każdy inny optymalny mechanizm jest zasadniczo równoważny.