Mekanismdesign söker algoritmer vars ingångar tillhandahålls av själviska agenter som skulle ljuga om det vore fördelaktigt. Incitamentskompatibla mekanismer tvingar agenterna att säga sanningen genom att göra det i sitt eget intresse att göra det. Ofta, som i kombinatoriska auktioner, sådana mekanismer innebär lösningen av NP-hårda problem. Tyvärr, approximation algoritmer normalt förstör incitament kompatibilitet. Randomiserad avrundning är en vanlig teknik för att utforma approximationsalgoritmer. Vi utformar en version av randomiserad avrundning som är incitamentskompatibel, vilket ger en sanningsenlig mekanism för kombinatoriska auktioner med enstaka parameteragenter (t.ex. "ensamsinnade budgivare") som ungefär maximerar auktionens sociala värde. Vi diskuterar två ortogonala föreställningar om sannfärdighet för en randomiserad mekanism, sannfärdighet med hög sannolikhet och i förväntan, och ger en mekanism som uppnår båda samtidigt. Vi anser kombinatoriska auktioner där flera kopior av många olika objekt är till salu, och varje budgivare jag önskar en delmängd S~. Med tanke på en uppsättning anbud, problemet med att hitta fördelningen av poster som maximerar den totala värderingen är det välkända SETPACKING problemet. Detta problem är NP-hård, men för objekt med många identiska kopior kan den optimala approximeras mycket väl. För att trimma denna approximationsalgoritm till en sanningsenlig auktionsmekanism övervinner vi två problem: vi visar hur man gör tilldelningsalgoritmen monoton, och ger en metod för att beräkna lämpliga betalningar på ett effektivt sätt.
Archer m.fl. Ref beaktade ett annat fall av ensinnade anbudsgivare där flera identiska kopior finns tillgängliga för olika typer av objekt.
An approximate truthful mechanism for combinatorial auctions with single parameter agents
{'venue': "SODA '03", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}