Abstrakt. Black-box transformationer har studerats ingående i algoritmisk mekanism design som ett generiskt verktyg för att omvandla algoritmer till sanningsenliga mekanismer utan att försämra approximationsgarantierna. Medan sådana omvandlingar har utformats för en mängd olika inställningar, Chawla et al. visade att det inte finns någon helt allmän omvandling av svarta lådor för enparametermiljöer. I det här dokumentet undersöker vi potentialen och gränserna för Black-box transformationer i priorfree (dvs icke-bayesian) inställning i nedstängda enparameter miljöer, en stor och viktig klass av miljöer i mekanismdesign. På den positiva sidan visar vi att en sådan omvandling kan bevara en konstant bråkdel av välfärden vid varje insats om agenternas privata värderingar tar på sig ett konstant antal värden som är långt ifrån varandra, medan vi på den negativa sidan visar att denna uppgift inte är möjlig för allmänna privata värderingar.
Suksompong REF tar hänsyn till fallet med nedstängda enparametermiljöer, och visar också gränser för effekten av minskning av svarta lådor.
On Black-Box Transformations in Downward-Closed Environments
{'venue': 'Theory of Computing Systems, 63(6):1207-1227 (2019)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}