Vi anser att problemet med att utforma en intäktsmaximering auktion för en enda post, när värdena för budgivarna hämtas från en korrelerad distribution. Vi observerar att det finns en algoritm som finner den optimala randomiserade mekanismen som löper i tiden polynom i storleken på stödet. Vi utnyttjar detta resultat för att visa att i den oraklemodell som införts av Ronen och Saberi [FOCS'02] finns det en polynomisk tid sanningsenlig i förväntan mekanism som ger en (1,5 + )-uppskattning till de intäkter som kan uppnås genom en optimal sanningsenlig-in-förväntning mekanism, och en polynom tid deterministisk sanningsenlig mekanism som garanterar 5 3 approximation till de intäkter som kan uppnås genom en optimal deterministisk sanningsenlig mekanism. Vi visar att - approximationsmekanismen ger samma approximationsgrad även när det gäller den optimala sanningsenliga-in-expectationsmekanismen. Detta visar att skillnaden mellan sanningsenliga och deterministiska mekanismer är relativt liten. På vägen löser vi en öppen fråga om Mehta och Vazirani [EC'04]. Slutligen utvidgar vi en del av våra resultat till flerpunktsärendet och visar hur man beräknar de optimala mekanismerna för sanningsenlig förväntan för budgivare med mer komplexa värderingar.
Å andra sidan visade för randomiserade mekanismer REF att optimal kan beräknas i tid polynom i storleken på distributionens stöd.
Optimal auctions with correlated bidders are easy
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}