I kombinatoriska offentliga projekt finns det en uppsättning projekt som kan genomföras, och en uppsättning självintresserade aktörer med en andel i den uppsättning projekt som väljs. En offentlig planerare måste välja en delmängd av dessa projekt, med förbehåll för en resursbegränsning, med målet att maximera social välfärd. Kombinatoriska offentliga projekt har dykt upp som ett av de paradigmiska problemen i Algoritmisk Mechanism Design, ett område som handlar om att lösa grundläggande resursfördelningsproblem i närvaro av både själviskt beteende och den beräkningsmässiga begränsningen av polynom tid. Vi utformar en polynom-tid, sanningsenlig-in-förväntning, (1−1/e)-tillnärmningsmekanism för välfärdsmaximering i en grundläggande variant av kombinatoriska offentliga projekt. Våra resultat gäller kombinatoriska offentliga projekt när spelare har värderingar som är matriser ranksummor (MRS), som omfattar de flesta konkreta exempel på submodulära funktioner som studeras i detta sammanhang, inklusive täckning funktioner och matris viktade rank funktioner. Vår approximationsfaktor är den bästa möjliga, förutsatt att P = NP. Vår är den första mekanismen som uppnår en konstant faktor approximation för en naturlig NP-hård variant av kombinatoriska offentliga projekt.
Vårt arbete är relaterat till att utforma sanningsenliga mekanismer för kombinatoriska offentliga projekt REF.
A truthful randomized mechanism for combinatorial public projects via convex optimization
{'venue': "EC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}