Vi utformar en förväntad polynomtid, sanningsenlig i förväntan, (1 − 1/e) - approximeringsmekanism för välfärdsmaximering i en grundläggande klass av kombinatoriska auktioner. Våra resultat gäller för budgivare med värderingar som är matroid ranksummor (MRS), som omfattar de flesta konkreta exempel på submodulära funktioner som studeras i detta sammanhang, inklusive täckning funktioner och matroid viktade-rank funktioner. Vår approximationsfaktor är den bästa möjliga, även för kända och uttryckligen givna täckningsvärderingar, förutsatt att P = NP. Vår är den första sanningsenlig-i-förväntning och polynom-tid mekanism för att uppnå en konstant-faktor approximation för en NP -hård välfärd maximering problem i kombinatoriska auktioner med heterogena varor och begränsade värderingar. Vår mekanism är en direktion av ett nytt ramverk för att utforma approximeringsmekanismer baserade på randomiserade avrundningsalgoritmer. En typisk sådan algoritm optimerar först över en fraktionerad avslappning av det ursprungliga problemet, och sedan slumpmässigt rundar den fraktionerade lösningen till en integrerad. Med sällsynta undantag kan sådana algoritmer inte omvandlas till sanningsenliga mekanismer. High-level idén med vår mekanism design ram är att optimera direkt över (slump) utgången av avrundningsalgoritmen, snarare än över indata till avrundningsalgoritmen. Detta * En fullständig version av detta dokument finns på
I REF presenteras en allmän ram som också tar upp problemets avslappning.
From convex optimization to randomized mechanisms: toward optimal combinatorial auctions
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}