Approximation for strategic single point weighted steiner tree problem

摘要

This paper studies the strategic version of single point weighted Steiner tree problem. We focus on Bayesian mechanism design setting for the problem. We find the optimal mechanism for it and prove that the optimal mechanism is incentive compatible, individually rational but computationally inefficient. We propose a class of approximation mechanisms and prove that the mechanisms are all incentive compatible, individually rational and computationally efficient. Based on this class of mechanisms, we give a deterministic mechanism with approximation ratio of 3 and a randomized mechanism with approximation ratio of 2.54.