Aukce odloženého přijetí - Deferred-acceptance auction

A aukce s odloženým přijetím (DAA) je aukce ve kterém je alokace zvolena opakovaným odmítáním nejméně atraktivních nabídek. Je to pravdivý mechanismus se strategickými vlastnostmi, díky nimž je obzvláště vhodný pro komplexní aukce, jako je rádiové spektrum realokační aukce.[1]

Příklad

Předpokládejme, že vláda chce prodat vysílací práva ve dvou oblastech: severní a jižní. O tato práva soutěží tři agenti:

  • Alice potřebuje obě oblasti a oceňuje je (společně) jako 3 mil. USD.
  • Bob potřebuje pouze sever a hodnotí jej jako $ 1M.
  • Carl potřebuje pouze jih a hodnotí jej jako $ 1M.

Vláda chce maximalizovat sociální zabezpečení. V tomto případě existují dvě proveditelná alokace: buď udělit všechna práva Alici (sociální péče = 3), nebo udělit sever Bobovi a jižní Carlovi (sociální péče = 2). Vzhledem k tomu, že ocenění jsou soukromými informacemi agentů, musí vláda použít a pravdivý mechanismus s cílem přimět agenty, aby odhalili své skutečné ocenění. Porovnáváme dva typy pravdivých mechanismů.

Řešení Vickrey – Clarke – Groves

The Algoritmus Vickrey – Clarke – Groves (VCG) najde sociálně optimální alokaci, která má dát obě oblasti Alici. Alice by měla zaplatit cenu určenou externalitami, které ukládá ostatním agentům. V tomto případě Alice zaplatí 2 miliony dolarů, protože bez ní by blahobyt Boba a Carla byl 2 miliony dolarů. Bob a Carl nic nedostávají a nic neplatí.

Podobný výsledek lze provést prostřednictvím okamžité přijetí (nebo chamtivý dopředu) aukce. Tato aukce iterativně přijímá agenta s nejvyšší hodnotou, kterého je stále možné vybrat, a účtuje jim prahové platby (nejmenší nabídku, kterou měli učinit, aby vyhráli). V tomto případě je nejprve vybrána Alice, takže již nelze vybrat Boba a Carla. Alice zaplatí svou prahovou hodnotu, která je 1 milion USD.

Aukční řešení s odloženým přijetím

2. The aukce s odloženým přijetím iterativně odmítá agenta s nejnižší hodnotou, kterého lze odmítnout, při zachování optimální sady aktivních agentů. Nejprve je tedy odmítnut Carl, potom Bob. Alice zůstává a je přijata. Zaplatí prahovou hodnotu, která je 1 milion USD.

Oba typy aukcí jsou pravdivé - žádný jediný agent by nemohl získat tím, že by nahlásil jinou hodnotu. Liší se však, když se mohou agenti tvořit koalice. Předpokládejme, že Bob a Carl společně zvýší nabídku na 4 miliony USD. Nyní aukce VCG přijme Boba a Carla a každému z nich bude účtovat cenu 0 (protože každý z nich sám nemá žádný vliv na přidělení Alici)! Naproti tomu DAA odmítne Alici, poté přijme Boba a Carla a každému z nich naúčtuje jeho prahovou cenu, která je 3 miliony USD - takže ze svého nesprávného hlášení nic nezískají (ve skutečnosti ztratí 2 miliony USD).

Viz také

Výkon aukcí s odloženým přijetím byl analyzován pomocí Stanfordská Univerzita ekonomové Paul Milgrom a Ilya Segal v roce 2014.[2] Aplikace této myšlenky v a dvojitá aukce nastavení nastínili tehdejší vědci z oblasti počítačové vědy včetně Tim Roughgarden v roce 2014 téhož roku.[3]

Související články

Reference

  1. ^ Paul Milgrom a Ilya Segal (2014). „Aukce odloženého přijetí a realokace rádiového spektra“ (PDF). Citováno 8. srpna 2016.
  2. ^ Dütting, Paul; Gkatzelis, Vasilis; Roughgarden, Tim (2014). "Výkon aukcí s odloženým přijetím". Sborník z patnácté konference ACM o ekonomii a výpočtu - EC '14. p. 187. doi:10.1145/2600057.2602861. ISBN  9781450325653.
  3. ^ Dütting, Paul; Roughgarden, Tim; Talgam-Cohen, Inbal (2014). Modularita a chamtivost ve dvojitých aukcích. Sborník příspěvků z 15. konference o ekonomii a výpočtu (EC'14). 241–258. doi:10.1145/2600057.2602854. ISBN  9781450325653.