Mechanismus extrakce zisku - Profit extraction mechanism
v konstrukce mechanismu a teorie dražby, a mechanismus extrakce zisku (také zvaný extraktor zisku nebo extraktor příjmů) je pravdivý mechanismus jehož cílem je vyhrát předem stanovenou částku zisku, pokud je to možné.[1]:347
Extrakce zisku v aukci digitálního zboží
Zvažte a digitální aukce zboží ve kterém chce producent filmu rozhodnout o ceně, za kterou prodá kopie svého filmu. Možným přístupem je, aby se producent rozhodl o určitém výnosu, R, kterého chce dosáhnout. Poté R-zisk-extraktor funguje následujícím způsobem:
- Zeptejte se každého agenta, kolik je ochoten za film zaplatit.
- Pro každé celé číslo , nechť být počet agentů ochotných platit alespoň . Všimněte si, že se slabě zvyšuje s .
- Pokud existuje takhle , pak najděte největší takový (což se musí rovnat ), prodejte jim film agentům a účtovat každému takovému agentovi cenu ve výši .
- Pokud žádný takový existuje, aukce je zrušena a nejsou žádní vítězové.
Tohle je pravdivý mechanismus. Důkaz: Protože agenti mají jednoparametrický nástroj pravdivost je ekvivalentní monotónnost. Extraktor zisku je monotónní, protože:
- Pokud vítězný agent zvýší svoji nabídku, pak slabě se zvyšuje a agent je stále jedním z nejvyšší nabídky, takže stále vyhrává.
- Vítězný agent platí , což je přesně prahová cena - cena, pod kterou nabídka přestane být vítězem.
Odhad maximálního výnosu
Hlavní výzvou při použití aukce založené na extraktoru zisku je vybrat nejlepší hodnotu parametru . V ideálním případě bychom chtěli být maximálním výnosem, který lze získat z trhu. Tento maximální příjem však předem neznáme. Můžeme to zkusit odhadnout jedním z následujících způsobů:
- náhodně rozdělit uchazeče do dvou skupin, takže každý uchazeč má šanci 1/2 jít do každé skupiny. Nechť R1 je maximální příjem ve skupině 1 a R2 maximální příjem ve skupině 2. Spusťte R1-profit-extractor ve skupině 2 a R2-profit-extractor ve skupině 1.
Tento mechanismus zaručuje zisk nejméně 1/4 maximálního zisku. Varianta tohoto mechanismu rozděluje agenty na tři skupiny místo na dvě a dosahuje alespoň 1/3,25 maximálního zisku.[1]:348
2. Odhad konsensu:
- Vypočítejte maximální příjem v celé populaci; použít určitý proces náhodného zaokrouhlování, který zaručuje pravdivost výpočtu s vysokou pravděpodobností. Nechť R je odhadovaný výnos; spusťte R-profit-extraktor v celé populaci.
Tento mechanismus zaručuje v aukci digitálního zboží zisk minimálně 1/3,39 maximálního zisku.[1]:350
Extrakce zisku v dvojité aukci
Myšlenku vytěžování zisku lze zobecnit na libovolnou nástroj s jedním parametrem agenti. Zejména jej lze použít v a dvojitá aukce kde několik prodejců prodává jednu jednotku nějaké položky (s různými náklady) a několik kupujících chce nanejvýš jednu jednotku této položky (s různými oceněními). [2] Následující mechanismus je přibližný extraktor zisku:
- Objednávejte kupující sestupně a prodejci vzestupně.
- Najděte největší takhle .
- The kupující s vysokou hodnotou kupují zboží za cenu . The nízkonákladoví prodejci prodávají zboží za cenu .
Mechanismus je pravdivý - lze to dokázat pomocí argumentu monotónnosti podobného aukci digitálního zboží. Výnos dražebníka je , který se blíží požadovanému výnosu, když je dostatečně velký.
Kombinace tohoto extraktoru zisku s odhadem konsensu poskytuje pravdivý mechanismus dvojité aukce, který zaručuje zisk nejméně 1/3,75 maximálního zisku.
Dějiny
Mechanismus extrakce zisku je zvláštním případem a sdílení nákladů mechanismus.[3] Bylo adaptováno z literatury o sdílení nákladů na nastavení aukce.[4][5]
Reference
- ^ A b C Jason D. Hartline a Anna R. Karlin, „Maximalizace zisku při návrhu mechanismu“. Kapitola 13 v Vazirani, Vijay V.; Nisan, Noame; Roughgarden, Tim; Tardos, Éva (2007). Algoritmická teorie her (PDF). Cambridge, Velká Británie: Cambridge University Press. ISBN 0-521-87282-0.
- ^ Deshmukh, Kaustubh; Goldberg, Andrew V .; Hartline, Jason D .; Karlin, Anna R. (2002). "Pravdivé a konkurenceschopné dvojité aukce". Algoritmy - ESA 2002. Přednášky z informatiky. 2461. str. 361. doi:10.1007/3-540-45749-6_34. ISBN 978-3-540-44180-9.
- ^ Moulin, Hervé; Shenker, Scott (2001). "Strategické sdílení submodulárních nákladů: zůstatek rozpočtu versus efektivita". Ekonomická teorie. 18 (3): 511. CiteSeerX 10.1.1.25.4285. doi:10.1007 / pl00004200.
- ^ Andrew V. Goldberg, Jason D. Hartline (2003). „Konkurenceschopnost prostřednictvím konsensu“. Sborník čtrnáctého výročního sympózia ACM-SIAM o diskrétních algoritmech. SODA 03. Citováno 14. března 2016.
- ^ Fiat, Amos; Goldberg, Andrew V .; Hartline, Jason D .; Karlin, Anna R. (2002). "Konkurenční všeobecné aukce". Sborník z třináctého ročníku ACM symposia o teorii práce s počítači - STOC '02. str. 72. doi:10.1145/509907.509921. ISBN 1581134959.