Elhalasztott elfogadási aukció - Deferred-acceptance auction
.jpg)
A halasztott elfogadási aukció (DAA) egy olyan aukció , amelyben az allokációt úgy választják meg, hogy többször elutasítják a legkevésbé vonzó ajánlatokat. Ez egy hiteles mechanizmus stratégiai tulajdonságokkal, amelyek különösen alkalmassá teszik olyan összetett aukciókra, mint a rádióspektrum -átcsoportosítási aukció.
Példa
Tegyük fel, hogy a kormány két területen kívánja eladni a sugárzási jogokat: Északon és Délen. Három ügynök versenyez ezekért a jogokért:
- Alice -nek mindkét területre szüksége van, és ezeket (együtt) 3 millió dollárra becsüli.
- Bobnak csak Északra van szüksége, és 1 millió dollárra becsüli.
- Carlnak csak a Délre van szüksége, és 1 millió dollárra becsüli.
A kormány maximalizálni kívánja a szociális jólétet. Ebben az esetben két megvalósítható elosztás létezik: vagy minden jogot megad Alice -nek (jólét = 3), vagy az északi rész Bobnak, a déli pedig Carl -nak (jólét = 2). Mivel az értékelések az ügynökök privát adatai, a kormánynak hiteles mechanizmust kell alkalmaznia annak érdekében, hogy rábírja az ügynököket, hogy felfedjék valódi értékeiket. Kétféle igaz mechanizmust hasonlítunk össze.
Vickrey – Clarke – Groves megoldás
A Vickrey – Clarke – Groves (VCG) algoritmus megtalálja a társadalmilag optimális elosztást, vagyis mindkét területet Alice-nek kell adni. Alice -nek olyan árat kell fizetnie, amelyet az externáliák határoznak meg a többi ügynökkel szemben. Ebben az esetben Alice 2 millió dollárt fizet, hiszen nélküle Bob és Carl jóléte 2 millió dollár lett volna. Bob és Carl nem kapnak semmit és nem fizetnek semmit.
Hasonló eredmény valósítható meg azonnali elfogadó (vagy előre kapzsi ) árveréssel. Ez az aukció iteratívan elfogadja a legmagasabb értékű ügynököt, amely még megvalósítható, és felszámítja a küszöbértékeket (a legkisebb ajánlatot, amelyet a nyeréshez kellett volna tenniük). Ebben az esetben először Alice -t választják ki, így Bob és Carl már nem választhatók ki. Alice kifizeti a küszöbértékét, ami 1 millió dollár.
Késleltetett elfogadási aukciós megoldás
2. A halasztott elfogadási aukció iteratívan elutasítja a legalacsonyabb értékű ügynököt, amelyet el lehet utasítani, miközben megtartja az aktív hatóanyagok optimális készletét. Tehát először Carlt utasítják el, aztán Bobot. Alice marad, és elfogadják. Fizeti a küszöbértéket, amely 1 millió dollár.
Mindkét aukciós típus igaz - egyetlen ügynök sem nyerhet más érték bejelentésével. Különbségek vannak azonban abban az esetben, ha az ügynökök koalíciókat hozhatnak létre . Tegyük fel, hogy Bob és Carl együtt 4 millió dollárra emelik ajánlatukat. Most a VCG aukció elfogadja Bobot és Carlt, és mindegyiküknek 0 árat számít fel (mivel mindegyikük önmagában nincs hatással az Alice számára történő kiosztásra)! Ezzel szemben a DAA elutasítja Alice -t, majd elfogadja Bobot és Carlt, és mindegyiküknek felszámítja a küszöbárát, ami 3 millió dollár - tehát nem nyernek semmit a téves jelentésből (sőt, 2 millió dollárt veszítenek).
Lásd még
A halasztott elfogadási aukciók teljesítményét Paul Milgrom és Ilya Segal Stanford Egyetemi közgazdászok elemezték 2014-ben. Ennek az ötletnek a kettős aukciós környezetben történő alkalmazását vonták körbe az akkori Stanford informatikai kutatók, köztük Tim Roughgarden 2014-ben.