Myersons seminära arbete ger en beräkningseffektiv intäktsoptimal auktion för att sälja en vara till flera budgivare [17]. Att generalisera detta arbete till att sälja flera objekt på en gång har varit en central fråga i ekonomi och algoritmisk spelteori, men dess komplexitet har förblivit dåligt förstådd. Vi besvarar denna fråga genom att visa att en intäktsoptimal auktion i multi-punktsinställningar inte kan hittas och genomföras beräkningsmässigt effektivt, om inte ZPP P #P. Detta gäller även för en enda additiv budgivare vars värden för objekten är självständigt fördelade på två rationella tal med rationell sannolikhet. Vårt resultat är mycket allmänt: vi visar att det är svårt att beräkna någon kodning av en optimal auktion av något format (direkt eller indirekt, sanningsenlig eller icke-sanning) som kan genomföras i förväntad polynom tid. I synnerhet, under välförstådda komplexitet-teoretiska antaganden, intäktsoptimering i mycket enkla multi-punktsinställningar kan endast dras nytta av approximation. Vi noterar att vår hårdhet resultat gäller randomiserade mekanismer i en mycket enkel inställning, och är inte en artefakt att införa kombinatoriska struktur till problemet genom att tillåta korrelation mellan objekt värden, införa kombinatoriska värderingar, eller kräva mekanismen att vara deterministiska (vars struktur är lätt kombinatoriska). Vårt bevis möjliggörs genom en flödestolkning av lösningarna i ett exponentiellt linjärt program för intäktsmaximering med ytterligare en supermodulalitetsbegränsning.
Ett annat exempel är Daskalakis et al. Ref överväga en enkel-bidder multiitem (och därmed multi-parameter) inställning och bevisa att det är #P-hård att beräkna en beskrivning av intäktsmaximering incitament-kompatibel mekanism.
The Complexity of Optimal Mechanism Design
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}