En av de grundläggande frågorna i Algoritmisk Mechanism Design är om det finns en inneboende konflikt mellan sanning och beräkningsförmåga: i synnerhet, om polynom-tid sanningsenliga mekanismer för kombinatoriska auktioner är bevisligen svagare i fråga om approximation förhållande än icke-sanning. Denna fråga besvarades helt nyligen för allmänt sanningsenliga mekanismer för kombinatoriska auktioner [4] och till och med för mekanismer för sanningsenlig förväntan [12]. Båda dessa resultat grundar sig dock på informationsteoretiska argument för värderingar som ges av ett värde oracle, och lämnar möjligheten öppen för sanningsenliga mekanismer i polynomtid för kortfattat beskrivna värderingsklasser. Detta papper är den första att bevisa beräkning hårdhet resultat för sanningsenliga mekanismer för kombinatoriska auktioner med kortfattat beskrivna värderingar. Vi bevisar att det finns en klass av koncis representerade submodulära värderingar för vilka ingen deterministisk sanningsenlig mekanism ger en m 1/2− - approximation för en konstant > 0, om inte N P = RP (m betecknar antalet objekt). Dessutom bevisar vi att även sanningsenliga-in-expectation mekanismer inte kan approxima kombinatoriska auktioner med vissa kortfattat beskrivna submodulära värderingar bättre än inom n γ, där n är antalet budgivare och γ > 0 några absolut konstant, om inte N P / poly. Dessutom bevisar vi beräkningshårdhet resultat för två relaterade problem.
På samma sätt, en stark icke-konstant lägre gräns bevisas även för randomiserade polynom tid sanningsenliga i förväntan mekanismer för CAs med koncist representerade submodulära värderingar REF.
The computational complexity of truthfulness in combinatorial auctions
{'venue': "EC '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}