Optimal Budget-Feasible Mechanisms for Additive Valuations
Optimal Budget-Feasible Mechanisms for Additive Valuations
In this article, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio of 2, improving the previous best known result of 3. Our bound is tight with respect to either the optimal offline benchmark or its …