Abstract-Vi studerar en ny klass av mekanism design problem där resultaten begränsas av betalningarna. Denna grundläggande klass av mekanism design problem fångar många gemensamma ekonomiska situationer, och ändå har det inte studerats, till vår kunskap, i det förflutna. Vi fokuserar på upphandling auktioner där säljare har privata kostnader, och auktionsförrättaren syftar till att maximera en nyttofunktion på undergrupper av poster, under förutsättning att summan av de betalningar som tillhandahålls av mekanismen inte överstiger en viss budget. Standard mekanism design idéer såsom VCG-mekanismen och dess varianter är inte tillämpliga här. Vi visar att budgetbegränsningen för allmänna funktioner kan göra mekanismer godtyckligt dåliga när det gäller köparens nytta. Vårt huvudsakliga resultat visar dock att det för den viktiga klassen av submodulära funktioner är möjligt att uppnå ett begränsat approximationsförhållande. Bättre approximativa resultat erhålls för underklasser av de submodulära funktionerna. Vi utforskar utrymmet för budgetgenomförbara mekanismer inom andra områden och ger en karakterisering under mer begränsade villkor.
Ramen för den budgetgenomförbara mekanismens utformning föreslogs av Singer Ref.
Budget Feasible Mechanisms
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}