I detta dokument presenterar vi de första approximationsalgoritmerna för problemet med att utforma intäkter optimalt Bayesian incitament kompatibla auktioner när det finns flera (heterogena) poster och när budgivare har godtycklig efterfrågan och budgetbegränsningar (och additiva värderingar). Våra mekanismer är förvånansvärt enkla: Vi visar att en sekventiell all-pay mekanism är en 4 approximation till intäkterna från den optimala ex-interim sanningsenliga mekanismen med en diskret typ utrymme för varje budgivare, där hennes värderingar för olika poster kan korreleras. Vi visar också att en sekventiell postad prismekanism är en O(1) approximation till intäkterna från den optimala i efterhand sanningsenliga mekanismen när typutrymmet för varje budgivare är en produktfördelning som uppfyller standardriskräntan villkor. Vi visar vidare en logaritmisk approximation när risknivåns tillstånd tas bort, och fullbordar bilden genom att visa att det krävs prispaket med objekt för att uppnå en sublogaritmisk approximation, även för regelbundna distributioner och en budgivare. Våra resultat är baserade på att formulera nya LP lättnader för dessa problem, och utveckla generiska avrundning system från första principer.
För en särskild form av kombinatoriska auktioner med hårda budgetbegränsningar presenterar REF en all pay BIC-mekanism och en sekventiell postad prissättningsmekanism.
Budget constrained auctions with heterogeneous items
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}