Det huvudsakliga problemet i algoritmisk mekanism design är att slå samman de incitament begränsningar som påtvingas av själviskt beteende med de algoritmiska begränsningar som införs av beräkningsförmåga. Detta fält motiveras av konstaterandet att den främsta metoden för att utforma incitamentskompatibla mekanismer, nämligen Vickrey, Clarke och Groves, och den centrala metoden för att kringgå beräkningshinder, dvs. approximativa algoritmer, är i grunden oförenliga: naturliga tillämpningar av VCG-metoden för en approximationsalgoritm ger inte någon incitamentskompatibel mekanism. Vi överväger att lätta på desideratum för (i efterhand) stimulanskompatibilitet (IC) till Bayesian incitamentkompatibilitet (BIC), där sanningsberättande är en Bayes-Nash jämvikt (standardbegreppet om incitamentkompatibilitet i ekonomi). För välfärdsmaximering i enkelparameter agentinställningar, ger vi en allmän black-box minskning som förvandlar alla approximationsalgoritm till en Bayesian incitament kompatibel mekanism med i huvudsak samma 1 approximationsfaktor. Med andra ord, för en stor relevant klass av problem och lätt avslappning av standard (i datavetenskap) lösning koncept, vi helt lösa det centrala problemet i algoritm mekanism design. 1 Mer specifikt får vi en FPTAS: för alla vi tar en β-tillnärmning algoritm och ge en BIC (1 +  på) β-tillnärmningsmekanism. Denna (1 +  på) faktor härrör från statistiska metoder som verkar nödvändiga för en minskning av svarta lådor.
Minskningar från mekanismdesign till algoritmdesign i Bayesian inställningen studerades först av Hartline och Lucier REF, som visade att varje approximationsalgoritm för en enparameter social välfärd problem kan omvandlas till en Bayesian incitament kompatibel mekanism med godtyckligt liten förlust i förväntade prestanda.
Bayesian Algorithmic Mechanism Design
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}