Optimal Budget-Feasible Mechanisms for Additive Valuations
Optimal Budget-Feasible Mechanisms for Additive Valuations
In this paper, we obtain the tight approximation guarantees for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with an 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 …