Abstract-We ger en minskning från intäktsmaximering till välfärd maximering i flerdimensionella Bayesian auktioner med godtyckliga-eventuellt kombinatoriska-genomförbarhet begränsningar och oberoende budgivare med godtyckliga-eventuellt kombinatoriska-efterfrågan begränsningar, lämpligt utvidga Myersons singledimensionella resultat [21] till denna inställning. Vi visar också att varje genomförbar Bayesisk auktion, särskilt den inkomstoptimala en-kan genomföras som en distribution över virtuella VCG fördelningsregler. En virtuell VCG-fördelningsregel har följande enkla form: Varje budgivares typ t i omvandlas till en virtuell typ fi(ti), via en anbudsspecifik funktion. Sedan väljs den allokering som maximerar virtuell välfärd. Med hjälp av denna karakterisering visar vi hur man hittar och kör den intäktsoptimala auktionen med endast black-box tillgång till ett genomförande av VCG tilldelningsregeln. Vi generaliserar detta resultat till godtyckligt korrelerade budgivare och inför idén om en andra ordningens VCG-fördelningsregel. Våra resultat är beräkningseffektiva för alla flerdimensionella inställningar där budgivarna är additiva, eller effektivt kan kartläggas som additiva, även om genomförbarheten och efterfrågans begränsningar fortfarande kan vara godtyckliga kombinatoriska. I detta fall, våra mekanismer kör i tid polynom i antalet poster och det totala antalet budgivare typer, men inte typ profiler. Detta är polynom i antalet poster, antalet budgivare och kardinaliteten i stödet till varje budgivares värdefördelning. För generiska korrelerade distributioner är detta den naturliga beskrivningen av problemets komplexitet. Körtiden kan förbättras ytterligare till polynom i endast antalet objekt och antalet budgivare i postsymmetriska inställningar genom användning av tekniker från [15].
I REF, Cai et al. ge den optimala lösningen för en mycket mer allmän miljö där budgivare är additiva, och med (eventuellt) godtyckliga genomförbarhetsbegränsningar, genom att minska intäktsoptimeringen till välfärdsoptimering.
Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization
{'venue': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'journal': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}