Aukcja z odroczonym odbiorem
.jpg)
Aukcja z odroczoną akceptacją (DAA) to aukcja , w której alokacja jest wybierana poprzez wielokrotne odrzucanie najmniej atrakcyjnych ofert. Jest to prawdomówny mechanizm o strategicznych właściwościach, które sprawiają, że szczególnie nadaje się do złożonych aukcji, takich jak aukcja relokacji widma radiowego .
Przykład
Załóżmy, że rząd chce sprzedać prawa do transmisji na dwóch obszarach: północnym i południowym. Trzech agentów konkuruje o te prawa:
- Alice potrzebuje obu obszarów i wycenia je (łącznie) na 3 miliony dolarów.
- Bob potrzebuje tylko Północy i wycenia ją na milion dolarów.
- Carl potrzebuje tylko Południa i wycenia je na milion dolarów.
Rząd chce maksymalizować dobrobyt społeczny. W tym przypadku możliwe są dwie alokacje: albo przyznanie wszystkich praw Alicji (dobrobyt = 3), albo przyznanie północy Bobowi, a południa Karolowi (dobrobyt = 2). Ponieważ wyceny są prywatną informacją agentów, rząd musi użyć prawdziwego mechanizmu , aby skłonić agentów do ujawnienia ich prawdziwych wycen. Porównujemy dwa rodzaje mechanizmów prawdy.
Rozwiązanie Vickreya-Clarke'a-Grovesa
Vickrey -Clarke-Groves (VCG) znajduje społecznie optymalną alokację, która ma dać Alice oba obszary. Alicja powinna zapłacić cenę określoną przez efekty zewnętrzne, jakie nakłada na innych agentów. W tym przypadku Alice płaci 2 miliony dolarów, ponieważ bez niej dobrobyt Boba i Carla wyniósłby 2 miliony dolarów. Bob i Carl nic nie otrzymują i nic nie płacą.
Rozwiązanie aukcji z odroczoną akceptacją
Aukcja z odroczoną akceptacją iteracyjnie odrzuca agenta o najniższej wartości, który można odrzucić przy zachowaniu optymalnego zestawu aktywnych agentów. Tak więc Carl zostaje odrzucony jako pierwszy, a potem Bob. Alice pozostaje i zostaje zaakceptowana. Płaci wartość progową, która wynosi 1 mln USD.
Oba typy aukcji są zgodne z prawdą — żaden pojedynczy agent nie mógłby zyskać, zgłaszając inną wartość. Różnią się jednak tym, kiedy agenci mogą tworzyć koalicje . Załóżmy, że Bob i Karol wspólnie podnoszą swoją ofertę do 4 mln USD. Teraz aukcja VCG zaakceptuje Boba i Carla i obciąży każdego z nich ceną równą 0 (ponieważ każdy z nich osobno nie ma wpływu na przydział Alicji)! W przeciwieństwie do tego DAA odrzuci Alice, a następnie zaakceptuje Boba i Carla i obciąży każdego z nich jego ceną progową, która wynosi 3 miliony dolarów - więc nie zyskują nic na swoim błędnym zgłoszeniu (w rzeczywistości tracą 2 miliony dolarów).
Zobacz też
Wyniki aukcji z odroczoną akceptacją zostały przeanalizowane przez Dütting i in. w 2014 r. Zastosowanie tego pomysłu w podwójnej aukcji zostało nakreślone przez ówczesnych informatyków ze Stanford, w tym Tima Roughgardena w 2014 r. w tym samym roku.