Optimal Budget-Feasible Mechanisms for Additive Valuations
share
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 √(2) + 2 for the weaker integral benchmark.
READ FULL TEXT