Abstrakt. Motiverad av många praktiska tillämpningar, i detta dokument studerar vi budgetgenomförbara mekanismer där målet är att upphandla oberoende uppsättningar från matroider. Mer specifikt får vi en matroid M = (E, I) där varje jord (odelbart) element är ett själviskt medel. Kostnaden för varje element (dvs. för att sälja varan eller utföra en tjänst) är bara känd för själva elementet. Det finns en köpare med en budget med additiva värderingar över uppsättningen element E. Målet är att utforma en incitamentskompatibel (sann) budget genomförbar mekanism som upphandlar en oberoende uppsättning av matrisen under den givna budgeten som ger det största möjliga värdet till köparen. Vårt resultat är en deterministisk, polynomisk-tid, individuellt rationell, sanningsenlig och budget genomförbar mekanism med 4 approximation till optimal oberoende uppsättning. Sedan utvidgar vi vår mekanism till att ställa in matris skärningspunkter där målet är att upphandla gemensamma oberoende uppsättningar från flera matriser. Vi visar att med tanke på en polynomisk tidsdeterministisk blackbox som returnerar α-tillnärmningslösningar till matroid skärningsproblemet, finns det en deterministisk, polynomisk tid, individuellt rationell, sanningsenlig och budget genomförbar mekanism med (3α + 1)-tillnärmning till den optimala gemensamma oberoende uppsättningen.
Leonardi och Al. REF utforskade additivmodellen där de vinnande agenterna måste bilda ett oberoende set från en matris.
Budget Feasible Mechanisms on Matroids
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}