Abstrakt. Budget genomförbar mekanism design är studien av upphandling kombinatoriska auktioner där säljare har privata kostnader för att producera poster, och köparen (auctioneer) syftar till att maximera hennes värdering funktion på en delmängd av köpta poster under budgetbegränsningen på den totala betalningen. En av de viktigaste frågorna på området är "vilka värderingsområden medger sanningsenliga budgetmekanismer med "liten" approximation till det sociala optimala?" Singer [Proceedings of the 51st FOCS, IEEE Press, Piscataway, NJ, 2010, s. 765-774] visade att submodulära funktioner har en konstant approximeringsmekanism. Dobzinski, Papadimitriou och Singer [Proceedings of the 12:e ACM Conference on Electronic Commerce, ACM, New York, 2011, s. 273-282] gav en O(log 2 n) approximeringsmekanism för subadditiva funktioner och påpekade att "En grundläggande fråga är om det, oavsett beräkningsmässiga begränsningar, finns en mekanism som är genomförbar i budgeten med konstant faktor för subadditiva funktioner." I detta dokument ger vi ett positivt svar på denna fråga. I detta syfte befriar vi den tidigare fria mekanismens utformningsram från den Bayesianska mekanismens utformningsram (dessa är två standardmetoder från datavetenskap respektive ekonomi). Sedan konverterar vi våra resultat i Bayesian inställning tillbaka till det tidigare fria ramverket genom att använda Yaos minimax princip. Längs vägen får vi följande resultat: (i) en polynom tid konstant approximation för XOS värderingar (alias. Delvis subadditiva värderingar, en superuppsättning submodulära funktioner), ii) en polynomtid O(log n/ log log n)-uppskattning för allmänna subadditiva värderingar, iii) en konstant approximation för allmänna subadditiva funktioner i Bayesiens ramverk-vi tillåter korrelation i fördelningen av säljarens kostnader och tillhandahåller en universell sanningsenlig mekanism, iv) förekomsten av en mekanism för föregående-fri konstant approximation via Yaos minimax-princip.
Senare, Bei et al. REF visade att det fanns budgetgenomförbara mekanismer för O(1)-tillnärmning för den subadditive köparen.
Worst-Case Mechanism Design via Bayesian Analysis
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Computer Science']}