Optimal Budget-Feasible Mechanisms for Additive Valuations

Nick Gravin, Yaonan Jin, Pinyan Lu, Chenhao Zhang

In this paper, we obtain 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 fractional relaxation. We also present a simple deterministic mechanism with the tight approximation guarantee of $3$ against the fractional optimum, improving the best known result of $\sqrt{2} + 2$ for the weaker integral benchmark.

Knowledge Graph



Sign up or login to leave a comment